授業のホームページ

理解度確認問題（一階述語論理）

（本ページは今後更新する可能性があります．最後の日付を確認して下さい．）

「一階述語論理」のスライドの最後にある練習問題（以下に再掲）を再度検討しよう．

練習問題：指定された述語記号や関数記号を使って，「　」内のそれぞれの文を一階述語論理式で表現せよ．

v(X) : X は野菜である，e(X) : 私は X を食べる
1. 「野菜以外（の食べ物）は何でも食べます」
2. 「野菜は食べません」
3. 「食べる野菜も食べない野菜もあります」
p(X,Y) : X は Y の親である， X=Y : X と Y は同一人物である）
1. 「どんな人にも，親がちょうど二人いる」
述語記号は数学の等号や不等号（＝，＜など），関数記号は数学の ×（掛算），定数記号は自然数および問題文に出てくる記号のみを使用
1. 「k はm とn の公約数である」
2. 「k は素数である」

以下に，いくつかの問について誤答例（完全に間違っているものから惜しいものまで含みます）を示します．色が赤に近いものほど大きな誤りです．これをヒントに，すべての問の正解を書いてみてください．提出は不要ですが，自信がない場合は上田あてに質問をしてください．アドレスは ueda.thisistoberemoved@ueda.info.waseda.ac.jp から ".thisistoberemoved" を取り除いたものです．

答案が構文的に正しい論理式になっていれば，表現された内容が「どのくらい惜しいか」によって部分点を与えることもできますが，論理式の形になっていないもの，特に述語記号の引数に論理式を書いてしには特に注意してください．限定記号（∀，∃）のつけ忘れや余分な限定記号も，論理式の内容を根本的に変えてしまうので要注意です．

『野菜以外は何でも食べます』
- ∀X(e(v(￢X)))
- ∀X(e(￢v(X)))
- e(∀X(￢v(X)))
  - 上の三つはそもそも一階述語論理式の形をなしていない（ X≦(Y≠3) が不等式の形をなしていないのと同じ）．この類の解答をした人は，一階述語論理式の構文規則を特によく復習すること．
- ∀X(￢v(X) ⇒ e(v(X)))
  - これもやはり構文規則違反．ただし，１ヶ所直せば正解になるので，うっかりミスと見ることもできる．
- ￢v(X) ⇒ e(X)
  - 一階述語論理式にはなっているが，限定記号の正しい使い方ができるかどうかを見る問題で限定記号を明示していないのは（かなり）まずい．
- ∀X(￢v(X)) ⇒ e(X)
  - 限定記号は正しいが，導入された局所変数（束縛変数）の有効範囲（括弧を閉じる場所）が誤り．最後の X が自由変数になってしまっている．括弧の場所を一つ直せば正解になるが，論理式を木構造で考えると大きな間違いということになってしまうので，十分注意してほしい．
- ∀X(￢v(X) ∧ e(X))
  - これだと「世の中のすべての（食べ）物は野菜ではなくて，しかも私はそれを食べる」になってしまう．
『食べる野菜も食べない野菜もあります』
- ∃X∃Y(v(X) ⇒ e(X)，v(Y) ⇒ ￢e(Y)，￢(X＝Y))
- ∃X(e(v(X)) ∧ ￢e(v(X)))
  - 上の二つも一階述語論理の式になっていない（コンマは論理記号ではない）．
- ∃X(v(X) ⇒ e(X)) ∧ ∃X(v(X) ⇒ ￢e(X))
  - 野菜以外の食べ物が世の中にあったら，∧ の左も右も真になってしまう． 「『～な～がある』という自然言語文を訳したら ∃X(　⇒　) という形にはならない」 という授業中の注意を思い出してほしい．
- ∃X∃Y(v(X)∧v(Y) ⇒ e(X) ∧ ￢e(Y))
  - これも ⇒ の使い方がおかしい．∃ から始まる式の原則に違反．
