Aussagenlogik Schichten-Normalform Beweis, dass diese für alle gilt

Question

Aufgabe:

Wir definieren die »Schichten-Normalform« für aussagenlogische Formeln wie folgt:
1. Literale sind in Schichten-Normalform.
2. Sind ϕ und ψ in Schichten-Normalform, so nennen wir (ϕ ∨ψ) eine U-Formel.
3. Sind ϕ und ψ beides U-Formeln, so ist (ϕ ∧ψ) in Schichten-Normalform.
Die obige Definition ist eine komplizierte (aber genaue) Art, Folgendes auszudrücken: Malt man eine Formel in SchichtenNormalform als Baum auf, dessen Knoten die Junktoren sind, so ist die Wurzel ein ∧-Knoten mit zwei Kindern, die beide
∨-Knoten sind, deren (jeweils zwei) Kinder wieder ∧-Knoten und so weiter bis zu den Blättern, die dann Literale sind.
Jede »Schicht« des Baumes besteht also nur aus ∧-Knoten und Blättern oder nur aus ∨-Knoten.
Geben Sie einen natürlichsprachlichen Beweis dafür an, dass jede aussagenlogische Formel zu einer Formel in SchichtenNormalform äquivalent ist, ähnlich wie der Beweis zur DNF

Problem/Ansatz:

Komme auf keinen Ansatz, bräuchte da Hilfe

Comments

Bitte in Zukunft Fragen nur einmal absenden. Habe das Duplikat entfernt.

---

ähnlich wie der Beweis zur DNF

Bitte diesen Beweis angeben oder verlinken.  Hast du den in deinen Unterlagen oder bei deinen alten Fragen?

---

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?