Seite parallel anzeigen
Negationsnormalform
(Aussagenlogik Kapitel 6.3.1)Diese Seite nimmt Bezug auf
(Seite parallel anzeigen)
- Aussagenlogik: Normalformen
- Aussagenlogik: Ersetzung von Teilformeln
- Aussagenlogik: Einige aussagenlogische Äquivalenzen - Vereinfachung von Formeln
Eine Formel α ist genau dann in Negationsnormalform (NNF), wenn sie eine der folgenden 3 Formen hat:
- α=T,
- α=F oder
- α besteht nur aus Literalen (Atomen und negierten Atomen) und den Junktoren & und |.
Beispiel - Formeln in Negationsnormalform
Die folgenden Formeln sind in Negationsnormalform:
- a&b
- !a|b&c
- !a|(b&(c|!b)|a)
- a&b|!c&a&(c&a|!b)
Die folgenden Formeln sind nicht in Negationsnormalform:
- F|a - enthält die Wahrheitskonstante F
- !a->b&c - enthält die Implikation
- !(a|b)->(c|!b)|a - enthält die Implikation und die Negation steht in der Teilformel !(a|b) nicht direkt vor den Atomen
- a&b|!(c&a)&(c&a|!b) - die Negation steht in der Teilformel !(c&a) nicht direkt vor den Atomen
Man erhält sie, indem man die Formel vereinfacht, indem man
-
(So weit als möglich) alle Wahrheitskonstanten eliminiert,
Hierfür stehen die folgenden Äquivalenzen zur Verfügung:- Negation von T und F [ !T≡F bzw. !F≡T ],
- Neutralität [ γ|F≡γ und γ&T≡γ ].
- Tautologie [ γ|T≡T ].
- Unerfüllbarkeit [ γ&F≡F ].
Beispiel - Elimination der Wahrheitskonstanten
Betrachten wir die Formel- α = a->b<->a|c&F
Um die Wahrheitskonstante F zu eliminieren, können wir zunächst die Äquivalenz- "Unerfüllbarkeit" [ γ&F≡F ] auf die Teilformel c&F anwenden,
- indem wir γ=c setzen und die äquivalente Teilformel F erhalten.
- α ≡ a->b<->a|F
Im nächsten Schritt können wir die Äquivalenz- "Neutralität" [ γ|F≡γ ] auf die Teilformel a|F anwenden,
- indem wir γ=a setzen und die äquivalente Teilformel a erhalten.
- α ≡ a->b<->a
-
alle Junktoren "->" und "<->" durch "&", "|" und "!" ersetzt,
Hierfür können wir folgende 2 Äquivalenzen heranziehen:- materiale Äquivalenz [ γ<->δ≡(γ&δ)|(!γ&!δ) ] und
- materiale Implikation [ γ->δ≡!γ|δ ].
Beispiel - Elimination der materialen Implikation und der materialen Äquivalenz
Betrachten wir die Ergebnisformel aus dem vorherigen Beispiel- α = a->b<->a
Um die materiale Implikation zu eliminieren, können wir die Äquivalenz- "materiale Implikation" [ γ->δ≡!γ|δ ] auf die Teilformel a->b anwenden,
- indem wir γ=a und δ=b setzen und die äquivalente Teilformel !a|b erhalten.
- α ≡ !a|b<->a
Um die materiale Äquivalenz zu eliminieren, können wir die Äquivalenz- "materiale Äquivalenz" [ γ<->δ≡(γ&δ)|(!γ&!δ) ] auf die Teilformel !a|b<->a anwenden,
- indem wir γ=!a|b und δ=a setzen und die äquivalente Teilformel (!a|b)&a|!(!a|b)&!a erhalten.
- α ≡ (!a|b)&a|!(!a|b)&!a
-
und alle Negationen direkt vor die Variablen und Konstanten schiebt und doppelte Negationen eliminiert,
Dies geschieht durch die Anwendung der Äquivalenzen- DeMorgan [ !(γ&δ)≡!γ|!δ und !(γ|δ)≡!γ&!δ ] und
- Doppelte Negation [ !!γ≡γ ].
Beispiel - Negationen direkt vor die Variablen und Konstanten schieben und doppelte Negationen eliminieren
Betrachten wir wieder die Ergebnisformel aus dem vorherigen Beispiel- α = (!a|b)&a|!(!a|b)&!a
Um die Negationen direkt vor die Variablen zu schieben, können wir die Äquivalenz- "De Morgan" [ !(γ|δ) ≡ !γ&!δ ] auf die Teilformel !(!a|b) anwenden,
- indem wir γ=!a und δ=b setzen und die äquivalente Teilformel !!a&!b erhalten.
- α ≡ (!a|b)&a|!!a&!b&!a
Um die doppelte Negation zu eliminieren, können wir die Äquivalenz- "Doppelte Negation [ !!γ ≡ γ ] auf die Teilformel !!a anwenden,
- indem wir γ=a setzen und die äquivalente Teilformel a erhalten.
- α ≡ (!a|b)&a|a&!b&!a
Diese Formel ist in Negationsnormalform.
Um eine möglichst einfache Formel zu ehalten und auch die Zwischenergebnisse möglichst einfach zu halten, kann man selbstverständlich jederzeit (wenn dies möglich ist) während der Umwandlung
-
die folgenden Äquivalenzen zur Vereinfachung der Formel anwenden:
- Idempotenz [ γ°γ≡γ für ° ∈ {&, |} ]
- Absorption [ γ|(γ&δ)≡γ und γ&(γ|δ)≡γ ]
- Negation [ γ&!γ≡F und γ|!γ≡T ]
Für die Anwendung der obigen Äquivalenzen kann es oft notwendig sein,
-
die Formel umzustrukturieren.
Hierfür kommen die folgenden Äquivalenzen zur Anwendung:- Kommutativität [ γ°δ≡δ°γ für ° ∈ {&, |, <->} ]
- Assoziativität [ γ|(δ|λ)≡(γ|δ)|λ und γ&(δ&λ)≡(γ&δ)&λ ]
Beispiel - Weitere Vereinfachung der Formel
Betrachten wir wieder die Ergebnisformel aus dem vorherigen Beispiel
- α = (!a|b)&a|a&!b&!a
Diese Formel ist bereits in Negationsnormalform, kann aber mit den zur Verfügung stehenden Äqivalenzen noch weiter vereinfacht werden:
Anwendung der Äquivalenz "Assoziativität" [ γ&(δ&λ)≡γ&δ&λ ]
auf die Teilformel a&!b&!a [ γ=a, δ=!b, λ=!a ] ergibt a&!b&!a ≡ a&(!b&!a) und somit
- α ≡ (!a|b)&a|a&(!b&!a)
Anwendung der Äquivalenz "Kommutativität" [ γ&δ≡δ&γ ]
auf die Teilformel !b&!a [ γ=!b, δ=!a ] ergibt !b&!a ≡ !a&!b und somit
- α ≡ (!a|b)&a|a&(!a&!b)
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&!a&!b
Anwendung der Äquivalenz "Negation" [ γ&!γ≡F ]
auf die Teilformel a&!a [ γ=a ] ergibt a&!a ≡ F und somitDurch die Anwendung der Negation, enthält diese Formel wieder eine Wahrheitskonstante und ist somit nicht mehr in Negationsnormalform!
- α ≡ (!a|b)&a|F&!b
Anwendung der Äquivalenz "Kommutativität" [ γ&δ≡δ&γ ]
auf die Teilformel F&!b [ γ=F, δ=!b ] ergibt F&!b ≡ !b&F und somit
- α ≡ (!a|b)&a|!b&F
Anwendung der Äquivalenz "Unerfüllbarkeit" [ γ&F≡F ]
auf die Teilformel !b&F [ γ=!b ] ergibt !b&F ≡ F und somit
- α ≡ (!a|b)&a|F
Anwendung der Äquivalenz "Neutralität" [ γ|F≡γ ]
auf die Teilformel (!a|b)&a|F [ γ=(!a|b)&a ] ergibt (!a|b)&a|F ≡ (!a|b)&a und somit
- α ≡ (!a|b)&a
Diese Formel ist in Negationsnormalform und kann mit den zur Verfügung stehenden Äquivalenzen nicht weiter vereinfacht werden:
NNF(α) = (!a|b)&a
- zurück zu Normalformen
- zum Seitenanfang
- weiter zu
