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

Übungsaufgaben

Aufgabe

Beweise mittels Wahrheitstabellen, dass die folgenden Aussagen Tautologien sind.

1. ${}(\alpha \wedge \alpha )\leftrightarrow \alpha$.
2. ${}\alpha \wedge \beta \rightarrow \alpha$.
3. ${}\alpha \rightarrow (\beta \rightarrow \alpha )$.
4. ${}(\alpha \rightarrow (\beta \rightarrow \gamma ))\rightarrow ((\alpha \rightarrow \beta )\rightarrow (\alpha \rightarrow \gamma ))$.
5. ${}(\alpha \rightarrow \beta )\leftrightarrow (\neg \alpha \vee \beta )$.

Aufgabe

Man beweise mittels Wahrheitstabellen die Regeln von de Morgan, nämlich dass

$\neg (\beta \vee \gamma )\leftrightarrow (\neg \beta \wedge \neg \gamma )$

und

$\neg (\beta \wedge \gamma )\leftrightarrow (\neg \beta \vee \neg \gamma )$

Tautologien sind.

Aufgabe

Es seien ${}p_{1},\ldots ,p_{n}$ Aussagenvariablen und ${}\beta _{1},\ldots ,\beta _{n}$ Aussagen. Zeige, dass man, wenn man in einer allgemeingültigen Aussage ${}\alpha$ jedes Vorkommen von ${}p_{i}$ durch ${}\beta _{i}$ ersetzt, wieder eine allgemeingültige Aussage erhält. Zeige, dass die Umkehrung davon nicht gilt.

Aufgabe

Zeige, dass eine Aussage ${}\alpha \in L^{V}$ genau dann eine Kontradiktion ist, wenn ${}\neg \alpha$ eine Tautologie ist.

Aufgabe

Man gebe möglichst viele Beispiele für aussagenlogische Kontradiktionen an.

Aufgabe

Skizziere ein Entscheidungsverfahren, das für eine gegebene Aussage ${}\alpha \in L^{V}$ entscheidet, ob es sich um eine aussagenlogische Tautologie handelt oder nicht.

Aufgabe *

Professor Knopfloch kommt gelegentlich mit verschiedenen Socken und/oder mit verschiedenen Schuhen in die Universität. Er legt folgende Definitionen fest.

1. Ein Tag heißt sockenzerstreut, wenn er verschiedene Socken anhat.
2. Ein Tag heißt schuhzerstreut, wenn er verschiedene Schuhe anhat.
3. Ein Tag heißt zerstreut, wenn er sockenzerstreut oder schuhzerstreut ist.
4. Ein Tag heißt total zerstreut, wenn er sowohl sockenzerstreut als auch schuhzerstreut ist.

a) Vom Jahr ${}2015$ weiß man, dass ${}17$ Tage sockenzerstreut und ${}11$ Tage schuhzerstreut waren. Wie viele Tage waren in diesem Jahr maximal zerstreut und wie viele Tage waren minimal zerstreut? Wie viele Tage waren in diesem Jahr maximal total zerstreut und wie viele Tage waren minimal total zerstreut?

b) Vom Jahr ${}2013$ weiß man, dass ${}270$ Tage sockenzerstreut und ${}120$ Tage schuhzerstreut waren. Wie viele Tage waren in diesem Jahr maximal zerstreut und wie viele Tage waren minimal total zerstreut?

c) Erstelle eine Formel, die die Anzahl der sockenzerstreuten, der schuhzerstreuten, der zerstreuten und der total zerstreuten Tage in einem Jahr miteinander in Verbindung bringt.

Die folgenden Aufgaben verwenden den Begriff einer Äquivalenzrelation. Dieser ist für viele Konstruktionen in der Mathematik und in der mathematischen Logik entscheidend. Siehe Äquivalenzrelation/Einführung/Textabschnitt.

Eine Äquivalenzrelation auf einer Menge ${}M$ ist eine Relation ${}R\subseteq M\times M$, die die folgenden drei Eigenschaften besitzt (für beliebige ${}x,y,z\in M$).

1. Es ist ${}x\sim x$ (reflexiv).
2. Aus ${}x\sim y$ folgt ${}y\sim x$ (symmetrisch).
3. Aus ${}x\sim y$ und ${}y\sim z$ folgt ${}x\sim z$ (transitiv).

Dabei bedeutet ${}x\sim y$, dass das Paar ${}(x,y)$ zu ${}R$ gehört.

Aufgabe

