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

Übungsaufgaben

Aufgabe Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 Referenznummer erstellen

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 * Aufgabe 10.5 ändern

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 Referenznummer erstellen

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 * Referenznummer erstellen

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 Referenznummer erstellen

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 * Referenznummer erstellen

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 Referenznummer erstellen

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)Referenznummer erstellen

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)Aufgabe 10.12 ändern

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)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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