Функціональна повнота

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Функціональна повнота множини логічних операцій чи булевих функцій — це можливість подати всі можливі значення таблиць істинності за допомогою формул із елементів цієї множини.

У логіці зазвичай застосовують такий набір операцій: кон'юнкція (\land), диз'юнкція (\lor), заперечення (\neg), імплікація (\to) та еквівалентність (\leftrightarrow). Ця множина операцій є функціонально повною. Але вона не є мінімальною функціонально повною системою, оскільки:

 A \to B = \neg A \lor B
 A \leftrightarrow B = (A \to B) \land (B \to A)

Отже \{\neg, \land, \lor\} також є функціонально повною системою. Але \lor також може бути виражене (за законом де Моргана) як:

A \lor B = \neg(\neg A \land \neg B).

\land також може бути визначено через \lor подібним чином.

Також  \vee може бути виражена через  \rightarrow таким чином:

 \ A \vee B := (A \rightarrow B) \rightarrow B.

Отже ~\{\neg\} та одна з \{\land, \lor, \rightarrow\} є мінімальною функціонально повною системою.

У контексті логіки висловлювань, функціонально повний набір зв'язків також називається (неформально) адекватним[Джерело?].

Критерій повноти[ред.ред. код]

Докладніше: Критерій Поста

Критерій Поста сформульовано американським математиком Емілем Постом 1941 року. Він описує необхідні та достатні умови функціональної повноти для множини булевих функцій.

Критерій:

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

Мінімальні множини бінарних операцій[ред.ред. код]

множини з одного елемента
штрих Шефера (або {NAND}[1]), стрілка Пірса (або {NOR}[2]).
множини двох елементів
\{ \lor, \lnot \}, \{ \land, \lnot \}, \{ \to, \lnot \},
\{ \to, \bot \}, \{ \not\to, \top \},
\{ \to, \not\to \}, \{ \to, \not\leftrightarrow \}, \{ \not\to, \leftrightarrow \}
множини трьох елементів
{\lor, \leftrightarrow, \bot}, {\lor, \leftrightarrow, \not\leftrightarrow}, {\lor, \not\leftrightarrow, \top}, {\land, \leftrightarrow, \bot}, {\land, \leftrightarrow, \not\leftrightarrow}, {\land, \not\leftrightarrow, \top}.

Посилання[ред.ред. код]

Джерела[ред.ред. код]

  • Wernick, William (1942) "Complete Sets of Logical Functions," Transactions of the American Mathematical Society 51: 117–32.

Дивись також[ред.ред. код]