ド・モルガンの法則
ド・モルガンの法則
A∨B⇔B∨A
を導きたいってこどネットを徘徊していたところ「論理和の交換法則はこの論理展開で行くんじゃない？」とヒントになりそうなものを発見しましたので共有します。
ド・モルガンの法則の自然演繹です。
1.A,B(仮定1,2)
2.A∧B(∧導入)
3.¬(A∧B)(仮定3)
4.⊥
5.¬A(¬導入,仮定1キャンセル)
6.¬A∨¬B(∨導入 )
7.¬(¬A∨¬B)(仮定4)
8.⊥
9.¬B(¬導入,仮定2キャンセル)
10.¬A∨¬B(∨導入)
11.⊥
12.¬(¬(¬A∨¬B))(¬導入,仮定4キャンセル)
13.¬A∨¬B(¬¬除去)
14.¬(A∧B)→¬A∨¬B
推論規則に従いド・モルガンの法則
¬(A∧B)⇒¬A∨¬B
が演繹されています。
補足
1.は仮定1,2を立てています
※この仮定は後々解消します。
2.1の仮定を元に∨導入
3.新たに仮定¬(A∨B)を導入
※この仮定がド・モルガンの法則の前件命題かつ仮定1を解消する
4.仮定との矛盾を演繹し
※演繹に矛盾。規則通りに仮定を解消し¬導入
5.¬Aが演繹
6.論理和導入と仮定4の導入
※仮定4は解消される
7.矛盾を演繹
8.仮定2を解消し¬導入
9.∨導入
10.仮定4を解消し矛盾を演繹
11.残る仮定3に¬導入
12.二重否定の除去
13.仮定3と結論を繫げる⇒導入
ド・モルガンの法則が導けました。
面白いと思ったのは前提と仮定の立て方。
一見すると無関係の前提を立て、そこから仮定の導入、解消を繰り返して上記のド・モルガンの法則の前件命題を、続いて後件命題を導いています。
なんとなくですが、
A∨B⇔B∨A
は上記のド・モルガンの法則のような論理展開になる気がするんですよね。
[A](仮定)
A∨B(∨導入)
¬(A∨B)(仮定)
⊥(排中律)
¬A(背理法)
[B](仮定)
A∨B(∨導入)
¬(A∨B)(仮定)
⊥(排中律)
¬B(背理法)
¬A∧¬B(∧導入)
¬(A∨B)→¬A∧¬B(→導入)
[A∧B](仮定)
[¬A](仮定)
A(∧除去)
⊥(排中律)
¬A→⊥(→導入)
[¬B](仮定)
B(∧除去)
⊥(排中律)
¬B →⊥(→導入)
[¬A ∨¬B](仮定)
⊥(∨除去)
¬(A∧B)(背理法)
¬A∨¬B →¬(A∧B )(→導入)
¬A∧¬B(仮定)
[A](仮定)
¬A(∧除去)
⊥(排中律)
A→⊥(→導入)
[B] (仮定)
¬B(∧除去)
⊥(排中律)
B→⊥(→導入)
[A∨B](仮定)
⊥(∨除去)
¬(A∨B)(⊥除去)
¬A∧¬B→¬(A∨B)(→導入)
コメント