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).
Teil 1·Erklärung
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
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).
Aussagenlogik kann nur konkrete Sätze. Prädikatenlogik kann Aussagen über Objekte und ihre Beziehungen. Klausurpflicht in 9/15 Modellierungs-Modulen.
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 →!
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
Aussagenlogik kann nur konkrete Sätze. Prädikatenlogik kann Aussagen über Objekte und ihre Beziehungen. Klausurpflicht in 9/15 Modellierungs-Modulen.
Prädikatenlogik 1. Stufe (First-Order Logic, FOL): Erweiterung der Aussagenlogik um Quantoren (∀, ∃) und Prädikate (Eigenschaften / Beziehungen mit Variablen).
Konkrete Objekte: Peter, Berlin, 42.
Platzhalter für Objekte: x, y, z, .... Meist Kleinbuchstaben.
Großbuchstaben mit Argumenten:
Mensch(x) — einstellig: "x ist ein Mensch"Liebt(x, y) — zweistellig: "x liebt y"Zwischen(x, y, z) — dreistelligneg (nicht), land (und), lor (oder), → (impliziert), ↔ (genau dann wenn).
∀: "für alle"∃: "es existiert mindestens ein"| 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) |
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.
∀ x P(x) ist wahr, wenn P(a) wahr ist für ALLE a in der Domäne.
Falsifikation: Zeige EIN Gegenbeispiel.
∃ x P(x) ist wahr, wenn P(a) wahr ist für MINDESTENS EIN a.
Beweis: Konstruiere ein Beispiel.
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".
Eine Variable 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.
Eltern(x, y)∃ z (Eltern(z, x) land Eltern(z, y) land x ≠ y)∃ z (Eltern(x, z) land Eltern(z, y))∃ k (x = 2k)x > 1 land ∀ a ∀ b (x = a · b → a = 1 lor b = 1)Edge(x, y)Path(y, x) (transitive Hülle)Ein Modell M besteht aus:
D — Menge von ObjektenPeter^M ist ein bestimmtes Element in DMensch^M ⊆ D ist die Menge der MenschenEine Formel ist wahr im Modell, wenn sie sich gemäß M als wahre Aussage interpretieren lässt.
| 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).
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.
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).
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 →!
6 Aufgaben zu Formalisierung, Quantoren und De Morgan.
Klausurfragen mit Lösungen (6)
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 ∀.
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.
Zuordnungen:
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
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.
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
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).
6 typische Klausurfragen zu Syntax, Semantik und Entscheidbarkeit.
Klausurfragen mit Lösungen (6)
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.
Antwort: ∃
Erklärung: Existenzquantor: ∃ (umgekehrtes E für 'Es existiert'). Allquantor: ∀ (umgekehrtes A für 'Für Alle'). →: Implikation. ⊕: XOR (Exklusiv-Oder). Klausur-Standard.
Lösungen pro Lücke:
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
Richtige Reihenfolge:
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
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.
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