Normaalvormen van logische formules

Propositielogica: Geldig gevolg en consistentie

Normaalvormen van logische formules

Een verzameling $\mathcal{C}$ van connectieven heet functioneel volledig als elke formule uit de propositielogica equivalent is met een formule die alleen connectieven uit $\mathcal{C}$ gebruikt.

De verzameling $\{\neg, \land, \lor\}$ is functioneel volledig.

De formules $\varphi\rightarrow\psi$ en $\neg\,\varphi\lor \psi$ zijn logisch equivalent. De formules $\varphi\leftrightarrow\psi$ en $(\varphi\rightarrow\psi)\land(\psi\rightarrow\varphi)$ zijn logisch equivalent. We kunnen in de propositielogica dus zonder de implicatie en equivalentie connectieven als we de connectieven $\neg$ , $\land$ en $\lor$ maar behouden.

De verzameling $\{\neg,\rightarrow\}$ is functioneel volledig.

De formules $\varphi\lor \psi$ en $\neg\,\varphi\rightarrow \psi$ zijn logisch equivalent. De formules $\varphi\land \psi$ en $\neg(\varphi\rightarrow \neg\,\psi)$ zijn logisch equivalent. We kunnen in de propositielogica dus zonder de disjunctie, conjunctie en equivalentie connectieven als we de connectieven $\neg$ en $\rightarrow$ maar behouden.

We noteren het exclusieve disjunctie connectief met het symbool $\oplus$ (of $\veebar$ ); de waarheidstabel van dit connectief is: $\begin{array}{cc|c} \varphi & \psi & \varphi\oplus \psi \\ \hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1\\ 1 & 1 & 0 \end{array}$ Als we in het alfabet van de propositielogica het symbool $\top$ voor een altijd ware bewering (verum, een connectief zonder argumenten) opnemen, dan is verzameling $\{\top, \oplus, \land\}$ functioneel volledig.

De logische formules $\neg\,\varphi$ en $\top \oplus \varphi$ zijn logisch equivalent. De logische formules $\varphi\lor \psi$ en $(\varphi\oplus \psi)\oplus(\varphi\land \psi)$ zijn logisch equivalent. zijn logisch equivalent. We kunnen in de propositielogica dus zonder de disjunctie, implicatie en equivalentie connectieven als we de connectieven $\top$ , $\oplus$ en $\land$ maar behouden.

Merk op dat $\top\oplus\top$ in deze propositielogica een altijd onware bewering is. Dit wordt falsum genoemd en meestal genoteerd met $\bot$ .

We definiëren het noch connectief met symbool $\star$ via onderstaande waarheidstabel $\begin{array}{cc|c} \varphi & \psi & \varphi\star \psi \\ \hline 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0\\ 1 & 1 & 0 \end{array}$ Voor formules $\varphi$ en $\psi$ geldt dat $\varphi\star \psi$ en $\neg\varphi\land\neg\psi$ equivalent zijn.

De verzameling $\{\star\}$ is functioneel volledig.

De logische formules $\neg\,\varphi$ en $\varphi\ast \varphi$ zijn logisch equivalent. De logische formules $\varphi\lor \psi$ en $(\varphi\star \psi)\star(\varphi\star \psi)$ zijn logisch equivalent. De logische formules $\varphi\land \psi$ en $\bigl((\varphi\star \varphi)\star(\psi\star \psi)\bigr)\star\bigl((\varphi\star \varphi)\star(\psi\star \psi)\bigr)$ zijn logisch equivalent. We kunnen in de propositielogica dus zonder de gebruikelijke connectieven als we maar het noch connectief $\star$ introduceren.

Normaalvormen Een literaal is een propositieletter of een negatie van een propositieletter. We definiëren de volgende normaalvormen van logische formules.

Disjunctieve normaalvorm

