Kurs:Einführung in die mathematische Logik (Osnabrück 2016)/Vorlesung 3/latex
\setcounter{section}{3}
\zwischenueberschrift{Tautologien}
In der letzten Vorlesung haben wir erklärt, wie man ausgehend von einer Wahrheitsbelegung $\lambda$ der Aussagenvariablen zu einer Interpretation
\mavergleichskette
{\vergleichskette
{I
}
{ = }{I^\lambda
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
einer jeden Aussage
\mathl{\alpha \in L^V}{} kommt. Dabei hängt der Wahrheitsgehalt im Allgemeinen von $\lambda$ und von $\alpha$ ab. Eine besondere Situation liegt vor, wenn der Wahrheitswert von $\alpha$ nicht von der Belegung abhängt, also der Aussage immanent ist.
\inputdefinition
{}
{
Ein Ausdruck
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {zu einer Menge von
\definitionsverweis {Aussagenvariablen}{}{}
$V$} {} {}
heißt
\definitionswort {allgemeingültig}{}
\zusatzklammer {oder eine semantische
\definitionswort {Tautologie}{,}} {} {}
wenn für jede
\definitionsverweis {Wahrheitsbelegung}{}{}
$\lambda$ die Beziehung
\mavergleichskettedisp
{\vergleichskette
{I^\lambda( \alpha )
}
{ =} { 1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gilt.
}
\inputbemerkung
{}
{
Den Wahrheitswert eines Ausdrucks
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
unter der Interpretation $I^\lambda$ zu einer Belegung $\lambda$ kann man übersichtlich berechnen, wenn man abhängig von den Variablenwerten
\zusatzklammer {für die in $\alpha$ auftretenden Variablen} {} {}
sukzessive die Werte der konstituierenden Bestandteile von $\alpha$ berechnet. Um festzustellen, ob eine Tautologie vorliegt, legt man eine \stichwort {Wahrheitstabelle} {} an, bei der die Zeilen durch die möglichen Kombinationen an
\mathl{0,1}{-}Werten der einzelnen
\zusatzklammer {in $\alpha$ vorkommenden} {} {}
Variablen gegeben sind. Am übersichtlichsten wird die Tabelle, wenn man sich bei der Zeilenreihenfolge an das Dualsystem hält. Bei $n$ Variablen gibt es
\zusatzklammer {neben der Kopfzeile} {} {}
$2^n$ Zeilen.
}
\inputbeispiel{}
{
Der Ausdruck
\zusatzklammer {wir verzichten hier und im Folgenden häufig auf Klammern} {} {}
\mavergleichskettedisp
{\vergleichskette
{ \varphi
}
{ =} {( \alpha \rightarrow \beta) \leftrightarrow ( \neg \beta \rightarrow \neg \alpha)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
genannt \stichwort {Kontraposition} {,} ist eine
\definitionsverweis {Tautologie}{}{}
\zusatzklammer {unabhängig davon, ob
\mathl{\alpha, \beta}{}
\definitionsverweis {Aussagenvariablen}{}{}
oder Aussagen bezeichnen} {} {.}
Um dies nachzuweisen, muss man den Wahrheitswert dieses Ausdruckes bei jeder
\definitionsverweis {Wahrheitsbelegung}{}{}
berechnen, was wir mit einer Wahrheitstabelle durchführen.
\wahrheitstabellezweifuenf{Kontraposition} {\zeileundsieben { $ \alpha $ } { $ \beta $ } {$ \alpha \rightarrow \beta $} {$ \neg \alpha $} {$ \neg \beta $} {$ \neg \beta \rightarrow \neg \alpha $} {$ (\alpha \rightarrow \beta) \leftrightarrow ( \neg \beta \rightarrow \neg \alpha) $} }
{\zeileundsieben {w} {w} { w} {f} {f} { w} { w} }
{\zeileundsieben {w} {f} {f} {f} {w} {f} {w} }
{\zeileundsieben {f} {w} {w} {w} {f} {w} {w} }
{\zeileundsieben {f} {f} {w} {w} {w} {w } {w } }
Dagegen ist der Ausdruck
\mavergleichskettedisp
{\vergleichskette
{ \varphi
}
{ =} { { \left( \neg { \left( (p) \wedge (\neg (q) ) \right) } \right) } \rightarrow ( r )
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
keine Tautologie, da wir in
Beispiel 2.13
eine Wahrheitsbelegung mit dem Gesamtwert $f$ angegeben haben.
}
\inputdefinition
{}
{
Ein Ausdruck
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {zu einer Menge von
\definitionsverweis {Aussagenvariablen}{}{}
$V$} {} {}
heißt
\zusatzklammer {semantische} {} {}
\definitionswort {Kontradiktion}{}
\zusatzklammer {oder
\definitionswort {Widerspruch}{}} {} {,}
wenn für jede
\definitionsverweis {Wahrheitsbelegung}{}{}
$\lambda$ die Beziehung
\mavergleichskettedisp
{\vergleichskette
{ I( \alpha )
}
{ =} { 0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gilt.
}
\inputdefinition
{}
{
Es sei $V$ eine Menge von
\definitionsverweis {Aussagenvariablen}{}{}
und $L^V$ die zugehörige aussagenlogische Sprache. Eine Teilmenge
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt
\definitionswort {erfüllbar}{,}
wenn es eine
\definitionsverweis {Wahrheitsbelegung}{}{}
$\lambda$ mit zugehöriger Interpretation $I$ derart gibt, dass
\mavergleichskette
{\vergleichskette
{ I( \alpha )
}
{ = }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für alle
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ \Gamma
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt.
}
Diese Sprechweise verwendet man insbesondere für einen einzelnen Ausdruck
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ \Gamma^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
\inputfaktbeweis
{Aussagenlogik/Tautologie und Erfüllbarkeit/Fakt}
{Lemma}
{}
{
\faktsituation {Ein Ausdruck
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {zu einer Menge von
\definitionsverweis {Aussagenvariablen}{}{}
$V$} {} {}}
\faktfolgerung {ist genau dann eine
\zusatzklammer {semantische} {} {}
\definitionsverweis {Tautologie}{}{,}
wenn $\neg \alpha$ nicht
\definitionsverweis {erfüllbar}{}{}
ist.}
\faktzusatz {}
\faktzusatz {}
}
{
Wir beweisen die kontraponierte Aussage, dass $\alpha$ genau dann keine Tautologie ist, wenn $\neg \alpha$ erfüllbar ist. Dass keine Tautologie vorliegt, bedeutet, dass es eine
\definitionsverweis {Wahrheitsbelegung}{}{}
$\lambda$ derart gibt, dass
\mavergleichskettedisp
{\vergleichskette
{ I^\lambda (\alpha)
}
{ =} { 0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Dies bedeutet aber
\mavergleichskettedisp
{\vergleichskette
{ I^\lambda ( \neg \alpha)
}
{ =} {1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
was gerade die Erfüllbarkeit von $\neg \alpha$ besagt.
\zwischenueberschrift{Die Folgerungsbeziehung}
In gewissen Situationen interessiert man sich dafür, welche Ausdrücke aus einer bestimmten Menge von Ausdrücken, etwa einem Axiomensystem, gefolgert werden können.
\inputdefinition
{}
{
Es sei $V$ eine Menge von Variablen und $L^V$ die zugehörige aussagenlogische Sprache. Es sei
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{ L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Teilmenge und
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Man sagt, dass $\alpha$ aus $\Gamma$
\definitionswort {folgt}{,}
geschrieben
\mathl{\Gamma \vDash \alpha}{,} wenn für jede
\definitionsverweis {Interpretation}{}{}
$I$
\zusatzklammer {gegeben durch eine
\definitionsverweis {Wahrheitsbelegung}{}{}
$\lambda$} {} {}
mit
\mathl{I \vDash \Gamma}{} auch
\mathl{I \vDash \alpha}{} gilt.
}
Für die Menge aller Aussagen, die aus der Aussagenmenge $\Gamma$ folgt, schreiben wir
\mathl{\Gamma^\vDash}{.} Tautologien sind genau die aus der leeren Ausdrucksmenge
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ = }{\emptyset
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgerbaren Aussagen. Daher schreibt man für Tautologien auch $\vDash \alpha$.
\zwischenueberschrift{Ein Ableitungskalkül für die aussagenlogischen Tautologien}
Wir formulieren nun einen syntaktischen Ableitungskalkül für
\zusatzklammer {syntaktische} {} {}
Tautologien. Dieser generiert, ausgehend von gewissen axiomatisch fixierten Grundtautologien, rekursiv eine Menge von Aussagen, die, wie wir später sehen werden, mit der Menge der allgemeingültigen Sätzen
\zusatzklammer {semantische Tautologien} {} {}
übereinstimmt. Wir arbeiten allein mit den logischen Symbolen
\mathl{\neg, \wedge, \rightarrow}{,} d.h. wir verzichten auf $\vee$ und auf $\leftrightarrow$. Dies reduziert die Ausdrucksstärke der Sprache nicht, da man
\mathl{\alpha \leftrightarrow \beta}{} als Abkürzung für
\mathl{{ \left( \alpha \rightarrow \beta \right) } \wedge { \left( \beta \rightarrow \alpha \right) }}{} und
\mathl{\alpha \vee \beta}{} als Abkürzung für
\mathl{\neg \alpha \rightarrow \beta}{} einführen kann. Um Klammern zu sparen verwenden wir die Konvention, dass die Negation sich auf das folgende Zeichen bezieht und dass die Konjunktion stärker bindet als die Implikation. Man könnte auch die Implikation
\mathl{\alpha \rightarrow \beta}{} durch
\mathl{\neg { \left( \alpha \wedge \neg \beta \right) }}{} definieren und eliminieren, doch dann würden die Ausdrücke sehr unübersichtlich.
\inputaxiom
{}
{
Für eine Aussagenvariablenmenge $V$ und beliebige Ausdrücke
\mathl{\alpha, \beta, \gamma}{} legt man folgende
\zusatzklammer {syntaktische} {} {}
\definitionswortenp{Tautologien}{} axiomatisch fest.
\aufzaehlungsechs{
\mathdisp {\vdash \alpha \rightarrow (\beta \rightarrow \alpha)} { . }
}{
\mathdisp {\vdash (\alpha \rightarrow \beta) \wedge (\beta \rightarrow \gamma) \rightarrow (\alpha \rightarrow \gamma)} { . }
}{
\mathdisp {\vdash (\alpha \rightarrow \beta) \wedge ( \alpha \rightarrow \gamma) \rightarrow (\alpha \rightarrow \beta \wedge \gamma)} { . }
}{
\mathdisp {\vdash (\alpha \wedge \beta \rightarrow \gamma) \rightarrow (\alpha \rightarrow ( \beta \rightarrow \gamma))} { }
und
\mathdisp {\vdash (\alpha \rightarrow ( \beta \rightarrow \gamma)) \rightarrow (\alpha \wedge \beta \rightarrow \gamma)} { . }
}{
\mathdisp {\vdash \neg \alpha \wedge \alpha \rightarrow \beta} { . }
}{
\mathdisp {\vdash (\alpha \rightarrow \beta) \wedge (\neg \alpha \rightarrow \beta) \rightarrow \beta} { . }
}
}
Man spricht häufig auch genauer von \stichwort {Axiomenschemata} {,} da jedes Axiom bei unterschiedlichen Einsetzungen eine Vielzahl von Axiomen representiert. Das \stichwort {Kettenschlussaxiom} {} (2) besagt die \stichwort {Transitivität der Implikation} {,} Axiom (5) heißt \stichwort {Widerspruchsaxiom} {} und Axiom (6) heißt \stichwort {Fallunterscheidungsaxiom} {.} Diese Tautologien sind die axiomatisch fixierten Grundtautologien und fungieren als die Startglieder im rekursiven Aufbau der syntaktischen Tautologien. Um überhaupt aus diesen Axiomen weitere Tautologien generieren zu können, braucht man Ableitungsregeln. Davon gibt es lediglich eine.
\stichwort {Modus ponens} {}
Aus
\mathkor {} {\vdash \alpha} {und} {\vdash (\alpha) \rightarrow (\beta )} {}
folgt
\mathl{\vdash \beta}{.}
\inputdefinition
{}
{
Unter einer
\definitionswort {syntaktischen Tautologie}{}
versteht man einen Ausdruck
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\zusatzklammer {zu einer Aussagenvariablenmenge $V$} {} {,}
den man aus den
{{
Axiomlink
Grundtautologien|Axiomseitenname=
Aussagenlogik/Syntaktische Tautologien/Implikation, Negation, Konjunktion/Axiom
|Nr=
|SZ=
}}
rekursiv mittels
\definitionsverweis {Modus ponens}{}{}
erhalten kann.
}
\inputbemerkung
{}
{
Eine Durchsicht der
Grund\-tautologien
zeigt, dass es sich jeweils auch um
\definitionsverweis {semantische Tautologien}{}{}
handelt, siehe
Aufgabe 3.15.
Wenn ferner $\alpha$ und
\mathl{( \alpha) \rightarrow ( \beta )}{} semantische Tautologien sind, so ist auch $\beta$ eine semantische Tautologie. D.h. die semantischen Tautologien sind unter Modus ponens abgeschlossen. Dies bedeutet insgesamt, dass syntaktische Tautologien stets semantische Tautologien sind. Diese Eigenschaft nennt man auch die \stichwort {Korrektheit} {} des syntaktischen Kalküls, er leitet ausschließlich semantische Tautologien, also wahre Aussagen ab. Die umgekehrte Aussage, dass sich jede semantische Tautologie auch syntaktisch in dem angegebenen Kalkül ableiten lässt, nennt man die \stichwort {Vollständigkeit} {} des Kalküls.
}
\zwischenueberschrift{Weitere Tautologien und Regeln}
\inputfaktbeweis
{Aussagenlogik/Ableitungskalkül/Triviale Implikation/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktfolgerung {Es ist
\mathdisp {\vdash \alpha \rightarrow \alpha} { . }
}
\faktzusatz {}
\faktzusatz {}
}
{
Es ist
\mathdisp {\vdash { \left( \alpha \rightarrow { \left( \alpha \rightarrow \alpha \right) } \right) } \wedge { \left( \neg \alpha \rightarrow { \left( \alpha \rightarrow \alpha \right) } \right) } \rightarrow { \left( \alpha \rightarrow \alpha \right) }} { }
nach
Axiom 3.8 (6),
woraus sich nach
Axiom 3.8 (4)
mit Modus Pones auch
\mathdisp {\vdash { \left( \alpha \rightarrow { \left( \alpha \rightarrow \alpha \right) } \right) } \rightarrow { \left( { \left( \neg \alpha \rightarrow { \left( \alpha \rightarrow \alpha \right) } \right) } \rightarrow { \left( \alpha \rightarrow \alpha \right) } \right) }} { }
ergibt. Wegen
Axiom 3.8 (1)
ist
\mathdisp {\vdash \alpha \rightarrow { \left( \alpha \rightarrow \alpha \right) }} { }
und daher mit Modus ponens auch
\mathdisp {\vdash { \left( \neg \alpha \rightarrow { \left( \alpha \rightarrow \alpha \right) } \right) } \rightarrow { \left( \alpha \rightarrow \alpha \right) }} { . }
Wegen
Axiom 3.8 (5)
ist
\mathdisp {\vdash \neg \alpha \wedge \alpha \rightarrow \alpha} { }
und damit mit
Axiom 3.8 (4)
auch
\mathdisp {\vdash \neg \alpha \rightarrow { \left( \alpha \rightarrow \alpha \right) }} { , }
sodass sich
\mathdisp {\vdash \alpha \rightarrow \alpha} { }
ergibt.
\inputfaktbeweis
{Aussagenlogik/Ableitungskalkül/Konjunktion/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktfolgerung {Für
\mavergleichskette
{\vergleichskette
{ \alpha , \beta
}
{ \in }{ L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mathdisp {\vdash \alpha \wedge \beta \rightarrow \alpha} { }
und
\mathdisp {\vdash \alpha \wedge \beta \rightarrow \beta} { . }
}
\faktzusatz {}
\faktzusatz {}
}
{
Nach
Axiom 3.8 (4)
ist
\mathdisp {\vdash { \left( \alpha \rightarrow { \left( \beta \rightarrow \alpha \right) } \right) } \rightarrow { \left( \alpha \wedge \beta \rightarrow \alpha \right) }} { }
und wegen
Axiom 3.8 (1)
ist
\mathdisp {\vdash \alpha \rightarrow { \left( \beta \rightarrow \alpha \right) }} { , }
sodass mit Modus ponens auch
\mathdisp {\vdash \alpha \wedge \beta \rightarrow \alpha} { }
gilt. Für die andere Behauptung gehen wir von
Lemma 3.11
aus, was
\mathdisp {\vdash \beta \rightarrow \beta} { }
liefert. Wegen
Axiom 3.8 (1)
haben wir
\mathdisp {\vdash { \left( \beta \rightarrow \beta \right) } \rightarrow { \left( \alpha \rightarrow { \left( \beta \rightarrow \beta \right) } \right) }} { , }
also mit Modus ponens auch
\mathdisp {\vdash \alpha \rightarrow { \left( \beta \rightarrow \beta \right) }} { . }
Nach
Axiom 3.8 (4)
ist
\mathdisp {\vdash { \left( \alpha \rightarrow { \left( \beta \rightarrow \beta \right) } \right) } \rightarrow { \left( \alpha \wedge \beta \rightarrow \beta \right) }} { , }
woraus sich nach dem bisher Bewiesenen
\mathdisp {\alpha \wedge \beta \rightarrow \beta} { }
ergibt.
\inputbemerkung
{}
{
Die aussagenlogischen Axiome der Form
\mathl{\vdash \alpha \rightarrow \beta}{} führen zu entsprechenden Schlussregeln, d.h. Vorschriften, wie man aus
\zusatzklammer {schon etablierten} {} {}
syntaktischen Tautologien neue Tautologien erhält. Wir gehen unter diesem Gesichtspunkt die Axiome durch.
Aus
\mathl{\vdash \alpha}{} folgt
\mathl{\vdash \beta \rightarrow \alpha}{.}
Dies ergibt sich aus der Voraussetzung
\mathl{\vdash \alpha}{} aus
\mathl{\vdash \alpha \rightarrow ( \beta \rightarrow \alpha )}{} und dem Modus ponens.
Aus
\mathl{\vdash \alpha \wedge \beta}{} folgt
\mathl{\vdash \alpha}{}
\zusatzklammer {und ebenso \mathlk{\vdash \beta}{}} {} {.}
Dies ergibt sich aus
\mathl{\vdash \alpha \wedge \beta \rightarrow \alpha}{}
nach Lemma 3.12
und der Voraussetzung
\mathl{\vdash \alpha \wedge \beta}{} mittels Modus ponens. Umgekehrt gilt die sogenannte \stichwort {Konjunktionsregel} {,} d.h. aus
\mathkor {} {\vdash \alpha} {und} {\vdash \beta} {}
folgt auch
\mathl{\vdash \alpha \wedge \beta}{.} Dies ergibt sich aus
\mathdisp {\vdash \alpha \rightarrow ( \beta \rightarrow \alpha \wedge \beta )} { }
\zusatzklammer {was aus den Axiomen folgt, siehe
Aufgabe 3.16} {} {}
aus den Voraussetzungen durch eine zweifache Anwendung des Modus ponens.
Aus
\mathkor {} {\vdash \alpha \rightarrow \beta} {und} {\vdash \beta \rightarrow \gamma} {}
ergibt sich
\mathl{\vdash \alpha \rightarrow \gamma}{.} Diese Regel heißt \stichwort {Kettenschlussregel} {.} Nach der obigen abgeleiteten Konjunktionsregel folgt aus den Voraussetzungen direkt
\mathl{\vdash ( \alpha \rightarrow \beta ) \wedge (\beta \rightarrow \gamma )}{} und daraus und dem Kettenschlussaxiom mit dem Modus ponens
\mathl{\vdash \alpha \rightarrow \gamma}{.}
}
\inputfaktbeweis
{Aussagenlogik/Syntaktische Tautologien/Implikation, Negation, Konjunktion/Axiomatik/Kommutativität der Konjunktion/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktfolgerung {Es ist
\mathdisp {\vdash \alpha \wedge \beta \rightarrow \beta \wedge \alpha} { . }
}
\faktzusatz {}
\faktzusatz {}
}
{
Nach
Axiom 3.8 (3)
ist
\mathdisp {\vdash (( \alpha \wedge \beta ) \rightarrow \beta) \wedge ((\alpha\wedge \beta ) \rightarrow \alpha) \rightarrow ( \alpha \wedge \beta\rightarrow \beta \wedge \alpha )} { . }
Die beiden Bestandteile des Vordersatzes gelten nach
Lemma 3.12,
sodass auch ihre Konjunktion ableitbar ist. Daher ist auch der Nachsatz ableitbar.
{Aussagenlogik/Syntaktische Tautologien/Implikation, Negation, Konjunktion/Axiomatik/Assoziativität der Konjunktion/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktfolgerung {Es ist
\mathdisp {\vdash { \left( \alpha \wedge \beta \right) } \wedge \gamma \rightarrow \alpha \wedge { \left( \beta \wedge \gamma \right) }} { . }
}
\faktzusatz {}
\faktzusatz {}
{ Siehe Aufgabe 3.17. }
\inputfaktbeweis
{Aussagenlogik/Syntaktische Tautologien/Implikation, Negation, Konjunktion/Axiomatik/Konjugierte Implikation/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktfolgerung {\aufzaehlungzwei {
\mathdisp {\vdash ( \alpha \rightarrow \beta) \rightarrow (\alpha \wedge \gamma\rightarrow \beta)} { . }
} {
\mathdisp {\vdash (\alpha \rightarrow \beta) \wedge (\gamma \rightarrow \delta) \rightarrow (\alpha \wedge \gamma\rightarrow \beta \wedge \delta)} { . }
}}
\faktzusatz {}
\faktzusatz {}
}
{
\aufzaehlungzwei {\teilbeweis {}{}{}
{Nach
Axiom 3.8 (2)
ist
\mathdisp {\vdash { \left( \alpha \wedge \gamma \rightarrow \alpha \right) } \wedge { \left( \alpha \rightarrow \beta \right) } \rightarrow { \left( \alpha \wedge \gamma \rightarrow \beta \right) }} { }
und daher mit
Axiom 3.8 (4)
auch
\mathdisp {\vdash ( \alpha \wedge \gamma \rightarrow \alpha ) \rightarrow ((\alpha \rightarrow \beta) \rightarrow ( \alpha \wedge \gamma \rightarrow \beta))} { . }
Der Vordersatz ist nach
Lemma 3.12
ableitbar, also auch der Nachsatz.}
{}
} {\teilbeweis {}{}{}
{Nach Teil (1) ist
\mathdisp {\vdash (\alpha \rightarrow \beta) \rightarrow (\alpha \wedge \gamma \rightarrow \beta)} { }
und
\zusatzklammer {unter Verwendung von
Lemma 3.14
und
Aufgabe *****} {} {}
\mathdisp {\vdash (\gamma \rightarrow \delta) \rightarrow (\alpha \wedge \gamma \rightarrow \delta)} { . }
Daher gilt auch
\zusatzklammer {nach der Regelversion zu Teil (1)} {} {}
\mathdisp {\vdash (\alpha \rightarrow \beta) \wedge (\gamma \rightarrow \delta) \rightarrow (\alpha \wedge \gamma \rightarrow \beta)} { }
und
\mathdisp {\vdash (\alpha \rightarrow \beta) \wedge (\gamma \rightarrow \delta) \rightarrow (\alpha \wedge \gamma \rightarrow \delta)} { }
bzw. unter Verwendung von
Axiom 3.8 (4)
und der
Assoziativität der Konjunktion
\mathdisp {\vdash (\alpha \rightarrow \beta) \wedge (\gamma \rightarrow \delta) \wedge \alpha \wedge \gamma \rightarrow \beta} { }
und
\mathdisp {\vdash (\alpha \rightarrow \beta) \wedge (\gamma \rightarrow \delta) \wedge \alpha \wedge \gamma \rightarrow \delta} { . }
Nach
Axiom 3.8 (3)
ist mit der Abkürzung
\mathl{\varphi =(\alpha \rightarrow \beta) \wedge (\gamma \rightarrow \delta) \wedge \alpha \wedge \gamma}{}
\mathdisp {\vdash (\varphi \rightarrow \beta ) \wedge (\varphi \rightarrow \delta) \rightarrow (\varphi \rightarrow \beta \wedge \delta)} { . }
Da die beiden Teilaussagen im Vordersatz ableitbar sind, ist auch der Nachsatz ableitbar, was unter Verwendung von
Axiom 3.8 (4)
zur Behauptung umformulierbar ist.}
{}
}
Die folgende Aussage gibt eine \anfuehrung{interne Version}{} des Modus ponens, der ja nach Definition eine Schlussregel ist.
\inputfaktbeweis
{Aussagenlogik/Syntaktische Tautologien/Implikation, Negation, Konjunktion/Axiomatik/Modus ponens intern/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktfolgerung {Es ist
\mathdisp {\vdash \alpha \wedge (\alpha \rightarrow \beta) \rightarrow \beta} { . }
}
\faktzusatz {}
\faktzusatz {}
}
{
Nach
Axiom 3.8 (6)
ist
\mathdisp {\vdash (\alpha \rightarrow \beta) \wedge (\neg \alpha \rightarrow \beta) \rightarrow \beta} { , }
und
Axiom 3.8 (5)
kann man wegen
Axiom 3.8 (4)
zu
\mathdisp {\vdash \alpha \rightarrow ( \neg \alpha \rightarrow \beta)} { }
umformulieren. Daraus und aus
\zusatzklammer {Lemma 3.11} {} {}
\mathdisp {\vdash { \left( \alpha \rightarrow \beta \right) } \rightarrow { \left( \alpha \rightarrow \beta \right) }} { }
ergibt sich mit der Regelversion zu
Lemma 3.16 (2)
\mathdisp {\vdash \alpha \wedge { \left( \alpha \rightarrow \beta \right) } \rightarrow { \left( \neg \alpha \rightarrow \beta \right) } \wedge { \left( \alpha \rightarrow \beta \right) }} { }
und daraus durch den Kettenschluss die Behauptung.
\inputfaktbeweis
{Aussagenlogik/Syntaktische Tautologien/Implikation, Negation, Konjunktion/Axiomatik/Weitere Schlussregeln/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktvoraussetzung {\aufzaehlungzwei {Aus
\mathl{\vdash \alpha \rightarrow ( \beta \rightarrow \gamma)}{} und
\mathl{\vdash \gamma \rightarrow \delta}{} folgt
\mathl{\vdash \alpha \rightarrow (\beta \rightarrow \delta)}{.}
} {Aus
\mathl{\vdash \alpha}{} und
\mathl{\vdash \alpha \wedge \beta \rightarrow \gamma}{} ergibt sich
\mathl{\vdash \beta \rightarrow \gamma}{.}
}}
\faktfolgerung {}
\faktzusatz {}
\faktzusatz {}
}
{
\aufzaehlungzwei {\teilbeweis {}{}{}
{Sei
\mathdisp {\vdash \alpha \rightarrow (\beta \rightarrow \gamma)} { }
und
\mathdisp {\vdash \gamma \rightarrow \delta} { . }
Nach
Bemerkung 3.13
gilt auch
\mathdisp {\vdash \alpha \rightarrow ( \gamma \rightarrow \delta )} { }
und daraus ergibt sich mit
Axiom 3.8 (3),
der Konjunktionsregel und dem Modus ponens
\mathdisp {\vdash \alpha \rightarrow (\beta \rightarrow \gamma ) \wedge (\gamma \rightarrow \delta)} { . }
Mittels des Kettenschlusses ergibt sich daraus und aus Axiom 3.8 (2)
die Behauptung.}
{}
} {\teilbeweis {}{}{}
{Siehe
Aufgabe 3.27.}
{}
}
Die folgenden Tautologien machen wichtige Aussagen über das Negationszeichen. Die Tautologie (2) ist eine wichtige Variante der \stichwort {Widerspruchstautologie} {} und die in (5) und (6) ausgedrückte Äquivalenz heißt \stichwort {Kontraposition} {.}
\inputfaktbeweis
{Aussagenlogik/Syntaktische Tautologien/Implikation, Negation, Konjunktion/Axiomatik/Weitere Tautologien/Mit Negation/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktfolgerung {\aufzaehlungsechs{
\mathdisp {\vdash ( \neg \alpha \rightarrow \alpha) \rightarrow \alpha} { . }
}{
\mathdisp {\vdash ( \neg \beta \rightarrow \neg \alpha) \wedge (\neg \beta \rightarrow \alpha) \rightarrow \beta} { }
}{
\mathdisp {\vdash \alpha \rightarrow \neg \neg \alpha} { . }
}{
\mathdisp {\vdash \neg \neg \alpha \rightarrow \alpha} { . }
}{
\mathdisp {\vdash ( \alpha \rightarrow \beta ) \rightarrow ( \neg \beta \rightarrow \neg \alpha)} { . }
}{
\mathdisp {\vdash ( \neg \beta \rightarrow \neg \alpha) \rightarrow ( \alpha \rightarrow \beta )} { . }
}}
\faktzusatz {}
\faktzusatz {}
}
{
\aufzaehlungsechs{\teilbeweis {}{}{}
{Die Fallunterscheidungstautologie liefert
\mathdisp {\vdash ( \alpha \rightarrow \alpha) \wedge ( \neg \alpha \rightarrow \alpha) \rightarrow \alpha} { . }
Aus
\zusatzklammer {Lemma 3.11} {} {}
\mathdisp {\vdash \alpha \rightarrow \alpha} { }
ergibt sich daraus die Behauptung.}
{}
}{\teilbeweis {}{}{}
{Nach
Axiom 3.8 (3)
gilt
\mathdisp {\vdash ( \neg \beta \rightarrow \neg \alpha) \wedge (\neg \beta \rightarrow \alpha) \rightarrow (\neg \beta \rightarrow \neg \alpha \wedge \alpha)} { }
und nach
Axiom 3.8 (5)
gilt
\mathdisp {\vdash \neg \alpha\wedge \alpha \rightarrow \beta} { . }
Nach
Lemma 3.18 (1)
folgt
\mathdisp {\vdash ( \neg \beta \rightarrow \neg \alpha) \wedge (\neg \beta \rightarrow \alpha) \rightarrow (\neg \beta \rightarrow \beta )} { , }
woraus nach Teil (1) die Behauptung mit der Kettenschlussregel folgt.}
{}
}{\teilbeweis {}{}{}
{Nach
Axiom 3.8 (1)
ist
\mathdisp {\vdash \neg \neg \alpha \rightarrow ( \alpha \rightarrow \neg \neg \alpha)} { . }
Nach
Axiom 3.8 (5)
ist
\mathdisp {\vdash \neg \alpha \wedge \alpha \rightarrow \neg \neg \alpha} { , }
was wir mit
Axiom 3.8 (4)
zu
\mathdisp {\vdash \neg \alpha \rightarrow ( \alpha \rightarrow \neg \neg \alpha)} { , }
umformulieren können. Daraus ergibt sich
\mathdisp {\vdash \alpha \rightarrow \neg \neg \alpha} { }
mit der Fallunterscheidungsregel.}
{}
}{\teilbeweis {}{}{}
{Nach
Axiom 3.8 (1)
ist
\mathdisp {\vdash \alpha \rightarrow ( \neg \neg \alpha \rightarrow \alpha)} { . }
Nach
Axiom 3.8 (5)
ist
\mathdisp {\vdash \neg \alpha \wedge \neg \neg \alpha \rightarrow \alpha} { , }
was wir zu
\mathdisp {\vdash \neg \alpha \rightarrow (\neg \neg \alpha \rightarrow \alpha)} { , }
umformulieren können. Daraus ergibt sich
\mathdisp {\vdash \neg \neg \alpha \rightarrow \alpha} { }
mit der Fallunterscheidungsregel.}
{}
}{\teilbeweis {}{}{}
{Es ist nach
Axiom 3.8 (1)
\mathdisp {\vdash \neg \alpha \rightarrow (\neg \beta \rightarrow \neg \alpha)} { }
und damit auch
\mathdisp {\vdash \neg \alpha \rightarrow ((\alpha \rightarrow \beta ) \rightarrow (\neg \beta \rightarrow \neg \alpha))} { . }
Ferner ist nach einer Variante von
Axiom 3.8 (5)
\mathdisp {\vdash \beta \rightarrow (\neg \beta \rightarrow \neg \alpha)} { . }
Nach
Lemma 3.17
ist
\mathdisp {\vdash \alpha \rightarrow ((\alpha \rightarrow \beta ) \rightarrow \beta )} { , }
woraus sich
\mathdisp {\vdash \alpha \rightarrow ((\alpha \rightarrow \beta ) \rightarrow (\neg \beta \rightarrow \neg \alpha))} { }
ergibt. Mit der Fallunterscheidungsregel folgt die Behauptung.}
{}
}{\teilbeweis {}{}{}
{Dies folgt aus (3), (4) und (5).}
{}
}