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

Übungsaufgaben

Aufgabe

Ersetze in den folgenden aussagenlogischen Tautologien

$p_{1}{\text{ durch }}\beta _{1}:=\exists xRxy,\,p_{2}{\text{ durch }}\beta _{2}:=\forall u{\left(fu=c\rightarrow Pc\right)},\,p_{3}{\text{ durch }}\beta _{3}:=\exists y\forall xgxz=y,\,p_{4}{\text{ durch }}\beta _{4}:=Rcu\rightarrow c=u.$

1. ${}p_{1}\wedge p_{2}\rightarrow p_{1}$,
2. ${}{\left(p_{1}\wedge p_{4}\rightarrow \neg p_{2}\right)}\wedge {\left(p_{1}\wedge p_{4}\rightarrow {\left(p_{2}\rightarrow p_{1}\right)}\right)}\rightarrow {\left(p_{1}\wedge p_{4}\rightarrow \neg p_{2}\wedge {\left(p_{2}\rightarrow p_{1}\right)}\right)}$,
3. ${}p_{3}\wedge \neg p_{3}\rightarrow p_{4}$,
4. ${}{\left(p_{1}\wedge p_{4}\rightarrow p_{3}\right)}\wedge {\left(\neg {\left(p_{1}\wedge p_{4}\right)}\rightarrow p_{3}\right)}\rightarrow p_{3}$.

Aufgabe

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

$\vdash t_{1}=t_{2}\wedge t_{2}=t_{3}\wedge \ldots \wedge t_{n-1}=t_{n}\rightarrow t_{1}=t_{n}.$

Aufgabe *

Es seien ${}s_{1},\ldots ,s_{n},t_{1},\ldots ,t_{n}$ Terme und ${}f$ ein ${}n$-stelliges Funktionssymbol. Zeige, dass die Ableitbarkeit

$\vdash s_{1}=t_{1}\wedge \ldots \wedge s_{n}=t_{n}\rightarrow fs_{1}\ldots s_{n}=ft_{1}\ldots t_{n}$

gilt.

Aufgabe

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

1. $\vDash s=t\rightarrow t=s.$

2. $\vDash r=s\wedge s=t\rightarrow r=t.$

3. $\vDash s_{1}=t_{1}\wedge \ldots \wedge s_{n}=t_{n}\rightarrow fs_{1}\ldots s_{n}=ft_{1}\ldots t_{n}.$

4. $\vDash s_{1}=t_{1}\wedge \ldots \wedge s_{n}=t_{n}\wedge Rs_{1}\ldots s_{n}\rightarrow Rt_{1}\ldots 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\rightarrow r_{1}{\frac {s}{x}}=r_{2}{\frac {t}{x}}$

nicht ableitbar sein muss.

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}\rightarrow r_{1}{\frac {s}{x}}=r_{2}{\frac {s}{x}}$

nicht ableitbar sein muss.

Aufgabe

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

Aufgaben zum Abgeben

Aufgabe (4 Punkte)

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

$\vdash s_{1}=t_{1}\wedge \ldots \wedge s_{n}=t_{n}\rightarrow {\left(r{\frac {s_{1},\ldots ,s_{n}}{x_{1},\ldots ,x_{n}}}=r{\frac {t_{1},\ldots ,t_{n}}{x_{1},\ldots ,x_{n}}}\right)}.$

Aufgabe (4 Punkte)

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

1. Es sei ${}R$ ein ${}k$-stelliges Relationssymbol und ${}r_{1},\ldots ,r_{k}$ seien Terme. Zeige die Ableitbarkeit

   $\vdash s_{1}=t_{1}\wedge \ldots \wedge s_{n}=t_{n}\rightarrow {\left((Rr_{1}\ldots r_{k}){\frac {s_{1},\ldots ,s_{n}}{x_{1},\ldots ,x_{n}}}\rightarrow (Rr_{1}\ldots r_{k}){\frac {t_{1},\ldots ,t_{n}}{x_{1},\ldots ,x_{n}}}\right)}.$

2. Es seien ${}r_{1}$ und ${}r_{2}$ Terme. Zeige die Ableitbarkeit

   $\vdash s_{1}=t_{1}\wedge \ldots \wedge s_{n}=t_{n}\rightarrow {\left(r_{1}{\frac {s_{1},\ldots ,s_{n}}{x_{1},\ldots ,x_{n}}}=r_{2}{\frac {s_{1},\ldots ,s_{n}}{x_{1},\ldots ,x_{n}}}\rightarrow r_{1}{\frac {t_{1},\ldots ,t_{n}}{x_{1},\ldots ,x_{n}}}=r_{2}{\frac {t_{1},\ldots ,t_{n}}{x_{1},\ldots ,x_{n}}}\right)}.$

Tipp: Verwende Aufgabe 10.8

Aufgabe (4 Punkte)

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

$\vDash s_{1}=t_{1}\wedge \ldots \wedge s_{n}=t_{n}\rightarrow {\left(\alpha {\frac {s_{1},\ldots ,s_{n}}{x_{1},\ldots ,x_{n}}}\rightarrow \alpha {\frac {t_{1},\ldots ,t_{n}}{x_{1},\ldots ,x_{n}}}\right)}.$

Aufgabe (4 Punkte)

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

$\vdash s=t\rightarrow {\left({\left(\exists z\beta \right)}{\frac {s}{x}}\rightarrow {\left(\exists z\beta \right)}{\frac {t}{x}}\right)}$

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

Fußnoten