Een logische formule $\varphi$ is in disjunctieve normaalvorm als $\varphi$ een disjunctie is van conjuncties van literalen, d.w.z. de volgende vorm bezit $\varphi=D_1\lor\ldots\land D_{n}$ waarbij elk disjunctielid $D_i=l_{i1}\land \ldots\land L_{im_i}$ een conjunctie van literalen $l_{i1},\ldots, L_{im_i}$ is.

Een disjunctieve normaalvorm is volledig als elke propositievariabele precies één keer voorkomt in elk disjunctielid.

Voorbeelden van formules in normaalvorm: $p,\;\; \neg\,p,\;\; p\lor\neg\,q,\;\; \neg\,p\land q\text{ en }$ $(p\land r)\lor(\neg\,p\land r)\lor(\neg\,p\land\neg\, r)$ Voorbeelden van formules die
in disjunctieve normaalvorm zijn: $\neg\neg\,p\text{ en }\neg\,p\land(p\lor q)$ Ze zijn equivalent met de normaalvormen $p\text{ en }\neg\,p\land q$ $p\lor q$ is niet volledig, maar wel equivalent met de volledige normaalvorm $(p\land q)\lor (\neg\,p\land q)\lor (p\land\neg\,q)$ .

Conjunctieve normaalvorm

Een logische formule $\varphi$ is in conjunctieve normaalvorm als $\varphi$ een conjunctie is van disjuncties van literalen, d.w.z. de volgende vorm bezit $\varphi=C_1\land\ldots\land C_{n}$ waarbij elk conjunctielid $C_i=l_{i1}\lor \ldots\lor L_{im_i}$ een disjunctie van literalen $l_{i1},\ldots, L_{im_i}$ is.

Voorbeelden van formules in normaalvorm: $p,\;\; \neg\,p,\;\; p\land\neg\,q,\;\; \neg\,p\lor q\text{ en }$ $(p\lor r)\land(\neg\,p\lor r)\land(\neg\,p\lor\neg\, r)$ Voorbeelden van formules die
in conjunctieve normaalvorm zijn: $\neg\neg\,p\text{ en }\neg\,p\lor(p\land q)$ Ze zijn equivalent met de normaalvormen $p\text{ en }\neg\,p\lor q$

Algebraïsche normaalvorm

Een logische formule $\varphi$ is in algebraïsche normaalvorm als $\varphi$ een exclusieve disjunctie is van conjuncties van propositievariabelen of een exclusieve disjunctie van verum met zo'n formule, d.w.z. de volgende vorm bezit $\varphi=C_1\oplus\ldots\oplus C_{n}\text{ of } \varphi=\top\oplus C_1\oplus\ldots\oplus C_{n}$ waarbij elk conjunctielid $C_i=P_{i1}\land \ldots\land P_{im_i}$ een conjunctie van propositievariabelen $l_{i1},\ldots, L_{im_i}$ is.

Voorbeelden van formules in algebraísche normaalvorm: $p,\;\; \top\oplus\,p,\;\; p\land q,\;\; \top\oplus p\land q,\text{ en }$ $\top\oplus (p\land r)\oplus( p\land r)$ Voorbeelden van formules die
in algebraísche normaalvorm zijn: $\top\oplus (\top\oplus p)\text{ en }(\top\oplus p)\land(p\oplus q)$ Ze zijn equivalent met de normaalvormen $p\text{ en }q\oplus(p\land q)$

Omzettingen van logische formules in een normaalvorm verloopt meestal via een reeks van toepassingen van bekende tautologieën zoals de regels van De Morgan, distributiviteitsregels en dubbele negatie. Elke logische formule is logisch equivalent met precies één volledige disjunctieve normaalvorm (op associatieve en distributieve regels na)

De algebraïsche normaalvorm is de meest simpele normaalvorm omdat hier niet met literalen gewerkt hoeft te worden, maar enkel met propositievariabelen en het verum connectief. Ook geldt dat logisch equivalente formules dezelfde algebraïsche normaalvorm hebben. Hiermee kan logische equivalentie in een 'automatische stelling bewijzer' eenvoudiger nagegaan worden dan met de volledige disjunctieve normaalvorm.