5. Теория полноты

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

Проверим вначале критерий Поста на известных примерах, а затем докажем его справедливость в общем случае.

Пример: .

По теореме о представлении любой булевой функции в виде СДНФ данная система полна. И в тоже время система не содержится ни в одном из классов T₀, T₁ , S, M, L, поэтому критерий Поста справедлив для данной системы.

Пример:

Полнота данной системы следует из теоремы о представлении любой булевой функции в виде полинома Жегалкина, и вновь критерий Поста справедлив для данной системы, т.к. система не принадлежит ни одному из пяти классов.

Пример:  не полная, так как

и критерий Поста справедлив для данной системы, т.к. L.

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

Необходимость : пусть система K полна.

Покажем, что она не принадлежит ни одному из пяти классов. Допустим противное : система принадлежит одному из пяти классов. Пусть KT₀ .Т.е. все функции K сохраняют 0. Но тогда и любая суперпозиция функций из K будет сохранять 0. Но тогда [K] , и K  неполная. Пусть K T₁, тогда любая суперпозиция из K сохраняет 1, тогда [K]. Пусть KS, тогда суперпозиция любых функций будет самодвовойственна, тогда [K].

Пусть KM, тогда [K]. Пусть KL, тогда [K]. Получаем противоречие (система не является полной, в силу замкнутости классов T₀, T₁, S, M, L относительно суперпозиций).

Достаточность : пусть система K не содержится ни в одном из пяти классов, т.е.

Построим заведомо полную систему .

I этап :

II этап :

I этап: и, и переименуем все их переменные в:и:

X	f0	f1
0	1	1,0
1	1,0	0

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

1)

2)

3)

4)

Простейшими окажутся 1) и 4).

Рассмотрим 1) и 4) случаи.

1 случай :

X	f0	f1
0	1	1
1	1	0

т.е .

4 случай :

X	f0	f1
0	1	0
1	0	0

т.е .

Остались 2) и 3)

2 случай :

X	f0	f1
0	1	0
1	1	0

т.е .

Построим вывод :

.

M , следовательно по определению существует пара наборов (нижний строго больше верхнего), а значение функции наоборот :

Разобьем множество переменных на два множестваи.

- переменные, которые не изменяются в двух данных наборах, а - все остальные переменные:

И теперь все переменные множества переименнуем вx , а во все переменные множестваподставим соответствующие константы :

.

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

Например, пусть наборы были:

X1	x2	X3	x4	x5	fM
0	1	0	1	0	1
1	1	0	1	1	0