Aussagenlogik/Variablenbelegung/Ableitbarkeit/Fakt/Beweis

Beweis

Wir führen Induktion über den Aufbau der Sprache ${}L^{\{p_{1},\ldots ,p_{n}\}}$. Bei

${}\alpha =p_{i}\,$

ergibt sich die Aussage aus Fakt. Bei

${}\alpha =\neg \beta \,$

ergibt sich die Aussage aus der Induktionsvoraussetzung und aus Fakt  (3). Es sei nun

${}\alpha =\beta _{1}\wedge \beta _{2}\,.$

Bei

$\vdash \gamma \rightarrow \beta _{1}\,\,{\text{ und }}\,\,\vdash \gamma \rightarrow \beta _{2}$

ergibt sich die Ableitung

$\vdash \gamma \rightarrow \beta _{1}\wedge \beta _{2}$

im Wesentlichen aus Axiom  (3). Bei

$\vdash \gamma \rightarrow \neg \beta _{1}$

ergibt sich die Ableitung

$\vdash \gamma \rightarrow \neg {\left(\beta _{1}\wedge \beta _{2}\right)}$

aus Kontraposition auf Fakt. Es sei nun

${}\alpha =\beta _{1}\rightarrow \beta _{2}\,.$

Bei

$\vdash \gamma \rightarrow \neg \beta _{1}\,\,{\text{ oder }}\,\,\vdash \gamma \rightarrow \beta _{2}$

ergibt sich die Ableitung

$\vdash \gamma \rightarrow {\left(\beta _{1}\rightarrow \beta _{2}\right)}$

aus Axiom  (1) bzw. aus Axiom  (5). Bei

$\vdash \gamma \rightarrow \beta _{1}\,\,{\text{ oder }}\,\,\vdash \gamma \rightarrow \neg \beta _{2}$

hingegen ergibt sich die Ableitung

$\vdash \gamma \rightarrow \neg {\left(\beta _{1}\rightarrow \beta _{2}\right)}$

folgendermaßen. Nach Fakt ist

$\vdash \beta _{1}\wedge {\left(\beta _{1}\rightarrow \beta _{2}\right)}\rightarrow \beta _{2},$

was wir als

$\vdash \beta _{1}\rightarrow {\left({\left(\beta _{1}\rightarrow \beta _{2}\right)}\rightarrow \beta _{2}\right)}$

schreiben. Kontraposition auf den Nachsatz ergibt

$\vdash \beta _{1}\rightarrow {\left(\neg \beta _{2}\rightarrow \neg {\left(\beta _{1}\rightarrow \beta _{2}\right)}\right)},$

was wir wiederum als

$\vdash \beta _{1}\wedge \neg \beta _{2}\rightarrow \neg {\left(\beta _{1}\rightarrow \beta _{2}\right)}$

schreiben. Aus den beiden Voraussetzungen ergibt sich mit Hilfe von Axiom  (3)

$\vdash \gamma \rightarrow \beta _{1}\wedge \neg \beta _{2}$

und somit mit der Kettenschlussregel

$\vdash \gamma \rightarrow \neg {\left(\beta _{1}\rightarrow \beta _{2}\right)}.$

Zur bewiesenen Aussage