Propositielogica: Geldig gevolg en consistentie
Normaalvormen van logische formules
Functionele volledigheid 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 verzameling \(\{\neg,\rightarrow\}\) is functioneel volledig.
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.
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.
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 niet
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 niet
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 niet
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.
