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

Übungsaufgaben

Aufgabe

Es sei  $\Gamma \subseteq L^V$  eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge $V$ und $\alpha \in L^V$. Es gelte $\Gamma ⊢\alpha$. Zeige, dass es dann auch eine endliche Teilmenge  $\Delta \subseteq \Gamma$  mit $\Delta ⊢\alpha$ gibt.

Aufgabe

Es sei $\Gamma \subseteq L^V$ eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge $V$. Es gelte $p\to q\in \Gamma$ und $q\to r\in \Gamma$. Folgt daraus $p\to r\in \Gamma$?

Aufgabe

Es sei  $\Gamma =\{p,\mathrm{\neg }q,r\to s\}\subseteq L^V$  ($p,q,r,s$ seien Aussagenvariablen). Welche der folgenden Aussagen lassen sich aus $\Gamma$ ableiten?

$p\to q,\mathrm{\neg }p\to q,p\to \mathrm{\neg }q,\mathrm{\neg }p\to \mathrm{\neg }q,r\to q,(r\to q)\to \mathrm{\neg }p,(s\to p)\to (r\to \mathrm{\neg }q),(\mathrm{\neg }q\to \mathrm{\neg }p)\to s.$

Aufgabe

Zeige, dass man aus $\Gamma =\{p\}$ unendlich viele Aussagen ableiten kann, die keine Tautologien sind.

Aufgabe *

Es sei  $\Gamma \subseteq L^V$  eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge $V$. Zeige

${\Gamma }^{⊢}={\left({\Gamma }^{⊢}\right)}^{⊢}.$

Aufgabe

Es sei  $\Gamma \subseteq L^V$  eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge $V$. Zeige die folgenden Regeln für die Ableitungsbeziehung (dabei seien $\alpha ,\beta ,\gamma ,{\alpha }_i$ Aussagen).

1. Konjunktionsregel: $\Gamma ⊢\alpha \wedge \beta$ genau dann, wenn $\Gamma ⊢\alpha$ und $\Gamma ⊢\beta$.
2. Kettenschlussregel: Wenn $\Gamma ⊢\alpha \to \beta$ und $\Gamma ⊢\beta \to \gamma$, dann auch $\Gamma ⊢\alpha \to \gamma$.
3. Modus ponens: Wenn $\Gamma ⊢\alpha$ und $\Gamma ⊢\alpha \to \beta$, dann ist auch $\Gamma ⊢\beta$.
4. Wenn $\Gamma ⊢\alpha$, so auch $\Gamma ⊢\beta \to \alpha$.
5. Wenn $\Gamma ⊢{\alpha }_1,\dots ,\Gamma ⊢{\alpha }_n$ und $\Gamma ⊢{\alpha }_1\wedge \dots \wedge {\alpha }_n\to \beta$, dann auch $\Gamma ⊢\beta$.
6. Widerspruchsregel: Wenn $\Gamma ⊢\alpha$ und $\Gamma ⊢\mathrm{\neg }\alpha$, dann auch $\Gamma ⊢\beta$.
7. Fallunterscheidungsregel: Wenn $\Gamma ⊢\alpha \to \beta$ und $\Gamma ⊢\mathrm{\neg }\alpha \to \beta$, dann auch $\Gamma ⊢\beta$.

Aufgabe

Es sei $V=\{p,q,r\}$ eine Aussagenvariablenmenge. Welche der folgenden Aussagen aus $L^V$ lassen sich aus  $\Gamma =V$  ableiten?

1. $p,$

2. $p\wedge q\to r,$

3. $\mathrm{\neg }p\wedge q\to r,$

4. $\mathrm{\neg }p\wedge \mathrm{\neg }q\to \mathrm{\neg }r,$

5. $p\to (q\to r),$

6. $p\to (q\to \mathrm{\neg }r),$

7. $\mathrm{\neg }q.$

Aufgabe

Es sei  ${\Gamma }_1=\{p\wedge q\to r\}$  und  ${\Gamma }_2=\{p\to (q\to r)\}$.  Zeige

${\Gamma }_1^{⊢}={\Gamma }_2^{⊢}.$

Aufgabe *

Es sei $\Gamma \subseteq L^V$ eine Ausdrucksmenge in der Sprache der Aussagenlogik über einer Aussagenvariablenmenge $V$ und es seien $\alpha ,\beta \in L^V$. Zeige, dass

$\Gamma \cup \{\alpha \}⊢\beta$

zu

$\Gamma ⊢\alpha \to \beta$

äquivalent ist.

Aufgabe *

Es sei $\Gamma \subseteq L^V$ eine Ausdrucksmenge in der Sprache der Aussagenlogik über einer Aussagenvariablenmenge $V$ und es sei $\alpha \in L^V$. Es gelte

