Тема 4 Полнота и замкнутость

4.2 Теорема о полноте

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

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

Приведем пример полных систем.

Пример 1. Как отмечено выше, система является полной.

Пример 2. Множество всех булевых функций P2 является полной системой.

В вопросе о полноте важную роль играет следующая теорема.

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

Действительно, так как Д1 – полная система, то любая булева функция представима в виде суперпозиции функций из Д1. А так как любая функция из Д1 представима в виде суперпозиций функций из Д2, то Д2 – полная система.

Пример 3. Система – полная.

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

С понятием полноты тесно связано понятие замкнутого класса и замыкания.

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

Всякая система М булевых функций порождает некоторый замкнутый класс. Этот класс состоит из всех булевых функций, которые можно получить суперпозициями из М. Такой класс называется Замыканием М и обозначается [М]. Для замкнутого класса М следует, что [М]=М. Очевидно, что если М – полная система, что [М]=Р2.

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

Первый класс – класс булевых функций, сохраняющих константу С, т. е. функций , для которых .

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

Ясно, что функции принадлежат классу Т0, а не принадлежит Т0. Следовательно, .

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

Как и выше, легко подсчитать число таких функций от переменных. Их ровно .

Ясно, что функции принадлежат классу Т1, а функция - нет. Следовательно, .

Третий замечательных класс – класс всех самодвойственных функций S.

Булева функция называется Самодвойственной, если она совпадает со своей двойственной, т. е. .

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

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

Используя законы дистрибутивности и идемпотентности, имеем:

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

Очевидно, что и принадлежат классу S, а , не принадлежит классу S. Следовательно, .

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

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

Четвертый замечательный класс – класс всех линейных булевых функций.

Булевы функции вида , где и равны нулю или единице, называют Линейными.

Нетрудно подсчитать число всех линейных булевых функций от переменных. Их число равно .

Очевидно, что функции принадлежат L, а функции Xy не принадлежат L. Следовательно .

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

Пример 5. Выяснить, является ли функция линейной. Запишем данную функцию в виде полинома Жегалкина:

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

Пятый замечательный класс – класс М всех монотонных булевых функций.

Два набора и называются Сравнимыми, если .

Запись означает, что набор предшествует набору .

Например, , а наборы и несравнимы.

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

Очевидно, что константы 0,1 и функция х – монотонные функции.

Функции - монотонные функции (доказательство осуществляется проверкой).

Функции не являются монотонными, так как , а .

Следовательно, .

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

Теорема 1. Булева функция, имеющая дизъюнктивную нормальную форму, не содержащую отрицаний, является монотонной функцией, отличной от 0 и 1.

Докажем данную теорему. Пусть булева функция имеет дизъюнктивную нормальную форму Д, не содержащую отрицаний, и пусть на наборе , . Тогда Д содержит конъюнкцию равную единице на наборе . Следовательно, . Возьмем любой набор такой, что . В нем обязательно . Поэтому конъюнкция при этом наборе равна 1, а значит . Итак, условие монотонности для ДНФ Д выполнено. А это значит, что функция монотонна.

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

Классы булевых функций являются замкнутыми классами.

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

Аналогичным образом доказывается замкнутость класса .

Если самодвойственные функции, то . Итак, S – замкнутый класс.

Пусть , где - монотонные функции, и пусть их наборы переменных. Здесь переменные функции Ф состоят из функций . Пусть и два таких набора, что . Каждый из наборов и однозначно определяет следующие наборы значений переменных . Причем . Так как – монотонные функции, то . Следовательно, . Из монотонности функции f получаем, что .

Итак, М – замкнутый класс.

Замкнутость класса L следует непосредственно из определения линейных функций.

Как показано выше, функция не принадлежит классу М. Следующая теорема показывает, что всякая немонотонная функция содержит, в некотором смысле, в своем составе функцию отрицания.

Теорема 2. Если - немонотонная функция, то в результате ее суперпозиции с константами 0 и 1 может быть получена функция отрицания одного из аргументов функции .

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

. (1)

Так как , то обязательно найдется такая пара соседних наборов из цепочки (1) и , что . Не ограничивая общности, мы может считать, что

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

А это значит, что . Следовательно, .

