ド・モルガンの定理

質問

こんにちは、よろしくお願いします。

ド・モルガンの定理はベン図を用いると、視覚的に理解できる。
しかし、ベン図を用いず、数式のみで証明するとなると結構難しい。
参考書などにもほとんどのっていない。
そこで、次のように証明してみた（添付図の下の部分）。

否定（否定A∨否定B）＝A∧B　　　・・・(1)※
否定（否定（A∧B））＝A∧B　　　　　・・・(2)
(1)、(2)より、否定A∨否定B＝否定（A∧B）

同様に
否定A∧否定B＝否定（A∨B）

※(1)の考え方
否定（否定A）＝A、、否定∨＝∧、否定（否定B）＝B

これで証明になっているでしょうか、皆さんのご意見をお聞かせ下さい。

回答No.6

akatsuki_0 · ベストアンサー

#2です。「∨を否定することはできない」について追記します。命題論理として解釈するにせよ、集合論的に解釈するにせよ、「∨」は二項関数記号で、「￢」は一項関数記号です。「∨を否定することはできない」ということで言いたいのは、否定をつけられるのは項だけだということです。初等的な算術の例でいえば、「-(2+3)」はwell-formedですが「-+」はそうではありません。意味が分からないとかそういうことではなくて、形式的に（=記号上の）問題があるということです。

参考になるURLということですが、例えば、wikipediaの「ブール代数」の項目をご覧下さい。「数式のみで証明したい」というのをブール代数の公理図式から導きたいということであれば、そこで挙げられている公理に代入などして頑張ってやる必要があります。ちなみに、#3さんの証明は代数的な証明ではないです。

お礼

何度もご回答ありがとうございます。
ブール代数・・・調べてみます。

回答No.7

Caper

たびたび、ごめんなさい。ANo.3 の訂正です。De Morgen はあやまりで、De Morgan が正しいようです。

　 それと、kenjoko さん のご質問に対して、ANo.3 は的を射たものになっていないようですね。どうもすみませんでした。取り急ぎ、ご連絡まで。

お礼

たびたびのご回答ありがとうございます。

＞ANo.3 は的を射たものになっていないようですね。どうもすみませんでした。

　　とんでもございません。

＞A = 真 のとき。
　 ￢(A∨B) = ￢(真∨B) = ￢真 = 偽

￢(真∨B) = ￢真・・・ここのところがいまいちピンとこない。
ここが理解できると後も同様に解けると思います。

回答No.5

Caper

ごめんなさい。ANo.3 の訂正です。

　 命題論理における De Morgen の法則 の証明にまちがいがありました。以下のとおりに改めさせてください。

　 ￢(A∨B) = ￢A∧￢B の証明

　 ( 証明開始 )

　 A = 真 のとき。
　 ￢(A∨B) = ￢(真∨B) = ￢真 = 偽
★ ￢A∧￢B = ￢真∧￢B = 偽∧￢B = 偽
★ よって、￢(A∨B) = ￢A∧￢B (= 偽)

　 A = 偽 のとき。
　 ￢(A∨B) = ￢(偽∨B) = ￢B
★ ￢A∧￢B = ￢偽∧￢B = 真∧￢B = ￢B
★ よって、￢(A∨B) = ￢A∧￢B (= ￢B)

　 ( 証明終わり )

回答No.4

Tacosan

「※(1)の説明では納得してもらいないでしょうから」って書いてるけど, どうしたって「納得してもらえる」と思える方がおかしい. これはせいぜい「考え方」でしかなく, その「考え方」があってるかどうかについては一言もないんだもの (「考え方」が間違っているとしても, 何らかの理由で「結果的にはあっている」ことがあり得る: 当然, そのような議論に意味はない).

で #2 の「∨を否定することはできません」については, まあ, そりゃそうだわな. そもそも「∨の否定」が何を意味するのか全く定義されていない.

もちろんド・モルガンの定理をブール代数の公理で示すことはできる.

お礼

＞何らかの理由で「結果的にはあっている」ことがあり得る: 当然, そのような議論に意味はない).

私もそう思います、ありがとうございました。

回答No.3

Caper

● 私が参考にした数学書

　 * 前原昭二 著「 復刊 数理論理学序説 」( 共立出版 2010/09/25 復刊 1 刷 )
　 * 松坂和夫 著「 集合・位相入門 」( 岩波書店 1983/12/05 第 17 刷 )

　 なお、下記の私の記述にまちがいがありました場合は、ひらにごめんなさい。それらのまちがいは、もちろん私の誤解によるものであり、上記の 2つ の書籍によるものでは決してありません。

● まず、命題論理における De Morgen の法則の証明について、説明させてください。

