Aussagenlogik Flashcards
Eine Aussage ist…
(1) ein Satz in der natürlichen Sprache
2) ist entweder wahr (W) oder falsch (F
Einfache / atomare Aussage
(1) ist eine Aussage
(2) enthält nur einen Sachverhalt = unteilbare Aussage –> enthält keine aussagenlogischen Verknüpfungen
Logische Operatoren / Verknüpfungen
(1) Negation
(2) Konjunktion
(3) Disjunktion
(4) Folgerung / Implikation
Die Semantik der Aussagenlogik wird…
über Wahrheitswerte “wahr” und “falsch” definiert –> Aussagenlogik ist damit eine zweiwertige Logik
Belegung
Belegung ist eine Funktion α : Var -> {1, 0} die jeder atomaren Formel entweder den Wert 1 oder 0 zuweist
Funktionale Vollständigkeit
Eine Teilmenge der Boolschen Funktionen ist funktional vollständig, wenn damit alle Boolschen Funktionen ausgedrückt werden können
Die Menge {not, and, or} ist…
Funktional vollständig
Die Menge {not, and} ist…
Funktional vollständig
Eine Belegung α für Var ist ein Modell einer Formel F über Var, wenn…
α(F) = 1
Die Semantik einer Formel ergibt sich aus?
Der Menge ihrer Modelle
Eine Formel F ist erfüllbar, wenn…
F mind. ein Modell hat (sonst unerfüllbar)
Eine Menge von F Formeln ist konsistent (widerspruchsfrei), wenn…
es ein Modell für F gibt
Eine Menge von F Formeln ist inkonsistent (widersprüchlich), wenn…
es kein Modell gibt
Eine Formel F ist allgemein gültig / eine Tautologie, wenn…
Jede Belegung auch ein Modell ist
Eine Formel F ist semantisch äquivalent zu G, wenn…
a(F) = a(G) für alle Belegungen a
G folgt aus F, wenn…
jedes Modell F auch Modell von G ist
Eine Formel F ist genau dann eine Tautologie, wenn…
notF unerfüllbar ist
Zwei Formel F und G sind semantisch äquivalent genau dann, wenn…
F aus G folgt und G aus F folgt
Kompaktheitssatz
Eine (unendliche) Menge von aussagenlogischen Formeln ist genau dann erfüllbar, wenn jede endliche Teilmenge erfüllbar ist
Äquivalenzen
Idempotenz Kommutativität Assoziativität Absorption Distributivität Doppelnegation de Morgansche Regeln
Normalform
Eine Normalform ist eine Einschränkung auf der Syntax sodass jede beliebige Formel in eine semantisch Äquivalente Formel in Normalform
umgewandelt werden kann –> vereinfacht maschinelle Verarbeitung von logischen Formeln
KNF
Eine Formel ist in konjunktiver Normalform (KNF), wenn sie eine Konjunktion von Disjunktionen von Literalen ist
DNF
Eine Formel ist in disjunktiver Normalform (DNF), wenn sie eine Disjunktion von Konjunktionen von Literalen ist
