close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

27.10.2010

EinbettenHerunterladen
Was bisher geschah: klassische Aussagenlogik
Syntax : aussagenlogische Formel (Baumdarstellung)
Induktive Definition:
Atome (elementare Formeln): Aussagevariablen
Konstruktion zusammengesetzter Formeln mit
Junktoren
Semantik : Boolesche Funktion, Menge von Modellen
Belegung von Aussagevariablen W : P → {0, 1}
Wahrheitswerttabelle einer aussagenlogischen
Formel
(Werte unter allen möglichen Belegungen)
Modellmenge einer aussagenlogischen Formel
(erfüllende Belegungen)
erfüllbare, allgemeingültige, unerfüllbare Formeln
Zusammenhang Syntax – Semantik : Verknüpfung von
Teilformeln durch Junktoren (Syntax)
Modellmengen der Teilformeln durch
entsprechende Mengenoperationen (Semantik)
Semantische Äquivalenz und syntaktisches Umformen
42
Wiederholung: Wichtige Äquivalenzen
Für alle aussagenlogischen Formeln ϕ, ψ, η gilt:
ϕ ∨ ϕ ≡ ϕ,
ϕ ∧ ϕ ≡ ϕ,
ϕ ∨ f ≡ ϕ,
ϕ∧t≡ϕ
ϕ ∨ ψ ≡ ψ ∨ ϕ, ϕ ∧ ψ ≡ ψ ∧ ϕ
(Kommutativität von ∧ und ∨)
ϕ ∨ (ψ ∨ η) ≡ (ϕ ∨ ψ) ∨ η
ϕ ∧ (ψ ∧ η) ≡ (ϕ ∧ ψ) ∧ η
(Assoziativität von ∧ und ∨)
ϕ ∧ (ψ ∨ η) ≡ (ϕ ∧ ψ) ∨ (ϕ ∧ η)
ϕ ∨ (ψ ∧ η) ≡ (ϕ ∨ ψ) ∧ (ϕ ∨ η)
(Distributivgesetze)
¬¬ϕ ≡ ϕ (Doppelnegation)
¬(ϕ ∨ ψ) ≡ ¬ϕ ∧ ¬ψ, ¬(ϕ ∧ ψ) ≡ ¬ϕ ∨ ¬ψ
(DeMorgansche Regeln)
ϕ ∨ ψ ≡ ¬(¬ϕ ∧ ¬ψ), ϕ ∧ ψ ≡ ¬(¬ϕ ∨ ¬ψ)
(Dualität von ∧ und ∨)
ϕ → ψ ≡ ¬ψ → ¬ϕ (Kontraposition)
(ϕ ∧ ψ) ∨ (¬ϕ ∧ ψ) ≡ ψ (Fallunterscheidung)
43
Junktorbasen (vollständige Operatorensysteme)
Eine Menge J von Junktoren heißt genau dann Junktorbasis,
wenn zu jeder aussagenlogische Formel ϕ eine äquivalente
aussagenlogische Formel ψ (d.h. ϕ ≡ ψ) existiert, wobei ψ nur
Junktoren aus der Menge J enthält.
Beispiele: Die Mengen
{¬, ∨, ∧}
{¬, ∨}
{¬, ∧}
{¬, →}
{f, →}
sind Junktorbasen.
Die Mengen {∨, ∧} und {∨, ∧, →} sind keine Junktorbasen.
44
Normalformen
spezielle Formeln:
Literal Atom oder negiertes Atom
NNF Formeln, in denen das Negationssymbol ¬
höchstens auf Atome angewendet wird, heißen in
Negations-Normalform.
Beispiel: ¬p ∨ ((¬q ∨ p) ∧ q), ¬p, p
mi
CNF Formeln der Form ni=1
j=1 li,j
mit Literalen li,j
heißen in konjunktiver Normalform.
Beispiel: (¬p ∨ ¬q) ∧ (p ∨ q) ∧ ¬q, p ∨ q, p ∧ ¬q, ¬p
mi
DNF Formeln der Form ni=1
j=1 li,j
mit Literalen li,j
heißen in disjunktiver Normalform.
Beispiel: ¬p ∨ (¬q ∧ p) ∨ (p ∧ q), p ∨ q, p ∧ ¬q, ¬p
45
Satz über Normalformen
Satz
Zu jeder Formel ϕ ∈ AL(P) existieren
eine äquivalente Formel ϕ1 ∈ AL(P) in NNF,
eine äquivalente Formel ϕ2 ∈ AL(P) in CNF und
eine äquivalente Formel ϕ3 ∈ AL(P) in DNF.
Transformation beliebiger Formeln in Normalformen:
1. Formeln mit Junktoren →, ↔, t, f schrittweise durch
Formeln mit ausschließlich ∨, ∧, ¬ ersetzen
2. Konstruktion einer NNF durch (mehrmalige) Anwendung
der deMorganschen Regeln
3. Konstruktion einer CNF und DNF durch (mehrmalige)
Anwendung der Distributivgesetze auf die NNF
Beispiel: p ↔ q , (a → b) → c
46
Kanonische Normalformen
CNF ni=1 ϕi heißt kanonisch gdw. in jeder Disjunktion ϕi jede
Aussagenvariable vorkommt.
DNF ni=1 ϕi heißt kanonisch gdw. in jeder Konjuntion ϕi jede
Aussagenvariable vorkommt.
Minterme : Konjunktionen in einer kanonischen DNF
Maxterme : Disjunktionen in einer kanonischen CNF
Satz
Zu jeder Formel ϕ ∈ AL(P) existieren (bis auf Umordnung)
eindeutige Formeln ϕ1 , ϕ2 ∈ AL(P) mit ϕ ≡ ϕ1 ≡ ϕ2 , wobei
ϕ1 in kanonischer CNF und
ϕ2 in kanonischer DNF.
Die kanonischen CNF und DNF einer Formel ϕ lassen sich aus
der Wahrheitswerttabelle der Formel ϕ ablesen.
47
Document
Kategorie
Gesundheitswesen
Seitenansichten
7
Dateigröße
100 KB
Tags
1/--Seiten
melden