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

ド・モルガンの法則
¬(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
 p        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)