Ist doch Logisch

시작하기. 무료입니다
또는 회원 가입 e메일 주소
Ist doch Logisch 저자: Mind Map: Ist doch Logisch

1. Algorithmen

1.1. Aussagenlogik

1.1.1. Auswertungsproblem Linearzeit / Polyzeit

1.1.2. Erfüllbarkeitsproblem NP-vollständig

1.1.3. Gültigkeitsproblem co-NP-vollständig

1.1.4. Gültigkeitsproblem für KNF/DNF Linearzeit

1.1.5. Folgerbarkeitsproblem co-NP-vollständig

1.1.6. Hornformeln

1.1.6.1. Erfüllbarkeitsproblem Linearzeit

1.1.7. Resolutionskalkül Erfüllbarkeit: NP (2^n)

1.2. Prädikatenlogik

1.2.1. Auswertungsproblem PSpace-vollständig

1.2.2. Entscheidungsproblem Nicht entscheidbar

1.2.3. Erfüllbarkeitsproblem

1.2.4. Gültigkeitsproblem

2. Prädikatenlogik

2.1. Allgemein

2.1.1. Erweitert die AL um Quantoren

2.1.2. Aussagen über unendliche Mengen treffen

2.1.3. Mächtiger aber mehr Komplexität

2.2. Syntax

2.2.1. Variable

2.2.2. Funktion

2.2.2.1. stelligkeit = anzahl der parameter

2.2.2.2. Hat rückgabewert (wert oder variable)

2.2.3. Prädikat/Relation

2.2.3.1. Aussgage / Kein Rückgabewert

2.2.3.2. z.B. even, >, "x ist beliebt bei y"

2.2.4. Term

2.2.4.1. induktiv

2.2.4.1.1. Sei S eine Signatur. Die Menge T(S) der S-Terme ist dann: VAR [Teilmenge von] T(S) sind t_1,...,t_n € T(S) und f € F^n(S), dann ist auch f(t_1,...,t_n) € T(S)

2.2.5. Prädikatenlogische Formel

2.2.5.1. induktiv

2.2.5.1.1. Einzelne VARs sind eine Formel. Verundete und vernichtete, ... sind dann auch Formeln

2.2.6. Teilformel

2.2.6.1. Wie Aussagenlogitk

2.2.7. freie/gebundene Variabel

2.2.7.1. kommt x in einer Teilformel forall x: G oder exists x: G vor, so heißt x gebunden, sonst frei

2.3. Semantik

2.3.1. Zuweisung/Interpretation

2.3.1.1. Ein Paar (A, ß) mit Zuweisung ß in A heisst Interpretation

2.3.1.2. Wie vorher bei AL die Belegung

2.3.2. Struktur

2.3.2.1. Besteht aus nichtleerem Universum A und Interpretsfkt

2.3.3. Signatur

2.3.3.1. Die Namen

2.3.3.2. Aus diesen Namen kannste Fkt und Relationen basteln

2.3.4. Erfülltheitsrelationen

2.3.4.1. das Zeichen |=

2.4. Koinzidenzlemma

2.4.1. Analog zur AL

2.4.2. Erlaubt uns nur die freien Variablen zu betrachten

2.5. Isomorphielemma

2.5.1. Isomporphie=Gleichheit

2.5.2. Zwei Strukturen sind gleich, außer dass man Elemente des Universums umbenennen muss

2.6. Auswertungsproblem

2.6.1. exponentiell viel Zeit: NP

2.6.2. PSpace-vollständig

2.6.3. Algorithmus rekursiv die einzelnen Teilformeln

2.7. Äquivalenzen

2.7.1. Analog zu Al

2.7.2. Zusätzlich

2.7.2.1. Dualität von forall, exists

2.7.2.2. Distrubutiv für forall, exsits

2.8. Domänenunabhängigkeit

2.8.1. Gültig in allen Domänen

2.9. FO und Datenbanken

2.9.1. Datenbankinstanz = relationale Struktur

2.9.2. Übersetzung FO->SQL benötigt nur linear zeit

2.9.3. FO in der Ausdrücksstärke = SQL-Kern

2.10. Ersetzungslemma

2.10.1. wie AL

2.11. Reduzierte FO-Formel

2.11.1. Formel hat nur Junktoren neg, UND und den Quantor exists

2.12. Erfüllbar/Gültig/Konsequenz

2.12.1. wie AL

2.13. Normalformen

2.13.1. Negations-Normalform

2.13.1.1. Wenn in einer Formel Negationenn ur auf Atome angewendet werden

