1. 命題論理

2014 年 B 科微分積分学演習
1. 命題論理
命題, 真理表, 恒真命題, 逆・裏・対偶
✩
✬
命題. 正しいか正しくないか (真か偽か) が定まる文や式を命題という. 真な命題には T ,
偽な命題には F という印をつけ, これをこの命題の真理値という.
命題結合記号. 2 つの命題 P , Q に対し, これらを結合して新しい命題 (合成命題) を作る
ことができる.
(1) P ∨ Q [P または Q]
(2) P ∧ Q [P かつ Q]
(3) ¬P
[P でない (P の否定命題)]
(4) P ⇒ Q [P ならば Q]
特に, (P ⇒ Q) ∧ (Q ⇒ P ) を P ⇔Q と表す.
要素となっている命題と合成命題の真理値を表にしたものを真理表, 真偽表などという.
P Q
T T
T F
F T
F F
P ∨Q P ∧Q P ⇒Q
T
T
T
T
F
F
T
F
T
F
F
T
P ¬P
T F
F T
いくつかの命題を結合して得られる命題が, 要素となっている命題の真偽に関わらず常に
真となるとき, その命題を恒真命題 (tautology) という. 逆に, 常に偽となるものを矛盾
命題という. また, 命題 P と Q の真理値が完全に一致するとき, P と Q は論理同値である
といい, P ≡ Q と表す.
例 (1) P ∨ (¬P ) は恒真命題である. 実際,
(2) ¬(P ⇒ Q) ≡ P ∧ (¬Q). 実際,
P P ∨ (¬P )
T T T F
F F T T
P
T
T
F
F
Q
T
F
T
F
¬(P
F
T
F
F
⇒ Q) P ∧ (¬Q)
T
F F
F
T T
T
F F
T
F T
命題代数の法則. t を恒真命題, f を矛盾命題とする. 命題 P , Q, R に対し
(1) ¬(¬P ) ≡ P
(対合律)
(2) ¬(P ∨ Q) ≡ ¬P ∧ ¬Q, ¬(P ∧ Q) ≡ ¬P ∨ ¬Q
(ド・モルガンの法則)
(3) P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R), P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R) (分配律)
(4) P ∨ P ≡ P , P ∧ P ≡ P
(べき等律)
(5) P ∨ (Q ∨ R) ≡ (P ∨ Q) ∨ R, P ∧ (Q ∧ R) ≡ (P ∧ Q) ∧ R
(結合律)
(6) P ∨ Q ≡ Q ∨ P , P ∧ Q ≡ Q ∧ P
(交換律)
(7) P ∨ f ≡ P , P ∧ t ≡ P , P ∨ t ≡ t, P ∧ f ≡ f
(同一律)
(8) P ∨ ¬P ≡ t, P ∧ ¬P ≡ f
(排中律・矛盾律)
注意結合律より, (P ∧ Q) ∧ R と P ∧ (Q ∧ R) の真偽は一致するので, 括弧を省略して
P ∧ Q ∧ R と表す. 4 つ以上の場合や, ∨ の場合も同様である.
逆・裏・対偶. 命題 P ⇒ Q に対し, Q ⇒ P , ¬P ⇒ ¬Q, ¬Q ⇒ ¬P をそれぞれ逆・裏・
対偶という.
✫
–1–
✪
問 1. 次の文や式は命題であるか, 命題であればその真理値を示せ.
(1) 5 < 3
(2) 3 ≤ 8 + 4
(3) 今日は暑い
(4) x2 + 5 < 0 を満たす実数 x は存在する
(5) すべての実数 x に対し, x2 = (x + 1)2 − 1 − 2x (6) x − 1 > 6
問 2. P , Q を命題とする. 次の命題の真理表を作成せよ.
(1) ¬P ∧ Q
(4) (P ⇒ Q) ∧ (Q ⇒ P )
(2) ¬P ∨ Q
(
)
(5) P ∧ (P ⇒ Q) ⇒ Q
(3) ¬(P ∨ ¬Q)
(6) Q ⇒ (P ⇒ Q)
問 3. P , Q, R を命題とする. 真理表を作成して, 次の論理同値を確かめよ.
(1) ¬(¬P ) ≡ P
(3) ¬(P ∧ Q) ≡ ¬P ∨ ¬Q
(5) P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)
(2) ¬(P ∨ Q) ≡ ¬P ∧ ¬Q
(4) P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)
(6) P ⇒ Q ≡ ¬P ∨ Q
問 4. P , Q, R を命題とする. 命題代数の法則を用い, 次の命題が恒真命題であることを示せ.
(
)
(
)
(1) (P ⇒ Q) ∧ (Q ⇒ R) ⇒ (P ⇒ R)
(2) (¬P ) ⇒ (Q ∧ (¬Q)) ⇒ P
問 5. P , Q, R を命題とする. 命題代数の法則を用い, 次の論理同値を確かめよ.
(
)
(1) (P ∨ Q) ⇒ R ≡ (P ⇒ R) ∧ (Q ⇒ R), (2) (P ∨ Q) ⇒ (¬P ) ⇒ R) ≡ P ∨ ¬Q ∨ R
(3) P ∨ (P ∧ Q) ≡ P
(4) P ∧ (P ∨ Q) ≡ P,
問 6. 命題 P ⇒ Q に対して, 逆・裏・対偶の真理表を作成せよ.
問 7. 次の命題が真であることを示せ. ただし, a は整数, x, y は実数とする.
(1) a2 は偶数 ⇒ a は偶数
(2) x + y > 2 ⇒ (x > 1 ∨ y > 1)
問 8. 次のことを示せ. ただし, P , Q, R は命題, x は実数とする.
)
(
(
)
1
(1) P ⇒ (Q ∨ R) ≡ P ∧ (¬Q) ⇒ R
(2) x > 0 ⇒ x ≥ 1 ∨ ≥ 1
x
補充問題
問 9. 下図のように 4 枚のカードが置いてある. それぞれのカードには表にはアルファベッ
トが, 裏には数字が記されている. この４枚のカードについて,
命題「表に母音が記されたカードの裏には奇数が記されている」
の真偽を確かめるには, 最小限度どのカードをめくってみる必要があるか.
E
7
F
8
問 10. 命題 P , Q, R, S に対し, 次の命題を条件を満たすように変形せよ.
(1)
(2)
(3)
(4)
(P ∧ Q) ∨ (R ∧ S)
¬((P ∨ Q) ∧ R)
¬((P ⇒ Q) ⇒ R)
P ⇔Q
条件:
条件:
条件:
条件:
P ∨ R と Q ∨ R が現れる.
(¬P ) ∨ (¬R) が現れる.
(¬P ) ∧ (¬R) が現れる.
結合法則 ∨ と ¬ のみが現れる.
–2–

Download Report