Toiminnallinen täydellisyys

Loogisten operaatioiden tai Boolen funktioiden joukon toiminnallinen täydellisyys on kyky ilmaista kaikki mahdolliset totuustaulukoiden arvot käyttämällä kaavoja tämän joukon elementeistä. Matemaattinen logiikka käyttää yleensä seuraavia operaatioita: konjunktio ( ), disjunktio ( ), negaatio ( ), implikaatio ( ) ja ekvivalenssi ( ). Tämä toimintosarja on toiminnallisesti valmis. Mutta se ei ole toiminnallisesti täydellinen järjestelmä, koska: $\maa$ $\lor$ $\neg$ $\to$ $\vasen oikea nuoli$

A\to B=\neg A\tai B

A\vasen oikea nuoli B=(A\–B)\maa (B\–A)

Se on siis myös toiminnallisesti täydellinen järjestelmä. Mutta voidaan ilmaista ( de Morganin lain mukaan ) myös seuraavasti: $\{\neg ,\land ,\lor \}$ $\lor$

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

$\maa$ voidaan myös määritellä läpi samalla tavalla. $\lor$

Se voidaan ilmaista myös seuraavasti : $\vee$ $\nuoli oikealle$

\A\vee B:=(A\nuoli oikealle B)\nuoli oikealle B.

Joten yksi niistä on myös minimaalisesti toiminnallisesti täydellinen järjestelmä. ${\näyttötyyli \{\neg \))$ $\{\land ,\lor ,\rightarrow \}$

Täydellisyyskriteeri

Postin kriteeri kuvaa tarpeelliset ja riittävät ehdot Boolen funktiojoukkojen toiminnalliselle täydellisyydelle. Sen muotoili amerikkalainen matemaatikko Emil Post vuonna 1941 .

Kriteeri:

Joukko Boolen funktioita on toiminnallisesti täydellinen , jos ja vain jos se ei sisälly kokonaan mihinkään esitäydetyistä luokista .