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

●問1

0変数の関数記号(対象定数) c，1変数の関数記号 f，1変数の述語記号 P，
2変数の述語記号 R，を記号として使う言語について考える．
この言語に対する構造を与えるため，対象領域を非負整数全体の集合Ｎとし，
各記号の解釈 [・] を次式で定める．

[c]      ＝ 0
[f](n)   ＝ n+2
[P](n)   ＝ 1 (n は偶数)，      [P](n)   ＝ 0 (その他)
[R](m,n) ＝ 1 (m≦n)，           [R](m,n) ＝ 0 (その他)

構造 (Ｎ, [・]) のもとでの次の各論理式の真偽を，理由と共に述べよ．
(1) P(f(c))
(2) ∀y R(f(c), y)
(3) ∀x∀y ( R(x,y) ⇒ R(f(x),f(y)) )

●問2

次の各論理式が恒真かどうかを，理由と共に述べよ．

(1) ∃x(P(x)∧Q(x))
(2) ∃y∀x R(x,y) ⇒ ∀x∃y R(x,y)

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

●答1 (述語論理の意味論)

(1) 真（0+2 は偶数）
(2) 偽（0+2 は非負整数の最小値ではない）
(3) 真（非負整数 m,n が m≦n を満たせば，m+2≦n+2 も成立）

［解説］

問題に与えられた構造は，c を「0」という非負整数，f を「〜に2を足す」という
関数，P を「〜は偶数」という性質，R を「〜は〜以下」という関係，として
解釈している．

この構造のもとで，各論理式は次の意味をもつ．
P(f(c)) は「0+2は偶数」，∀y R(c,y) は「0+2は非負整数の最小値」，
∀x∀y ( R(x,y) ⇒ R(f(x),f(y)) ) は「関係 ≦ は両辺に2ずつ足して保たれる」．
これらの論理式の解釈から，真偽が判定できる．

構造 (U, [・]) のもとでの論理式の真理値を計算しても，真偽が判定できる．

(1) P(f(c)) の (U, [・]) での真理値

   [P]([f]([c]))
＝ [P]([f](0))          ([c] の定義)
＝ [P](2)               ([f] の定義，0+2 ＝ 2)
＝ 1                    ([P] の定義，2 は偶数)

(2) ∀y R(f(c), y) の (U,I) での真理値

   min{ [R]([f(c)], n) | n∈Ｎ }
＝ min{ [R](2, n) | n∈Ｎ }      ([f], [c] の定義)
＝ min{ 0, 1 }                  ([R] の定義，[R](2, n) は n＝0 で 0，n＝2 で 1)
＝ 0

(3) ∀x∀y ( R(x,y) ⇒ R(f(x),f(y)) ) の〈U,I〉での真理値

   min{ min{ max{  1 - [R](m,n) , [R]([f](m),[f](n)) } | n∈Ｎ } | m∈Ｎ }
＝ min{ min{ 1 | n∈Ｎ } | m∈Ｎ }
＝ 1

1行目から2行目への式変形では「m≦n のとき m+2≦n+2」という性質を使う．
この性質は，[R] と [f] の定義から，「[R](m,n)＝1 のとき [R]([f](m),[f](n))＝1」
を意味する．

●答2 (述語論理の恒真性)

(1) 恒真ではない．なぜなら，自然数全体の集合で，P を「偶数である」，
Q を「奇数である」と解釈すると，与えられた論理式が偽となるからである．

［解説］

論理式が恒真でないことを示すには，真理値が偽となる構造を一つ示せばよい．
解答で示した構造以外にも，非空集合上で P, Q を常に偽の述語と解釈すれば，
与えられた論理式は偽となる．P, Q を解釈した述語の真理集合の共通部分に
要素が存在しなければ，どんな解釈でも良いので，真理値が偽となる構造は
多数ある．

(2) 恒真である．自然演繹による証明図を以下に示す．

                      2
                 ∀x R(x,b)
                 ─────∀E
                   R(a,b)
         1       ─────∃I
   ∃y∀x R(x,y) ∃y R(a,y)
   ────────────∃E 2
          ∃y R(a,y)
        ───────∀I
        ∀x∃y R(x,y)
───────────────⇒I 1
∃y∀x R(x,y) ⇒ ∀x∃y R(x,y)

［解説］

論理式が恒真であることを示すには，自然演繹で証明可能なことを示せばよい．
上の証明図で，∃E と ∀I の規則を使う際，変数条件が成り立つのを確かめる．
次の図は，変数条件を満たさないため，自然演繹の証明として認められない．

                       2
                  ∀x R(x,b)
          1       ─────∀E
    ∃y∀x R(x,y)   R(a,b)
    ───────────∃E 2
            R(a,b)
          ─────∃I
          ∃y R(a,y)
        ───────∀I
        ∀x∃y R(x,y)
───────────────⇒I 1
∃y∀x R(x,y) ⇒ ∀x∃y R(x,y)


∀Iの規則適用については，結論 ∀x∃y R(x,y) で有効な仮定 1 に
変数 a が現れないため変数条件を満たす．しかし，∃Eの規則適用については，
前提 R(a,b) に b が自由変数として出現するため，変数条件を満たさない．

なお，∃E と ∀I の規則を解答と逆の順に使う次の証明も可能．

                     2
                ∀x R(x,b)
                ─────∀E
                  R(a,b)
                ─────∃I
                ∃y R(a,y)
      1       ───────∀I
∃y∀x R(x,y)  ∀x∃y R(x,y)
──────────────∃E 2
        ∀x∃y R(x,y)
───────────────⇒I 1
∃y∀x R(x,y) ⇒ ∀x∃y R(x,y)

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

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