Kurs:Einführung in die mathematische Logik (Osnabrück 2016)/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 ${}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 (4 Punkte)Aufgabe 10.10 ä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.10

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.

Fußnoten