2.13.1.2. Jede Formel kann in linearzeit in NNF gewandelt werden

2.13.2. Pränex-Normalform

2.13.2.1. bereinigt

2.13.2.1.1. Keine Variable tritt sowohl frei als auch gebunden auf

2.13.2.1.2. Keine Variable wird mehr als einmal quantifiziert

2.13.2.1.3. Jede Formel kann in linearzeit bereinigt werden

2.13.2.2. Formel ist in Pränex-Normalform, wenn

2.13.2.2.1. Formel-Bereinigt

2.13.2.2.2. Alle Quantoren vorne stehen

2.14. Unentscheidbarkeit Prädikatenlogik

2.14.1. endliche Gültigkeit, Erfülbarkeit, Konsequenz sind unentscheidbar in FO

2.15. Positives zu berichten

2.15.1. Gültige Formeln sind rekursiv aufzählbar

2.15.2. Syntaktische-Einschränkungen liefern Entscheidbarkeit

2.16. FO-Theorien

2.16.1. Goldbachsche Vermutung

2.16.2. Presburger Arithmetik

2.16.3. Skolem Arithmetik

2.16.4. Artihmetik der reellen Zahlen

2.16.5. arithmetik der natürlichen Zahlen

2.16.6. Axiomatisierung

2.17. Sequenzenkalkül

2.17.1. Allgemein

2.17.1.1. Kalkül für Gültigkeit

2.17.1.2. Zum Ableiten aller Tautologien / unerfüllbaren Formeln

2.17.2. Def./Syntax Sequenz

2.17.2.1. Ausdruck der Form Γ -> Δ

2.17.2.2. Γ = Antezendenz

2.17.2.3. Δ = Sukzedenz

2.17.3. FO Satz

2.17.3.1. Tautologie wenn ∅ -> {phi}

2.17.3.2. Unerfüllbar wenn {phi} -> ∅

2.17.4. Schlussregeln. 2 Stk pro Junktor

2.17.5. SK-Beweis

2.17.5.1. Baum

2.17.5.2. Jede ableitbare Sequenz ist gültig

2.17.6. Wichtigste Anwendung: Beweis der Kompaktheit von Fo

2.18. Rekursive Aufzählbarkeit

2.18.1. endliche Strukturen

2.18.1.1. Die Menge der erfüllbaren Formeln ist rekursiv aufzählbar für jede aufzählbare Signatur Tau

2.18.2. unendliche Strukturen

2.18.2.1. Für jede aufzählbare Signatur Tau sind rekursiv aufzählbar:

2.18.2.1.1. Die Menge aller Tautologie aus FO(Tau)

2.18.2.1.2. Die Menge aller unerfüllbaren Formeln aus FO(tau)

2.18.2.2. Wenn Tau mind. ein binäres Relationssymbol enthält ist die Menge der erfüllbaren FO-Formeln nicht aufzählbar

2.18.3. Rekursive Aufzählung liefert Semi-Entscheidbarkeit für Gültigkeit

2.19. Löwenheim/Skolem

2.19.1. Alles was n endliches Modell hat, hat auch n unendliches

2.19.2. Überabzählbarkeit/Abzählbarkeit ist nicht FO-Ausdrückbar

2.20. Ausdrückbarkeit

2.20.1. Eigenschaft die nicht unter isomophie abgeschlossen ist NICHT FO-ausdrückbar

2.20.2. Zusammenhang von ungerichteten Graphen ist nicht ausdrückbar

2.20.3. Ehrenfeucht-Fraisse-Spiele

2.20.3.1. Erlauben nicht-ausdrückbarkeit von Eigenschaften als FO-Formel

2.20.3.2. Zwei Spieler: Spoiler (beginnt), Duplikator

2.20.3.3. Spielfeld 2 Tau-Strukturen

2.20.3.4. jeder Spieler zieht abwechselnd

2.20.3.5. Wenn Spoiler aus A zieht, muss Duplikator aus B, und umgekehrt

2.20.3.6. k Schritte, vorher festgelegt

2.20.3.7. Wenn die Menge nach k Schritten ein partieller Isomorphismus ist, gewinnt Duplikator

2.20.3.8. Gewinnstrategie: Wenn einer gewinnen kann, ohne das der andere was dagegen machen kann

2.20.3.9. Zusammenhang EF und FO

2.20.3.9.1. Abwechselnde Züge entsprechen Quantorenalterniereungen

2.20.3.9.2. Duplikator hat Gewinnstrategien wenn Strutur A und Struktur B jeweils Formel phi erfüllen (A |= phi und B |= phi)

