述語について成り立つ関係

質問

・∃x｛P(x)⇒Q(x)｝　⇔　｛∀xP(x)⇒∃Q(x)｝　が成り立つ
・｛∃xP(x)⇒∃Q(x)｝　⇒　　∃x｛P(x)⇒Q(x)｝　は成り立つが、その逆は成り立たない

という2つを証明したいのですが、全く分かりません。
ドモルガンは使えそうもありませんし、
P(x)＝｛（P(x)∧Q(x)）∨（P(x)∧Q(x)のバー）｝
という変形などをしたりもしたのですが、やっぱり分かりません。

どなたかお知恵を貸してください。お願いします。

回答No.2

stomachman · ベストアンサー

否定を表すバーは書けないんで、以下では代わりに、数学でよく使われる「￢」を用います。つまり
￢A
とは「Aの否定」という意味です。
　ところで、「⇒」てのをそのまま扱おうとすると混乱しやすいですね。A⇒Bは￢A∨Bという形に書き換えるのが良い。いわば「⇒」は万札であって、小銭に崩すと扱いやすくなります。

●問題１：{∀xP(x)⇒∃xQ(x)} ⇔ ∃x{P(x)⇒Q(x)｝を証明せよ
　まず左辺の
｛∀xP(x)⇒∃xQ(x)｝
ですが、これ、xが２つの別の意味で使われていますんで混乱しやすい。キブンが悪いです。で、全く同じ論理式を
｛∀xP(x)⇒∃yQ(y)｝
と表しても良いのはお分かりでしょう。
　さて｛∀xP(x)⇒∃yQ(y)｝を小銭に崩せば
￢(∀xP(x)) ∨(∃yQ(y))
となります。
　ここで、￢(∀xP(x)) とは「どんなxについてもP(x)が成り立つわけじゃない」という意味ですから、これを∃x(￢P(x)) 「P(x)が成り立たないようなxが少なくともひとつ存在する」と言っても同じことです。つまり、
￢(∀xP(x)) ∨(∃yQ(y))
は
∃x(￢P(x)) ∨ (∃yQ(y))
と同じです。「P(x)が成り立たないようなxが存在するか、或いはQ(y)が成り立つようなyが存在する」という意味ですね。

　一方、右辺の∃x｛P(x)⇒Q(x)｝は、これも小銭に崩せば
∃x(￢P(x)∨Q(x))
と同じことであって、つまり「￢P(x)を満たすか、或いはQ(x)を満たす、そのようなxが存在する」という意味ですが、これがまた
∃x(￢P(x)) ∨ ∃xQ(x)
すなわち「￢P(x)を満たすxが存在するか、Q(x)を満たすxが存在する」と等価であることは、ちょっと考えれば分かるでしょう。
　ただ、この式ではxを２つの別の意味で使っていてキブンが悪いんで、
∃x(￢P(x)) ∨ ∃yQ(y)
と書き換えておきます。

以上の準備によって、問題１は
{∃x(￢P(x)) ∨ ∃yQ(y)}⇔{∃x(￢P(x)) ∨ ∃yQ(y)}
を証明する問題であることが分かりました。ではいよいよ取りかかりましょうか…と思ったら、あれれ、⇔の右辺と左辺は全く同じです。
証明終わり。（え？え？）

●問題２｛∃xP(x)⇒∃xQ(x)｝ ⇒ ∃x｛P(x)⇒Q(x)｝を証明せよ
　左辺
∃xP(x)⇒∃xQ(x)
は、キブンが悪いんで
∃xP(x)⇒∃yQ(y)
と書き換えておきます。さらにこれを小銭に崩しましょう。
￢(∃xP(x))∨∃yQ(y)
となります。ここで、￢(∃xP(x))は「P(x)を満たすようなxは存在しない」って意味であり、すなわち∀x(￢P(x))「どんなxについても￢P(x)である」というのと同じですから、
∀x(￢P(x))∨∃yQ(y)
となります。
　右辺
∃x(P(x)⇒Q(x))
も小銭にしましょう。
∃x(￢P(x)∨Q(x))
そうすると、これが
∃x(￢P(x))∨∃xQ(x)
と等価であることが分かりやすいでしょう？で、キブンを直すために
∃x(￢P(x))∨∃yQ(y)
と書き換えておきましょう。

以上の準備によって、問題２は
{∀x(￢P(x))∨∃yQ(y)}⇒{∃x(￢P(x))∨∃yQ(y)}
を証明する問題であることが分かります。左辺は選言（∨）の形ですから、場合分けすれば良いですね。
(1)∀x(￢P(x))の場合
∀x(￢P(x))とは「xとして何を持ってきても￢P(x)が成り立つ」んですから、「￢P(x)を満たすxが存在する」わけで、∃x(￢P(x))でもあります。だから
∃x(￢P(x))
は真であり、よって右辺
∃x(￢P(x))∨∃yQ(y)
は真です。
(2) ∃yQ(y)の場合
右辺にも∃yQ(y)がありますね。
∃x(￢P(x))∨∃yQ(y)
は真です。
これで
{∀x(￢P(x))∨∃yQ(y)}⇒{∃x(￢P(x))∨∃yQ(y)}
が証明できました。

●問題３ ￢(∃x｛P(x)⇒Q(x)｝⇒｛∃xP(x)⇒∃xQ(x)})を証明せよ
　￢(A⇒B)は(￢B⇒￢A)と等価です（対偶ってやつです）から、
￢{∃xP(x)⇒∃xQ(x)}⇒￢∃x{P(x)⇒Q(x)}
を証明すれば良い訳です。うだうだ言わないで大人しく小銭に換えてみましょう。
　まず左辺の
￢{∃xP(x)⇒∃xQ(x)}
は、問題２の途中経過で出てきた式を流用して
￢{∃x(￢P(x))∨∃yQ(y)}
であり、これはすなわち
{￢∃x(￢P(x))}∧ {￢∃yQ(y)}
と同じで、
{∀x￢(￢P(x))}∧ {∀y￢Q(y)}
とも同じですから、結局
∀xP(x)∧∀y￢Q(y)
と等価です。
　また右辺の
￢∃x{P(x)⇒Q(x)}
もまた、問題２の途中経過から
￢{∀x(￢P(x))∨∃yQ(y)}
であり、これは
￢{∀x(￢P(x))}∧￢{∃yQ(y)}
と同じで、
{∃x￢(￢P(x))}∧{∀y￢Q(y)}
ですから、結局
∃xP(x)∧∀y￢Q(y)
となります。
　以上の準備から、問題３は
{∀xP(x)∧∀y￢Q(y)}⇒{∃xP(x)∧∀y￢Q(y)}
を証明する問題であることが分かりました。
　ここで一般に
A∧B⇒C∧B
というのは
A⇒C
とおんなじ事ですから、問題３は
∀xP(x)⇒∃xP(x)
と等価です。これは自明ですね。
証明おわり～

