Aussagenlogik Flashcards
(25 cards)
Kompaktheitssatz (AL)
Für Formelmenge PHI teilmenge AL:
i)
PHI erfuellbar gdw. jede endliche Teilmenge von PHI erfuellbar
ii)
aus PHI folgt phi gdw. bereits endliches PHI_0 Teilmenge PHI existiert, sodass aus PHI_0 folgt phi
Koinzidenzlemma
sei psi element AL, I und I’ zwei zu psi passende Interpr., sodass I(X)=I’(X) für alle X element tau(psi). Dann ist [psi]^I = [psi]^I’
Definition logisch äquivalent
Zwei Formeln psi, phi heissen logisch äquitvalent, wenn für jede zu beiden passende Interpretation gilt: [psi]^I = [phi]^I
Definition funktional vollständig
Eine Menge von Boolschen Funktioen ist funkt. vollständig, wenn sich daraus jede Boolsche Funktion f wie folgt definieren lässt: zu jeder Funktion f element B^n gibt es eine Formel psi(X1, .. , Xn) mit h_psi = f
Definition erfüllbarkeitsäquivalent
zwei Formeln heissen erfüllbarkeitsäquivlanet, wenn beide erfüllbar oder beide unerfüllbar sind.
Definition Horn-Formel
Eine Horn-Formel ist eine Formel in KNF, wobei jede Klausel (also jede Disjunktion) höchstens ein positives Literal enthält
Was liefert der Markierungslagorithmus für Hornformeln?
Entweder ist die Hornformel unerfüllbar, oder er liefert das kleinste Modell (indem alle Variablen, die nicht mit 1 belegt werden müssen, mit 0 belegt werden)
Satz 1.13 zu Hornformeln (Anzahl kleinste Modelle)
Hornformeln sind entweder unerfüllbar oder haben ein kleinstes Modell
Definition kleinstes Modell
Wenn eine Formel ein kleinstes Modell besitzt, wird in keinem Modell eine Variable mit 0 belegt, die im kleinsten Modell mit 1 belegt ist
Definition Tiefe einer Formel in AL
d(psi) := 0 für atomare psi
d(nicht psi) := d(psi) + 1
d(psi * phi) := max(d(phi), d(psi)) +1, wobei * beliebiger Junktor
Definition (atomare) Formel ( AL)
In der AL sind Boolsche Konstanten (0,1), Aussagenvariablen und durch Junktoren verknüpfte Aussagenvariablen Formeln.
Boolsche Konstanten und Aussagenvariablen nennen wir atomare Formeln.
Lemma 1.6: Wann ist eine Formel psi erfüllbar? (AL)
psi ist erfüllbar gdw. nicht psi keine Tautologie ist
Lemma von Zorn
Sei (A,
Lemma von König
Sei T ein endlich verzweigter Baum mit Wurzel w, in dem es beliebig lange endliche Wege gibt. Dann gibt es auch einen unendlichen Weg in T (der bei der Wurzel w beginnt)
Definition Baum
Ein Baum mit Wurzel w ist ein zusammenhängender, zykelfreier, gerichteter Graph T= (V, E) mit einem ausgezeichneten Knoten w element V, so dass keine Kante in w endet und in jedem anderen Knoten genau eine Kante endet. Ein solcher Baum heisst endlich verzweigt, wenn von jedem v element V nur endlich viele Kanten ausgehen.
Definition Korrektheit und Vollständigkeit (Kalkül)
Ein Beweiskalkül ist korrekt, wenn keine falschen Aussagen darin ableitbar sind.
Es ist vollständig, wenn alle wahren Aussagen ableitbar sind.
Resolutionssatz
Eine Klauselmenge K ist genau dann unerfüllbar, wenn die leere Klausel element Res*(K) ist.
Worst case laufzeit Erfüllbarkeitstest mit Resolution
2^(2n) Schritte, d.h. Res*(K) = Res^(2^(2n))(K), denn es gibt nur 2^(2n) verschiedene Klauseln mit Literalen X_0, … , X_n-1, nicht X_0, … , nicht X_n-1
Worst case Laufzeit Einheitsresolution für Horn-Formeln
?
Definition Einheitsresolvente (bei Einheitsresolution für Horn-Formeln)
Seien C1, C2, C Klauseln.
C ist Einheitsresolvente von C1 und C2, wenn C Resolvente von C1 und C2 ist, und entweder |C1| = 1 oder |C2|= 1 ist.
Korrektheit und Vollständigkeit Einheitsresolution
Einheitsresolution ist nur für Horn-Formeln vollständig
Definition gültige Sequenz (AL)
Eine Sequenz Gamma => Delta ist gültig, wenn jedes Modell von Gamma auch ein Modell mindestens einer Formel aus Delta ist. Die Sequenz ist nicht gültig, wenn eine Interpretation existiert, die alle Formel aus Gamma wahr, und alle Formeln aus Delta falsch macht. Dann falsifiziert I die Sequenz.
Definition Beweis im Sequenzkalkül (AL)
Ein Beweis in SK ist ein Baum, dessen Knoten auf folgende Weise mit Sequenzen beschriftet sind:
- Jedes Blatt ist mit einem Axiom beschriftet
- Jeder innere Knoten des Baumes ist mit der unteren Zeile einer Schlussregel von SK beschriftet; die Kinder dieses Knotens müssen dann gerade mit den in der oberen Zeile dieser Regel auftretenden Sequenz beschriftet sein. Also hat jeder innere Knoten ein oder zwei Kinder.
Lemma 1.28 Zusammenhang Prämisse, Konklusion (SK in AL)
Für jede Regel des SK und jede AL Interpretation I gilt:
I falsifiziert die Konklusion der Regel genau dann, wenn I eine Prämisse der Regel falsifiziert. Es folgt: Die Konklusion ist gültig gdw. die Prämissen gültig sind.
(VORSICHT: das hier bezieht sich wohl nur auf die Angegebenen Schlussregeln, und nicht auf jede Regel.
Wenn wir beweisen wollen, dass eine beliebige Regel gültig ist, reicht es immer zu zeigen, dass aus der gültigkeit der Prämisse die Gültigkeit der Konklusion folgt. Also nur eine Richtung, “kein genau dann wenn”)
