Замкнутым (англ closed set). Определение: Замыканием

Определение:
Говорят, что функция монотонна (англ. monotonic function) , если ∀i(ai⩽bi)⇒f(a1,…,an)⩽f(b1,…,bn)∀i(ai⩽bi)⇒f(a1,…,an)⩽f(b1,…,bn).

Класс линейных функций LL.

Определение:
Говорят, что функция линейна (англ. linear function), если существуют такие a0,a1,a2,…,ana0,a1,a2,…,an, где ai∈{0,1},∀i=1,n¯¯¯¯¯¯¯¯ai∈{0,1},∀i=1,n¯, что для любых x1,x2,…,xnx1,x2,…,xn имеет место равенство:
f(x1,x2,…,xn)=a0⊕a1⋅x1⊕a2⋅x2⊕…⊕an⋅xnf(x1,x2,…,xn)=a0⊕a1⋅x1⊕a2⋅x2⊕…⊕an⋅xn.
Количество линейных функций от nn переменных равно  2n+1 2n+1.
Функция является линейной тогда, и только тогда, когда в ее полиноме Жегалкина присутствуют слагаемые, каждое из которых зависит не более чем от одной переменной. Построить полином Жегалкина можно с помощью преобразования Мебиуса.
Формулировка и доказательство критерия Поста
Теорема:
Набор булевых функций KK является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов S,M,L,T0,T1S,M,L,T0,T1, иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.
Доказательство:
▹▹
Необходимость.
Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора KK входили в один из перечисленных классов, то и все суперпозиции, а, значит, и замыкание набора входило бы в этот класс, и набор KK не мог бы быть полным.
Достаточность.
Докажем, что если набор KK не содержится полностью ни в одном из данных классов, то он является полным.

1. 
   Рассмотрим функцию, не сохраняющую ноль — f0f0 (то есть функцию, для которой f0(0)=1f0(0)=1). Тогда f0(1)f0(1) может принимать два значения:
   
   1. 
      f0(1)=1f0(1)=1, тогда f0(x,x,x,…,x)=1f0(x,x,x,…,x)=1.
      
   2. 
      f0(1)=0f0(1)=0, тогда f0(x,x,x,…,x)=¬xf0(x,x,x,…,x)=¬x.
      
2. 
   Рассмотрим функцию, не сохраняющую один — f1f1 (то есть функцию, для которой f1(1)=0f1(1)=0). Тогда f1(0)f1(0) может принимать два значения:
   
   1. 
      f1(0)=0f1(0)=0, тогда f1(x,x,x,…,x)=0f1(x,x,x,…,x)=0.
      
   2. 
      f1(0)=1f1(0)=1, тогда f1(x,x,x,…,x)=¬xf1(x,x,x,…,x)=¬x.
      

Таким образом, возможны четыре варианта:

• 
  Мы получили функцию ¬¬.
  

Используем несамодвойственную функцию fsfs. По определению, найдется такой вектор x0x0, что fs(x0)=fs(¬x0)fs(x0)=fs(¬x0). Где x0=(x01,x02,…,x0k)x0=(x01,x02,…,x0k).
Рассмотрим fs(xx01,xx02,…,xx0k)fs(xx01,xx02,…,xx0k), где либо xx0i=xxx0i=x, при x0i=1x0i=1. Либо xx0i=¬xxx0i=¬x, при x0i=0x0i=0. Нетрудно заметить, что fs(0)=fs(1)⇒fs=constfs(0)=fs(1)⇒fs=const. Таким образом мы получили одну из констант.

• 
  Мы получили ¬¬ и 0⇒0⇒ имеем константу, равную 11, поскольку ¬0=1¬0=1.
  
• 
  Мы получили ¬¬ и 1⇒1⇒ имеем константу, равную 00, поскольку ¬1=0¬1=0.
  
• 
  Мы получили 11 и 00.
  

Рассмотрим немонотонную функцию fmfm. Существуют такие x1,x2,…,xnx1,x2,…,xn, что fm(x1,x2,…,xi−1,0,xi+1,…,xn)=1fm(x1,x2,…,xi−1,0,xi+1,…,xn)=1, fm(x1,x2,…,xi−1,1,xi+1,…,xn)=0fm(x1,x2,…,xi−1,1,xi+1,…,xn)=0, зафиксируем все x1,x2,…,xnx1,x2,…,xn, тогда fm(x1,x2,…,xi−1,x,xi+1,…,xn)=¬xfm(x1,x2,…,xi−1,x,xi+1,…,xn)=¬x.
В итоге имеем три функции: ¬¬, 00, 11.
Используем нелинейную функцию flfl. Среди нелинейных членов flfl (ее представления в виде полинома Жегалкина), выберем тот, в котором минимальное количество элементов. Все аргументы кроме двух в этом члене приравняем единице, оставшиеся два назовем x1x1 и x2x2. Все элементы, не входящие в данный член, примем равными нулю. Тогда эта функция будет представима в виде gl=x1∧x2[⊕x1][⊕x2][⊕ 1]gl=x1∧x2[⊕x1][⊕x2][⊕ 1], где в квадратных скобках указаны члены, которые могут и не присутствовать (остальные слагаемые будут равны нулю, поскольку в них есть как минимум один аргумент, не входящий в выбранный член, так как в выбранном члене минимальное число элементов).