4.2 Теорема о полноте. Цель данного параграфа дать ответ на один из основных вопросов алгебры логики – вопрос о необходимом и достаточном условии полноты системы булевых функций. Ответ на этот вопрос дает следующая теорема, доказательство которой будет вестись по методу А. В.Кузнецова и С. К.Яблонского.

Теорема 3 (о полноте). Для того, чтобы система булевых функций Д была полной, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из пяти замкнутых классов T0, T1, S, M, L.

Доказательство. Необходимость. Пусть Д – полная система, целиком содержащаяся в одном из классов T0, T1, S, M, L. Не ограничивая общности, будем считать, что . Тогда . Следовательно, , что невозможно.

Достаточность. Пусть система булевых функций Д целиком не содержится ни в одном из классов T0, T1, S, M, L. Тогда в системе Д обязательно найдутся следующие функции: , не сохраняющая 0, , не сохраняющая 1, не самодвойственная функция , нелинейная функция , не монотонная функция . Учитывая понятие фиктивной переменной, мы можем считать, что эти функции зависят от одних и тех же переменных.

Вначале построим из системы функций Д константы 0 и 1.

Рассмотрим функцию . Эта функция есть суперпозиция функций и . Так как не принадлежит классу T0, . Если теперь g(1)=1, то - константа 1. Подставляя константу 1 в функцию , мы получаем константу 0, ибо .

Пусть теперь . Из равенства g(0)=1 и g(1)=0 заключаем, что . Возьмем несамодвойственную функцию . Очевидно, что в этом случае найдется такой набор переменных , что =. Рассмотрим функцию и построим с помощью операции суперпозиции функцию . Тогда получаем:

(1)

Итак, h(0)=h(1). А это значит, что h(X) есть константа 0 или 1. Так как мы построили функцию , то суперпозиция этой функции с одной из констант дает другую константу. Следовательно, константы 0 и 1 нами построены.

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

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

Где константы 0 или 1. Построим функцию следующим образом:

Итак, теорема о полноте полностью доказана.

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

	T0	T1	S	L	M
F1
F2
…	…	…	…	…	…
Fn-1
Fn

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

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

, ;

, .

Составим таблицу Поста для системы Д1:

	T0	T1	S	L	M
	-	-	-	-	-

Нетрудно заметить, что .

Ясно, что не принадлежит Т0 и Т1. Двойственная функция к функции имеет вид:

Следовательно, не принадлежит классу S. Найдем полином Жегалкина для функции : .

Следовательно, функция не принадлежит классу L. Так как , а , то не принадлежит классу М.

Итак, система является полной.

Составим таблицу Поста для системы Д2:

	T0	T1	S	L	M
	+	+	+	+	–
	+	+	–	–	+
0	+	–	–	+	+
1	–	+	–	+	+

Исследуем функцию . Легко проверить, что она принадлежит классам Т1, Т0, L. Покажем, что она является самодвойственной.

Функция немонотонна, так как , а . В каждом столбце таблица Поста для системы Д2 стоит минус. Следовательно, система Д2 является полной.

Составим таблицу Поста для системы Д3:

T0	T1	S	L	M
–	+	–	–	–
–	–	+	+	–

Из таблицы видно, что система Д3 является полной.

Составим таблицу Поста для системы Д4:

	T0	T1	S	L	M
	-	-	+	-	-

Исследуем функцию .

Легко проверить, что данная функция не принадлежит ни Т0, ни Т1. Так как , а значение функции при наборе (0,0,0) больше, чем при наборе (1,1,1), то функция немонотонна. Очевидно, что все переменные данной функции являются существенными. А так как данная функция не может совпадать ни с , ни с , то она нелинейная. Как и в примере, можно показать, что функция является самодвойственной. Следовательно, система Д4 не является полной.

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

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

Теорема 4. Максимальное возможное число функций в несократимой полной системе булевых функций равно 4.

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

Следующий пример показывает, что константа 4 не может быть понижена.

Пример 2. Рассмотрим систему функций .

Составим таблицу Поста для данной системы:

	T0	T1	S	L	M
	+	+	-	-	+
0	+	-	-	+	+
1	-	+	-	+	+
	+	+	+	+	-

Из таблицы видно, что данная система является полной и несократимой, ибо

< Предыдущая		Следующая >