Beweis. Wir führen einen konstruktiven Beweis. Sei ϕ eine Formel.
1. Wir erstellen die Wahrheitstafel für ϕ. Hieraus konstruieren wir die Formel ϕ
(dazu gleich mehr).
2. Es bleiben die behaupteten Eigenschaften von ϕ' nachzuweisen. Aus der Konstruktion
wird klar sein, dass ϕ' in disjunktiver Normalform ist. Wir zeigen dann noch, dass
ϕ ≡ ϕ'
glt (dazu auch gleich mehr).
Wir erstellen die Wahrheitstafel für ϕ. Diese ist wie folgt aufgebaut: Es gibt für jede in
ϕ vorkommende Variable eine Spalte sowie eine Ergebnisspalte. Es gibt für jede mögliche
Variablenbelegung β eine Zeile. In ihr stehen die Werte der Variablen sowie β(ϕ) in der
Ergebnisspalte. Die Formel ϕ' wird nun wie folgt gebildet:
Es gibt für jede Zeile der Wahrheitstafel mit β(ϕ) = 1 ein Monom in ϕ'. Ein solches Monom enthält genau ein Literal für
jede Variable von ϕ, wobei genau die Literale negiert sind, für die die Variable in der Zeile
0 ist.
Als Beispiel für die Konstruktion betrachten wir die Formel ϕ = (¬a → b)∧(b∧c).
$$ \begin{array}{cccc} {\beta(a)} & {\beta(b)} & {\beta(c)} & {\beta((\neg a \rightarrow b) \wedge(b \wedge c))} \\ {0} & {0} & {0} & {0} \\ {0} & {0} & {1} & {0} \\ {0} & {1} & {0} & {0} \\ {0} & {1} & {1} & {0} \\ {1} & {0} & {0} & {0} \\ {1} & {0} & {1} & {0} \\ {1} & {1} & {0} & {0} \\ {1} & {1} & {1} & {1} \end{array} $$
$$ \begin{array}{llll} {\beta(a)} & {\beta(b)} & {\beta(c)} & {\hat{\beta}((\neg a \rightarrow b) \wedge(b \wedge c))} & {\text { Monom }} \\ {0} & {0} & {0} & {0} & {-} \\ {0} & {0} & {1} & {0} & {-} \\ {0} & {1} & {0} & {0} & {-} \\ {0} & {1} & {0} & {0} & {-} \\ {1} & {0} & {0} & {0} & {-} \\ {1} & {0} & {1} & {0} & {-} \\ {1} & {1} & {0} & {0} & {} & {-} \\ {1} & {1} & {1} & {1} & {} & {a \wedge b \wedge c} \end{array} $$ Also: ϕ' = (¬a∧b∧c)∨(a∧b∧c). Offenbar ist ϕ' in disjunktiver Normalform. Es bleibt zu zeigen, dass ϕ ≡ ϕ' gilt. Dazu zeigen wir zwei Richtungen: 1. Jedes Modell von ϕ ist ein Modell von ϕ' 2. Jedes Modell von ϕ' ist ein Modell von ϕ. Für die Hinrichtung zeigen wir, dass jedes Modell von ϕ ein Modell von ϕ' ist. Es gelte $$\beta \models \varphi$$
β |= ϕ. Dann gilt β(ϕ) = 1. Also gibt es ein Monom µ innerhalb von ϕ'
für dieses β. Für µ gilt nun β(µ) = 1, da alle Literale in µ von β wahr gemacht werden. Da ϕ' alle seine Monome durch Oder-Junktoren verbindet, folgt β(ϕ')= 1. Für die Rückrichtung zeigen wir, dass jedes Modell von ϕ'
auch ein Modell von ϕ ist. Es gelte β |= ϕ'. Dann muss für
mindestens eines der Monome µ gelten, dass ˆβ(µ) = 1 gilt. Dies bedeutet aber, dass in der
Wahrheitstafel von ϕ die zu β gehörige Zeile eine 1 aufweist. Also ist β ein Modell von ϕ
Im Endeffekt, kann ich dies doch 1 zu 1 benutzen oder nicht?