Русская Википедия:Функциональная полнота
Шаблон:Нет источников Функциональная полнота множества логических операций или булевых функций — это возможность выразить все возможные значения таблиц истинности с помощью формул из элементов этого множества. Математическая логика обычно использует такой набор операций: конъюнкция (<math>\land</math>), дизъюнкция (<math>\lor</math>), отрицание (<math>\neg</math>), импликация (<math>\to</math>) и эквиваленция (<math>\leftrightarrow</math>). Это множество операций является функционально полным. Но оно не является минимальной функционально полной системой, поскольку:
- <math> A \to B = \neg A \lor B </math>
- <math> A \leftrightarrow B = (A \to B) \land (B \to A)</math>
Таким образом <math>\{\neg, \land, \lor\}</math> также является функционально полной системой. Но <math>\lor</math> также может быть выражено (в соответствии с законом де Моргана) как:
- <math>A \lor B = \neg(\neg A \land \neg B)</math>
<math>\land</math> также может быть определена через <math>\lor</math> подобным образом:
- <math>A \land B = \neg(\neg A \lor \neg B)</math>
Также <math> \vee </math> может быть выражена через <math> \rightarrow </math> следующим образом:
- <math> \ A \vee B = (A \rightarrow B) \rightarrow B</math>
Итак <math>\{\neg\}</math> и одна из <math>\{\land, \lor, \rightarrow\}</math> является минимальной функционально полной системой.
Критерий полноты
Шаблон:Main Критерий Поста описывает необходимые и достаточные условия функциональной полноты множеств булевых функций. Был сформулирован американским математиком Эмилем Постом в 1941 году.
Критерий:
- Множество булевых функций является функционально полным тогда и только тогда, когда оно не содержится полностью ни в одном из предполных классов.
Минимальные множества бинарных операций
- Множества из одного элемента
- <math>\{ | \}</math> (штрих Шеффера), <math>\{ \darr \}</math> (стрелка Пирса)
- Множества двух элементов
- <math>\{ \lor, \lnot \}, \{ \land, \lnot \}, \{ \to, \lnot \}, \{ \to, \bot \}, \{ \not\to, \top \}, \{ \to, \not\to \}, \{ \to, \not\leftrightarrow \}, \{ \not\to, \leftrightarrow \}</math>
- Множества трёх элементов
- <math>\{ \lor, \leftrightarrow, \not\leftrightarrow \}, \{ \lor, \not\leftrightarrow, \top \}, \{ \land, \leftrightarrow, \bot \}, \{ \land, \leftrightarrow, \not\leftrightarrow \}, \{ \land, \not\leftrightarrow, \top \}, \{ \lor, \leftrightarrow, \bot \}</math>.
То же в другой нотации:
- <math>\bigl\langle \lor, \odot, \oplus \bigr\rangle</math>, <math>\bigl\langle \lor, \oplus, 1 \bigr\rangle</math>, <math>\bigl\langle \wedge, \odot, 0 \bigr\rangle</math>, <math>\bigl\langle \wedge, \odot, \oplus \bigr\rangle</math>, <math>\bigl\langle \wedge, \oplus, 1 \bigr\rangle</math> (см. алгебра Жегалкина), <math>\bigl\langle \lor, \odot, 0 \bigr\rangle</math> (инверсный к предыдущему).
См. также
