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

Пусть $A$ — некоторое подмножество функций из $P_2$. Замыканием множества $A$ называется множество $[A]$ всех функций алгебры логики, представимых в виде формул над множеством $A$.

Полное описание всех замкнутых классов было дано американским математиком Э. Постом. В частности, он доказал, что множество всех замкнутых классов булевых функций счетно и в каждом замкнутом классе $A$ можно выделить конечную подсистему $A'$, порождающую $A$, т.е. имеющую своим замыканием класс $A$, т.е. $A = [A']$ .

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

  • Любое множество является подмножеством своего замыкания: $A\subseteq[A]$.
  • Замыкание подмножества является подмножеством замыкания: $A\subseteq B \Rightarrow [A]\subseteq[B]$. Следует заметить, что из строгого вложения множеств следует лишь нестрогое вложение их замыканий: $A\subset B \Rightarrow [A]\subseteq[B]$.
  • Многократное применение операции замыкания эквивалентно однократному: $=[A]$

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

Пример:

  • Пусть $A = P_2$. Очевидно, что $[A] = P_2$, т.е. класс $A$ является замкнутым.
  • Класс $A = \ { 1,x_1 + x_2\ } $ не замкнут, так как $[A]$ содержит константу $0 = 1 + 1$.

Система функций $A$ называется (функционально) полной, если любая функция алгебры логики может быть записана в виде формулы над $A$, т.е. если $[A] = P_2$

Пример:

  • Система $P_2$ является полной.
  • Система $ { \bar { x } ,x_1 \wedge x_2,x_1 \vee x_2 } $ полна в силу следствия 1.1.
  • Система $\ { 0,1\ } $, очевидно, не полна.

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

Теорема (сведение к заведомо полной системе). Пусть даны две системы $A,В$ функций из $P_2$, относительно которых известно, что система $A$ полна и каждая ее функция представима в виде формулы над $B$. Тогда система $B$ является полной.

Доказательство. По условию теоремы $[A] = P_2$ и $A \subseteq [B]$. Тогда в силу свойства (2) операции замыкания мы имеем

$P_2 = [A] \subseteq $.

Применив свойство (1), получим

$P_2 \subseteq [B]$.

С другой стороны, очевидно, что

$P2 \supseteq [B]$,

Следовательно, имеет место равенство $[B] = P_2$, т.е. система $B$ является полной.