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

《离散数学的命题逻辑ppt课件》由会员分享，可在线阅读，更多相关《离散数学的命题逻辑ppt课件（122页珍藏版）》请在金锄头文库上搜索。

1、数理逻辑: 命题逻辑逻辑逻辑o逻辑不仅对理解数学推理十分重要，而且在逻辑不仅对理解数学推理十分重要，而且在计算机科学中有许多应用。这些逻辑规则用于计算机科学中有许多应用。这些逻辑规则用于计算机电路设计、计算机程序构造、程序正确计算机电路设计、计算机程序构造、程序正确性证明等许多方面！性证明等许多方面！2Copyright2007byXuDezhi3逻辑学逻辑学o逻辑学逻辑学=研究正确推理的科学研究正确推理的科学o推理：由一个或几个命题推出另外一个命题的思维形式。推理：由一个或几个命题推出另外一个命题的思维形式。o逻辑学的作用逻辑学的作用1、有助于准确、严密地表达和交流思想。2、有助于培养、提高

2、认知能力，获得间接知识。3、有助于识别、驳斥谬误和诡辩，进行批判性思维。p数理逻辑：用数学方法研究推理的一门学科数理逻辑：用数学方法研究推理的一门学科n一套符号体系 + 一组推理规则3Copyright2007byXuDezhi4 逻辑学逻辑学o逻辑学关注的是陈述（命题）之间的关系 。例如 :n我的表是数字的.n所有数字设备都依靠电池运行.n因此，我的表依靠电池运行o注意：逻辑学并不关心前面两个陈述（命题）的真假。但是，如果它们是真的，则推论也一定是真的。4p命题：命题：n凡是具有确定真假意义的陈述句均称为命题。凡是具有确定真假意义的陈述句均称为命题。p命题的值命题的值:n若为若为“真真”，用

3、或表示；，用或表示；n若为若为“假假”，用或表示。，用或表示。p由于一个命题的值只可能取由于一个命题的值只可能取“真真”或或“假假”两种值，两种值，因此，命题逻辑也称为因此，命题逻辑也称为“二值逻辑二值逻辑”。p延伸阅读:模糊逻辑基本概念基本概念:命题与命题的值命题与命题的值5下面三类陈述句是命题：下面三类陈述句是命题：1.现实可判断真假的陈述句。现实可判断真假的陈述句。2.目前还不知道真假，但它们本身是具有真假意目前还不知道真假，但它们本身是具有真假意义的。义的。3.其真假与讨论问题范围（论域）有关的陈述句其真假与讨论问题范围（论域）有关的陈述句（如：所有的人都爱跑步）。（如：所有的人都爱跑

