Функциональная полнота

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

Таким образом также является функционально полной системой. Но также может быть выражено (в соответствии с законом де Моргана) как:

также может быть определена через подобным образом.

Также может быть выражена через следующим образом:

Итак и одна из является минимальной функционально полной системой.

Критерий полноты

Критерий Поста описывает необходимые и достаточные условия функциональной полноты множеств булевых функций. Был сформулирован американским математиком Эмилем Постом в 1941 году.

Критерий:

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

Минимальные множества бинарных операций

Множества из одного элемента
(штрих Шеффера), (стрелка Пирса)
Множества двух элементов
Множества трёх элементов
.

То же в другой нотации:

, , , ,  (см. алгебра Жегалкина), (инверсный к предыдущему).

См. также

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.