Mnogochlen_Zhegalkina

1. Двоичное сложение. Многочлен Жегалкина

Операция двоичного
сложения и её свойства.
Многочлен Жегалкина.

2. Двоичная сумма

Двоичной суммой (суммой Жегалкина, кольцевой
суммой) называется логическая операция, которая
обозначается символом и принимает истинное
значение, когда высказывания различны по
значению.

3. Свойства двоичного сложения

x x 0
x x 1
x 0 x
x 1 x
Коммутативность :
x y y x
Ассоциативность :
x y z x y z
Дистрибутивность :
x y z xz yz

4. Выражение основных логических операций через конъюнкцию и кольцевую сумму

x x 1
x y x y xy
x y x xy 1
x y x y 1

5. Многочлен Жегалкина

формула над множеством функций , .
Пример:
1 x xyz
y x xy
Теорема. Для любой булевой функции
существует задающий ее многочлен
Жегалкина. Он единственен с точностью
до перестановок слагаемых и порядка
переменных в конъюнкциях.

6. Методы получения многочлена Жегалкина

1. С помощью равносильных
преобразований:
● заменить все логические связки через
кольцевую сумму и конъюнкцию;
● привести подобные слагаемые.
2. С помощью метода неопределенных
коэффициентов (МНК)
3. С помощью треугольника Паскаля

7. Пример

x y z y
x y z y x y 1 z y
x y 1 1 z y x y z y
x y z x y z y x y z x z y z y
x y z 1 x z 1 y z 1 y
x y z 1 xz x yz y y
z 1 xz yz y z 1 xz yz z 1 xz yz y
1 z 1 xz yz zy y xyz yzy 1
z 1 xz yz zy y xyz yz 1
y z xz zy xyz.

8. Метод неопределенных коэффициентов

Для функции, зависящей от трех
переменных, в общем виде многочлен
Жегалкина имеет вид:
f 0 1 x 2 y 3 z 12 xy 23 yz 13 xz 123 xyz
С помощью таблицы истинности
подставляют в этот многочлен значения
переменных:
f 000 0 0;1
f 001 0 3 0;1 3 0;1 3 0;1
...

9. Пример

x y z y
f 0 1 x 2 y 3 z 12 xy 23 yz 13 xz 123 xyz
f 000 0 0
f (001) a0 3 0 3 1 3 1
f (010) a0 2 0 2 1 2 1
f (100) a0 1 0 1 0 1 0
f (011) a0 2 3 23 0 1 1 23 1 23 1
f (101) a0 1 3 13 0 0 1 13 0 13 1
f (110) a0 1 2 12 0 0 1 12 1 12 0
f (111) a0 1 2 3 12 13 23 123
0 0 1 1 0 1 1 123 1 123 1
f y z yz xz xyz

10. Треугольник Паскаля

x
y
z
f
0
0
0
0 0
0
0
1
1
0
1
0
1
0
1
1
1
1
0
0
0
1
0
1
0
1
1
0
1
1
1
1
1
Треугольник Паскаля
1
1
1
1
0
1
0
1
0
1
0
1
0
0
1
1
1
1
1
1
0
0
0
1
Слагаемые
0
1
0
0
1
1
0
1
0
1
z
1
y
0
yz
x
xz
xy
xyz

11. Решение задач

Решить всеми тремя способами (равносильными
преобразованиями, методом неопределенных
коэффициентов, треугольником Паскаля):
1. x y z x
y
z
x
y
2.
x
y
z
y
3.