Тема 3.7 Теорема Поста.

Для того чтобы система функций была полной, необходимо и достаточно, чтобы она не содержалась целиком ни в одном из классов T0, T1, L, S, M.

Доказательство. Докажем необходимость этого условия.

N = {f1, f2, ...fs, ...} полна в Р2, покажем, что тогда она не лежит целиком в Q, где через Q обозначим любой из классов T0, T1, L, S, M. Докажем от противного, пусть N I Q, очевидно, [N] I [Q] = Q, но [N] = P2, т.к. N – полна в Р2, отсюда Р2=Q, но это не так. Необходимость доказана.

Докажем достаточность. Пусть F = {f0, f1, fL, fm, fs}, где f0ÏT0, f1ÏT1, fLÏL, fsÏS и fmÏM. Покажем, что суперпозицией функций системы F можно получить полную систему G = {x1&x2, }.

1. Пусть g(x) = f0(x, …, x). Тогда g(0) = f( 0, …, 0) = 1. Далее возможны два случая:

g(1) = 1. Тогда g(x) º 1. Функция h(x) = f1(g(x), …, g(x)) = f1(1, …, 1) = 0, т.е. h(x) º 0. Получили константы 0 и 1;

g(1) = 0. Тогда g(x) =. По лемме о несамодвойственной функции суперпозицией над {fs, } можно получить одну из констант, например, 0. Тогда f0(0, …, 0) = 1 есть другая константа.

В обоих случаях получили обе константы.

2. По лемме о немонотонной функции суперпозицией над {fm, 0, 1} можно получить отрицание.

3. По лемме о нелинейной функции суперпозицией над {fL, 1, } можно получить конъюнкцию. Теорема доказана.

Следствие. Всякий замкнутый класс функций из Р2, не совпадающий с Р2 содержится, по крайней мере, в одном из замкнутых классов T0, T1, L, S, M. Действительно, если N не является подмножеством Q, то [N] = P2, что неверно. Примеры использования теоремы Поста.

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

Отметим еще одно обстоятельство, касающееся приведенной системы. Какую бы функцию из этой системы мы ни удалили, система станет неполной, действительно, {f2, f3, f4}ÌL, {f1, f3, f4}ÌT1, {f1, f2, f4}ÌT0, {f1, f2, f3}ÌM. 2. Мы знаем, что система {x1|x2} – полна в Р2. Какова для нее критериальная таблица? x1|x2= = x1x2A1.

Согласно критериальной таблице, полной является и система {1, x1x2, x1Ax2}.

	Т0	Т1	L	M	S
LT1	-	+	+	-	-
S\T0	-	-	-	+	-

и А – полная система функций.

Система функций {f1, ..., fs, ...} называется базисом в Р2,если она полна в Р2, но любая ее подсистема не будет полной. Например, система функций {x1&x2, 0, 1, x1x2x3} – базис.

Контрольная работа

Вариант I

1. Составить таблицу истинности для булевой функции:

2. Составить СДНФ и СКНФ для:

3. Найти минимальную (сокращённую) ДНФ для в.ф. ы

4. Определить является ли следующая система функций полной {0,1,x,}

5. Дана формула . Определите булевую функцию, которую реализует данная формула (составить таблицу истинности)

Вариант II

1. Составить таблицу истинности для булевой функции:

2. Составить СДНФ и СКНФ для:

3. Найти минимальную (сокращённую) ДНФ для в.ф. ы

4. Определить является ли следующая система функций полной

5. Дана формула . Определите булевую функцию, которую реализует данная формула (составить таблицу истинности)