Einführung in die Logik

Institut für
Theoretische Informatik
ITI
Dr. Jürgen Koslowski
Einführung in die Logik
Aufgabenblatt B, 2016-07-04
Übungsaufgabe 47
Wir betrachten die Theorie der gerichteten Graphen, also die Signatur Σ = hRi, die aus nur
einem 2-stelligen Prädikatssymbol besteht. Welche der folgenden Formeln sind allgemeingültig?
Im positiven Fall genügt eine kurze Begründung, andernfalls ist eine Σ-Struktur anzugeben, in
der die Formel falsch ist.
(a) ∃y : ∀x : P (x, y) ⇒ ∀x : ∃y : P (x, y)
(b) ∀x : ∃y : P (x, y) ⇒ ∃y : ∀x : P (x, y)
(c) ∃x : ∃y : x = y
(d) ∃x : ∀y : ∃x : x = y
Lösungsvorschlag:
(a) Allgemeingültig: sofern die line Seite erfüllt wird, sind alle Knoten x mit einen universellen
Knoten y verbunden. Insbesondere geht von jedem Knoten eine gerichtete Kante aus. Somit
wird auch die rechte Seite erfüllt.
(b) Umgekehrt, wenn von jederm Knoten x eine Kante ausgeht, braucht diese nicht für alle Knoten dasselbe Ziel zu haben. Als Struktur betrachte einen Graphen mit 2 Knoten
{u, v}, die wechselseitig verbunden sind: R = {hu, vi, hv, ui}. Damit ist die Formel nicht
allgemeingültig.
(c) Unsere Modelle sind alle nichtleer. Insofern kann man für x und y dasselbe Element wählen:
allgemeingültig
(d) Das Element x aus der Gleichung wird durch den inneren Existenzquantor gebunden; damit
hat der äußere Existenzquantor keinen Effekt. Umbenennen liefert die äquivalente Formel
∃z : ∀y : ∃x : x = y
Die innere Formel ∀y : ∃x : x = y ist allgemeingültig: man kann für y immer x wählen. Da
unsere Modelle immer nichtleeren Träger haben, ist auch die Menge der Wahrheitswerte,
über die für den äußeren Quantor das Supremum zu bestimmen ist, nichtleer. Da mindestens einer dieser Wahrheitswerte 1 ist, nimmt auch das Supremum diesen Wert an. Also:
allgemeingültig.
Aufgabe 48 [10 PUNKTE]
Betrachten Sie die Signatur mit den Funktionssymbolen e, f0 , f1 mit Stelligkeiten 0, 1, 1
und mit dem Relationssymbol P der Stelligkeit 2. Für diese Signatur sei die folgende Struktur
A = hA, eA , f0A , f1A , P A i gegeben: die Trägermenge A = {0, 1}∗ besteht aus allen Binärwörtern,
eA = ε ist das leere Wort (Binärstring der Länge 0), f0A (w) = w0 und f1A (w) = w1 hängen an
ein gegebenes Binärwort eine 0 bzw. eine 1 an und P A (v, w) bedeutet v ist ein Präfix von w.
(a) [4 punkte] Ist die Formel ∀w : ∃v : ∀u : ((P (w, v) ∧ u = x) ∧ P (v, w)) in dieser Struktur
gültig? Begründen Sie Ihre Antwort.
(b) [4 punkte] Ist die Formel ∀x : (¬(x = e) ⇒ ∃y : (x = f0 (y) ∨ x = f1 (y))) in dieser
Struktur gültig? Beschreiben Sie in Worten, was sie aussagt.
(c) [2 punkte] Geben Sie eine Formel mit der freien Variablen x an, die in der gegebenen
Struktur genau für die Belegungen α wahr ist, für die α(x) mit 00 endet.
Aufgabe 49 [12 PUNKTE]
Wir betrachten die Signatur Σ mit einem zweistelligen Prädikatensymbol <, und die Σ-Struktur
N mit Trägermenge IN , in der < die übliche Bedeutung hat. Für welche Belegungen α :
IN gilt α
b(ϕi ) = 1?
{x, y}
(a) [4 punkte] ϕo := x = x ∨ ∀x : x < x
(b) [4 punkte] ϕ1 := x = y ∧ ∀x : x < x
(c) [4 punkte] ϕ2 := x = y ∧ ∀x : ∃y : x < y
Argumentieren Sie detailliert, unter Verwendung der formalen Semantik der Prädikatenlogik
(also der induktiven Definition von α
b).
Aufgabe 50 [6 PUNKTE]
[6 punkte] Wir betrachten eine Signatur Σ mit nur einem einstelligen Funktionssymbol f . Finden Sie eine Formel ϕ, die in keiner endlichen Σ-Struktur, aber in mindestens einer unendlichen
Σ-Struktur wahr ist.
[Hinweis: Jede injektive Funktion auf einer endlichen Menge ist bereits surjektiv.]
Abgabe bis Montag, 2016-07-11, im Kasten neben IZ 343

Download Report