Kurs:Einführung in die mathematische Logik (Osnabrück 2021)/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

Unterscheide zwischen den verschiedenen Bedeutungen von Gleichheit.

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

Aufgabe

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

$\vdash 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},\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 ${}x_{1},\ldots ,x_{n}$ Variablen, ${}s_{1},\ldots ,s_{n},t_{1},\ldots ,t_{n}$ Terme und ${}\alpha$ ein Ausdruck in einer prädikatenlogischen Sprache ${}L^{S}$. Zeige, dass

$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)}$

allgemeingültig ist.

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

Es sei ${}S$ ein Symbolalphabet einer prädikatenlogischen Sprache mit einer leeren Variablenmenge. Zeige, dass man für Terme ${}s,t$ im Allgemeinen ${}s=t\rightarrow t=s$ nicht ableiten kann.

Aufgaben zum Abgeben

Aufgabe (2 Punkte)

Es seien ${}c,d$ Konstanten, es sei ${}f$ ein zweistelliges Funktionssysmbol und es ${}R$ ein dreistelliges Relationssymbol. Man erläutere, wie man die prädikatenlogische Tautologie

${\left(Rxcfyd\vee z=x\right)}\wedge \neg {\left(Rxcfyd\vee z=x\right)}\rightarrow {\left(\exists xfxc=d\right)}$

aus einer aussagenlogischen Tautologie im Sinne von Lemma 10.2 erhält.

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.12

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.

Die Aufgabe zum Aufgeben

Aufgabe (6 Punkte)

Wir betrachten eine Variante des Ableitungskalkül (geschrieben ${}\vdash _{V}$) der Aussagenlogik, bei dem die Grundtautologien aus Axiom 3.8 unverändert übernommen werden, bei der aber der Modus ponens durch die Schlussregel

Wenn ${}\vdash _{V}\alpha \wedge (\alpha \rightarrow \beta )$, dann ist ${}\vdash _{V}\beta$

ersetzt wird. Stimmen ${}\vdash$ und ${}\vdash _{V}$ überein?

Fußnoten