Seite parallel anzeigen





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

Konjunktive Normalform

(Aussagenlogik Kapitel 6.3.3)

Diese Seite nimmt Bezug auf

(Seite parallel anzeigen)
Liste überspringen
Zum Seitenanfang

Eine Formel α ist genau dann in konjunktiver Normalform (KNF, engl. CNF), wenn sie eine der folgenden 3 Formen hat:
  • α=T,
  • α=F oder
  • α ist eine Konjunktion von Disjunktionen von Literalen.

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

Beispiel - Formeln in konjunktiver Normalform

Die folgenden Formeln sind in konjunktiver 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 konjunktiver Normalform.

Man erhält sie, indem man das Distributivgesetz
  • γ|(δ&λ)≡(γ|δ)&(γ|λ)
auf die Negationsnormalform der Formel anwendet.

Beispiel - Umwandlung einer Formel in ihre konjunktive Normalform

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

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

Diese Formel ist in Negationsnormalform, aber noch nicht in konjunktiver Normalform, da die Formel eine Disjunktion ist (der Hauptjunktor der Formel ist die Disjunktion) und das Disjunkt b&(a|d&b) eine Konjunktion ist.

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

Diese Formel ist noch nicht in konjunktiver Normalform, da die Disjunktion a|d&b eine Konjunktion enthält.

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

Diese Formel ist noch nicht in konjunktiver Normalform, da die Disjunktion a|(a|d)&(a|b) eine Konjunktion enthält.

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

Diese Formel ist nun in konjunktiver Normalform, kann aber noch weiter vereinfacht werden:

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

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