+2 Daumen
751 Aufrufe

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

Avatar von

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?

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community