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

Другая замечательная алгебра булевых функций строится на основе операций сложения по модулю 2 и конъюнкции. Она называется алгеброй Жегалкина по имени предло­жившего ее советского ученого. Непосредственной проверкой по таблицам соответствия устанавливаются следующие основные свой­ства этой алгебры:

- коммутативность х + у = у + х; ху = ух;

- ассоциативность х + (у + г) = (х + у) + г; х(уг) = (ху)г;

- дистрибутивность умножения относительно сложения х(у + г ) = ху + хг;

- свойства констант. ; ;

Все эти свойства подобны обычной алгебре, но в отличие от булевой алгебры закон дистрибутивности сложения относительно умножения не имеет силы. Справедливы также следующие тождества:

- закон приведения подобных членов при сложении х + х = 0;

- закон идемпотентности для умножения хх = х.

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

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

Пример.

Через операции алгебры Жегалкина можно выразить все другие булевы функции:

.

10.8. Канонические многочлены

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

Действительно, если привести данную функцию к совершенной нормальной форме и заменить все дизъюнкции через суммы по модулю 2, а отрицание переменных представить в соответствии с тождеством , то после раскрытия скобок получим некоторое алгебраическое выражение. Оно приводится к канониче­скому многочлену на основе соотношений х + х = 0 и хх = х. Такое представление всегда возможно и единственно (с точностью до по­рядка расположения членов).

Пример.

(1 + х + у) (1 + ху) + (х + ху) у = 1 + х + у + ху + хху + уху + ху + хуу =

= 1 + х + у + ху + ху + ху + ху + + ху = 1 + х + у + ху.

Проблема разрешимости в алгебре Жегалкина сводится к ука­занным преобразованиям, в процессе которых делается вывод о вы­полнимости той или иной формулы.

Пример.

х(х у)  у = х (1 + х + ху)  у = ху  у = 1 + ху + хуу =1 + ху + ху = 1

Так как эта формула является тождественной единицей, то она невыполнима.

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

х  у  г = х + у + г + ху + хг + уг + хуг.

Однако при использовании вычислительных машин различия в сложности выполнения операций булевой алгебры и арифметиче­ских операций значительно ослабляются.

10.9. Типы булевых функций

В алгебре логики из множества различных булевых функций п переменных у= f() выделяются следующие пять типов булевых функций.

1) Функции, сохраняющие константу 0, т. е. такие f(), что f(0,…,0) = 0. Так как на одном из 2^п наборов () значения таких функций фиксированы, то их число равно , т. е. половина всех функций п переменных сохраняет константу 0.

2) Функции, сохраняющие константу 1, т. е. такие f(), что f(1,…,1) = 1. Их число, как и в предыдущем случае, равно половине общего числа всех функций п переменных.

3) Самодвойственные функции, т. е. такие, которые принимают противоположные значения на любых двух противоположных наборах. Если в общей таблице соответствия наборы, как обычно следуют в порядке их номеров, то противоположные друг другу наборы располагаются симметрично относительно середины их рас­положения. Это значит, что строка значений самодвойственной функ­ции должна быть антисимметричной относительно своей середины. Самодвойственная функция полностью определяется заданием ее значений на половине всех наборов (остальные значения определя­ются по условию антисимметричности), поэтому число независимых наборов равно и число всех таких функций .

4) Линейные функции, т. е. такие, которые представляются в алгебре Жегалкина каноническим многочленом, не содержащим произведений переменных: , где коэффи­циенты принимают значения 0 или 1. Так как всего коэффициентов п+1, то число различных линейных многочленов будет . В силу однозначности представления функции канони­ческим многочленом это число выражает и количество линейных функций.

5) Монотонные функции, т.е. такие, которые для любых двух наборов из множества значений переменных, частично упорядочен­ного соотношением ()  () при , удовлетворяют неравенству f ()  f ().

Рассмотренные типы функций замкнуты относительно операции суперпозиции, т. е. суперпозиция любого числа булевых функций данного типа является функцией того же типа.