Funktionell fullständighet

Den funktionella fullständigheten för en uppsättning logiska operationer eller booleska funktioner är förmågan att uttrycka alla möjliga värden av sanningstabeller med formler från elementen i denna uppsättning. Matematisk logik använder vanligtvis följande uppsättning operationer: konjunktion ( ), disjunktion ( ), negation ( ), implikation ( ) och ekvivalens ( ). Denna uppsättning operationer är funktionellt komplett. Men det är inte ett minimalt funktionellt komplett system, eftersom: $\landa$ $\lor$ $\neg$ $\till$ $\vänster högerpil$

A\till B=\neg A\eller B

A\vänsterhögerpil B=(A\till B)\land (B\till A)

Därmed är det också ett funktionellt komplett system. Men kan också uttryckas (enligt de Morgans lag ) som: $\{\neg ,\land ,\lor \}$ $\lor$

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

$\landa$ kan också definieras genom på liknande sätt. $\lor$

Det kan också uttryckas i termer av: $\vee$ $\höger pil$

\A\vee B:=(A\högerpil B)\högerpil B.

Så en av dem är också ett minimalt funktionellt komplett system. ${\displaystyle \{\neg \))$ $\{\land ,\lor ,\högerpil \}$

Fullständighetskriterium

Posts kriterium beskriver de nödvändiga och tillräckliga villkoren för den funktionella fullständigheten av uppsättningar av booleska funktioner. Den formulerades av den amerikanske matematikern Emil Post 1941 .

Kriterium:

En uppsättning booleska funktioner är funktionellt komplett om och bara om den inte är helt inkluderad i någon av de förkompletta klasserna .