Formale Systeme (Fach) / Logik (Lektion)

ok

Diese Lektion wurde von Sogn erstellt.

Lektion lernen

zurück  |  weiter 1 / 1

• Woraus besteht das Alphabet der Aussagenlogik? Definition 3.3 Ein Alphabet der Aussagenlogik besteht aus. einer (abzahlbar) unendlichen Menge ¨ R = {p1, p2, . . .} von  aussagenlogischen Variablen,. der Menge {¬, ∧, ∨, →, ↔} von Junktoren und. der Menge {(, )} der Sonderzeichen.
• Was ist ein Atom? Eine (aussagenlogische) atomare Formel, auch kurz Atomgenannt, ist eine aussagenlogische Variable.
• Was ist eine aussagenlogische Formel? Die Menge der (aussagenlogischen) Formeln ist die kleinste Menge L(R)von Zeichenreihen ¨uber R, den Junktoren und den Sonderzeichen,die die folgenden Eigenschaften erf ¨ullt: 1. Wenn F eine atomare Formel ist, dann ist F ∈ L(R). 2. Wenn F ∈ L(R), dann ist ¬F ∈ L(R). 3. Wenn ◦/2 ein Junktor ist und F, G ∈ L(R) sind,    dann ist (F ◦ G) ∈ L(R).
• Was ist die Menge der Teilformeln? Die Menge der Teilformeln von F ist die kleinste Formelmenge SF ,die die folgenden Bedingungen erfüllt: 1. F ∈ SF .2. Wenn ¬G ∈ SF ist, dann ist auch G ∈ SF .3. Wenn (G1 ◦ G2) ∈ SF ist, dann sind auch G1, G2 ∈ SF . Die Menge RF der in F vorkommenden Variablen ist SF ∩ R.G heißt Teilformel von F, wenn es in SF enthalten ist.
• Was ist eine Interpretation? Eine (aussagenlogische) Interpretation I = (W, ·) besteht ausder Menge W der Wahrheitswerte und einer Abbildung ·I: L(R) → W, welche die folgenden Bedingungen erfüllt: [F] =¬∗[G] I wenn F von der Form ¬G ist,([G1]I ◦∗ [G2]I) wenn F von der Form (G1 ◦ G2) ist.
• Was ist eine Interpretation? Eine (aussagenlogische) Interpretation I = (W, ·) besteht ausder Menge W der Wahrheitswerte und einer Abbildung ·I: L(R) → W, welche die folgenden Bedingungen erfüllt: [F] =¬∗[G] I wenn F von der Form ¬G ist,([G1]I ◦∗ [G2]I) wenn F von der Form (G1 ◦ G2) ist.
• Was ist eine Interpretation? Eine (aussagenlogische) Interpretation I = (W, ·) besteht ausder Menge W der Wahrheitswerte und einer Abbildung ·I: L(R) → W, welche die folgenden Bedingungen erfüllt: [F] =     ¬∗[G] wenn F von der Form ¬G ist,            ([G1] ◦∗ [G2]) wenn F von der Form (G1 ◦ G2) ist. (Bei jeden [] soll sich ein i gedacht werden)
• Gibt es für jede Abbildung eine Interpretation? (Beweis) Für jede Abbildung g : R → W gibt es genau eine Interpretation I = (W, ·), sodass für alle A ∈ R gilt: g(A) = [A]. Wir konstruieren:     g(F) wenn F ∈ R,    ¬∗[G] wenn F von der Form ¬G ist,    ([G1] ◦∗ [G2]) wenn F von der Form (G1 ◦ G2) ist. . Nach Konstruktion gilt für alle A ∈ R: g(A) = [A] . Nach Satz 3.7 ist I = (W, ·) eindeutig bestimmt und bildet alle F ∈ L(R) auf einen         Wahrheitswert  ab. . Nach Konstruktion erfüllt I die Bedingungen aus Definition 3.9. . Folglich ist I eine Interpretation.
• 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.
• Was ist ein Modell? Eine Interpretation I = (W, ·) heißt Modell für eine aussagenlogische Formel F, symbolisch I |= F, wenn Fi = T.
• Beweis : Eine Formel F ist allgemeingültig (|= F) gdw. ¬F ist unerfüllbar. Eine Formel F ist allgemeingültig (|= F) gdw. ¬F ist unerfüllbar. Beweis |= F  gdw. alle Interpretationen sind Modelle für F        gdw. keine Interpretation ist Modell für ¬F        gdw. ¬F ist unerfüllbar.
• Wie nennt man eine Formel, welche immer erfüllbar ist? Allgemeingültige Formel, bzw. Tautologie.
• Was besagt die logische Konsequenz? Eine aussagenlogische Formel F ist genau dann eine (aussagen-) logische Konsequenz einer Menge von Formeln G, symbolisch G |= F, wenn für jede Interpretation I = (W, ·) gilt: Wenn I Modell für G ist, dann ist I auch Modell für F.
• Alle 11 Äquivalenzen. (F ∧ F) ≡ F(F ∨ F) ≡ F  Idempotenz (F ∧ G) ≡ (G ∧ F)(F ∨ G) ≡ (G ∨ F)  Kommutativitat¨ ((F ∧ G) ∧ H) ≡ (F ∧ (G ∧ H))((F ∨ G) ∨ H) ≡ (F ∨ (G ∨ H))  Assoziativitat¨ ((F ∧ G) ∨ F) ≡ F((F ∨ G) ∧ F) ≡ F  Absorption (F ∧ (G ∨ H)) ≡ ((F ∧ G) ∨ (F ∧ H))(F ∨ (G ∧ H)) ≡ ((F ∨ G) ∧ (F ∨ H))  Distributivitat ¬¬F ≡ F Doppelte Negation ¬(F ∧ G) ≡ (¬F ∨ ¬G)¬(F ∨ G) ≡ (¬F ∧ ¬G) de Morgan (F ∨ G) ≡ F, wenn F allgemeingültig(F ∧ G) ≡ G, wenn F allgemeingültig Tautologie (F ∨ G) ≡ G, wenn F unerfüllbar(F ∧ G) ≡ F, wenn F unerfüllbar Unerfüllbarkeit (F ↔ G) ≡ ((F ∧ G) ∨ (¬G ∧ ¬F)) Äquivalenz (F → G) ≡ (¬F ∨ G) Implikation
• Wann sind zwei Formel semantisch äquivalent? Zwei aussagenlogische Formeln F und G heißen semantisch aquivalent , symbolisch F ≡ G, wenn für alle Interpretationen I gilt: I |= F gdw. I |= G.
• Was sind Positionen? Wie lautet die Rekursion? Sei F eine Formel.Die Menge der Positionen in F, symbolisch PF , ist pos(F). Rekursion siehe S.39
• Wie lautet das Ersetzungstheorem? Sei F, H, G ∈ L(R), π ∈ PF , F[π] = G und G ≡ H. Dann gilt: F ≡ F[π → H].
• Wann ist eine Formel in NNF? Eine Formel F ist in Negationsnormalformwenn alle in F vorkommenden Negationszeichen ¬unmittelbar vor aussagenlogischen Variablen stehen.
• Wann ist eine Formel in Klauselform? Eine Formel der Aussagenlogik ist in konjunktiver Normalform, wenn sie eine Konjunktion von Disjunktionstermen ist. Disjunktionsterme sind dabei Disjunktionen von Literalen. Literale sind nichtnegierte oder negierte Variablen.
• 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.
• Was besagt der Endlichkeitssatz? Eine Menge G von Formeln der Aussagenlogik istgenau dann erfüllbar, wenn jede endliche Teilmenge H ⊆ G erfüllbar ist.
• Wann ist eine Formel in Klauselform erfüllbar? Was bedeuten gleiche Literale für die Klausel? Eine Klauselform ist erfüllbar, wenn jede Klausel erfüllbar ist. Es gibt also ein Modell für jede Klausel.Haben zwei Klauseln die gleichen Literale , und somit die gleichen Modelle sind sie äquivalent und somit ist c1 erfüllbar , wenn c2 erfüllbar ist.
• Was ist das Alphabet? Eine endliche oder abzählbare unendliche Menge von Symbolen/ Zeichen.
• Was ist die Menge der Wörter Σ*? Die Menge aller Wörter aus (über) Σ. Bedingungen: Das leere Wort ist enthalten. Wenn w in Σ* enthalten ist, und a in Σ ist, dann ist auch aw in Σ*.
• Beweis Korrektheit des aussagenlogischen Resolutionsverfahrens? Beweis Korrektheit:  z.Zg. Wenn |- F, dann |= F. Es sei |- F. - Es gibt eine zu ¬F semantisch äquivalente Formel G in Klauselform.  - Wir finden eine Resolutionswiderlegung für G, d.h. eine Resolutionsableitung für G mit leerer Klausel [] als letzte Zeile. - Seien nun D1,...Dm [] alle in der Ableitung berechneten Resolventen. - Es gilgt G ist äquivalent zu <G,D1,...Dm,[]> - Da [] unerfüllbar ist, folgt das G = [], also G ist unerfüllbar. - Wegen G = ¬F gilt somit |= F.
• Beweis Vollständigkeit des Resolutionsverfahren? z.zG Wenn =| F, dann -| F. - Es gelte |= F. - Wir finden eine Formel G in Klauselform mit G = ¬F. - ¬F ist unerfüllbar , somit auch G.
• Wie lautet das Induktionsprinzip für Schleifen? Wenn E vor dem Eintritt in eine Schleife W wahr und eine Schleifenvariante für W ist, dann ist E auch nach Verlassen von W wahr.
• Was ist ein Literal? Ein Literal ist eine aussagenlogische Variable , welche sowohl positiv als auch negativ sein kann.
• Ist die leere Klausel [ ] wahr oder falsch? Falsch, < > ist wahr.
• Wie lautet der aussagenlogische Resolutionsbeweis? Sei F eine aussagenlogische Formel und G eine zu ¬F äquivalente Formel in Klauselform. Ein aussagenlogischer Resolutionsbeweis für F ist eine Resolutionswiderlegung für G.  F heißt Theorem des Resolutionskalküls, wenn es einen Resolutionsbeweis für F gibt. |-- F. 
• Was ist der Rang einer Formel? Eine Funktion rng , welche jede aussagenlogische Formel H aus L(R) auf eine natürliche Zahl abbildet. 0, wenn H ein Literal rng(F) + 1 , wenn H von der Form ¬F rng(F) + rng(G)+1, wenn H und F in Form (F v G) , (F und G) ist rng(¬F) + rng (¬G) + 1, wenn H von ¬(FvG), ¬(F und G) ist
• Benötigte Beweise des Endlichkeitssatzes? (i) Wenn G erfüllbar ist, dann ist jede endliche Teilmenge H ⊆ G erfüllbar. (Dies folgt unmittelbar aus der Definition der Erfüllbarkeit von Mengen.) (ii) Wenn jede endliche Teilmenge H ⊆ G erfüllbar ist, dann ist G erfüllbar.
• Wie testen wir die Erfüllbarkeit einer möglicherweise unendlich großen Menge von Formeln? Idee Es reicht aus, alle endlichen Teilmengen zu betrachten Wir erinnern uns ≡ ist eine Aquivalenzrelation auf ¨ L(R) Sei L(R, n) ⊆ L(R) die Menge der aussagenlogischen Formeln, in denenhochstens die aussagenlogischen Variablen ¨ p1, . . . , pn vorkommen Dann finden wir 2n verschiedene Interpretationen f ¨ur L(R, n) Es gibt 22^n verschiedene durch ≡ auf L(R, n) definierte Aquivalenzklassen
• Wie lauten die Ersetzungsregeln? 1 F[Λ   → H] = H, 2 F[1π → H] = ¬(G[π → H]), wenn F von der Form ¬G ist. 3 F[1π → H] = (G1[π → H] ◦ G2), wenn F vdF (G1 ◦ G2) ist. 4 F[2π → H] = (G1 ◦ G2[π → H]), wenn F vdF (G1 ◦ G2) ist.
• Wie notiert man allgemein Konjunktionen/Disjunktionen? Konjunktionen: <F1, …, Fn> Disjunktion: [F1, …, Fn]
• Regeln zur Umwandlung in DNF? ¬¬DD (D1 ∧ D2)D1 | D2  ¬(D1 ∧ D2)¬D1, ¬D2 (D1 ∨ D2)D1, D2 ¬(D1 ∨ D2)¬D1 | ¬D2
• Wann ist zu G G' eine äquivalente KNF? Wenn G eine Konjunktion von Disjunktionen ist undG' aus G durch die Anwendung einer der im Algorithmus zur Transformationin Klauselform verwendeten Ersetzungsregel erhalten wurde,dann gilt: G' ist eine Konjunktion von Disjunktionen und G ≡ G'

zurück  |  weiter 1 / 1