Diskretka4
.pdf
Сумма элементарных конъюнктов без отрицаний
Определение. Многочленом Жегалкина называется сумма нескольких элементарных конъюнктов без отрицаний.
Примеры. 0, 1,
Сумма элементарных конъюнктов без отрицаний
Определение. Многочленом Жегалкина называется сумма нескольких элементарных конъюнктов без отрицаний.
Примеры. 0, 1, xy,
Сумма элементарных конъюнктов без отрицаний
Определение. Многочленом Жегалкина называется сумма нескольких элементарных конъюнктов без отрицаний.
Примеры. 0, 1, xy, 1 + x,
Сумма элементарных конъюнктов без отрицаний
Определение. Многочленом Жегалкина называется сумма нескольких элементарных конъюнктов без отрицаний.
Примеры. 0, 1, xy, 1 + x, x + y,
Сумма элементарных конъюнктов без отрицаний
Определение. Многочленом Жегалкина называется сумма нескольких элементарных конъюнктов без отрицаний.
Примеры. 0, 1, xy, 1 + x, x + y, x + y + xy,
Сумма элементарных конъюнктов без отрицаний
Определение. Многочленом Жегалкина называется сумма нескольких элементарных конъюнктов без отрицаний.
Примеры. 0, 1, xy, 1 + x, x + y, x + y + xy, 1 + x + xy + xyz,
. . .
Существование и единственность многочлена Жегалкина
Теорема. Любая булева функция f : B:n ! B представляется в виде многочлена Жегалкина, причем единственным образом
Существование и единственность многочлена Жегалкина
Теорема. Любая булева функция f : B:n ! B представляется в виде многочлена Жегалкина, причем единственным образом
Доказательство существования. Представим f в СДНФ
f (x1; x2; : : : ; xn) = _ x1 1 x2 2 xn n :
( 1; 2;::: n)2Bn:f ( 1; 2;::: n)=1
Существование и единственность многочлена Жегалкина
Теорема. Любая булева функция f : B:n ! B представляется в виде многочлена Жегалкина, причем единственным образом
Доказательство существования. Представим f в СДНФ
f (x1; x2; : : : ; xn) = _ x1 1 x2 2 xn n :
( 1;2;:::n)2Bn:f ( 1;2;:::n)=1
Заметим, что при ( 1; 2; : : : n) 6= ( 10 ; 20 ; : : : n0 ) имеем
(x1 1 x2 2 xn n ) (x1 10 x2 20 xn n0 ) = 0:
Существование и единственность многочлена Жегалкина
Теорема. Любая булева функция f : B:n ! B представляется в виде многочлена Жегалкина, причем единственным образом
Доказательство существования (продолжение). Поэтому,
f (x1; x2; : : : ; xn) = X x1 1 x2 2 xn n :
( 1; 2;::: n)2Bn:f ( 1; 2;::: n)=1