¬の分配法則と二重否定の除去と導入

股関節おじさんの勉強部屋

2023.07.11

論理和と論理積の結合、分配法則を学んでいえふと、「ド・モルガンの法則は否定の分配法則だ」と頭に浮かびました。

否定演算には分配法則が成り立つことをド・モルガンの法則は言っているのですね。

¬の分配法則と二重否定の除去と導入

¬の分配法則と二重否定の除去と導入

ド・モルガンの法則

【定義】
$\displaystyle P,Q\in {\bot ,\top }$に対して

$\displaystyle \neg (P\lor Q)=\neg P\land \neg Q\,,$

$\neg (P \land Q) = \neg P \lor \neg Q$
が成り立つ。これをド・モルガンの法則という[1]。
Wikipedia

二重否定の導入と除去

ついで二重否定の除去と導入。

英語記事しか探せませんでした。

【二重否定の導入と除去】
Double negation elimination and double negation introduction are two valid rules of replacement. They are the inferences that, if not not-A is true, then A is true, and its converse, that, if A is true, then not not-A is true, respectively. The rule allows one to introduce or eliminate a negation from a formal proof. The rule is based on the equivalence of, for example, It is false that it is not raining. and It is raining.

The double negation introduction rule is:

P
⇒\Rightarrow
¬\neg
¬\neg P
and the double negation elimination rule is:

¬\neg
¬\neg P
⇒\Rightarrow P
Wikipedia

¬¬Aが真ならAは真、つまり¬¬A⇒Aが成立しその逆も真となる定理があると言ってます。

証明してみます。

A⇔¬¬Aの証明

1.[¬¬A](仮定)
2.A(排中律)
3.¬¬A→A

1.[A](仮定)
2.¬¬A排中律
3.A→¬¬A

Aか¬Aしかありえないかつ¬Aではないので、¬¬AはAであるって論理です。

1.[A],[¬A]
2.⊥
3.¬¬A
A→¬¬A

意味的にはあまり変わらない気がしますが、A∧¬Aを仮定として矛盾を、背理法で¬Aの否定¬¬Aを演繹するって論理でもよのかなあと。

証明と論理に強くなる ~論理式の読み方から、ゲーデルの門前まで~ (知の扉)

【排中律】（はいちゅうりつ、英: Law of excluded middle、仏: Principe du tiers exclu）とは、論理学において、任意の命題 P に対し”P ∨ ¬P“（P であるか、または P でない）が成り立つことを主張する法則である。
Wikipedia

【背理法】
P を仮定すると、矛盾 ⊥ が導けることにより、P の否定 ¬P を結論付けることは否定の導入などと呼ばれる[2]。

$\displaystyle {\cfrac {\displaystyle {[P] \atop \bot }}{\neg P}}$
これに対して ¬P を仮定すると矛盾 ⊥ が導けることにより P を結論付けることを狭義の背理法あるいは否定の除去ということがある。

$\displaystyle {\cfrac {\displaystyle {[\neg P] \atop \bot }}{P}}$
Wikipedia