Funkcionális teljesség

A logikai műveletek vagy Boole-függvények halmazának funkcionális teljessége az igazságtáblázatok összes lehetséges értékének kifejezése a halmaz elemeiből származó képletekkel. A matematikai logika általában a következő műveletsorokat használja: konjunkció ( ), diszjunkció ( ), tagadás ( ), implikáció ( ) és ekvivalencia ( ). Ez a műveletsor funkcionálisan teljes. De ez nem egy minimálisan funkcionálisan teljes rendszer, mert: $\föld$ $\lor$ $\neg$ $\nak nek$ $\bal jobbra nyíl$

A\-B=\neg A\vagy B

A\balra jobbra nyíl B=(A\B-be)\land (B\A-ba)

Így funkcionálisan is teljes rendszer. De kifejezhető ( de Morgan törvénye szerint ) így is: $\{\neg ,\land ,\lor \}$ $\lor$

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

$\föld$ keresztül is definiálható hasonló módon. $\lor$

A következőképpen is kifejezhető : $\vee$ $\jobb nyíl$

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

Az egyik tehát egy minimális funkcionálisan komplett rendszer is. ${\displaystyle \{\neg \))$ $\{\föld ,\lor ,\jobbra nyíl \}$

Teljességi kritérium

A Post kritériuma leírja a logikai függvényhalmazok funkcionális teljességének szükséges és elégséges feltételeit. Emil Post amerikai matematikus fogalmazta meg 1941- ben .

Kritérium:

A logikai függvények egy halmaza akkor és csak akkor funkcionálisan teljes , ha nem tartalmazza teljes mértékben egyik előre befejezett osztályban sem .