2010秋季学期-离散数学-命题逻辑-语义.pdf

离离 散散 数数 学学 Instructor: 李劲 Email: ljatynu@ School of Software Technology YunNan University 2010.9 ~ 2011.1 1.2 语义—— 真值表 A (P ∧Q ) →(¬(Q ∨R )) 弄真指派 PP QQ RR ((P ∧QQ)) ¬((QQ ∨R )) AA v (0 01) v( A) 1 弄真指派集 T Ω (A) {(0 0 0),(1 0 0),(01 0), (0 01),(1 01),(011)} 若A(P , P ,..., P ) 1 2 n 则,指派数目| Ω(A ) | 2n v v( A) 1 若 是可满足的,当且仅当存在指派 ,使得 A 若 是重言式,当且仅当对任意指派v ∈Ω( A) ,使得v( A) 1 A 若若 是是矛盾矛盾式式,当且仅当对任意指派当且仅当对任意指派vv ∈Ω∈Ω(( AA)) ,使得使得vv(( AA)) 00 AA 2010-10-11 云南大学软件学院 2 1.2 语义—— 逻辑等价 逻辑等价 当命题公式当命题公式 为重言式时为重言式时,称称 逻辑等价于逻辑等价于 ,记为记为 AA ↔BB AA BB AA ⇔BB P Q A Q →(P ∨(P ∧Q)) B Q =→P A ↔B 1 1 1 1 1 1 0 1 1 1 00 11 00 00 11 0 0 1 1 1 • AA ⇔BB ,任意任意v ∈ΩΩ((AA)), v((AA)) 11 则则,v((BB )) 11 且,任意v ∈Ω(B), v(B) 1 则,v( A) 1 ,则, TT TT • A ⇔B Ω (A) =Ω (B ) • A ⇔B ,则,A真B真,反之亦然。也称A逻辑等值于B。 2010-10-11 云南大学软件学院 3 1.2 语义—— 逻辑蕴含 逻辑蕴含 当命题公式当命题公式 为重言式时为重言式时,称称 逻辑蕴含逻辑蕴含 ,记为记为 AA →→BB AA BB AA ⇒⇒BB P Q A P ∧(Q →¬P ) B Q →(P ∨(P ∧Q )) A →B 11 11 00 11