述語論理についての質問です。

質問

下記の２式について理解できず困っています。説明をお願いします。

∀x [P(x) →ψ] ⇔ ∃x P(x) →ψ

（ψは変数を含まないとする）

この左の式と右の式が同じである意味がわかりません。
できれば例文を使って教えていただければありがたいです。

∃x [P(x) →ψ] ⇔ ∀x P(x) →ψ

（ψは変数を含まないとする）

同じく、この左の式と右の式が同じである意味がわかりません。
できればこちらも例文を使って教えていただければありがたいです。

どうぞよろしくお願いします。

回答No.5

noname#221368

トリビアルでない例が思いつけなかったので、一般的な意味としての話になります。

　　∀x [P(x) →ψ] ⇔ ∀x[P(x)] →ψ　⇒　∃x[P(x)] →ψ　　　(1)

　まず、(1)の最左辺から中辺への移行は良いですよね？。「ψは変数xを含まないとする」の条件です。中辺から最右辺への移行は、∀x[P(x)]　⇒　∃x[P(x)]　が成り立つという、論理の一般規則です。

　ところで中辺の言ってる事は、「P(x)を成り立たせる全てのxで、ψが成り立つ」です。これはP(x)の外延集合{x|P(x)}が、ψの外延集合に含まれるという事です。実際、「ψは変数xを含まない」ので、ψの外延集合はx全体とみなせます（ψが成り立つなら）。雑に書けば、{x|P(x)}⊂{x|ψ}＝{x|任意のx}、です。よって最右辺、

　　「P(x)を満たすxが一つでもあれば、ψが成り立つ」　　　　　(2)

になります。ふつうはψ(x)で、ψ(x)が成り立つかどうかもxに依存しますが、「ψは変数xを含まない」のでこれが言えます。これが中辺から最右辺への移行の意味です。そしてこの状況は、最左辺から中辺への移行の段階で、形式的には予定されていた事になります。

　　∃x [P(x) →ψ] ⇔ ∃x[P(x)] →ψ⇒　∀x [P(x)] →ψ　　　(3)

　(3)の最左辺から中辺への移行は、(1)と同じです。中辺は(2)です。ところが、∀x [P(x)]からは必ず∃x [P(x)]を導けますから、その結果と中辺を合わせると、最右辺∀x [P(x)] →ψが、∃x[P(x)] →ψから導ける事になります。∃x[P(x)]のxは、∀x [P(x)]のどのxでもOKですから（(2)の言ってる事）・・・。そしてこの状況は、最左辺から中辺への移行の段階で、形式的には予定されていた事になります。

　以上の流れで行くと（同値ですが、同じでない証明図は沢山あります）、(2)がポイントで、それは、「ψは変数xを含まない」事を表しています。

　　(1)と(3)を合わせれば、質問文の関係式は出てきます。

　形式論理のシェマって、実に良くできてますよね？(^^；)。

　出来が良すぎて（スタイリッシュ過ぎて）、悩みますよね・・・(^^；)。

回答No.4

itshowsun

すいません。まだ訂正がありました。
最後の式
　　∃x[P(x)→ψ]　⇔　∃xP(x)→ψ
は
　　∀x[P(x)→ψ] ⇔ ∃xP(x)→ψ
です。
　第2の問題は同じようにできます。

補足

大変わかりやすく説明していただいてありがとうございました。

もう一つ質問なんですが、説明していただいた質問の左右の式を
日本語でいうとどのように解釈すればいいのでしょうか？

例えば　∀X people(X) → dead(X) の場合、
日本語では　”すべての人間は死ぬ”　と解釈できると思いますが、
質問の左右の式はこのように日本語で表すとどのようになるのでしょうか。

お手数をお掛けしますが、これも教えていただけるとありがたいです。
よろしくお願いします。

回答No.3

itshowsun

NO.2で
　　∃xP(x) = ￢∃x￢P(x)
は
　　∃xP(x) = ￢∀x￢P(x)
に訂正します。

回答No.2

itshowsun

問題が古典論理であるとします。このとき、
　　φ→ψ = ￢φ∨ψ
　　∀xP(x) = ￢∃x￢P(x)
　　∃xP(x) = ￢∃x￢P(x)
が成立します。よって
　　∀x[P(x)→ψ] = ∀x(￢P(x)∨ψ)
　　　　　　　　　 = ∀x￢P(x)∨ψ
　　　　　　　　　 = ￢(￢∀x￢P(x))∨ψ
　　　　　　　　　 = ￢∃xP(x)∨ψ
　　　　　　　　　 = ￢(∃xP(x))∨ψ
　　　　　　　　　 = ∃xP(x)→ψ
よって
　　∃x[P(x)→ψ]　⇔　∃xP(x)→ψ
となります。

回答No.1

entap

ψは変数を含まないとする、とは、変数xを含まないとする、ということでしょうか?

補足

そのとおりです。

もうしわけありません、書き忘れていました。

ψは変数xを含まないとする。　です。

よろしくお願いします。