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

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 (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

Lösungen zu der folgenden Aufgabe direkt an den Dozenten. Bis Ende Mai.

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