命题逻辑等值演算课件(离散数学)综述.ppt

第二章命题逻辑等值演算 1 本章主要内容?等值式?范式合取范式析取范式?联结词的完备集重点内容: ?消解法 等值式?等值式?基本等值式?等值演算和置换规则 3一、等值式定义 1:设A和B是两个命题公式,如果 A、B在任意指派下,其真值都是相同的,则称 A和B是等值的,或逻辑相等, 记作 A?B,称 A?B为等值式。 p ? q?q??p? p ? q (p ? q) ?(q ? p)? 4一、等值式 p ? q?q??p11110 011 (p ? q) ?(?q ?? p)1111 5一、等值式 p ? q (p ? q) ?(q ? p) 11000011 ( p ? q) ?((p ? q) ?(q ? p))1111 6一、等值式定义 2:若A?B是重言式,则称 A与B等值,记作 A?B,并称 A?B是等值式。例如, (p? q) ? ((?p? q)?(?r?r )) 说明:定义中, A、B、?均为元语言符号, A 或B中可能有哑元出现。 r是哑元 7一、等值式等值式的性质: ,即对任意公式 A,有 A?A。 ,即对任意公式 A和B,若 A ? B,则 B ?A。 ,即对任意公式 A、B和C,若 A?B、B?C,则 A ?C。 8一、等值式例1:“除非有时间,我才去看电影。”上面这句话的意思相当于“如果没有时间,我就不去看电影。”令: p:我有时间; q:我去看电影 pq? qp???? 9 p q p ? q? p ? q? q ?? p 0 0 11 1 1 0 1 11 0 1 1 0 00 1 0 1 1 10 0 1 p ? q 和? q ?? p是等值的。判断两个公式是否为等值式的基本方法是: 通过两个公式的真值表进行验证。 10