Полнота и замкнутость (примеры полных систем). Теорема Поста.

(1) – система булевых функций.

Система (1) называется полной, если любую булеву функцию можно реализовать формулой в этой системе.

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

Пусть даны две системы булевых функций (1) (2) относительно которых известно, что (1) – полная система и каждая функция первой системы представляется в виде суперпозиции функций (2) системы, тогда (2) – полная система. Система (1) называется функционально замкнутым классом, если любая суперпозиция функций этой системы принадлежит ей же. Функционально замкнутые классы отличные от пустого класса и от класса называются собственными функционально замкнутыми классами. Рассмотрим важнейшие функционально замкнутые классы. 1. - это класс функций, сохраняющий ноль, т. е. функций для которых Пример. . 2. - это класс функций, сохраняющий единицу, т. е. функций для которых Пример. . 3. - это класс линейных функций, т. е. функции, для которых полином Жегалкина является линейным относительно каждой переменной. . 4. - это класс монотонных функций. Пусть

, где - двоичные векторы, являющиеся наборами значений переменных ; Вектор предшествует или младше вектора , если , такие наборы называются сравнимыми. Свойства отношений. 1) - рефлексивность 2) и - симметричность 3) и - транзитивность.

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

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

	+	-	-	+	-
	+	-	+	-	-
	-	+	+	+	-

По теореме Поста система является полной, если каждый столбец таблицы содержит хотя бы один «-».