証明の考え方

証明とは、前提から結論へ、各段階が正当化された道筋を示すこと。

推論規則#

規則	形
モーダスポネンス	$P$、$P\to Q$ から $Q$
モーダストレンス	$\neg Q$、$P\to Q$ から $\neg P$
三段論法	$P\to Q$、$Q\to R$ から $P\to R$

これらは形式だけで正しさが決まる。 内容を理解しなくても検証できることが形式化の意義で、 だから計算機に証明を検証させられる。

健全性と完全性#

性質	意味
健全性	証明できることは真である
完全性	真であることは証明できる

一階述語論理はどちらも成り立つ（Gödel の完全性定理）。 一方、算術を含む体系では不完全性定理により、 真だが証明できない命題が存在する。

誤りやすい形#

• 逆の混同 — $P\to Q$ から $Q\to P$ を導く
• 必要条件で満足する — 必要条件を確かめて結論と思う
• 循環論法 — 示したいことを前提に使う
• 一般化しすぎ — 例をいくつか確かめて「すべて」と言う

最後は特に注意が要る。 手法の比較で 「いくつかの関数で勝った」から 「この手法は優れている」と結論するのは、この誤りの一形態。

参考文献#

• Herbert B. Enderton. A Mathematical Introduction to Logic, 2nd ed. Academic Press, 2001. https://doi.org/10.1016/b978-0-08-049646-7.50005-9
• Kenneth H. Rosen. Discrete Mathematics and Its Applications, 8th ed. McGraw-Hill, 2019. https://www.mheducation.com/highered/product/discrete-mathematics-applications-rosen/M9781259676512.html
• MIT OCW 6.042J Mathematics for Computer Science https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-fall-2010/