Aussagenlogik/Variablenbelegung/Ableitbarkeit/Fakt/Beweis/Aufgabe/Lösung

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

α = p_{i}

ergibt sich die Aussage aus Fakt. Bei

α = \neg β

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

α = β_{1} \land β_{2} .

Bei

⊢ γ \to β_{1} und ⊢ γ \to β_{2}

ergibt sich die Ableitung

⊢ γ \to β_{1} \land β_{2}

im Wesentlichen aus Axiom (3). Bei

⊢ γ \to \neg β_{1}

ergibt sich die Ableitung

⊢ γ \to \neg (β_{1} \land β_{2})

aus Kontraposition auf Fakt. Es sei nun

α = β_{1} \to β_{2} .

Bei

⊢ γ \to \neg β_{1} oder ⊢ γ \to β_{2}

ergibt sich die Ableitung

⊢ γ \to (β_{1} \to β_{2})

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

⊢ γ \to β_{1} oder ⊢ γ \to \neg β_{2}

hingegen ergibt sich die Ableitung

⊢ γ \to \neg (β_{1} \to β_{2})

folgendermaßen. Nach Fakt ist

⊢ β_{1} \land (β_{1} \to β_{2}) \to β_{2},

was wir als

⊢ β_{1} \to ((β_{1} \to β_{2}) \to β_{2})

schreiben. Kontraposition auf den Nachsatz ergibt

⊢ β_{1} \to (\neg β_{2} \to \neg (β_{1} \to β_{2})),

was wir wiederum als

⊢ β_{1} \land \neg β_{2} \to \neg (β_{1} \to β_{2})

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

⊢ γ \to β_{1} \land \neg β_{2}

und somit mit der Kettenschlussregel

⊢ γ \to \neg (β_{1} \to β_{2}) .