Seite parallel anzeigen





Einige aussagenlogische Äquivalenzen - Vereinfachung von Formeln

(Aussagenlogik Kapitel 6.2.1)

Diese Seite nimmt Bezug auf

(Seite parallel anzeigen)
Liste überspringen
Zum Seitenanfang

Nun wollen wir einige, für die Umwandlung von aussagenlogischen Formeln gebräuchlichsten Äquivalenzen anführen, die in den folgenden Kapiteln zur Anwendung kommen.

Für die Vereinfachung einer Formel α
  • kann man die folgenden Äquivalenzen heranziehen und
  • alle Teilformeln von α,
  • die den Formelschemata auf der linken Seite der Äquivalenzen entsprechen
  • durch entsprechende Formeln ersetzen,
  • die den Schemata auf der rechten Seite entsprechen.

materiale Äquivalenz
γ<->δ≡(γ&δ)|(!γ&!δ)
materiale Implikation
γ->δ≡!γ|δ
De Morgan
!(γ&δ)≡!γ|!δ
!(γ|δ)≡!γ&!δ
Distribution
γ|(δ&λ)≡(γ|δ)&(γ|λ)
γ&(δ|λ)≡(γ&δ)|(γ&λ)
Absorption
γ|(γ&δ)≡γ
γ&(γ|δ)≡γ
Idempotenz
γ°γ≡γ für ° ∈ {&, |}
Doppelte Negation
!!γ≡γ
Negation
γ&!γ≡F
γ|!γ≡T
Negation von T und F
!T≡F
!F≡T
Neutralität
γ|F≡γ
γ&T≡γ
Tautologie
γ|T≡T
Unerfüllbarkeit
γ&F≡F

Beispiel - Vereinfachung einer Formel

Betrachten wir die Formel
  • α = !a|(b|a)->a

Hier können wir die Äquivalenz
  • "materiale Implikation" [ γ->δ≡!γ|δ ]
  • auf α anwenden,
  • indem wir γ=!a|(b|a) und δ=a setzen und so
  • die äquivalente Formel !(!a|(b|a))|a erhalten.
Wie erhalten also
  • α ≡ !(!a|(b|a))|a


Auf diese Formel können wir die Äquivalenz
  • "De Morgan" [ !(γ|δ)≡!γ&!δ ]
  • auf die Teilformel !(!a|(b|a)) anwenden,
  • indem wir γ=!a und δ=(b|a) setzen und
  • die äquivalente Teilformel !!a&!(b|a) erhalten.
Ersetzen wir die Teilformel durch die äquivalente Teilformel, erhalten wir
  • α ≡ !!a&!(b|a)|a


Hier bietet es sich sofort an, die doppelte Negation zu eliminieren. Um dies zu ereichen, können wir die Äquivalenz
  • "Doppelte Negation" [ !!γ≡γ ]
  • auf die Teilformel !!a anwenden,
  • indem wir γ=a setzen und
  • die äquivalente Teilformel a erhalten.
Ersetzen wir die Teilformel durch die äquivalente Teilformel, erhalten wir
  • α ≡ a&!(b|a)|a


Auch diese Formel könnten wir weiter vereinfachen, indem wir etwa die Äquivalenz "De Morgan" auf die Teilformel !(b|a) anwenden.
Will man eine Formel umwandeln, ist es jedoch oft notwendig, sie zunächst umzustrukturieren, um die obigen Äquivalenzen anwenden zu können, wie das nächste Beispiel zeigt. Für die Umstrukturierung von Formeln kann man die folgenden Äquivalenzen heranziehen:

Kommutativität
γ°δ≡δ°γ
für ° ∈ {&, |, <->}
Assoziativität
γ|(δ|λ)≡γ|δ|λ
γ&(δ&λ)≡γ&δ&λ

Beispiel - Umstrukurierung und Vereinfachung einer Formel

Betrachten wir die Formel
  • α = a|(!b|!a)

Nachdem die Disjunktion so definiert ist, dass die Reihenfolge der Disjunkte egal ist, können wir mit etwas Übung sehen, dass wir die Äquivalenz
  • "Negation" [ γ|!γ≡T ] anwenden könnten,
  • indem wir γ=a setzen und so
  • die zu α äquivalente Formel T|!b erhalten.


Diese Äquivalenz ist jedoch nicht sofort anwendbar, da die Struktur der Formel weder der linken, noch der rechten Seite der Äquivalenz entspricht. D.h. Wir müssen die Formel zunächst so umstrukturieren, dass sie a|!a als Teilformel enthält:

Wenden wir also die Äquivalenz
  • "Kommutativität" [ γ°δ≡δ°γ ]
  • auf die Teilformel !b|!a an,
  • indem wir γ=!a und δ=!a setzen,
  • so erhalten wir die äquivalente Teilformel !a|!b.
Ersetzen wir die Teilformel durch die äquivalente Teilformel, erhalten wir
  • α ≡ a|(!a|!b)

Wenden wir die Äquivalenz
  • "Assoziativität" [ γ|(δ|λ)≡γ|δ|λ ]
  • auf die Formel a|(!a|!b) an,
  • indem wir γ=a, δ=!a und λ=!b setzen,
  • erhalten wir die äquivalente Formel a|!a|b.
Wir erhalten also
  • α ≡ a|!a|!b


Auf diese Formel können wir die Äquivalenz
  • "Negation" [ γ|!γ≡T ]
  • auf die Teilformel a|!a anwenden,
  • indem wir γ=a setzen und
  • die äquivalente Teilformel T erhalten.
Ersetzen wir die Teilformel durch die äquivalente Teilformel, erhalten wir
  • α ≡ T|!b