論理学について質問です

質問

次の論理式、A∧B⇒C、 D∧E⇒F、 C∧F⇒G　が常に成り立つとき、A∧B∧D∧E⇒G は常に成り立ちますか？

できれば、成り立つか成り立たないかを解説付きでおねがいします。

回答No.1

nobuyuki0505 · ベストアンサー

成り立ちます。使う公式は三つ。

1.A∧(B∧C)=(A∧B)∧C
2.A→B,B→Cならば、A→C.
3.A→BであればA∧C→B∧Cが成立。

1.2.はよく知られた公式で、3.は調べましたが見つからなかったので、自力で証明しました。

3の証明は簡単なので、省略します。1.2.は有名なので除外。

論理的に説明すると、
A∧B→Cより、3を適用すれば、
(A∧B)∧(D∧E)→C∧(D∧E)
また、
D∧E→Fに3を適用すれば、
(D∧E)∧C→F∧C
この二つより、2を適用すれば、
(A∧B)∧(D∧E)→F∧C
を得るが、
C∧F→G
であったため、再び2を適用すれば、
(A∧B)∧(D∧E)→G
を得る。
最後に1を用いれば、
(A∧B)∧(D∧E)=A∧B∧D∧E
を得るので、A∧B∧D∧E→Gは真だと分かる。

回答No.7

noname#212313

#3, 4, 5です。

　ちょとキナ臭くなってきましたので、ネタ晴らしをしておきます。#3には間違いが入れてあります（#4の図もそれに起因する、同じ間違いがある）。下記です。

#3>> C∧F⇒G
#3 誤>　Gは「C∧F」に含まれるということです。

　他の部分の「⇒」と、言葉で説明した包含関係が逆になっていますよね。C∧Fが必ずGになるということは、集合C∧Fが集合Gに含まれるということのはずです。つまり、以下のようにせねばなりません。

>> C∧F⇒G
正>　Gは「C∧F」を含む（「C∧F」はGに含まれる）ということです。

　上記を「ここはおかしんじゃないの？」と質問者様にご指摘いただくよう、工夫するつもりでした。正解には、少なくとも最後の部分は質問者様に辿り着いて頂きたいと思っています。単純知識ならいざ知らず、複雑な思考を要する問題では、「あ、分かった！」という嬉しさを横取りしてはいけませんものね。

　さて、これを踏まえると、図はこの回答に添付したようなものになります。GはC∧Fを含み、C∧FはA∧B∧D∧Eを含みます。したがって、A∧B∧D∧EはGに含まれます。

　つまり、成り立つのです。

回答No.6

noname#212313

#5 mmitsukuniさん。名指しされた以上、仕方ないですね。お答えします。

　能書きは不要なんですよ。#3で私が出した反例が不成立であることを証明しなさい。できなければ、迂回した理屈をいくらこねても価値はない。

　以上。

回答No.5

mmitsukuni

Dio_Genes さんの回答は，命題P⇒Qについての典型的な間違いです．