　 その前に、下準備を。
　 以下における、A, B とは命題変数です。すなわち、A, B はいずれも、とり得る値が 真 か 偽 かのいずれかです。さらに言い換えれば、A ∈ {真, 偽}, B ∈ {真, 偽} です。真 と 偽 は、命題変数に代入することができる定数です。
　 以下における ￢ という記号は「 否定 」を意味します。∨ という記号は「 または 」を意味します。∧ という記号は「 かつ 」を意味します。= という記号は「 命題の同値 」を意味します。
　 = については、≡ や ⇔ などが代用されることもあります。　

　 ￢(A∨B) = ￢A∧￢B の証明

　 ( 証明開始 )

　 A = 真 のとき。
　 ￢(A∨B) = ￢(真∨B) = ￢真 = 偽
　 ￢A∨￢B = ￢真∧￢B = 偽∧￢B = 偽
　 よって、￢(A∨B) = ￢A∨￢B (= 偽)

　 A = 偽 のとき。
　 ￢(A∨B) = ￢(偽∨B) = ￢B
　 ￢A∨￢B = ￢偽∧￢B = 真∧￢B = ￢B
　 よって、￢(A∨B) = ￢A∨￢B (= ￢B)

　 ( 証明終わり )

　 ￢(A∧B) = ￢A∨￢B の証明も同様であると思われます。

● 次に、集合における De Morgen の法則の証明について、説明させてください。

　 以下における ^c という記号は「 補集合 」を意味します。

　 (A∪B)^c = (A^c)∩(B^c) の証明

　 ( 証明開始 )

　 ( x は (A∪B)^c に含まれる ) という命題を変形させてゆきます。

　 ( x は (A∪B)^c に含まれる )
　 = (x ∈ (A∪B)^c)
　 = ￢(x ∈ A∪B)　( 補集合の定義による変形 )
　 = ￢((x ∈ A)∨(x ∈ B))　( 和集合の定義による変形 )
　 = ￢(x ∈ A)∧￢(x ∈ B)　( 命題論理における De Morgen の法則による変形 )
　 = (x ∈ A^c)∧(x ∈ B^c)　( 補集合の定義による変形 )
　 = (x ∈ (A^c)∩(B^c))　( 共通部分の定義による変形 )
　 = (x は (A^c)∩(B^c) に含まれる )

　 よって、
　 (A∪B)^c
　 = {x| x は (A∪B)^c に含まれる }
　 = {x| x は (A^c)∩(B^c) に含まれる }
　 = (A^c)∩(B^c)

　 ( 証明終わり )

　 (A∩B)^c = (A^c)∪(B^c) の証明も同様であると思われます。

● 以上における私の記述の中に、わかりにくい個所・まちがいではないかと思われる個所がありましたら、「 補足 」機能を利用するなどして、遠慮なくご指摘ください。

回答No.2

akatsuki_0

よく分からない点が多いのですが。幾つか箇条書きで記します。
1.　何を前提にして証明したいのでしょうか。(1)や(2)はブール代数の公理ではないと思います。図を使ってもいいのか使いたくないのかもはっきりしません。また、「(1)の考え方」というところですが、∨を否定することはできません。

2.　図の下に「-A∪-Bの証明」とありますが、これ自体はド・モルガンの法則ではないですよね。

3.　「∧」や「∨」と、「∪」「∩」が混在しています。どちらかに統一すべきだと思います。

お礼

＞2.　図の下に「-A∪-Bの証明」とありますが、これ自体はド・モルガンの法則ではないですよね。

　-A∪-B　＝－（A∩B）の証明です。ごめんなさい。

補足

ご回答ありがとうございます。

＞1.　何を前提にして証明したいのでしょうか。(1)や(2)はブール代数の公理ではないと思います。図を使ってもいいのか使いたくないのかもはっきりしません。

図を用いず、数式のみで証明したい。

＞また、「(1)の考え方」というところですが、∨を否定することはできません。

　　　　ここのところがよく分かりません。

＞2.　図の下に「-A∪-Bの証明」とありますが、これ自体はド・モルガンの法則ではないですよね。

　-A∪-B　＝－（A∩B）　、-A∩-B　＝－（A∪B）　　　　　　　違いますか？

＞3.　「∧」や「∨」と、「∪」「∩」が混在しています。どちらかに統一すべきだと思います。

パソコンに不慣れなもので、すみません。∧＝∩、∪＝∨と理解して下さい。

PS：参考になるようなURL等知っていましたら、お知らせください。

回答No.1

Tacosan

「なんで (1) が成り立つんですか～」って聞かれたら困らないかなぁ....

補足

＞「なんで (1) が成り立つんですか～」って聞かれたら困らないかなぁ....

困りますよね、※(1)の説明では納得してもらいないでしょうから（No.２さん参照）

やはり、ベン図を用いるしかないんですかね？