4、步）。下面的不是命题：下面的不是命题：感叹句感叹句，疑问句，祈使句，疑问句，祈使句,非命题陈述句：悖论语句非命题陈述句：悖论语句(如如:我正在说谎我正在说谎)。6例：例：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) 火星上有水。火星上有水。 7p简单命题简单命题( (原子

5、命题）原子命题）它不能再分解成更它不能再分解成更简单的命题。简单的命题。p在命题逻辑中，简单命题被看作是一个整体，在命题逻辑中，简单命题被看作是一个整体，不再分析其内部的逻辑形式。不再分析其内部的逻辑形式。 常用大写字母：常用大写字母：P，Q，R，.表示简单命题。表示简单命题。 p例如：例如：P: 4P: 4是质数，是质数，Q Q：所有人都爱学习：所有人都爱学习简单命题与复合命题简单命题与复合命题8复合命题（命题的组合）复合命题（命题的组合）p复合（杂）命题复合（杂）命题命题可以通过逻辑联接词命题可以通过逻辑联接词构成新的命题，即复合命题。复合命题的子命构成新的命题，即复合命题。复合命题的子命

6、题也可以是复合命题。题也可以是复合命题。p例如：例如：n如果明天天气晴朗，我就到湘江边散步如果明天天气晴朗，我就到湘江边散步。n如果太阳从西边升起如果太阳从西边升起, ,我就可以长生不老。我就可以长生不老。 9命题可以通过一些逻辑联结词构成新的命题（复命题可以通过一些逻辑联结词构成新的命题（复合命题）合命题）1.否定词否定词: 定义定义：设是命题，复合命题：设是命题，复合命题“ ”是的否定，是的否定，规定规定 为真当且仅当为假。为真当且仅当为假。例：例：长沙的秋天景色很美。长沙的秋天景色很美。 ：Q:上海处处都清洁。上海处处都清洁。 Q：五种常用的命题（逻辑）联接词五种常用的命题（逻辑）联接词

7、10定义定义：设，是命题，复合命题设，是命题，复合命题“并且并且”称为称为和的合取和的合取, ,写成写成。为真当且仅当为真当且仅当与同时为真。真值表如下：与同时为真。真值表如下：2. 2. 合取词合取词 “”11 定义定义：设，是命题，复合命题设，是命题，复合命题“或者或者”称为和称为和的析取的析取, ,记为记为。为真当且仅当与至少为真当且仅当与至少有一个为真。真值表如下：有一个为真。真值表如下：3.3.析取词析取词“”12 定义定义：设，是命题，复合命题设，是命题，复合命题“如果，则如果，则”称为蕴涵称为蕴涵, ,记为记为: :。 称为条件，为结论。规定称为条件，为结论。规定为假当且仅当为为

8、假当且仅当为真而为假。真而为假。4.4.蕴涵词蕴涵词 “”PQ“如果P,则Q”“P是Q的充分条件”“Q是P的必要条件”“Q每当P”13在日常生活中在日常生活中,蕴含式中条件与结论是有逻辑联系的，即有蕴含式中条件与结论是有逻辑联系的，即有因果关系，称为即形式蕴含因果关系，称为即形式蕴含.p在数理逻辑中在数理逻辑中,蕴含式中条件和结论不一定有因果关系，蕴含式中条件和结论不一定有因果关系，即实质蕴含。即实质蕴含。例：如果太阳从西方升起，我就可以长生不例：如果太阳从西方升起，我就可以长生不老。老。p逆命题逆命题ofpq:qpp逆反命题逆反命题ofpq:qp形式蕴含与实质蕴含形式蕴含与实质蕴含14定义：

9、定义： 设，是命题，复合命题设，是命题，复合命题“当且仅当当且仅当”称为等值。记为：称为等值。记为： 为真当且仅当与同时为真或同时为假。为真当且仅当与同时为真或同时为假。5. 5. 等值等值( (双条件双条件) )联接词联接词“”15例：例：非本仓库工作人员，一律不得入内。非本仓库工作人员，一律不得入内。 令令 P P：某人是仓库工作人员；某人是仓库工作人员； Q Q：某人可以进入仓库某人可以进入仓库。则上述命题可表示为：则上述命题可表示为：P P Q Q16命题的符号化命题的符号化使用上面介绍的逻辑联结词使用上面介绍的逻辑联结词, ,可将一些自然语句翻可将一些自然语句翻译成逻辑式译成逻辑式.

10、 .即命题符号化即命题符号化. .（1 1）从语句中分析出各原子）从语句中分析出各原子( (简单简单) )命题，将它们符号命题，将它们符号化化( (用字母表示用字母表示) ) （2 2）使用合适的命题联结词，把原子命题逐个联结起）使用合适的命题联结词，把原子命题逐个联结起来，组成复合命题的符号化表示。来，组成复合命题的符号化表示。17例：用符号形式表示下列命题。例：用符号形式表示下列命题。 （1 1）如果明天早上下雨或下雪，那么我不去学校）如果明天早上下雨或下雪，那么我不去学校 （2 2）如果明天早上不下雨且不下雪，那么我去学校。）如果明天早上不下雨且不下雪，那么我去学校。 （3 3）如果明天

11、早上不是雨夹雪，那么我去学校。）如果明天早上不是雨夹雪，那么我去学校。 （4 4）只有当明天早上不下雨且不下雪时，我才去学校。）只有当明天早上不下雨且不下雪时，我才去学校。 令令 P P：明天早上下雨；明天早上下雨； Q Q：明天早上下雪；明天早上下雪； R R：我去学校。我去学校。 （1）（）（PQ）R；（2）（）（PQ）R；（3）(PQ）R （4）R(PQ） 18例例: :不是鱼死，就是网破不是鱼死，就是网破设：鱼死，：网破设：鱼死，：网破则为：则为： (P(PQ) Q) ( P PQ)Q)注意注意: : l命题符号化时命题符号化时, ,由于自然语言丰富多彩且有时还具有二义由于自然语言丰富

12、多彩且有时还具有二义性，只有在具体的语言环境中，每个联接词才有确切的含义，性，只有在具体的语言环境中，每个联接词才有确切的含义，因此具体问题要具体分析因此具体问题要具体分析; ;l 复合命题的真值只取决于构成它的各原子命题的复合命题的真值只取决于构成它的各原子命题的( (真）值，真）值，而与这些原子命题的具体内容无关。而与这些原子命题的具体内容无关。19o 上面定义的五个联结词，他们各自可以表示上面定义的五个联结词，他们各自可以表示自然语言中的一些常用语句。要表达更复杂的自然语言中的一些常用语句。要表达更复杂的语句，还可能会用到多个联结词，形成更复杂语句，还可能会用到多个联结词，形成更复杂的复

13、合命题。的复合命题。20基本定义：命题变元与命题公式基本定义：命题变元与命题公式2 2命题变元：命题变元： 一个没有指定具体内容的命题符号：一个没有指定具体内容的命题符号： 即命题的真假没有指定。即命题的真假没有指定。 如果没对一个命题变元赋以内容时，它的值不能确如果没对一个命题变元赋以内容时，它的值不能确定，一旦用一个具体的命题代入，它的真值就确定了。定，一旦用一个具体的命题代入，它的真值就确定了。 1.1.命题常元：一个表示确定命题的大写字母：命题常元：一个表示确定命题的大写字母： 即命题的值已确定。即命题的值已确定。21命题公式命题公式 命题公式（或简称公式）是由命题常元（命题公式（或简

14、称公式）是由命题常元（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）而产生的符号串是命题公）而产生的符号

15、串是命题公式。式。 22例例1 1 判断下列符号串是否为命题公式。判断下列符号串是否为命题公式。 （1 1） (P(QPR(P(QPR）) )； （2 2）(PQ)(PQ)(QR)(QR) 为了省掉一些括号为了省掉一些括号, ,作如下约定：作如下约定：1.1.五种连接词的五种连接词的运算优先级运算优先级的次序由高到低如下：的次序由高到低如下： ， ， ， 2.2.多个同类联接词按从左到右的优先次序运算。多个同类联接词按从左到右的优先次序运算。3.3.公式公式（ A A ）的括号可省略的括号可省略4.4.整个公式的最外层括号可省略整个公式的最外层括号可省略23q例：以下符号串是命题公式，可按定义

16、生成。例：以下符号串是命题公式，可按定义生成。（ P）（PQ） R） Q）按约定可省掉一些（）简化写成：按约定可省掉一些（）简化写成： P（PQ） R Q24 命题公式的真假值是不确定的。当命题公式中命题公式的真假值是不确定的。当命题公式中所有的命题变元都代以命题时，命题公式就变为所有的命题变元都代以命题时，命题公式就变为命题。命题。 即所有公式中的命题变元用指定的命题（真值）即所有公式中的命题变元用指定的命题（真值）代入（或指派），就得到一个公式的值。代入（或指派），就得到一个公式的值。252.2.公式的解释公式的解释( (指派指派) )l设设G G是命题公式，是命题公式，A A1 1，A

17、A2 2，AAn 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,n, ,i=1,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)个命题变元的命题公式共有个命

18、题变元的命题公式共有2 2n n个不同个不同的解释。的解释。l可以采用真值表的方法，将一个命题公式的所有解释与可以采用真值表的方法，将一个命题公式的所有解释与公式的真值对应起来，形成该命题公式的真值表。公式的真值对应起来，形成该命题公式的真值表。26例：公式：例：公式：在解释在解释(0(0，0)0)，(0(0，1 1）和）和（1 1，1 1）下为真，在其他解释下为假。）下为真，在其他解释下为假。 公式的真值表公式的真值表27(PQ)(PQ)RR的真值表的真值表PQR(PQ)(PQ)RR0000111100110011010101010101000128判断判断 p p ( (q q r r)

19、) 和（和（p p q)q) (p(p r r) )是否等是否等值的真值表值的真值表 29逻辑运算和位运算逻辑运算和位运算o计算机用位（计算机用位（bit)表示信息。位是一个具有两个可能值的表示信息。位是一个具有两个可能值的符号，即符号，即0和和1。计算机的位运算对应于逻辑联结词。只。计算机的位运算对应于逻辑联结词。只要在位运算符要在位运算符(AND(AND），）， （OROR）和）和（XORXOR）的真值表）的真值表中用中用1 1代替代替T T，用，用0 0代替代替F F即可。即可。o信息一般用位串信息一般用位串( (即即0 0和和1 1构成的序列构成的序列) )表示。对位串的运算表示。对位

20、串的运算即可用来处理信息。即可用来处理信息。xyx OR yx AND yx XOR y0011010101110001011030命题逻辑的应用命题逻辑的应用o逻辑在数学、计算机科学一其他许多学科有着重要的应用。例如，数学，自然科学以及自然语言中的语句通常不太准确，甚至有歧义，为了使其精确表达，可以将它们翻译成逻辑语言。31命题逻辑应用实例命题逻辑应用实例1.系系统规范范说明明:在描述硬件系统和软件系统时，系统和软件工程师根据自然语言描述的需求，生成精确而无二义性的规范说明，这些规范说明可作为系统开发的规范说明。 例1:使用逻辑联结词表示规范说明:“当文件系统已满时，不能够发送自动应答”。

21、令p表示：能够发送自动应答，令q表示:文件系统满了。则该规范说明可以表示成:q p32命题逻辑的应用命题逻辑的应用例2:确定下列系统规范说明是否是一致的。确定下列系统规范说明是否是一致的。“诊断消息存储在缓冲区中或者被重传.”“诊断消息没有存储在缓冲区中。”如果诊断消息存储在缓冲区中，那么它被重传。”（备注: 三个规范说明都能同时为真则表示是一致的)。33布尔搜索布尔搜索o逻辑联结词广泛用于大量信息搜索中。例如网页索引。由于搜索采用命题逻辑技术，所以称为布尔搜索。o例:网页搜索。大部份Web搜索引擎支持布尔搜索技术，以有助于寻找有关特定主题的网页。基本都支持AND，OR及NOT等。(但用户不需

22、要写出来)。34逻辑电路逻辑电路o命题逻辑可应用于计算机硬件的设计。35思考题：利用命题逻辑解决问题思考题：利用命题逻辑解决问题 问题：三人估计比赛结果，甲说问题：三人估计比赛结果，甲说“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第二第

23、二; ;则则 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第一第一361.2 1.2 重言式重言式定义：定义： 设设G G是一个命题公式。是一个命题公式。 重言式重言式： G G在它的所有解释下均为真，则称在它的所有解释下均为真，则称G G是永真是永真 的，或称的，或称G G为重言式；为重言式； 矛盾式矛盾式：若：若G G

24、在它的所有解释下均为假，则称在它的所有解释下均为假，则称G G是永假是永假的，或称的，或称G G为矛盾式；为矛盾式； 可满足式可满足式：若：若G G至少存在一个指派，使其值为真，则至少存在一个指派，使其值为真，则称称G G为可满足的，如果至少存在一个指派，使其值为为可满足的，如果至少存在一个指派，使其值为假，则称此公式为非永真。假，则称此公式为非永真。37重言式（永真式）重言式（永真式）我们只研究重言式，因为：我们只研究重言式，因为：l 重言式的否定是矛盾式，重言式的否定是矛盾式， 矛盾式的否定是重言式。故矛盾式的否定是重言式。故只需研究其一。只需研究其一。l 重言式的合取、析取、蕴含、等值等

25、都是重言式，由重言式的合取、析取、蕴含、等值等都是重言式，由简单的重言式可推出复杂的重言式。简单的重言式可推出复杂的重言式。l 重言式中有许多非常有用的恒等式和永真蕴含式。重言式中有许多非常有用的恒等式和永真蕴含式。38例如： PPPP：重言式：重言式 PPPP：矛盾式：矛盾式 (P(PQ) RQ) R：偶然式（可满足式）：偶然式（可满足式）39定义：定义： 对于公式对于公式A A和和B B，如果在任何相同的解释如果在任何相同的解释下，其相下，其相应的值都相同，则称应的值都相同，则称A A与与B B逻辑等值（价），记为：逻辑等值（价），记为：A AB B。读作。读作“A A等价于等价于B”B”

26、。或者说如果。或者说如果A AB是重言式是重言式, ,则称则称A AB.B.v注意注意: : 符号符号“”是关系符，不是逻辑联结词。是关系符，不是逻辑联结词。 A AB B当且仅当当且仅当A AB B是重言式。是重言式。恒等式恒等式40基本的逻辑恒等式（基本的逻辑恒等式（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(Q

27、R)P(QR)(P(PQ)(PQ)(PR)R) P(QR) P(QR)(P(PQ)Q)(P(PR)R)416.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) (

28、P (P(Q(QR) R) P PQ QR R 42思考1o思考思考:对联结词是否还可以归约对联结词是否还可以归约,即五种联结词即五种联结词是否都是必要的是否都是必要的?o如果能归约如果能归约,能归约到什么程度能归约到什么程度?43恒等式的判别：真值表方法和命题演算方法恒等式的判别：真值表方法和命题演算方法例例1 1 用真值表方法证明用真值表方法证明 E E1010： (P(P Q) Q) P PQ Q PQ00011110 (P Q)1000 PQ 10001111 (P Q) PQ44例例2 2 用真值表方法证明用真值表方法证明E E1111：P PQ QP P Q Q解：解： 构造构造P

29、 PQ Q P P Q Q的真值表如下：的真值表如下：PQPQ P Q00111011111000111111PQ P Q45PQ PQ是否成立？是否成立？由由于于公公式式PQ和和P Q所所标标记记的的列列不不完完全全相相同同所所以以，因因此此PQ PQ不成立。不成立。PQ P Q PQPQ00111101100101101011001146( (1) 1) 代入规则代入规则 重言式的任何重言式的任何代入实例代入实例仍是重言式。仍是重言式。2 2命题演算方法命题演算方法例：例： （P PQ Q） （ Q QP P）是重言式，是重言式，用公式用公式 AB AB 代换其中的命题变元代换其中的命题变

30、元P P得到的新公式得到的新公式 （ABAB）Q Q）（ Q Q（ABAB）仍是重言式。）仍是重言式。注意：注意： 因为因为A A B B 当且仅当当且仅当 A A B B是重言式。所是重言式。所以，对于基本恒等式中的任一命题变元出现的每一处均用以，对于基本恒等式中的任一命题变元出现的每一处均用同一命题公式代入，所得到的仍是恒等式。同一命题公式代入，所得到的仍是恒等式。47说明：说明：基本恒等式表中，基本恒等式表中，P,Q,RP,Q,R可以表示任意命题公式。利用可以表示任意命题公式。利用代入定理，由这些恒等式可以得到无穷多个恒等式。代入定理，由这些恒等式可以得到无穷多个恒等式。例如：由例如：由

31、 PP P P1 1 可知：可知：(PQ)(PQ) (PQ)(PQ)1 1 ( ( P) P) ( ( P)P)1 1.48 (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

32、 CD D。如果将公。如果将公式式A A中的子公式中的子公式C C置换成公式置换成公式D D之后，得到的公式是之后，得到的公式是B B，则，则A AB B。 49(3) (3) 等值演算等值演算 等值演算是指利用已知的一些恒等式，根据置换等值演算是指利用已知的一些恒等式，根据置换规则、代入规则推导出另外一些恒等式的过程。规则、代入规则推导出另外一些恒等式的过程。 由代入规则知前述的基本等值（恒等）式不仅对任由代入规则知前述的基本等值（恒等）式不仅对任意的命题变元意的命题变元P P，Q Q，R R是成立的，而且当是成立的，而且当P P，Q Q，R R分别为分别为命题公式时，这些等值式仍然成立命题

33、公式时，这些等值式仍然成立 例例2 2 证明：证明：（PQ）（RQ）（PR）Q证明证明（PQ）（RQ）（ PQ）( RQ)E11（ P R）QE3(分配律分配律) (PR)QE10(德德.摩根律摩根律)(PR)QE1150例例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(交换律，吸收律交换律，吸收律)51例例4 4 判别下列公

34、式的类型。判别下列公式的类型。（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） PF所以所以Q ( P( PQ)是矛盾式。是矛盾式。52（2） （PQ） P （ PQ） P P 吸收律吸收律 该公式是可满足式。该公式是可满足式。 53例例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） （补余

35、律）（补余律）P P（P P Q Q） （同一律）同一律）P P （ P PQ Q） （De MorganDe Morgan律）律）（P PP P）Q Q （结合律）结合律）1 1Q Q （补余律）补余律）T T （零律）（零律） 54命题公式逻辑恒等的应用：命题公式逻辑恒等的应用： 1、判定两个命题公式是否逻辑等值；、判定两个命题公式是否逻辑等值； 2、判断是否为重言式或矛盾式；、判断是否为重言式或矛盾式； 3、对命题公式进行化简、对命题公式进行化简55逻辑等值应用实例逻辑等值应用实例将下面用高级语言写成的一段程序化简：将下面用高级语言写成的一段程序化简： ifAthenifBthenXel

36、seYelseifBthenXelseYATFTFFA 56此段程序执行此段程序执行X X的条件为的条件为： ABAB执行执行Y Y的条件为的条件为： ABAB它们分别可化简为：它们分别可化简为：ABAB(AA)B (由分配律由分配律)TBB而而ABAB也可化简也可化简ABABB所以上述语句可化简成：所以上述语句可化简成：ifBthenXelseY57永真蕴含式永真蕴含式 定义定义 如果如果 A AB B 是永真式，则称其为永真蕴是永真式，则称其为永真蕴含式含式, ,记作记作A AB, B, 即即A AB BT T，则称公式，则称公式A A永真蕴含永真蕴含公式公式B B。注意：注意： 符号符号

37、“”和和 “ “”的区别的区别58基本的永真蕴含式基本的永真蕴含式 P10P10注意：这些基本的永真蕴含式将作为以后注意：这些基本的永真蕴含式将作为以后我们利用命题逻辑进行逻辑推理的基础！我们利用命题逻辑进行逻辑推理的基础！59永真蕴含式的判别方法永真蕴含式的判别方法判定判定“AB”是否成立的问题可转化为判定是否成立的问题可转化为判定AB是否为重言式，有下述判定方法：是否为重言式，有下述判定方法：1.真值表法；真值表法；2.假定前件假定前件A为真，看结论是否一定为真为真，看结论是否一定为真3.假定后件假定后件B为假，看前件是否一定为假为假，看前件是否一定为假1.真值表法真值表法例例证明证明：（

38、：（PQ）（PR）（QR） R602.假定前件为真假定前件为真 假定前件为真，检查在此情况下，其结论是否也为真。假定前件为真，检查在此情况下，其结论是否也为真。例例证明证明: Q（PQ） P证明证明:令前件令前件 Q（PQ）为真，为真，则则 Q为真为真,且且PQ为真。为真。于是于是Q为假，因而为假，因而P也为假。因此也为假。因此 P为真为真。故上面蕴含式故上面蕴含式成立。成立。613、假定结论为假假定结论为假 假定结论为假，检查在此情况下，其前件是否也为假假定结论为假，检查在此情况下，其前件是否也为假. .例例证明蕴含式证明蕴含式(PQ) (RS)(P R)(Q S)证证明明令令结结论论(P

39、R)(Q S)为为假假，则则P R为为真真，Q S为为假假,于是于是P、R均为真，而均为真，而Q和和S至少一个为假。至少一个为假。由此可知由此可知PQ与与RS中至少一个为假中至少一个为假,因此因此(PQ) (RS)为假为假.故上述蕴含式成立。故上述蕴含式成立。62对偶式及对偶原理对偶式及对偶原理 定义定义 设设A A是一个仅含有联结词是一个仅含有联结词 、和和的命题公式，将公式的命题公式，将公式A中用中用代替代替、用、用代替代替、用、用T代替代替F、用、用F代替代替T，所得的命题公式称为所得的命题公式称为A的对偶式，记为的对偶式，记为A*。例如例如：PQR和和（PQ）R互为对偶式互为对偶式 P

40、QR的对偶式是的对偶式是( PQ)R63定理：定理： 设设A A是一个仅含有联结词是一个仅含有联结词 、和和的的命题公式，命题公式，P1，P2.Pn是出现于其中的全部命是出现于其中的全部命题变元，则题变元，则 A(P1，P2.Pn)A*( P1， P2. Pn)A( P1， P2. Pn) A*(P1，P2.Pn)64对偶原理对偶原理对偶原理对偶原理: 设设A和和B是两个仅含有联结词是两个仅含有联结词 、 和和的命的命题公式，如果题公式，如果A B， 则则A* B*。 利用对偶原理可知：利用对偶原理可知： （1 1）若）若A A为重言式（永真式），则为重言式（永真式），则A A* *为矛盾式。

41、为矛盾式。 （2 2）由一些等值式）由一些等值式, ,利用对偶原理则可得到另一些等值式。利用对偶原理则可得到另一些等值式。 如：如： P(QR)P(QR)(P(PQ)(PQ)(PR) R) 则立即可知则立即可知: : P P(Q(QR)R) (P (PQ)Q)(P(PR) R) 65可满足性的应用可满足性的应用o在不同领域：如机器人学，软件测试，计算机辅助设计、机器视觉、集成电路设计、计算机网络以及遗传学中的许多问题都可以用命题可满足性来建立模型。o例如:数独谜题（要求每一行，每一列、每个小九宫格都每包含九个不同的数字）66数独数独谜题的求解的求解(命命题逻辑法法)o用命题逻辑描述即为:p（i

42、,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=967可满足性问题求解可满足性问题求解 可满足性问题求解: 真值表可以判定复合命题是否为可满足的,或者等价地,判断其否定是否为永真式）。当含少量命题变元时，可以手动来完成，但当命题变元很多时，就不切实际了。例如，当有20个命题变元时，真值表就有220行，显然需要计算机来判断是否是可满足式。 当许多应用建模涉及成千上万个变量的复合命题的可满足性时，如当变量为

43、1000时,要检查21000种可能的真值组合中的每一种,一台计算机在几万亿年之内都不可能完成!（即这是一个NP难的问题!-算法课中讲解算法复杂性问题） 但是，在实际应用中，某些特定类型的复合命题的可满足性问题求解方法还是有一些进展，如数独谜题的求解。681.判断下列等值式是否成立判断下列等值式是否成立（1）（）（PQ）（RQ）（PR）Q（2） （PQ）（P Q）（ PQ）2判定下列蕴含式是否成立判定下列蕴含式是否成立P(QR)(PQ)(PR）练习练习69解解（1）（）（PQ）（RQ）（ PQ）（ RQ）（ P R）Q（PR）Q（2） （PQ） (（PQ）（QP）) (（ PQ）（ QP）)（P

44、 Q）（ PQ）（PR）Q702 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）为假。为假。因此蕴含式成立。因此蕴含式成立。71o讨论讨论: 判断下面命题是否成立判断下面命题是否成立? (1)若A B,则则 A B(2)若A B,则则 A B72注意:理解理解基本恒等式和基本永真蕴含式记忆

45、记忆应用应用它们是我们以后利用命题逻辑进行推理的基础.73基本的逻辑恒等式（基本的逻辑恒等式（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)746.6.De MorganDe Morgan律律： （PQPQ） PP

46、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 75最常用的推理规则(常用的永真蕴含式)1.1.附加：附加：P P (P(P Q)Q)， Q Q (P(P Q)Q)2.2.化简：

47、化简：(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 S761.4 1.4 范式范式命题公式千变万化，这对研究其性质和应用研究带来很大的困难。为此，我们有必要研究如何将命题公式转化为其逻辑等价的标准形式标准

48、形式的问题，以简化研究工作并方便应用。这种标准形式称为范式。1.合取范式与析取范式2.主合取范式和主析取范式77范式范式( (主析取范式和主合取范式主析取范式和主合取范式) ) （一）极小项、极大项（一）极小项、极大项 定义定义 设有命题变元设有命题变元P P1 1，P P2 2，,P Pn n ，形形如如P P1 1*P*P2 2*P*P3 3*P Pn n* * 的的命题公式称为是由命题变元命题公式称为是由命题变元P P 1 1，P P2 2，P Pn n所产生的极小项。而形所产生的极小项。而形如如 P P1 1*P*P2 2*P*P3 3*P Pn n* * 的命题公式称为是由命题变元的

49、命题公式称为是由命题变元P P1 1，P P2 2，P Pn n所产生所产生的极大项。其中的极大项。其中P Pi i* *为为P Pi i或为或为 P Pi i(i=1,2,n).(i=1,2,n). 例如例如, P, P1 1PP2 2PP3 3， P P1 1PP2 2 P P3 ,3 , P P1 1 P P2 2PP3 ,. 3 ,. 即每个变元在析取式（合取式）中出现一次且只出现一次，出现的形式是变即每个变元在析取式（合取式）中出现一次且只出现一次，出现的形式是变元或变元的否定则这样的析取式（合取式）称为关于这些变元的极大项元或变元的否定则这样的析取式（合取式）称为关于这些变元的极大

50、项（极小项）（极小项）78 常用常用m mk k(0k2(0k2n n-1)-1)表示极小项表示极小项 P1*P2*P3*Pn* ，其，其中中k k为二进制为二进制t t1 1t t2 2.t tn n对应的十进制。且若对应的十进制。且若Pi*为为 P Pi,t ti i=0.=0.否则为否则为1 1。 例如，三个命题变元例如，三个命题变元P,Q,RP,Q,R共共形成八个极小项形成八个极小项 m m0 0= = PP QQ R R， m m1 1= = PP QR QR ， m m2 2= = PQPQ R R m m3 3= = PQRPQR， m m4 4= P= P QQ R R， m

51、m5 5= P= P QRQR m m6 6= PQ= PQ R R， m m7 7=PQR=PQR极小项：极小项：79极大项：极大项： 常用常用M Mk k(0k2(0k2n n-1)-1)表示表示极极大大项项 P1*P2*P3*Pn* ，其中其中k k为二进制为二进制t t1 1t t2 2.t tn n对应的十进制。且若对应的十进制。且若Pi*为为 P Pi,t ti i=1.=1.否则为否则为0 0。 例如，三个命题变元例如，三个命题变元P,Q,R共形成八个极大项共形成八个极大项 M M0 0= P= P Q Q R R， M M1 1= P = P Q Q R R ， M M2 2=

52、 P = P Q Q R R M M3 3=P=PQ Q R R， M M4 4= = P P Q Q R R， M M5 5= = P P Q Q R R M M6 6= = P PQ Q R R， M M7 7= = P PQ QR R80例：含有例：含有3个命题变元个命题变元P,Q,R的全部极大项和极小项如下所示的全部极大项和极小项如下所示极小项极小项 极大项极大项 PQR -0 0 0 PQR -0 0 0PQR -0 0 0 PQR -0 0 0 PQR -0 0 1 PQR -0 0 1 PQR -0 0 1 PQR -0 0 1 PQR -0 1 0 PQR - 0 1 0 PQ

53、R -0 1 0 PQR - 0 1 0 PQR -0 1 1 PQR - 0 1 1 PQR -0 1 1 PQR - 0 1 1 PQR - -1 0 0 PQR -1 0 0 PQR - -1 0 0 PQR -1 0 0 PQR _ _ _1 0 1 PQR -1 0 1 PQR _ _ _1 0 1 PQR -1 0 1 PQR - - -1 1 0 PQR - 1 1 0 PQR - - -1 1 0 PQR - 1 1 0 PQR - -1 1 1 PQR 1 1 1 PQR - -1 1 1 PQR 1 1 1容易看出，容易看出，对于每个极小于每个极小项( (极大极大项) )只

54、存在一种解只存在一种解释使其使其值为真真（假）（假）( (即右即右边的的编号）号）81极小项的性质：极小项的性质：1 1）每一个极小项）每一个极小项m mk k在与其下标相对应的指派下其值为真，而在与其下标相对应的指派下其值为真，而在其余在其余2 2n n-1-1种指派下其值为假。种指派下其值为假。2 2）任意两个不同的极小项的合取式是一个矛盾式）任意两个不同的极小项的合取式是一个矛盾式 ( (请证明请证明) )3 3）全部（）全部（2 2n n个个）极小项的析取式是一个重言式极小项的析取式是一个重言式思考：在任何同一解释下，为什么极小项思考：在任何同一解释下，为什么极小项mi和和mj不能同时

55、不能同时为真？即为什么为真？即为什么mimj是永假式？（是永假式？（ij)82极大项的性质：极大项的性质：1 1）每一个极大项）每一个极大项M Mk k在与其下标相对应的指派下值为假在与其下标相对应的指派下值为假 ，而在，而在其余其余2 2n n-1-1种指派下值为真。种指派下值为真。2 2）任意两个不同的极大项的析取式是一个重言式）任意两个不同的极大项的析取式是一个重言式3 3）全部）全部2 2n n个极大项的合取式是一个矛盾式个极大项的合取式是一个矛盾式思考：在任何同一解释下，为什么极大项思考：在任何同一解释下，为什么极大项i和和j不能同不能同时为假？即为什么时为假？即为什么ij是永真式？

56、（是永真式？（ij)83定义定义：由极小项所组成的析取式，称为主析取范式由极小项所组成的析取式，称为主析取范式。例如：例如：( ( P P1 1P P2 2 P P3 3) ) ( ( P P1 1 P P2 2 P P3 3) ) (P(P1 1 P P2 2 P P3 3) )是一个主析取范式是一个主析取范式。 定义定义:若一个主析取范式与公式若一个主析取范式与公式A等价等价,则称之为则称之为A的主析取范式。的主析取范式。主析取范式主析取范式84 定义：定义：由极大项所组成的合取式，称为主合取范式由极大项所组成的合取式，称为主合取范式 (P(P1 1P P2 2 P P3 3) ) (P(

57、P1 1 P P2 2 P P3 3) ) ( ( P P1 1P P2 2P P3 3) ) ( ( P P1 1 P P2 2P P3 3) ) 是一个主合取范式。是一个主合取范式。定义定义:若一个主合取范式与公式若一个主合取范式与公式A等价等价,则称之为则称之为A的主合的主合取范式。取范式。主合取范式主合取范式85五、求公式的主析取范式和主合取范式的方法五、求公式的主析取范式和主合取范式的方法(一）真值表法一）真值表法(二）公式演算法二）公式演算法86用真值表法求范式用真值表法求范式(一个公式的真值表确定了一个公式的真值表确定了,则公式的则公式的标准形式即范式就可确定标准形式即范式就可确

58、定)- - -极小项极小项 PQR PQR 极大项极大项 PQRPQR-极小项极小项 PQRPQR-极小项极小项 PQRPQR极大项极大项 PQRPQR-极小项极小项 PQRPQR极大项极大项 PQR PQR 极大项极大项 PQRPQRPQRA0 0 00 0 00 0 10 0 10 1 00 1 00 1 10 1 11 0 01 0 01 0 11 0 11 1 01 1 01 1 11 1 1 1 1 0 01 11 10 01 10 00 087所以所以A A的主析取范式为的主析取范式为 ：(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)A A的主合取

59、范式为：的主合取范式为：(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)用真值表方法求主范式比较简单，但当变元数目较多用真值表方法求主范式比较简单，但当变元数目较多时，列真值表就太麻烦。时，列真值表就太麻烦。注注: : 只要知道一命题公式只要知道一命题公式G G的主析的主析( (合取合取) )取范式，就取范式，就可立即写出可立即写出G G的真值表的真值表, ,反之，若已知反之，若已知G G的真值表，的真值表，则表中所有使则表中所有使G G为真的解释所对应的极小项为真的解释所对应的极小项( (极大项极大项) )的析取的析取( (合取合取) )，便是，便是G G的主

60、析取范式的主析取范式.(.(主合取范式主合取范式) ) 88求求 ( P Q) (P R )的主的主(合合)析取范式析取范式( P Q) (P R)(析取范式析取范式)( P Q R) ( P Q R) (P Q R) (P Q R)m2 m3 m5 m7(P Q R) (P Q R) ( P Q R) ( P Q R)M0 M1 M4 M689定理定理每一个不为永假的命题公式每一个不为永假的命题公式G(PG(P1 1, P, P2 2, , , , P Pn n）必与一个由必与一个由 P P1 1，P P2 2，P Pn n 所产生的主析取范式等价。所产生的主析取范式等价。 永真公式的主析取

61、范式包含所有永真公式的主析取范式包含所有2 2n n个极小项。个极小项。 永假公式的主析取范式不存在永假公式的主析取范式不存在. .定理：定理：每一个不为永真的公式每一个不为永真的公式G(PG(P1 1, P, P2 2, , , , P Pn n） 必有一个由必有一个由 P P1 1, P, P2 2, , , , P Pn n所产生的主合取范式等价。所产生的主合取范式等价。永假公式的主合取范式包含所有永假公式的主合取范式包含所有 2 2n n个极大项个极大项。永真公式不存在主合取范式。永真公式不存在主合取范式。 90(二）二）公式演算法公式演算法求主合取范式步骤如下：求主合取范式步骤如下：

62、1)消去公式消去公式A中中的的和和，得，得A1;2)利用德。摩尔根律将利用德。摩尔根律将A1中的中的内移到原子之前，并内移到原子之前，并利用双重否定律使每个原子之前最多只有一个利用双重否定律使每个原子之前最多只有一个,得得A2;3)利用分配律将利用分配律将A2的结果化为若干个析取式的合取，的结果化为若干个析取式的合取，其中每个析取式的因子皆为原子或原子的否定其中每个析取式的因子皆为原子或原子的否定,A3;4)对于对于A3的结果中的每个析取式的结果中的每个析取式B，若命题变元，若命题变元P在在B中不出现，则用中不出现，则用(BP)(BP)取代取代B，直到每个，直到每个B都变为极大项为止。都变为极

63、大项为止。91例例1 1 求合式公式求合式公式 P(PQ)(QP)P(PQ)(QP)的主范式。的主范式。主合取范式：主合取范式： P(PQ)(Q P)P(PQ)(Q P) P(P Q)(Q P) P(P Q)(Q P) P P(P Q)(QP) (P Q)(QP) (双重否定律双重否定律) ) (P(PPQ) (P(QP) PQ) (P(QP) 由分配律由分配律 (PQ)(PQ)(PP) (PQ)(PQ)(PP) 由分配律由分配律 (PQ)(PQ)主析取范式：主析取范式：P(PQ)(Q P)P(PQ)(Q P) (P(PQ)Q) (P(QQ) (PP)Q)(P(QQ) (PP)Q) (PQ)(

64、PQ) (PQ)(PQ)(PQ)(PQ) (PQ)(PQ) (PQ)(PQ) (PQ) (PQ)(PQ) (PQ) 92例例2:2:求合式公式（求合式公式（P P(Q(QR)R)）(P(QR)(P(QR)的主合取范式的主合取范式和主析取范式和主析取范式（P P(Q(QR)R)）(P(QR)(P(QR)( (P P (Q (QR)R)(P(P (QR)(QR) (P (P Q) Q) （P P R R）（P P QQ）（P P RR）(P(P Q Q R R) )（P P Q Q RR）（P P QQ R R）（P P Q Q R R）（P P QQ R R）（P P Q Q RR）即即主主合合

65、取取范范式式为为：(P(P Q Q R R) ) （P P Q Q RR）（P P QQ R R）（P P Q Q R R）（P P QQ R R）（P P Q Q RR）主析取范式为：（主析取范式为：（PQRPQR） （PQRPQR）93主主析取范式与主合取范式之关系析取范式与主合取范式之关系 由于主合取范式与主析取范式在形式上对偶，所以可以由于主合取范式与主析取范式在形式上对偶，所以可以通过主析取范式来求得对应的主合取范式。反之亦然。通过主析取范式来求得对应的主合取范式。反之亦然。注注: : m mi i与与M Mi i： m mi iM Mi i， M Mi im mi i 例：例：M

66、M3 3= P= PQ QR R, ,( (被解释被解释(0,1,1)(0,1,1)弄假弄假) )，则，则 M M3 3= = P P Q Q R=mR=m3 3 ( (被解释被解释(0,1,1)(0,1,1)满足满足）设含设含n n个命题变元的公式个命题变元的公式G G的主析取范式为：的主析取范式为： G G m mi1i1 m miKiK （含（含k k个极小项）个极小项） 因为因为G GG GT T，即对，即对2 2n n个解释全为真个解释全为真。所以所以 G Gm mj1j1 m mj2j2 m mj2j2n n-K -K (2(2n n-k-k个极小项个极小项) )94o于是于是:

67、G: G( ( G)G) （m mj1j1 m mj2j2 m mj2j2n-kn-k） m mj1j1m mj2 j2 m mj2j2n-kn-k) ) M Mj1j1 M Mj2 j2 M Mj2j2n-kn-ko例：公式例：公式: P: P Q Q 其主析取范式为其主析取范式为 P P Q Qm m3 3 其主合取范式为其主合取范式为 P P Q Q (P(P Q)Q) (P(PQ)Q) ( ( P P Q)Q) M M0 0 M M1 1 M M2 2o如果我们求得了主析取范式，就可相应的求得主合如果我们求得了主析取范式，就可相应的求得主合取范式取范式( (编号互补编号互补) )。反之

68、。反之, ,也成立。也成立。95练习：练习：求公式求公式 （ PQ）（PQ）的主析取范式）的主析取范式及主合取范式及主合取范式。96解：解： 求主析取范式求主析取范式 （ P PQ Q）（P PQ Q） （ P PQ Q）（ P PQ Q） （P P Q Q） （ P PQ Q） （ P PQ Q） （P P Q Q） （P P Q Q） （ P PQ Q） （P P Q Q） （P P Q Q） （ P PQ Q） P P） （( ( P PQ Q） Q Q） （P P Q Q） （ P P P P） （ Q Q P P） （ P P Q Q） （ Q Q Q Q） （ P P Q Q） （

69、P PQ Q ） （P P Q Q） m m1 1 m m2 2 m m3 3 97o （ P PQ Q）（P PQ Q） （ P PQ Q）（ P PQ Q） （P P Q Q） （ P PQ Q） （ P PQ Q） （P P Q Q） （P P Q Q） （ P PQ Q） （P P Q Q） （P P （ P PQ Q） （P P Q Q） （Q Q （ P PQ Q） （P P Q Q） （P PP PQ Q） （P P P P Q Q） （Q Q P PQ Q） （Q Q P P Q Q） （P P Q Q） M M0 0求主合取范式98总结总结: :令令A A（a1a1、a2a2

70、、anan）包含有包含有n n个变量的公式，则有：个变量的公式，则有：1、如果如果A A存在与之等值的主析取范式，则必唯一；存在与之等值的主析取范式，则必唯一；2 2、如果、如果A A存在与之等值的主合取范式，则必唯一；存在与之等值的主合取范式，则必唯一；3 3、A A是永真公式当且仅当与是永真公式当且仅当与A A等值的主析取范式恰有等值的主析取范式恰有2 2n n个极小个极小项或没有主合取范式；项或没有主合取范式；4 4、A A是永假公式当且仅当与是永假公式当且仅当与A A等值的主合取范式恰有等值的主合取范式恰有2 2n n个极大个极大项或没有主析取范式；项或没有主析取范式；5 5、两个命题

71、公式等值当且仅当它们有相同的主合取范式或相、两个命题公式等值当且仅当它们有相同的主合取范式或相同的主析取范式。同的主析取范式。99思考1o设计一个简单的表决器设计一个简单的表决器, ,表决者每人座位旁有一表决者每人座位旁有一按钮按钮, ,若同意则按下按钮若同意则按下按钮, ,否则不铵按钮否则不铵按钮, ,当表决当表决结果超过半数时结果超过半数时, ,会场电铃会响会场电铃会响, ,否则不会响否则不会响. .试试以表决人数为以表决人数为3 3人的情况设计表决器的逻辑关系人的情况设计表决器的逻辑关系. .100思思考考22 张张先先生生手手中中有有代代号号为为A、B、C、D、E的的五五种种股股票票，

72、根根据据当当前前股股市市情情况况及及张张先先生生本本人人的的经经济济需需求求，需需要要有有若若干干个个股股票票抛抛出出，但但又必须满足如下复杂的要求：又必须满足如下复杂的要求：（1）若）若A抛出，则抛出，则B也抛出；也抛出；（2）B和和C要留一种股票且只能留一种；要留一种股票且只能留一种；（3）C和和D要么全抛，要么都不抛；要么全抛，要么都不抛；（4）D和和E两种股票中必然有一种或两种要抛出；两种股票中必然有一种或两种要抛出；（5）若）若E抛出，则抛出，则A、B也抛出。也抛出。上上述述五五种种条条件件全全部部满满足足，问问有有几几种种合合理理的的方方案案供供张张先先生生选择。选择。101解解:

73、 :为简化为简化 , ,用用A,B,C,D,EA,B,C,D,E表示如下命题表示如下命题: : A:A:抛出；抛出；: :抛出；抛出；: :抛出；抛出； : :抛出；抛出； E:E:抛出抛出则上述规则分别可表示为则上述规则分别可表示为: :(1) AB(2)B C(3)CD(4)DE(5)E(AB)即只需求出使上述即只需求出使上述5 5个公式都为真的解释即可个公式都为真的解释即可. . 或者求出公式或者求出公式:(AB)(B C)(CD)(DE)(E(AB)的主析取范式的主析取范式为了减少变元个数，直接利用和等值，为了减少变元个数，直接利用和等值，公式变为：公式变为：(AB)(B C)(E)(

74、E(AB)方案：只抛和方案：只抛和方案：抛出，和方案：抛出，和1025 推理理论（推理规则和证明方法）推理理论（推理规则和证明方法） 推理是由已知的命题得到新命题的思维过程。推理是由已知的命题得到新命题的思维过程。 数学中的证明是建立数学命题真实性的有效论证。数学中的证明是建立数学命题真实性的有效论证。 本节主要掌握本节主要掌握: : 1. 1. 一些推理规则一些推理规则; ; 2. 2. 应用推理规则进行推理的方法应用推理规则进行推理的方法; ; 3. 3. 对正确的论证进行形式化的证明。对正确的论证进行形式化的证明。103例例1 如果x是偶数，则x2是偶数PQx是偶数Px2是偶数Q 例例2

75、 如果x是偶数，则x2是偶数PQx2是偶数Qx是偶数P 104例例3 如果x是偶数，则x2是偶数PQx不是偶数Px2不是偶数Q例例4如果x是偶数，则x2是偶数PQx2不是偶数Qx不是偶数P105o依据数学知识，例和例的推理是正确的由此可知，有研究推理的必要推理规则是正确推理的依据，推理规则是正确推理的依据，而正确推理对任何一门科学都是非常重要的o对任一蕴含式: A B 来说,如果前提A为真,则可保证B为真,因此,任何一个蕴含式都可作为一条推理规则任何一个蕴含式都可作为一条推理规则. 106推理规则推理规则定义：定义： 若H1H2HnC，则称C C是H1，H2，,Hn的有效结论。称从 H1H2H

76、n推出C。这样的推理是正确的！ 注：推理正确不等于结论为真推理正确不等于结论为真! 结论为真，还取决于前提H1H2Hn的真假，如果前提为真，则结论C为真，前提为假时，C可能为真，也可能为假。1071.1.如何判断由一个前提集合能否能推出某个结论如何判断由一个前提集合能否能推出某个结论? ?（即判定前提和结论之间的蕴含关系是否成立）（即判定前提和结论之间的蕴含关系是否成立）2.2.方法如下方法如下: :（1 1）真值表法）真值表法（2 2）命题演算法）命题演算法（3 3）形式证明法）形式证明法 108最常用的推理规则1.1.附加：附加：P P (P(P Q)Q)， Q Q (P(P Q)Q)2.

77、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 S109对有效论证的形式化证明（使用推理规则建对有效论证的形式化证明（使用推理规则建立论证立论证)只列出前提和结论叫论证，但它未必是有效的只列

78、出前提和结论叫论证，但它未必是有效的!证明是有效论证的证明是有效论证的展开展开，它由一系列公式组成，它们或，它由一系列公式组成，它们或者是前提，或者是公理，或者是前面列出的公式的结论，者是前提，或者是公理，或者是前面列出的公式的结论，这些结论都必须根据这些结论都必须根据推理规则推理规则得出得出1 1. 永真蕴含式都可作为推理规则。 2 2. AB 相当于 AB 且BA，所以恒等式也是推理规则。3 3. P规则：在推导的任何步骤上都可以引入前提。4 4. T规则：在推导中，如果前面有一个或多个公式蕴含S，则可把S引入推导过程。110例：证明下述论证：例：证明下述论证： 如果这里有球赛，则通行是困

79、难的。如果这里有球赛，则通行是困难的。 如果他们按时到达，则通行是不困难的。如果他们按时到达，则通行是不困难的。 他们按时到达了。他们按时到达了。 所以这里没有球赛。所以这里没有球赛。 设设P P：这里有球赛这里有球赛，Q Q：通行是困难的。通行是困难的。R R：他们按时到达。他们按时到达。 则上述论证能表达如下：则上述论证能表达如下： PQ PQ RQ RQ R R P P证明证明请请看看后后面面的的证证明明，凡凡是是能能构构造造形形化化式式证证明明的的，都都是是有有效效的的论论证证，不不能能构造证明的论证，则不是有效的。构造证明的论证，则不是有效的。111证明：证明： （为了清楚，在左边加

80、上数字） 1 R (P1 R (P规则，前提规则，前提3)3) 2 RQ (P 2 RQ (P规则，前提规则，前提2)2) 3 Q (T 3 Q (T规则，由规则，由1,2 1,2 据据I3)I3) 4 PQ (P 4 PQ (P规则，前提规则，前提1)1) 5 QP (T 5 QP (T 规则，由规则，由4 4，据，据E24)E24) 6 P (T 6 P (T规则，由规则，由3,5 3,5 据据I3)I3) 形式化证明形式化证明：由一系列公式组成，它们或者是前提，或者公理，或者是前面公式的结论，但这些结论必需根据推理规则得出。 112论证的一般形式：定理定理的常见形式：的常见形式：“P P

81、当且仅当当且仅当Q”Q” “如果如果P,P,则则Q” Q” 前者相当于：前者相当于：P PQ Q而且而且Q QP P的形式，后者相当于：的形式，后者相当于：P PQ Q。定理出现的主要形式：定理出现的主要形式：（）（） P PQ Q（）（） P P：只需证明：只需证明P P是假，是假，（）（）PQPQ：只需证明只需证明：P P和和Q Q都真，都真，（）（）P QP Q： 转为转为P P Q Q形式。形式。 我们主要研究我们主要研究: P: PQ Q形式的证明方法。形式的证明方法。 1131*. 1*. 直接证明法：假设直接证明法：假设P P是真，若能推得是真，若能推得Q Q是真，是真， 则则P

82、 PQ Q是真。是真。2*. 2*. 逆反证明法：逆反证明法：将将P PQ Q 形式转化为直接证明形式转化为直接证明Q Q P P 。3*.3*.（P P1 1 P P2 2 P Pn n) ) Q Q 形式命题的证明：形式命题的证明： 转化为：转化为： Q Q ( (PP1 1PP2 2P Pn n),), 假设假设Q Q为假，只要能推出某一个为假，只要能推出某一个P Pi i为假，则命题就成立。为假，则命题就成立。证明方法证明方法：1144*. P4*. P1 1 P P2 2 P Pn n( (P PQ Q）形式的证明：）形式的证明：转化为证明：转化为证明： P P1 1 P P2 2

83、P Pn n P PQ 即把即把P P移作前提，这个方法叫移作前提，这个方法叫CPCP规则。规则。1155*.5*.反证法反证法( (归谬法）归谬法） 设命题公式设命题公式H H1 1 H Hm m是相容的是相容的. .于是于是, (H, (H1 1 H Hm m ) )G G 当且仅当且仅当当H H1 1,H Hm m, , G G是不相容的是不相容的. . 证明证明: :因为因为 (H(H1 1 H Hm m ) )G G (H(H1 1 H Hm m ) ) G G (H(H1 1 H Hm mG G) ) 所以所以, (H, (H1 1 H Hm m ) )G G当且仅当当且仅当 (H

84、(H1 1 H Hm mG)G)P PP P当且仅当当且仅当H H1 1, , ,H Hm m, , G G不相容不相容. .故定理成立故定理成立. .注注: :此种将此种将 G G作为附加前提作为附加前提, ,进而推出矛盾的证明称为归缪法。进而推出矛盾的证明称为归缪法。数学中的反证法属此类方法数学中的反证法属此类方法116如果需证：如果需证：H H1 1 H H2 2 H Hn nC C, ,可以转化为证明：可以转化为证明： H H1 1 H H2 2 H Hn n C C F F ( (矛盾式矛盾式) ) 即可。即可。（前提为真，如果假设结论（前提为真，如果假设结论 C C为假，则蕴含矛盾

85、，由此可为假，则蕴含矛盾，由此可知假设结论为假不成立，即结论一定为真）知假设结论为假不成立，即结论一定为真）117反证法举例反证法举例证明：证明： ( (P Q Q）是）是P Q Q的的有效结论有效结论. .（将（将( (P Q)Q)作为假设前提）作为假设前提）1 1( (PQ)Q) P ，（假设前提）2 PQ TQ T，1 1，3 3 P TP T，2 2，4 4P Q Q P P 5 5P T，4，6PP TP T，3 3，5 5，合取，合取118例例: :用归谬法用归谬法, ,构造推理的证明构造推理的证明前提前提:P:P( ( (R(R S)S) Q Q),P,),P, S S 结论结论

86、: : Q Q证明证明: :1.1.P P( ( (R(R S)S) Q Q) ) 前提引入前提引入 2.2.P P 前提引入前提引入3.3. (R(R S)S)Q Q 假言推理假言推理, ,根据根据(1)(1)，(2) (2) 4.4. ( ( Q)Q) 否定结论作附加前提引入否定结论作附加前提引入5.5.Q Q 双重否定，根据双重否定，根据(4)(4)6.6.R R S S 拒取式拒取式, ,根据根据(3)(3)，(5)(5)7.7. S S 前提引入前提引入8.8.S S 化简，根据化简，根据(6)(6)9.9.S SS S 合取，根据合取，根据(7)(7)，(8)(8)由(9)得出矛盾

87、,根据归谬法可知推理正确.119命题逻辑小结命题逻辑小结 1 1. 掌握五种逻辑联结词（逻辑运算符）的逻辑含义，会掌握五种逻辑联结词（逻辑运算符）的逻辑含义，会将命题符号化。将命题符号化。 2. 2. 掌握基本的恒等式，基本的永真蕴含式，从逻辑角度去掌握基本的恒等式，基本的永真蕴含式，从逻辑角度去理解它们。理解它们。3. 3. 知道代入规则（对永真式）和替换规则，会对公式进行知道代入规则（对永真式）和替换规则，会对公式进行 ( (命题演算命题演算) )4. 4. 会求公式的范式与主范式。会求公式的范式与主范式。5. 5. 掌握一些常用的证明方法。会构造有效论证的形式化证掌握一些常用的证明方法。

88、会构造有效论证的形式化证明，以训练思维的严密性和逻辑性。明，以训练思维的严密性和逻辑性。120延伸阅读：时序逻辑o1996年图灵奖获得者以色列应用研究数学系教授阿米尔.伯努利提出时序逻辑。o时序逻辑是对普通命题逻辑的扩充，但这一扩充意义重大，它使得系统具有了处理随时间变化而改变其值的时态变元的能力。（引入时态算子（任一时刻，某一时刻，下一时刻，直到），以及相关的公理和推理规则）o时序逻辑成为研究并发程序尤其是持续不终止的反应式程序（如操作系统、网络通信协议等）的强有力的形式化工具，可充分表达程序的安全性、活性和事件的优先性等。成为程序规约、验证等的有力工具。o我国科学家中科院院士唐雅松在其基础上，将时态逻辑用于软件开发的整个过程，包括需求定义、规约、设计、证实、验证、代码生成和集成，并开发了世界上第一个可执行时态逻辑语言XYZ/E和一组相应的CASE工具，在国际上引起强烈反响。伯努力本人和唐也建立了联系，成为了朋友。121本章作业(命题逻辑部份)1.1:1,2,5,7,111.2:3,4,7,8,11,121.3:1,2,3(a,b)1.5:6，8，12122