離散数学の問題

質問

離散数学の勉強を始めました。以下の問題を解きたいのですが、分かりません。お分かりの方、教えて頂けないでしょうか。quantifiersを使わずに、命題で表せという問題です。
Suppose we are considering the domain of just two numbers D = {0, 1}. Convert the following propositions containing quantifiers to propositions that do not use any quantifiers.
For example, ∀x P(x) can be restated as P(0) ∧ P(1).
１. ∀x ∃y P(x, y)
２. ∃x P(x) ∨ (∀y Q(x, y))
３. ￢ (∀x ∃y [P(x) → Q(y)])

回答No.2

jmh

> (P(０) ∨ P(１)) ∨ (Q(x, ０) ∧ Q(x, １))
>
えー、ｘが残っちゃうの？

> ￢ ([(P(０)→Q(０)) ∨ P(１)→Q(１)] ∧ [(P(０)→Q(０)) ∨ P(１)→Q(１)])
>
￢１．のＰを［Ｐ（ｘ）→Ｑ（ｙ）］にすると、そうなる？

> なるほど、そういうことですね！わかりました。
>
じゃぁ、Ｄ＝｛０｝だとどうなるか？

お礼

> えー、ｘが残っちゃうの？
こうでしょうか？

（２）∃x P(x) ∨ (∀y Q(x, y))
↓
∃x P(x) ∨ (Q(x, ０) ∧ Q(x, １))
↓
(P(０) ∨ (Q(０, ０) ∧ Q(０, １)) ∨ (P(１) ∨ (Q(１, ０) ∧ Q(１, １))

（３）￢ (∀x ∃y [P(x) → Q(y)])
↓
￢ (∀x [(P(x)→Q(０)) ∨ P(x)→Q(１)]
↓
￢ ([(P(０)→Q(０)) ∨ P(０)→Q(１)] ∧ [(P(１)→Q(０)) ∨ P(１)→Q(１)])

回答No.1

jmh

１. ∀ｘ∃ｙＰ（ｘ，ｙ）
　　　　　↓
　　∀ｘＰ（ｘ，０）∨Ｐ（ｘ，１）
　　　↓
　　（Ｐ（０，０）∨Ｐ（０，１））∧（Ｐ（１，０）∨Ｐ（１，１））

For example, … に従って、∀ｘＰ（ｘ）をＰ（０）∧Ｐ（１）に、∃ｘＰ（ｘ）をＰ（０）∨Ｐ（１）に、それぞれ書き換えてみました。

お礼

結局、回答は以下の通り。
xはfree variable、Precidence of Quantifiers。

（２）∃x P(x) ∨ (∀y Q(x, y))
↓
(P(０) ∨ P(１)) ∨ (Q(x, ０) ∧ Q(x, １))

補足

jmhさん、ご回答有り難うございます。
なるほど、そういうことですね！わかりました。
そうすると、（２）と（３）は以下のように考えましたが如何でしょうか。もしおわかりでしたらご教示頂きたいです。

（２）∃x P(x) ∨ (∀y Q(x, y))
↓
(P(０) ∨ P(１)) ∨ (Q(x, ０) ∧ Q(x, １))

（３）￢ (∀x ∃y [P(x) → Q(y)])
↓
￢ (∀x [(P(x)→Q(０)) ∨ P(x)→Q(１)]
↓
￢ ([(P(０)→Q(０)) ∨ P(１)→Q(１)] ∧ [(P(０)→Q(０)) ∨ P(１)→Q(１)])