Ersetzung von Teilformeln

---

Beispiel - Ersetzung logisch äquivalenter Formeln in der Arithmetik

Da die logische Äquivalenz der arithmetischen Gleichheit entspricht, wollen wir zur Veranschaulichung zunächst ein Beispiel aus der Arithmetik anführen:

Betrachten wir den Ausdruck

• (7+3)*9

Der Teilausdruck

• 7+3

kann, ohne den Wert zu verändern, durch

• 10

ersetzt werden. Somit erhalten wir einen zum Ursprungsausdruck gleichwertigen Ausdruck

• 10*9.

---

---

Beispiel - Ersetzung logisch äquivalenter Formeln in der Aussagenlogik

Betrachten wir die Formel

• γ = !(!p&!q)|p

In der Äquivalenz

• R1: !(a&b) ≡ !a|!b

können wir (wie im vorherigen Kapitel gezeigt)

• a durch !p, und
• b durch !q

substituieren, und erhalten die Äquivalenz

• !(!p&!q) ≡ !!p|!!q

Ersetzen wir nun die Teilformel

• !(!p&!q)

von γ durch die äquivalente Formel

• !!p|!!q

so erhalten wir die zu γ äquivalente Formel

• γ₁ = !!p|!!q|p

---

Nun wollen wir eine weiter Äquivalenz einführen:

• R2: !!a ≡ a

Substituieren wir hier

• a durch p,

so erhalten wir

• !!p ≡ p

und somit durch Ersetzung der entsprechenden Teilformel in γ₁ die zu γ äquivalente Formel

• γ₂ = p|!!q|p

Wiederholen wir diesen Vorgang für !!q, so erhalten wir die zu γ äquivalente Formel

• γ₃ = p|q|p

---

Betrachten wir nun die Äquivalenz

• R3: a|b ≡ b|a

und substituieren wir

• a durch q und
• b durch p

so erhalten wir

• q|p ≡ p|q

und somit durch Ersetzung der entsprechenden Teilformel in γ₃ die zu γ äquivalente Formel

• γ₄ = p|p|q

Nachdem auch die folgende Äquivalenz gilt:

• R4: a|a ≡ a

erhalten wir durch Substitution und Ersetzung der entsprechenden Teilformel aus γ₄ die zu γ äquivalente Formel

• γ₅ = p|q

---

Die Äquivalenz kann durch die folgenden Tabellen überprüft werden:

p	q	!p	!q	!p&!q	!(!p&!q)	!(!p&!q)|p
0	0	1	1	1	0	0
0	1	1	0	0	1	1
1	0	0	1	0	1	1
1	1	0	0	0	1	1

p	q	p|q
0	0	0
0	1	1
1	0	1
1	1	1

---