Seite parallel anzeigen





Du befindest dich hier: Aussagenlogik / Umwandlung von Formeln / Normalformen

Disjunktive Normalform

(Aussagenlogik Kapitel 6.3.2)

Diese Seite nimmt Bezug auf

(Seite parallel anzeigen)
Liste überspringen
Zum Seitenanfang

Eine Formel α ist genau dann in disjunktiver Normalform (DNF), wenn sie eine der folgenden 3 Formen hat:
  • α=T,
  • α=F oder
  • α ist eine Disjunktion von Konjunktionen von Literalen.

Eine Formel in disjunktiver Normalform ist also eine Wahrheitskonstante, oder hat folgende Form:
(λ1,1& ... &λ1,n1)| ... |(λm,1& ... &λm,nm)
für beliebige Zahlen m, n und beliebige Literale λi,ji, 1<=i<=m, 1<=ji<=ni.

Beispiel - Formeln in disjunktiver Normalform

Die folgenden Formeln sind in disjunktiver Normalform:
  • (x&y)|(!z&x)|!y
  • a&b&c&d&!e
  • s|t|!u|v|!w
Zu jeder aussagenlogischen Formel gibt es eine logisch äquivalente Formel in disjunktiver Normalform.

Man erhält sie, indem man das Distributivgesetz
  • γ&(δ|λ)≡(γ&δ)|(γ&λ)
auf die Negationsnormalform der Formel anwendet indem man die Teilformeln die den Formelschemata auf der linken Seite der Äquivalenz entsprechen durch entsprechende Formeln ersetzen, die den Schemata auf der rechten Seite entsprechen.

Beispiel - Umwandlung einer Formel in ihre disjunktive Normalform

Betrachten wir die Formel
  • γ = a->b|a&(c|b)

Anwendung der Äquivalenz "materiale Implikation" [ γ->δ≡!γ|δ ]
auf die Teilformel a->b|a&(c|b) [ γ=a, δ=b|a&(c|b) ] ergibt a->b|a&(c|b)≡!a|(b|a&(c|b)) und somit
  • α ≡ !a|(b|a&(c|b))

Diese Formel ist in Negationsnormalform, aber noch nicht in distributiver Normalform, da die Konjunktion a&(c|b) eine Disjunktion enthält.

Um dies aufzulösen, wenden wir die Distributivität auf diese Formel an:
Anwendung der Äquivalenz "Distributivität" [ γ&(δ|λ)≡γ&δ|γ&λ ]
auf die Teilformel a&(c|b) [ γ=a, δ=c, λ=b ] ergibt a&(c|b)≡a&c|a&b und somit
  • α ≡ !a|(b|(a&c|a&b))

Diese Formel ist bereits in disjunktiver Normalform, kann aber noch weiter vereinfacht werden:

Anwendung der Äquivalenz "Kommutativität" [ γ|δ≡δ|γ ]
auf die Teilformel a&c|a&b [ γ=a&c, δ=a&b ] ergibt a&c|a&b≡a&b|a&c und somit
  • α ≡ !a|(b|(a&b|a&c))
Anwendung der Äquivalenz "Assoziativität" [ γ|(δ|λ)≡γ|δ|λ ]
auf die Teilformel b|(a&b|a&c) [ γ=b, δ=a&b, λ=a&c ] ergibt b|(a&b|a&c)≡b|a&b|a&c und somit
  • α ≡ !a|(b|a&b|a&c)
Anwendung der Äquivalenz "Kommutativität" [ γ&δ≡δ&γ ]
auf die Teilformel a&b [ γ=a, δ=b ] ergibt a&b≡b&a und somit
  • α ≡ !a|(b|b&a|a&c)
Anwendung der Äquivalenz "Absorption" [ γ|γ&δ≡γ ]
auf die Teilformel b|b&a [ γ=b, δ=a ] ergibt b|b&a≡b und somit
  • α ≡ !a|(b|a&c)

Diese Formel ist in disjunktiver Normalform und kann mit den zur Verfügung stehenden Äquivalenzen nicht weiter vereinfacht werden:
DNF(α) = !a|(b|a&c)