2.20.3.9.3. Wenn wir zeigen wollen, dass eine Sache/Eigenschaften nicht in FO ausdrückbar ist, müssen wir zeigen, dass der Duplikator für jedes k>=0 eine Gewinnstrategie hat.

3. Logik zweiter Stufe

3.1. Man kann auch über Mengen von Elementen und Relationen quantifizieren

3.2. Transitive Hülle oder even sind ausdrückbar

3.3. erfüllt nicht Kompaktheitseigenschaft

3.4. Abzählbarkeit und überabzählbarkeit ausdrückbar

3.5. MSO

3.5.1. nur unäre Relationssymbnole

3.5.2. Zusammenhang von Graphen ausdrückbar

3.5.3. für praktischen Einsatz zu langsam

3.6. Auswertung von SO/MSO

3.6.1. polynomiell viel Platz für MSO

3.6.2. exponentiell viel Platz für SO

3.6.3. MSO: Pspace-vollständig

3.6.4. SO. Exspace-vollständig

3.7. MSO über linearen Strukturen

3.7.1. MSO entscheidbar über eingeschränkte Strukturklassen

3.7.1.1. endliche und unendliche Strukturklassen

3.7.1.2. endliche und unendliche Baumstrukturen

3.7.1.2.1. Worte im Sinne der formalen Sprache

3.8. S1S-Struktur

3.8.1. Wörter über €_n

3.9. Temporallogik

3.9.1. LTL,CTL,µ-Kalkül

3.9.2. LTL

3.9.2.1. Neue Quantorenzeichen: O, ◊ ,□,Until

3.10. Die in SO definierbaren Entscheidungsprobleme sind exakt die NP-Probleme

4. Aussgenlogik

4.1. Allgemein

4.1.1. Sehr beschränkte Logik

4.1.2. Vieles nicht aussagbar

4.1.3. Logische Verknüpfung mittels Junktoren nicht, und, oder

4.2. Atomare Formeln

4.2.1. Wahrheitswerte oder Variablen

4.3. Syntax

4.3.1. Beschreibt wie Formeln zusammengesetzt werden können

4.3.2. Induktiv definiert

4.4. Semantik

4.4.1. Bedeutung

4.4.2. Wahrheitstabelle: Wie die einzelnen Zeilen erstellt werden

4.4.3. Es gibt eine Belegung (Funktion)

4.4.3.1. Regeln legen fest wie die Fuktion rechnet

4.4.4. Wenn 1 rauskommt, erfüllt die Belegung die Formel: V |= phi.

4.4.4.1. V ist ein Modell von phi

4.5. Junktoren

4.6. Koinzidenzlemma

4.6.1. var(phi) die variablen die in Formel phi vorkommen

4.6.2. Sei phi Formel und V1, V2 Belegungen mit V1(x) = V2(x) für alle x, dann sind die beiden gleich V1(phi) = V2(phi)

4.7. Auswertungsproblem

4.7.1. Gegeben: AL phi und Belegung V. Frage: Gilt V(phi) = 1?

4.7.2. In linearzeit Lösbar

4.7.3. Vorgehen: Rekursiv alle Teilformen auswerten

4.8. Kompaktheitssatz

4.8.1. Eine Menge von AL ist genau dann erfüllbar, wenn jede endliche Teilmenge erfüllbar ist.

4.9. Äquivalenz

4.9.1. Idempotenz

4.9.2. Kommutativität

4.9.3. Assoziativität

4.9.4. Absorption

4.9.5. Distributivgestöätz

4.9.6. Doppelnegation

4.9.7. De Morgansche Regel

4.9.8. Tautologieregeln

4.9.9. Unerfüllbarkeitsregeln

4.10. Ersetzungsllemma

4.10.1. F1,F2 zwei Äquivalente Formeln, G eine in der F1 als Teilformel vorkommt. Sei G' die Formel die man erhält wenn man G in F1 durch F2 ersetzt. Dann: G=G'

4.10.2. Äquivalente Formeln sind austauchbar

4.11. Boolsche Funktionen

4.11.1. Fkt mit >= 1 boolschen Parametern die einen boolschen Wahrheitswert zurückgibt

4.11.2. Jede Aussagenlogische Formel phi, mit |Var(phi)| = n berechnet n-stellige boolsche-Fkt Fi

4.12. Normalformen

4.12.1. Konjunktive

4.12.2. Disjunktive

4.12.3. jede ALF kann in KNF/DNF gewandelt werden

4.13. Funktionale Vollständigkeit

4.13.1. Um alles ausdrücken zu können, braucht man nicht alle Junktoren.

