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

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

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

От формулы алгебры логики всегда можно перейти к формуле алгебры Жегалкина. Для этого нужно заменить основные элементарные функции алгебры логики на соответствующие эквивалентные выражения алгебры Жегалкина (1) - (5), представленные выше.

 В полученной формуле нужно раскрыть скобки и произвести упрощения, используя соотношения (1.4), а также следующие соотношения: x & x  = x и   x·1 = x. Полученное выражение и будет полиномом Жегалкина для данной формулы.

Пример. Найти полином Жегалкина для функции:   f( x, y ) = ( xy )(  x z ). 

Полученное выражение и есть полином Жегалкина.

 

            При нахождении полинома Жегалкина для некоторой формулы алгебры логики можно использовать следующее соотношение, вытекающее из представления дизъюнкции в алгебре Жегалкина:

                           f1  f2 = f1 f2,                                                                           (1.5)

справедливое при   f1f2 = 0. Используем соотношение (1.5) для нахождения полинома Жегалкина в следующих примерах.

Пример. Найти полином Жегалкина для функции:        f( x, y ) =  x y   .

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