Kurs:Einführung in die mathematische Logik (Osnabrück 2021)/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 \vdash \alpha$. Zeige, dass es dann auch eine endliche Teilmenge ${}\Delta \subseteq \Gamma$ mit ${}\Delta \vdash \alpha$ gibt.

Aufgabe

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

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

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

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 ${}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 _{1}=\{p\wedge q\rightarrow r\}$ und ${}\Gamma _{2}=\{p\rightarrow (q\rightarrow r)\}$. Zeige

${}\Gamma _{1}^{\vdash }=\Gamma _{2}^{\vdash }\,.$

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 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}\vdash \alpha$ und ${}\Gamma _{2}\vdash \beta$. Zeige ${}\Gamma _{1}\cup \Gamma _{2}\vdash \alpha \wedge \beta$.
2. Es gelte ${}\Gamma _{1}\vdash \alpha$ und ${}\Gamma _{2}\vdash \alpha$. Folgt daraus ${}\Gamma _{1}\cap \Gamma _{2}\vdash \alpha$?

Aufgabe *

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

${}\Gamma =\{\alpha _{1},\alpha _{2},\ldots ,\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 \vdash \alpha$ die Folgerungsbeziehung ${}\Gamma \vDash \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\vDash \Gamma$ und ${}I\vDash \neg \alpha$. Zeige ${}\Gamma \not \vdash \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^{\vDash }$ 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 ${}\neg p$ enthalte. Zeige, dass ${}\Delta ^{\vdash }$ 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,\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.