Замыкание и его свойства

С понятием полноты тесно связано понятие замыкания и замкнутого класса. Пусть М - некоторое подмножество функций из P₂. Замыканием множества М называется множество всех булевых функций, представимых в виде формул через функции множества М. Замыкание множества М обозначается [М].

Примеры. 1. [S_i (i=1,...,7)] = P₂.

2. Пусть M={1,x₁Åx₂}. Замыканием этого множества будет множество L всех линейных функций, то есть функций, имеющих вид: f(x₁,...,x_n)=c₀Åc₁x₁Å...Åc_nx_n, где константы c_i принимают значения либо 0, либо 1 (i = 0,1,...,n).

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

1. Множество является подмножеством своего замыкания, т.е. М Í [М].

2. Замыкание к замыканию множества М равно замыканию множества М, т.е. [[М]] = [М].

3. Если множество М₁ является подмножеством множества М₂, то и для их замыканий справедливо такое же соотношение: (М₁ Í М₂) ® ([М₁] Í [М₂]).

4. Объединение замыканий является подмножеством замыкания от объединения:

[М₁] È [М₂] Í [М₁ È М₂].

Множество М называется функционально замкнутым, если оно совпадает со своим замыканием: [М] = М. Замкнутое множество иногда называют замкнутым классом.

Примеры. 1. Класс М=P₂ является замкнутым классом.

2. Класс L всех линейных функций является замкнутым, так как выражение, составленное из линейных выражений, является линейным.

3. Множество M={1,x₁Åx₂} не замкнуто, так как, например, отрицание, которое можно выразить через функции этого множества ( =xÅ1), в самом этом множестве не содержится.

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

В терминах замыкания и замкнутого класса можно дать другое определение полноты (эквивалентное исходному): множество M - полная система, если замыкание этого множества представляет собой все множество булевых функций: [M] = P₂.