ВАЖНЕЙШИЕ ЗАМКНУТЫЕ КЛАССЫ. ТЕОРЕМА ПОСТА О ПОЛНОТЕ

аранов Виктор Павлович. Дискретная математика.

Раздел 4. Функциональные системы с операциями. Алгебра логики.

Лекция 23. Важнейшие замкнутые классы. Теорема Поста о полноте.

Лекция 23. ВАЖНЕЙШИЕ ЗАМКНУТЫЕ КЛАССЫ.

ТЕОРЕМА ПОСТА О ПОЛНОТЕ

План лекции:

1. Важнейшие замкнутые классы булевых функций.
   1. Класс функций, сохраняющий константу 0.
   2. Класс функций, сохраняющий константу 1.

1.3. Класс самодвойственных функций.

1.4. Класс монотонных функций.

1.5. Класс линейных функций.

2. Теорема Поста о полноте.

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

1. Важнейшие замкнутые классы булевых функций
   1. Класс функций, сохраняющий константу 0

Обозначим через класс всех булевых функций из , сохраняющих константу 0, то есть функций, которые равны нулю на нулевом наборе переменных:

.

Заметим, что если , а , то и .

Легко убедиться, что функции 0, , , , принадлежат классу , а функции 1, , , не входят в .

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

Покажем, что – замкнутый класс. Для этого надо доказать следующее утверждение.

Лемма 1. Суперпозиция функций из класса является функцией класса .

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

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

Теперь покажем, что функция , полученная в результате применения операции , принадлежит , если принадлежат :

.

Лемма доказана.

Пример 1. Функции и входят в , поэтому суперпозиция этих функций будет сохранять 0. Следовательно, система неполная.

1. Класс функций, сохраняющий константу 1

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

.

Например, функции 1, , , принадлежат классу , а функции 0, , не входят в .

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

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

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

Как и выше, нетрудно проверить, что добавление равных функций не выводит за пределы класса :

.

Очевидно, что самодвойственными будут функции , . Менее тривиальным примером является функция :

Для самодвойственной функции имеет место тождество

.

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

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

является самодвойственной, если самодвойственны. Последнее устанавливается непосредственно:

.

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

Лемма 2. Если , то из нее путем подстановки функций и можно получить несамодвойственную функцию одного переменного, то есть константу.

Доказательство. Так как , то найдется набор такой, что

.

Рассмотрим функции () и положим

.

Тогда

Лемма доказана.

Например, функция несамодвойственна, так как . Аналогично для функции имеем: .

1. Класс монотонных функций

Рассмотрим множество двоичных слов длины . Зададим на этом множестве отношение порядка (предшествования) следующим образом: будем говорить, что слово

предшествует слову

,

если

.

Тот факт, что слово предшествует слову будем обозначать .

Отношение предшествования удовлетворяет аксиомам рефлексивности, антисимметричности и транзитивности.

Например, 001011, 001001111111.

Слова 01 и 10 не находятся в отношении предшествования. Такие слова называются несравнимыми.

Отношение “” можно представить в виде ориентированного графа. Для имеем следующий граф:

Рис. 1. Представление отношения предшествования в виде ориентированного графа

Слово предшествует слову , если от к можно пройти по стрелкам.

Функция называется монотонной, если для любых наборов переменных и выполняется условие

,

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

Очевидно, что функция, равная монотонной функции, также является монотонной.

Например, монотонными функциями будут 0, 1, , , .

Обозначим через множество всех монотонных функций. Покажем, что класс монотонных функций замкнут.

Лемма 3. Суперпозиция функций из класса является функцией класса .

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

Пусть , где . Покажем, что . Рассмотрим два сравнимых набора значений аргументов функции :

.

Тогда , и в силу монотонности имеет место неравенство

.

Отсюда и в силу монотонности имеет место неравенство

.

В результате имеем

Таким образом, . Лемма доказана.

Будем называть наборы и соседними по -ой координате , если

, .

Докажем теперь лемму о немонотонной функции.

Лемма 4. Из немонотонной функции путем подстановки констант на места некоторых аргументов можно получить отрицание.

Доказательство. Пусть . Это значит, что

.

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

, .

