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

●問1

自然演繹の形式体系で，次の三つの仮定から S を導く導出を作れ．
・ (P⇒Q) ⇒ (R⇒S)
・ R ⇒ (P⇒Q)
・ R

●問2

次の各命題を論理式で表し，真偽を述べ，証明または反証せよ．
整数，変数，論理記号，括弧，不等号 ≧，約数の記号 | を使ってよい．
なお，対象領域は整数全体の集合とする（つまり x∈Ｚ 等を明示する必要はない）．

(1) ある整数は，2以上のどの整数も約数にもたない．
(2) どんな整数についても，それ以上の偶数がある．

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

●答1 (自然演繹における導出)

(教科書 p.111 確認問題3.2の解答と解説を参照)

●答2 (論理式による表現：全称と存在の併用， 証明法：存在と全称の証明)

(教科書 p.107 確認問題1.21の解答と解説，教科書 p.51 例題2.8 を参照)

［解説］

存在命題 ∃x P(x) を証明するには，P(x) を満たす対象 x の例を１つ示す．
全称命題 ∀x P(x) を証明するには，任意の対象 x について P(x) を示す．
特に，∀x ∃y R(x,y) の形の命題を証明するには，
任意の対象 x に応じて，R(x,y) を満たす対象 y を選ぶ対応付けを与えればよい．

(1) の ∀y (y≧2 ⇒ ¬ y|x) の部分や (2) の ∃y (y≧x ∧ 2|y) の部分が，
条件付きの全称や存在であることに注意する．

なお，| を使わずに ＝ と ・ を使って表すなら，x|y は ∃k y＝k・x と表せるので，
(1) は ∃x ∀y (y≧2 ⇒ ¬ ∃k x＝k・y)
(2) は ∀x ∃y (y≧x ∧ ∃k y＝2・k)
とも書ける．

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

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