Класс линейных функций

Костромской Государственный  Университет им. Некрасова

Кафедра Прикладной математики и информатики

 

 

 

 

 

 

 

 

 

Курсовая работа по теме:

«Класс линейных функций»

 

 

 

 

 

 

    Выполнила:

студентка 3го курса

физико-математического

       факультета

Лебедева Е.А. Преподаватель:

Сидоров А.В.

 

 

Кострома 2012

 

Содержание

 

• Введение
• Теоретическая часть
• Практическая часть
• Заключение
• Список использованной литературы и ресурсов интернета

 

 

 

Введение

 

Используемые обозначения:

A + B  дизъюнкция

A & B, AB конъюнкция

A→B  следование

A ~ B  эквиваленция

⌐A   отрицание

A ⊕ B  сложение по модулю 2

F   функция

L  класс линейных функций

 

Теоретическая часть

 

Булева функция  называется линейной, если она представима полиномом первой степени

F(x₁,x₂,…,x_n) = k₀ ⊕ k₁x₁ ⊕ k₂x₂ ⊕ … ⊕ k_nx_n

Количество  линейных функций равно 2 в степени n + 1, где п – число переменных.

Для п = 2 их 8:

F₁(x₁,x₂) = 0,  F₂(x₁,x₂) = x₁, F₃(x₁,x₂) = x₂, F₄(x₁,x₂) = x₁ ⊕ x₂, F₅(x₁,x₂) = 1 ⊕ x₁,  F₆(x₁,x₂) = 1 ⊕ x₂,  F₇(x₁,x₂) = 1 ⊕ x₁ ⊕ x₂,  F₈(x₁,x₂) = 1.

Полином Жегалкина — полином (многочлен) над  , то есть полином с коэффициентами вида 0 и 1, где в качестве произведения берется конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве удобного средства для представления функций булевой логики.

Полином Жегалкина представляет собой  сумму по модулю два (операция «исключающее или») произведений неинвертированных  переменных, а также (если необходимо) константы 1.

