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

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

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

 

 

 

 

 

 

 

 

 

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

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

 

 

 

 

 

 

    Выполнила:

студентка 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

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

Многочлен Жегалкина: (x ⊕ 1)(y ⊕ 1)(z ⊕ 1)q ⊕ (x ⊕ 1)(y ⊕ 1)z(q ⊕ 1) ⊕ (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) ⊕ xyzq = xyzq ⊕ xyq ⊕ xzq ⊕ yzq ⊕ q ⊕ xyzq ⊕ xyz ⊕ xzq ⊕ yq ⊕ xz ⊕ yz ⊕ qz ⊕ z ⊕ xyzq ⊕ xyz ⊕ xyq ⊕ zq ⊕ xy ⊕ yz ⊕ qy ⊕ y ⊕ xyzq ⊕ yzq ⊕ (xyzq ⊕ yxq ⊕ zxq ⊕ xq) ⊕ (xyzq ⊕ yxz ⊕ qxz ⊕ xz) ⊕ (xyzq ⊕ zxy ⊕ qxy ⊕ xy) ⊕ xyzq

 

11)

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

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

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

 

12)

0	0	0	0	1	⌐x⌐y⌐z⌐q
0	0	0	1	0
0	0	1	0	1	⌐x⌐yz⌐q
0	0	1	1	0
0	1	0	0	0
0	1	0	1	1	⌐xy⌐zq
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	0
1	0	1	1	1	x⌐yzq
1	1	0	0	1	xy⌐z⌐q
1	1	0	1	0
1	1	1	0	1	xyz⌐q
1	1	1	1	0

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

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

 

13)

0	0	0	0	1	⌐x⌐y⌐z⌐q
0	0	0	1	0
0	0	1	0	1	⌐x⌐yz⌐q
0	0	1	1	0
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	0
1	1	0	1	1	xy⌐zq
1	1	1	0	0
1	1	1	1	1	Xyzq

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

 

14)

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

Многочлен Жегалкина: (x ⊕ 1)(y ⊕ 1)z(q ⊕ 1) ⊕ (x ⊕ 1)(y ⊕ 1)zq ⊕ (x ⊕ 1)y(z ⊕ 1)(q ⊕ 1) ⊕ (x ⊕ 1)y(z ⊕ 1)q ⊕ x(y ⊕ 1)(z ⊕ 1)(q ⊕ 1) ⊕ x(y ⊕ 1)(z ⊕ 1)q ⊕ xyz(q ⊕ 1) ⊕ xyzq = (xyzq ⊕ xyz ⊕ xzq ⊕ yq ⊕ xz ⊕ yz ⊕ qz ⊕ z) ⊕ (xyzq ⊕ xzq ⊕ yzq ⊕ zq)⊕ (xyzq ⊕ xyz ⊕ xyq ⊕ zq ⊕ xy ⊕ yz ⊕ qy ⊕ y) ⊕ (xzyq ⊕ xyq ⊕ zyq ⊕ yq) ⊕(xyzq⊕ xyq ⊕ xzq ⊕ yzx ⊕ xq ⊕ yx ⊕ zx ⊕ x) ⊕ (xyzq ⊕ yxq ⊕ zxq ⊕ xq) ⊕ (xyzq ⊕ xyz) ⊕ xyzq

 

15)

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	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	⌐xy⌐zq
1	0	1	1	0
1	1	0	0	0
1	1	0	1	1	xy⌐zq
1	1	1	0	1	xyz⌐q
1	1	1	1	0

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

 

Ответ: 1,3-5,7-15 принадлежат L; 2,6 принадлежат L.

 

 

№3.

1. F(00) = c = 1, F(01) = 0, F(10) = 0, F(11) = 1, (1001)

F = x₁ ⊕ x₂ ⊕ 1

2. F(00) = 0, F(01) = 0, F(10) = 1, F(11) = 1, (0011)

F = x₁

3. F(00) = c = 1, F(01) = 0, F(10) = 0, F(11) = 1, F(100) = 0, F(101) = 1, F(110) = 1, F(111) = 0, (10010110)

F = x₁ ⊕ x₂ ⊕ x₃ ⊕ 1

4. F(00) = c = 1, F(01) = 0, F(10) = 0, F(11) = 1, F(100) = 0, F(101) = 1, F(110) = 1, F(111) = 0, (10010110)

F = x₁ ⊕ x₂ ⊕ x₃ ⊕ 1

5. F(00) = 1, F(01) = 0, F(10) = 1, F(11) = 0, F(100) = 1, F(101) = 0, F(110) = 1, F(111) = 0, (10101010)

F = x₃ ⊕ 1

6. F(00) = 0, F(01) = 1, F(10) = 1, F(11) = 0, F(100) = 1, F(101) = 0, F(110) = 1, F(111) = 0, (01101010)

F = x₁ ⊕ x₂

9) F(00) = 1, F(01) = 0, F(10) = 1, F(11) = 0, F(100) = 0, F(101) = 1, F(110) = 0, F(111) = 1, F(1000) = 0, F(1001) = 1, F(1010) = 0, F(1011) = 1, F(1100) = 1, F(1101) = 0, F(1110) = 1, F(1111) = 0, (1010010101011010)

