Замыкание. Свойства операции замыкания

Замкнутые классы

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

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

Отметим некоторые свойства замыкания:

1) ;

2) ;

3) если , то ;

4) если мы рассмотрим и , и , то .

Определение. Класс (множество) называется замкнутым, если .

Пример:

1) Класс является замкнутым классом.

2) – незамкнутый класс, так как , а

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

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

3.13. Классы и их свойства

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

1) , но .

2) .

Утверждение 2. – замкнутый класс.

Доказательство: Так как , рассмотрим суперпозицию

,

где . Тогда

.

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

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

1) , но .

2) .

Утверждение 3. – замкнутый класс.

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