Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Erklärung
Aussagenlogik kann nur konkrete Sätze. Prädikatenlogik kann Aussagen über Objekte und ihre Beziehungen. Klausurpflicht in 9/15 Modellierungs-Modulen.
Die Idee in einem Satz
Prädikatenlogik 1. Stufe (First-Order Logic, FOL): Erweiterung der Aussagenlogik um Quantoren (∀, ∃) und Prädikate (Eigenschaften / Beziehungen mit Variablen).
Syntax: 5 Bausteine
1. Konstanten (Individuen)
Konkrete Objekte: Peter, Berlin, 42.
2. Variablen
Platzhalter für Objekte: x, y, z, .... Meist Kleinbuchstaben.
3. Prädikate (Eigenschaften / Beziehungen)
Großbuchstaben mit Argumenten:
Mensch(x), einstellig: "x ist ein Mensch"Liebt(x, y), zweistellig: "x liebt y"Zwischen(x, y, z), dreistellig
4. Junktoren (wie Aussagenlogik)
neg (nicht), land (und), lor (oder), → (impliziert), ↔ (genau dann wenn).
5. Quantoren
- Allquantor
∀: "für alle" - Existenzquantor
∃: "es existiert mindestens ein"
Beispiele für Formeln
Einfache Aussagen
| Deutsch | Formel |
|---|---|
| Alle Menschen sind sterblich | ∀ x (Mensch(x) → Sterblich(x)) |
| Es gibt einen sterblichen Menschen | ∃ x (Mensch(x) land Sterblich(x)) |
| Peter ist ein Mensch und sterblich | Mensch(Peter) land Sterblich(Peter) |
Verschachtelte Quantoren
Reihenfolge ist wichtig!
| Formel | Bedeutung |
|---|---|
∀ x ∃ y Vater(y, x) | Jeder Mensch hat (mindestens) einen Vater. |
∃ y ∀ x Vater(y, x) | Es gibt EINEN Vater von ALLEN, Adam! |
Beide Aussagen sind verschieden! ∀∃ ≠ ∃∀ im Allgemeinen.
Quantor-Regeln
Allquantor ∀
∀ x P(x) ist wahr, wenn P(a) wahr ist für ALLE a in der Domäne.
Falsifikation: Zeige EIN Gegenbeispiel.
Existenzquantor ∃
∃ x P(x) ist wahr, wenn P(a) wahr ist für MINDESTENS EIN a.
Beweis: Konstruiere ein Beispiel.
De Morgan für Quantoren
neg(∀ x P(x)) ≡ ∃ x neg P(x)
neg(∃ x P(x)) ≡ ∀ x neg P(x)
"Nicht alle" = "Es gibt einen, der nicht". "Nicht existiert" = "für alle gilt nicht".
Freie und gebundene Variablen
Eine Variable ist:
- Gebunden, wenn sie durch einen Quantor eingeführt wird.
- Frei, wenn sie nicht gebunden ist.
Beispiel:
∀ x underbraceLiebt(x, y)_(x gebunden, y frei)
Eine Formel ohne freie Variablen heißt Satz (Sentence), kann nur wahr oder falsch sein.
Modellierungs-Beispiele
Familien-Beziehungen
- "x ist Elternteil von y":
Eltern(x, y) - "x ist Geschwister von y":
∃ z (Eltern(z, x) land Eltern(z, y) land x ≠ y) - "x ist Großeltern von y":
∃ z (Eltern(x, z) land Eltern(z, y))
Zahlen
- "x ist gerade":
∃ k (x = 2k) - "x ist prim":
x > 1 land ∀ a ∀ b (x = a · b → a = 1 lor b = 1)
Graphen
- "Es gibt eine Kante zwischen x und y":
Edge(x, y) - "Knoten x ist erreichbar von y":
Path(y, x)(transitive Hülle)
Interpretation / Modell
Ein Modell M besteht aus:
- Domäne
D, Menge von Objekten - Interpretation der Konstanten, z.B.
Peter^Mist ein bestimmtes Element inD - Interpretation der Prädikate, z.B.
Mensch^M ⊆ Dist die Menge der Menschen
Eine Formel ist wahr im Modell, wenn sie sich gemäß M als wahre Aussage interpretieren lässt.
Gültigkeit + Erfüllbarkeit
| Begriff | Bedeutung |
|---|---|
| Erfüllbar (Satisfiable) | Existiert ein Modell, in dem Formel wahr ist |
| Allgemeingültig (Valid) | Wahr in JEDEM Modell, Tautologie |
| Widerspruch (Contradictory) | Wahr in KEINEM Modell, Antinomie |
| Kontingent | Wahr in manchen, falsch in anderen Modellen |
Entscheidbarkeit: Aussagenlogik ist entscheidbar. Prädikatenlogik 1. Stufe ist nur semi-entscheidbar, es gibt keinen Algorithmus, der für jede Formel die Gültigkeit in endlicher Zeit feststellt (Church 1936, Turing 1936).
Klausur-Faustregeln
1. Großbuchstaben für Prädikate, Kleinbuchstaben für Variablen. Konstanten oft mit konkreten Namen.
2. Quantor-Reihenfolge wichtig: ∀∃ ≠ ∃∀.
3. De Morgan für Quantoren: ¬∀ ⇔ ∃¬, ¬∃ ⇔ ∀¬.
4. Implikation in ∀ häufig: "Alle X sind Y" = ∀x (X(x) → Y(x)).
5. Konjunktion in ∃ häufig: "Es gibt ein X, das Y ist" = ∃x (X(x) ∧ Y(x)).
6. Prädikatenlogik 1. Stufe ist nur semi-entscheidbar. Keine Algorithmus für allgemeine Gültigkeit.
Häufige Stolpersteine
1. ∀∃ mit ∃∀ verwechseln. "Jeder hat einen Vater" vs. "Es gibt einen Vater aller". Unterschiedliche Bedeutungen.
2. Implikation in ∃-Aussagen. "Es gibt einen X mit Y" → falsch wäre ∃x (X(x) → Y(x)). Richtig: ∃x (X(x) ∧ Y(x)).
3. Vergessen, Variablen zu binden. Formeln mit freien Variablen sind keine Sätze und können nicht uneingeschränkt wahr/falsch sein.
4. Negation falsch transformieren. Bei ¬(∀x P(x) → Q(x)) muss man umformen: ¬(∀x (¬P(x) ∨ Q(x))) ⇔ ∃x (P(x) ∧ ¬Q(x)).
5. Mehrstellige Prädikate Argumente vertauschen. Liebt(Peter, Maria) ≠ Liebt(Maria, Peter). Reihenfolge ist semantisch wichtig.
6. Annahme dass FOL alles ausdrücken kann. Falsch, manche Aussagen brauchen Logik höherer Stufe (z.B. Induktions-Prinzip in der Arithmetik).
Interaktiv verstehen
Prädikatenlogik-Explorer
5 Beispiel-Formeln mit Highlighting: Quantoren (rot/akzent), Prädikate (fett), Variablen (kursiv). Toggle zwischen den Beispielen für Detail-Interpretation.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Bei "Formalisieren Sie die Aussage" IMMER schrittweise: 1) Welche Objekte/Konstanten sind beteiligt? 2) Welche Prädikate (Eigenschaften/Beziehungen)? 3) Welcher Quantor passt (alle/manche/genau einer)? 4) Junktoren (→ bei "wenn-dann", ∧ bei "und"). Bei "es gibt X, das Y ist" IMMER ∃x (X(x) ∧ Y(x)), nicht →!
Praxis-Übung
Prädikatenlogik, Praxis-Übung
6 Aufgaben zu Formalisierung, Quantoren und De Morgan.
Klausurfragen mit Lösungen (6)
- F1.Welche Aussage modelliert 'Alle Menschen sind sterblich' korrekt?
Antwort: ∀x (Mensch(x) → Sterblich(x))
Erklärung: Standard-Muster für 'Alle X sind Y': ∀x (X(x) → Y(x)). Antwort A würde sagen: 'Alle Objekte sind Menschen UND sterblich', falsch (nicht alle sind Menschen). Antwort C ist Existenz-Aussage. Antwort D fehlt Klammerung. Klausur-Klassiker: 'Alle X sind Y' = Implikation in ∀.
- F2.Welche Aussage modelliert 'Es gibt einen Studenten, der Mathe mag' korrekt?
Antwort: ∃x (Student(x) ∧ MagMathe(x))
Erklärung: Standard-Muster für 'Es gibt X, das Y ist': ∃x (X(x) ∧ Y(x)). Antwort A wäre falsch: ∃x (Student(x) → MagMathe(x)) ist trivial wahr (jedes Nicht-Student-Objekt erfüllt die Implikation). Klausur-Falle: → in ∃ ist falsch, ∧ ist richtig. Umgekehrt: → in ∀ ist richtig.
- F3.Ordne Quantor-Konstellation der Bedeutung zu.
Zuordnungen:
- ∀x ∃y Vater(y, x) → Jeder hat einen Vater (verschieden je nach Person)
- ∃y ∀x Vater(y, x) → EIN gemeinsamer Vater aller (Adam)
- ∀x ∀y Liebt(x, y) → Jeder liebt jeden
- ∃x ∀y Liebt(x, y) → Es gibt jemand, der alle liebt
Erklärung: Quantor-Reihenfolge wichtig: ∀∃ ≠ ∃∀. ∀x ∃y P(x, y): für jedes x ein anderes y möglich. ∃y ∀x P(x, y): ein FESTES y für alle x. ∀∀ und ∃∃ sind kommutativ, Reihenfolge egal.
Typ: Zuordnung
- F4.Wie negiert man ∀x P(x) korrekt (De Morgan)?
Antwort: ¬∀x P(x) ⇔ ∃x ¬P(x)
Erklärung: De Morgan für Quantoren: ¬∀x P(x) ⇔ ∃x ¬P(x). 'Nicht alle erfüllen P' bedeutet 'Es gibt mindestens einen, der P nicht erfüllt'. Analog ¬∃x P(x) ⇔ ∀x ¬P(x). Klausur-Klassiker bei Beweisen + logischen Umformungen.
- F5.Die Aussagen ∀x ∃y P(x, y) und ∃y ∀x P(x, y) sind logisch äquivalent.
Antwort: Falsch
Erklärung: FALSCH. ∀x ∃y P(x, y) erlaubt unterschiedliche y für unterschiedliche x. ∃y ∀x P(x, y) verlangt ein FESTES y, das für alle x funktioniert. Beispiel mit P(x, y) = 'y > x' in ℕ: ∀x ∃y wahr (zu jedem x gibt es größeres y). ∃y ∀x falsch (kein y ist größer als ALLE x). ∀∃ ist schwächer als ∃∀. Klausur-Falle.
Typ: Wahr/Falsch
- F6.Was bedeutet 'Prädikatenlogik 1. Stufe ist semi-entscheidbar'?
Antwort: Es gibt einen Algorithmus, der gültige Formeln bestätigt (positiv halt), aber nicht-gültige nicht zwingend in endlicher Zeit ablehnt
Erklärung: Semi-Entscheidbarkeit (Church 1936, Turing 1936): Für gültige FOL-Formeln existiert Beweis-Verfahren, das in endlicher Zeit JA sagt. Für nicht-gültige Formeln kann der Algorithmus aber unendlich lange laufen. Daher: FOL ist semi-entscheidbar, aber NICHT entscheidbar. Aussagenlogik ist im Gegensatz dazu vollständig entscheidbar (Wahrheits-Tabelle).
Klausur-Quiz
Prädikatenlogik, Klausur-Quiz
6 typische Klausurfragen zu Syntax, Semantik und Entscheidbarkeit.
Klausurfragen mit Lösungen (6)
- F1.Was ist der Unterschied zwischen Aussagenlogik und Prädikatenlogik 1. Stufe?
Antwort: Prädikatenlogik kennt Quantoren (∀, ∃) und Prädikate mit Variablen; Aussagenlogik nur konkrete Aussagen
Erklärung: Aussagenlogik: nur konkrete Aussagen (A, B, ...) mit Junktoren (∧, ∨, ¬, →). Prädikatenlogik 1. Stufe: Erweiterung um Quantoren (∀, ∃), Prädikate (P(x)), Variablen, Konstanten. Damit kann Prädikatenlogik viel reichhaltigere Strukturen modellieren, Klausur-Standard-Vergleich.
- F2.Welches Symbol ist der Existenzquantor in der Prädikatenlogik?
Antwort: ∃
Erklärung: Existenzquantor: ∃ (umgekehrtes E für 'Es existiert'). Allquantor: ∀ (umgekehrtes A für 'Für Alle'). →: Implikation. ⊕: XOR (Exklusiv-Oder). Klausur-Standard.
- F3.In der Prädikatenlogik haben Variablen, die unter einem Quantor stehen, den Status {{1}}. Ohne Quantor sind sie {{2}}. Eine Formel ohne freie Variablen heißt {{3}}. De-Morgan-Regel: ¬∀x P(x) ⇔ {{4}} ¬P(x).
Lösungen pro Lücke:
- {{1}}: gebunden
- {{2}}: frei
- {{3}}: Satz / Sentence
- {{4}}: ∃x / ∃
Erklärung: Gebundene Variable: unter Quantor (∀x, ∃x). Freie Variable: ohne Quantor, Formel kann ohne Belegung nicht wahr/falsch sein. Satz: alle Variablen gebunden, also abgeschlossen. De Morgan: ¬∀ ⇔ ∃¬, ¬∃ ⇔ ∀¬. Diese Konzepte sind FOL-Pflichtwissen.
Typ: Lückentext
- F4.Bringe die 4 Stufen der Logik-Hierarchie in aufsteigender Ausdrucksstärke.
Richtige Reihenfolge:
- Aussagenlogik (nur Junktoren)
- Prädikatenlogik 1. Stufe (Quantoren über Objekte)
- Logik 2. Stufe (Quantifizierung über Prädikate)
- Höhere Logiken (HOL)
Erklärung: Hierarchie: Aussagenlogik (entscheidbar, Wahrheits-Tabelle) → Prädikatenlogik 1. Stufe (semi-entscheidbar, ∀x über Objekte) → 2. Stufe (∀P über Prädikate, z.B. Induktion in Arithmetik) → höhere Logiken. Je mächtiger, desto weniger entscheidbar. Praxis-Standard: FOL als Compromise zwischen Ausdrucksstärke und Entscheidbarkeit.
Typ: Reihenfolge
- F5.Wann ist eine Formel der Prädikatenlogik 1. Stufe ALLGEMEINGÜLTIG (Valid)?
Antwort: Wenn sie in JEDEM Modell wahr ist
Erklärung: Allgemeingültig (Valid) = wahr in JEDEM Modell, eine Tautologie der Prädikatenlogik. Beispiel: ∀x (P(x) ∨ ¬P(x)) (Tertium non datur). Erfüllbar = wahr in MINDESTENS EINEM Modell. Widerspruch = wahr in KEINEM Modell. Klausur-Standard.
- F6.Die Prädikatenlogik 1. Stufe ist semi-entscheidbar, es gibt einen Algorithmus, der gültige Formeln bestätigt, aber nicht-gültige Formeln können unendlich lange im Algorithmus laufen.
Antwort: Wahr
Erklärung: RICHTIG. Church 1936 + Turing 1936 zeigten: die Gültigkeit in FOL ist semi-entscheidbar (recursively enumerable). Für gültige Formeln gibt es einen vollständigen Beweis-Algorithmus (z.B. Resolution). Für nicht-gültige Formeln kann der Algorithmus aber unendlich lange laufen. Konsequenz: kein Algorithmus, der für JEDE Formel die Gültigkeit in endlicher Zeit entscheidet. Aussagenlogik ist dagegen vollständig entscheidbar (Wahrheits-Tabelle).
Typ: Wahr/Falsch
