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

Übungsaufgaben

Aufgabe

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

$p\rightarrow q,\,\neg p\rightarrow q,\,p\rightarrow \neg q,\,\neg p\rightarrow \neg q,\,r\rightarrow q,\,{\left(r\rightarrow q\right)}\rightarrow \neg p,\,{\left(s\rightarrow p\right)}\rightarrow {\left(r\rightarrow \neg q\right)},\,{\left(\neg q\rightarrow \neg p\right)}\rightarrow 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 die folgenden Regeln für die Ableitungsbeziehung (dabei seien $\alpha ,\beta ,\gamma ,\alpha _{i}$ Aussagen).

1. Konjunktionsregel: ${}\Gamma \vdash \alpha \wedge \beta$ genau dann, wenn ${}\Gamma \vdash \alpha$ und ${}\Gamma \vdash \beta$.
2. Kettenschlussregel: Wenn ${}\Gamma \vdash \alpha \rightarrow \beta$ und ${}\Gamma \vdash \beta \rightarrow \gamma$, dann auch ${}\Gamma \vdash \alpha \rightarrow \gamma$.
3. Modus ponens: Wenn ${}\Gamma \vdash \alpha$ und ${}\Gamma \vdash \alpha \rightarrow \beta$, dann ist auch ${}\Gamma \vdash \beta$.
4. Wenn ${}\Gamma \vdash \alpha$, so auch ${}\Gamma \vdash \beta \rightarrow \alpha$.
5. Wenn ${}\Gamma \vdash \alpha _{1},\ldots ,\Gamma \vdash \alpha _{n}$ und ${}\Gamma \vdash \alpha _{1}\wedge \ldots \wedge \alpha _{n}\rightarrow \beta$, dann auch ${}\Gamma \vdash \beta$.
6. Widerspruchsregel: Wenn ${}\Gamma \vdash \alpha$ und ${}\Gamma \vdash \neg \alpha$, dann auch ${}\Gamma \vdash \beta$.
7. Fallunterscheidungsregel: Wenn ${}\Gamma \vdash \alpha \rightarrow \beta$ und ${}\Gamma \vdash \neg \alpha \rightarrow \beta$, dann auch ${}\Gamma \vdash \beta$.

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 \}\vdash \beta$

zu

$\Gamma \vdash \alpha \rightarrow \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 \not \vdash \alpha .$

Zeige, dass dann

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

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 \vdash \alpha$ die Folgerungsbeziehung ${}\Gamma \vDash \alpha$ impliziert.

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\rightarrow r,$

3. $\neg p\wedge q\rightarrow r,$

4. $\neg p\wedge \neg q\rightarrow \neg r,$

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

6. $p\rightarrow (q\rightarrow \neg r),$

7. $\neg q.$

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 \vdash \alpha$. Zeige, dass es dann auch eine endliche Teilmenge ${}\Delta \subseteq \Gamma$ mit ${}\Delta \vdash \alpha$ gibt.

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^{\vDash }$ maximal widerspruchsfrei ist.

Aufgabe

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

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,\neg q\rightarrow r\}\subseteq L^{V}$ ($p,q,r$ seien Aussagenvariablen). Welche der folgenden Aussagen lassen sich aus ${}\Gamma$ ableiten?

$p\rightarrow q,\,\neg q\rightarrow p,\,\neg p\rightarrow r,\,\neg q\rightarrow r\wedge p,\,\neg r\rightarrow q,\,r\rightarrow {\left(q\rightarrow \neg p\right)}.$

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 \vdash \beta$ und ${}\Gamma \vdash \neg \beta$.
3. Es ist ${}\Gamma ^{\vdash }=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\}\vdash \alpha .$

Zeige, dass bereits

$\vdash \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\})^{\vdash }$ als auch ${}(\Gamma \cup \{\neg p\})^{\vdash }$ maximal widerspruchsfrei ist.