- ∀X∀Y(v(X) ⇒ e(X) ∨ v(Y) ⇒ ￢e(Y))
  - まずこれだと，∨ が ⇒ よりも強く結びつくので ∀X∀Y(v(X) ⇒ ((e(X) ∨ v(Y)) ⇒ ￢e(Y))) という意味になってしまう．おそらく ∀X∀Y((v(X) ⇒ e(X)) ∨ (v(Y) ⇒ ￢e(Y))) のつもりと思うが，これは「（私は）どの野菜も食べるか，野菜は一切食べないかのどちらかだ」という意味で，題意と異なる，というか，正反対の内容である．（しかし，正反対というのはちょっと直せば正解に至るということなので，たとえば下の誤答に比べると高い部分点を与えても良いのかもしれない．）
- ∀X(v(X) ⇒ e(X) ∨ ￢e(X))
  - 気持はわかるが，これだと「どんな野菜も，私は食べるか食べないかのどちらかだ」という，当たり前の主張（恒真式）になってしまっている．たとえば，野菜しか食べない人についても「どんな野菜も，私は食べるか食べないかのどちらかだ」は当てはまってしまう．
- ￢∀X(v(X) ⇒ ￢e(X))
  - 「野菜をまったく食べないわけではない」という意味である．これは「食べる野菜もある」つまり ∃X(v(X) ∧ e(X)) と論理的に同値である．しかしこれに加えて「食べない野菜もある」ことも表現する必要がある．（半分は正解なので，50％の部分点をあげることができます．）
    - ［補足］ ￢∀X(v(X)⇒￢e(X)) と ∃X(v(X)∧e(X)) は論理的に同値である，つまり ￢∀X(v(X)⇒￢e(X)) ⇔ ∃X(v(X)∧e(X)) は恒真である．このこともよく復習して，一階述語論理式の式変形ができるようにしておいてほしい．
『どんな人にも親がちょうど二人いる』
- ∃A∃B∀X(p(A,X) ∧ p(B,X) ∧ ￢(A=B))
- ∀X∃A∃B(p(A,X) ∧ p(B,X) ∧ ￢(A=B))
  - どちらも，親が二人「以上」いるという主張になってしまっている．「ちょうど二人」というためには，「二人以上」と「二人以下」の両方の条件を書かなければならない．
  - さらに一つめは，「世の中すべての人に共通の両親がいる」という主張になっている．異なる種類の限定記号が並ぶときは，順序が非常に重要．
- ∀X∃A∃B(p(A,X) ∧ p(B,X) ∧ ￢(A=B) ∧ ∀W(￢p(W,X)))
  - 「二人以下」も表現しようとした姿勢は買える．しかし，最後の条件は「Xさんには親が（まったく）いない」という内容なので， AさんとBさんが親だという前半の主張とも矛盾してしまう．「Xさんには親がいない」ではなくて「WさんがXさんの親ならば， WさんはAさんかBさんのどちらかと同一人物だ」と書かなければならない．
『k は m と n の公約数である』
- ∃m∃n∃k∃i∃j(m＝i×k ∧ n＝j×k)
- ∀m∀n∀k∃i∃j(m＝i×k ∧ n＝j×k)
  - 『k は m と n の公約数である』は k, m, n に関する主張であるが，上の二つの論理式では，k, m, n がすべて局所変数（束縛変数）（限定記号によって導入された変数）になってしまっている．つまり外からは k, m, n が見えない論理式になってしまっている．しばしば見られる誤答例．
- ∃i∃j(m＝i×k ∧ n＝j×k ∧￢(i=j))
  - 惜しい．条件をつけすぎた．4 は 8 と 8 の公約数であるが，上記の式はこのケースを排除してしまった（が，この解答にはかなり良い部分点をあげることができます）．
  なお上の解答は小文字の変数を使っています．授業では原則として変数は大文字にしました．それにならうと ∃I∃J(m＝I×k ∧ n＝J×k ∧￢(I=J)) となります．こちらの方が，どれが定数でどれが変数か明確に意識できるので分かりやすかもしれません．

Last update: July 14, 2009