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

●問1

命題 (Ａ⇒Ｂ)∧(Ｂ⇒Ａ) について，次の設問に答えよ．

(1) この命題の真理表を，結合子の下に 0, 1 を並べる形式で示せ．

(2) 上記の命題と論理同値な（つまり，真理表が一致する）命題を一つ挙げよ．
    ただし，論理結合子の個数がなるべく少ないものを挙げること．

●問2

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

(1) x が y の約数であることを表す記法 x｜y を使って，次の主張を論理式で表せ．
    (x-1) の 2 乗が 4 で割り切れるならば，x は偶数ではない．

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

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

●答1 (真理表)

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

［解説］

含意⇒と同値⇔の真理表はすぐに思い出せるようにしておくとよい．
論理同値な論理式を見付けるには，次回以降に学ぶ論理法則による同値変形も有用．
なお，「論理結合子の個数が少ないもの」という条件を取り除くと，
与えられた論理式が (Ａ∧Ｂ)∨(¬Ａ∧¬Ｂ) や (¬Ａ∨Ｂ)∧(Ａ∨¬Ｂ)
などと論理同値であることも，真理表を書いて確かめられる．

●答2 (証明法：含意の間接証明)

(1) 4｜(x-1)^2 ⇒ ¬ 2｜x

(2) (教科書 p.45 例題2.2 を参照)

［解説］

証明すべき主張は「Ａ⇒Ｂ」の形をしている．この含意が直接証明しにくいなら，
間接証明（対偶の証明や背理法による証明）を試すとよい．

・対偶の証明：　結論の否定 ¬Ｂ を仮定して前提の否定 ¬Ａ を導く．
・背理法の証明：前提 Ａ と結論の否定 ¬Ｂ を仮定して矛盾を導く．


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

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