論理学の練習問題 自然演繹 命題論理 ド・モルガンの法則の証明

ド・モルガンの法則
¬(p∧q)←→(¬p∨¬q)
¬(p∨q)←→(¬p∧¬q)

証明

(1)　¬(p∧q)→(¬p∨¬q)
　　　1　 2,4
　　　p　 q
　　────　　 3
　　　p∧q　　¬(p∧q)
　　─────────
　　　 　　　 ⊥　　　　　　⊥
　　　　　──── 1　　──── 2
　　　　　　　¬p　　　　　¬q
　　　　　　──── 　　────
　q∨¬q　　¬p∨¬q　　　¬p∨¬q
　──────────────── 4
　　　　　　　¬p∨¬q
　　　─────────── 3
　　　　¬(p∧q)→(¬p∨¬q)

(2)　(¬p∨¬q)→¬(p∧q)
　　　　　1　　　　　1
　　　　p∧q　　　 　p∧q
　　　　──　 2　　──　 2
　　　　　p　 ¬p　　q　 ¬q

　　3　　────　　────
¬p∨¬q　　 ⊥　　　　　⊥
────────────── 2
　　　　　　　　　⊥
　　　　　　　───── 1
　　　　　　　　¬(p∧q)
　　　　─────────── 3
　　　　　(¬p∨¬q)→¬(p∧q)

(3)　¬(p∨q)→(¬p∧¬q)
　1　　　　　　　　2
　ｐ　　　　　　　　q
───　　　3　　───　　 3
　p∨q　¬(p∨q)　　p∨q　¬(p∨q)
───────　───────
　　　 ⊥　　　　　　　 ⊥
　 　─── 1　　　　─── 2
　　　¬p　　　　　　¬q
───────────────
　　　　　　¬p∧¬q
　　　─────────── 3
　　　　¬(p∨q)→(¬p∧¬q)

(4)　(¬p∧¬q)→¬(p∨q)
　　　　3　　　　　　　　3
　　¬p∧¬q　　　　　¬p∧¬q
　　────　1　　　 ────　 1
　 　　¬p　　p　　　　　¬q　　q
　 2　 ─────　　　　─────
　p∨q　　 ⊥　　　　　　　　 ⊥
────────────────── 1
　　　　　　　　　⊥
　　　　　　─────── 2
　　　　　　　　¬(p∨q)
　　　　　─────────── 3
　　　　　　(¬p∧¬q)→¬(p∨q)