Дизъюнктивная нормальная форма (ДНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Любая булева формула может быть приведена к ДНФ.

Конъюнктивная нормальная форма (ДНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литералов. Любая булева формула может быть приведена к ДНФ.

 

Совершенной ДНФ (СДНФ) называется ДНФ, в которой нет равных элементарных конъюнкций и все элементарные конъюнкции содержат одни и те же переменные, причем каждую переменную – только один раз (включая вхождения под знаком отрицания).

Совершенная КНФ (СКНФ) определяется как КНФ, в которой нет одинаковых сомножителей; все сомножители содержат одни и те же переменные, причем каждую переменную – только один раз.

 

Практическая часть

 

 №1.

1. x→y = (x ⊕ 1) + y = (x ⊕ 1)y ⊕ x ⊕ 1 ⊕ y = xy ⊕ x ⊕ 1,

F не принадлежит L

2. ⌐(x→y) ⊕ (⌐x)y = ⌐(xy ⊕ x ⊕ y ⊕ 1) ⊕ (x ⊕ 1)y = (⌐x ⊕ ⌐y) & x & y & 0 ⊕ (x ⊕ 1)y = xy ⊕ y, F принадлежит L
3. x(⌐y) & (x ~ y) = x(y ⊕ 1) & (x ⊕ y ⊕ 1) = (xy ⊕ x)x ⊕ (xy ⊕ x)y ⊕ (xy ⊕ x)1 = xy ⊕ xy ⊕ xy ⊕ xy ⊕ x = x, F принадлежит L
4. xy + (⌐x)(⌐y) = xy + (x ⊕ 1)(y ⊕ 1) = xy + (xy ⊕ x ⊕ y ⊕ 1) = xy & (xy ⊕ x ⊕ y ⊕ 1) ⊕ xy ⊕ (xy ⊕ x ⊕ y ⊕ 1) = xy ⊕ xy ⊕ xy ⊕ xy ⊕ xy ⊕ xy ⊕ x ⊕ y ⊕ 1, F не принадлежит L
5. (xy + (⌐x)(⌐y))z + (⌐z)((⌐x)y + x(⌐y)) = (xy ⊕ (x ⊕ 1)(y ⊕ 1))z ⊕ (z ⊕ 1)(x ⊕ y) = (xy ⊕ xy ⊕ x ⊕ y ⊕ 1)z ⊕ x ⊕ y ⊕ xz ⊕ yz = xyz ⊕ xyz ⊕ xz ⊕ yz ⊕ z ⊕ x ⊕ y ⊕ xz ⊕ yz = x ⊕ y ⊕ z, F принадлежит L
6. ((x→y)(y→x)) ~ z = ((xy ⊕ x ⊕ 1)(xy ⊕ y ⊕ 1)) ~ z = (xy ⊕ y ⊕ xy ⊕ x ⊕ xy ⊕ x ⊕ xy ⊕ y ⊕ 1) ~ z, F принадлежит L
7. xy(⌐z) + x(⌐y ) = xy(z ⊕ 1) ⊕ x(y ⊕ 1) = (xyz ⊕ xy) ⊕ (xy ⊕ x) = xyz ⊕ x, F не принадлежит L
8. xyz ⊕ xy(⌐z) ⊕ (⌐x)y = xyz ⊕ xy(z ⊕ 1) ⊕ (x ⊕ 1)y = xyz ⊕ (xyz ⊕ xy) ⊕ xy ⊕ y = y, F принадлежит L
9. m(x,y,z) ⊕ (⌐x)(⌐y)(⌐z) ⊕ xyz = m(x,y,z) ⊕ (x ⊕ 1)(y ⊕ 1)(z ⊕ 1) ⊕ xyz = m(x,y,z) ⊕ xyz ⊕ xyz ⊕ xy ⊕ xz ⊕ z ⊕ 1 ⊕ yz, F принадлежит L
10. (x + yz) ⊕ xyz = xyz ⊕ x ⊕ yz ⊕ xyz = yz ⊕ x, F не принадлежит L
11. (x + yz) ⊕ (⌐x)yz = (x ⊕ yz ⊕ xyz) ⊕ (x ⊕ 1)yz = x ⊕ yz ⊕ xyz ⊕ yz ⊕ xyz = x, F принадлежит L
12. (xyz + x(⌐y)(⌐z)) ⊕ x(y ⊕ z) = (xyz ⊕ x(y ⊕ 1)(z ⊕ 1)) ⊕ xy ⊕ xz = xyz ⊕ xyz ⊕ xy ⊕ xz ⊕ x = xy ⊕ xz ⊕ x, F не принадлежит L
13. (xyz ⊕ x(⌐y)(⌐z)) ⊕ x(y + z) = xyz ⊕ x((y ⊕ 1)(z ⊕ 1)) ⊕ xy ⊕ xz ⊕ xyz = xyz ⊕ xyz ⊕ xy ⊕ xz ⊕ x ⊕ xy ⊕ xz, F принадлежит L
14. (xyz ⊕ (⌐x)(⌐y)z) + (⌐x)(⌐y)z + (x(⌐y)z ⊕ (⌐x)yz) = xyz ⊕ (x ⊕ 1)(y ⊕ 1)z + (x ⊕ 1)(y ⊕ 1)z ⊕ x(y ⊕ 1)z + ((x ⊕ 1)yz ⊕ x(x ⊕ 1)(y ⊕ 1)) = ((xyz ⊕ xyz ⊕ xz ⊕ yz ⊕ z) ⊕ (xyz ⊕ xz ⊕ yz ⊕ z) ⊕ (xyz ⊕ xyz ⊕ xz ⊕ yz ⊕ z)) & (xyz ⊕ xz ⊕ yz ⊕ z) & ((x ⊕ 1)yz ⊕ x(x ⊕ 1)(y ⊕ 1)) ⊕ ((x ⊕ 1)yz ⊕ x(x ⊕ 1)(y ⊕ 1)) ⊕ ((xyz ⊕ xyz ⊕ xz ⊕ yz ⊕ z) ⊕ (xyz ⊕ xz ⊕ yz ⊕ z) ⊕ (xyz ⊕ xyz ⊕ xz ⊕ yz ⊕ z) & (xyz ⊕ xz ⊕ yz ⊕ z)), F принадлежит L
15. ((⌐x)(⌐y)(⌐z) ~ xy(⌐z)) ~ ((x(⌐y)z) ~ (⌐x)yz) = (x ⊕ 1)(y ⊕ 1)(z ⊕ 1) ~ xy(z ⊕ 1) ~ xz(y ⊕ 1) ~ (x ⊕ 1)yz = (xyz ⊕ xy ⊕ yz ⊕ y ⊕ z ⊕ xz ⊕ x ⊕ 1) ~ (xyz ⊕ xy ~ xyz ⊕ xz ~ xyz ⊕ yz), F не принадлежит L

Прим. & - дизъюнкция

Вывод: 1,4,7,10,12,15 не принадлежат  L; 2,3,5,6,8,9,11,13,14 принадлежат L.

 

№2.

Прим. Сложение по модулю два  (⊕) можно выразить через дизъюнкцию, конъюнкцию и отрицание:

⌐AB + B⌐A = A ⊕ B,  ⌐A = 1 ⊕ A,

A + B = (A⊕1)(B⊕1) ⊕ 1 = AB ⊕ A ⊕ B

Для получения канонического  полинома Жегалкина заменим в  СДНФ ⌐A на 1 ⊕ A = ⌐A и преобразуем полученное выражение, используя распределительный закон конъюнкции относительно сложения по модулю два, и учитывая, что A ⊕ A = 0, A ⊕ 0 = A.

 

1)

0	0	1	⌐x⌐y
0	1	0
1	0	0
1	1	1	xy

СДНФ: (⌐x⌐y) + (xy)

Многочлен Жегалкина: (x ⊕ 1)(y ⊕ 1) + xy = xy ⊕ x ⊕ y ⊕ 1 + xy = (xy ⊕ x ⊕ y ⊕ 1)xy ⊕ xy ⊕ (xy ⊕ x ⊕ y ⊕ 1)= xy ⊕ x ⊕ y ⊕ 1

 

2)

