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

Übungsaufgaben

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 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 $\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 zu einer Aussagenvariablenmenge $V$. Zeige, dass die Ableitungsbeziehung $\Gamma ⊢\alpha$ die Folgerungsbeziehung $\Gamma \models \alpha$ impliziert.

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 $\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.

Aufgabe

Bestimme zu jedem Ausdruck $\alpha \in L^V$ mit maximal acht Zeichen zur Aussagenvariablenmenge $V=\{p,q\}$, ob er bei der durch $\lambda (p)=1,\lambda (q)=0$ fetgelegten Interpretation wahr oder falsch ist.

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 (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.