Kurs:Einführung in die mathematische Logik (Osnabrück 2016)/Arbeitsblatt 24

Übungsaufgaben

Aufgabe

Überprüfe, um die folgenden Wörter korrekt gebildete (einschließlich Klammerung) modallogische Ausdrücke sind.

1. ${}\Box ((p)\wedge (q))$,
2. ${}(p)\rightarrow \Box (q)$,
3. ${}(p)\rightarrow (\Box (q))$,
4. ${}(\Diamond (p))\rightarrow ((\Box (q))\rightarrow (r))$.

Aufgabe

Zeige, dass das ${}K$- Axiom äquivalent zu

$\vdash \Diamond \alpha \rightarrow (\Diamond \neg \beta \vee \Diamond (\alpha \wedge \beta ))$

ist.

Aufgabe

Formuliere die in Bemerkung 23.7 aufgeführten Eigenschaften für das Ableitungsprädikat in der Sprache der Modallogik.

Aufgabe *

Zeige, dass im ${}K$- System der Ausdruck

$\Box (\alpha \rightarrow \beta )\rightarrow (\Diamond \alpha \rightarrow \Diamond \beta )$

ableitbar ist.

Aufgabe

Wir betrachten eine formale Modallogik, die durch das Axiomenschema

$\vdash \Box \alpha \leftrightarrow \neg \alpha$

gegeben sei.

1. Erfüllt diese Modallogik das Axiomenschema K?
2. Erfüllt diese Modallogik die Nezessisierungsregel?
3. Erfüllt diese Modallogik das Ideologieaxiom?

Aufgabe

Es sei ${}p_{i}$ ${}i\in I$, eine Familie von Aussagenvariablen und sei ${}L$ die zugehörige modallogische Sprache. Es sei ${}S$ ein prädikatenlogisches Symbolalphabet, das unter anderem Konstanten ${}c_{i}$, ${}i\in I$, und eine fixierte Variable ${}x$ enthalte.

1. Definiere eine natürliche injektive Abbildung

   $\Psi \colon L\longrightarrow L^{S},$

   bei der ${}p_{i}$ auf ${}x=c_{i}$ und ${}\Box \alpha$ auf ${}\forall x\Psi (\alpha )$ abgebildet wird.

2. Was ist ${}\Psi (\Diamond \alpha )$?
3. Zeige, dass zu jeder in der ${}K$- Modallogik ableitbaren modallogischen Aussage ${}\alpha$ auch ${}\Psi (\alpha )$ im Prädikatenkalkül ableitbar ist.

Aufgabe

1. Zeige, dass in einer ${}K$- Modallogik das Axiomenschema

   $\Diamond (\alpha \wedge \beta )\rightarrow \Diamond \alpha \wedge \Diamond \beta$

   gilt.

2. Zeige, dass in einer ${}K$-Modallogik das Axiomenschema

   $\Diamond \alpha \wedge \Diamond \beta \rightarrow \Diamond (\alpha \wedge \beta )$

   nicht gelten muss.

Aufgabe

1. Zeige, dass in einer ${}K$- Modallogik das Axiomenschema

   $\Diamond \alpha \vee \Diamond \beta \rightarrow \Diamond (\alpha \vee \beta )$

   gilt.

2. Zeige, dass in einer ${}K$-Modallogik das Axiomenschema

   $\Diamond (\alpha \vee \beta )\rightarrow \Diamond \alpha \vee \Diamond \beta$

   nicht gelten muss.

Zur folgenden Aufgabe vergleiche auch Aufgabe 11.21.

Aufgabe

Zeige, dass in einer ${}K$- Modallogik das Axiomenschema

$\Diamond (\alpha \rightarrow \beta )\rightarrow (\Diamond \alpha \rightarrow \Diamond \beta )$

nicht gelten muss.

Aufgabe *

Es sei ${}\Gamma$ eine arithmetische Ausdrucksmenge und ${}\alpha$ ein einstelliges Prädikat mit

$\Gamma \vdash \alpha (n)$

für alle ${}n\in \mathbb {N}$. Zeige, dass es einen Satz ${}q$ mit

$\Gamma \vdash \alpha (GN(q))\leftrightarrow q$

gibt.

Aufgabe

Es sei ${}\Gamma$ eine arithmetische Ausdrucksmenge und ${}\alpha$ ein einstelliges Prädikat mit

$\Gamma \vdash \neg \alpha (n)$

für alle ${}n\in \mathbb {N}$. Zeige, dass es einen Satz ${}q$ mit

$\Gamma \vdash \alpha (GN(q))\leftrightarrow q$

gibt.

Aufgabe

Wir setzen

${}\alpha (x):=\exists y{\left(x=y+y\right)}\,$

und es sei die Gödelisierung mit Primzahlen vorausgesetzt. Zeige (ohne den Fixpunktsatz zu verwenden), dass es einen Satz ${}q\in L_{0}^{\rm {Ar}}$ mit

$PA\vdash \alpha (GN(q))\leftrightarrow q$

gibt.

Aufgabe

Es sei ${}k$ eine fixierte positive natürliche Zahl und es sei

${}\alpha (x):=\exists y{\left(x=ky\right)}\,,$

wobei ${}ky$ als die ${}k$-fache Addition von ${}y$ mit sich selbst realisiert werde. Es sei die Gödelisierung mit Primzahlen vorausgesetzt. Zeige (ohne den Fixpunktsatz zu verwenden), dass es einen Satz ${}q\in L_{0}^{\rm {Ar}}$ mit

$PA\vdash \alpha (GN(q))\leftrightarrow q$

gibt.

Aufgaben zum Abgeben

Aufgabe (2 Punkte)

Überprüfe, um die folgenden Wörter korrekt gebildete (einschließlich Klammerung) modallogische Ausdrücke sind.

1. ${}\Box ((p)\wedge (q)$,
2. ${}(p)\rightarrow \Diamond ((q)\vee (r))$,
3. ${}(\Box (\Box ((p))))\rightarrow (\Box (q))$,
4. ${}((\Diamond (p))\rightarrow ((\Box (q))\rightarrow (r)))$.

Aufgabe (2 Punkte)

Zeige, dass in einer ${}K$- Modallogik

$\vdash \Diamond \neg \neg \alpha \leftrightarrow \neg \neg \Diamond \alpha$

ableitbar ist.

Aufgabe (2 Punkte)

Zeige, dass die ${}K$- Modallogik widerspruchsfrei ist.

Aufgabe (4 (2+2) Punkte)

Es sei ${}\Gamma$ eine arithmetische Ausdrucksmenge und ${}\alpha$ ein einstelliges Prädikat.

1. Es gelte

   $\Gamma \vdash \alpha (n)$

   für endlich viele ${}n\in \mathbb {N}$ und für alle übrigen natürlichen Zahlen gelte

   $\Gamma \vdash \neg \alpha (n).$

   Zeige, dass es einen Satz ${}q$ mit

   $\Gamma \vdash \alpha (GN(q))\leftrightarrow q$

   gibt.

2. Es gelte

   $\Gamma \vdash \neg \alpha (n)$

   für endlich viele ${}n\in \mathbb {N}$ und für alle übrigen natürlichen Zahlen gelte

   $\Gamma \vdash \alpha (n).$

   Zeige, dass es einen Satz ${}q$ mit

   $\Gamma \vdash \alpha (GN(q))\leftrightarrow q$

   gibt.