0	0	1	⌐x⌐y
0	1	1	(⌐x)y
1	0	0
1	1	1	Xy

СДНФ: (⌐x⌐y) + (xy) + ((⌐x)y)

Многочлен Жегалкина: xy ⊕ x ⊕ y ⊕ 1 ⊕ (x ⊕ 1)y = xy ⊕ x ⊕ y ⊕ 1 ⊕ xy ⊕ y = x ⊕ 1

 

3)

0	0	0	1	⌐x⌐y⌐z
0	0	1	0
0	1	0	0
0	1	1	1	(⌐x)yz
1	0	0	0
1	0	1	1	x(⌐y)z
1	1	0	1	xy(⌐z)
1	1	1	0

СДНФ: (⌐x⌐y⌐z) + (⌐x)yz + (x(⌐y)z) + xy(⌐z)

Многочлен Жегалкина: (x ⊕ 1)(y ⊕ 1)(z ⊕ 1) + (x ⊕ 1)yz + x(y ⊕ 1)z + xy(z ⊕ 1) = xyz ⊕ xz ⊕ yz ⊕ z ⊕ xy ⊕ x ⊕ y ⊕ 1 + xyz ⊕ yz + xyz ⊕ xz + xyz ⊕ xy = (xyz ⊕ xy ⊕ yz ⊕ xz ⊕ x ⊕ y ⊕ z ⊕ 1) + xyz(yz ⊕ xy ⊕ xz) =  (xyz ⊕ xy ⊕ yz ⊕ xz ⊕ x ⊕ y ⊕ z ⊕ 1)xyz(yz ⊕ xy ⊕ xz) ⊕ xyz(yz ⊕ xy ⊕ xz) ⊕ (xyz ⊕ xy ⊕ yz ⊕ xz ⊕ x ⊕ y ⊕ z ⊕ 1) = xyz ⊕ xy ⊕ yz ⊕ xz ⊕ x ⊕ y ⊕ z ⊕ 1

 

4)

0	0	0	1	⌐x⌐y⌐z
0	0	1	1	⌐x⌐yz
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	1	xy(⌐z)
1	1	1	1	xyz

СДНФ: (⌐x⌐y⌐z) + ⌐x⌐yz + xy(⌐z) + xyz

Многочлен Жегалкина: xyz ⊕ xz ⊕ yz ⊕ z ⊕ xy ⊕ x ⊕ y ⊕ 1 + (x ⊕ 1)(y ⊕ 1)z + xy(z ⊕ 1) + xyz = xyz ⊕ xz ⊕ yz ⊕ z ⊕ xy ⊕ x ⊕ y ⊕ 1 + xyz ⊕ xz ⊕ yz ⊕ z + xyz ⊕ xy + xyz = (xyz ⊕ xy ⊕ yz ⊕ xz ⊕ x ⊕ y ⊕ z ⊕ 1)(xyz ⊕ xz ⊕ yz ⊕ z) ⊕ (xyz ⊕ xz ⊕ yz ⊕ z) ⊕ (xyz ⊕ xy ⊕ yz ⊕ xz ⊕ x ⊕ y ⊕ z ⊕ 1) + xyz(xyz ⊕ xy) ⊕ xyz ⊕ (xyz ⊕ xy) = (xyz ⊕ xy ⊕ yz ⊕ xz ⊕ x ⊕ y ⊕ z ⊕ 1)(xyz ⊕ xz ⊕ yz ⊕ z) ⊕ (xyz ⊕ xz ⊕ yz ⊕ z) ⊕ (xyz ⊕ xy ⊕ yz ⊕ xz ⊕ x ⊕ y ⊕ z ⊕ 1)

 

