离散数学的命题逻辑ppt课件.ppt

2逻辑逻辑o 逻辑不仅对理解数学推理十分重要，而且在逻辑不仅对理解数学推理十分重要，而且在计算机科学中有许多应用。这些逻辑规则用于计算机科学中有许多应用。这些逻辑规则用于计算机电路设计、计算机程序构造、程序正确计算机电路设计、计算机程序构造、程序正确性证明等许多方面！性证明等许多方面！3Copyright 2007 by Xu Dezhi3逻辑学逻辑学o 逻辑学逻辑学 = 研究正确推理的科学研究正确推理的科学o 推理：由一个或几个命题推出另外一个命题的思维形式。推理：由一个或几个命题推出另外一个命题的思维形式。o 逻辑学的作用逻辑学的作用1、有助于准确、严密地表达和交流思想。2、有助于培养、提高认知能力，获得间接知识。3、有助于识别、驳斥谬误和诡辩，进行批判性思维。p 数理逻辑：用数学方法研究推理的一门学科数理逻辑：用数学方法研究推理的一门学科n 一套符号体系 + 一组推理规则4Copyright 2007 by Xu Dezhi4 逻辑学逻辑学o 逻辑学关注的是陈述（命题）之间的关系 。例如 :n 我的表是数字的.n 所有数字设备都依靠电池运行.n 因此，我的表依靠电池运行o 注意：逻辑学并不关心前面两个陈述（命题）的真假。但是，如果它们是真的，则推论也一定是真的。5p命题：命题：n凡是具有确定真假意义的陈述句均称为命题。凡是具有确定真假意义的陈述句均称为命题。p命题的值命题的值:n若为若为“真真”，用或表示；，用或表示；n若为若为“假假”，用或表示。，用或表示。 p由于一个命题的值只可能取由于一个命题的值只可能取“真真”或或“假假”两种值，两种值，因此，命题逻辑也称为因此，命题逻辑也称为“二值逻辑二值逻辑”。p延伸阅读:模糊逻辑基本概念基本概念: 命题与命题的值命题与命题的值6下面三类陈述句是命题：下面三类陈述句是命题：1. 现实可判断真假的陈述句。现实可判断真假的陈述句。2.目前还不知道真假，但它们本身是具有真假意目前还不知道真假，但它们本身是具有真假意义的。义的。3. 其真假与讨论问题范围（论域）有关的陈述句其真假与讨论问题范围（论域）有关的陈述句（如：所有的人都爱跑步）。（如：所有的人都爱跑步）。下面的不是命题：下面的不是命题： 感叹句感叹句 ，疑问句，祈使句，疑问句，祈使句, 非命题陈述句：悖论语句非命题陈述句：悖论语句(如如:我正在说谎我正在说谎)。7例：例：1)1) 地球绕着月亮转。地球绕着月亮转。2)2) 1+1=31+1=3。3)3) 禁止烟火！禁止烟火！4)4) 地球有一天会爆炸。地球有一天会爆炸。5)5) 明天会下雨吗？明天会下雨吗？6)6) x5.x5.7)7) 如果明天天气晴朗，我就到湘江边散步如果明天天气晴朗，我就到湘江边散步。8)8) 如果太阳从西边升起如果太阳从西边升起, ,我就可以长生不老。我就可以长生不老。 9)9) 火星上有水。火星上有水。 8p简单命题简单命题( (原子命题）原子命题）它不能再分解成更它不能再分解成更简单的命题。简单的命题。p在命题逻辑中，简单命题被看作是一个整体，在命题逻辑中，简单命题被看作是一个整体，不再分析其内部的逻辑形式。不再分析其内部的逻辑形式。 常用大写字母：常用大写字母：P，Q，R，. .表示简单命题。表示简单命题。 p例如：例如：P: 4P: 4是质数，是质数，Q Q：所有人都爱学习：所有人都爱学习简单命题与复合命题简单命题与复合命题9复合命题（命题的组合）复合命题（命题的组合）p 复合（杂）命题复合（杂）命题命题可以通过逻辑联接词命题可以通过逻辑联接词构成新的命题，即复合命题。复合命题的子命构成新的命题，即复合命题。复合命题的子命题也可以是复合命题。题也可以是复合命题。p 例如：例如：n 如果明天天气晴朗，我就到湘江边散步如果明天天气晴朗，我就到湘江边散步。n 如果太阳从西边升起如果太阳从西边升起, ,我就可以长生不老。我就可以长生不老。 10命题可以通过一些逻辑联结词构成新的命题（复命题可以通过一些逻辑联结词构成新的命题（复合命题）合命题）1.否定词否定词: 定义定义：设是命题，复合命题：设是命题，复合命题“ ”是的否定，是的否定，规定规定 为真当且仅当为假。为真当且仅当为假。 例：例： 长沙的秋天景色很美。长沙的秋天景色很美。 ： Q:上海处处都清洁。上海处处都清洁。 Q： 五种常用的命题（逻辑）联接词五种常用的命题（逻辑）联接词11定义定义：设，是命题，复合命题设，是命题，复合命题“并且并且”称为称为和的合取和的合取, ,写成写成。为真当且仅当为真当且仅当与同时为真。真值表如下：与同时为真。真值表如下：2. 2. 合取词合取词 “ “”12 定义定义：设，是命题，复合命题设，是命题，复合命题“或者或者”称为和称为和的析取的析取, ,记为记为。为真当且仅当与至少为真当且仅当与至少有一个为真。真值表如下：有一个为真。真值表如下：3.3.析取词析取词“”13 定义定义：设，是命题，复合命题设，是命题，复合命题“如果，则如果，则”称为蕴涵称为蕴涵, ,记为记为: :。 称为条件，为结论。规定称为条件，为结论。规定为假当且仅当为假当且仅当为真而为假。为真而为假。4.4.蕴涵词蕴涵词 “ “”PQ “如果P,则Q”“P是Q的充分条件”“Q是P的必要条件”“Q每当P”14 在日常生活中在日常生活中,蕴含式中条件与结论是有逻辑联系的，即有蕴含式中条件与结论是有逻辑联系的，即有因果关系，称为即形式蕴含因果关系，称为即形式蕴含.p在数理逻辑中在数理逻辑中,蕴含式中条件和结论不一定有因果关系，蕴含式中条件和结论不一定有因果关系，即实质蕴含。即实质蕴含。 例：如果太阳从西方升起，我就可以长生不例：如果太阳从西方升起，我就可以长生不老。老。p逆命题逆命题 of pq : qp p逆反命题逆反命题 of pq : q p形式蕴含与实质蕴含形式蕴含与实质蕴含15定义：定义： 设，是命题，复合命题设，是命题，复合命题“当且仅当当且仅当”称为等值。记为：称为等值。记为： 为真当且仅当与同时为真或同时为假。为真当且仅当与同时为真或同时为假。5. 5. 等值等值( (双条件双条件) )联接词联接词“”16 例：例：非本仓库工作人员，一律不得入内。非本仓库工作人员，一律不得入内。 令令 P P：某人是仓库工作人员；：某人是仓库工作人员； Q Q：某人可以进入仓库：某人可以进入仓库。 则上述命题可表示为：则上述命题可表示为：P P Q Q17命题的符号化命题的符号化使用上面介绍的逻辑联结词使用上面介绍的逻辑联结词, ,可将一些自然语句翻可将一些自然语句翻译成逻辑式译成逻辑式. .即命题符号化即命题符号化. . （1 1）从语句中分析出各原子）从语句中分析出各原子( (简单简单) )命题，将它们符号命题，将它们符号化化( (用字母表示用字母表示) ) （2 2）使用合适的命题联结词，把原子命题逐个联结起）使用合适的命题联结词，把原子命题逐个联结起来，组成复合命题的符号化表示。来，组成复合命题的符号化表示。18例：用符号形式表示下列命题。例：用符号形式表示下列命题。 （1 1）如果明天早上下雨或下雪，那么我不去学校）如果明天早上下雨或下雪，那么我不去学校 （2 2）如果明天早上不下雨且不下雪，那么我去学校。）如果明天早上不下雨且不下雪，那么我去学校。 （3 3）如果明天早上不是雨夹雪，那么我去学校。）如果明天早上不是雨夹雪，那么我去学校。 （4 4）只有当明天早上不下雨且不下雪时，我才去学校。）只有当明天早上不下雨且不下雪时，我才去学校。 令令 P P：明天早上下雨；：明天早上下雨； Q Q：明天早上下雪；：明天早上下雪； R R：我去学校。：我去学校。 （1）（）（PQ） R； （2）（）（P Q）R；（3）(PQ）R （4） R(P Q） 19例例: :不是鱼死，就是网破不是鱼死，就是网破设：鱼死，：网破设：鱼死，：网破则为：则为： (P(PQ) Q) ( P PQ)Q)注意注意: : l 命题符号化时命题符号化时, ,由于自然语言丰富多彩且有时还具有二义由于自然语言丰富多彩且有时还具有二义性，只有在具体的语言环境中，每个联接词才有确切的含性，只有在具体的语言环境中，每个联接词才有确切的含义，因此具体问题要具体分析义，因此具体问题要具体分析; ;l 复合命题的真值只取决于构成它的各原子命题的复合命题的真值只取决于构成它的各原子命题的( (真）值，真）值，而与这些原子命题的具体内容无关。而与这些原子命题的具体内容无关。20o 上面定义的五个联结词，他们各自可以表示上面定义的五个联结词，他们各自可以表示自然语言中的一些常用语句。要表达更复杂自然语言中的一些常用语句。要表达更复杂的语句，还可能会用到多个联结词，形成更的语句，还可能会用到多个联结词，形成更复杂的复合命题。复杂的复合命题。21基本定义：命题变元与命题公式基本定义：命题变元与命题公式 2 2命题变元：命题变元： 一个没有指定具体内容的命题符号：一个没有指定具体内容的命题符号： 即命题的真假没有指定。即命题的真假没有指定。 如果没对一个命题变元赋以内容时，它的值不能确如果没对一个命题变元赋以内容时，它的值不能确定，一旦用一个具体的命题代入，它的真值就确定了。定，一旦用一个具体的命题代入，它的真值就确定了。 1.1.命题常元：一个表示确定命题的大写字母：命题常元：一个表示确定命题的大写字母： 即命题的值已确定。即命题的值已确定。22命题公式命题公式 命题公式（或简称公式）是由命题常元（命题公式（或简称公式）是由命题常元（T T和和F F）、命题）、命题变元以及命题联结词按一定的规则产生的符号串。变元以及命题联结词按一定的规则产生的符号串。定义定义 （命题公式的递归定义。）（命题公式的递归定义。） （1 1）单个命题符号是公式；）单个命题符号是公式； （2 2）如果）如果A A是命题公式，则是命题公式，则AA是命题公式；是命题公式； （3 3）如果）如果A A和和B B是命题公式，则（是命题公式，则（ABAB），）， （ABAB）,(AB,(AB）,(A ,(A B B）也是命题公式；）也是命题公式； 有限次地利用上述（有限次地利用上述（1 1）（3 3）而产生的符号串是命题公）而产生的符号串是命题公式。式。 23例例1 1 判断下列符号串是否为命题公式。判断下列符号串是否为命题公式。 （1 1） (P(QPR(P(QPR）) )； （2 2）(PQ)(QR)(PQ)(QR) 为了省掉一些括号为了省掉一些括号, ,作如下约定：作如下约定：1.1. 五种连接词的五种连接词的运算优先级运算优先级的次序由高到低如下：的次序由高到低如下： ， ， ， 2.2. 多个同类联接词按从左到右的优先次序运算。多个同类联接词按从左到右的优先次序运算。3.3. 公式公式（ A A ）的括号可省略）的括号可省略4.4. 整个公式的最外层括号可省略整个公式的最外层括号可省略24q 例：以下符号串是命题公式，可按定义生成。例：以下符号串是命题公式，可按定义生成。 （ P）（P Q） R） Q） 按约定可省掉一些（）简化写成：按约定可省掉一些（）简化写成： P（PQ） R Q25 命题公式的真假值是不确定的。当命题公式中命题公式的真假值是不确定的。当命题公式中所有的命题变元都代以命题时，命题公式就变为所有的命题变元都代以命题时，命题公式就变为命题。命题。 即所有公式中的命题变元用指定的命题（真值）即所有公式中的命题变元用指定的命题（真值）代入（或指派），就得到一个公式的值。代入（或指派），就得到一个公式的值。262.2.公式的解释公式的解释( (指派指派) )l设设G G是命题公式，是命题公式，A A1 1，A A2 2，A An n是出现在是出现在G G中的所有命题变中的所有命题变元，指定元，指定A A1 1,A,A2 2, ,A An n的一组真值的一组真值（a a1 1,a,a2 2, ,a an n)a)ai i T,FT,F,i=1,i=1,n, n, 则这组真值称为公式则这组真值称为公式G G的一个解释。的一个解释。 例如公式例如公式: :(PQ) 的解释为的解释为:(T,T)(T,F),(F,T),(F,F) 或表示为或表示为: :(1,1),(1,0),(0,1),(0,0)(1,1),(1,0),(0,1),(0,0)l由定义知，含由定义知，含n(nn(n 1)1)个命题变元的命题公式共有个命题变元的命题公式共有2 2n n个不同个不同的解释。的解释。l可以采用真值表的方法，将一个命题公式的所有解释与可以采用真值表的方法，将一个命题公式的所有解释与公式的真值对应起来，形成该命题公式的真值表。公式的真值对应起来，形成该命题公式的真值表。27例：公式：例：公式：在解释在解释(0(0，0)0)，(0(0，1 1）和）和（1 1，1 1）下为真，在其他解释下为假。）下为真，在其他解释下为假。 公式的真值表公式的真值表28(PQ)(PQ)RR的真值表的真值表PQR(PQ)(PQ)RR000011110011001101010101 0 1 0 1 0 0 0 1 29判断判断 p p (q (q r r) ) 和（和（p p q)q) (p(p r r) )是否等值是否等值的真值表的真值表 30逻辑运算和位运算逻辑运算和位运算o 计算机用位（计算机用位（bit)表示信息。位是一个具有两个可能值的表示信息。位是一个具有两个可能值的符号，即符号，即0和和1。计算机的位运算对应于逻辑联结词。只。计算机的位运算对应于逻辑联结词。只要在位运算符要在位运算符(AND(AND），）， （OROR）和）和（XORXOR）的真值表）的真值表中用中用1 1代替代替T T，用，用0 0代替代替F F即可。即可。o 信息一般用位串信息一般用位串( (即即0 0和和1 1构成的序列构成的序列) )表示。对位串的运算表示。对位串的运算即可用来处理信息。即可用来处理信息。xyx OR yx AND yx XOR y0011010101110001011031命题逻辑的应用命题逻辑的应用o 逻辑在数学、计算机科学一其他许多学科有着重要的应用。例如，数学，自然科学以及自然语言中的语句通常不太准确，甚至有歧义，为了使其精确表达，可以将它们翻译成逻辑语言。32命题逻辑应用实例命题逻辑应用实例 1.系统规范说明系统规范说明:在描述硬件系统和软件系统时，系统和软件工程师根据自然语言描述的需求，生成精确而无二义性的规范说明，这些规范说明可作为系统开发的规范说明。 例1:使用逻辑联结词表示规范说明:“当文件系统已满时，不能够发送自动应答”。 令p表示：能够发送自动应答，令q表示:文件系统满了。则该规范说明可以表示成:q p33命题逻辑的应用命题逻辑的应用例2:确定下列系统规范说明是否是一致的。确定下列系统规范说明是否是一致的。“诊断消息存储在缓冲区中或者被重传.”“诊断消息没有存储在缓冲区中。”如果诊断消息存储在缓冲区中，那么它被重传。”（备注: 三个规范说明都能同时为真则表示是一致的)。34布尔搜索布尔搜索o 逻辑联结词广泛用于大量信息搜索中。例如网页索引。由于搜索采用命题逻辑技术，所以称为布尔搜索。o 例:网页搜索。大部份Web搜索引擎支持布尔搜索技术，以有助于寻找有关特定主题的网页。基本都支持AND，OR 及NOT等。(但用户不需要写出来)。35逻辑电路逻辑电路o 命题逻辑可应用于计算机硬件的设计。36思考题：利用命题逻辑解决问题思考题：利用命题逻辑解决问题 问题：三人估计比赛结果，甲说问题：三人估计比赛结果，甲说“A A第一，第一，B B第二第二”，乙说，乙说“ “ C C第二，第二，D D第四第四“，丙说，丙说”A A第二，第二，D D第四第四“，结果三人的，结果三人的估计都对了一半，试确定估计都对了一半，试确定A A，B B，C C，D D的名次。的名次。 解：解： 设设 P: AP: A第一第一; Q: B; Q: B第二第二; R: C; R: C第二第二 S: DS: D第第四四; H: A; H: A第二第二; ;则则 P P Q ,R Q ,R SS和和H H S S 的值都为的值都为1;1;而而P PH,H, QR QR和和QH QH 的值都为的值都为0;0;因此可得出因此可得出:P:P和和R R及及H H的值为的值为0,Q0,Q和和S S的值为的值为1.1.由此得出由此得出:B:B第二第二,D,D第四第四,A,A第三第三,C,C第一第一 371.2 1.2 重言式重言式定义：定义： 设设G G是一个命题公式。是一个命题公式。 重言式重言式： G G在它的所有解释下均为真，则称在它的所有解释下均为真，则称G G是永真是永真 的，或称的，或称G G为重言式；为重言式； 矛盾式矛盾式：若：若G G在它的所有解释下均为假，则称在它的所有解释下均为假，则称G G是永假是永假的，或称的，或称G G为矛盾式；为矛盾式； 可满足式可满足式：若：若G G至少存在一个指派，使其值为真，则至少存在一个指派，使其值为真，则称称G G为可满足的，如果至少存在一个指派，使其值为为可满足的，如果至少存在一个指派，使其值为假，则称此公式为非永真。假，则称此公式为非永真。38重言式（永真式）重言式（永真式）我们只研究重言式，因为：我们只研究重言式，因为：l 重言式的否定是矛盾式，重言式的否定是矛盾式， 矛盾式的否定是重言式。故矛盾式的否定是重言式。故只需研究其一。只需研究其一。l 重言式的合取、析取、蕴含、等值等都是重言式，由重言式的合取、析取、蕴含、等值等都是重言式，由简单的重言式可推出复杂的重言式。简单的重言式可推出复杂的重言式。l 重言式中有许多非常有用的恒等式和永真蕴含式。重言式中有许多非常有用的恒等式和永真蕴含式。39例如： PPPP：重言式：重言式 PPPP：矛盾式：矛盾式 (P(PQ) RQ) R：偶然式（可满足式）：偶然式（可满足式）40定义：定义： 对于公式对于公式A A和和B B，如果在任何相同的解释，如果在任何相同的解释下，其相下，其相应的值都相同，则称应的值都相同，则称A A与与B B逻辑等值（价），记为：逻辑等值（价），记为：A AB B。读作。读作“A A等价于等价于B”B”。或者说如果。或者说如果A AB是重言是重言式式, ,则称则称A AB.B.v注意注意: : 符号符号“”是关系符，不是逻辑联结词。是关系符，不是逻辑联结词。 A AB B当且仅当当且仅当A AB B是重言式。是重言式。恒等式恒等式41基本的逻辑恒等式（基本的逻辑恒等式（P8-P9P8-P9）1.1. 双重否定律：双重否定律：P PP P2.2. 等幂律：等幂律：P PPPPP，P PPPPP3.3. 交换律：交换律：P PQ QQPQP，PQPQQPQP4.4. 结合律：结合律：( (P PQ)Q)R RP(QR)P(QR) ( (P PQ)Q)R RP(QR)P(QR)5.5. 分配律分配律：P(QR)P(QR)(P(PQ)(PQ)(PR)R) P(QR) P(QR)(P(PQ)Q)(P(PR)R)6.6. De MorganDe Morgan律律： （PQPQ） PP Q Q （PQPQ） PP Q Q7.7. 吸收律：吸收律：PP（PQPQ）P P P P（PQPQ）P P8.8. 零律：零律： P1P11 P01 P00 09.9. 同一律：同一律：P0P0P P1P P1P P10.10.补余律：补余律：PP P P1 P1 P P P0 0补充补充： P PQ QPQPQ P PQ Q Q QPP P PQ Q(P(PQ)(Q)(Q QP)P) (PQ)(PQ)(PQ)(PQ) (P (P(Q(QR) R) P PQ QR R 43思考1o 思考思考:对联结词是否还可以归约对联结词是否还可以归约,即五种联结词即五种联结词是否都是必要的是否都是必要的?o 如果能归约如果能归约,能归约到什么程度能归约到什么程度?44恒等式的判别：真值表方法和命题演算方法恒等式的判别：真值表方法和命题演算方法 例例1 1 用真值表方法证明用真值表方法证明 E E1010： (P (P Q) Q) P PQ Q P Q0 00 11 1 1 0 (P Q)1000 PQ 10001111 (P Q) PQ45例例2 2 用真值表方法证明用真值表方法证明E E1111：P PQ QP P Q Q解：解： 构造构造P PQ Q P P Q Q的真值表如下：的真值表如下： PQPQ P Q00111011111000111111PQ P Q46PQ PQ 是否成立？是否成立？由于公式由于公式PQ和和P Q所标记的列不完全相同所以，因所标记的列不完全相同所以，因此此PQ PQ 不成立。不成立。PQ P Q PQPQ00111101100101101011001147 ( (1) 1) 代入规则代入规则 重言式的任何重言式的任何代入实例代入实例仍是重言式。仍是重言式。2 2命题演算方法命题演算方法 例：例： （P PQ Q） （ Q QP P）是重言式，）是重言式，用公式用公式 AB AB 代换其中的命题变元代换其中的命题变元P P得到的新公式得到的新公式 （ABAB）Q Q）（ Q Q（ABAB）仍是重言式。）仍是重言式。 注意：注意： 因为因为A A B B 当且仅当当且仅当 A A B B是重言式。所是重言式。所以，对于基本恒等式中的任一命题变元出现的每一处均用以，对于基本恒等式中的任一命题变元出现的每一处均用同一命题公式代入，所得到的仍是恒等式。同一命题公式代入，所得到的仍是恒等式。48说明：说明：基本恒等式表中，基本恒等式表中，P,Q,RP,Q,R可以表示任意命题公式。利用可以表示任意命题公式。利用代入定理，由这些恒等式可以得到无穷多个恒等式。代入定理，由这些恒等式可以得到无穷多个恒等式。例如：由例如：由 PP P P1 1 可知：可知：(PQ)(PQ) (PQ)(PQ)1 1 ( ( P) P) ( ( P)P)1 1. (2)(2)替换替换规则规则 子公式子公式: : 设设C C是命题公式是命题公式A A的一部分，且的一部分，且C C本身也是本身也是一个命题公式，则称一个命题公式，则称C C为公式为公式A A的子公式。的子公式。 例如例如 设公式设公式A=A=（ PQPQ）（P PQ Q）（RR S S） 则则 PQPQ，P PQ Q，（，（P PQ Q）（RR S S）等均是）等均是A A的的子公式，子公式，替换规则：替换规则：设设C C是公式是公式A A中的子公式，且中的子公式，且C CD D。如果将公。如果将公式式A A中的子公式中的子公式C C置换成公式置换成公式D D之后，得到的公式是之后，得到的公式是B B，则，则A AB B。 (3) (3) 等值演算等值演算 等值演算是指利用已知的一些恒等式，根据置换等值演算是指利用已知的一些恒等式，根据置换规则、代入规则推导出另外一些恒等式的过程。规则、代入规则推导出另外一些恒等式的过程。 由代入规则知前述的基本等值（恒等）式不仅对任由代入规则知前述的基本等值（恒等）式不仅对任意的命题变元意的命题变元P P，Q Q，R R是成立的，而且当是成立的，而且当P P，Q Q，R R分别为分别为命题公式时，这些等值式仍然成立命题公式时，这些等值式仍然成立 例例2 2 证明：证明：（PQ）（RQ）（PR）Q证明证明 （PQ）（RQ） （ PQ）( RQ) E11 （ P R）Q E3( 分配律分配律) (PR)Q E10(德德.摩根律摩根律) (PR) Q E11 51 例例3 3 证明下列命题公式的恒等关系证明下列命题公式的恒等关系 (P Q ) ( P ( P Q ) ) P Q 证明证明： (P Q) ( P ( P Q) (P Q) ( ( P P ) Q ) (结合律结合律) (P Q) ( P Q) (等幂律等幂律) ( P Q ) ( P Q ) (交换律交换律) P (Q (P Q) (结合律结合律) P Q (交换律，吸收律交换律，吸收律) 52例例4 4 判别下列公式的类型。判别下列公式的类型。 （1） Q ( P（ PQ）) （2）（）（PQ） P解解（1） Q （ P（ PQ） Q （P（ PQ） Q （P P）（PQ） Q （1（PQ） Q （PQ） Q P Q （Q Q） P F 所以所以Q ( P ( PQ)是矛盾式。是矛盾式。 53（2） （PQ） P （ PQ） P P 吸收律吸收律 该公式是可满足式。该公式是可满足式。 54例例5 5：证明公式：证明公式P P( (（ Q Q P P） Q Q）为重言式。）为重言式。 P P( (（ Q Q P P） Q Q）P P（ Q Q Q Q） （P P Q Q） （分配律）（分配律）P P（F F （P P Q Q） （补余律）（补余律）P P（P P Q Q） （同一律）（同一律）P P （ P PQ Q） （De MorganDe Morgan律）律）（P PP P）Q Q （结合律）（结合律）1 1Q Q （补余律）（补余律）T T （零律）（零律） 55命题公式逻辑恒等的应用：命题公式逻辑恒等的应用： 1、判定两个命题公式是否逻辑等值；、判定两个命题公式是否逻辑等值； 2、判断是否为重言式或矛盾式；、判断是否为重言式或矛盾式； 3、对命题公式进行化简、对命题公式进行化简56逻辑等值应用实例逻辑等值应用实例将下面用高级语言写成的一段程序化简：将下面用高级语言写成的一段程序化简： if A then if B then X else Y else if B then X else YATFTFFA 57此段程序执行此段程序执行X X的条件为的条件为： ABAB执行执行Y Y的条件为的条件为： ABAB它们分别可化简为：它们分别可化简为：ABAB (AA) B (由分配律由分配律) TB B而而ABAB也可化简也可化简ABABB 所以上述语句可化简成：所以上述语句可化简成：if B then X else Y58永真蕴含式永真蕴含式 定义定义 如果如果 A AB B 是永真式，则称其为永真蕴是永真式，则称其为永真蕴含式含式, ,记作记作A AB, B, 即即A AB BT T，则称公式，则称公式A A永真蕴永真蕴含公式含公式B B。注意：注意： 符号符号“”和和 “ “”的区别的区别59基本的永真蕴含式基本的永真蕴含式 P10P10注意：这些基本的永真蕴含式将作为以后注意：这些基本的永真蕴含式将作为以后我们利用命题逻辑进行逻辑推理的基础！我们利用命题逻辑进行逻辑推理的基础！永真蕴含式的判别方法永真蕴含式的判别方法 判定判定“A B”是否成立的问题可转化为判定是否成立的问题可转化为判定A B是否为重言式，有下述判定方法：是否为重言式，有下述判定方法： 1. 真值表法；真值表法； 2. 假定前件假定前件A为真，看结论是否一定为真为真，看结论是否一定为真 3. 假定后件假定后件B为假，看前件是否一定为假为假，看前件是否一定为假 1. 真值表法真值表法 例例 证明证明 ：（：（PQ）（P R）（Q R） R61 2. 假定前件为真假定前件为真 假定前件为真，检查在此情况下，其结论是否也为真。假定前件为真，检查在此情况下，其结论是否也为真。 例例证明证明 : Q （PQ） P证明证明:令前件令前件 Q（PQ）为真，）为真，则则 Q为真为真, 且且PQ为真。为真。于是于是Q为假，因而为假，因而P也为假。因此也为假。因此 P为真为真。故上面蕴含式故上面蕴含式 成立。成立。62 3、 假定结论为假假定结论为假 假定结论为假，检查在此情况下，其前件是否也为假假定结论为假，检查在此情况下，其前件是否也为假. . 例例 证明蕴含式证明蕴含式 (PQ) (RS) (P R) (Q S)证明证明 令结论令结论(P R)(Q S)为假，则为假，则P R为真，为真，Q S为假为假,于是于是P、R均为真，而均为真，而Q和和S至少一个为假。至少一个为假。 由此可知由此可知 PQ与与RS中至少一个为假中至少一个为假, 因此因此(PQ) (RS)为假为假.故上述蕴含式成立。故上述蕴含式成立。63 对偶式及对偶原理对偶式及对偶原理 定义定义 设设A A是一个仅含有联结词是一个仅含有联结词 、 和和的命题公式，将公式的命题公式，将公式A中用中用代替代替、用、用代替代替、用、用T代替代替F、用、用F代替代替T，所得的命题公式称为，所得的命题公式称为A的对偶式，记为的对偶式，记为A*。 例如例如：PQ R和和（P Q） R互为对偶式互为对偶式 PQR的对偶式是的对偶式是( P Q) R64定理：定理： 设设A A是一个仅含有联结词是一个仅含有联结词 、 和和的命题公式，的命题公式，P1，P2. Pn是出现于其中的全部命是出现于其中的全部命题变元，则题变元，则 A(P1，P2. Pn) A*( P1， P2. Pn) A ( P1， P2. Pn) A*(P1，P2. Pn)65对偶原理对偶原理对偶原理对偶原理: 设设A和和B是两个仅含有联结词是两个仅含有联结词 、 和和的命的命题公式，如果题公式，如果A B， 则则A* B*。 利用对偶原理可知：利用对偶原理可知： （1 1）若）若A A为重言式（永真式），则为重言式（永真式），则A A* *为矛盾式。为矛盾式。 （2 2）由一些等值式）由一些等值式, ,利用对偶原理则可得到另一些等值式。利用对偶原理则可得到另一些等值式。 如：如： P(QR)P(QR)(P(PQ)(PQ)(PR) R) 则立即可知则立即可知: : P P(Q(QR)R) (P (PQ)Q)(P(PR) R) 66可满足性的应用可满足性的应用o 在不同领域：如机器人学，软件测试，计算机辅助设计、机器视觉、集成电路设计、计算机网络以及遗传学中的许多问题都可以用命题可满足性来建立模型。o 例如:数独谜题（要求每一行，每一列、每个小九宫格都每包含九个不同的数字）67数独谜题的求解数独谜题的求解(命题逻辑法命题逻辑法)o 用命题逻辑描述即为: p（i,j,n)o 给定一个数独谜题，要求解这个谜题，我们可以寻找一个可满足性问题的解，该问题要求一组729个变元p(i,j,n)的真值，使得所有列出的合取式为真。i=1 n=1 j=1i=9 n=9 j=9i=1 n=1 j=1i=9 n=9 j=968可满足性问题求解可满足性问题求解 可满足性问题求解: 真值表可以判定复合命题是否为可满足的,或者等价地,判断其否定是否为永真式）。当含少量命题变元时，可以手动来完成，但当命题变元很多时，就不切实际了。例如，当有20个命题变元时，真值表就有220行，显然需要计算机来判断是否是可满足式。 当许多应用建模涉及成千上万个变量的复合命题的可满足性时，如当变量为1000时,要检查21000种可能的真值组合中的每一种,一台计算机在几万亿年之内都不可能完成!（即这是一个NP难的问题!-算法课中讲解算法复杂性问题） 但是，在实际应用中，某些特定类型的复合命题的可满足性问题求解方法还是有一些进展，如数独谜题的求解。69 1.判断下列等值式是否成立判断下列等值式是否成立 （1）（）（PQ） （R Q）（PR） Q （2） （PQ）（P Q）（ PQ） 2判定下列蕴含式是否成立判定下列蕴含式是否成立 P(QR)(PQ)(PR）练习练习70解解（1）（）（PQ）（RQ）（ PQ） （ RQ）（ P R）Q （PR）Q（2） （PQ） (（PQ）（QP）) (（ PQ）（ QP）) （P Q）（ PQ）（PR）Q712 2判定蕴含式判定蕴含式 P P( (Q QR)R)(P PQ)Q)( (P PR R）是否成立）是否成立 解假定结论（解假定结论（PQ）（PR）为假，）为假，则则PQ为真，为真，PR为假。为假。由由P PR R为假为假, ,得得P P为真，为真，R R为假。为假。 又又PQ为真，故得为真，故得Q为真。为真。于是于是P为真，为真，QR为假。为假。从而从而 P（QR）为假。）为假。因此蕴含式成立。因此蕴含式成立。72o 讨论讨论: 判断下面命题是否成立判断下面命题是否成立? (1) 若 A B,则则 A B (2) 若A B,则则 A B73注意: 理解理解基本恒等式和基本永真蕴含式 记忆记忆 应用应用 它们是我们以后利用命题逻辑进行推理的基础.74基本的逻辑恒等式（基本的逻辑恒等式（P8-P9P8-P9）1.1. 双重否定律：双重否定律：P PP P2.2. 等幂律：等幂律：P PPPPP，P PPPPP3.3. 交换律：交换律：P PQ QQPQP，PQPQQPQP4.4. 结合律：结合律：( (P PQ)Q)R RP(QR)P(QR) ( (P PQ)Q)R RP(QR)P(QR)5.5. 分配律分配律：P(QR)P(QR)(P(PQ)(PQ)(PR)R) P(QR) P(QR)(P(PQ)Q)(P(PR)R)756.6. De MorganDe Morgan律律： （PQPQ） PP Q Q （PQPQ） PP Q Q7.7. 吸收律：吸收律：PP（PQPQ）P P P P（PQPQ）P P8.8. 零律：零律： P1P11 P01 P00 09.9. 同一律：同一律：P0P0P P1P P1P P10.10.补余律：补余律：PP P P1 P1 P P P0 0补充补充： P PQ QPQPQ P PQ Q Q QPP P PQ Q(P(PQ)(Q)(Q QP)P) (PQ)(PQ)(PQ)(PQ) (P (P(Q(QR) R) P PQ QR R 76最常用的推理规则(常用的永真蕴含式)1.1. 附加：附加：P P (P(P Q)Q)， Q Q (P(P Q)Q)2.2. 化简：化简：(P(P Q) Q) P (PP (P Q) Q) Q Q3.3. 合取：合取：P,Q P,Q P P Q Q4.4. 假言推理：假言推理：P PQ,P Q,P Q Q5.5. 析取三段论：析取三段论：P P Q, Q, P P Q Q6.6. 拒取式：拒取式：P PQ, Q, Q Q P P7.7. 假言三段论：假言三段论：P PQ,QQ,QR R P PR R8.8. 构造性二难构造性二难: P: PQ,RQ,RS,PS,P R R Q Q S S771.4 1.4 范式范式 命题公式千变万化，这对研究其性质和应用研究带来很大的困难。为此，我们有必要研究如何将命题公式转化为其逻辑等价的标准形式标准形式的问题，以简化研究工作并方便应用。这种标准形式称为范式。 1.合取范式与析取范式 2.主合取范式和主析取范式78 范式范式( (主析取范式和主合取范式主析取范式和主合取范式) ) （一）极小项、极大项（一）极小项、极大项 定义定义 设有命题变元设有命题变元P P1 1，P P2 2，,P,Pn n ，形如形如P P1 1* *PP2 2* *PP3 3* *PPn n* * 的命题公式称为是由命题变元的命题公式称为是由命题变元P P 1 1，P P2 2，P Pn n所产生的极小项。而形所产生的极小项。而形如如 P P1 1* *PP2 2* *PP3 3* *PPn n* * 的命题公式称为是由命题变元的命题公式称为是由命题变元P P1 1，P P2 2，P Pn n所产所产生的极大项。其中生的极大项。其中P Pi i* *为为P Pi i或为或为 P Pi i(i=1,2,(i=1,2,n).n). 例如例如, P, P1 1PP2 2PP3 3， P P1 1PP2 2 P P3 ,3 , P P1 1 P P2 2PP3 ,3 ,. . 即每个变元在析取式（合取式）中出现一次且只出现一次，出现的形式是变即每个变元在析取式（合取式）中出现一次且只出现一次，出现的形式是变元或变元的否定则这样的析取式（合取式）称为关于这些变元的极大项元或变元的否定则这样的