Completitudine funcțională

Completitudinea funcțională a unui set de operații logice sau funcții booleene este capacitatea de a exprima toate valorile posibile ale tabelelor de adevăr folosind formule din elementele acestui set. Logica matematică utilizează de obicei următorul set de operații: conjuncție ( ), disjuncție ( ), negație ( ), implicație ( ) și echivalență ( ). Acest set de operațiuni este complet funcțional. Dar nu este un sistem minim complet funcțional, deoarece: $\teren$ $\lor$ $\neg$ $\la$ $\leftrightarrow$

A\to B=\neg A\lor B

A\leftrightarrow B=(A\la B)\land (B\la A)

Astfel, este și un sistem complet funcțional. Dar poate fi exprimat (conform legii lui de Morgan ) ca: $\{\neg ,\land ,\lor \}$ $\lor$

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

$\teren$ poate fi, de asemenea, definit printr -un mod similar. $\lor$

Poate fi exprimat și în termeni de: $\vee$ $\sageata dreapta$

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

Deci, unul dintre ele este și un sistem minim complet funcțional. $\{\neg \)$ $\{\land ,\lor ,\rightarrow \}$

Criteriul de completitudine

Criteriul lui Post descrie condițiile necesare și suficiente pentru completitudinea funcțională a mulțimilor de funcții booleene. A fost formulată de matematicianul american Emil Post în 1941 .

Criteriu:

Un set de funcții booleene este complet funcțional dacă și numai dacă nu este complet conținut în nici una dintre clasele precompletate .