5)

0	0	0	1	⌐x⌐y⌐z
0	0	1	0
0	1	0	1	⌐xy⌐z
0	1	1	0
1	0	0	0
1	0	1	1	x⌐yz
1	1	0	0
1	1	1	1	Xyz

СДНФ: (⌐x⌐y⌐z) + ⌐xy⌐z + x⌐yz + xyz

Многочлен Жегалкина: xyz ⊕ xz ⊕ yz ⊕ z ⊕ xy ⊕ x ⊕ y ⊕ 1 + (x ⊕ 1)(z ⊕ 1)y + xz(y ⊕ 1) + xyz = (xyz ⊕ xz ⊕ yz ⊕ z ⊕ xy ⊕ x ⊕ y ⊕ 1) ⊕ (xyz ⊕ y ⊕ xy ⊕ yz) ⊕ (xyz ⊕ xz ⊕ yz ⊕ z ⊕ xy ⊕ x ⊕ y ⊕ 1) (xyz ⊕ y ⊕ xy ⊕ yz) + xyz ⊕ xz= (xyz ⊕ xz ⊕ xy ⊕ yz ⊕ x ⊕ y ⊕ z ⊕ 1) ⊕ (xyz ⊕ xz) ⊕ (xyz ⊕ xz ⊕ xy ⊕ yz ⊕ x ⊕ y ⊕ z ⊕ 1)

 

6)

0	0	0	1	⌐x⌐y⌐z
0	0	1	0
0	1	0	1	⌐xy⌐z
0	1	1	0
1	0	0	0
1	0	1	1	x⌐yz
1	1	0	1	xy⌐z
1	1	1	0

СДНФ: (⌐x⌐y⌐z) + ⌐xy⌐z + x⌐yz + xy⌐z

Многочлен Жегалкина: xyz ⊕ xz ⊕ yz ⊕ z ⊕ xy ⊕ x ⊕ y ⊕ 1 + (x ⊕ 1)(z ⊕ 1)y + xy(z ⊕ 1) + xyz = (xyz ⊕ xz ⊕ yz ⊕ z ⊕ xy ⊕ x ⊕ y ⊕ 1) ⊕ (xyz ⊕ y) ⊕ (xyz ⊕ xz ⊕ yz ⊕ z ⊕ xy ⊕ x ⊕ y ⊕ 1)(xyz ⊕ y) + (xyz ⊕ xy) ⊕ xyz ⊕ xyz ⊕ xyz = ((xyz ⊕ xz ⊕ yz ⊕ z ⊕ xy ⊕ x ⊕ y ⊕ 1) ⊕ (xyz ⊕ y) ⊕ (xyz ⊕ xz ⊕ yz ⊕ z ⊕ xy ⊕ x ⊕ y ⊕ 1)(xyz ⊕ y)) ⊕ (xyz ⊕ xz ⊕ yz ⊕ z ⊕ xy ⊕ x ⊕ y ⊕ 1) ⊕ (xyz ⊕ y) ⊕ (xyz ⊕ xz ⊕ yz ⊕ z ⊕ xy ⊕ x ⊕ y ⊕ 1)(xyz ⊕ y) ⊕ xyz

 

7)

0	0	0	0	1	⌐x⌐y⌐z⌐q
0	0	0	1	1	⌐x⌐y⌐zq
0	0	1	0	0
0	0	1	1	0
0	1	0	0	1	⌐xy⌐z⌐q
0	1	0	1	0
0	1	1	0	0
0	1	1	1	1	⌐xyzq
1	0	0	0	0
1	0	0	1	1	x⌐y⌐zq
1	0	1	0	1	x⌐yz⌐q
1	0	1	1	0
1	1	0	0	1	xy⌐z⌐q
1	1	0	1	0
1	1	1	0	0
1	1	1	1	1	Xyzq

СДНФ: (⌐x⌐y⌐z⌐q) + (⌐x⌐y⌐zq) + (⌐xy⌐z⌐q) + (⌐xyzq) + (x⌐y⌐zq) + (x⌐yz⌐q) + (xy⌐z⌐q) + xyzq