$\Gamma ⊬\alpha .$

Zeige, dass dann

$\Gamma \cup \{\mathrm{\neg }\alpha \}$

widerspruchsfrei ist.

Aufgabe

Es seien  ${\Gamma }_1,{\Gamma }_2\subseteq L^V$  Ausdrucksmengen in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge $V$ und seien $\alpha ,\beta \in L^V$.

1. Es gelte ${\Gamma }_1⊢\alpha$ und ${\Gamma }_2⊢\beta$. Zeige ${\Gamma }_1\cup {\Gamma }_2⊢\alpha \wedge \beta$.
2. Es gelte ${\Gamma }_1⊢\alpha$ und ${\Gamma }_2⊢\alpha$. Folgt daraus ${\Gamma }_1\cap {\Gamma }_2⊢\alpha$?

Aufgabe *

Es sei $n\in {\mathbb{N}}_{+}$. Man gebe ein Beispiel für eine aussagenlogische widersprüchliche Ausdrucksmenge

$\Gamma =\{{\alpha }_1,{\alpha }_2,\dots ,{\alpha }_n\}$

derart, dass jede echte Teilmenge davon widerspruchsfrei ist.

Aufgabe

Es sei  $\Gamma \subseteq L^V$  eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge $V$. Zeige, dass die Ableitungsbeziehung $\Gamma ⊢\alpha$ die Folgerungsbeziehung $\Gamma \models \alpha$ impliziert.

Aufgabe

Es sei  $\Gamma \subseteq L^V$  eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge $V$ und es sei $\alpha \in L^V$. Es gebe eine Interpretation $I$ mit $I\models \Gamma$ und $I\models \mathrm{\neg }\alpha$. Zeige $\Gamma ⊬\alpha$.

Aufgabe *

Es sei $L^V$ die Sprache der Aussagenlogik zu einer Aussagenvariablenmenge $V$ und es sei $\lambda$ eine Wahrheitsbelegung der Variablen mit zugehöriger Interpretation $I$. Zeige, dass $I^{\models }$ maximal widerspruchsfrei ist.

Aufgabe

Führe die Einzelheiten im Beweis zu Lemma 4.7 für die Implikation durch.

Aufgabe

Es sei  $\Delta \subseteq L^V$  eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge $V$, die zu jeder Aussagenvariablen $p\in V$ entweder $p$ oder $\mathrm{\neg }p$ enthalte. Zeige, dass ${\Delta }^{⊢}$ maximal widerspruchsfrei ist.

Aufgabe

Es sei $\Gamma \subseteq L^V$ eine widerspruchsfreie, aber nicht maximal widerspruchsfreie Aussagenmenge, die unter Ableitungen abgeschlossen sei. Zeige, dass $\Gamma$ nicht durch die Hinzunahme von endlich vielen Aussagen zu einer maximal widerspruchsfreien Aussagenmenge aufgefüllt werden kann.

Aufgaben zum Abgeben

Aufgabe (3 Punkte)

Es sei $\Gamma =\{p,\mathrm{\neg }q\to r\}\subseteq L^V$ ($p,q,r$ seien Aussagenvariablen). Welche der folgenden Aussagen lassen sich aus $\Gamma$ ableiten?

$p\to q,\mathrm{\neg }q\to p,\mathrm{\neg }p\to r,\mathrm{\neg }q\to r\wedge p,\mathrm{\neg }r\to q,r\to (q\to \mathrm{\neg }p).$

Aufgabe (3 Punkte)

Es sei $\Gamma \subseteq L^V$ eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge $V$. Zeige, dass folgende Aussagen äquivalent sind.

1. $\Gamma$ ist widersprüchlich.
2. Für jedes $\beta \in L^V$ ist $\Gamma ⊢\beta$ und $\Gamma ⊢\mathrm{\neg }\beta$.
3. Es ist ${\Gamma }^{⊢}=L^V$.

Aufgabe (4 Punkte)

Es sei $p$ eine Aussagenvariable und $\alpha \in L^V$ eine Aussage, in der die Variable $p$ nicht vorkommt. Es gelte

$\{p\}⊢\alpha .$

Zeige, dass bereits

$⊢\alpha$

gilt.

Aufgabe (3 Punkte)

Es sei $V$ eine Aussagenvariablenmenge. Konstruiere eine Ausdrucksmenge $\Gamma \subseteq L^V$, die abgeschlossen unter Ableitungen und nicht maximal widerspruchsfrei ist, die aber die Eigenschaft besitzt, dass für jede Aussagenvariable $p$ sowohl $(\Gamma \cup \{p\}{)}^{⊢}$ als auch $(\Gamma \cup \{\mathrm{\neg }p\}{)}^{⊢}$ maximal widerspruchsfrei ist.