「ド・モルガンの法則」の版間の差分
削除された内容 追加された内容
双対性の説明（いらなかったかも）、本が好きの記号を変更、ほかformatting |
|||
1行目:
'''ド・モルガンの法則'''（ド・モルガンのほうそく、De Morgan's laws）とは、[[数理論理学]]や[[集合論]]において、論理積（集合の積、共通部分）と論理和（集合の和、合併）、否定（補集合）
この関係性は、真・偽を反転させ、論理和・論理積の定義を交換した論理体系が元の論理体系と同一視できることを指しているので、'''ド・モルガンの[[双対性]]'''とよばれることもある。
== 概要 ==
6 ⟶ 8行目:
: <math>\neg (P \land Q) = \neg P \lor \neg Q</math>
: <code>!(P || Q) == !P && !Q</code>
: <code>!(P && Q) == !P || !Q</code>
が成立するということである。
同じことを集合の言葉を用いて言い換えると、
29 ⟶ 32行目:
の否定
「私の身長は 160 cm 以上であり、かつ私の体重は 50 kg 以上」ではない
の真偽が、次の命題と等しいことを、ド・モルガンの法則は主張している。
「私の身長は 160 cm 未満であるか、または私の体重は 50 kg 未満」である
同じようにして
38 ⟶ 41行目:
== 述語論理におけるド・モルガンの法則 ==
上のド・モルガンの法則
A(x) を変数 x についての言明とすると * 「全てのxに対しA(x)」の否定は「あるxが存在して￢A(x)」
* 「あるxが存在してA(x)」の否定は「全てのxに対し￢A(x)」
と表現できる。
「全てのxに対し〜」、「あるxに対し〜」を表す記号<math>\forall, \exists</math>を使って書くと
* <math>\neg\forall x~A(x) \Leftrightarrow \exists x~\neg A(x)</math>▼
* <math>\neg\exists x~A(x) \Leftrightarrow \forall x~\neg A(x)</math>▼
となる。
具体例を挙げると、
* 「全ての人が冷蔵庫を持っている」の否定は「ある人は冷蔵庫を持っていない」（すなわち、「冷蔵庫を持っていない人が少なくとも一人いる」）
* 「ある人が冷蔵庫を持っている」（すなわち、「冷蔵庫を持っている人が少なくとも一人いる」）の否定は「全ての人が、冷蔵庫を持っていない」（すなわち、「誰ひとりとして冷蔵庫を持っていない」）
▲* <math>\neg\forall x~A(x) \Leftrightarrow \exists x~\neg A(x)</math>
▲* <math>\neg\exists x~A(x) \Leftrightarrow \forall x~\neg A(x)</math>
命題論理におけるド・モルガンの法則を認めれば以下のようにして述語論理版のド・モルガンの法則を確かめることができる。▼
今xが1から100までの数を表す変数だとする。このとき「全てのxに対しA(x)」であるとは、「A(1)かつA(2)かつ… A(100)」を意味する。これを否定すると▼
￢A(1)または￢「A(2)かつ... A(100)」▼
▲
となり、「A(2)かつ… 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)」は「A(1)またはA(2)または… A(100)」ということだが、これの否定は
であり、これをつづけて「全てのxに対し￢A(x)」が得られる。
59 ⟶ 72行目:
=== 全否定と部分否定 ===
[[全否定]]や[[部分否定]]をどう言い換えるかという問題は
たとえば、「…という本が好きだ」という言明を表すのに、「…」を本を表す変数として、
(''…'')'''が好き'''
という記号を用いることにする。
この記号を使って「全ての本が好きだ」という言明を述語論理で表現すると、
「全ての''本''に対し、(''本'')'''が好き'''」
となる。
部分否定の言明「'''全ての本が好きだというわけではない'''」を述語論理で表現すると
(全ての''本''に対し、(''本'')'''が好き''') ''の否定''
ド・モルガンの法則により、
ある''本''に対し、（(''本'')'''が好き''' ''の否定''）
すなわち「'''好きでない本がある'''」、「'''嫌いな本がある'''」と言い換えられることがわかる。
他方、全否定「'''すべての本が嫌いだ'''」は
全ての''本''に対し ((''本'')'''が好き''' ''の否定'')
を指し、ド・モルガンの法則によって
(ある''本''に対し (''本'')'''が好き''') ''の否定''
「'''好きな本がある'''」の否定、つまり「'''好きな本はない'''」であることが分かる。
{{DEFAULTSORT:ともるかんのほうそく}}
| |||