命題論理式の真偽 (Truth Value)

命題の真偽


1. 命題 p が真である: p = T

2. 命題 p が偽である: p = F

真理値表 (Truth Table)


否定

p	¬p
T	F
F	T

連言

p　q	p ∧ q
T　T	T
T　F	F
F　T	F
F　F	F

選言

p　q	p ∨ q
T　T	T
T　F	T
F　T	T
F　F	F

含意

p　q	p → q
T　T	T
T　F	F
F　T	T
F　F	T

同値

p　q	p ≡ q (= (p → q) ∧ (q → p))
T　T	T
T　F	F
F　T	F
F　F	T

[定義] (解釈 Interpretation)


論理式の真偽を，そこに現れる基本論理式の真偽から決定することを 解釈という．

また，命題論理式 F が与えられたとき A₁, A₂, ..., A_n をFの中に出現する基本命題とする．A₁, A₂, ..., A_n への真理値 {T, F}のそれぞれの割り当て方 I を F の解釈と呼ぶこともあり，[F]_I と表記する．

p　q	¬p	¬p ∨ q
T　T
T　F
F　T
F　F

(¬p → q) → r の真理値表を完成させなさい．

p　q　r	¬p	¬p → q	(¬p → q) → r
T　T　T
T　T　F
T　F　T
T　F　F
F　T　T
F　T　F
F　F　T
F　F　F

よく使われる同値関係


1. 可換則 commutative
   (a) P ∨ Q ≡ Q ∨ P
   (b) P ∧ Q ≡ Q ∧ P

2. 結合則 associative
   (a) (P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R)
   (b) (P ∧ Q) ∧ R ≡ P ∧ (Q ∧ R)

3. 分配則 distributive
   (a) P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)
   (b) P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)

4. (a) P ∨ T ≡ T
   (b) P ∧ T ≡ P

5. (a) P ∨ F ≡ P
   (b) P ∧ F ≡ F

6. 同語反復 tautology
   (a) P ∨ ¬P ≡ T (排中律)
   (b) P ∧ ¬P ≡ F

7. 二重否定 double negation
   (a) ¬(¬P)≡ P

8. 展開 expansion
   (a) ¬(P ∨ Q) ≡ ¬P ∧ ¬Q
   (b) ¬(P ∧ Q) ≡ ¬P ∨ ¬Q

9. その他
   P ∨ P ≡ P ∧ P ≡ P
   

命題論理式 F と解釈 I に対する [F]_Iの再帰計算


1. F が命題記号 G の時は [F]_I = [G]_I

2. F が (¬G) という形式のときは [F]_I = [¬ G]_I = ¬[G]_I

3. F が (G ∧ H)，(G ∨ H), (G → H), (G ≡ H) のいずれかの形式をし ている時は [F]_Iの値は上記の真理値表に基づいて決定する．

• 講義の詳細