Алгебра Жегалкина и линейные функции

Алгебра Жегалкина – это алгебра над множеством двух бинарных булевых функций (И, ) и нульарной функции 1. Легко проверить следующие соотношения в этой алгебре:

;

;

;

.

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

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

Контрольные вопросы и упражнения

1. Дайте определение полной системе булевых функций.

2. Перечислите классы Поста.

3. Дайте определение двойственной функции. Приведите примеры.

4. Дайте определение самодвойственной функции. Приведите примеры.

5. Постройте полином Жегалкина для функции «стрелка Пирса».

6. Сформулируйте теорему Поста.

7. Что такое базис? Приведите примеры базисов.