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. $◻((p)\wedge (q))$,
2. $(p)\to ◻(q)$,
3. $(p)\to (◻(q))$,
4. $(◊(p))\to ((◻(q))\to (r))$.

Aufgabe

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

$⊢◊\alpha \to (◊\mathrm{\neg }\beta \vee ◊(\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

$◻(\alpha \to \beta )\to (◊\alpha \to ◊\beta )$

ableitbar ist.

Aufgabe

Wir betrachten eine formale Modallogik, die durch das Axiomenschema

$⊢◻\alpha \leftrightarrow \mathrm{\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

   $\mathrm{\Psi }:L⟶L^S,$

   bei der $p_i$ auf $x=c_i$ und $◻\alpha$ auf $\mathrm{\forall }x\mathrm{\Psi }(\alpha )$ abgebildet wird.

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

Aufgabe

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

   $◊(\alpha \wedge \beta )\to ◊\alpha \wedge ◊\beta$

   gilt.

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

   $◊\alpha \wedge ◊\beta \to ◊(\alpha \wedge \beta )$

   nicht gelten muss.

Aufgabe

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

   $◊\alpha \vee ◊\beta \to ◊(\alpha \vee \beta )$

   gilt.

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

   $◊(\alpha \vee \beta )\to ◊\alpha \vee ◊\beta$

   nicht gelten muss.

Zur folgenden Aufgabe vergleiche auch Aufgabe 11.21.

Aufgabe

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

$◊(\alpha \to \beta )\to (◊\alpha \to ◊\beta )$

nicht gelten muss.

Aufgabe *

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

$\mathrm{\Gamma }⊢\alpha (n)$

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

$\mathrm{\Gamma }⊢\alpha (GN(q))\leftrightarrow q$

gibt.

Aufgabe

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

$\mathrm{\Gamma }⊢\mathrm{\neg }\alpha (n)$

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

$\mathrm{\Gamma }⊢\alpha (GN(q))\leftrightarrow q$

gibt.

Aufgabe

Wir setzen

$\alpha (x):=\mathrm{\exists }y(x=y+y)$

und es sei die Gödelisierung mit Primzahlen vorausgesetzt. Zeige (ohne den Fixpunktsatz zu verwenden), dass es einen Satz $q\in L_0^{\mathrm{A}\mathrm{r}}$ mit

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

gibt.

Aufgabe

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

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

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^{\mathrm{A}\mathrm{r}}$ mit

$PA⊢\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. $◻((p)\wedge (q)$,
2. $(p)\to ◊((q)\vee (r))$,
3. $(◻(◻((p))))\to (◻(q))$,
4. $((◊(p))\to ((◻(q))\to (r)))$.

Aufgabe (2 Punkte)

Zeige, dass in einer $K$-Modallogik

$⊢◊\mathrm{\neg }\mathrm{\neg }\alpha \leftrightarrow \mathrm{\neg }\mathrm{\neg }◊\alpha$

ableitbar ist.

Aufgabe (2 Punkte)

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

Aufgabe (4 (2+2) Punkte)

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

1. Es gelte

   $\mathrm{\Gamma }⊢\alpha (n)$

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

   $\mathrm{\Gamma }⊢\mathrm{\neg }\alpha (n).$

   Zeige, dass es einen Satz $q$ mit

   $\mathrm{\Gamma }⊢\alpha (GN(q))\leftrightarrow q$

   gibt.

2. Es gelte

   $\mathrm{\Gamma }⊢\mathrm{\neg }\alpha (n)$

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

   $\mathrm{\Gamma }⊢\alpha (n).$

   Zeige, dass es einen Satz $q$ mit

   $\mathrm{\Gamma }⊢\alpha (GN(q))\leftrightarrow q$

   gibt.