━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
数理論理学 第４回「論理式と証明法 3」の要点
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

●含意Ａ⇒Ｂの証明法

間接証明（対偶法）
        Ｂが偽（¬Ｂが真）であることを仮定し，Ａが偽（¬Ａが真）であることを導く
        ※Ａ⇒Ｂ の対偶 ¬Ｂ⇒¬Ａ の直接証明に相当

間接証明（背理法）
        Ａ⇒Ｂ が真であることを示す証明法
        Ａが真であり，Ｂが偽（¬Ｂが真）であることを仮定し，矛盾を導く

補題の利用
        適切な命題Ｃを見つけて，Ａ⇒Ｃ と Ｃ⇒Ｂ の二つを証明する

●同値Ａ⇔Ｂの証明法

双方向の含意の証明
        Ａ⇔Ｂ が真であることを示す証明法
        両方向の含意 Ａ⇒Ｂ と Ｂ⇒Ａ が共に真であることを示す

同値変形
        論理式(の一部)をそれと真偽が一致する別の論理式に置き替える式変形を反復
        Ａ⇔Ｃ1，Ｃ1⇔Ｃ2，…，Ｃn-1⇔Ｃn，Ｃn⇔Ｂ の一連の証明を次の形に示す
           Ａ
        ⇔ Ｃ1
        ：
        ：
        ⇔ Ｃn
        ⇔ Ｂ

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
授業のホームページ

山田 俊行
https://www.cs.info.mie-u.ac.jp/~toshi/