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

Теория:

Рассмотрим алгоритмы построения полинома Жегалкина булевой функции, заданной различными способами, а именно: совершенной ДНФ, произвольной ДНФ, формулой и таблицей истинности.

Алгоритм построения полинома Жегалкина по СовДНФ (основан на доказательстве теоремы о существовании полинома Жегалкина).

Начало. Задана совершенная ДНФ функции f(x₁, …, x_n).

Шаг 1. Заменяем каждый символ дизъюнкции на символ дизюнкции с исключением.

Шаг 2. Заменяем каждую переменную с инверсией x равносильной формулой x 1.

Шаг 3. Раскрываем скобки.

Шаг 4. Вычеркиваем из формулы пары одинаковых слагаемых.

Конец. Получен полином Жегалкина функции f(x₁, …, x_n).

Пример. Найдем полином Жегалкина мажоритарной булевой функции по ее совершенной ДНФ.

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

и унок 10 - Пример выполнения задания на построение полинома Жегалкина

б) определение полноты набора булевых функций. Для этого необходимо заполнить таблицы истинности для функций алгебры логики и провести их исследования на сохранение 0, сохранение 1, самодвойственность, монотонность, линейность. По результатам сделать вывод о полноте предложенного набора функций. На рисунке 11 приведен пример задания данного типа.

Рс нок 11 - Пример задания на определение полноты набора булевых функций

Для выполнения этого типа заданий заполните доступные для ввода ячейки таблицы значениями 0, 1, + или -. На рисунке 3 приведено решение примера, представленного на рисунке 2.

Рснок 12 - Пример выпо лнения задания, приведенного на рисунке 2

8) Ответьте на контрольные вопросы.
9) Просмотрите итоги выполнения работы.

4 Контрольные вопросы и задания

1. Какие элементарные операции используются в алгебре Жегалкина?
2. Что такой полином Жегалкина?
3. Какая булева функция называется линейной?
4. Приведите алгоритм преобразования булевых функций к виду полинома Жегалкина.
5. Приведите примеры линейных булевых функций.
6. При каких условиях набор булевых функций полон? Определите функционально полный набор.
7. Сформулировать понятие замкнутого класса. Какие замкнутые классы рассматриваются в булевой алгебре?
8. Является ли объединение функционально замкнутых классов функционально замкнутым классом?
9. Запишите тождества, позволяющие выразить основные операции булевой алгебры в алгебре Жегалкина.
10. Сколько различных полиномов Жегалкина можно построить для произвольной булевой функции?
11. Дайте определения булевых функций, сохраняющих ноль и единицу.
12. Установить, сохраняет ли 0 и 1 функция Шеффера.
13. Определите монотонность булевой функции?
14. Какой набор булевых функций называется несократимым?