27
Formale Syteme 2020 (Fach) / Logik (Lektion)
Anzeige
- Wie nennt man eine Formel, welche immer erfüllbar ist? Allgemeingültige Formel, bzw. Tautologie.
- Wann ist eine Formel f allgemeingültig? Wenn jede Wertzuweisung w ein Modell ist. Wenn für jede Wertzuweisung gilt w(f) = 1 Wenn für jede Wertzuweisung gilt w(¬f) = 0 -> wahr Wenn keine Wertzuweisung ein Modell zu ¬f ist ⇒ Wenn ¬f unerfüllbar ist. Wenn sie aus der leeren Formelmenge folgt ∅ Ξ f (Modell)
- Wann sind zwei Formel äquivalent? Wenn sie die selben Modelle haben (Also in der Wahrheitstafel das gleiche Muster haben). Sind beide Formel Tautologien oder unerfüllbar, sind sie automatisch äquivalent.
- Wann ist eine Formel in Negationsnormalform? Sofern in der Formel nur ¬,∧,∨ vorkommen und ¬ nur vor Atomen, nicht vor Formel vorkommt.
- Wann ist eine Formel in NNF, KNF und DNF? NNF: wenn alle in F vorkommenden Negationszeichen ¬ unmittelbar vor aussagenlogischen Variablen stehen. KNF (Klauselform): Disjunktion von Konjunktionstermen DNF: Konjunktion von Disjunktionstermen (Klauseln)
- Ist die leere Klausel [ ] wahr oder falsch? Falsch, < > ist wahr.
- Was ist eine Klausel und was eine duale Klausel? Eine Klausel ist eine verallgemeinerte Disjunktion Eine duale Klausel ist eine verallgemeinerte Konjunktion
- Was ist Resolution? Resolution ist ein Verfahren zum Nachweis der Unerf ¨ullbarkeit beliebigerFormeln. Resolution ist Suche nach der leeren Klausel unter Verwendung einergeeigneten Ableitungsregel.
- Wie lauten die vier Erfüllbarkeiten und wann treten sie ,in Bezug auf Interpretationen, ein? F ist erfüllbar, wenn es eine Interpretation gibt, die auf wahr abbildet. F ist allgemeingültig, wenn alle Interpretationen auf wahr abbilden. (Tautologie) F ist widerlegbar, wenn es eine Interpretation gibt, die auf falsch abbildet. F ist unerfüllbar, wenn alle Interpretationen auf falsch abbilden.
- Wann ist eine Formel eine HORN Formel? Eine Formel ist in Hornformel , wenn sie in KNF ist, und höchstens ein positives Literal enthält. (Je Klammer). Sie besteht aus sogenannten Hornklauseln, spezielle Arten von Implikationen.
- Anzeige
- Welche Methoden gibt es, um zu prüfen ob eine Formel erfüllbar ist? Wahrheitstafel DNF Hornformel (polynomiell) Resolution Semantisches Tableau
- Wie lautet die Formel für die Erweiterung? Φ = Φ v (Φ ∧ Y)
- Wie kann man mit semantischen Tableaus beweisen, dass ψ allgemeingültig ist? Indem man ein semantisches Tableau für ¬ψ aufstellt und prüft, ob dies unerfüllbar ist.
- Wenn Γ |= ψ und ψ eine Tautologie ist, ist dann Γ auch allgemeingültig? Nein, da zB. {a} |= (a, ¬a). Zweites ist eine Tautolgie, a aber nicht.
- In welcher Form ist die Hornformel? In KNF, also besteht sie aus Disjunktionen innerhalb von Konjunktionen
- Folgt aus |= φ, dass φ allgemeingültig ist? Ja, |= φ steht für Ø |= φ, d.h. jedes Modell der leeren Menge erfüllt die Formel φ und alle Wertzuweisungen sind Modelle von φ.
- Was ist das Ziel vom Hilbert-Kalkül? Alle Tautologien aus Axiomen mit Hilfe von Ableitungsregeln herzuleiten -> Kürzen der Formel durch Ableiten
- Wie lautet die Formel vom Modus Ponens? Φ ( Φ -> ψ ) geteilt durch ψ
- Wann gilt A |= F? Wenn jedes Modell von A auch Modell von F ist oder jede Formel von A auch in F enthalten ist. (Semantische Konsequenz)Wahrheitstabelle aufstellen und schauen, ob bei jeder Wertzuweisung die selbe 1 steht.
- Was sind Unterformeln UNT? Teilformel einer Formel, Bsp (¬p -> q) v (a ∨ b) ¬p q a b (a ∨ b)
- Was ist eine Wertzuweisung? Eine Wertzuweisung weist jeder Variable einen booleanschen Wert zu. P -> (0,1)
- Was versteht man unter Auswertung von Formeln? Den Wahrheitswert einer Formel durch Auswertung all ihrer Unterformel bestimmen. (Wahrheitstabelle)
- Wann ist eine Wertzuweisung ein Modell? Wenn sie die Formel erfüllt.
- Wann gilt Γ |= Φ ? Wenn jedes Modell von Γ auch ein Modell der Formel Φ ist. Wenn kein Modell von Γ auch ein Modell von ¬Φ ist. Wenn es kein Modell gibt welches Γ ∪ {¬Φ} gibt Wenn Γ ∪ {¬Φ} unerfüllbar ist
- Wann sind zwei Formel mit gleichen Literalen äquivalent? Wenn sie dieselben Modelle haben. Warheitstabelle aufstellen und schauen ob sich die selbe Zahlenreihenfolge aus 0 und 1 ergibt.
- Warum ist die Äquivalenz eine Äquivalenzrelation? Reflexiv (Äquivalent zu sich selbst) Symmetrisch (Wenn Formel 1 äquivalent zu Formel 2 ist, dann auch umgekehrt) Transitiv (Wenn Formel 1 äquivalent zu Formel 2 ist, und Formel 2 zu 3 , dann auch 1 zu 3)
- Wie kann man eine Formel auf Erfüllbarkeit testen? Wahrheitstafel und prüfe ob eine 1 vorkommt Wandle Formel in DNF um und prüfe, ob eine der Teilformeln erfüllbar ist. Im schlimmsten Fall beide exponentiell, deswegen Tableaus und Hornformeln (polynominell).