Дискретная математика. Алгебра Жегалкина

1. Дискретная математика

2. Алгебра Жегалкина

• Алгеброй Жегалкина называется
алгебра вида
AG P2 , &,
В алгебре Жегалкина действуют
тождества:
.

3. Тождества алгебры Жегалкина

1) коммутативность сложения по модулю 2:
х у у х
2) ассоциативность сложения по модулю 2:
( х ⊕у) ⊕z = х ⊕( y ⊕z )
3) дистрибутивность конъюнкции по
отношению к сложению по модулю 2:
( x ⊕y) z = xz ⊕yz
4) свойства констант
x x 0, x 0 x

4. Формулы перехода

От любой булевой формулы можно
перейти к формуле алгебры
Жегалкина, используя тождества:
x y xy x y
x x 1

5. Полином Жегалкина

Полином Жегалкина – это формула
алгебры Жегалкина, имеющая вид суммы
по модулю 2 элементарных конъюнкций
различного количества переменных без
отрицаний.
xyz⊕xy⊕xz ⊕yz ⊕x⊕y ⊕z ⊕1

6. Линейная функция

Линейной функцией называется функция,
полином Жегалкина которой имеет вид:
f ( x1 , x2 , ..., xn ) 1x1 2 x2 ... n xn
1 , 2 , ..., n , 0, 1
Примеры линейных функций от 3-х
переменных:
1) x ⊕y ⊕z ⊕1;
3) x y;
2) x ⊕y ⊕z;
4) z ⊕1.

7. Утверждение 1

Утверждение 1
Если
f1 • f 2 = 0
то
f1 ∨f 2 = f1 ⊕ f 2

8. Утверждение 2

Утверждение 2
Если формула F – СДНФ, то
при переходе к формуле
алгебры Жегалкина
достаточно заменить символы
дизъюнкции ( ∨ )на символ
сложения по модулю 2 (⊕ ).

9. Пример 1

f ( x, y, z) xy z xy z xy z
x y 1 z 1 x y 1 z 1
= x(yz ⊕y ⊕z ⊕1)⊕xy⊕x ⊕z ⊕1 =
x y xy x y
=
xyz
⊕
xz
⊕
z
⊕
1
.
=
0
( x ⊕xx⊕
y) z x=
xz
x ⊕
1 yz
= xyz⊕xy⊕xz⊕x ⊕xy⊕x ⊕z ⊕1 =

10. Пример 2 Дана СДНФ:

f ( x, y, z ) = xyz ∨ xyz ∨ xyz =
= xyz⊕xyz ⊕xyz =
= xyz⊕x(y ⊕1)z ⊕xy(z ⊕1) =
xyz xyz xz xyz xy
f1 f(2 x=⊕
0
,
f
∨
f
=
f
⊕
f
1zxz
2xz
1 yz 2
xyz
xy
.
y
)
=
⊕
x⊕
x xx= 01

11. Теорема (о существовании и единственности полинома Жегалкина логической функции)

У каждой логической функции
существует и единственен
полином Жегалкина.

12. Доказательство:

1. Существование полинома
уже доказано.
2. Докажем единственность.
Для этого установим взаимно
однозначное соответствие между
полиномами и логическими
функциями от n переменных.

13. Доказательство:

Полином состоит из слагаемых
– конъюнкций переменных без
отрицаний.
Сколько может быть различных
слагаемых?
Столько, сколькими способами
можно составить подмножеств
из множества переменных.

14.

Множество переменных имеет
вид: U={x1, x2, x3, …, xn}.
1; конъюнкция без переменных
{x1} x1 ;
{x1, x2} x1x2;
{x1, x2, x3} x1x2x3;…
{x1, x2, x3, …, xn} x1x2x3…xn.

15. Доказательство:

Полином от полинома отличается составом слагаемых.
Значит, сколько подмножеств
множества слагаемых можно
образовать, столько и будет
полиномов.

16.

0; полином без слагаемых
{{x1}} x1
полином с одним слагаемым ;
{{x1}, {x1, x2}} x1 x1x2
полином с 2 слагаемыми ;
{{x1}, {x1, x2}, {x1, x2, x3}}
x1 x1x2 x1x2x3
полином с 3 слагаемыми ; и так далее.

17. Доказательство:

Значит, между этими
множествами можно
установить ВОЗ
соответствие.