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

Алгебра жегалкина

• Часть 1
• | 2
• | 3
• | 4
• | 5
• | 6
• | 7
• | 8
• | 9

            Определение. Алгеброй Жегалкина называется алгебра над множеством логических функций и переменных, сигнатура которой содержит две бинарные операции   &   и   , и две нульарные операции – константы 0 и 1.

            В алгебре Жегалкина выполняются следующие соотношения:

1.   x  y = y  x;

2.   x ( y  z )  =  x y  x z;

3.   x  x = 0; 

                                                                                                          (1.4)

4.   x   = 1; 

5.   x  0 = x.

            Эти соотношения легко проверить табличным способом. Кроме перечисленных соотношений в алгебре Жегалкина выполняются соотношения булевой алгебры относительно конъюнкции и констант

.

            Найдем выражения для основных элементарных функций алгебры логики в алгебре Жегалкина.

1.        =  x  1. 

Это соотношение проверяется непосредственной подстановкой 0 и 1 в обе части равенства.

предыдущаяследующая