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

数理逻辑:命题逻辑,2,逻辑,逻辑不仅对理解数学推理十分重要，而且在计算机科学中有许多应用。这些逻辑规则用于计算机电路设计、计算机程序构造、程序正确性证明等许多方面！,3,Copyright 2007 by Xu Dezhi,3,逻辑学,逻辑学=研究正确推理的科学推理：由一个或几个命题推出另外一个命题的思维形式。逻辑学的作用1、有助于准确、严密地表达和交流思想。2、有助于培养、提高认知能力，获得间接知识。3、有助于识别、驳斥谬误和诡辩，进行批判性思维。数理逻辑：用数学方法研究推理的一门学科一套符号体系+一组推理规则,4,Copyright 2007 by Xu Dezhi,4,逻辑学,逻辑学关注的是陈述（命题）之间的关系。例如:我的表是数字的.所有数字设备都依靠电池运行.因此，我的表依靠电池运行注意：逻辑学并不关心前面两个陈述（命题）的真假。但是，如果它们是真的，则推论也一定是真的。,5,命题：凡是具有确定真假意义的陈述句均称为命题。命题的值:若为“真”，用或表示；若为“假”，用或表示。由于一个命题的值只可能取“真”或“假”两种值，因此，命题逻辑也称为“二值逻辑”。延伸阅读:模糊逻辑,基本概念:命题与命题的值,6,下面三类陈述句是命题：1.现实可判断真假的陈述句。2.目前还不知道真假，但它们本身是具有真假意义的。3.其真假与讨论问题范围（论域）有关的陈述句（如：所有的人都爱跑步）。,下面的不是命题：感叹句，疑问句，祈使句,非命题陈述句：悖论语句(如:我正在说谎)。,7,例：地球绕着月亮转。1+1=3。禁止烟火！地球有一天会爆炸。明天会下雨吗？x5.如果明天天气晴朗，我就到湘江边散步。如果太阳从西边升起,我就可以长生不老。9)火星上有水。,8,简单命题(原子命题）它不能再分解成更简单的命题。在命题逻辑中，简单命题被看作是一个整体，不再分析其内部的逻辑形式。常用大写字母：P，Q，R，.表示简单命题。例如：P:4是质数，Q：所有人都爱学习,简单命题与复合命题,9,复合命题（命题的组合）,复合（杂）命题命题可以通过逻辑联接词构成新的命题，即复合命题。复合命题的子命题也可以是复合命题。例如：如果明天天气晴朗，我就到湘江边散步。如果太阳从西边升起,我就可以长生不老。,10,命题可以通过一些逻辑联结词构成新的命题（复合命题）1.否定词:定义：设是命题，复合命题“”是的否定，规定为真当且仅当为假。例：长沙的秋天景色很美。：Q:上海处处都清洁。Q：,五种常用的命题（逻辑）联接词,11,定义：设，是命题，复合命题“并且”称为和的合取,写成。为真当且仅当与同时为真。真值表如下：,2.合取词“”,12,定义：设，是命题，复合命题“或者”称为和的析取,记为。为真当且仅当与至少有一个为真。真值表如下：,3.析取词“”,13,定义：设，是命题，复合命题“如果，则”称为蕴涵,记为:。称为条件，为结论。规定为假当且仅当为真而为假。,4.蕴涵词“”,PQ“如果P,则Q”“P是Q的充分条件”“Q是P的必要条件”“Q每当P”,14,在日常生活中,蕴含式中条件与结论是有逻辑联系的，即有因果关系，称为即形式蕴含.在数理逻辑中,蕴含式中条件和结论不一定有因果关系，即实质蕴含。例：如果太阳从西方升起，我就可以长生不老。逆命题 of pq:qp 逆反命题 of pq:q p,形式蕴含与实质蕴含,15,定义：设，是命题，复合命题“当且仅当”称为等值。记为：为真当且仅当与同时为真或同时为假。,5.等值(双条件)联接词“”,16,例：非本仓库工作人员，一律不得入内。,令 P：某人是仓库工作人员；Q：某人可以进入仓库。,则上述命题可表示为：P Q,17,命题的符号化,使用上面介绍的逻辑联结词,可将一些自然语句翻译成逻辑式.即命题符号化.,（1）从语句中分析出各原子(简单)命题，将它们符号化(用字母表示)（2）使用合适的命题联结词，把原子命题逐个联结起来，组成复合命题的符号化表示。,18,例：用符号形式表示下列命题。（1）如果明天早上下雨或下雪，那么我不去学校（2）如果明天早上不下雨且不下雪，那么我去学校。（3）如果明天早上不是雨夹雪，那么我去学校。（4）只有当明天早上不下雨且不下雪时，我才去学校。,令 P：明天早上下雨；Q：明天早上下雪；R：我去学校。,（1）（PQ）R；（2）（P Q）R；（3）(PQ）R（4）R(P Q）,19,例:不是鱼死，就是网破设：鱼死，：网破则为：(PQ)(PQ)注意:命题符号化时,由于自然语言丰富多彩且有时还具有二义性，只有在具体的语言环境中，每个联接词才有确切的含义，因此具体问题要具体分析;复合命题的真值只取决于构成它的各原子命题的(真）值，而与这些原子命题的具体内容无关。,20,上面定义的五个联结词，他们各自可以表示自然语言中的一些常用语句。要表达更复杂的语句，还可能会用到多个联结词，形成更复杂的复合命题。,21,基本定义：命题变元与命题公式,2命题变元：一个没有指定具体内容的命题符号：即命题的真假没有指定。,如果没对一个命题变元赋以内容时，它的值不能确定，一旦用一个具体的命题代入，它的真值就确定了。,1.命题常元：一个表示确定命题的大写字母：即命题的值已确定。,22,命题公式 命题公式（或简称公式）是由命题常元（T和F）、命题变元以及命题联结词按一定的规则产生的符号串。,定义（命题公式的递归定义。）（1）单个命题符号是公式；（2）如果A是命题公式，则A是命题公式；（3）如果A和B是命题公式，则（AB），（AB）,(AB）,(A B）也是命题公式；有限次地利用上述（1）（3）而产生的符号串是命题公式。,23,例1 判断下列符号串是否为命题公式。（1）(P(QPR）)；（2）(PQ)(QR)为了省掉一些括号,作如下约定：五种连接词的运算优先级的次序由高到低如下：，多个同类联接词按从左到右的优先次序运算。公式（A）的括号可省略整个公式的最外层括号可省略,24,例：以下符号串是命题公式，可按定义生成。（P）（P Q）R）Q）按约定可省掉一些（）简化写成：P（PQ）RQ,25,命题公式的真假值是不确定的。当命题公式中所有的命题变元都代以命题时，命题公式就变为命题。,即所有公式中的命题变元用指定的命题（真值）代入（或指派），就得到一个公式的值。,26,2.公式的解释(指派),设G是命题公式，A1，A2，An是出现在G中的所有命题变元，指定A1,A2,An的一组真值（a1,a2,an)aiT,F,i=1,n,则这组真值称为公式G的一个解释。例如公式:(PQ)的解释为:(T,T)(T,F),(F,T),(F,F)或表示为:(1,1),(1,0),(0,1),(0,0),由定义知，含n(n1)个命题变元的命题公式共有2n个不同的解释。,可以采用真值表的方法，将一个命题公式的所有解释与公式的真值对应起来，形成该命题公式的真值表。,27,例：公式：在解释(0，0)，(0，1）和（1，1）下为真，在其他解释下为假。,公式的真值表,28,(PQ)R的真值表,29,判断 p(qr)和（pq)(pr)是否等值的真值表,30,逻辑运算和位运算,计算机用位（bit)表示信息。位是一个具有两个可能值的符号，即0和1。计算机的位运算对应于逻辑联结词。只要在位运算符(AND），（OR）和（XOR）的真值表中用1代替T，用0代替F即可。信息一般用位串(即0和1构成的序列)表示。对位串的运算即可用来处理信息。,31,命题逻辑的应用,逻辑在数学、计算机科学一其他许多学科有着重要的应用。例如，数学，自然科学以及自然语言中的语句通常不太准确，甚至有歧义，为了使其精确表达，可以将它们翻译成逻辑语言。,32,命题逻辑应用实例,1.系统规范说明:在描述硬件系统和软件系统时，系统和软件工程师根据自然语言描述的需求，生成精确而无二义性的规范说明，这些规范说明可作为系统开发的规范说明。例1:使用逻辑联结词表示规范说明:“当文件系统已满时，不能够发送自动应答”。令p表示：能够发送自动应答，令q表示:文件系统满了。则该规范说明可以表示成:q p,33,命题逻辑的应用,例2:确定下列系统规范说明是否是一致的。“诊断消息存储在缓冲区中或者被重传.”“诊断消息没有存储在缓冲区中。”如果诊断消息存储在缓冲区中，那么它被重传。”（备注:三个规范说明都能同时为真则表示是一致的)。,34,布尔搜索,逻辑联结词广泛用于大量信息搜索中。例如网页索引。由于搜索采用命题逻辑技术，所以称为布尔搜索。例:网页搜索。大部份Web搜索引擎支持布尔搜索技术，以有助于寻找有关特定主题的网页。基本都支持AND，OR 及NOT等。(但用户不需要写出来)。,35,逻辑电路,命题逻辑可应用于计算机硬件的设计。,36,思考题：利用命题逻辑解决问题,问题：三人估计比赛结果，甲说“A第一，B第二”，乙说“C第二，D第四“，丙说”A第二，D第四“，结果三人的估计都对了一半，试确定A，B，C，D的名次。,解：设 P:A第一;Q:B第二;R:C第二 S:D第四;H:A第二;,则 P Q,R S和H S 的值都为1;而PH,QR和QH 的值都为0;因此可得出:P和R及H的值为0,Q和S的值为1.由此得出:B第二,D第四,A第三,C第一,37,1.2 重言式,定义：设G是一个命题公式。重言式：G在它的所有解释下均为真，则称G是永真 的，或称G为重言式；矛盾式：若G在它的所有解释下均为假，则称G是永假的，或称G为矛盾式；可满足式：若G至少存在一个指派，使其值为真，则称G为可满足的，如果至少存在一个指派，使其值为假，则称此公式为非永真。,38,重言式（永真式）,我们只研究重言式，因为：重言式的否定是矛盾式，矛盾式的否定是重言式。故只需研究其一。重言式的合取、析取、蕴含、等值等都是重言式，由简单的重言式可推出复杂的重言式。重言式中有许多非常有用的恒等式和永真蕴含式。,39,例如：,PP：重言式 PP：矛盾式(PQ)R：偶然式（可满足式）,40,定义：对于公式A和B，如果在任何相同的解释下，其相应的值都相同，则称A与B逻辑等值（价），记为：AB。读作“A等价于B”。或者说如果AB是重言式,则称AB.注意:符号“”是关系符，不是逻辑联结词。AB当且仅当AB是重言式。,恒等式,41,基本的逻辑恒等式（P8-P9）,双重否定律：PP等幂律：PPP，PPP交换律：PQQP，PQQP结合律：(PQ)RP(QR)(PQ)RP(QR)分配律：P(QR)(PQ)(PR)P(QR)(PQ)(PR),De Morgan律：（PQ）PQ（PQ）PQ吸收律：P（PQ）P P（PQ）P零律：P11 P00同一律：P0P P1P补余律：PP1 PP0补充：PQPQ PQ QP PQ(PQ)(QP)(PQ)(PQ)(P(QR)PQR,43,思考1,思考:对联结词是否还可以归约,即五种联结词是否都是必要的?如果能归约,能归约到什么程度?,44,恒等式的判别：真值表方法和命题演算方法,例1 用真值表方法证明 E10：(PQ)PQ,45,例2 用真值表方法证明E11：PQPQ,解：构造PQ PQ的真值表如下：,46,PQ PQ 是否成立？,由于公式PQ和PQ所标记的列不完全相同所以，因此PQ PQ 不成立。,47,(1)代入规则 重言式的任何代入实例仍是重言式。,2命题演算方法,例：（PQ）（QP）是重言式，用公式 AB 代换其中的命题变元P得到的新公式（AB）Q）（Q（AB）仍是重言式。,注意：因为A B 当且仅当 A B是重言式。所以，对于基本恒等式中的任一命题变元出现的每一处均用同一命题公式代入，所得到的仍是恒等式。,48,说明：基本恒等式表中，P,Q,R可以表示任意命题公式。利用代入定理，由这些恒等式可以得到无穷多个恒等式。例如：由 PP1 可知：(PQ)(PQ)1(P)(P)1.,(2)替换规则 子公式:设C是命题公式A的一部分，且C本身也是一个命题公式，则称C为公式A的子公式。,例如 设公式A=（PQ）（PQ）（RS）,则PQ，PQ，（PQ）（RS）等均是A的子公式，,替换规则：设C是公式A中的子公式，且CD。如果将公式A中的子公式C置换成公式D之后，得到的公式是B，则AB。,(3)等值演算 等值演算是指利用已知的一些恒等式，根据置换规则、代入规则推导出另外一些恒等式的过程。,由代入规则知前述的基本等值（恒等）式不仅对任意的命题变元P，Q，R是成立的，而且当P，Q，R分别为命题公式时，这些等值式仍然成立,例2 证明：（PQ）（RQ）（PR）Q,证明（PQ）（RQ）（PQ）(RQ)E11（P R）Q E3(分配律)(PR)Q E10(德.摩根律)(PR)Q E11,51,例3 证明下列命题公式的恒等关系(P Q)(P(P Q)P Q,证明：(PQ)(P(PQ)(PQ)(P P)Q)(结合律),(PQ)(PQ)(等幂律),(P Q)(PQ)(交换律),P(Q(PQ)(结合律),PQ(交换律，吸收律),52,例4 判别下列公式的类型。（1）Q(P（PQ）)（2）（PQ）P,解（1）Q（P（PQ）Q（P（PQ）Q（PP）（PQ）Q（1（PQ）Q（PQ）QPQ（QQ）P F 所以Q(P(PQ)是矛盾式。,53,（2）（PQ）P（PQ）P P 吸收律 该公式是可满足式。,54,例5：证明公式P(（QP）Q）为重言式。P(（QP）Q）P（QQ）（PQ）（分配律）P（F（PQ）（补余律）P（PQ）（同一律）P（PQ）（De Morgan律）（PP）Q（结合律）1Q（补余律）T（零律）,55,命题公式逻辑恒等的应用：1、判定两个命题公式是否逻辑等值；2、判断是否为重言式或矛盾式；3、对命题公式进行化简,56,逻辑等值应用实例,将下面用高级语言写成的一段程序化简：if A then if B then X else Y else if B then X else Y,57,此段程序执行X的条件为：ABAB执行Y的条件为：ABAB它们分别可化简为：ABAB(AA)B(由分配律)TB B而ABAB也可化简ABABB 所以上述语句可化简成：if B then X else Y,58,永真蕴含式 定义 如果 AB 是永真式，则称其为永真蕴含式,记作AB,即ABT，则称公式A永真蕴含公式B。,注意：符号“”和“”的区别,59,基本的永真蕴含式 P10,注意：这些基本的永真蕴含式将作为以后我们利用命题逻辑进行逻辑推理的基础！,永真蕴含式的判别方法 判定“A B”是否成立的问题可转化为判定A B是否为重言式，有下述判定方法：,1.真值表法；2.假定前件A为真，看结论是否一定为真 3.假定后件B为假，看前件是否一定为假,1.真值表法,例 证明：（PQ）（P R）（Q R）R,61,2.假定前件为真 假定前件为真，检查在此情况下，其结论是否也为真。,例证明:Q（PQ）P,证明:令前件Q（PQ）为真，,则Q为真,且PQ为真。,于是Q为假，因而P也为假。因此 P为真。,故上面蕴含式 成立。,62,3、假定结论为假 假定结论为假，检查在此情况下，其前件是否也为假.,例 证明蕴含式(PQ)(RS)(PR)(QS),证明 令结论(PR)(QS)为假，则PR为真，QS为假,于是P、R均为真，而Q和S至少一个为假。,由此可知 PQ与RS中至少一个为假,因此(PQ)(RS)为假.,故上述蕴含式成立。,63,对偶式及对偶原理,定义 设A是一个仅含有联结词、和的命题公式，将公式A中用代替、用代替、用T代替F、用F代替T，所得的命题公式称为A的对偶式，记为A*。,例如：PQ R和（P Q）R互为对偶式,PQR的对偶式是,(P Q)R,64,定理：设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）若A为重言式（永真式），则A*为矛盾式。（2）由一些等值式,利用对偶原理则可得到另一些等值式。如：P(QR)(PQ)(PR)则立即可知:P(QR)(PQ)(PR),66,可满足性的应用,在不同领域：如机器人学，软件测试，计算机辅助设计、机器视觉、集成电路设计、计算机网络以及遗传学中的许多问题都可以用命题可满足性来建立模型。例如:数独谜题（要求每一行，每一列、每个小九宫格都每包含九个不同的数字）,67,数独谜题的求解(命题逻辑法),用命题逻辑描述即为:p（i,j,n)给定一个数独谜题，要求解这个谜题，我们可以寻找一个可满足性问题的解，该问题要求一组729个变元p(i,j,n)的真值，使得所有列出的合取式为真。,i=1 n=1 j=1,i=9 n=9 j=9,i=1 n=1 j=1,i=9 n=9 j=9,68,可满足性问题求解,可满足性问题求解:真值表可以判定复合命题是否为可满足的,或者等价地,判断其否定是否为永真式）。当含少量命题变元时，可以手动来完成，但当命题变元很多时，就不切实际了。例如，当有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）,（PR）Q,（PR）Q,（2）（PQ）,(（PQ）（QP）),(（PQ）（QP）),（PQ）（PQ）,（PR）Q,71,2判定蕴含式 P(QR)(PQ)(PR）是否成立,解假定结论（PQ）（PR）为假，,则PQ为真，PR为假。,由PR为假,得P为真，R为假。,又PQ为真，故得Q为真。,于是P为真，QR为假。,从而 P（QR）为假。,因此蕴含式成立。,72,讨论:判断下面命题是否成立?(1)若 A B,则A B(2)若A B,则A B,73,注意:理解基本恒等式和基本永真蕴含式 记忆 应用 它们是我们以后利用命题逻辑进行推理的基础.,74,基本的逻辑恒等式（P8-P9）,双重否定律：PP等幂律：PPP，PPP交换律：PQQP，PQQP结合律：(PQ)RP(QR)(PQ)RP(QR)分配律：P(QR)(PQ)(PR)P(QR)(PQ)(PR),75,De Morgan律：（PQ）PQ（PQ）PQ吸收律：P（PQ）P P（PQ）P零律：P11 P00同一律：P0P P1P补余律：PP1 PP0补充：PQPQ PQ QP PQ(PQ)(QP)(PQ)(PQ)(P(QR)PQR,76,最常用的推理规则(常用的永真蕴含式),附加：P(PQ)，Q(PQ)化简：(PQ)P(PQ)Q合取：P,Q PQ假言推理：PQ,P Q析取三段论：PQ,P Q拒取式：PQ,Q P假言三段论：PQ,QR PR构造性二难:PQ,RS,PR QS,77,1.4 范式,命题公式千变万化，这对研究其性质和应用研究带来很大的困难。为此，我们有必要研究如何将命题公式转化为其逻辑等价的标准形式的问题，以简化研究工作并方便应用。这种标准形式称为范式。1.合取范式与析取范式 2.主合取范式和主析取范式,78,范式(主析取范式和主合取范式)（一）极小项、极大项 定义 设有命题变元P1，P2，,Pn，形如P1*P2*P3*Pn*的命题公式称为是由命题变元P 1，P2，Pn所产生的极小项。而形如 P1*P2*P3*Pn*的命题公式称为是由命题变元P1，P2，Pn所产生的极大项。其中Pi*为Pi或为Pi(i=1,2,n).,例如,P1P2P3，P1P2P3,P1P2P3,.即每个变元在析取式（合取式）中出现一次且只出现一次，出现的形式是变元或变元的否定则这样的析取式（合取式）称为关于这些变元的极大项（极小项）,79,常用mk(0k2n-1)表示极小项 P1*P2*P3*Pn*，其中k为二进制t1t2.tn对应的十进制。且若Pi*为 Pi,ti=0.否则为1。,例如，三个命题变元P,Q,R共形成八个极小项 m0=PQR，m1=PQR，m2=PQR m3=PQR，m4=PQR，m5=PQR m6=PQR，m7=PQR,极小项：,80,极大项：,常用Mk(0k2n-1)表示极大项 P1*P2*P3*Pn*，其中k为二进制t1t2.tn对应的十进制。且若Pi*为Pi,ti=1.否则为0。,例如，三个命题变元P,Q,R共形成八个极大项 M0=PQ R，M1=P Q R，M2=P Q R M3=PQ R，M4=PQR，M5=PQ R M6=PQR，M7=PQR,81,例：含有3个命题变元P,Q,R的全部极大项和极小项如下所示,极小项 极大项 PQR-0 0 0 PQR-0 0 0 PQR-0 0 1 PQR-0 0 1 PQR-0 1 0 PQR-0 1 0 PQR-0 1 1 PQR-0 1 1 PQR-1 0 0 PQR-1 0 0 PQR _ _ _1 0 1 PQR-1 0 1 PQR-1 1 0 PQR-1 1 0 PQR-1 1 1 PQR 1 1 1容易看出，对于每个极小项(极大项)只存在一种解释使其值为真（假）(即右边的编号）,82,极小项的性质：,1）每一个极小项mk在与其下标相对应的指派下其值为真，而在其余2n-1种指派下其值为假。,2）任意两个不同的极小项的合取式是一个矛盾式(请证明),3）全部（2n个）极小项的析取式是一个重言式思考：在任何同一解释下，为什么极小项mi和mj不能同时为真？即为什么mi mj是永假式？（i j),83,极大项的性质：,1）每一个极大项Mk在与其下标相对应的指派下值为假，而在其余2n-1种指派下值为真。2）任意两个不同的极大项的析取式是一个重言式3）全部2n个极大项的合取式是一个矛盾式,思考：在任何同一解释下，为什么极大项i和j不能同时为假？即为什么i j是永真式？（i j),84,定义：由极小项所组成的析取式，称为主析取范式。,例如：(P1P2P3)(P1P2P3)(P1P2P3)是一个主析取范式。,定义:若一个主析取范式与公式A等价,则称之为A的主析取范式。,主析取范式,85,定义：由极大项所组成的合取式，称为主合取范式,(P1P2P3)(P1P2P3)(P1P2P3)(P1P2P3)是一个主合取范式。,定义:若一个主合取范式与公式A等价,则称之为A的主合取范式。,主合取范式,86,五、求公式的主析取范式和主合取范式的方法(一）真值表法(二）公式演算法,87,用真值表法求范式(一个公式的真值表确定了,则公式的标准形式即范式就可确定),-极小项 PQR 极大项 PQR-极小项 PQR-极小项 PQR极大项 PQR-极小项 PQR极大项 PQR 极大项 PQR,88,所以A的主析取范式为：(PQR)(PQR)(PQR)(PQR)A的主合取范式为：(PQR)(PQR)(PQR)(PQR)用真值表方法求主范式比较简单，但当变元数目较多时，列真值表就太麻烦。注:只要知道一命题公式G的主析(合取)取范式，就可立即写出G的真值表,反之，若已知G的真值表，则表中所有使G为真的解释所对应的极小项(极大项)的析取(合取)，便是G的主析取范式.(主合取范式),89,求(PQ)(P R)的主(合)析取范式,(PQ)(P R)(析取范式)(PQ R)(PQ 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 M6,90,定理 每一个不为永假的命题公式G(P1,P2,Pn）必与一个由 P1，P2，Pn 所产生的主析取范式等价。,永真公式的主析取范式包含所有2n个极小项。,永假公式的主析取范式不存在.,定理：每一个不为永真的公式G(P1,P2,Pn）必有一个由 P1,P2,Pn所产生的主合取范式等价。,永假公式的主合取范式包含所有 2n个极大项。,永真公式不存在主合取范式。,(二）公式演算法,求主合取范式步骤如下：1)消去公式A中 的和，得A1;2)利用德。摩尔根律将A1中的内移到原子之前，并利用双重否定律使每个原子之前最多只有一个,得A2;3)利用分配律将A2的结果化为若干个析取式的合取，其中每个析取式的因子皆为原子或原子的否定,A3;4)对于A3的结果中的每个析取式B，若命题变元P在B中不出现，则用(BP)(BP)取代B，直到每个B都变为极大项为止。,92,例1 求合式公式 P(PQ)(QP)的主范式。主合取范式：P(PQ)(Q P)P(P Q)(Q P)P(P Q)(QP)(双重否定律)(PPQ)(P(QP)由分配律(PQ)(PQ)(PP)由分配律(PQ)主析取范式：P(PQ)(Q P)(PQ)(P(QQ)(PP)Q)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ),93,例2:求合式公式（P(QR)）(P(QR)的主合取范式和主析取范式,（P(QR)）(P(QR)(P(QR)(P(QR)(P Q)（P R）（PQ）（PR）(PQR)（PQR）（PQ R）（PQ R）（PQR）（PQ R）即主合取范式为：(P QR)（PQR）（PQ R）（PQ R）（PQ R）（PQ R）主析取范式为：（PQR）（PQR）,94,主析取范式与主合取范式之关系,由于主合取范式与主析取范式在形式上对偶，所以可以通过主析取范式来求得对应的主合取范式。反之亦然。注:mi与Mi：miMi，Mimi 例：M3=PQR,(被解释(0,1,1)弄假)，则 M3=PQR=m3(被解释(0,1,1)满足）设含n个命题变元的公式G的主析取范式为：G mi1miK（含k个极小项）因为GGT，即对2n个解释全为真。所以 Gmj1mj2mj2n-K(2n-k个极小项),95,于是:G(G)（mj1mj2mj2n-k）mj1mj2 mj2n-k)Mj1Mj2 Mj2n-k例：公式:PQ 其主析取范式为 PQm3 其主合取范式为 PQ(PQ)(PQ)(PQ)M0 M1 M2如果我们求得了主析取范式，就可相应的求得主合取范式(编号互补)。反之,也成立。,96,练习：求公式（PQ）（PQ）的主析取范式及主合取范式。,97,解：求主析取范式（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）P）（(PQ）Q）（PQ）（PP）（QP）（PQ）（Q Q）（PQ）（PQ）（PQ）m1m2m3,98,（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（P（PQ）（PQ）（Q（PQ）（PQ）（PPQ）（PPQ）（QPQ）（QPQ）（PQ）M0,求主合取范式,99,总结:令A（a1、a2、an）包含有n个变量的公式，则有：,1、如果A存在与之等值的主析取范式，则必唯一；2、如果A存在与之等值的主合取范式，则必唯一；3、A是永真公式当且仅当与A等值的主析取范式恰有2n个极小项或没有主合取范式；4、A是永假公式当且仅当与A等值的主合取范式恰有2n个极大项或没有主析取范式；5、两个命题公式等值当且仅当它们有相同的主合取范式或相同的主析取范式。,100,思考1,设计一个简单的表决器,表决者每人座位旁有一按钮,若同意则按下按钮,否则不铵按钮,当表决结果超过半数时,会场电铃会响,否则不会响.试以表决人数为3人的情况设计表决器的逻辑关系.,思考2 张先生手中有代号为A、B、C、D、E的五种股票，根据当前股市情况及张先生本人的经济需求，需要有若干个股票抛出，但又必须满足如下复杂的要求：（1）若A抛出，则B也抛出；（2）B和C要留一种股票且只能留一种；（3）C和D要么全抛，要么都不抛；（4）D和E两种股票中必然有一种或两种要抛出；（5）若E抛出，则A、B也抛出。上述五种条件全部满足，问有几种合理的方案供张先生选择。,解:为简化,用A,B,C,D,E表示如下命题:A:抛出；:抛出；:抛出；:抛出；E:抛出则上述规则分别可表示为:(1)AB(2)B C(3)C D(4)DE(5)E(AB)即只需求出使上述5个公式都为真的解释即可.或者求出公式:(AB)(B C)(C D)(DE)(E(AB)的主析取范式为了减少变元个数，直接利用和等值，公式变为：(AB)(B C)(E)(E(AB),方案：只抛和方案：抛出，和,103,5 推理理论（推理规则和证明方法）,推理是由已知的命题得到新命题的思维过程。数学中的证明是建立数学命题真实性的有效论证。本节主要掌握:1.一些推理规则;2.应用推理规则进行推理的方法;3.对正确的论证进行形式化的证明。,104,例1 如果x是偶数，则x2是偶数 PQ x是偶数 P x2是偶数 Q 例2 如果x是偶数，则x2是偶数 PQ x2是偶数 Q x是偶数 P,105,例3 如果x是偶数，则x2是偶数 PQ x不是偶数 P x2不是偶数 Q 例4 如果x是偶数，则x2是偶数 PQ x2不是偶数 Q x不是偶数 P,106,依据数学知识，例和例的推理是正确的由此可知，有研究推理的必要推理规则是正确推理的依据，而正确推理对任何一门科学都是非常重要的对任一蕴含式:A B 来说,如果前提A为真,则可保证B为真,因此,任何一个蕴含式都可作为一条推理规则.,107,推理规则,定义：若H1H2HnC，则称C是H1，H2，,Hn的有效结论。称从 H1H2Hn推出C。这样的推理是正确的！注：推理正确不等于结论为真!结论为真，还取决于前提H1H2Hn的真假，如果前提为真，则结论C为真，前提为假时，C可能为真，也可能为假。,108,1.如何判断由一个前提集合能否能推出某个结论?（即判定前提和结论之间的蕴含关系是否成立）2.方法如下:（1）真值表法（2）命题演算法（3）形式证明法,109,最常用的推理规则,附加：P(PQ)，Q(PQ)化简：(PQ)P(PQ)Q合取：P,Q PQ假言推理：PQ,P Q析取三段论：PQ,P Q拒取式：PQ,Q P假言三段论：PQ,QR PR构造性二难:PQ,RS,PR QS,110,对有效论证的形式化证明（使用推理规则建立论证),只列出前提和结论叫论证，但它未必是有效的!证明是有效论证的展开，它由一系列公式组成，它们或者是前提，或者是公理，或者是前面列出的公式的结论，这些结论都必须根据推理规则得出1.永真蕴含式都可作为推理规则。2.AB 相当于 AB 且BA，所以恒等式也是推理规则。3.P规则：在推导的任何步骤上都可以引入前提。4.T规则：在推导中，如果前面有一个或多个公式蕴含S，则可把S引入推导过程。,111,例：证明下述论证：如果这里有球赛，则通行是困难的。如果他们按时到达，则通行是不困难的。他们按时到达了。所以这里没有球赛。设P：这里有球赛，Q：通行是困难的。R：他们按时到达。则上述论证能表达如下：PQ RQ R P证明请看后面的证明，凡是能构造形化式证明的，都是有效的论证，不能构造证明的论证，则不是有效的。,112,证明：（为了清楚，在左边加上数字）1 R(P规则，前提3)2 RQ(P规则，前提2)3 Q(T规则，由1,2 据I3)4 PQ(P规则，前提1)5 QP(T 规则，由4，据E24)6 P(T规则，由3,5 据I3)形式化证明：由一系列公式组成，它们或者是前提，或者公理，或者是前面公式的结论，但这些结论必需根据推理规则得出。,113,论证的一般形式：,定理的常见形式：“P当且仅当Q”“如果P,则Q”前者相当于：PQ而且QP的形式，后者相当于：PQ。定理出现的主要形式：（）PQ（）P：只需证明P是假，（）PQ：只需证明：P和Q都真，（）P Q：转为P Q形式。我们主要研究:PQ形式的证明方法。,114,1*.直接证明法：假设P是真，若能推得Q是真，则PQ是真。2*.逆反证明法：将PQ 形式转化为直接证明Q P。3*.（P1 P2 Pn)Q 形式命题的证明：转化为：Q(P1P2Pn),假设Q为假，只要能推出某一个Pi为假，则命题就成立。,证明方法：,115,4*.P1 P2 Pn(PQ）形式的证明：转化为证明：P1 P2 Pn PQ 即把P移作前提，这个方法叫CP规则。,116,5*.反证法(归谬法）设命题公式H1 Hm是相容的.于是,(H1 Hm)G 当且仅当H1,Hm,G是不相容的.证明:因为(H1 Hm)G(H1 Hm)G(H1 HmG)所以,(H1 Hm)G当且仅当(H1 HmG)PP当且仅当H1,Hm,G不相容.故定理成立.注:此种将G作为附加前提,进而推出矛盾的证明称为归缪法。数学中的反证法属此类方法,117,如果需证：H1 H2 HnC,可以转化为证明：H1 H2 Hn C F(矛盾式)即可。（前提为真，如果假设结论 C为假，则蕴含矛盾，由此可知假设结论为假不成立，即结论一定为真）,118,反证法举例,证明：(P Q）是P Q的有效结论.（将(P Q)作为假设前提）,(PQ)P，（假设前提）PQ T，1，P T，2，P Q P P T，4，PP T，3，5，合取,119,例:用归谬法,构造推理的证明前提:P(RS)Q),P,S 结论:Q证明:P(RS)Q)前提引入 P 前提引入(RS)Q 假言推理,根据(1)，(2)(Q)否定结论作附加前提引入Q 双重否定，根据(4)RS 拒取式,根据(3)，(5)S 前提引入S 化简，根据(6)SS 合取，根据(7)，(8)由(9)得出矛盾,根据归谬法可知推理正确.,120,命题逻辑小结,1.掌握五种逻辑联结词（逻辑运算符）的逻辑含义，会将命题符号化。2.掌握基本的恒等式，基本的永真蕴含式，从逻辑角度去理解它们。3.知道代入规则（对永真式）和替换规则，会对公式进行(命题演算)4.会求公式的范式与主范式。5.掌握一些常用的证明方法。会构造有效论证的形式化证明，以训练思维的严密性和逻辑性。,121,延伸阅读：时序逻辑,1996年图灵奖获得者以色列应用研究数学系教授阿米尔.伯努利提出时序逻辑。时序逻辑是对普通命题逻辑的扩充，但这一扩充意义重大，它使得系统具有了处理随时间变化而改变其值的时态变元的能力。（引入时态算子（任一时刻，某一时刻，下一时刻，直到），以及相关的公理和推理规则）时序逻辑成为研究并发程序尤其是持续不终止的反应式程序（如操作系统、网络通信协议等）的强有力的形式化工具，可充分表达程序的安全性、活性和事件的优先性等。成为程序规约、验证等的有力工具。我国科学家中科院院士唐雅松在其基础上，将时态逻辑用于软件开发的整个过程，包括需求定义、规约、设计、证实、验证、代码生成和集成，并开发了世界上第一个可执行时态逻辑语言XYZ/E和一组相应的CASE工具，在国际上引起强烈反响。伯努力本人和唐也建立了联系，成为了朋友。,122,本章作业(命题逻辑部份),1.1:1,2,5,7,111.2:3,4,7,8,11,121.3:1,2,3(a,b)1.5:6，8，12,