Способы получения полинома Жегалкина

Способ неопределённых коэффициентов.

Пример 1: Рассмотрим этот способ на примере преобразования функции

.

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

Последовательность действий здесь такова:

1) Записать полином в общем виде

.

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

В результате получим систему уравнений.

2) Решить полученную систему уравнений.

Система уравнений Решение

; ; ;

; ; ;

; ;

;

Следовательно, – нелинейная функция.

Получение полинома Жегалкина по КНФ и ДНФ:

Здесь применяются свойства 2 и 10 функции М2.

Пример 2: Представим функцию примера 1 в конъюнктивной форме (в системе И, ИЛИ, НЕ) и выполним преобразования для получения полинома Жегалкина

Сначала избавляемся от ИЛИ по свойству 10, затем избавляемся от НЕ по свойству 2 и, наконец, по правилу 2 удаляем x₂: .

Пример 3:Пусть задана функция в ДНФ. Для перехода к форме в виде полинома Жегалкина необходимо выполнить следующее

Действия здесь аналогичны предыдущему примеру:

избавляемся от ИЛИ, а затем от НЕ и от x₂, так как .

Получение полинома Жегалкина по СДНФ:

1. Вместо символа дизъюнкции пишем ;

2. Исключаем инверсии по свойству ;

3. Раскрываем скобки и упрощаем ( и т.п.).

При выполнении первого пункта здесь учитывается то, что в СДНФ всегда присутствуют произведения, отличающиеся видом хотя бы одной переменной, например, abc и ab , поэтому преобразование их суммы по свойству 10 получается таким

= ,

так как .

Вопросы для самоконтроля

1. Что такое – функционально полная система логических операций (функций)? Приведите пример.

2. Что такое базис? Минимальный базис?

3. Как можно доказать полноту системы логических функций?

4. Как можно исключить «лишние» функции из заданной системы функций?

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

6. Какие логические функции не сохраняют 0 и 1? Приведите пример.

7. Поясните понятия двойственной и самодвойственной логической функции. Приведите примеры.

8. Приведите примеры монотонной и немонотонной логической функции.

9. Какой особенностью обладают монотонные функции?

10. Какими свойствами обладает операция Сложение по модулю 2?

11. Поясните понятие линейной и нелинейной логической функции.

12. Какие способы преобразования логических функций в полином Жегалкина Вы знаете? Приведите примеры. Какому способу Вы отдали бы предпочтение и почему?