Diskretka4
.pdf
Существование и единственность многочлена Жегалкина
Доказательство единственности. Пусть N = 22n и f1; f2; : : : ; fNвсе булевы функции от n аргументов. Пусть Gi количество различных многочленов Жегалкина функции fi ,
i = 1; N: В силe доказанного Gi 1, i = 1; N. Тогда для количества G всех многочленов Жегалкина от n аргументов имеем
NN
G = XGi X1 = N = 22n = G;
i=1 i=1
поскольку всего существует только 2n конъюнктов без отрицаний, каждый из которых может входить или не входить в многочлен. Поэтому, Gi = 1 для каждого i = 1; N; то есть каждая fi имеет только один многочлен Жегалкина.
Пример
|
x |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
y |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
z |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
f |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Пример
x |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
y |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
z |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
f |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
f = xyz _xyz _xyz _xyz _xyz _xyz
Пример
x |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
y |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
z |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
f |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
f = xyz _xyz _xyz _xyz _xyz _xyz = xyz +xyz +xyz +xyz + xyz + xyz
Пример
x |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
y |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
z |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
f |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
f = xyz _xyz _xyz _xyz _xyz _xyz = xyz +xyz +xyz +xyz + xyz + xyz = (1 + x)(1 + y)z + (1 + x)(1 + z)y + (1 + x)yz + (1 + y)(1 + z)x + (1 + y)xz + (1 + z)xy
Пример
x |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
y |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
z |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
f |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
f = xyz _xyz _xyz _xyz _xyz _xyz = xyz +xyz +xyz +xyz + xyz + xyz = (1 + x)(1 + y)z + (1 + x)(1 + z)y + (1 + x)yz + (1 + y)(1 + z)x + (1 + y)xz + (1 + z)xy = (1 + x + y + xy)z + (1 + x + z + xz)y + (1+ x)yz + (1+ y + z + yz)x + (1+ y)xz + (1+ z)xy
Пример
x |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
y |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
z |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
f |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
f = xyz _xyz _xyz _xyz _xyz _xyz = xyz +xyz +xyz +xyz + xyz + xyz = (1 + x)(1 + y)z + (1 + x)(1 + z)y + (1 + x)yz + (1 + y)(1 + z)x + (1 + y)xz + (1 + z)xy = (1 + x + y + xy)z + (1 + x + z + xz)y + (1+ x)yz + (1+ y + z + yz)x + (1+ y)xz + (1+ z)xy = (z + xz + yz + xyz) + (y + xy + zy + xzy) + (yz + xyz) + (x + yx + zx + yzx) + (xz + yxz) + (xy + zxy)
Пример
x |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
y |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
z |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
f |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
f = xyz _xyz _xyz _xyz _xyz _xyz = xyz +xyz +xyz +xyz + xyz + xyz = (1 + x)(1 + y)z + (1 + x)(1 + z)y + (1 + x)yz + (1 + y)(1 + z)x + (1 + y)xz + (1 + z)xy = (1 + x + y + xy)z + (1 + x + z + xz)y + (1+ x)yz + (1+ y + z + yz)x + (1+ y)xz + (1+ z)xy = (z + xz + yz + xyz) + (y + xy + zy + xzy) + (yz + xyz) + (x + yx + zx + yzx) + (xz + yxz) + (xy + zxy) = x + y + z + xy + xz + yz
Пример
|
x |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|||
|
y |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|||
|
z |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
f |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
||
|
|
f |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Пример
x |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|||
y |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|||
z |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
f |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
||
|
f |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
f = 1 + f = 1 + (xyz _ xyz)