Многочлен Жегалкина: (x ⊕ 1)(y ⊕ 1)(z ⊕ 1)(q ⊕ 1) ⊕ (x ⊕ 1)(y ⊕ 1)(z ⊕ 1)q ⊕ (x ⊕ 1)y(z ⊕ 1)(q ⊕ 1) ⊕ (x ⊕ 1)yzq ⊕ x(y ⊕ 1)(z ⊕ 1)q ⊕ x(y ⊕ 1)z(q ⊕ 1) ⊕ xy(z ⊕ 1)(q ⊕ 1) = (x ⊕ 1)(y ⊕ 1)(z ⊕ 1)(q ⊕ 1) ⊕ x(y ⊕ 1)(zq ⊕ z ⊕ q) ⊕ (x ⊕ 1)(xzq ⊕ xz ⊕ xq ⊕ yzq) = xyzq ⊕ xyz ⊕ xyq ⊕ xzq ⊕ xy ⊕ yz ⊕ zq ⊕ xq ⊕ yq ⊕ xz ⊕ x ⊕ y ⊕ z ⊕ q ⊕ 1

 

8)

0	0	0	0
0	0	1	1	⌐x⌐yz
0	1	0	1	⌐xy⌐z
0	1	1	0
1	0	0	1	x⌐y⌐z
1	0	1	0
1	1	0	0
1	1	1	1	Xyz

 
СДНФ: ⌐x⌐yz + ⌐xy⌐z + x⌐y⌐z + xyz

Многочлен Жегалкина: (x ⊕ 1)(y ⊕ 1)z + (x ⊕ 1)y(z ⊕ 1) + x(y ⊕1)(z ⊕ 1) + xyz = (xyz ⊕ xz ⊕ yz ⊕ z) ⊕ (xyz ⊕ xy ⊕ yz ⊕ y) ⊕ (xyz ⊕ xz ⊕ yz ⊕ z)(xyz ⊕ xy ⊕ yz ⊕ y) ⊕ (xyz ⊕ xy ⊕ xz ⊕ x) ⊕ xyz ⊕ (xyz ⊕ xy ⊕ xz ⊕ x)xyz

 

9)

0	0	0	0	1	⌐x⌐y⌐z⌐q
0	0	0	1	0
0	0	1	0	0
0	0	1	1	1	⌐x⌐yzq
0	1	0	0	0
0	1	0	1	1	⌐xy⌐zq
0	1	1	0	1	⌐xyz⌐q
0	1	1	1	0
1	0	0	0	0
1	0	0	1	1	x⌐y⌐zq
1	0	1	0	1	x⌐yz⌐q
1	0	1	1	0
1	1	0	0	1	xy⌐z⌐q
1	1	0	1	0
1	1	1	0	0
1	1	1	1	1	Xyzq

СДНФ: ⌐x⌐y⌐z⌐q + ⌐x⌐yzq + ⌐xy⌐zq + ⌐xyz⌐q + x⌐y⌐zq + xy⌐z⌐q + x⌐yz⌐q + xyzq

Многочлен Жегалкина: (x ⊕ 1)(y ⊕ 1)(z ⊕ 1)(q ⊕ 1) ⊕ (x ⊕ 1)(y ⊕ 1)zq ⊕ (x ⊕ 1)y(z ⊕ 1)q ⊕ (x ⊕ 1)yz(q ⊕ 1) ⊕ x(y ⊕ 1)(z ⊕ 1)q ⊕ xy(z ⊕ 1)(q ⊕ 1) ⊕ x(y ⊕ 1)z(q ⊕ 1) ⊕ xyzq = (xyzq ⊕ xyq ⊕ xzq ⊕ yzq ⊕ xq ⊕ yq ⊕ zq ⊕ q ⊕ xyz ⊕ xy ⊕ yz ⊕ xz ⊕ x ⊕ y ⊕ 1 ⊕ z) ⊕ (xyzq ⊕ xzq ⊕ yzq ⊕ zq) ⊕ (xzyq ⊕ xyq ⊕ zyq ⊕ yq) ⊕ (xqyz ⊕ xyz ⊕ qyz ⊕ yz) ⊕ (xyzq ⊕ yxq ⊕ zxq ⊕ xq) ⊕ (xyzq ⊕ zxy ⊕ qxy ⊕ xy) ⊕ (xyzq ⊕ yxz ⊕ qxz ⊕ xz) ⊕ xyzq

 

10)

0	0	0	0	0
0	0	0	1	1	⌐x⌐y⌐zq
0	0	1	0	1	⌐x⌐yz⌐q
0	0	1	1	0
0	1	0	0	1	⌐xy⌐z⌐q
0	1	0	1	0
0	1	1	0	0
0	1	1	1	1	⌐xyzq
1	0	0	0	0
1	0	0	1	1	x⌐y⌐zq
1	0	1	0	1	x⌐yz⌐q
1	0	1	1	0
1	1	0	0	1	xy⌐z⌐q
1	1	0	1	0
1	1	1	0	0
1	1	1	1	1	Xyzq