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

Шаблон:Нет источников Функциональная полнота множества логических операций или булевых функций — это возможность выразить все возможные значения таблиц истинности с помощью формул из элементов этого множества. Математическая логика обычно использует такой набор операций: конъюнкция ($\wedge$), дизъюнкция ($\vee$), отрицание ($\mathrm{\neg }$), импликация ($\to$) и эквиваленция ($\leftrightarrow$). Это множество операций является функционально полным. Но оно не является минимальной функционально полной системой, поскольку:

$A\to B=\mathrm{\neg }A\vee B$

$A\leftrightarrow B=(A\to B)\wedge (B\to A)$

Таким образом $\{\mathrm{\neg },\wedge ,\vee \}$ также является функционально полной системой. Но $\vee$ также может быть выражено (в соответствии с законом де Моргана) как:

$A\vee B=\mathrm{\neg }(\mathrm{\neg }A\wedge \mathrm{\neg }B)$

$\wedge$ также может быть определена через $\vee$ подобным образом:

$A\wedge B=\mathrm{\neg }(\mathrm{\neg }A\vee \mathrm{\neg }B)$

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

$A\vee B=(A\to B)\to B$

Итак $\{\mathrm{\neg }\}$ и одна из $\{\wedge ,\vee ,\to \}$ является минимальной функционально полной системой.

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

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

Критерий:

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

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

Множества из одного элемента

$\{|\}$ (штрих Шеффера), $\{\downarrow \}$ (стрелка Пирса)

Множества двух элементов

$\{\vee ,\mathrm{\neg }\},\{\wedge ,\mathrm{\neg }\},\{\to ,\mathrm{\neg }\},\{\to ,\mathrm{\perp }\},\{\to ̸,\mathrm{\top }\},\{\to ,\to ̸\},\{\to ,\leftrightarrow ̸\},\{\to ̸,\leftrightarrow \}$

Множества трёх элементов

$\{\vee ,\leftrightarrow ,\leftrightarrow ̸\},\{\vee ,\leftrightarrow ̸,\mathrm{\top }\},\{\wedge ,\leftrightarrow ,\mathrm{\perp }\},\{\wedge ,\leftrightarrow ,\leftrightarrow ̸\},\{\wedge ,\leftrightarrow ̸,\mathrm{\top }\},\{\vee ,\leftrightarrow ,\mathrm{\perp }\}$.

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

$⟨\vee ,\odot ,\oplus ⟩$, $⟨\vee ,\oplus ,1⟩$, $⟨\wedge ,\odot ,0⟩$, $⟨\wedge ,\odot ,\oplus ⟩$, $⟨\wedge ,\oplus ,1⟩$ (см. алгебра Жегалкина), $⟨\vee ,\odot ,0⟩$ (инверсный к предыдущему).

См. также

• Замкнутые классы булевых функций