4.14. Критерий функциональной полноты

ТЕОРЕМА 4.9

Класс B  P₂ является полной системой тогда и только тогда, когда он целиком не содержится ни в одном из классов Т₀, Т₁, S, L, M.

Доказательство

Необходимость. Пусть [B] = P₂. Тогда B целиком не содержится ни в одном из классов Т₀, Т₁, S, L, M, поскольку в противном случае всякий из перечисленных классов, содержащий B, являлся бы полной системой, что неверно.

Достаточность. Пусть B целиком не содержится ни в одном из классов Т₀, Т₁, S, L, M. Выделим из B пять функций f₀, f₁, f_S, f_L, f_M, которые не содержатся в перечисленных классах Т₀, Т₁, S, L, M соответственно. При этом не исключается совпадение некоторых из выделенных функций.

Покажем, что через выделенные функции системы B выражаются функции полной системы x₁& x₂ и .

4.14.1. Построение функций-констант

Рассмотрим функцию f₀. По определению f₀(0,..., 0) = 1.

Если f₀(1,..., 1) = 1, то h(x) = f₀(x,..., x) = 1, т.е. это функция, получаемая из f₀ отождествлением всех переменных, является константой 1. В противном случае f₀(1, . . . , 1) = 0. Поэтому f₀(x,...,x) = . Тогда по лемме о несамодвойственной функции из f₀ с помощью функции отрицания и тождественной функции можно получить одну из констант.

Вторая константа получается из первой константы с помощью отрицания (т.е. является отрицанием первой константы).

Значит, из f₀ можно получить либо одну из констант, либо обе константы и отрицание.

Рассмотрим функцию f₁. По определению этой функции f₁(1,...,1) = 0. Если f₁(0, . . . , 0) = 0, то f₁(x, . . . , x) = 0, т.е. это функция-константа 0.

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

Поэтому из f₀ и f₁ с помощью отождествления переменных всегда можно выразить обе функции-константы, а в некоторых случаях еще и функцию отрицания.

4.14.2. Построение отрицания

Рассмотрим функцию f_M. По лемме о немонотонной функции через f_M с помощью функций-констант и тождественной функции x можно выразить отрицание .

4.14.3. Построение конъюнкции

Рассмотрим функцию f_L. По лемме о нелинейной функции из f_L с помощью уже полученных функций 0, 1, и обозначений переменных можно выразить конъюнкцию x₁&x₂.

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

Доказательство окончено.

Упражнение.

Используя доказательство критерия полноты, выразить функции x₁&x₂ и через функции полной системы .

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

При этом если система B является конечной, то такая проверка может быть проведена за конечное время.

Для проверки полноты произвольной конечной системы B можно построить таблицу со строками, соответствующими функциям системы B, и пятью столбцами, соответствующими пяти классам: Т₀, Т₁, S, L и M.

Таблица заполняется символами "+" и "". Некоторый элемент таблицы это "+", если функция, соответствующая строке, содержится в классе функций, соответствующем столбцу. В противном случае элемент таблицы равен "".

Если в каждом столбце полученной таблицы имеется хотя бы один минус, то B  это полная система.

Если в таблице имеется столбец, содержащий только символы "+", то B  это неполная система.

Например. Для системы B = {x₁  x₂, x₁ + x₂} таблица имеет вид:

	Т0	Т1	S	L	M
x1  x2		+			
x1 + x2	+			+	

Следовательно, множество функций {x₁  x₂, x₁ + x₂}  это полная система.

Классы Т₀, Т₁, S, L и M объединяет одно общее свойство, которое состоит в том, что всякий из них является "почти" полным.