Folien Übungsstunde 10

PRÄDIKATENLOGIK
1. PRÄDIKATE UND QUANTOREN
Begriffe:
Variablen: Bezeichnen beliebige Objekte des Universums
Beispiel: x,y,z
Konstanten: Bezeichnen feste Objekte des Universums
Beispiel: Die Zahl 0
Funktionen: Operieren auf dem Universum
Beispiel: add(x,y)
Gleichungen: s ≈ t bedeutet, dass die Terme s und t
denselben Wert haben im Universum.
Prädikate: R(t1,t2,…,tn) heisst, dass das Prädikat R auf
t1,…,tn zutrifft.
Beispiel: Smaller(x,y)
Allquantor: ∀xA ist wahr, falls A wahr ist für jedes x aus
dem Universum. ∀xA ist falsch, wenn es ein Objekt x gibt,
so dass A falsch ist.
Existenzquantor: ∃xA ist wahr, falls es mindestens ein x gibt, für
das A wahr ist. ∃xA ist falsch, falls A falsch ist für alle x aus dem
Universum.
2. SYNTAX
Beispiele für Terme: - push(add(x2,1),x3)
- succ(succ(x1))
Beispiele für Formeln: - ∀x(Q(x) ∧ R(x) ∧ ¬∃y(P(y)))
- ∀x((x ≈ zero) → ∃y(succ(y) ≈ x))
Quantoren binden stärker als aussagenlogische Operatoren:
∃x Q(x) ∧ R(x) = (∃x Q(x)) ∧ R(x)
Eine Folge von gleichen Quantoren kann zusammengefasst
werden:
∀x, y, z(R(x, y,z)) steht für ∀x∀y∀z(R(x, y, z))
Beispiel: Block World (Tarski’s World)
Prädikate in Tarski’s World:
Triangle(x)
Square (x)
Pentagon (x)
Small(x)
Medium(x)
Large(x)
SameSize(x,y)
Smaller(x,y)
Larger(x,y)
SameRow(x,y)
SameCol(x,y)
LeftOf(x,y)
Between(x,y,z)
Beispiel: Aussagen über Tarskis World
1. Es gibt genau ein kleines Quadrat.
wahr
∃x(Square(x) ∧ Small(x) ∧ ∀y(Square(y) ∧ Small(y) → y ≈ x))
2. Es gibt mindestens 2 Fünfecke von gleicher Grösse.
wahr
∃x∃y(Pentagon(x) ∧ Pentagon(y) ∧ ¬(x ≈ y) ∧ SameSize(x, y))
3. ∀y∀z(Pentagon(y) ∧ Pentagon(z) → y ≈ z)
falsch
3. FREIE UND GEBUNDENE VARIABLEN
Bereich von Quantoren:
Bereich von ∀y
∃x (P(x) ∧ ∀y(Q(y) → x = y))
Bereich von ∃x
Begriffe:
Freie Variable: Ein Vorkommen einer Variable x in einer
Formel A heisst gebunden, falls es im Bereich eines
Quantors ∃x oder ∀x liegt, sonst heisst das Vorkommen frei.
Satz: Formel die keine freie Variable enthält.
Umbennenung gebundener Variablen:
Formeln, die gleich sind bis auf die Namen der gebundenen
Variablen, werden identifiziert.
Beispiele: - ∀x(P(x) ∧ Q(z)) = ∀t(P(t) ∧ Q(z))
- ∀x(P(x) ∨ Q(y)) ≠ ∀t(P(t) ∨ Q(z))
Substitution von Termen für Variablen
Achtung:
1. Es können nur freie Variablen ersetzt werden.
2. Gebundene Variablen müssen umbenannt werden, falls es zu
einer Kollision kommt.
Beispiel: A = ∀y∃z(R(x,z) ∧ Q(y, z))
Gesucht: A f (xy )
1. Gebundene Variablen umbenennen: A = ∀t∃z(R(x, z) ∧ Q(t, z))
2. Freie Variablen ersetzen: A = ∀t∃z(R(f (y), z) ∧ Q(t,z))
Beispiel 1: Welche der folgenden Ausdrücke sind Formeln der
Prädikatenlogik?
∀x(R(x) ∧ ¬Q(x))
∃y∀x(P(x) ∧ (Q(x) → R(y)))
∀x∀y((P(x) ∧ P(z)) → x ≈ y))
Beispiel 2: A = ∀y(P(x) ∧ R(z) → ∃x(R(x) ∨ (y ≈ z))
1. Gib die Menge der freien und gebundenen Variablen der
Formel A an:
2. Ergebnis der Substitution von f(y) für x in der Formel A:
Beispiel 3: Übersetze die folgenden Aussagen in Prädikatenlogik:
1. Es gibt ein mittelgrosses Fünfeck.
2. Es gibt genau 2 kleine Quadrate.
3. Alle Quadrate befinden sich links von allen Fünfecken.

Download Report