2015 年 4 月 28 日情報論理学第 3 回講義復習問題問題 1 (¬(P → R)) ∧ (Q ∨ R) は充足可能か ? 真理値表を用いて調べよ．問題 2 ¬((¬P) → P) は充足可能であることを (真理値表を使わず) 解釈の定義を使って示せ．問題 3 P → Q と ¬P ∨ Q は論理的同値か，真理値表を書いて調べよ．問題 4 P ∧ (P ∨ Q) ∼ = P を (真理値表を使わず) 解釈の定義を使って示せ．問題 5 以下の論理的同値性を同値変形を用いて示せ． (変形に用いた規則の名前も記入すること． ) (1) P → Q → S ∼ =P∧Q→S (2) (P → Q) → Q ∼ =P∨Q (3) (P → Q) ∧ (Q → P) ∼ = (P ∧ Q) ∨ (¬P ∧ ¬Q) 問題 6 以下の証明図の足りないところを補足せよ． [Q]2 [ ]3 →I1 R 2 Q → R →I →I3 ((P → Q) → R) → Q → R 問題 7 以下は (P → Q) → (Q → R) → P → R の証明図である．空いているところを埋めよ． [ ]3 [P]1 2 Q [Q → ] →E 1 →I P→R →I →P→R →I (P → Q) → (Q → R) → P → R 問題 8 以下は (P → Q ∧ R) → P → R ∧ Q の証明図である．空いているところを埋めよ． [ ] [ ] [ ] [ ] →E →E Q∧R Q∧R ∧E ∧E 1 P → R ∧ Q →I →I2 (P → Q ∧ R) → P → R ∧ Q 1 問題 9 足りない箇所を補なって，次の命題論理式の証明図を完成させよ． ]2 [ ∧E ]2 [ Q→R P ∧E ∧I ((P ∧ Q) ∧ R) → (P ∧ (Q → R)) →I2 問題 10 次の命題論理式の証明図を書け． (1) (P → P → Q) → R → P → Q (2) P → Q → P ∧ Q (3) (P ∧ Q → R) → (Q → P → R) 問題 11 以下の命題論理式の証明図を書け． (1) (P → Q) ∧ (Q → R) → P → R (2) (P → Q) → P ∧ R → Q (3) R → P ∧ Q → Q ∧ (R ∧ P) 問題 12 論理的同値性 ∼ = が同値関係となることを証明せよ． 2 情報論理学第 3 回講義復習問題解答問題 1 P T T T T F F F F Q T T F F T T F F R P → R ¬(P → R) Q ∨ R (¬(P → R)) ∧ (Q ∨ R) T T F T F F F T T T T T F T F F F T F F T T F T F F T F T F T T F T F F T F F F ゆえに，充足可能．問題 2 v(P) = F となる解釈 v を考える．このとき， [[P]]v = F， [[¬P]]v = T．よって， [[¬P → P]]v = F．従って， [[¬(¬P → P)]]v = T．よって， ¬(¬P → P) は充足可能．問題 3 P T T F F Q P → Q ¬P ¬P ∨ Q T T F T F F F F T T T T F T T T ゆえに， P → Q と ¬P ∨ Q は論理的同値．問題 4 v を任意の付値とする． v(P) の値で場合分けする． • v(P) = T のとき．このとき， [[P]]v = T であるから， [[P ∨ Q]]v = T．よって， [[P ∧ (P ∨ Q)]]v = T = [[P]]v となる． • v(P) = F のとき．このとき， [[P]]v = F であるから， [[P ∧ (P ∨ Q)]]v = F = [[P]]v となる．よって，いづれの場合も [[P ∧ (P ∨ Q)]]v = [[P]]v となる．ゆえに， P ∧ (P ∨ Q) ∼ = P が成立．問題 5 (1) (2) P→Q→S ∼ = ¬P ∨ (Q → S) (含意) ∼ = ¬P ∨ (¬Q ∨ S) (含意) ∼ = (¬P ∨ ¬Q) ∨ S (結合律) ∼ (ド・モルガンの法則) = ¬(P ∧ Q) ∨ S ∼ (含意) = P∧Q→S (P → Q) → Q ∼ (含意) = ¬(P → Q) ∨ Q ∼ ¬(¬P ∨ Q) ∨ Q (含意) = ∼ (ド・モルガンの法則) = (¬¬P ∧ ¬Q) ∨ Q ∼ (二重否定) = (P ∧ ¬Q) ∨ Q ∼ = (P ∨ Q) ∧ (¬Q ∨ Q) (分配律) ∼ (⊤ 規則) = (P ∨ Q) ∧ ⊤ ∼ (⊤ 規則) = P∨Q 3 (3) ∼ = ∼ = ∼ = ∼ = ∼ = ∼ = ∼ = ∼ = ∼ = (P → Q) ∧ (Q → P) (¬P ∨ Q) ∧ (¬Q ∨ P) ((¬P ∨ Q) ∧ ¬Q) ∨ ((¬P ∨ Q) ∧ P) ((¬P ∧ ¬Q) ∨ (Q ∧ ¬Q)) ∨ ((¬P ∨ Q) ∧ P) ((¬P ∧ ¬Q) ∨ ⊥) ∨ ((¬P ∨ Q) ∧ P) (¬P ∧ ¬Q) ∨ ((¬P ∨ Q) ∧ P) (¬P ∧ ¬Q) ∨ ((¬P ∧ P) ∨ (Q ∧ P)) (¬P ∧ ¬Q) ∨ (⊥ ∨ (Q ∧ P)) (¬P ∧ ¬Q) ∨ (Q ∧ P) (P ∧ Q) ∨ (¬P ∧ ¬Q) (含意 ×2) (分配律) (分配律) (⊥ 規則) (⊥ 規則) (分配律) (⊥ 規則) (⊥ 規則) (交換律 ×2) 問題 6 [Q]2 1 [(P → Q) → R]3 P → Q →I →E R 2 →I Q→R →I3 ((P → Q) → R) → Q → R 問題 7 [Q → R]2 [P → Q]3 Q [P]1 →E →E R 1 →I P→R →I2 (Q → R) → P → R →I3 (P → Q) → (Q → R) → P → R 問題 8 [P → Q ∧ R]2 [P]1 [P → Q ∧ R]2 [P]1 →E →E Q∧R Q∧R ∧E ∧E R Q ∧I R∧Q 1 →I P→R∧Q →I2 (P → Q ∧ R) → P → R ∧ Q 問題 9 [(P ∧ Q) ∧ R]2 [(P ∧ Q) ∧ R]2 ∧E ∧E P∧Q R 1 ∧E →I P Q→R ∧I P ∧ (Q → R) →I2 ((P ∧ Q) ∧ R) → (P ∧ (Q → R)) 問題 10 (1) (2) Q]3 [P → P → P→Q [P]1 →E [P]1 →E Q 1 →I P→Q 2 R → P → Q →I →I3 (P → P → Q) → R → P → Q 4 [P]2 [Q]1 P ∧ Q ∧I 1 Q → P ∧ Q →I 2 P → Q → P ∧ Q →I (3) [P]1 [Q]2 [P ∧ Q → P ∧ Q ∧I →E R 1 →I P→R 2 Q → P → R →I →I3 (P ∧ Q → R) → Q → P → R R]3 問題 11 (1) [(P → Q) ∧ (Q → R)]2 ∧E P→Q [(P → Q) ∧ (Q → R)]2 ∧E Q→R Q →E R 1 →I P→R →I2 (P → Q) ∧ (Q → R) → P → R (2) [P]1 →E (3) [P ∧ Q]1 ∧E [P ∧ Q]1 P [R]2 ∧E ∧I Q R∧P ∧I Q ∧ (R ∧ P) →I1 P ∧ Q → Q ∧ (R ∧ P) →I2 R → P ∧ Q → Q ∧ (R ∧ P) [P ∧ R]1 ∧E [P → P →E Q 1 P ∧ R → Q →I →I2 (P → Q) → P ∧ R → Q Q]2 問題 12 以下， (* *) で囲まれた部分はコメントである． def (* 同値関係 ⇐⇒ 反射的かつ対称的かつ推移的な関係，であるから， “(∼ = は反射的) かつ ∼ ∼ (= は対称的) かつ (= は推移的)” を示せばよい． ∧ の導入規則から，これには， “(∼ = は反射的)” と “(∼ = は推移的)” をそれぞれ示せばよい． *) = は対称的)” と “(∼ (証明) (1) 反射性 A を任意の命題論理式とする．任意の付値 v について， [[A]]v = [[A]]v が成立する．よって，論理的同値性の定義より， A ∼ = A． (2) 対称性 (* 対称性は，任意の A, B について， “A ∼ = B ならば B ∼ = A” が成立するという性質．従っ ∼ ∼ て， → の導入規則より “A = B” を仮定して， “B = A” を導けばよい． *) A, B を任意の命題論理式とする． A ∼ = B と仮定する．すると，論理的同値性の定義より，任意の付値 v について， [[A]]v = [[B]]v ．よって，任意の付値 v について， [[B]]v = [[A]]v ．従って，論理的同値性の定義より， B ∼ = A． (3) 推移性 (* 推移性は任意の A, B, C について， “(A ∼ = B かつ B ∼ = C) ならば A ∼ = C” が成立すると ∼ ∼ いう性質．従って， → の導入規則より “A = B かつ B = C” を仮定して， “A ∼ = C” を導け ∼ ∼ ∼ ばよい．また， ∧ の除去規則より， “A = B かつ B = C” があれば， “A = B” も “B ∼ = C” も使ってよい． *) A, B, C を任意の命題論理式とする． A ∼ = B， B ∼ = C と仮定する．すると，論理的同値性の定義より，任意の付値 v について， [[A]]v = [[B]]v かつ [[B]]v = [[C]]v ．ゆえに，任意の付値 v について， [[A]]v = [[C]]v ．よって，論理的同値性の定義より， A ∼ = C． (* 証明中では，推論を表わすのに， “すると ” や “ゆえに ”， “よって ”， “従って ” など，さまざまな言い方を用いるが，これは文章が単調になるのを避け，読みやすくするためである．証明においてはこれらに意味の違いはない． “， ” も，文脈に応じて “かつ ” と読む． *) 5 (* 実は，上の証明では，まだ学習していない述語論理や等号に関する推論を用いている．述語論理では，このような証明が完全に証明図で書けるようになる． *) 6