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

●問1

命題の組 Ａ⇒(Ｂ⇒Ｃ) と Ａ∧Ｂ⇒Ｃ が論理同値かどうか，理由と共に述べよ．

●問2

ここでは，整数を対象とする論理式を扱う．つまり，変数の変域が整数全体の
集合Ｚであると約束し，x∈Ｚ などを暗黙の了解と考えて省略する．

(1) 整数に関する主張「3倍すると奇数になる数を2乗しても奇数になる」を
    論理式で表せ．整数 x に関する性質「x は奇数である」を「x:奇」で表すこと．

(2) この主張が正しいことを証明せよ．証明の方針(何を仮定して何を導くかなど)を
    明示すること．

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

●答1 (真理表と論理同値)

どちらの命題も，Ａ,Ｂ,Ｃ が順に 真，真，偽 のときだけ偽，その他の場合は
真となり，両者の真偽は常に一致する．よって，二つの命題は論理同値である．

［解説］

含意(⇒)と論理積(∧)の真理値の求め方を確認する．含意については偽になる場合を，
論理積については真になる場合を考えると，手早く計算できる．
Ａ⇒(Ｂ⇒Ｃ) が偽となるのは，Ａ が真で Ｂ⇒Ｃ が偽の場合であり，
Ｂ⇒Ｃ が偽となるのは，Ｂ が真で Ｃ が偽の場合である．
また，Ａ∧Ｂ⇒Ｃ が偽となるのは，Ａ∧Ｂ が真で Ｃ が偽の場合であり，
Ａ∧Ｂ が真になるのは，Ａ と Ｂ が共に真の場合である．

各命題の真理表を書き，二つの表の対応する行の値が一致することを調べてもよい．
基本命題が Ａ,Ｂ,Ｃ の三つからなる場合は，真偽の組み合せが 8 (＝2^3) 通りある．

あるいは，論理法則（恒真な同値命題）を使って同値変形してもよい
(教科書 p.48 例題2.5 を参照)．

●答2 (含意の連鎖による含意の証明)

(1) 3x:奇 ⇒ x^2:奇
(2) (教科書 p.46 例題2.3 を参照)

［解説］

(1) 全称を明示して ∀x (3x:奇 ⇒ x^2:奇) と書いてもよい．また，
∀x (∀y (y＝3x ⇒ y:奇) ⇒ ∀z (z＝x^2 ⇒ z:奇)) などとも同値である．

(2) 証明すべき主張は「Ａ⇒Ｂ」の形をしている．この含意の直接証明も間接証明も
うまくいかないとき，前提Ａと結論Ｂの間に別の主張Ｃを挟んで，Ａ⇒Ｃ と Ｃ⇒Ｂ
の二つの含意に分けて証明してもよい．

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

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