Примеры использования теоремы Поста.

1. Покажем, что система функций {f₁ =x₁x₂, f₂ =0, f₃ =1, f₄ = x₁Åx₂Åx₃} полна в Р₂. Составим таблицу, которая называется критериальной :

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

Отметим еще одно обстоятельство, касающееся приведенной системы. Какую бы функцию из этой системы мы ни удалили, система станет неполной, действительно, {f₂, f₃, f₄}ÌL, {f₁, f₃, f₄}ÌT₁, {f₁, f₂, f₄}ÌT₀, {f₁, f₂, f₃}ÌM.

2. Мы знаем, что система {x₁|x₂} – полна в Р₂. Какова для нее критериальная таблица? x₁|x₂= = x₁x₂Å1.

3. Составим критериальную таблицу для другой полной системы функций из Р₂: {0, 1, x₁x₂, x₁Åx₂}.

Согласно критериальной таблице, полной является и система {1, x₁x₂, x₁Åx₂}. Константа 0 введена в эту систему для удобства, тогда мы можем записать полином Жегалкина в виде, где а равны 0, если члены х х ...х , в полиноме отсутствуют.

4. Выясним, полна ли система . Составим критериальную таблицу, очевидно . Чтобы показать, что , достаточно найти одну функцию и . Возьмем , удовлетворяющую требуемым условиям. Если f S\T₀, то f(0, ..., 0) = 1, f(1, ..., 1)=0, следовательно, f M, f T₁. Рассмотрим функцию h = x₁x₂ x₂x₃ x₁x₃=1, набор ее значений (11101000), h S\T₀, но h L. Следовательно, критериальная таблица имеет вид:

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

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

Система функций {f₁, ..., f_s, ...} называется базисом в Р₂,если она полна в Р₂, но любая ее подсистема не будет полной. Например, система функций {x₁&x₂, 0, 1, x₁ x₂ x₃} – базис.

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

Вариант I

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

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

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

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

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

Вариант II

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

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

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

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

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