P⇒Q という論理式が真になるのは，次の２つの場合です．
　(1)　Pが真でかつQが真のとき
　(2)　Pが真でなければ，(Qの真偽にかかわらず）論理式は真
論理学を知らない人が間違いやすいのは，命題P⇒Qについての(2)です．

約束：「明日晴れたら」⇒「遊園地へ連れて行く」
ここで，「明日雨が降ったとき」は
「「遊園地へ連れて行って」も「連れて行かなくても」
「約束」は守ったこと(真)になるのではないですか．

命題：(X>1)⇒(X>0）の例も考えてください．
上の命題は，「全てのXについて成り立つ」というから意味があるのです．
これが，X>1だけの定義範囲(正整数など)しか考えないのなら
「(X>0)⇒」の部分は不要で，単に「X>0」が成り立つと書けばよい．

それで，これらを図で説明するのなら，
それぞれの命題が独立して真，偽となる集合(ベン図)を書いてください．
　P∩B　と　￢P∩B　と　P∩￢B　と　￢P∩￢B　が必要です．
集合の包含関係は必ず上の４つがないと，命題の意味がありません．

さて，P⇒Qをベン図で説明すると，
(1) はP∩B の部分が真　(2)は￢P（Pの外側）も真
ということを表します．集合図の各部に「真」（「偽」）を
記入しなければなりません．

あとは，「論理学　ベン図」で検索してください．

ということで，前に回答したとおり「質問者の命題は成り立ちます」

回答No.4

noname#212313

#3です。

　添付した図が編集途中でした。あれでも説明として成り立ちますが、もう少しはっきりとA∧B∧D∧EからGが外れているように描いたものを添付してみます。

回答No.3

noname#212313

結論を申せば、成り立ちません。

　以下、集合で説明してみます。「P⇒Q」（PであるならQである）というのは、集合として表現すると、「QはPを含む」「PはQに含まれる」（「P⊆Q」「Q⊇P」などと書く）ということです

　A～Gを集合で表して、包含関係を考えてみます（添付図）。

>A∧B⇒C

　『「AかつB」ならばC』ということを集合で考えると、集合「A∧B」が集合Cに含まれるということになります（記号で書くと、A∩B⊆C）。Cは「A∧B」以外の要素を持てるわけです。

　念のため、例で考えると、A＝{1, 2}、B＝{1, 3}、C＝{1, 6}だとすると、A∧B＝{1}で、これはCに含まれています。Cは6というAにもBにも無い要素を持っていても、A∧Bを含んでいればいいので問題ありません。また、Cには、Aの2も、Bの3もありませんが、条件はA∧Bですので、やはり問題ありません。

　すると、CはAにもBにも無い要素を持てるわけです。言い換えれば「AまたはB」（A∨B、A∪B）という、AとB両方合わせた集合に無い要素を、Cは持っていてもよいのです。

>D∧E⇒F

　同じく、集合「D∧E」が集合Fに含まれるということです（D∩E⊇F）。上記と同様、DにもEにも無い要素を持てるということになります。

　Cは「A∧B」に無い要素を持っていてもよく、Fは「D∧E」に無い要素を持っていてもいいのでした。それらのうち、CにもFにも属する要素があってもいいわけです。つまり、「C∧Fは、A、B、D、Eのどれも持っていない要素を持てることになります。

> C∧F⇒G

　Gは「C∧F」に含まれるということです。「C∧F」にはA、B、D、Eどれにも属さない要素があることは分かっています。その要素がGに属していても問題ありません。

　つまり、GもA、B、D、Eに属さない要素を持っていてもいいわけです。ですので、成り立ちません。

　成り立たないことを示すには反例が一つあれば充分です。

A＝{1, 2}
B＝{1, 3}
D＝{1, 4}
E＝{1, 5}

C＝{1, 6}
F＝{1, 6}

だとします。

A∧B＝{1}　←Cに含まれている
D∧E＝{1}　←Fに含まれている

より、

A∧B∧D∧E＝{1}

です。一方、

C∧F＝{1, 6}

ですから、これにGが含まれるよう。

G＝{6

とすることができます。そうすると、A∧B∧D∧Eの要素「1」はGに含まれていません。従って反例が存在することが分かりましたので、「A∧B∧D∧E⇒G」は成り立ちません。

P.S.

　もし「⇒」の向きが逆、あるいは、等しいことを表す「⇔」だったら成り立つものになります。

回答No.2

mmitsukuni

回答１は，自分で作った公式3を証明なしで使ってはいけませんね。
さらに、A⇒B,B⇒CならばA⇒C（３段論法）もこれを証明しようと
すると、結局⇒の意味を証明することになり、質問者の問題を
直接証明することとほぼ同じことになります。

それでは、論理代数の基本に戻って証明してみましょう。

論理代数は、真(1とする)と偽(0とする)の２値と
この上で定義された基本論理演算：NOT(￢)，AND（∧），OR(∨)
から成り立ってます。（つまり⇒はあとから定義した演算）

十分条件を示す⇒ですが、次のように定義されてます。
　　P⇒Q≡￢P∨Q　（≡は定義）
この定義が「ならば」(十分条件)という意味に合致しています。

さてここで，問題を論理式できちんと表してみましょう。

まず，A,B,D,Eは無駄に変数を増やしているだけなので
A∧B＝X　，D∧E＝Y　とおくと簡単になりますね。
（見やすくするため，∧を・で，∨を＋で表すことにし，括弧に{[()]}を使ってます。）

質問者の問題(全体)を論理式で表すと次のようになります。

Ｑ＝{[(X⇒C)∧(Y⇒F)∧(C∧F⇒G)] ⇒ (X∧Y⇒G)｝
　＝{[(X⇒C)・(Y⇒F)・(C・F⇒G)] ⇒ (X・Y⇒G)｝
　 (⇒を上記定義式で表します。全体と内部の⇒に注意。)
　＝{￢[(￢X＋C)・(￢Y＋F)・(￢(C・F)＋G)]＋[￢(X・Y)＋G]｝
　（最初の￢をド・モルガンの定理で括弧内に分配）
　＝{(X・￢C)＋(Y・￢F)＋(C・F・￢G）}＋(￢X＋￢Y＋G)｝
　（後ろの項を前に移動して簡単化しやすいペアを作る）
　＝(￢X＋X・￢C)＋(￢Y＋Y・￢F)＋（G＋￢G・C・F）
　（分配法則：￢P＋P・Q＝(￢P＋P)・(￢P＋Q)＝1・(￢P＋Q)＝￢P＋Q など）
　＝(￢X＋￢C)＋(￢Y＋￢F)＋(G＋C・F）
　＝￢X＋￢C＋￢Y＋￢F＋G＋C・F
　（さらにCについてまとめて）
　＝￢X＋(￢C＋C・F)＋￢Y＋￢F＋G
　＝￢X＋￢C＋F＋￢Y＋￢F＋G
　（ORはどれか一つでも真なら真）
　＝F+￢F＋・・・・＝１

結局，全体の問題文を表す論理式Ｑは定数１となり,恒真式となります．

なお，論理式の意味がよく分かっていれば，こんな煩雑なことをしなくても
X,Yの真偽すべての組み合わせについて⇒の意味を考えて，
X=0またはY=0の場合はＱの結論部分（X∧Y⇒G)＝1だからＱ＝１
X=Y=1のとき,C=F=1 ゆえに G=1だから（X∧Y⇒G)＝1
で、これを真理値表にまとめれば、これでも立派な証明になる。