Функциональная полнота булевых функций

Теорема.

Каждый из классов Поста замкнут.

Замкнутые классы Поста попарно различны.

В таблице 3.28 приведем результаты исследования на принадлежность классам Поста каждой булевой функции двух переменных.

Таблица 3.28 − Принадлежность булевых функций классам Поста

Булева функция	Формула	Классы Поста
Константа 0		*	-	-	*	*
Конъюнкция		*	*	-	*	-
Отрицание импликации		*	-	-	-	-
Повторение первого аргумента		*	*	*	*	*
Отрицание обратной импликации		*	-	-	-	-
Повторение второго аргумента		*	*	*	*	*
Сумма по модулю 2	)	*	-	-	-	*
Дизъюнкция		*	*	-	*	-
Стрелка Пирса		-	-	-	-	-
Эквиваленция		-	*	-	-	*
Отрицание второго аргумента		-	-	*	-	*
Обратная импликация		-	*	-	-	-
Отрицание первого аргумента		-	-	*	-	*
Импликация		-	*	-	-	-
Штрих Шеффера		-		-	-	-
Константа 1		-	*		*	*

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

Дата добавления: 2014-10-22