━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
数理論理学 確認問題10
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

●問1

論理式 ∀m ∃n (m≦n ∧ ¬ m＝n) について問題に答えよ．

(1) この論理式を (補助資料集のp.14に示す形式の) 木構造で表せ．

(2) この論理式の部分論理式の総数を答えよ．

●問2

自然数に関する次の性質について問題に答えよ．

        ・ 0∈X
        ・ n∈X ⇒ n＋2∈X

(1) 二つの性質を同時に満たす自然数の集合 X の例を二つ示せ．

(2) そのような集合のうち，包含関係について最小のものを {n | P(n)} の形に表せ．
    ただし，P(n) は自然数 n に関する述語とする．

──────────────────────────────────────

●答1 (論理式の再帰構造)

(1) 論理式 ∀m ∃n (m≦n ∧ ¬ m＝n) を表す木構造を以下に示す．

         　　∀ｍ
         　　 ｜
         　　∃ｎ
          　　｜
        　　　∧
        　　／　＼
        　≦　　　¬　
         ／＼　　 ｜
        ｍ　ｎ　  ＝
        　　　　 ／＼
        　　　　ｍ　ｎ

(2) 6個

［解説］

(1) 式の構文的な構造を表す木構造のことを構文木という．
与えられた論理式の各部分論理式を [ ] で囲んだものを以下に示す．

        [∀m [∃n [ ( [m≦n] ∧ [¬ [m＝n]] ) ]

論理結合子 ¬ は述語に付くので，¬m の部分でなく ¬m＝n が論理式である．
なお，量化子を使った論理式 ∀x P(x) や ∃x P(x) の
∀や∃の直後の変数を葉に独立させて，次の図のように構文木で表す方法もある．

        　　∀　　       　　∃
        　／　＼　      　／　＼
        ｘ　　　Ｐ      ｘ　　　Ｐ
        　　　　｜      　　　　｜
        　　　　ｘ      　　　　ｘ

(2) 部分論理式を全て列挙すると，m＝n，¬m＝n，m≦n，¬m＝n∧m≦n，
∃n (¬m＝n∧m≦n)，∀m ∃n (¬m＝n∧m≦n)，となる．
論理式全体も部分論理式の一つであることに注意する．
なお，命題記号・述語記号・論理結合子・量化子 のどれかが根になっている部分木が
部分論理式に対応する．

●答2 (帰納的定義)

(1) 偶数である自然数全体の集合 {2n | n∈Ｎ} や 自然数全体の集合 Ｎ や
    集合 {2n | n∈Ｎ} ∪ {2n+1 | n∈Ｎ, n≧5} など．

(2) {n | ∃k∈Ｎ n＝2k}

［解説］

いくつかの性質を満たす集合は，一般には，複数存在することも，
一つも存在しないこともある．集合の帰納的定義は，ある性質を
満たす最小の集合として与えることが多い．この問題では，
二つの性質を満たす最小の集合は偶数である自然数全体の集合である．

定義を与える文脈では，「最小の」という言葉を省くことが多い．
例えば「集合 Y を，0∈Y と n∈Y ならば n＋2∈Y との二つの性質を満たす
ものと定義する」という場合には，Y は偶数である自然数全体の集合である．

集合 {n | ∃k∈Ｎ n＝2k} は {2n | n∈Ｎ} と同じ集合を表す．
また，約数の記法 x|y が許されるなら，{n | 2|n} と書いても良い
（二つの縦棒のうち，最初のものは集合 {n | P(n)} を，二つ目は
約数の述語 x|y を表す）．

X が有限集合の場合には，X が問題の二つの性質を満たさない（誤答の例）．
例えば，X＝{0, 2} の場合，n＝2 について，含意の前提 n∈X が成り立つが
結論 n＋2∈X が成り立たないことに注意する．

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
授業のホームページ

山田 俊行
https://www.cs.info.mie-u.ac.jp/~toshi/