F = x₁ ⊕ x₂ ⊕ x₄ ⊕ 1

10) F(00) = 1, F(01) = 0, F(10) = 0, F(11) = 1, F(100) = 1, F(101) = 0, F(110) = 1, F(111) = 0, F(1000) = 0, F(1001) = 1, F(1010) = 0, F(1011) = 1, F(1100) = 0, F(1101) = 1, F(1110) = 0, F(1111) = 1, (1001101001010101)

F = x₁ ⊕ x₃ ⊕ x₄ ⊕ 1

 

№4.

1. F(x³) = x₁x₂ + x₂(⌐x₃) + (⌐x₃)x₁

F(x,y,1) = xy + y(⌐1) + (⌐1)x = xy + y(0) + x(0) = xy

F(x,y,y) = xy + y(⌐y) + (⌐y)x = xy + (⌐y)x = xy

 

11) F = (x₁ + x₂ + x₃)(⌐x₁ + ⌐x₂ + ⌐x₃ + x₄)

F(x,x,x,y) = (x + x + x)(⌐x + ⌐x + ⌐x + y) = x(⌐x) + x(⌐x) + x(⌐x) + x(⌐x) + x(⌐x) + x(⌐x) + x(⌐x) + x(⌐x) + xy + xy + xy = xy

 

12) F = (x₁ + ⌐x₂ + ⌐x₃ + ⌐x₄) (⌐x₁ + ⌐x₂ + x₃ + x₄) (⌐x₂ + x₃)

F(x,1,y,1) = (x + ⌐1 + ⌐y + ⌐1) (⌐x + ⌐1 + y + 1) (⌐1 + y) = x(⌐x) + x(0) + xy + x + (⌐y)( ⌐x) + (⌐y) = xy

 

№5.

8) F = ( x₁⌐x₂ + (⌐x₁)x₂x₃) ⊕ (⌐x₁)x₂x₃ = … = x₁(⌐x₂) + x₁(⌐x₂)x₃ + (⌐x₁)x₂x₃ не принадлежит L → нельзя представить в виде xy

 

№6.

1. ,

a₁,…, a_n-1 – произвольный набор значений переменных

F(a₁,…, a_n-1) = x_n ⊕ φ(a₁,…, a_n-1) → F(a₁,…, a_n-1,0) < > F(a₁,…, a_n-1,1), противоречие

2. F = x_ng ⊕ h , g< >0

Если g< >1 → существует набор a = (a₁,…, a_n-1): g(a) = 0 → F(a₁,…, a_n-1,0) < > F(a₁,…, a_n-1,1) = h(a) → g = 1

 

№10.

Количество (F( )) = 2С_n^k = 2n!/(n-k)!k!

 

№11.

Число линейных функций таких, что значение функции на единичном  наборе равно значению функции на нулевом наборе и равно единице?

Общее число: 2^{n + 1}, минус два набора.

Ответ: 2^n-1.

 

№12.

F(x₁,x₂,0,…,0) = x₁→x₂

F принадлежит L → x₁→x₂ = F(x₁,x₂,0,…,0) принадлежит L, противоречие → F не принадлежит L

 

№13.

F(x,0,…,0) < > F(x,1,…,1), n = 2k + 1

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

Пусть F принадлежит L →

F = x₁ ⊕ … ⊕ x_n ⊕ δ, δ принадлежит (0,1)

F(x,0,…,0) < > F(x,1,…,1) → n = 2k → F не принадлежит L

 

№14.

F не принадлежит L → существуют i, j: F = x_ix_jφ₁ ⊕ x_iφ₂ ⊕ x_jφ₃ ⊕ φ4, φ_1,2,3,4 не зависят от i, j и φ₁< >0. Пусть существует такой набор (a₁,…, a_i-1, a_{i + 1},…, a_j-1, a_{j + 1},…, a_n), что значение функции φ₁ на этом наборе равно 1 → ψ(x_i,x_j) = (a₁,…, a_i-1, x_i , a_{i + 1},…, a_j-1, x_j ,a_{j + 1},…, a_n) не принадлежит L.

 

№15.

Пусть функция F( ): наборы α, β, γ, δ: F(α) = F(β) = F(γ) = F(δ) = 1 при n = 2k + 1 раз. Пусть x_m = a_m → m принадлежит A₂. Если m принадлежит A₁, то x_m = x при γ_m = 1 и x_m = y при γ_m = 0. Результат: функция φ(x,y): φ(11) = F(α), φ(00) = F(β), φ(10) = F(γ), φ(01) = F(δ), φ(x,y) не принадлежит L.

 

 №19.

F принадлежит L → F принадлежит S∩L, если зависит от n = 2k + 1, иначе, F на нулевом наборе = 0, 1 не принадлежит [{F}] или F на нулевом наборе = 1, 0 не принадлежит [{F}].

 

 

 

 

 

 

 

 

 

 

 

 

 

Список используемой литературы и ресурсов интернета

 

1. Гаврилов, Сапоженко – Сборник задач по дискретной математике
2. ru.wikipedia.org