━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 数理論理学 確認問題５ ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
●問1 対象領域(変数の変域)を整数の集合 U＝{0,1,2,3,4,5} とする述語 P(x) が (a) x は 5 以下，(b) x は 0 と異なる，(c) x は偶数，(d) x は 1 と等しい， (e) x は負，の各場合について，次の問題に答えよ． (1) P(x) の真理集合 {x∈U | P(x)} を，要素を並べた形 (たとえば，P(x) が「x は素数」なら {2,3,5}) で表せ． (2) 全称命題 ∀x P(x) の真偽を○×で答えよ． (3) 存在命題 ∃x P(x) の真偽を○×で答えよ． ●問2 ここでは，整数を対象とする論理式を扱う．つまり，変数の変域が整数全体の 集合Ｚであると約束し，x∈Ｚ や y∈Ｚ などを暗黙の了解と考えて省略する． (1) 整数に関する主張「x が奇数であることは x の平方が奇数であることの 必要十分条件である」を論理式で表せ．ただし，x が奇数であることを 「x:奇」で表すこと． (2) この主張が正しいことを証明せよ．証明方針（何を仮定して何を導くか） を明示すること．なお，証明中で「偶数であることは奇数でないことの 必要十分条件である」という整数の性質を使ってよい． ────────────────────────────────────── ●答1 (述語の命題化，全称と存在の意味) (1) (2) (3) (a) {0,1,2,3,4,5} ○ ○ (b) { 1,2,3,4,5} × ○ (c) {0, 2, 4 } × ○ (d) { 1 } × ○ (e) { } × × ［解説］ 述語 P(x) の x を 0, 1 などの対象に置き換えると命題となり，真偽が定まる． 述語 P(x) の量化により得られる ∀xP(x) や ∃xP(x) も命題であり，真偽が定まる． ∀xP(x) が真となるのは，全ての対象 x について P(x) が真となるときである． ∃xP(x) が真となるのは，１つ以上の対象 x について P(x) が真となるときである． この問題では対象領域が {0, 1, 2, 3, 4, 5} という有限集合なので， ∀xP(x) は P(0)∧P(1)∧…∧P(5) と同値であり， ∃xP(x) は P(0)∨P(2)∨…∨P(5) と同値である． なお，(1)(e) の { } は ∅ と同じ0個の要素からなる集合だが， {∅} は空集合1個からなる集合なので誤り ●答2 (証明法：同値の証明，含意の直接証明と間接証明) (1) x:奇 ⇔ x^2:奇 (2) (a) x:奇 ⇒ x^2:奇，(b) x^2:奇 ⇒ x:奇，の二つの含意を示す． (a) の含意は直接証明し，(b) の含意は対偶を証明する． 証明： (=>) (教科書 p.108 確認問題2.1 の証明と解説を参照) (<=) 整数 x が奇数でないと仮定して，x^2 が奇数でないことを導く． x が奇数でない，つまり，偶数であると仮定すると，偶数の定義から， x＝2i を満たす整数 i が存在する．x^2 ＝ (2i)^2 ＝ 4 i^2 ＝ 2 (2 i^2) であり， 2 i^2 は整数だから，j ＝ 2 i^2 と定めると，x^2 ＝ 2j と表せる． よって，偶数の定義から，x^2 は偶数，つまり，奇数ではない． ［解説］ (1) 確認問題3の問1で学んだように，A⇔B は (A⇒B)∧(B⇒A) と論理同値なので， 問題の主張は，次の論理式でも書ける． (x:奇 ⇒ x^2:奇) ∧ (x^2:奇 ⇒ x:奇) また，全称や存在の記号を明示すると次の論理式でも書ける． ∀x (∃i x＝2i+1 ⇔ ∃j x^2＝2j+1) (2) まず，用語の定義を復習する． A⇔B が真のとき，Ａ は Ｂ の（Ｂ は Ａ の）必要十分条件であるという． A⇒B が真のとき，Ａ は Ｂ の十分条件，Ｂ は Ａ の必要条件という． 上記の (a) は x:奇 が x^2:奇 の十分条件であることに対応し， (b) は必要条件に対応する． 同値 Ａ⇔Ｂ の証明：双方向の含意 Ａ⇒Ｂ と Ｂ⇒Ａ を示す 含意 Ａ⇒Ｂ の直接証明：Ａ を仮定して Ｂ を導く 含意 Ａ⇒Ｂ の間接証明：¬Ｂ を仮定して ¬Ａ を導く（対偶の証明） ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 授業のホームページ 山田 俊行 https://www.cs.info.mie-u.ac.jp/~toshi/