离散数学及应用PPT课件

01.05.2020,-,1,离散数学(DiscreteMathematics),计算机科学与技术学院（SchoolofComputerScience(2)使用合适的联结词,把简单命题逐个的联结起来,组成复合命题的符号化表示.,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.3命题公式与翻译,例3：1)我今天进城，除非下雨。2)仅当你走我将留下。3)假如上午不下雨，我去看电影，否则就在家里读书或看报。4)除非你努力，否则你将失败。5)一个人起初说：“占据空间的、有质量的而且不断变化的叫做物质”；后来他改说，“占据空间的有质量的叫做物质，而物质是不断变化的。”问他前后主张的差异在什么地方，试以命题形式进行分析。,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.3命题公式与翻译,例4：P6例1.3.3，例1.3.4(5)，例1.3.5小结：本节介了命题公式的概念及复合命题的符号化.重点是理解命题公式的递归定义,掌握复合命题的符号化方法.作业:P7:2,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.4真值表与等价公式,1.4.1真值表(TruthTable)1.4.2等价公式(ProPositionalEquivalences)1.4.1真值表前面在定义联结词时,曾经使用过真值表,下面给出真值表的定义.,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.4真值表与等价公式,定义1.4.1(对公式的赋值或解释)设P1,P2,Pn是出现在公式A中的全部的命题变元,给P1,P2,Pn各指定一个真值，称为对A的一个赋值或解释。若指定的一组值使A的真值为真(假),称这组值为A的成真(假)赋值.,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.4真值表与等价公式,例如:对公式(PQ)R，赋值011(即令P=0，Q=1，R=1)为(PQ)R的成真赋值;另一组赋值010为(PQ)R的成假赋值；还有000，001，111,01.05.2020,-,第一章命题逻辑（ProPositionalLogic）1.4真值表与等价公式,考虑：含有n个命题变元的公式共有多少组不同的赋值？定义1.4.2(真值表)在命题公式A中,对于命题变元的每一组赋值和由它们所确定的命题公式A的真值列成表，称做命题公式A的真值表。,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.4真值表与等价公式,对公式A构造真值表的具体步骤为：（1）找出公式中所有命题变元P1,P2,Pn,列出全部的2n组赋值。（2）按从小到大的顺序列出对命题变元P1,P2,Pn,的全部2n组赋值。（3）对应各组赋值计算出公式A的真值，并将其列在对应赋值的后面。,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.4真值表与等价公式,例1.给出(PQ)(PQ)的真值表：,01.05.2020,-,第一章命题逻辑（ProPositionalLogic）1.4真值表与等价公式,例1.给出(PQ)(PQ)的真值表：,01.05.2020,-,第一章命题逻辑（ProPositionalLogic）1.4真值表与等价公式,例2：构造公式(PQ)R的真值表。,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.4真值表与等价公式,例2：构造公式(PQ)R的真值表。,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.4真值表与等价公式,练习1：构造公式(PQ)(QP)真值表。,01.05.2020,-,第一章命题逻辑（ProPositionalLogic）1.4真值表与等价公式,练习1：构造公式(PQ)(QP)真值表。,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.4真值表与等价公式,练习2：构造公式(PQ)Q真值表。,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.4真值表与等价公式,练习2：构造公式(PQ)Q真值表。,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.4真值表与等价公式,1.4.2等价公式给定n个命题变元,按合式公式的形成规则可以形成无数多个命题公式,但这些无穷尽的命题公式中，有些具有相同的真值表。考虑：由n个命题变元能生成?种真值(表)不同的命题公式？,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.4真值表与等价公式,定义1.4.3:给定两个命题公式A和B，设P1,P2,Pn为出现于A和B中的所有原子变元,若给P1,P2,Pn任一组真值指派,A和B的真值都相同,则称A和B是等价的或逻辑相等.记作AB。,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.4真值表与等价公式,注:(1)“”不是逻辑联结词.(2)命题公式之间的逻辑相等关系具有：自反性：AA；对称性：若AB，则BA；传递性：若AB且BC，则AC。,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.4真值表与等价公式,证明公式等价的方法：1.真值表法2.等值演算法1.真值表法例1.(PQ)(PQ)见真值表例题1.,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.4真值表与等价公式,例2.证明:PQ(PQ)(QP),01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.4真值表与等价公式,例2.证明:PQ(PQ)(QP),01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.4真值表与等价公式,例3：判断公式P(QR)、(PQ)R是否等价。,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.4真值表与等价公式,例3：判断公式P(QR)、(PQ)R是否等价。,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.4真值表与等价公式,由真值表可知，两个公式为等价式。2.等值演算法(EquivalentCalculation)等值演算中使用的一条重要规则：置换规则定义1.4.4(子公式)：如果X是wffA的一部分,且X本身也是wff，则称X是A的子公式。例如,P(PQ)为Q(P(PQ)的子公式。,01.05.2020,-,第一章命题逻辑（ProPositionalLogic）1.4真值表与等价公式,定理1.4.1(置换定理AxiomofrePlacement)设X是wffA的子wff，若XY，则若将A中的X用Y来置换，所得公式B与A等价，即AB。证：因为对变元的任一指派,X与Y真值相同，所以Y取代X后，公式B与公式A对变元的任一指派真值也相同,所以AB。,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.4真值表与等价公式,注:满足定理1.4.1的条件的置换称为等价置换(或等价代换).定义1.4.5(等值演算)：根据已知的等价公式,推演出另外一些等价公式的过程称为等值演算.,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.4真值表与等价公式,常用的等价式：1.双重否定律：PP2.结合律：(PQ)RP(QR)(PQ)RP(QR)(PQ)RP(QR)3.交换律:PQQPPQQPPQQP4.分配律:P(QR)(PQ)(PR)P(QR)(PQ)(PR),01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.4真值表与等价公式,常用的等价式：5.幂等律:PPPPPP6.吸收律:P(PQ)PP(PQ)P7.德.摩根律:(PQ)PQ(PQ)PQ8.同一律:PFPPTP9.零律:PTTPFF,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.4真值表与等价公式,常用的等价式：10.否定律：PPTPPF11.蕴涵等值式:PQPQ12.等价等值式:PQ(PQ)(QP)13.假言易位:PQQP14.等价否定等值式:PQPQ15.归谬论:(PQ)(PQ)P,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.4真值表与等价公式,其中P,Q,R等代表任意命题公式.这样上面的每一个公式都是一个模式,它可以代表无数多个同类型的命题公式.例如,PPT中,用(PQ)置换P,则得(PQ)(PQ)T,用P置换P,则得(P)(P)T。,01.05.2020,-,第一章命题逻辑（ProPositionalLogic）1.4真值表与等价公式,例1：证明Q(P(PQ)QP证:Q(P(PQ)QPP(吸收律)例2：证明PQQPQ证：(PQ)Q(PQ)(QQ)(PQ)TPQ,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.4真值表与等价公式,例3：证明(PQ)(QR)PQR证：(PQ)(QR)(PQ)(QR)(PQ)(QR)(PQ)(QR)(PQR)(QQR)PQR,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.4真值表与等价公式,例4：验证P(QR)(PQ)R证:右(PQ)RPQRP(QR)P(QR)P(QR)练：1.(PQ)(PR)P(QR)2.(PQ)(PQ)(PQ)(PQ),01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.4真值表与等价公式,等值演算在计算机硬件设计中,在开关理论和电子元器件中都占有重要地位.小结:本节介绍了真值表、公式等价、等值演算和等价置换等概念，给出了常用的重要等价公式（26个）。重点掌握用真值表法验证公式的等价性和等值演算法推演两个公式等价。,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.4真值表与等价公式,作业：Pg.13:1(2),(4)；2(2),(4)；4；6（3）预习:1.5,1.6思考题：Pg.13:5,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.5重言式与蕴含式(TautologyandImplication),1.5.1命题公式的分类1.5.2重言式(Tautology)与矛盾式(contradictory)的性质1.5.3蕴含式(ImPlication),01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.5重言式与蕴含式(TautologyandImplication),1.5.1命题公式的分类复合命题,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.5重言式与蕴含式(TautologyandImplication),定义1.5.1设A为任一命题公式，(1)若A在其各种赋值下的取值均为真，则称A是重言式或永真式,记为T或1。(2)若A在其各种赋值下的取值均为假，则称A是矛盾式或永假式,记为F或0。(3)若A不是矛盾式则称A为可满足式(satisfiable)。注:由定义可知,重言式一定是可满足式,反之不真.,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.5重言式与蕴含式(TautologyandImplication),判别命题公式的类型有两种方法:真值表法和等值演算法.等值演算法是将所给命题公式通过等值演算化为最简单的形式,然后再进行判别.例1.判别下列命题公式的类型.(1).Q(PQ)P)(重言式)(2).(PP)(QQ)R(矛盾式)(3).(PQ)P.(可满足式),01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.5重言式与蕴含式(TautologyandImplication),1.5.2重言式(Tautology)与矛盾式(contradictory)的性质定理1.5.1:任何两个重言式的合取或析取,仍然是一重言式.（由幂等律立得）证明:设A和B为两个重言式,则不论A和B的分量指派任何真值,总有A为T,B为T,故ABT，ABT。,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.5重言式与蕴含式(TautologyandImplication),定理1.5.2:一个重言式(矛盾式),对同一分量都用任何合式公式置换,其结果仍为一重言式(矛盾式).证明：由于重言式(矛盾式)的真值与对变元的赋值无关，故对同一变元以任何合式公式置换后，重言式(矛盾式)的真值仍永为T（F）。,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.5重言式与蕴含式(TautologyandImplication),定理1.5.3：A,B是两个命题公式，AB的充要条件是AB为重言式。证明:若AB为重言式，则AB永为T，即A，B的真值表相同，所以AB。反之，若AB，则A，B真值表相同，所以AB永为T，所以AB为重言式。,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.5重言式与蕴含式(TautologyandImplication),它们之间具有如下关系:PQQPQPPQ,1.5.3蕴含式（ImPlication）定义1.5.2：当且仅当PQ是一个重言式时，我们称“P蕴含Q”，并记作PQ.,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.5重言式与蕴含式(TautologyandImplication),因此,要证明PQ有三种方法:1)真值表法:即列出PQ的真值表,观察其是否永为真。2)等值演算法：通过证明PQ1来证PQ3)分析法：直接分析法:假定前件P是真，推出后件Q是真。间接分析法:假定后件是假，推出前件是假,即证QP。,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.5重言式与蕴含式(TautologyandImplication),例:证明Q(PQ)P1)法1：真值表（略）2)法2：Q(PQ)P(Q(PQ)(P)Q(PQ)(P)(PQ)(PQ)1即Q(PQ)P,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.5重言式与蕴含式(TautologyandImplication),3)直接分析法：若Q(PQ)为真，则Q，PQ为真，所以Q为假，P为假，所以P为真。间接分析法：若P为假，则P为真，再分二种情况：若Q为真，则Q为假,从而Q(PQ)为假.若Q为假，则PQ为假，则Q(PQ)为假.根据，所以Q(PQ)P,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.5重言式与蕴含式(TautologyandImplication),下面常用的14个蕴含式,都可以用上述方法加以推证.1.PQP2.PQQ3.PPQ4.PPQ5.QPQ6.(PQ)P7.(PQ)Q8.P(PQ)Q9.Q(PQ)P10.P(PQ)Q11.(PQ)(QR)PR12.(PQ)(PR)(QR)R13.(PQ)(RS)(PR)(QS)14.(PQ)(QR)(PR),01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.5重言式与蕴含式(TautologyandImplication),等价式与蕴含式的关系:定理1.5.4:设P,Q为任意两个命题公式,PQ的充要条件为PQ且QP.证：若PQ，则PQ为永真式因为PQ（PQ）（QP）所以PQ，QP为永真式,从而PQ，QP.反之，若PQ，QP，则PQ，QP为永真式,所以（PQ）（QP）为永真式，从而PQ为永真式，即PQ.,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.5重言式与蕴含式(TautologyandImplication),蕴含的性质:设A，B，C为任意wff,1)若AB，且A为永真式，则B必为永真式.2)若AB，BC，则AC.3)若AB，AC，则ABC.4)若AB且CB，则ACB.证：1)因为AB，A永为T,所以B必永为T.2)由I11（AB)(BC）AC,所以若AB，BC，则（AB)(BC）永为T,从而AC永为T,故AC.,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.5重言式与蕴含式(TautologyandImplication),3)（AB）（AC）（AB）（AC）A（BC）ABC4)(AB)(CB)(AB)(CB)(AC)B(AC)BACB,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.5重言式与蕴含式(TautologyandImplication),小结：本节介绍了命题公式的分类，重言式、矛盾式与蕴含式的概念及其性质，等价式与蕴涵式的关系。重点掌握:（1）用等值演算法判别命题公式的类型。（2）重言式、矛盾式与蕴涵式的性质。（3）等价式与蕴涵式的关系。,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.5重言式与蕴含式(TautologyandImplication),作业:Pg16：1,2(2),(4);5.预习:1.6思考题:1)为什么要引入联结词?2)什么是最小功能完备联结词组?,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.6其它联结词(OtherConnectives),1.6.1不可兼析取(排斥或/异或)(exclusiveor)1.6.2与非联结词(Nand)1.6.3或非联结词(Nor)1.6.4条件否定联结词(Non-conditional)1.6.5最小联结词组(Theminimalsetofconnectives),01.05.2020,-,在第二节(1.2)中我们定义了五种基本的联结词，,但在命题逻辑中,这些联结词还不能很广泛地直接表达命题之间的联系(例如,“P异或Q”只能间接地表示为(PQ)(PQ),为此本节再给出逻辑设计中常用的另外四种联结词.,第一章命题逻辑（PropositionalLogic）1.6其它联结词(OtherConnectives),01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.6其它联结词(OtherConnectives),1.6.1不可兼析取(排斥或/异或)(exclusiveor)定义1.6.1:设P,Q为二命题，复合命题“P,Q之中恰有一个为真”称为P与Q的不可兼析取，记作PQ，符号“”称为异或联结词.PQ为真当且仅当P和Q的真值不同.,01.05.2020,-,联结词“”的定义真值表,定义了联结词“”后,命题逻辑中的有些命题就可以符号化为非常简捷的形式.,第一章命题逻辑（PropositionalLogic）1.6其它联结词(OtherConnectives),01.05.2020,-,第一章命题逻辑（ProPositionalLogic）1.6其它联结词(OtherConnectives),例:派小王或小李中的一人去开会。（排斥或）设P：派小王去开会。Q：派小李去开会。则上述命题可符号化为：(PQ),01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.6其它联结词(OtherConnectives),说明：“”属于二元(binary)运算符.联结词“”的性质:设P,Q,R为命题公式,则有(1)PQQP(交换律)(2)(PQ)RP(QR)(结合律)(3)P(QR)(PQ)(PR)(分配律)(4)(PQ)(PQ)(PQ)(5)(PQ)(PQ)(6)PPF,FPP,TPP,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.6其它联结词(OtherConnectives),定理1.6.1:设P,Q,R为命题公式,如果PQR,则PRQ,QRP,且PQR为一矛盾式.证:由PQR得PRP(PQ)(PP)QFQQQRQ(PQ)FPPPQRRRF,01.05.2020,-,第一章命题逻辑（ProPositionalLogic）1.6其它联结词(OtherConnectives),1.6.2与非联结词(Nand)定义1.6.2设P,Q为二命题，复合命题“P与Q的否定”称为P与Q的与非式，记作PQ，符号“”称为与非联结词.PQ为真当且仅当P和Q不同时为真.,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.6其它联结词(OtherConnectives),联结词“”的定义真值表,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.6其它联结词(OtherConnectives),说明:(1)由定义可知,PQ(PQ)(2)“”属于二元(binary)运算符.联结词“”的性质:(1)PP(PP)P(2)(PQ)(PQ)(PQ)(PQ)(3)(PP)(QQ)PQ(PQ)PQ,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.6其它联结词(OtherConnectives),1.6.3或非联结词(Nor)定义1.6.3设P,Q为二命题，复合命题“P或Q的否定”称为P与Q的或非式，记作PQ，符号“”称为或非联结词.PQ为真当且仅当P与Q同为假.,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.6其它联结词(OtherConnectives),联结词“”的定义真值表,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.6其它联结词(OtherConnectives),说明:(1)由定义可知,PQ(PQ)(2)“”属于二元(binary)运算符.联结词“”的性质:(1)PP(PP)P(2)(PQ)(PQ)(PQ)(PQ)(3)(PP)(QQ)PQ(PQ)PQ,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.6其它联结词(OtherConnectives),1.6.4条件否定联结词(Non-conditional)定义1.6.4设P,Q为二命题，复合命题“PQ”称为命题P与Q的条件否定式,PQ为真当且仅当P为真且Q为假.,01.05.2020,-,第一章命题逻辑（ProPositionalLogic）1.6其它联结词(OtherConnectives),联结词“”的定义真值表,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.6其它联结词(OtherConnectives),说明:(1)由定义可知,PQ(PQ)(2)“”属于二元(binary)运算符.有了联结词后，合式公式的定义1.3.2可加入这四个联结词.,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.6其它联结词(OtherConnectives),1.6.5最小联结词组(Theminimalsetofconnectives)至此,我们一共定义了9个联结词,为了直接表达命题之间的联系,是否还需要定义其它联结词呢?回答是否定的.即含n个命题变元的所有个互不等价的命题公式,均可由这9个联结词直接表达.下面我们以含两个命题变元P，Q的所有互等价的命题公式为例，来说明这一问题。,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.6其它联结词(OtherConnectives),由两个命题变元P，Q所构成的互不等价的个命题公式如下:,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.6其它联结词(OtherConnectives),由上表可知,9个联结词足以直接表达命题之间的各种联系.二元运算中，9个联结词并不都是必要的。,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.6其它联结词(OtherConnectives),定义1.6.5：在一个联结词的集合中,如果一个联结词可由该集合中的其它联结词定义,则称此联结词为冗余联结词,否则称为独立联结词.不含冗余联结词的联结词组称为最小联结词组.说明:最小联结词组中的联结词构成的式子足以把一切命题公式等价的表达出来。,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.6其它联结词(OtherConnectives),对于9个联结词的集合,由于(1)PQ(PQ)(QP)(2)PQPQ(3)PQ(PQ)(4)PQ(PQ),01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.6其它联结词(OtherConnectives),(5)(PQ)(PQ)(6)PQ(PQ)(7)PQ(PQ)(8)PQ(PQ),01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.6其它联结词(OtherConnectives),故任意命题公式都可由仅包含,或,的命题公式等价代换.即9个联结词的集合中至少有七个冗余联结词.又注意到联结词,和,不再有冗余联结词,故,或,为最小联结词组.但实际中为了使用方便,命题公式常常同时包含,.,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.6其它联结词(OtherConnectives),例1:试证是最小联结词组.证：P(PP)PPPQ(PQ)(PQ)(PQ)(PQ)PQ(PQ)(PP)(QQ)(PP)(QQ)例2.试证，是最小联结词组证：PQ(PQ)(PQ)PQ(P)QPQ,01.05.2020,-,第一章命题逻辑（ProPositionalLogic）1.6其它联结词(OtherConnectives),小结:本节主要介绍了四种新的联结词及最小联结词组.作业:1.P19:2,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.6其它联结词(OtherConnectives),2.预习1.7思考题:1.何谓命题公式的(主)析(合)取范式?2.命题公式的(主)析(合)取范式唯一吗?3.为何要将命题公式化为与之等价的主析(合)取范式?4.如何将命题公式化为与之等价的主析(合)取范式?5.两个等价的命题公式其(主)析(合)取范式有何关系?,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.7对偶与范式(Dual(2)一个合取范式是重言式,当且仅当它的每一个简单析取式都是重言式.,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.7对偶与范式(Dual(2)除去中所有永假的析取项;,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.7对偶与范式(Dual(4)若中某简单合取式B中不含命题变元Pi,添加(PiPi),然后应用分配律展开.即BB1B(PiPi)(BPi)(BPi).例1：求(PQ)R)P的主析取范式。例2:求(PQ)R的主析取范式.例3:求(PQ)(PQ)的主析取范式.,01.05.2020,-,第一章命题逻辑（ProPositionalLogic）1.7对偶与范式(Dual(2)除去中所有永真的合取项;,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.7对偶与范式(Dual(4)若中某简单析取式B中不含命题变元Pi,添加(PiPi),然后应用分配律展开.即BB0B(PiPi)(BPi)(BPi).例1：求(PQ)R)P的主合取范式。例2:求(PQ)R的主合取范式.例3:求(PQ)(PQ)的主合取范式.,01.05.2020,-,第一章命题逻辑（ProPositionalLogic）1.7对偶与范式(Dual或称可由逻辑推出.一般地,如果有n个前提H1,H2,H3,.,Hn,若H1H2H3.HnC,则称C是一组前提H1,H2,Hn的有效结论。注意:在形式逻辑中,我们并不关心结论是否真实,而主要关心结论是否可以由给定的前提推出来,我们只注意推理的形式是否正确.因此,有效结论并不一定是正确的,只有正确的前提经过正确的推理得到的逻辑结论才是正确的.,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.8推理理论(InferenceTheory),证明C是A的有效结论的方法就是判别重言蕴含的方法.前面我们介绍的论证方法有真值表法、等值演算法、主析（合）取范式法。论证方法千变万化，但最基本、最常用的方法有三种：推理证明的方法,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.8推理理论(InferenceTheory),1.8.2真值表法(TruthTable)构造命题公式H1H2HnC的真值表，若为永真，H1H2HnC推理正确。例：证明(PQ)Q)P,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.8推理理论(InferenceTheory),由上面真值表可知(PQ)Q)P。1.8.3直接证法(DirectProof)直接证法：由一组前提，利用一些公认的推理规则，根据已知的等价或蕴含公式推演得到有效结论。常用的推理规则P规则:（也称前提引入规则）前提在推导过程中的任何时候都可以引用。T规则:在推导过程中，所证明的结论、已知的等价或蕴含公式都可以作为后续证明的前提，命题公式中的任何子公式都可以用与之等价的命题公式置换。,01.05.2020,-,第一章命题逻辑（ProPositionalLogic）1.8推理理论(InferenceTheory),常用的蕴含式和等价式见课本P43表1-8.3、1-8.4例1.如果考试及格，那我高兴。若我高兴，那么我饭量增加。我的饭量没增加，所以我考试没有及格。试对上述论证构造证明。解：设P：我考试及格.Q：我高兴。R：我饭量增加。则此论证可表为(PQ)(QR)RP证:,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.8推理理论(InferenceTheory),(PQ)(QR)RP证:1PQP2QRP3RP4QT，2，3I115PT，1，4I11,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.8推理理论(InferenceTheory),例2.证明RS是前提CD,CR,DS的有效结论。证：1.CDP2.CRP3.DSP4.CDT，1E5.RCT，2E6.RST，5，4，3I137.RST，6E,01.05.2020,-,第一章命题逻辑（ProPositionalLogic）1.8推理理论(InferenceTheory),例3：PQ,QR,PS,SR(QP)证明：1.PSP(前提引入)2.SP(前提引入)3.PT1,2I114.PQP(前提引入)5.QT3,4I116.QRP(前提引入)7.RT5,6I118.R(QP)T4,7I9,01.05.2020,-,第一章命题逻辑（ProPositionalLogic）1.8推理理论(InferenceTheory),例4：证明(P(QR)(SQ)(PS)R.证：（1）PSP（2）PT（1）I1（3）ST（1）I1（4）P（QR)P（5）QRT(2)，(4)I11（6）SQP（7）QT(3)，(6)I11（8）RT(5)，(7)I11,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.8推理理论(InferenceTheory),1.8.4间接证法(IndirectProof)附加前提证明法适用于如下类型蕴含式的证明:(A1A2Ak)(AB)(*)欲证明(*)式，只需证明(A1A2AkA)B即可，因为,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.8推理理论(InferenceTheory),(A1A2Ak)(AB)(A1A2Ak)(AB)(A1A2Ak)(AB)(A1A2Ak)(AB)A1A2AkAB(A1A2AkA)B(A1A2AkA)B(A1A2AkA)B这样一来,原来结论中的前件A就变成了前提,称A为附加前提.,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.8推理理论(InferenceTheory),由证(A1A2AkA)B永真而证得(A1A2Ak)(AB)永真的证明方法,称为附加前提证明法或CP规则.,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.8推理理论(InferenceTheory),例1:证明:(ABC)(BA)(DC)(AD)证：1.ABCP2.BAP3.DCP4.AP(附加前提)5.BCT1，4I116.ABT2,E7.CDT3，E8.BT4，6I119.CT5，8I1110.DT7，9I1111.AD，10CP,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.8推理理论(InferenceTheory),例2：前提：P(QR),SP,Q结论：SR.证明：1.SPP2.SP（附加前提引入）3.PT（1,2）I114.P(QR)P5.QRT（3,4）I116.QP7.RT（5,6）I118.SRT（2,7）CP,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.8推理理论(InferenceTheory),2.归谬法定义1.8.2：设命题公式集合为H1,H2,H3,.,Hn，若H1H2H3.Hn为永假式，则称H1,H2,H3,.,Hn是不相容的，否则称为相容的。由于(A1A2Ak)B(A1A2Ak)B(A1A2AkB)故要证(A1A2Ak)B永真,只需证A1A2AkB永假.这种将B作为附加前提推出矛盾的证明方法称为归谬法.,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.8推理理论(InferenceTheory),例1:证明(PQ)(RQ)(RS)P证：1.PP(附加前提)2.PQP3.QT(1,2)I114.RQP5.RT(3,4)I116.RSP7.RT(6)I18.RR(矛盾）T(5,7)由8得出了矛盾,根据归谬法说明原推理正确.,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.8推理理论(InferenceTheory),例2:从PQRS,(TQ)(SU),R,(WP)(TU),推出WT证：1.PQRSP2.(TQ)(SU)P3.(WP)(TU)P4.RP5.WP(附加前提)6.(RS)T4I37.(PQ)T1，6I118.PT5，3I119.QT7，8I1110.TT9，2I1111.WT,10CP,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.8推理理论(InferenceTheory),小结:本节将推理证明命题公式序列化.主要介绍了推理证明重言蕴含式的直接证法和间接证法。作业:1.P35:1,2,5,92.预习第二章2.1,2.2,01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.8推理理论(InferenceTheory),补充:分情况证明欲证：(P1P2Pn)Q只需证明,1in,有PiQ因为：(P1P2Pn)Q(P1P2Pn)Q（P1P2Pn)Q(P1Q)(P2Q)(PnQ)(P1Q)(P2Q).(PnQ),01.05.2020,-,第一章命题逻辑（PropositionalLogic）1.8推理理论(InferenceTheory),例：证明（(PQ)P)(PQ)P）)Q永真证：情况11.PQP2.PP3.QT1，2I11情况21.PQP2.PP3.QT1，2I11,01.05.2020,-,结束,谢谢!,第一章命题逻辑（PropositionalLogic）,01.05.2020,-,第二章谓词逻辑（PredicateLogic）,2.1谓词的概念与表示(Predicateanditsexpression)2.2谓词公式与翻译(Predicateformulae)2.3变元的约束(Boundofvariable)2.4谓词演算的等价式与蕴含式(Equivalences客体变元x,y,z具有关系A，记作A(x,y,z).,H(x)、L(x,y)、A(x,y,z)本身并不是一个命题.只有用特定的客体取代客体变元x,y,z后，它们才成为命题。我们称H(x)、L(x,y)、A(x,y,z)为命题函数。一般地我们有,01.05.2020,-,第二章谓词逻辑（PredicateLogic）2.1谓词的概念与表示(PredicateandItsExpression),定义2.1.1:由一个谓词H和n个客体变元组成的表达式H(x1,x2,xn)称为n元简单命题函数.由定义可知,n元谓词就是有n个客体变元的命题函数.当n=0时,称为0元谓词.因此,一般情况下,命题函数不是命题;特殊情况0元谓词就变成一个命题.复合命题函数:由一个或几个简单命题函数以及逻辑联结词组合而成的表达式.,01.05.2020,-,第二章谓词逻辑（PredicateLogic）2.1谓词的概念与表示(PredicateandItsExpression),例1:若x的学习好,则x的工作好设S(x):x学习好；W(x):x工作好则有S(x)W(x)例2:将下列命题用0元谓词符号化.(1)2是素数且是偶数.(2)如果2大于3,则2大于4.(3)如果张明比李民高,李民比赵亮高,则张明比赵亮高.,01.05.2020,-,第二章谓词逻辑（PredicateLogic）2.1谓词的概念与表示(PredicateandItsExpression),解:(1)设F(x):x是素数.G(x):x是偶数.则命题符号化为：F(2)G(2)(2)设L(x,y)：x大于y.则命题符号化为：L(2,3)L(2,4)(3)设H(x,y):x比y高.a:张明b:李民c：赵亮则命题符号化为：H(a,b)H(b,c)H(a,c)注意:命题函数中,客体变元在哪些范围内取特定的值,对命题的真值极有影响.,01.05.2020,-,第二章谓词逻辑（PredicateLogic）2.1谓词的概念与表示(PredicateandItsExpression),例如:H(x,y)H(y,z)H(x,z)若H(x,y)解释为:x大于y,当x,y,z都在实数中取值时,则这个式子表示“若x大于y且y大于z，则x大于z”。这是一个永真式。如果H(x,y)解释为:“x是y的儿子”,当x,y,z都指人时，则这个式子表示“若x为y的儿子且y是z的儿子，则x是z的儿子”。这是一个永假式。如果H(x,y)解释为:“x距y10米”,当x,y,z为平面上的点，则这个式子表示“若x距y10米且y距z10米，则x距z10米”。这个命题的真值将由x,y,z的具体位置而定，它可能是1，也可能是0。,01.05.2020,-,第二章谓词逻辑（PredicateLogic）2.1谓词的概念与表示(PredicateandItsExpression),在命题函数中，客体变元的取值范围称为个体域，又称之为论域。个体域可以是有限事物的集合，也可以是无限事物的集合。全总个体域：宇宙间一切事物组成的个体域称为全总个体域。,01.05.2020,-,第二章谓词逻辑（PredicateLogic）2.1谓词的概念与表示(PredicateandItsExpression),2.1.2量词(Quantifiers)量词：分为全称量词()和存在量词()1.全称量词(TheUniversalQuanti