Kurs:Einführung in die mathematische Logik (Osnabrück 2016)/Arbeitsblatt 10

Übungsaufgaben

Aufgabe

Ersetze in den folgenden aussagenlogischen Tautologien

p_{1} durch β_{1} := \exists x R x y, p_{2} durch β_{2} := \forall u (f u = c \to P c), p_{3} durch β_{3} := \exists y \forall x g x z = y, p_{4} durch β_{4} := R c u \to c = u .

$p_{1} \land p_{2} \to p_{1}$ ,
$(p_{1} \land p_{4} \to \neg p_{2}) \land (p_{1} \land p_{4} \to (p_{2} \to p_{1})) \to (p_{1} \land p_{4} \to \neg p_{2} \land (p_{2} \to p_{1}))$ ,
$p_{3} \land \neg p_{3} \to p_{4}$ ,
$(p_{1} \land p_{4} \to p_{3}) \land (\neg (p_{1} \land p_{4}) \to p_{3}) \to p_{3}$ .

Aufgabe

Unterscheide zwischen den verschiedenen Bedeutungen von Gleichheit.

Gleichheit von Elementen in einer Menge.
Gleichheit von Zeichenketten.
Das Gleichheitssymbol in einer erststufigen Sprache.

Aufgabe

Es sei $S$ ein Symbolalphabet einer Sprache erster Stufe. Es seien $S$ -Terme $s, t$ mit

⊢ s = t

gegeben. Zeige, dass es sich bei $s$ und $t$ um eine identische Zeichenreihe handelt.

Aufgabe

Es sei $S$ ein Symbolalphabet und $t_{1}, \dots, t_{n}$ seien $S$ -Terme. Zeige die Ableitbarkeit

⊢ t_{1} = t_{2} \land t_{2} = t_{3} \land \dots \land t_{n - 1} = t_{n} \to t_{1} = t_{n} .

Zeige direkt (ohne die Verwendung der Ableitungsbeziehung), dass die folgenden Ausdrücke allgemeingültig sind (dabei seien $r, s, t, s_{1}, \dots, s_{n}, t_{1}, \dots, t_{n}$ Terme, $f$ ein $n$ -stelliges Funktionssymbol und $R$ ein $n$ -stelliges Relationssymbol).

$⊨ s = t \to t = s .$
$⊨ r = s \land s = t \to r = t .$
$⊨ s_{1} = t_{1} \land \dots \land s_{n} = t_{n} \to f s_{1} \dots s_{n} = f t_{1} \dots t_{n} .$
$⊨ s_{1} = t_{1} \land \dots \land s_{n} = t_{n} \land R s_{1} \dots s_{n} \to R t_{1} \dots t_{n} .$

Aufgabe

Es seien $r_{1}, r_{2}, s, t$ Terme einer prädikatenlogischen Sprache $L^{S}$ und sei $x$ eine Variable. Zeige durch ein Beispiel, dass

s = t \to r_{1} \frac{s}{x} = r_{2} \frac{t}{x}

nicht ableitbar sein muss.^[1]

Aufgabe *

Zeige durch ein Beispiel, dass für Terme $r_{1}, r_{2}, s$ und eine Variable $x$ einer prädikatenlogischen Sprache $L^{S}$ der Ausdruck

r_{1} = r_{2} \to r_{1} \frac{s}{x} = r_{2} \frac{s}{x}

nicht ableitbar sein muss.

Aufgabe

Gehört in einem Ausdruck der Form $(x = y) \frac{t}{x}$ die Symbolfolge $\frac{t}{x}$ zur prädikatenlogischen Sprache? Gehört $(x = y) \frac{t}{x}$ dazu?

Aufgaben zum Abgeben

Aufgabe (4 Punkte)

Es seien $r, s_{1}, \dots, s_{n}, t_{1}, \dots, t_{n}$ Terme einer prädikatenlogischen Sprache $L^{S}$ und seien $x_{1}, \dots, x_{n}$ verschiedene Variablen. Zeige durch Induktion über den Aufbau des Termes $r$ die Ableitbarkeit

⊢ s_{1} = t_{1} \land \dots \land s_{n} = t_{n} \to (r \frac{s_{1}, \dots, s_{n}}{x_{1}, \dots, x_{n}} = r \frac{t_{1}, \dots, t_{n}}{x_{1}, \dots, x_{n}}) .

Aufgabe (4 Punkte)

Es seien $s_{1}, \dots, s_{n}, t_{1}, \dots, t_{n}$ Terme einer prädikatenlogischen Sprache $L^{S}$ und seien $x_{1}, \dots, x_{n}$ verschiedene Variablen.

Es sei $R$ ein $k$ -stelliges Relationssymbol und $r_{1}, \dots, r_{k}$ seien Terme. Zeige die Ableitbarkeit
$⊢ s_{1} = t_{1} \land \dots \land s_{n} = t_{n} \to ((R r_{1} \dots r_{k}) \frac{s_{1}, \dots, s_{n}}{x_{1}, \dots, x_{n}} \to (R r_{1} \dots r_{k}) \frac{t_{1}, \dots, t_{n}}{x_{1}, \dots, x_{n}}) .$
Es seien $r_{1}$ und $r_{2}$ Terme. Zeige die Ableitbarkeit
$⊢ s_{1} = t_{1} \land \dots \land s_{n} = t_{n} \to (r_{1} \frac{s_{1}, \dots, s_{n}}{x_{1}, \dots, x_{n}} = r_{2} \frac{s_{1}, \dots, s_{n}}{x_{1}, \dots, x_{n}} \to r_{1} \frac{t_{1}, \dots, t_{n}}{x_{1}, \dots, x_{n}} = r_{2} \frac{t_{1}, \dots, t_{n}}{x_{1}, \dots, x_{n}}) .$

Tipp: Verwende Aufgabe 10.10

Aufgabe (4 Punkte)

Es sei $S$ ein Symbolalphabet, $s_{1}, \dots, s_{n}, t_{1}, \dots, t_{n}$ seien $S$ -Terme, $x_{1}, \dots, x_{n}$ verschiedene Variablen und $α$ sei ein $S$ -Ausdruck. Zeige die Allgemeingültigkeit

⊨ s_{1} = t_{1} \land \dots \land s_{n} = t_{n} \to (α \frac{s_{1}, \dots, s_{n}}{x_{1}, \dots, x_{n}} \to α \frac{t_{1}, \dots, t_{n}}{x_{1}, \dots, x_{n}}) .

Aufgabe (4 Punkte)

Zeige durch ein Beispiel, dass bei einem ableitbaren Ausdruck der Form

⊢ s = t \to ((\exists z β) \frac{s}{x} \to (\exists z β) \frac{t}{x})

die durch die Existenzquantoren gebundenen Variablen (nach der durchgeführten Substitution) nicht übereinstimmen müssen.

Fußnoten

↑ Die Nicht-Ableitbarkeit wird durch die Angabe eines Modells gezeigt; dies verwendet die Korrektheit des Ableitungskalküls, den wir noch nicht vollständig behandelt haben.

<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2016) | >>

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)

[1] Die Nicht-Ableitbarkeit wird durch die Angabe eines Modells gezeigt; dies verwendet die Korrektheit des Ableitungskalküls, den wir noch nicht vollständig behandelt haben.

[1]