Автор работы: Пользователь скрыл имя, 17 Февраля 2013 в 09:54, курсовая работа
Используемые обозначения:
A + B дизъюнкция
A & B, AB конъюнкция
A→B следование
A ~ B эквиваленция
⌐A отрицание
A ⊕ B сложение по модулю 2
F функция
L класс линейных функций
Введение
Теоретическая часть
Практическая часть
Заключение
Список использованной литературы и ресурсов интернета
СДНФ: ⌐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.
F = x1 ⊕ x2 ⊕ 1
F = x1
F = x1 ⊕ x2 ⊕ x3 ⊕ 1
F = x1 ⊕ x2 ⊕ x3 ⊕ 1
F = x3 ⊕ 1
F = x1 ⊕ x2
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 = x1 ⊕ x2 ⊕ x4 ⊕ 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 = x1 ⊕ x3 ⊕ x4 ⊕ 1
№4.
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 = (x1 + x2 + x3)(⌐x1 + ⌐x2 + ⌐x3 + x4)
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 = (x1 + ⌐x2 + ⌐x3 + ⌐x4) (⌐x1 + ⌐x2 + x3 + x4) (⌐x2 + x3)
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 = ( x1⌐x2 + (⌐x1)x2x3) ⊕ (⌐x1)x2x3 = … = x1(⌐x2) + x1(⌐x2)x3 + (⌐x1)x2x3 не принадлежит L → нельзя представить в виде xy
№6.
a1,…, an-1 – произвольный набор значений переменных
F(a1,…, an-1) = xn ⊕ φ(a1,…, an-1) → F(a1,…, an-1,0) < > F(a1,…, an-1,1), противоречие
Если g< >1 → существует набор a = (a1,…, an-1): g(a) = 0 → F(a1,…, an-1,0) < > F(a1,…, an-1,1) = h(a) → g = 1
№10.
Количество (F( )) = 2Сnk = 2n!/(n-k)!k!
№11.
Число линейных функций таких, что значение функции на единичном наборе равно значению функции на нулевом наборе и равно единице?
Общее число: 2n + 1, минус два набора.
Ответ: 2n-1.
№12.
F(x1,x2,0,…,0) = x1→x2
F принадлежит L → x1→x2 = F(x1,x2,0,…,0) принадлежит L, противоречие → F не принадлежит L
№13.
F(x,0,…,0) < > F(x,1,…,1), n = 2k + 1
F не принадлежит L
Пусть F принадлежит L →
F = x1 ⊕ … ⊕ xn ⊕ δ, δ принадлежит (0,1)
F(x,0,…,0) < > F(x,1,…,1) → n = 2k → F не принадлежит L
№14.
F не принадлежит L → существуют i, j: F = xixjφ1 ⊕ xiφ2 ⊕ xjφ3 ⊕ φ4, φ1,2,3,4 не зависят от i, j и φ1< >0. Пусть существует такой набор (a1,…, ai-1, ai + 1,…, aj-1, aj + 1,…, an), что значение функции φ1 на этом наборе равно 1 → ψ(xi,xj) = (a1,…, ai-1, xi , ai + 1,…, aj-1, xj ,aj + 1,…, an) не принадлежит L.
№15.
Пусть функция F( ): наборы α, β, γ, δ: F(α) = F(β) = F(γ) = F(δ) = 1 при n = 2k + 1 раз. Пусть xm = am → m принадлежит A2. Если m принадлежит A1, то xm = x при γm = 1 и xm = 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}].