Критерий полноты

Теперь мы в состоянии сформулировать и доказать критерий полноты (теорему Поста), определяющий необходимые и достаточные условия полноты системы функций. Предварим формулировку и доказательство критерия полноты несколькими необходимыми леммами, имеющими и самостоятельный интерес.

Лемма 2.7. Лемма о несамодвойственной функции.

Если f(x₁, ... , x_n) S , то из нее путем подстановки функций x и x можно получить константу.

Доказательство. Так как fS, то найдется набор значений переменных =(₁ ,...,_n) такой, что

f(₁ ,...,_n) = f(₁ ,...,_n)

Заменим аргументы в функции f :

x_i заменяется на ,

то есть положим , и рассмотрим функцию

.

Мы имеем

Тем самым мы получили константу ( правда, неизвестно, какая это константа: 0 или 1). 

Лемма 2.8. Лемма о немонотонной функции.

Если функция f(x₁ ,...,x_n) немонотонна, f(x₁ ,...,x_n)  M, то из нее путем замены переменных и подстановки констант 0 и 1 можно получить отрицание.

Доказательство. Так как f(x₁ ,...,x_n)  M, то найдутся наборы и значений ее переменных, , , такие что , причем хотя бы для одного значения i имеет место _i < _i . Выполним следующую замену переменных функции f:

x_i заменим на

После такой подстановки получим функцию одной переменной (x), для которой имеем:

(0) = ;

(1) = .

Это означает, что (x)=x. Лемма доказана. 

Лемма 2.9. Лемма о нелинейной функции.

Если f(x₁ ,...,x_n)  L , то из нее путем подстановки констант 0, 1 и использования функции x можно получить функцию x₁&x₂ .

Доказательство. Представим f в виде ДНФ ( например, совершенной ДНФ) и воспользуемся соотношениями:

Пример. Приведем два примера применения указанных преобразований.



Таким образом, функция, записанная в дизъюнктивной нормальной форме, после применения указанных соотношений, раскрытия скобок и несложных алгебраических преобразований переходит в полином по mod 2 ( полином Жегалкина):

где A₀ константа, а А_i - конъюнкция некоторых переменных из числа x₁ ,..., x_n, i = 1, 2, ... , r.

Если каждая конъюнкция A_i состоит лишь из одной переменной, то f - линейная функция, что противоречит условию леммы.

Следовательно, в полиноме Жегалкина для функции f найдется член, в котором содержится не менее двух сомножителей. Без ограничения общности можно считать, что среди этих сомножителей присутствуют переменные x₁ и x₂ . Тогда полином можно преобразовать следующим образом:

f = x₁x₂f₁(x₃ ,..., x_n) + x₁f₂(x₃ ,..., x_n) + x₂f₃(x₃ ,..., x_n) + f₄(x₃ ,..., x_n),

где f₁(x₃ ,..., x_n)  0 (в противном случае в полином не входит конъюнкция, содержащая конъюнкцию x₁x₂).

Пусть (₃ ,...,_n) таковы, что f₁(₃ ,...,_n) = 1. Тогда

(x₁ ,x₂) = f(x₁ ,x₂ , ₃ ,...,_n) = x₁x₂+x₁+x₂+ ,

где , ,  - константы, равные 0 или 1.

Воспользуемся операцией отрицания, которая у нас имеется, и рассмотрим функцию (x₁ ,x₂), получающуюся из (x₁ ,x₂) следующим образом:

(x₁ ,x₂) = (x₁+, x₂+)++.

Очевидно, что

(x₁ ,x₂) =(x₁+)(x₂+)+(x₁+)+(x₂+)+++ = x₁x₂ .

Следовательно,

(x₁ ,x₂) = x₁x₂ .

Лемма доказана полностью. 

Лемма 2.10. Основная лемма критерия полноты.

Если в классе F={ f } функций алгебры логики содержатся функции, не сохраняющие единицу, не сохраняющие 0, несамодвойственные и немонотонные:

;

,

то из функций этой системы операциями суперпозиции и замены переменных можно получить константы 0, 1 и функцию .

