Полнота и замкнутость. Примеры функционально полных систем

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

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

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

2) Система

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

Теорема. Пусть даны две системы функций из :

, ,

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

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

По условию теоремы

, , …, .

Поэтому в формуле можно исключить вхождения функций , заменив их формулами над :

,

То есть мы выразили в виде формулы над . Теорема доказана.

Опираясь на эту теорему, можно установить полноту еще ряда систем и тем самым расширить список примеров полных систем.

3) Система является полной. Для доказательства возьмем за систему систему 2), а за систему – систему 3) и используем тождество

.

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

5) Система является полной. Для доказательства возьмем за систему систему 3), а за систему – систему 5). Тогда

, .

6) Система является полной. Для доказательства возьмем за систему систему 3), а за систему – систему 6). Имеем

.

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

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

Свойства замыкания:

1) ;

2) ;

3) если , то ;

4) .

Класс (множество) называется функционально замкнутым, если .

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

В терминах замыкания и замкнутого класса можно дать другое определение полноты, эквивалентное исходному: – полная система, если .