(P ∧ Q ) → ¬P ∨ ¬Q

レポート課題第 6 回【5/31 10:20a.m. 締切】 ⃝
1 問 2.11．次の命題論理式の真理値表を作成し，トートロ
ジーであるか判定せよ．
(1) P → ¬¬P .
(2) ¬¬P → P .
(3) ¬(P ∧ Q) → ¬P ∨ ¬Q.
(4) ¬P ∨ ¬Q → ¬(P ∧ Q).
⃝
2 問 2.12．定理 2.4 の (iv) 第 1 式，(vi) 第 2 式，(vii)，(viii) 第 2 式を証明せよ．．
(iv)
(vi)
(vii)
(viii)
【分配律】P ∧ (Q ∨ R) ⇄ P ∧ Q ∨ P ∧ R.
【ド・モルガンの法則】¬(P ∨ Q) ⇄ ¬P ∧ ¬Q.
【対偶】(P → Q) ⇄ (¬Q → ¬P ). ＜注意：配布プリントの定理 2.4 の (iv) は誤植です．＞
【吸収律】P ∨ P ∧ Q ⇄ P .
解答. ⃝
1 （問 2.11）
(1)
P
0
1
¬P
1
0
¬¬P
0
1
P → ¬¬P
1
1
∴
トートロジー．
P
0
1
¬P
1
0
¬¬P
0
1
¬¬P → P
1
1
∴
トートロジー．
(2)
(3)
P
0
0
1
1
P ∧Q
0
0
0
1
Q
0
1
0
1
¬(P ∧ Q)
1
1
1
0
¬P
1
1
0
0
∴
¬Q
1
0
1
0
¬P ∨ ¬Q
1
1
1
0
¬(P ∧ Q) → ¬P ∨ ¬Q
1
1
1
1
トートロジー．
(4)
P
0
0
1
1
¬P
1
1
0
0
Q
0
1
0
1
¬Q
1
0
1
0
¬P ∨ ¬Q
1
1
1
0
∴
P ∧Q
0
0
0
1
¬(P ∧ Q)
1
1
1
0
¬P ∨ ¬Q → ¬(P ∧ Q)
1
1
1
1
トートロジー．
⃝
2 （問 2.12 より）
(iv)
P
0
0
0
0
1
1
1
1
Q
0
0
1
1
0
0
1
1
∴
R
0
1
0
1
0
1
0
1
Q∨R
0
1
1
1
0
1
1
1
P ∧ (Q ∨ R)
0
0
0
0
0
1
1
1
P ∧Q
0
0
0
0
0
0
1
1
P ∧R
0
0
0
0
0
1
0
1
P ∧Q∨P ∧R
0
0
0
0
0
1
1
1
同値式 P ∧ (Q ∨ R) ⇄ P ∧ Q ∨ P ∧ R はトートロジーである．
9
(vi)
P
0
0
1
1
∴
Q
0
1
0
1
P ∨Q
0
1
1
1
¬(P ∨ Q)
1
0
0
0
¬P
1
1
0
0
¬Q
1
0
1
0
¬P ∧ ¬Q
1
0
0
0
同値式 ¬(P ∨ Q) ⇄ ¬P ∧ ¬Q はトートロジー．
(vii)
P
0
0
1
1
∴
Q
0
1
0
1
P →Q
1
1
0
1
¬Q
1
0
1
0
¬P
1
1
0
0
¬Q → ¬P
1
1
0
1
同値式 P → Q ⇄ ¬Q → ¬P はトートロジー．
(viii)
P
0
0
1
1
∴
Q
0
1
0
1
P ∧Q
0
0
0
1
P ∨ (P ∧ Q)
0
0
1
1
同値式 P ∨ P ∧ Q ⇄ P はトートロジー．
10

Download Report