全称記号∀、存在記号∃が複数あるときの否定

質問

￢∀x P(x) ⇔∃￢P(x)
￢∃x P(x) ⇔ ∀￢P(x)
でありますが、

(1)￢( ∀x　∃y P(x,y) )
(2)￢( ∀x ∀y ∃z P(x,y,z) )
などのように、∃と∀が同時に使われている際の否定はどのように解釈すればいいのでしょうか

(1)は∃x ∀y ￢P(x,y)となりますよね…
これはどのようにして計算されたのでしょうか…。

回答No.2

中村 拓男（@tknakamuri） · ベストアンサー

∀x∃y P(x,y) は厳密に書くと

∀x(∃y P(x,y))

です。ですから
￢∀x P(x) ⇔∃x￢P(x)
￢∃x P(x) ⇔ ∀x￢P(x)
を順に当てはめてゆけば答えが得られます。

これより ∀x や ∃x を括りだすパターンの方が
面白いですよ。良い練習になります。

∃x P(x)∨∀x Q(x) ⇔∃x [P(x)∨Q(x)]
∀x P(x)∧∀x Q(x) ⇔∀x [P(x)∧Q(x)]
∀x P(x)∨∀x Q(x) →∀x [P(x)∨Q(x)]
∃x P(x)∧∃x Q(x) ←∃x [P(x)∧Q(x)]

お礼

回答ありがとうございます。
とてもよく理解できました。

最後の変形とても面白いです！

回答No.3

Caper

● 簡単な例に取り組んでみては、いかがでしょうか。∀ と ∃ を理解することが、少しは楽になるかもしれません。

● ∀x P(x) と ∃x P(x) について

　 例えば、全体集合 (= 普遍集合 ) U を、いま、自然数全体の集合と定めるとします。すなわち、変数 x の変域を、いま、自然数全体の集合と定めるとします。自然数全体の集合は、{1, 2, 3, … } と表記されることが多々あります。

　 ∀x P(x) ≡ P(1)∧P(2)∧P(3)∧ …
　 ∃x P(x) ≡ P(1)∨P(2)∨P(3)∨ …

　 なお、≡ は「 同値 」を意味する記号です。∧ は「 かつ 」を意味する記号です。∨ は「 または 」を意味する記号です。

● 説明を簡略化するために、変数 x, 変数 y, 変数 z のいずれの変域も {1, 2} と定めるとします。

　 ￢(∀x P(x)) ≡ ￢(P(1)∧P(2)) ≡ (￢P(1))∨(￢P(2)) ≡ ∃x (￢P(x))
　 ￢(∃x P(x)) ≡ ￢(P(1)∨P(2)) ≡ (￢P(1))∧(￢P(2)) ≡ ∀x (￢P(x))

1) ￢(∀x (∃y P(x, y)))

　 以下において、P(x, y) を Pxy と表記することにします。

　 ￢(∀x (∃y Pxy))
　 ≡ ￢(∀x (Px1∨Px2))
　 ≡ ￢((P11∨P12)∧(P21∨P22))
　 ≡ (￢(P11∨P12))∨(￢(P21∨P22))
　 ≡ ((￢P11)∧(￢P12))∨((￢P21)∧(￢P22))
　 ≡ ∃x ((￢Px1)∧(￢Px2))
　 ≡ ∃x (∀y (￢Pxy))

2) ￢(∀x (∀y (∃z P(x, y, z))))

　 以下において、P(x, y, z) を Pxyz と表記することにします。

　 ￢(∀x (∀y (∃z Pxyz)))
　 ≡ ￢(∀x (∀y (Pxy1∨Pxy2)))
　 ≡ ￢(∀x ((Px11∨Px12)∧(Px21∨Px22)))
　 ≡ ￢(((P111∨P112)∧(P121∨P122))∧((P211∨P212)∧(P221∨P222)))
　 ≡ (￢((P111∨P112)∧(P121∨P122)))∨(￢((P211∨P212)∧(P221∨P222)))
　 ≡ ((￢(P111∨P112))∨(￢(P121∨P122)))∨((￢(P211∨P212))∨￢((P221∨P222)))
　 ≡ (((￢P111)∧(￢P112))∨((￢P121)∧(￢P122)))∨(((￢P211)∧(￢P212))∨((￢P221)∧(￢P222)))
　 ≡ ∃x (((￢Px11)∧(￢Px12))∨((￢Px21)∧(￢Px22)))
　 ≡ ∃x (∃y ((￢Pxy1)∧(￢Pxy2)))
　 ≡ ∃x (∃y (∀z (￢Pxyz)))

● 以下の記述は、補足です。よろしければ、お読みください。

　 論理学では、自然数全体の集合を、{1, 2, 3, … } としないで、{0, 1, 2, 3, … } とすることがあるようです。ご注意ください。

　 冒頭における ∀x P(x) と ∃x P(x) という表記には、全体集合 U が盛りこまれていません。全体集合 U を盛りこんだ表記としては、例えば、次のものがあります。→ は「 ならば 」を意味する記号です。

　 全称
　 ∀x ∈ U (P(x))
　 ∀x ((x ∈ U)→P(x))

　 存在
　 ∃x ∈ U (P(x))
　 ∃x ((x ∈ U)∧P(x))

　 いずれも、1つ目 の表記は略式であるようです。注目していただきたいのは、それぞれの 2つ目 の表記です。(x ∈ U) と P(x) との間に位置する記号が異なります。

● 私はそこつ者です。以上の記述の中にあやまりが含まれている可能性は高いです。まちがっていましたら、ひらにごめんなさい。
　 また、理解しづらい個所がございましたら、[ 補足 ]欄 を利用するなどして、遠慮なくお知らせください。

お礼

回答ありがとうございます。
おかげさまで具体的なイメージが湧きました。
またよろしくおねがいします！

回答No.1

stomachman

> ￢∀x P(x) ⇔∃￢P(x)

> ￢∃x P(x) ⇔ ∀￢P(x)

いや違いまっせ。

￢∀x P(x) ⇔∃x￢P(x)
￢∃x P(x) ⇔ ∀x￢P(x)
です。

> (1)￢( ∀x　∃y P(x,y) )

解釈も何もない。単に、外から順にド・モルガンやってけばいいだけです。

￢∀x∃yP(x,y)
∃x￢∃yP(x,y)
∃x∀y￢P(x,y)


> (2)￢( ∀x ∀y ∃z P(x,y,z) )

￢∀x∀y∃zP(x,y,z)
∃x￢∀y∃zP(x,y,z)
∃x∃y￢∃zP(x,y,z)
∃x∃y∀z￢P(x,y,z)

お礼

回答ありがとうございました！
おかげさまで理解できました。