Auf den ganzen Zahlen ${}\mathbb {Z}$ lebe eine Kolonie von Flöhen, und jeder Flohsprung geht fünf Einheiten weit (in beide Richtungen). Wie viele Flohpopulationen gibt es? Wie kann man einfach charakterisieren, ob zwei Flöhe zur gleichen Population gehören oder nicht?

Aufgabe

Es sei ${}B$ ein Blatt Papier (oder ein Taschentuch). Man versuche, sich die folgenden Äquivalenzrelationen auf ${}B$ und die zugehörige Identifizierungsabbildungen vorzustellen (möglichst geometrisch).

1. Die vier Eckpunkte sind untereinander äquivalent, ansonsten sind die Punkte nur zu sich selbst äquivalent.
2. Alle Randpunkte sind untereinander äquivalent, ansonsten sind die Punkte nur zu sich selbst äquivalent.
3. Jeder Punkt des linken Randes ist äquivalent zu seinem horizontal gegenüber liegenden Punkt am rechten Rand, ansonsten sind die Punkte nur zu sich selbst äquivalent.
4. Jeder Punkt des linken Randes ist äquivalent zu seinem horizontal gegenüber liegenden Punkt am rechten Rand und jeder Punkt des oberen Randes ist äquivalent zu seinem vertikal gegenüber liegenden Punkt, ansonsten sind die Punkte nur zu sich selbst äquivalent.
5. Jeder Punkt des Randes ist äquivalent zu seinem punktsymmetrisch (bezüglich des Mittelpunktes des Blattes) gegenüber liegenden Punkt, ansonsten sind die Punkte nur zu sich selbst äquivalent.
6. Es sei ${}K$ ein Kreis (d.h. eine Kreislinie) auf dem Blatt. Alle Kreispunkte seien untereinander äquivalent, ansonsten sind die Punkte nur zu sich selbst äquivalent.
7. Es gebe zwei Punkte ${}P\neq Q$, die untereinander äquivalent seien, ansonsten sind die Punkte nur zu sich selbst äquivalent.
8. Es sei ${}H$ die horizontale Halbierungsgerade des Blattes. Zwei Punkte sind genau dann äquivalent, wenn sie achsensymmetrisch zu ${}H$ sind.

Aufgabe

Zeige, dass die Beziehung

$\alpha \sim \beta ,{\text{ falls }}(\alpha )\leftrightarrow (\beta ){\text{ allgemeingültig ist}},$

eine Äquivalenzrelation auf ${}L^{V}$ definiert. Zeige, dass sowohl alle Tautologien als auch alle Kontradiktionen eine Äquivalenzklasse bilden. Wie viele Äquivalenzklassen besitzt diese Äquivalenzrelation, falls ${}V$ ${}n$ Elemente besitzt?

Aufgabe

Es sei ${}\sim$ die in Aufgabe 3.10 diskutierte Äquivalenzrelation auf ${}L^{V}$. Zeige, dass jede Äquivalenzklasse ${}[\alpha ]$ einen Repräsentanten in disjunktiver Normalform besitzt.

Aufgabe

Es sei ${}\sim$ die in Aufgabe 3.10 diskutierte Äquivalenzrelation auf ${}L^{V}$ und sei ${}Q$ die zugehörige Quotientenmenge. Es sei ${}\lambda$ eine Wahrheitsbelegung auf ${}V$. Zeige, dass dies eine wohldefinierte Abbildung auf ${}Q$ induziert.

Aufgabe

Es sei ${}V$ eine Menge von Aussagenvariablen und ${}\alpha$ eine Aussage in der zugehörigen formalen Sprache ${}L^{V}$. Es sei

$\varphi \colon V\longrightarrow V$

eine Abbildung und es sei ${}\varphi (\alpha )$ diejenige Aussage, die entsteht, wenn man in ${}\alpha$ jede Aussagenvariable ${}p$ durch ${}\varphi (p)$ ersetzt. Zeige die folgenden Aussagen.

1. Wenn ${}\alpha$ eine Tautologie ist, so ist auch ${}\varphi (\alpha )$ eine Tautologie.
2. Wenn ${}\varphi$ injektiv ist, so ist ${}\alpha$ genau dann eine Tautologie, wenn dies für ${}\varphi (\alpha )$ gilt.
3. ${}\varphi (\alpha )$ kann eine Tautologie sein, auch wenn ${}\alpha$ keine Tautologie ist.
4. Die Aussagen gelten ebenso, wenn man überall Tautologie durch Kontradiktion ersetzt.

Aufgabe

