Вопрос 2.

Основные классы Булевой функции

1.Функция называется сохраняющей ноль, если . Обозначают, что .

2.Функция называется сохраняющей единицу, если . Обозначают, что .

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

4.Функция называется монотонной: . Обозначают, что .

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

Теорема Поста. Полные системы связи.

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

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

Американский математик Эмиль Пост ввёл в рассмотрение следующие замкнутые классы булевых функций, они было сказано выше:

1.Функции, сохраняющие константу T₀ и T₁;

2.Самодвойственные функции S;

3.Монотонные функции M;

4.Линейные функции L.

Им было доказано, что любой замкнутый класс булевых функций, не совпадающий с P₂, целиком содержится в одном из этих пяти так называемых предполных классов, но при этом ни один из пяти не содержится целиком в объединении четырёх других. Таким образом критерий Поста для полноты системы сводится к выяснению, не содержится ли вся эта система целиком в одном из предполных классов. Если для каждого класса в системе найдётся функция, не входящая в него, то такая система будет полной, и с помощью входящих в неё функций можно будет получить любую другую булеву функцию.

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

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

Полином Жегалкина - полином(многочлен) над Z₂, то есть полином с коэффициентами вида 0 и 1, где в качестве произведения берется конъюнкция, а в качестве сложения исключающее или. Полином был предложен в 1927 году И. И. Жегалкиным в качестве удобного средства для представления функций булевой логики. Полином Жегалкина представляет собой сумму по модулю два (операция Исключающее ИЛИ) произведений неинвертированных переменных, а также (если необходимо) константы 1

Теорема. Любая функция п переменных может быть представлена полиномом Жегалкина и это представление единственно.

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

1.Получить ДНФ функции

2.Все ИЛИ заменить на Исключающее ИЛИ

3.Во всех термах заменить элементы с отрицанием на конструкцию: («элемент» «исключающее ИЛИ» 1)

4.Раскрыть скобки по правилам алгебры Жегалкина и привести попарно одинаковые термы

Имеется 2-й способ нахождения полинома Жегалкина для функций, заданных в виде ДНФ. Этот способ основан на том, что х+1 = . Если функция задана в виде ДНФ, то сначала убираем дизъюнкцию, используя при этом правило де Моргана, а все отрицания заменяем прибавлением единицы. После этого раскрываем скобки по обычным правилам, при этом учитываем, что четное число одинаковых слагаемых равно нулю (так как х+ х = 0), а нечетное число одинаковых слагаемых равно одному такому слагаемому.