述語論理におけるド・モルガンの法則
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/25 04:11 UTC 版)
「ド・モルガンの法則」の記事における「述語論理におけるド・モルガンの法則」の解説
上のド・モルガンの法則は、一階述語論理にも拡張できる。 A(x) を変数 x についての言明とすると 「全ての x に対し A(x)」の否定は「ある x が存在して ￢A(x)」 「ある x が存在して A(x)」の否定は「全ての x に対し ￢A(x)」 と表現できる。 「全ての x に対し〜」、「ある x に対し〜」を表す記号 ∀, ∃ を使って書くと ¬ ∀ x A ( x ) ⇔ ∃ x ¬ A ( x ) {\displaystyle \neg \forall x~A(x)\Leftrightarrow \exists x~\neg A(x)} ¬ ∃ x A ( x ) ⇔ ∀ x ¬ A ( x ) {\displaystyle \neg \exists x~A(x)\Leftrightarrow \forall x~\neg A(x)} となる。 具体例を挙げると、 「全ての人が冷蔵庫を持っている」の否定は「ある人は冷蔵庫を持っていない」（すなわち、「冷蔵庫を持っていない人が少なくとも一人いる」） 「ある人が冷蔵庫を持っている」（すなわち、「冷蔵庫を持っている人が少なくとも一人いる」）の否定は「全ての人が冷蔵庫を持っていない」（すなわち、「誰ひとりとして冷蔵庫を持っていない」） などである。また、後述するように部分否定や全否定の言い換えも述語論理におけるド・モルガンの法則を表現していると考えられる。 命題論理におけるド・モルガンの法則から、以下のようにして述語論理に拡張されたド・モルガンの法則を確かめられる（次節に注意）。 x が 1 から 100 までの数を表す変数だとする。このとき「全ての x に対し A(x)」は、「A(1) かつ A(2) かつ …… かつ A(100)」を意味する。これの否定は、命題論理のド・モルガンの法則から 「￢A(1)」または ￢「A(2) かつ A(3) かつ …… かつ A(100)」 となり、さらに「A(2) かつ A(3) かつ …… A(100)」の否定についても同様の操作をくりかえすことにより、「￢A(1) または ￢A(2) または … または ￢A(100)」が得られる。これは「ある x に対し ￢A(x)」ということと等しい。 また、逆に、「ある x に対し A(x)」は「A(1) または A(2) または…… A(100)」ということだが、これの否定は 「￢A(1)」かつ ￢「A(2) または A(3) または …… または A(100)」 であり、これをつづけて「全てのxに対し￢A(x)」が得られる。
※この「述語論理におけるド・モルガンの法則」の解説は、「ド・モルガンの法則」の解説の一部です。
「述語論理におけるド・モルガンの法則」を含む「ド・モルガンの法則」の記事については、「ド・モルガンの法則」の概要を参照ください。
- 述語論理におけるド・モルガンの法則のページへのリンク
