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

●問1

次の (1)〜(4) の命題を論理式で表せ．
なお，対象領域は整数全体の集合とし（つまり x∈Ｚ や y∈Ｚ 等の明示は不要で），
x が y の約数であることを x|y と表す．

(1) どの整数も，平方すると正である．
(2) 平方が自分自身に等しい整数が存在する．
(3) x が偶数ならば，x は4の倍数である．
(4) ある偶数は，その平方が4で割り切れない．

●問2

任意の命題 A, B について，以下の同値命題はどれも恒真である．
・ ¬¬A ⇔ A              (二重否定の法則)
・ A∨B ⇔ B∨A            (∨の交換法則)
・ A⇒B ⇔ ¬A∨B   (⇒ の ¬ と ∨ による表現)
これらの論理法則を使って，¬A⇒¬B ⇔ B⇒A が恒真であることを
同値変形により証明せよ．使った論理法則の名称を各行に明示すること．

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

●答1 (論理式による表現：全称と存在)

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

［解説］

量化子の後には必ず述語が続くので，∃x (x^2＝x) や ∀x (x^2＞0) の括弧は省いて
∃x x^2＝x や ∀x x^2＞0 と書いても良い．

●答2 (証明法：同値変形)

同値変形による証明を以下に示す．

   ¬A⇒¬B
⇔ ¬¬A ∨ ¬B      (⇒ の ¬ と ∨ による表現)
⇔ A ∨ ¬B        (二重否定の法則)
⇔ ¬B ∨ A        (∨の交換法則)
⇔ B⇒A           (⇒ の ¬ と ∨ による表現)

［解説］

教科書p.17の確認問題1.7で扱っているように，真理表を使った証明もできる．

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

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