Доказательство. Рассмотрим функцию . Тогда

.

Возможны два случая последующих рассмотрений, в дальнейшем изложении обозначенные как 1) и 2).

1). Функция на единичном наборе принимает значение 0:

.

Заменим все переменные функции переменной x . Тогда функция

есть , ибо

и .

Возьмем несамодвойственную функцию . Так как функцию мы уже получили, то по лемме о несамодвойственной функции (лемма 2.7. ) из можно получить константу. Вторую константу можно получить из первой, используя функцию . Итак, в первом рассмотренном случае получены константы и отрицание.

2). Функция на единичном наборе принимает значение 1:

.

Заменим все переменные функции переменной x (отождествим все переменные). Тогда функция есть константа 1, ибо

и .

Вторая константа 0 получается из функции , не сохраняющей единицу, : .

Теперь на основании леммы о немонотонной функции (лемма 2.8) из имеющейся у нас немонотонной функции и полученных констант 0 и 1 можно получить отрицание . Второй случай, а вместе с ним и основная лемма критерия полноты, полностью доказаны. 

Теорема 2.11. Критерий полноты систем функций алгебры логики (теорема Поста).

Для того, чтобы система функций F = {f_i} была полной, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из пяти замкнутых классов T₀ , T₁ , L , S, M, то есть для каждого из классов T₀ , T₁ , L , S, M в F найдется хотя бы одна функция, этому классу не принадлежащая.

Необходимость. Пусть F - полная система. Допустим, что F содержится в одном из указанных классов, обозначим его через K, т.е. F  K. Последнее включение невозможно, так как K - замкнутый класс, не являющийся полной системой.

Достаточность. Пусть система функций F = {f_i} целиком не содержится ни в одном из пяти замкнутых классов T₀ , T₁ , L , S, M. Возьмем в F функции:

.

Тогда на основании основной леммы (лемма 2.10) из функции не сохраняющей 0, функции не сохраняющей 1, несамодвойственной и немонотонной функций можно получить константы 0, 1 и функцию отрицание :

.

На основании леммы о нелинейной функции (лемма 2.9) из констант, отрицания и нелинейной функции можно получить конъюнкцию:

.

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

Теорема доказана полностью. 

Примеры.

1. Покажем, что функция f(x,y) = xy образует полную систему. Построим таблицу значений функции xy:

x	y	xy
0	0	1
0	1	1
1	0	1
1	1	0

f(0,0) = 1, следовательно, x  yT₀ .

f(1,1) = 0, следовательно, x  yT₁ .

f(0,0) = 1, f(1,1) = 0, следовательно, x  yM .

f(0,1) = f(1,0) = 1, - на противоположных наборах x  y принимает одинаковые значения, следовательно x  yS .

Наконец, , что означает нелинейность функции x  y.

На основании критерия полноты можно утверждать, что f(x,y) = x  y образует полную систему. 

2. Покажем, что система функций образует полную систему.

Действительно, .

Тем самым среди функций нашей системы найдены: функция, не сохраняющая 0, функция, не сохраняющая 1, несамодвойственная, немонотонная и нелинейная функции. На основании критерия полноты можно утверждать, что система функций образует полную систему.

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

Сформулируем теперь три следствия из критерия полноты.

Следствие 1. Всякий замкнутый класс K функций алгебры логики, не совпадающий со всем множеством функций алгебры логики (KP₂), содержится по крайней мере в одном из построенных замкнутых классов.

Определение. Замкнутый класс K называется предполным, если K неполный и для любой функции f K класс K  {f} - полный.

Из определения следует, что предполный класс является замкнутым.

Следствие 2. В алгебре логики существует только пять предполных классов, а именно: T₀ ,T₁ , L , M , S .

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

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

Из доказательства критерия полноты следует, что можно выделить не более пяти функций. Из доказательства основной леммы (лемма 2.10) следует, что либо несамодвойственна, либо не сохраняет единицу и не монотонна. Поэтому нужно не более четырех функций.