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

●問1

x が y の約数であることを x｜y と表す．次の各文を，論理記号を使って式で表せ．

(1) 2 は 4 の約数であり，かつ，2 は 3 の約数ではない．

(2) 12 は，2 と 3 の倍数だが，128 や 256 の約数ではない．

●問2

整数に関する主張「x, y が奇数のとき x-y が偶数である」について，
次の設問に答えよ．

(1) 主張を分析して，対象と述語をそれぞれ ( ) と [ ] で囲んで示せ．
    ただし，述語の範囲が明確になるように，必要に応じて文を言い換えること．

(2) 主張を論理式で表せ．ただし，整数 z に関する性質「z が奇数である」や
    「z が偶数である」を，z:奇 や z:偶 で表すこと．

(3) 主張が正しいことを定義に沿って証明せよ．ただし，偶数は整数 k を使って
    2k の形に表せる整数，奇数は整数 k を使って 2k+1 の形に表せる整数，
    と定義する．

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

●答1 (論理式による表現：論理結合子)

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

●答2 (証明法：含意命題の直接証明)

(教科書 p.102 確認確認1.3 の解答と解説 や 教科書 p.42 例題2.1 を参照)

［解説］

式に現れる括弧は，記号の優先度を考慮して，誤読を生じない範囲で
適度に省いて読みやすくする．どの括弧が省けるかについては，
解説資料集 p.3「記号の優先度」や p.4「記号による式の組み立て」を参照．

(2) では，記号の優先度の順が 関数記号 > 述語記号 > 論理結合子 であり，
論理結合子の中では，連言 ∧ の方が含意 ⇒ より優先度が高い，という約束の
もとで括弧を省くのが標準的である．括弧を全て補うと次の論理式になる．

        (((x:奇) ∧ (y:奇)) ⇒ ((x-y):奇))

証明すべき主張は「Ａ⇒Ｂ」の形をしているので，直接証明するために
Ａ(が真であること)を仮定して，Ｂ(が真であること)を導けばよい．

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

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