Замкнутые классы булевых функций

Выше показано, что любая функция может быть выражена в виде ДНФ, те. формулой, использующей функциональные знаки &,v,-> и

символы переменных Еще один интересный пример дает система функций

(1)

Выше показано, что . Используя это равенство и закон

де Моргана (свойство 11), выразим дизъюнкцию через функции

системы (1).

Поэтому в любой ДНФ можно выразить дизъюнкцию и отрицание через функции системы (1). Примеры:

1) = [заменяем знак отрицания] = - [заменяем знак дизъюнкции] = = [раскрываем скобки] =

2) = [заменяем знак дизъюнкции] =

То же преобразование можно выполнить проще, заменяя сначала знак дизъюнкции

. Первое слагаемое равно 0, так как

содержит произведение , и его можно из формулы удалить

Оставшуюся часть преобразуем, заменяя знак отрицания

Как видно из рассмотренных примеров, если в формуле после произведенных замен раскрыть скобки и выполнить умножения и

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

Полученная формула, порожденная логическими константами 0 и

1 и функциями называется многочленом Жегалкина

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

В самом деле, пусть два многочлена и

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

всех содержащих его членов, Р и Q можно представить в виде

где - многочлены, зависящие от переменных

Достаточно показать, что как многочлены Легко

проверить, что для п = 1 утверждение о единственности многочлена верно: все функции одной переменной - в табл 5. Тем самым выполнено базовое условие для применения метода математической индукции по числу переменных п. Выполним индукционный шаг: предположим, что

утверждение справедливо для функций (л —1) переменных и докажем его для п. Поскольку Р и Q тождественно равны, то при они

также равны Но при этом )

Значит, совпадают как многочлены, по предположению

индукции, и, прибавив к обеим частям (*) и, соответственно, к (**), получим

Левые части этих равенств равны, следовательно, равны и правые,

в том числе, при X = \, откуда равны как функции. Тогда, по

предположению индукции, они совпадают и как многочлены, что завершает доказательство

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

Замыкание системы булевых функций D - класс всех суперпозиций функций системы D.

Примеры: 1) Если система D - множество из двух функций: конъюнкции и дизъюнкции, то ее замыкание - всевозможные ДНФ такие, что входящие в них элементарные конъюнкции не содержат

*»••

отрицаний переменных (например, ). Любую

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

2) Если система D состоит из одной функции то ее

замыкание - всевозможные суммы различных переменных.

Замкнутый класс булевых функций - множество функций К,

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

Примеры. 1) Замыкание любой системы функций - замкнутый класс.

2) 4 функции одной переменной - замкнутый класс.

3) 2 функции образуют замкнутый класс.

4) Множество сумм по модулю 2 нечетного числа переменных является замкнутым классом, поскольку подстановка в такую функцию вместо переменной функции этого класса увеличивает число вхождений переменных в формулу на четное число; при этом некоторые слагаемые

могут взаимно сократиться ввиду эквивалентности , и число