演繹定理
「証明」 公理 1:
P 1. 仮説 Q 2. 仮説 P 3. 1 の反復 Q→P 4. 2 から 3 への演繹
P→(Q→P) 5. 1 から 4 への演繹 QED
「証明」 公理 2:
P→(Q→R) 1. 仮説 P→Q 2. 仮説 P 3. 仮説 Q 4. 3と2によるモーダスポネンス Q→R 5. 3と1によるモーダスポネンス R 6. 4と5によるモーダスポネンス P→R 7. 3から6への演繹 (P→Q)→(P→R) 8. 2から7への演繹
(P→(Q→R))→((P→Q)→(P→R)) 9. 1から8への演繹 QED
公理 1 を使って ((P→(Q→P))→R)→R を示す:
(P→(Q→P))→R 1. 仮説 P→(Q→P) 2. 公理 1 R 3. 2と1によるモーダスポネンス
((P→(Q→P))→R)→R 4. 1から3への演繹 QED
公理的命題論理では、公理図式として次のものを使うのが一般的である(ここで、P、Q、R は任意の命題)。
公理 1 : P→(Q→P)
公理 2 : (P→(Q→R))→((P→Q)→(P→R))
モーダスポネンス : P と P→Q から Q を推論する。
これらの公理から明らかに定理 P→P が得られる(命題論理参照)。簡単のため、定理 P→P も公理図式として採用することにする。これらの公理図式は、演繹定理が容易に導けるように選ばれている。従って、論点をはぐらかしているように見えるかもしれない。しかし、真理値表を使ってそれが恒真式であることを検証し、モーダスポネンスが妥当な推論であることを確認することで正当であることが確認できる。この体系は直観主義命題論理の含意断片の完全な証明計算体系である。以下の議論はこの体系より強い任意の体系(例えば古典命題論理)に対して適用できる。
ここで、Γと H から C を証明できるとき、Γから H→C を証明できることを示したいとする。Γ(反復ステップ)または公理における前提である演繹の各ステップ S について、公理1 S→(H→S) にモーダスポネンスを適用でき、H→S が得られる。ステップが H 自身(仮説ステップ)なら、公理図式を適用して H→H が得られる。ステップが A と A→S へのモーダスポネンスの適用結果であるとき、まずそれら前提が H→A と H→(A→S) に変換できることを示してから、公理2 (H→(A→S))→((H→A)→(H→S)) を使い、モーダスポネンスを適用して (H→A)→(H→S) を得て、最終的に H→S を得る。