Рассмотрим функцию одного аргумента

.

Имеем

.

Так как , а , то . Лемма доказана.

1. Класс линейных функций

Последним классом является класс всех линейных функций.

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

.

Класс , очевидно, содержит константы 0 и 1, тождественную функцию , отрицание , сумму по mod 2 . Дизъюнкция – нелинейная функция. Нелинейной также является конъюнкция , многочлен Жегалкина которого имеет вид .

Очевидным является следующее утверждение относительно замкнутости класса .

Лемма 5. Суперпозиция линейных функций является линейной функцией.

Докажем лемму о нелинейной функции.

Лемма 6. Пусть – нелинейная функция и . Подстановкой констант на места аргументов функции можно получить нелинейную функцию от двух аргументов.

Доказательство. Рассмотрим многочлен Жегалкина функции , который по условию содержит, по крайней мере, один член степени выше первой. Переименовывая переменные, будем считать , что в этот член входят переменные , и, возможно, какие-то другие переменные. Выполним следующую группировку членов полинома Жегалкина функции : соберем члены, в которые входят и и вынесем за скобки. Среди оставшихся соберем члены, содержащие , и вынесем за скобки. Точно так же соберем члены, содержащие , и вынесем за скобки. В результате получим

.

Здесь – некоторые функции от , причем функция тождественно не равна 0. Это следует из единственности полинома Жегалкина: если тождественно равно 0, то это означало бы, что функция имеет два полинома Жегалкина – с произведением и без него. Тогда для некоторого набора значений переменных имеем . Отсюда

,

где , , .

Лемма доказана.

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

Таблица 1

0	+	–	–	+	+
1	–	+	–	+	+
	–	–	+	–	+

1. Теорема Поста о полноте

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

– произвольная система функций из . Спрашивается, как выяснить, будет она полной или нет? Ответ на этот вопрос дает следующая теорема.

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

Доказательство. Необходимость. Пусть – полна, то есть . Допустим, что содержится в одном из указанных классов – обозначим его через , то есть . Тогда в силу свойств замыкания и замкнутости имеем

.

Отсюда , что не так. Необходимость доказана.

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

.

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

1. Построение при помощи функций , , и констант и отрицания.

Рассмотрим функции и . Построим функции одного аргумента:

и .

При сделанных предположениях

, .

В зависимости от того, какие значения имеют и , возможны четыре варианта.

1. , .

В этом случае , . В результате суперпозиции получаем константу 1: . Таким образом, отрицание и константы построены.

1. , .

В этом случае , . Строим , и первый этап закончен.

1. , .

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

.

Рассмотрим функцию , в которой на место -го аргумента ставится , если , или , если . Тогда

.

Отсюда следует, что . С помощью отрицания построим другую константу.

1. , .

Следовательно, , . Воспользуемся немонотонной функцией . По лемме 4 из путем подстановки констант можно получить отрицание.

1. Покажем, что из функций можно построить конъюнкцию. При этом будем использовать построенные на первом этапе константы и отрицание. Воспользуемся нелинейной функцией . Подставим в нее константы и построим нелинейную функцию от двух аргументов, что возможно по лемме 6:

.

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

В общем случае

Раскрыв скобки, убеждаемся, что . Таким образом, конъюнкция построена из функций системы .

Теорема доказана.

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

, где , ,

имеем следующую таблицу:

Таблица 2

Функция	Класс
	0	0	1	0	1
	1	1	0	1	0
	1	1	0	1	0

Пример. Импликация имеет следующую таблицу истинности:

0 0	1
0 1	1
1 0	0
1 1	1

Из таблицы следует, что не сохраняет 0, несамодвойственна, немонотонна. Кроме того, , так как

.

Добавляя к любую функцию, не сохраняющую 1, получим полную систему. Рассмотрим, например, систему , где . Построим отрицание и конъюнкцию:

, при и имеем ;

.

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

.

Баранов Виктор Павлович. Дискретная математика.

Раздел 4. Функциональные системы с операциями. Алгебра логики

ВАЖНЕЙШИЕ ЗАМКНУТЫЕ КЛАССЫ. ТЕОРЕМА ПОСТА О ПОЛНОТЕ