Prädikatenlogik/Aussagenlogische Tautologie/Einsetzen/Fakt/Beweis

Beweis

Wir führen Induktion über den Aufbau der aussagenlogischen Tautologien. Es sei eines der aussagenlogischen Axiome in den Ausdrücken und es seien die darin auftretenden Aussagenvariablen. Wir schreiben die zugrunde liegende aussagenlogische Tautologie in den Aussagenvariablen und nennen diese . Dann ist

Somit ist insgesamt

D.h. entsteht durch Einsetzung von prädikatenlogischen Ausdrücken in eine Basistautologie und gehört somit zu den in Axiom gelisteten Tautologien. Es sei nun eine aussagenlogische Tautologie, die durch Modens ponens erhalten wird. Dann gibt es also eine aussagenlogische Tautologie und ist ebenfalls eine aussagenlogische Tautologie. Nach Induktionsvoraussetzung sind dann und prädikatenlogische Tautologien. Da der Modus ponens eine erlaubte Schlussregel in der Prädikatenlogik ist, folgt, dass eine prädikatenlogische Tautologie ist.