Aussagenlogik/Ableitungsbeziehung/Widerspruchsfreiheit/Einführung/Textabschnitt

Definition

Es sei ${}\Gamma \subseteq L^{V}$ eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$ und sei ${}\alpha \in L^{V}$. Man sagt, dass ${}\alpha$ aus ${}\Gamma$ ableitbar ist, geschrieben

$\Gamma \vdash \alpha ,$

wenn es endlich viele Ausdrücke ${}\alpha _{1},\ldots ,\alpha _{n}\in \Gamma$ derart gibt, dass

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

gilt.

Die vorgegebene Ausdrucksmenge ${}\Gamma$ kann endlich oder unendlich sein, in der Ableitungsbeziehung kommen aber stets nur endlich viele Ausdrücke aus ${}\Gamma$ vor (eine „unendliche Konjunktion“ ist gar nicht definiert). Die Menge der aus einer gegebenen Ausdrucksmenge ${}\Gamma$ ableitbaren Ausdrücke bezeichnet man mit ${}\Gamma ^{\vdash }$, also

${}\Gamma ^{\vdash }={\left\{\alpha \in L^{V}\mid \Gamma \vdash \alpha \right\}}\,.$

Wegen ${}\vdash \alpha \rightarrow \alpha$ (nach Fakt) gilt ${}\Gamma \subseteq \Gamma ^{\vdash }$. Bei ${}\Gamma =\Gamma ^{\vdash }$ sagt man, dass ${}\Gamma$ abgeschlossenen unter Ableitungen ist. Die aus der leeren Menge ableitbaren Ausdrücke sind gerade die (syntaktischen) Tautologien.

Aus den (Grund- oder abgeleiteten) Tautologien ergeben sich direkt Regeln für die Ableitungsbeziehung.

Lemma

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

Dann gelten folgende 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$.

Beweis

Siehe Aufgabe.

$\Box$

Definition

Eine Ausdrucksmenge ${}\Gamma \subseteq L^{V}$ in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$ heißt widersprüchlich, wenn es einen Ausdruck ${}\alpha \in L^{V}$ mit ${}\Gamma \vdash \alpha$ und ${}\Gamma \vdash \neg \alpha$ gibt. Eine nicht widersprüchliche Ausdrucksmenge heißt widerspruchsfrei.

Nach Fakt  (6) kann man aus einer widersprüchlichen Aussagenmenge jede Aussage ableiten.