(1.2.3)--ch1-第二讲离散数学离散数学.pdf
离散数学离散数学 Discrete Mathematics 第一章第一章 命题逻辑命题逻辑 (1)否定联结词否定联结词(Negation)，P P 1 0 0 1 见假为真见假为真,见真为假见真为假.(2)合取联结词合取联结词(Conjunction)，P Q PQ 1 1 1 0 0 1 0 0 1 0 0 0 见假为假，全真为真见假为假，全真为真.(3)析取联结词析取联结词(Disjunction)，P Q P Q 1 1 1 0 0 1 0 0 1 1 1 0 见真为真见真为真,全假为假全假为假.(4)条件联结词条件联结词(Implication)，P Q PQ 1 1 1 0 0 1 0 0 1 0 1 1 前真后假为假前真后假为假,其他为真其他为真.(5)双条件联结词双条件联结词(Bicondition)，P Q PQ 1 1 1 0 0 1 0 0 1 0 0 1 相同为真相同为真,相异为假相异为假.例例5.令令 P：北京比天津人口多北京比天津人口多 解解.求下列复合命题的真值求下列复合命题的真值:(1)(PQ)(P Q)R (2)(QR)(P R)R：乌鸦是白色的乌鸦是白色的.Q：2+24.1 1 0 1 0 0 0 二、命题的符号化二、命题的符号化(翻译翻译)1 1 1 第一章第一章 命题逻辑命题逻辑 有关联结词优先级如下：有关联结词优先级如下：联结词的优先顺序联结词的优先顺序(由高到低由高到低)为为:,;如果出现的联结词同级如果出现的联结词同级,又无括号时又无括号时,则按从左到右则按从左到右的顺序运算的顺序运算;有括号时有括号时,应该先进行括号中的运算应该先进行括号中的运算.二、命题的符号化二、命题的符号化(翻译翻译)第一章第一章 命题逻辑命题逻辑 一、真值表一、真值表 定义定义1.在命题公式在命题公式 中中,对于分量指派真值的各种可能对于分量指派真值的各种可能 组合组合,就确定了这个命题公式的各种真值情况就确定了这个命题公式的各种真值情况,把它汇列把它汇列 成表成表,称为命题公式的称为命题公式的真值表真值表(truth table).1-4 真值表与等价公式真值表与等价公式 第一章第一章 命题逻辑命题逻辑 命题变元按字典序排列命题变元按字典序排列.为构造真值表方便和一致为构造真值表方便和一致,特约定如下特约定如下:对公式的每个指派对公式的每个指派,以二进制数从小到大或从大到以二进制数从小到大或从大到 小顺序列出小顺序列出.若公式复杂若公式复杂,可先列出各子公式的真值可先列出各子公式的真值(若有括号则若有括号则 应从里层向外层展开应从里层向外层展开),最后列出所给公式的真值最后列出所给公式的真值.第一章第一章 命题逻辑命题逻辑 例例1.构造公式构造公式(P Q)(Q P)真值表真值表.P Q 0 0 1 1 0 1 0 1 1 1 0 0 1 0 1 0 1 1 0 1 1 1 0 1 1 1 1 1 P Q PQ Q P(PQ)(Q P)第一章第一章 命题逻辑命题逻辑 构造真值表的步骤构造真值表的步骤:找出公式中所有命题变元找出公式中所有命题变元 P1,P2,Pn,按字典按字典序排列序排列,列出列出2n 组指派组指派.列出公式及公式中的子公式列出公式及公式中的子公式.计算各公式的真值计算各公式的真值.第一章第一章 命题逻辑命题逻辑 练习练习1.给出给出 (P Q)(P Q)的真值表的真值表.P Q P Q P Q P Q (P Q)(P Q)(P Q)0 0 1 1 0 1 0 1 1 1 0 0 1 0 1 0 1 1 1 0 0 0 0 1 1 1 1 0 1 1 1 1 第一章第一章 命题逻辑命题逻辑 定义定义1.给定两个命题公式给定两个命题公式 A 和和 B,设设 P1,P2,Pn 为所有出现在为所有出现在 A和和 B 中的原子变元中的原子变元.若给若给P1,P2,Pn 任意一组真值指派任意一组真值指派,A 和和B 的真值都相同的真值都相同,则称则称 A和和B 是是等价的等价的或或逻辑相等逻辑相等,记做记做 AB.符号“符号“”与“”与“”的区别”的区别 区别区别:“”不是联结词不是联结词,AB不表示一个公式不表示一个公式,它表它表 示两个公式间的一种关系示两个公式间的一种关系,即等价关系即等价关系.“”是联结词”是联结词,AB是一个公式是一个公式.注意注意:二、等价公式二、等价公式 第一章第一章 命题逻辑命题逻辑 P Q PQ QP PQ(PQ)(QP)0 0 1 1 0 1 0 1 例例2.证明证明:PQ (PQ)(QP)1 0 0 1 1 0 1 1 1 1 0 1 1 0 0 1 真值表法真值表法 证明公式等价的方法证明公式等价的方法 由真值表知由真值表知 PQ (PQ)(QP)第一章第一章 命题逻辑命题逻辑 基本等价式基本等价式命题定律命题定律 序号序号 命题定律命题定律 表达式表达式 1 对合律对合律 P P 2 幂等律幂等律 P P P，P P P 3 结合律结合律 (P Q)R P (Q R)(P Q)R P (Q R)4 交换律交换律 P Q Q P P Q Q P 5 分配律分配律 P (Q R)(P Q)(P R)P (Q R)(P Q)(P R)第一章第一章 命题逻辑命题逻辑 序号序号 命题定律命题定律 表达式表达式 6 德德.摩根律摩根律 (P Q)P Q (P Q)P Q 7 同一律同一律 P F P，P T P 8 零律零律 P T T，P F F 9 否定律否定律 P P T，P P F 10 吸收律吸收律 P (P Q)P P (P Q)P 基本等价式基本等价式命题定律命题定律(续续)第一章第一章 命题逻辑命题逻辑 序号序号 命题定律命题定律 表达式表达式 11 条件式转条件式转化律化律 PQ PQ,PQ Q P 12 双条件式双条件式转化律转化律 PQ (PQ)(QP)PQ (PQ)(P Q)13 输出律输出律 (PQ)R P(QR)14 归谬律归谬律 (PQ)(P Q)P 基本等价式基本等价式命题定律命题定律(续续)第一章第一章 命题逻辑命题逻辑 P Q P Q P(P Q)P Q P(P Q)0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 例例3.验证吸收率：验证吸收率：P (P Q)P P (P Q)P 思考：是否所有的等价公式都可以用真值表法证明思考：是否所有的等价公式都可以用真值表法证明?第一章第一章 命题逻辑命题逻辑 定义定义2.如果如果 X 是合式公式是合式公式 A 的一部分的一部分,且且 X 本身也本身也 是一个合式公式是一个合式公式,则称则称 X 为公式为公式 A 的一个的一个子公式子公式.定理定理1.(置换定理置换定理)设设 X 是合式公式是合式公式 A 的子公式的子公式,若若XY,若将若将A中的中的 X 用用Y 来置换来置换,则所得到的公式则所得到的公式 B 与公式与公式 A 等价等价,即即AB.注注:满足定理满足定理1的条件的置换称为的条件的置换称为等价置换或等价代换等价置换或等价代换.等价置换等价置换 第一章第一章 命题逻辑命题逻辑 例例4.证明证明:Q(P (P Q)QP 证明证明:由吸收律由吸收律,P (P Q)P 因此因此,据定理据定理1,有：有：Q(P (P Q)QP 第一章第一章 命题逻辑命题逻辑 2.等值演算法等值演算法 根据已知的等价公式和等价置换根据已知的等价公式和等价置换,推演出另外一些推演出另外一些等价公式的过程称为等价公式的过程称为等值演算等值演算.例例5.证明证明(P Q)(P Q)P 证证.(P Q)(P Q)(P (P Q)(Q (P Q)P (Q P)(Q Q)P T P 分配律分配律 吸收律吸收律,分配律分配律 吸收律，否定律吸收律，否定律 同一律同一律 第一章第一章 命题逻辑命题逻辑 第第一一章章 命命题题逻逻辑辑 例例6.证明证明:P (Q R)Q(PR)R(Q P)证证.P(QR)P (Q R)(P Q)R (Q P)R Q (P R)Q(PR)R(Q P)R(Q P)R(Q P)第第一一章章 命命题题逻逻辑辑 例例7.证明证明:(P Q)(P(Q R)(PQ)(PR)T 证证.原式左边原式左边 (P Q)(P (Q R)(PQ)(PR)(P Q)(P Q)(P R)(PQ)(PR)(P Q)(P R)(P Q)(P R)(P Q)(P R)(P Q)(P R)T 证证.(P Q)(Q R)练习练习.证明证明 (PQ)(Q R)P Q R (P Q)(Q R)(P Q)(Q R)(P Q)(Q R)(P Q R)(Q Q R)P Q R 第一章第一章 命题逻辑命题逻辑 第第一一章章 命命题题逻逻辑辑 内容小结内容小结 本节介绍了真值表、公式等价、等值演算和等价本节介绍了真值表、公式等价、等值演算和等价 置换等概念置换等概念,给出了常用的重要等价公式（给出了常用的重要等价公式（25个）个）重点掌握等价公式及用真值表法验证公式的等价性和重点掌握等价公式及用真值表法验证公式的等价性和等值演算法推演两个公式等价等值演算法推演两个公式等价.