Interpretiere die Wahrheitstabellen zu den Junktoren ${}\neg ,\wedge ,\vee ,\rightarrow ,\leftrightarrow$ als Wertetabellen von Funktionen. Was sind die Definitions-, die Werte- und die Bildmengen dieser Funktionen?

Aufgabe

Zeige, dass die axiomatisch fixierten syntaktischen Grundtautologien allgemeingültig sind

Aufgabe *

Beweise die aussagenlogische Tautologie

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

aus den aussagenlogischen Axiomen.

Aufgabe

Zeige das Assoziativgesetz für die Konjunktion, also

$\vdash {\left(\alpha \wedge \beta \right)}\wedge \gamma \rightarrow \alpha \wedge {\left(\beta \wedge \gamma \right)}.$

Aufgabe

Es seien ${}\alpha _{1},\ldots ,\alpha _{n}$ Ausdrücke und es seien ${}i_{1},\ldots ,i_{k}$ Elemente aus ${}\{1,\ldots ,n\}$. Zeige, dass

$\vdash \alpha _{1}\wedge \ldots \wedge \alpha _{n}\rightarrow \alpha _{i_{1}}\wedge \ldots \wedge \alpha _{i_{k}}$

gilt.

Aufgabe

Zeige, dass aus ${}\vdash \alpha _{1},\ldots ,\vdash \alpha _{n}$ und ${}\vdash \alpha _{1}\wedge \ldots \wedge \alpha _{n}\rightarrow \beta$ die Ableitbarkeit ${}\vdash \beta$ folgt.

Aufgabe *

Zeige, dass eine Regel der Form

Wenn ${}\vdash \alpha$, dann ${}\vdash \beta$ gelten kann, ohne dass ${}\vdash \alpha \rightarrow \beta$ gilt.

Aufgabe

Es seien ${}p_{1},\ldots ,p_{n}$ Aussagenvariablen und ${}\beta _{1},\ldots ,\beta _{n}$ Aussagen. Zeige, dass man, wenn man in einer syntaktischen Tautologie ${}\alpha$ jedes Vorkommen von ${}p_{i}$ durch ${}\beta _{i}$ ersetzt, wieder eine Tautologie erhält.

Aufgabe

Es sei ${}\alpha$ eine ableitbare Tautologie. Zeige, dass es eine Ableitung für ${}\alpha$ gibt, bei der in jedem Ableitungsschritt nur Aussagenvariablen auftreten, die in ${}\alpha$ vorkommen.

Aufgaben zum Abgeben

Aufgabe (3 Punkte)

Zeige, dass in einer aussagenlogischen Tautologie (und ebenso in einer aussagenlogischen Kontradiktion) mindestens eine Aussagenvariable mehrfach vorkommen muss.

Aufgabe (2 Punkte)

Es sei ${}\Gamma \subseteq L^{V}$ eine Aussagenmenge derart, dass in keiner Aussage ${}\alpha \in \Gamma$ das Negationszeichen ${}\neg$ vorkommt. Zeige, dass dann die Wahrheitsbelegung, die jeder Aussagenvariablen den Wert ${}1$ zuweist, zu einer Interpretation ${}I$ mit ${}\Gamma \subseteq I^{\vDash }$ führt.

Aufgabe (2 Punkte)

Zeige, dass die Aussage

$(\alpha \rightarrow \beta )\wedge (\beta \rightarrow \gamma )\wedge (\neg \alpha \rightarrow \beta )\rightarrow \gamma$

allgemeingültig ist.

Aufgabe (3 Punkte)

Zeige

$\vdash (\alpha \rightarrow \beta )\wedge (\beta \rightarrow \gamma )\wedge (\neg \alpha \rightarrow \beta )\rightarrow \gamma .$

Aufgabe (2 Punkte)

Begründe die folgende Ableitungsregel: Aus ${}\vdash \alpha$ und ${}\vdash \alpha \wedge \beta \rightarrow \gamma$ folgt ${}\vdash \beta \rightarrow \gamma$.

Aufgabe (3 Punkte)

Zeige, dass folgende rekursive Definition zur gleichen Menge an syntaktischen Tautologien führt:

Die Grundtautologien werden nur mit Aussagenvariablen formuliert.

Neben dem Modus ponens gibt es die Ersetzungsregel, d.h. wenn ${}\vdash \alpha$, so ist auch ${}\vdash \alpha '$, wobei ${}\alpha '$ ein Ausdruck ist, der entsteht, wenn man in ${}\alpha$ Aussagenvariablen durch beliebige Aussagen ersetzt.

Zeige, dass ohne diese Ersetzungsregel nicht die gleiche Menge beschrieben wird.

Fußnoten