4.13.2. nicht & und reichen, weil man das oder mit und/nicht darstellen kann

4.14. Erfüllbarkeit

4.14.1. Erfüllbar = die Formel phi hat ein Modell

4.14.2. Erfüllbarkeitsproblem

4.14.2.1. Gegeben: Formel F. Frage: Gibt es eine Belegung V, die ein Modell von F ist?

4.14.2.2. NP-Vollstaendig

4.14.3. Eine Menge von Formeln heißt erfüllbar, wenn mindestens eine ein Modell besitzt

4.15. Gültigkeit

4.15.1. Gültig = Tautologie = alle möglichen Belegungen sind ein Modell

4.15.2. Naiver Algorithmus: Zähle alle 2^n Belegungen auf und Prüfe

4.15.3. co-NP-vollständig

4.15.4. In KNF liearzeit

4.16. Dualität von Erfüllbarkeit/Gültigkeit

4.16.1. phi gültig, wenn nicht phi unerfüllbar ist

4.16.2. phi erfüllbar, wenn nicht phi gültig ist

4.17. Folgerbarkeit

4.17.1. Eine Formel psi ist folgerbar aus einer anderen Formel phi gdw. für alle Belegungen V mit V |= phi ist auch V |= psi

4.17.2. Schreibweise: phi |= psi (aus phi folgt psi. psi ist Konsequenz von phi)

4.17.3. Modus Ponens

4.17.3.1. phi UND (phi -> psi) |= psi

4.17.3.2. Aus: Es regnet (phi) UND Wenn es regnet, wird die Straße nass (phi -> psi), folgt: Straße ist nass (psi)

4.17.4. Beispiel: x UND y |= x

4.17.4.1. Alle Belegungen die auf der linken Seite Wahr ergeben, müssen auch rechts wahr sein.

4.18. Hornformeln

4.18.1. Formel in KNF, wobei jede Disjunktion höchstens 1 Positives Literal enthält

4.18.2. Erfüllbarkeit in linearzeit

4.18.3. Ausdrückbarkeit

4.18.3.1. x OR y -> z

4.18.3.2. nicht ausdrückbar: x OR y

4.19. Resolutionskalkül

4.19.1. Kalkül: Rechenregeln zum umformen der Formel

4.19.2. Resolutionskalkül

4.19.2.1. Kalkül zum entscheiden der unerfüllbarkeit von ALF in KNF

4.19.2.2. wegen Dualität auch Tautologie prüfbar

4.19.2.3. Klauselmenge aus KNF erstellen

4.19.2.4. Resolvente

4.19.2.4.1. Anschaulich: Wenn in F1 eine var positiv und in F2 negativ vorkommt, kann man die streichen. rest ist die Resolvente

4.19.2.4.2. K1, K2, K3 Klauseln. K3 Resolvente von K1 und K2, wenn es in K1 ein Literal postiv gibt, welches in K2 negativ ist

4.19.2.4.3. K3 = K1\{L} U K2\{neg L}

4.19.2.5. Resolutionslemma

4.19.2.5.1. F AL, K(F) Klauselmenge. K3 Resolvente von K1, K2. F ist äquivalent zu K(F) U {K3}

4.19.2.5.2. Wir können die Resolvente zur Formel hinzufügen und verändern damit die Formel nicht

4.19.2.6. Resolutionssatz

4.19.2.6.1. Eine Formel F unerfüllbar gdw leere Menge in Res^∞ (K(F)) gilt.

4.19.2.6.2. Also wenn die leere Menge als Resolvente rauskommt

4.19.2.6.3. Abbruchbedingung: 1. leere Menge kommt raus 2. Es fällt nichts mehr weg, es ändert sich nichts

4.19.2.7. Resolutionsschritte

4.19.3. Aufwand

4.19.3.1. NP

4.19.3.2. Es gibt spezialtypen von Formeln mit denen Berechnung in polynomieller Zeit möglich ist -> Horn-Formeln

4.20. Einheitsresolution

4.20.1. Einheitsresolvente:

4.20.1.1. Wenn ein Literal aus denen man die Resolvente macht nur ein Literal hat

4.20.1.2. Wenn leere Menge bei Einheitsresolution rauskommt, ist Horn-Formel unerfüllbar

4.21. Hilbert-Kalkül

4.21.1. Alle gültigen Formeln erzeugen

4.21.2. Gibt so Schlussfolgerungsregeln

5. Allgemein

5.1. Logisches System

5.2. Anwendung von Logik

5.2.1. Automatische Beweise

5.2.2. KI

5.2.3. Datenbanken