■

授業第二十二回目、本日は古典命題論理の健全性定理と完全性定理の話をします（述語論理の健全性と完全性は次回に持ち越しです）。
健全性定理は、証明可能な式は恒真式であることを主張し、こちらは証明図の長さに関する（メタの）帰納法により簡単に証明できます。また、完全性定理は恒真式は証明可能であることを主張するとても強烈な定理ですが、こちらはその対偶（「任意の証明不可能な式に対し、それを偽にする真理関数が構成できる」）を、証明探索樹を使ったやり方で示します。