Funkční úplnost

Funkční úplností množiny logických operací nebo booleovských funkcí je schopnost vyjádřit všechny možné hodnoty pravdivostních tabulek pomocí vzorců z prvků této množiny. Matematická logika obvykle používá následující sadu operací: spojka ( ), disjunkce ( ), negace ( ), implikace ( ) a ekvivalence ( ). Tato sada operací je funkčně kompletní. Nejde však o minimální funkčně kompletní systém, protože: $\přistát$ $\lor$ $\neg$ $\na$ $\leftrightarrow$

A\to B=\neg A\nebo B

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

Jedná se tedy také o funkčně kompletní systém. Ale může být také vyjádřen (podle de Morganova zákona ) jako: $\{\neg ,\land ,\lor \}$ $\lor$

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

$\přistát$ lze také definovat podobným způsobem. $\lor$

Dá se také vyjádřit slovy: $\vee$ $\šipka doprava$

\A\vee B:=(A\šipka vpravo B)\šipka vpravo B.

Jedním z nich je tedy také minimálně funkčně kompletní systém. ${\displaystyle \{\neg \))$ $\{\land ,\lor ,\rightarrow \}$

Kritérium úplnosti

Postovo kritérium popisuje nezbytné a dostatečné podmínky pro funkční úplnost množin booleovských funkcí. Zformuloval jej americký matematik Emil Post v roce 1941 .

Kritérium:

Sada booleovských funkcí je funkčně úplná tehdy a pouze tehdy , není-li zcela obsažena v žádné z předkompletních tříd .