回答No.1

suima

>>∃x｛P(x)⇒Q(x)｝　⇔　｛∀xP(x)⇒∃Q(x)｝
多分これは、
∃x｛P(x)⇒Q(x)｝　⇔　｛∀xP(x)⇒∃xQ(x)｝
だと思うので、そう解きます。

（⇒）
　∃x｛P(x)⇒Q(x)｝
が前提です。日本語にすれば、
「あるｘにおいて、Pが成り立つならQが成り立つ」
この”あるx”をaとおいておきましょう。
すると、前提はP(a)⇒Q(a)となります。
　今、この前提から｛∀xP(x)⇒∃xQ(x)｝を証明したいわけです。
この式を日本語にすると、
「任意のxに対してPが成り立つとき、あるxに対してQが成り立つ」
ということですね。
　さて、任意のxに対してPが成り立つということは、
もちろんx=aの時もPは成立します。
よって、P(a)が成り立ちます。
　前提はP(a)⇒Q(a)でしたから、Q(a)も成り立ちます。
つまり、x=aにおいてQが成立したわけです。
よって、∃xQ(x)が成立しました。
このとき前提にしたのは、∀xP(x)でしたから、
∀xP(x)⇒∃xQ(x)が成り立ちます。
（証明了）

記号論理学を知っているなら、
↓の書き方の方が分かりやすいかもしれないので、
書いておきますね。

1.∃x｛P(x)⇒Q(x)｝ 1 (H(仮定))
2.P(a)⇒Q(a) 1 (1,∃-E)
3.∀xP(x) 3 (H(仮定))
4.P(a) 3 (3,∀-E)
5.Q(a) 1,3 (2,4,⇒-E)
6.∃xQ(x) 1,3 (5,∃-I)
7.∀xP(x)⇒∃xQ(x) 1 (3-6,⇒-I)
8.∃x｛P(x)⇒Q(x)｝⇒｛∀xP(x)⇒∃Q(x)｝ (1-7,⇒-I)

(←)なのですが、私には証明不可能に思えます。
なぜなら｛∀xP(x)⇒∃xQ(x)｝を前提にしても、
肝心の∀xP(x)が示せないからです。
　あと、2問目も証明不可能に思えます。
単に私の知識が及ばないだけかもしれませんが・・・（汗