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

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

19.12.2020


Функциональная полнота множества логических операций или булевых функций — это возможность выразить все возможные значения таблиц истинности с помощью формул из элементов этого множества. Математическая логика обычно использует такой набор операций: конъюнкция ( ∧ {displaystyle land } ), дизъюнкция ( ∨ {displaystyle lor } ), отрицание ( ¬ {displaystyle eg } ), импликация ( → {displaystyle o } ) и эквиваленция ( ↔ {displaystyle leftrightarrow } ). Это множество операций является функционально полным. Но оно не является минимальной функционально полной системой, поскольку:

A → B = ¬ A ∨ B {displaystyle A o B= eg Alor B} A ↔ B = ( A → B ) ∧ ( B → A ) {displaystyle Aleftrightarrow B=(A o B)land (B o A)}

Таким образом { ¬ , ∧ , ∨ } {displaystyle { eg ,land ,lor }} также является функционально полной системой. Но ∨ {displaystyle lor } также может быть выражено (в соответствии с законом де Моргана) как:

A ∨ B = ¬ ( ¬ A ∧ ¬ B ) . {displaystyle Alor B= eg ( eg Aland eg B).}

∧ {displaystyle land } также может быть определена через ∨ {displaystyle lor } подобным образом.

Также ∨ {displaystyle vee } может быть выражена через → {displaystyle ightarrow } следующим образом:

  A ∨ B := ( A → B ) → B . {displaystyle Avee B:=(A ightarrow B) ightarrow B.}

Итак { ¬ } {displaystyle { eg }} и одна из { ∧ , ∨ , → } {displaystyle {land ,lor , ightarrow }} является минимальной функционально полной системой.

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

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

Критерий:

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

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

Множества из одного элемента { | } {displaystyle {|}} (штрих Шеффера), { ↓ } {displaystyle {downarrow }} (стрелка Пирса) Множества двух элементов { ∨ , ¬ } , { ∧ , ¬ } , { → , ¬ } , { → , ⊥ } , { ↛ , ⊤ } , { → , ↛ } , { → , ↮ } , { ↛ , ↔ } {displaystyle {lor ,lnot },{land ,lnot },{ o ,lnot },{ o ,ot },{ ot o , op },{ o , ot o },{ o , ot leftrightarrow },{ ot o ,leftrightarrow }} Множества трёх элементов { ∨ , ↔ , ⊥ } , { ∨ , ↔ , ↮ } , { ∨ , ↮ , ⊤ } , { ∧ , ↔ , ⊥ } , { ∧ , ↔ , ↮ } , { ∧ , ↮ , ⊤ } {displaystyle {lor ,leftrightarrow ,ot },{lor ,leftrightarrow , ot leftrightarrow },{lor , ot leftrightarrow , op },{land ,leftrightarrow ,ot },{land ,leftrightarrow , ot leftrightarrow },{land , ot leftrightarrow , op }} , ⟨ ∧ , ⊕ , 1 ⟩ {displaystyle {igl langle }wedge ,oplus ,1{igr angle }} (см. алгебра Жегалкина), ⟨ ∨ , ⊙ , 0 ⟩ {displaystyle {igl langle }lor ,odot ,0{igr angle }} (инверсный к предыдущему)