2015 年 4 月 21 日 情報論理学 第 2 回講義 復習問題 問題 1 以下のよ う に 命題を お く ． P: 天気がよ い． Q: 散歩に 行く R: 傘を も つ ． こ のと き ， 以下の命題が表す意味を 述べよ ． (1) P → Q． (2) (¬P) → (¬Q)． (3) ((¬P) ∧ Q) → R． 問題 2 Q ∧ R が偽のと き ， (R → P) ∨ (Q → P) の真理値値は 1 つに 定ま る か， 真理 値表を 書いて 考え よ ． 定ま る 場合はそ の真理値を 答え よ ． 問題 3 次の命題論理式の省略さ れて いる 括弧を すべて 補え ． (1) P ∧ P → (P → ¬ P ∨ P) → P (2) P → (P ∨ P → ¬ P ∨ P) → P 問題 4 次の命題論理式の括弧を (講義資料の括弧の省略の約束に 従っ て ) 可能な 限り 省略せよ ． (1) (¬(¬((P ∧ Q) → (Q ∧ P)))) (2) ((¬P) → ((¬Q) → (¬R))) 問題 5 付値 v0 を v0 (Pi ) = ( T (i が偶数のと き ) F (i が奇数のと き ) に よ り 定める と き ， 以下の値を (a) 解釈の定義に よ る 直接的な 計算方法， (b) ブー ル関数を 用いた式変形に よ る 計算方法， の 2 通り の方法で計算せよ ． (1) [[¬(P6 → P4 )]]v0 (2) [[P6 ∧ ¬P3 → ¬P1 ]]v0 問題 6 v を 任意の付値と する と き ， [[P ∧ ¬P]]v の値を (真理値表ではな く ) 解釈の 定義を 使っ て 求めよ ． 問題 7 [[P ∧ Q]]v = T， [[P → R]]v = F と な る と き ， [[Q → R]]v の値を (真理値表では な く ) 解釈の定義を 使っ て 求めよ ． 問題 8 [[P → Q]]v = [[P ∧ R]]v = F と な る と き ， [[Q ∨ R]]v の値を (真理値表ではな く ) 解釈の定義を 使っ て 求めよ ． 問題 9 [[P ∧ Q]]v = [[R ∧ ¬Q]]v = F と な る と き ， [[P ∧ R]]v の値を (真理値表ではな く ) 解釈の定義を 使っ て 求めよ ． 問題 10 以下の 2 引数ブール関数 f に対し て， 任意の付値 v について， f (v(P), v(Q)) = [[A]]v を 満たす命題論理式 A を 与え よ ． f (T, T) = T f (T, F) = F f (F, T) = F f (F, F) = T 問題 11 (P ∧ Q) → (R ∨ P) はト ート ロ ジーか， 真理値表を 書いて 調べよ ． 問題 12 P → (Q → (P ∧ Q)) がト ート ロ ジーである こ と を (真理値表を 使わず) 解釈 の定義を 用いて 示せ． 情報論理学 第 2 回講義 復習問題解答 問題 1 (1) P → Q： 天気がよ いな ら ば散歩に いく ． (2) (¬P) → (¬Q)： 天気が悪いな ら ば散歩に いかな い． (3) ((¬P) ∧ Q) → R： 天気が悪く て 散歩に いく な ら ば傘を も つ． 問題 2 真理値表は以下のよ う に な る ． P T T T T F F F F Q T T F F T T F F R Q ∧ R R → P Q → P (R → P) ∨ (Q → P) T T T T T F F T T T T F T T T F F T T T T T F F F F F T F T T F F T T F F T T T よ っ て ， Q ∧ R が偽のと き ， (R → P) ∨ (Q → P) はいつも 真と な る ． 問題 3 (1) ((P ∧ P) → ((P → ((¬ P) ∨ P)) → P)) (2) (P → (((P ∨ P) → ((¬ P) ∨ P)) → P)) 問題 4 (1) ¬¬(P ∧ Q → Q ∧ P) (2) ¬P → ¬Q → ¬R 問題 5 (a) 解釈の定義に よ る 直接的な 計算法． (1) [[P6 ]]v0 = [[P4 ]]v0 = T よ り ， [[P6 → P4 ]]v0 = T． よ っ て ， [[¬(P6 → P4 )]]v0 = F (2) [[P3 ]]v0 = F よ り ， [[¬P3 ]]v0 = T. よ っ て ， [[P6 ]]v0 = T よ り ， [[P6 ∧ ¬P3 ]]v0 = T. 一方， [[P1 ]]v0 = F よ り ， [[¬P1 ]]v0 = T. 以上よ り ， [[P6 ∧ ¬P3 → ¬P1 ]]v0 = T. (b) ブール関数を 用いた式変形に よ る 計算法． (1) [[¬(P6 → P4 )]]v0 = not([[P6 → P4 ]]v0 ) = not(imp([[P6 ]]v0 , [[P4 ]]v0 )) = not(imp(T, T)) = not(T) = F (2) [[P6 ∧ ¬P3 → ¬P1 ]]v0 = = = = = = = imp([[P6 ∧ ¬P3 ]]v0 , [[¬P1 ]]v0 ) imp(and([[P6 ]]v0 , [[¬P3 ]]v0 ), [[¬P1 ]]v0 ) imp(and([[P6 ]]v0 , not([[P3 ]]v0 )), not([[P1 ]]v0 )) imp(and(T, not(F))not(F)) imp(and(T, T), not(F)) imp(T, T) T 問題 6 [[P ∧ ¬P]]v = F と な る ． (証明) v(P) の値によ っ て 場合分け する ． v(P) = T の場合． こ のと き ， 解釈の定義よ り ， [[¬P]]v = F． よ っ て ， 解釈の定義よ り ， [[P ∧ ¬P]]v = F と な る ． v(P) = F の場合． こ のと き ， 解釈の定義よ り ， [[¬P]]v = T． よ っ て ， 解釈の定義よ り ， [[P ∧ ¬P]]v = F と なる ． 問題 7 [[P ∧ Q]]v = T よ り v(P) = v(Q) = T． [[P → R]]v = F よ り ， v(P) = T， v(R) = F． よ っ て ， [[Q → R]]v = F． 問題 8 [[P → Q]]v = F よ り ， v(P) = T かつ v(Q) = F． ま た ， [[P ∧ R]]v = F な ので， v(P) = T よ り ， v(R) = F が導かれる ． よ っ て ， v(Q) = v(R) = F よ り ， [[Q ∨ R]]v = F． 問題 9 v(Q) の値で場合分け し て 考え る ． (i) v(Q) = T の場合． [[P ∧ Q]]v = F よ り ， v(P) = F． よ っ て ， [[P ∧ R]]v = F． (ii) v(Q) = F の場合． こ のと き ， [[¬Q]]v = T な ので， [[R ∧ ¬Q]]v = F よ り ， v(R) = F． よ っ て ， [[P ∧ R]]v = F． よ っ て ， v(Q) の値に よ ら ず， [[P ∧ R]]v = F と な る ． 問題 10 真理値表が P T T F F Q T F T F ··· ··· ··· ··· ··· A T F F T と な る よ う な 命題論理式 A を 与え ればよ い． 解答例： (P ∧ Q) ∨ (¬P ∧ ¬Q) 問題 11 P T T T T F F F F Q T T F F T T F F R P ∧ Q R ∨ P (P ∧ Q) → (R ∨ P) T T T T F T T T T F T T F F T T T F T T F F F T T F T T F F F T ゆえ に ， ト ート ロ ジー． 問題 12 A = P → Q → P ∧ Q と おく ． 任意の付値 v に ついて ， [[A]]v = T と な る こ と を 示す． v(P) = F な ら ば， 解釈の定義よ り ， [[A]]v = T が成立． よ っ て ， 以下では v(P) = T の場合を 考え る ． v(Q) = F な ら ば， 解釈の定義よ り ， [[Q → P ∧ Q]]v = T が成立． よ っ て ， [[A]]v = T と な る ． 従っ て ， v(P) = v(Q) = T の場合を 考え ればよ い． こ のと き ， 解釈の定義よ り ， [[P ∧ Q]]v = T が成立． よ っ て ， [[Q → P ∧ Q]]v = T． 従っ て ， [[A]]v = T と な る ．
© Copyright 2024 ExpyDoc
