2014 年 7 月 1 日 情報論理学 第 10 回講義 復習問題 問題 1 以下の論理的同値性を 同値変形を 用いて 示せ． (変形に 用いた 規則の名前 も 示すこ と ． ) (1) ¬∀x (P(x) → Q(x)) ∼ = ∃x (P(x) ∧ ¬Q(x)) (2) ∀x (P(x) → Q) ∼ = ∃x P(x) → Q (3) ∃x (P(x) → Q(x)) ∼ = ∀x P(x) → ∃x Q(x) 問題 2 以下の論理的同値性を 同値変形を 用いて 示せ． (変形に 用いた 規則の名前 も 示すこ と ． ) (1) ∀x P(x) → ∃x Q(x) ∼ = ∃x ∀y (P(x) → Q(y)) (2) ¬∀x P(x, y) ∧ ∀y P(x, y) ∼ = ∃u ∀v (¬P(u, y) ∧ P(x, v)) 問題 3 次の証明図に 現われる ∀I の推論規則の適用に ついて ， 正し いか否か答え よ ． ま た， 正し く な い場合に は， そ の理由を 次の形で述べよ ．「 除去さ れて いな い仮定．．． に 変数．．． が自由に 出現する た め」 ． (1) (2) [P(x)]1 [Q(y)] ∧I P(x) ∧ Q(y) →I1 P(x) → P(x) ∧ Q(y) ∀I ∀y (P(x) → P(x) ∧ Q(y)) [P(x)]1 [Q(y)] ∧I P(x) ∧ Q(y) ∀I ∀x (P(x) ∧ Q(y)) →I1 P(x) → ∀x (P(x) ∧ Q(y)) 問題 4 以下の述語論理式の証明図を 書け． (1) ∀x ((P → Q(x)) ∧ P → Q(x)) (2) ∀x P(x) → P(a) ∧ P(b) (3) ∀x (P → Q(x)) → P → ∀y Q(y) (4) ∀x (P(x) → Q(x)) ∧ ∀y P(y) → ∀z Q(z) 問題 5 以下の述語論理式の証明図を 書け． (1) ∀x ∀y P(x, y) → ∀z P(z, z) (2) ∀x P(x) → ∀x ∀y (P(x) ∧ P(y)) (3) ∀x P(x) → ∀x∀y P(f(x, y)) (4) ∀x (P(x) → ∃y Q(x, y)) → P(a) → ∃y Q(a, y) 問題 6 以下の証明図に ついて ， 正し く な い推論を 指摘する と と も に 正し い証明図 に 直せ． た だし ， 証明図の結論を 変え て はいけ な い． 1 (1) (2) [∀x ∀y P(x, y)]1 ∀E ∀y P(x, y) ∀E P(y, z) ∀I ∀z P(y, z) ∀I ∀y ∀z P(y, z) →I1 ∀x ∀y P(x, y) → ∀y ∀z P(y, z) [∀x ∀y P(x, y)]1 ∀E ∀y P(y, y) ∀E P(y, y) ∀I ∀y P(y, y) →I1 ∀x ∀y P(x, y) → ∀y P(y, y) 2 情報論理学 第 10 回講義 復習問題解答 問題 1 (1) ¬∀x (P(x) → Q(x)) ∼ = ∃x ¬(P(x) → Q(x)) ∼ = ∃x ¬(¬P(x) ∨ Q(x)) ∼ = ∃x (¬¬P(x) ∧ ¬Q(x)) ∼ = ∃x (P(x) ∧ ¬Q(x)) (ド ・ モルガン の法則) (含意の法則) (ド ・ モルガン の法則) (二重否定) (2) ∀x (P(x) → Q) ∼ = ∀x (¬P(x) ∨ Q) ∼ = ∀x ¬P(x) ∨ Q ∼ = ¬∃x P(x) ∨ Q ∼ = ∃x P(x) → Q (含意の法則) (束縛の移動) (ド ・ モルガン の法則) (含意の法則) (3) ∃x (P(x) → Q(x)) ∼ = ∃x (¬P(x) ∨ Q(x)) ∼ = ∃x ¬P(x) ∨ ∃x Q(x) ∼ = ¬∀x P(x) ∨ ∃x Q(x) ∼ = ∀x P(x) → ∃x Q(x) (含意の法則) (束縛の分配) (ド ・ モルガン の法則) (含意の法則) 問題 2 (1) ∀x P(x) → ∃x Q(x) ∼ = ¬∀x P(x) ∨ ∃x Q(x) ∼ = ∃x ¬P(x) ∨ ∃x Q(x) ∼ = ∃x ¬P(x) ∨ ∃y Q(y) ∼ = ∃x ¬P(x) ∨ ∃x ∃y Q(y) ∼ = ∃x (¬P(x) ∨ ∃y Q(y)) ∼ = ∃x (∃y ¬P(x) ∨ ∃y Q(y)) ∼ = ∃x ∃y (¬P(x) ∨ Q(y)) ∼ = ∃x ∃y (P(x) → Q(y)) (含意の法則) (ド ・ モルガン の法則) (束縛変数の名前替え ) (束縛の導入・ 消去) (束縛の分配) (束縛の導入・ 消去) (束縛の分配) (含意の法則) (2) ¬∀x P(x, y) ∧ ∀y P(x, y) ∼ = ∃x ¬P(x, y) ∧ ∀y P(x, y) ∼ = ∃u ¬P(u, y) ∧ ∀y P(x, y) ∼ = ∃u ¬P(u, y) ∧ ∀v P(x, v) ∼ = ∃u (¬P(u, y) ∧ ∀v P(x, v)) ∼ = ∃u (∀v ¬P(u, y) ∧ ∀v P(x, v)) ∼ = ∃u ∀v (¬P(u, y) ∧ P(x, v)) 3 (ド ・ モルガン の法則) (束縛変数の名前替え ) (束縛変数の名前替え ) (束縛の移動) (束縛の導入・ 消去) (束縛の分配) 問題 3 (1) 正し く な い． 除去さ れて いな い仮定 [Q(y)] に 変数 y が自由に 出現する た め． (2) 正し く な い． 除去さ れて いな い仮定 [P(x)] に 変数 x が自由に 出現する ため． (仮 定 [P(x)] は最終的に は除去さ れて いる が， ∀I を 適用する 時点では除去さ れて いな いこ と に 注意． ) 問題 4 (1) [(P → Q(x)) ∧ P]1 [(P → Q(x)) ∧ P]1 ∧E ∧E P → Q(x) P →E Q(x) →I1 (P → Q(x)) ∧ P → Q(x) ∀I ∀x ((P → Q(x)) ∧ P → Q(x)) (2) [∀x P(x)]1 [∀x P(x)]1 ∀E ∀E P(a) P(b) ∧I P(a) ∧ P(b) →I1 ∀x P(x) → P(a) ∧ P(b) (3) [∀x (P → Q(x))]2 ∀E P → Q(y) [P]1 →E Q(y) ∀I ∀y Q(y) →I1 P → ∀y Q(y) →I2 ∀x (P → Q(x)) → P → ∀y Q(y) (4) [∀x (P(x) → Q(x)) ∧ ∀y P(y)]1 [∀x (P(x) → Q(x)) ∧ ∀y P(y)]1 ∧E ∧E ∀x (P(x) → Q(x)) ∀y P(y) ∀E ∀E P(z) → Q(z) P(z) →E Q(z) ∀I ∀z Q(z) →I1 ∀x (P(x) → Q(x)) ∧ ∀y P(y) → ∀z Q(z) 問題 5 (1) [∀x ∀y P(x, y)]1 ∀E ∀y P(z, y) ∀E P(z, z) ∀I ∀z P(z, z) →I1 ∀x ∀y P(x, y) → ∀z P(z, z) 4 (2) [∀x P(x)]1 [∀x P(x)]1 ∀E ∀E P(x) P(y) ∧I P(x) ∧ P(y) ∀I ∀y (P(x) ∧ P(y)) ∀I ∀x ∀y (P(x) ∧ P(y)) →I1 ∀x P(x) → ∀x ∀y (P(x) ∧ P(y)) (3) [∀x P(x)]1 ∀E P(f(x, y)) ∀I ∀y P(f(x, y)) ∀I ∀x∀y P(f(x, y)) →I1 ∀x P(x) → ∀x∀y P(f(x, y)) (4) [∀x (P(x) → ∃y Q(x, y))]2 ∀E P(a) → ∃y Q(a, y) [P(a)]1 →E ∃y Q(a, y) 1 →I P(a) → ∃y Q(a, y) →I2 ∀x (P(x) → ∃y Q(x, y)) → P(a) → ∃y Q(a, y) 問題 6 (1) 正し く な いのは 1 番上の ∀E の推論． 正し い証明図は， [∀x ∀y P(x, y)]1 ∀E ∀w P(y, w) ∀E P(y, y) ∀I ∀y P(y, y) →I1 ∀x ∀y P(x, y) → ∀y P(y, y) 変数 w は (y 以外の ) 他の変数でも よ い． (2) 正し く な いのは上から 2 番目 ∀E の推論． 正し い証明図は， [∀x ∀y P(x, y)]1 ∀E ∀w P(y, w) ∀E P(y, z) ∀I ∀z P(y, z) ∀I ∀y ∀z P(y, z) →I1 ∀x ∀y P(x, y) → ∀y ∀z P(y, z) 変数 w は (y 以外の ) 他の変数でも よ い． 5
© Copyright 2024 ExpyDoc
