Sun离散数学第1章命题逻辑(第1-7讲).ppt

《Sun离散数学第1章命题逻辑(第1-7讲).ppt》由会员分享，可在线阅读，更多相关《Sun离散数学第1章命题逻辑(第1-7讲).ppt（78页珍藏版）》请在三一办公上搜索。

1、,离散数学,主讲教师：信息院 孙丽云办公地点：F103,本课程共72学时，周学时为5，学分4.5；,若旷课超过总学时的1/3，或缺交作业超过总次数的1/4，则无考试资格且无补考资格。,课时安排：,总成绩100分，比例分配如下：（1）期末：70分；（2）期中：5分；（3）平时25分，包括作业情况（10分）：缺交作业一次扣2分，分数扣完为止；若出现雷同，所有雷同者每人扣5分！多次雷同无平时成绩！课堂情况：旷课1次扣2分；根据课堂上回答问题情况，可酌情加分或减分。,成绩评定,第一部分 数理逻辑：包括命题逻辑和谓词逻辑。第二部分 集合论：包括集合、关系和函数。第三部分 代数结构：包括代数系统的基本概念

2、，几类典型的代数系统。第四部分 图论基础：包括图的基本概念，几种特殊的图。,离散数学的主要内容,第1章 命题逻辑,数理逻辑：用数学方法研究推理，是研究推理中前题和结论之间的形式关系的科学。,1.1 数理逻辑简介,简单推理举例：(1)如果他不去玩电子游戏,他会有充足的时间;(2)假如他有充足的时间,他就会认真复习英语;(3)如果他认真复习英语,他的英语考试就不会不及格;(4)他的英语考试没及格。根据以上四个条件，能得到什么结论？,命题的真值:每个命题的唯一取值,只有“真”和“假”两个值,记作T(True)和F(False)或1和0。,命题：能分辨真假的陈述句。,1.2 命题及命题符号化,1.是否

3、是陈述句？,2.是否能分辨真假？,例1 判断下列语句是否为命题，若是命题判断其命题真值,1.北京化工大学是一所综合性的大学。2.你是北方学院的学生吗？3.今年的雪好大啊！4.雪是黑的。,(是命题、真值为T),(是命题，真值为F),(感叹句，不是命题),(疑问句，不是命题),1.x大于9。,(是命题，真值目前不能确定),(不是命题，不能分辨真假),例2 判断下列语句是否为命题，若是命题判断其命题真值,2.地球之外有生命存在。,1.2 命题及命题符号化,3.我正在说谎。,(悖论，不是命题),只要陈述句的真值是客观存在而且是唯一的，即使目前不知道真值，该陈述句也是命题。,判断一个语句是否是命题的关键

4、是：(1)语句必须是陈述句。(2)陈述句必须具有唯一的真值。要注意两点：一个陈述句在客观上能判断真假就是命题，而不受人的知识范围的限制。一个陈述句暂时不能确定真值，但到了一定时候就可以确定，与一个陈述句的真值不能唯一确定是不同的。,例：1-9=-8,例：2012年10月10日天气晴朗。,是命题。,是命题，真值需等2012年10月10日确定。,注意：,简单命题：由简单句构成的命题，也称为原子命题。,命题标识符：表示原子命题的符号,可用英文字母P,Q,R,来表示，并将字母放在所表示的命题之前。例：P:今天天气晴朗。,复合命题：由若干个原子命题通过联结词构成的复合句表示的命题。,例：如果明天天气好，

5、我们就去爬长城。,P：明天天气好。Q：我们去爬长城。联结词：如果就,组成：,命题可分为简单命题与复合命题。,1、否定联结词（用或表示）命题P的否定称为P的否命题，记作P。一元运算符，P（读作“非P”）。相当于“非”，“不”等联结词。,真值表,例1：P：今天是晴天。则：今天不是晴天可符号化为：例2：Q：小华学习用功。则Q表示的含义是：例3：R：北京是中国的首都。则求R及R的真值。,P,小华学习不用功。,逻辑联结词,1、否定联结词（用或表示）,注意：某个命题的否定命题不是简单的在原命题中加个“不”字就行的。,例1：P:这些都是学生；其否定命题的含义是？,P:这些有的不是学生。,例2：P:本句是六字

6、句；Q:本句不是六字句。P、Q互为否定命题吗？,不是，P、Q都为真命题。,复合命题“P并且Q”称为命题P和Q的合取式复合命题，记作PQ。二元运算符，PQ（读作“P且Q”）。相当于“既又”、“并且”等联结词。,真值表,2、合取联结词（用表示）,有假则假，全真才真,例1 P:李军聪明,Q:李军用功,则命题“李军既聪明又用功”便可由“PQ”来描述。例2 A:1+11=100,B:熊猫是稀有动物“AB”表示“1+11=100且熊猫是稀有动物”,在自然语言中,上述命题是没有意义的,因为A和B毫无内在联系。数理逻辑中,我们关心的是复合命题与构成复合命题的各原子命题之间的真值关系,即抽象的逻辑关系,并不关心

7、各语句的具体语义。但“”联结的是两个命题，并不能见到“与”、“和”就用“”。例：“张三和李四是好朋友。”是简单命题。,2、合取联结词（用表示）,复合命题“P或Q”称为命题P和Q的析取式复合命题，记作PQ。二元运算符，PQ（读作“P或Q”）。相当于“或或”、“或者”等联结词。,真值表,3、析取联结词（用表示）,例1 P:开关坏了。Q:灯泡坏了。则PQ:开关坏了或灯泡坏了。例2 P：235。Q：昨天是元宵节。则PQ表示？,有真则真，全假才假,日常语言中的“或”是具有二义性的，用“或”联结的命题有时是具有相容性的，如张笑爱唱歌或爱听音乐，我们称之为可兼或。而有时又具有排斥性，称为不可兼或（异或），如

8、：张笑只能挑选302或303房间。可用 表示，将在1.6节中简单介绍。,3、析取联结词（用表示）,注意：“pq”的逻辑关系是p、q两命题中至少有一个为真则析取式为真。因而，自然语言中常用的联结词诸如：“或者或者”、“可能可能”等，都可以符号化为“”。,复合命题“如果P则Q”称为命题P和Q的条件式复合命题，记作P Q。二元运算符，P Q（读作“如果P则Q”）。相当于“如果则”、“只要就”等联结词。,真值表,4、蕴含联结词或条件联结词（用表示）,命题P Q中的条件联结词“”表示的基本逻辑关系是:P是Q的充分条件,Q是P的必要条件。因此,复合命题:“只要P就Q”、“只有Q才P”等都可写成“P Q”的

9、形式。,5、等价联结词或双条件联结词（用表示）,复合命题“P当且仅当Q”称为命题P和Q的双条件式复合命题，记作P Q。二元运算符，P Q（读作“P当且仅当Q”）。相当于“当且仅当”、“同一样”等联结词。,真值表,例：将下列复合命题符号化并求其真值：(1)1+1=2当且仅当3+5=8。(2)3+6=8同7+9=10是一样的。,P Q中“”表示的基本逻辑关系是:P、Q互为充分必要条件。,1.3 命题公式,命题常元：数理逻辑中，字母P,Q,R表示的一个确定的简单命题。,命题变元：字母P,Q,R表示的不确指的命题。,（1）命题常元和命题变元是命题公式；（2）如果A是命题公式，则A也是命题公式；（3）如

10、果A,B是命题公式，则(AB),(AB),(AB)和(AB)也是命题公式；（4）规则（1）-（3）的有限次使用得到的由命题常元、命题变元、逻辑联结词和括号组成的符号串也是命题公式。,命题公式的递归定义：,注意：命题变元不是命题！,命题公式：由命题变元或命题常元、联结词和圆括号按一定逻辑关系联结起来的字符串。,1)(R(P)(P(Q)2)PQR3)P(QR)4)(PQ)(QR)5)(PQ),(Q R)6)(P Q)(P Q)(P Q)7)P,判别下列符号串是否为命题公式（P、Q、R是命题变元）,是,否（PQ不符合）,否（不符合）,否（右端多了括号）,否（，不符合）,是,是,命题公式举例,赋值：对

11、命题变元指派确定的真值，也称为真值指派。赋值是一组由0、1构成的数串，按顺序对应公式中的命题变元。,若公式A含有n（n1）个命题变元，那么对A共有多少种不同的赋值？,2n,定义：将公式A在所有赋值情况下的取值列成表，称为A的真值表。,例：命题公式(PQ)(PQ)(PQ)的真值表如下：,定义：将公式A在所有赋值情况下的取值列成表，称为A的真值表。,求真值表的步骤：（1）找出命题公式中所含的所有命题变元并按下标或字典顺序给出；（2）遵循由简单到复杂，由括号里面到外面的原则写出公式的各个组成部分。（3）顺序列出所有的赋值（2n个，按二进制数由小到大的顺序）；对应每个赋值，计算命题公式各组成部分的真值

12、，直到最后计算出命题公式的真值。,1）(PQ)(PQ)(PQ)2）(P(QP)R,例：给出下列命题公式的真值表（其中P,Q,R为命题变元）,1）解：,课堂练习,作业：求该命题公式的真值表：(PQ)QR,例：求(PQ)(PQ)(PQ)的真值表练习：(P(QP)R,2、命题公式的真值表,（1）命题是推理的基本要素。命题：有唯一取值的陈述句。命题真值可用1、0表示。,前讲复习：1、前2节小结,把一个用自然语言描述的命题用简单命题和联结词的符号化形式表示出来，称为命题的翻译或命题的符号化。,命题符号化步骤：(1)找出命题中各原子命题，将原子命题符号化。(2)找出命题中各联结词，将联结词符号化。(3)把

13、符号化的原子命题和符号化的联结词联结起来。,命题符号化,例1：72是偶数的充分必要条件为7是偶数。(1)原子命题符号化：P：72 是偶数，Q：7是偶数(2)联结词符号化：(3)命题符号化：P Q,例2：若你走路时看书或坐车时看书,你会近视。,(1)P:你走路时看书；R:你坐车时看书；S:你会近视。(2)（PR）S,命题符号化举例,例3：除非他以书面或口头方式通知我，否则我不参加会议。(1)变换形式理解原句意思“如果他不以书面或口头方式通知我，我不参加会议。”(2)P：他以书面方式通知我；Q：他以口头方式通知我；R：我参加会议。(3)(P Q)R,命题符号化举例,(1)理解原句：“你学好离散数学

14、”是“你学好程序设计”的充分条件。(2)P：你学好离散数学，Q：你学好程序设计。(3)P Q,例4：你只要学好离散数学，就能学好程序设计。,(1)理解原句：“你们学好离散数学”是“你们学好程序设计”的必要条件。(2)P：你们学好离散数学,Q：你们学好程序设计。(3)Q P(或P Q),例5：你们只有学好离散数学,才能学好程序设计,命题符号化举例,命题翻译时应注意以下两个语句的区分：只要P，就Q（P是Q的充分条件）翻译为：PQ（条件命题）只有P，才Q（P是Q的必要条件）翻译为：Q P（倒过来翻译）,1.公式的等价,设A和B是任意两个命题公式，若对A,B的任何一个真值指派，A和B总是取得相同的真值

15、（即A B为重言式），则称命题公式A和B是等价的，记作A B。,两命题公式是否等价，可通过真值表判断，若命题公式A和B的真值表是相同的，则命题公式A和B是等价的。,例：判断A B和(A B)(B A)是否等价。,基本等价式都可通过真值表进行验证。,基本等价公式,在命题逻辑中，经常会使用一些简单的等价式来完成较为复杂的等价式证明（等价演算），称这些简单的等价式为基本等价式或命题定律。（P1基本等值式记牢，非常重要！）,替换规则:设F(A)是含公式A的命题公式，F(B)是用命题公式B置换了F(A)中的A之后得到的命题公式，如果AB，则F(A)F(B)。,例：(PQ)(PR)(PQ)(PR),等价演

16、算,等价演算练习：证明：(P(QR)(PQR)P,证明：(P(QR)(PQR)P(QR)(QR)P(QR)(QR)P1 P,证明：(P(QR)(PQR)P,分配律,德摩根定律,排中律,同一律,等值演算在计算机硬件设计、开关理论和电子元器件中都占据重要地位。,此题若用真值表法证明，需注意Q、R为后一个命题公式的哑元。见P11例,等值演算举例,要求：将下图所示的逻辑电路简化,解：将上述逻辑电路写成命题公式：,或门,与门,等值演算应用举例,所以，该电路可简化为下图：,利用等值式将公式化简为：,等值演算应用举例,永真式：所有赋值均为成真赋值的公式，也称为重言式。永假式：所有赋值均为成假赋值的公式，也称

17、为矛盾式。可满足式：至少有一组赋值是成真赋值的公式。,任何不是矛盾式的公式是可满足式。,例：分别用真值表法和等价演算方法判断下列命题公式的类型,(P(QP)R,永真式！,公式的类型：,判别公式类型的两种方法：真值表法、等价演算,作业：P43 1、3、8,公式的类型,特别注意：和是两个完全不同的符号，具有不同含义。是逻辑联结词，是命题公式的一个部分；不是逻辑联结词，不是命题公式的组成部分，而是用来表示两个命题公式之间的关系。也要注意：=和的区别。,设A、B是公式，则AB等价于A B为永真式。,证明：因为A A是永真式，根据代入规则可得上式也为永真式。,例：证明(PQ)(PR)(PQ)(PR)为永

18、真式。,代入规则,思考,用尽可能多的方法证明：(AB)(CD)(AB)(CD)为永真式。目前学到的真值表的用途：（1）判断两公式是否等价；（2）判断公式的类型。,1.5 公式的蕴涵,设P，Q为两个命题公式，若PQ是永真式，则称命题公式P蕴涵命题公式Q，记作P Q。,和是两个完全不同的符号，具有不同的含义。是逻辑联结词，是命题公式的一个部分；不是逻辑联结词，不是命题公式的组成部分，而是用来表示两个命题公式之间的关系。,证明蕴涵式的三种方法：（都将蕴涵问题转化为求条件命题为永真的问题）真值表法；前件真推证后件真方法；后件假推证前件假方法。,例：推证(PQ)(QR)PR,定理：设P和Q为命题公式，P

19、Q的充要条件是P Q且Q P。,基本蕴涵式见P18,前讲内容复习,公式蕴涵概念基本蕴涵式蕴涵式证明的三种方法 具体题目选择合适的证明方法 例：证明PQ(PR)(QR)几对符号间的区别与联系：与、与=、与,真值表,1、与非联结词（用表示）,1.6 联结词完备集,复合命题“P与Q的否定”称为命题P和Q的与非式复合命题，记作PQ。二元运算符，PQ(PQ)。,真值表,2、或非联结词（用表示）,1.6 联结词完备集,复合命题“P或Q的否定”称为命题P和Q的或非式复合命题，记作PQ。二元运算符，PQ(PQ)。,真值表,3、蕴含的否定联结词“”,复合命题“如果P则Q的否定”称为P和Q蕴含的否定。二元运算符，

20、P Q(PQ)。,c,c,1.6 联结词完备集,复合命题“P或Q有且仅有一个成立”称为命题P和Q的异或式复合命题，记作P Q。二元运算符，P Q(P Q)。,1.6 联结词完备集,真值表,4、异或联结词（用 表示）,注意,设有一个联结词集合S，若由S中联结词构成的命题公式能表示任何命题公式，则称S是联结词完备集。,例：、是一个联结词完备集。,设有一个联结词完备集S，若从S中去掉任一联结词以后就不再是联结词完备集，则称S是极小联结词完备集。,例：、是一个极小联结词完备集。,1.6 联结词完备集,例：仅用 和表示公式(PQ)(PQ),1.7 公式的对偶,在给定仅含有联结词，和的命题公式A中，将联结

21、词换成，换成，1换成0，0换成1，由此得到命题公式A*，称A*为A的对偶式。,在基本等值式的等幂律、交换律和结合律中关于合取和析取的等值式是成对出现的，在数理逻辑中称这种性质为“对偶”。,例：请给出下列命题公式的对偶式。(PQ)(PQ)(1Q),上述命题公式的对偶式为(PQ)(PQ)(0Q),例：求P和P的对偶式，求0和1的对偶式,P的对偶式为P，0的对偶式为1。,对偶式,设A和A*是对偶式，P1,P2,，Pn是出现在A和A*中的所有命题变元，则有：A(P1,P2,Pn)A*(P1,P2,Pn)A(P1,P2,Pn)A*(P1,P2,Pn),注意：(1)式中的是针对所有命题变元的。例：(P(Q

22、R)(PQ1),定理,(P(QR)(PQ0),1.7 公式的对偶,借助对偶原理可以简化和推演一些命题公式，还可以通过已知的等价式来证明其他的等价式，简化证明过程。,例：若已知(PQ)(PQ)PQ 请证明：(PQ)(PQ)PQ,设A*、B*分别为公式A、B的对偶式，若AB，则A*B*。,定理,1.7 公式的对偶,1-7小节内容小结,1、命题、逻辑联结词及其真值表2、命题符号化3、公式等价的证明 基本等价式P13等价演算4、真值表的应用5、蕴含式的证明 基本蕴含式P18推理6、公式对偶7、几对符号间的区别与联系：与、与=、与,1-7小节练习题,一、判断下列语句是否为命题1、仁者无敌！2、x+y23

23、、如果雪是红的，那么地球是月亮的卫星4、这句话是假的。二、将下列命题符号化1、蓝色和黄色可以调成绿色2、付明和杨进都是运动员3、刘易斯是百米游泳冠军或百米跨栏冠军4、李飞现在在宿舍或在图书馆5、只有不下雨，我才不行上学校6、除非下雨，否则我步行上学校,1-7小节练习题,三、将下列命题符号化1、己所不欲，勿施于人。2、并非只要你努力了，就一定成功。3、做自己想做的事，就是快乐。4、李飞现在在宿舍或在图书馆5、只有不下雨，我才不行上学校6、除非下雨，否则我步行上学校四、证明 PQ(PQ),作业P44 第9、11题,1.8 公式的范式,范式给各种各样的公式提供了一个统一的表达形式，从而为我们讨论问题

24、，作机械的符号处理提供了方便。,简单析取式：仅由命题变元或命题变元的否定构成的析取式。,简单合取式：仅由命题变元或命题变元的否定构成的合取式。,例：P，Q，PQ，PQP,例：Q，PQ，PQR,命题变元或命题变元的否定既是简单析取式又是简单合取式。,如：P，P，Q，R,注意,定理：若A是简单合取式，则A是永假式等价于A的合取项中同时有某个命题变元及其否定。,合取范式,析取范式,由有限个简单合取式构成的析取式。,由有限个简单析取式构成的合取式。,例：PQ，(PQR)(PSQ),注意,例：PQ，(PQ)(PQ),命题变元或命题变元的否定既是一析取范式又是一合取范式。简单合取式（简单析取式）既可看作析

25、取范式，又可看作合取范式。例:P,R,PQ,PQ都既是析取范式又是合取范式。,1.8 公式的范式,练习2：求(PQ)(PQ)的合取范式。,练习1：求(PQ)(PQ)的析取范式。,任一命题公式都存在与其等价的析取范式和合取范式。,求析取和合取范式的步骤,(1)利用基本等价式将命题公式中的联结词全部转化为，；(2)利用德摩根定律将命题公式中的否定联结词直接移到命题公式命题变元之前，并取消双重否定；(3)利用分配律将命题公式化为析取范式或合取范式。,例：求(PQ)(PQ)的析取范式。,定理,有时所求析取或合取范式不唯一，但相互等值，即合取范式和析取范式不唯一。,1.8 公式的范式,思考：析取范式或合

26、取范式之间的转换方法。,设A是一个公式，那么（1）A为永假式等价于A的析取范式中每个简单合取式都是永假式（至少包含一个命题变元及其否定）。（2）A为永真式等价于A的合取范式中每个简单析取式都是永真式（至少包含一个命题变元及其否定）。,例：判断(P(PQ)Q的类型。,定理,1.8 公式的范式,可利用求公式的范式的方法判断公式的类型。,小结,1、联结词完备集（了解）2、对偶式（只做2对变换）3、范式（析取范式、合取范式）重点掌握命题公式向“析取范式”或“合取范式”的转换。例：求P(QR)的析取范式和合取范式,作业：P45 17,18,练习：判断哪些是由P,Q,R生成的小项：PQR，PQP，QR,(

27、PQ)P,PQ,小项：设P1,Pn是命题变元,A是包含它们的简单合取式,如果每个命题变元或其否定之中必有一个且仅有一个出现一次,则称A是由P1,Pn生成的小项。例：由P，Q生成的小项有：PQ，PQ，PQ，PQ。,主合取范式和主析取范式是对命题公式的唯一标准化。,1.9 公式的主范式,n个命题变元可组成 个不同的小项。,1.9 公式的主范式,2n,判断一个公式A是否为P1,Pn生成的小项,可通过如下步骤:(1)A是简单合取式;(2)A的合取项恰有n个;(3)A的合取项中没有相同的,也没有互为否定的.这3条中任一条被破坏,则A不是由P1,Pn生成的小项.,由p,q生成的小项的真值表：,我们用mi表

28、示在十进制为i的赋值下真值为1的小项。,强调：小项中命题变元要求按角标顺序或字典顺序排列。,1.9 公式的主范式,主析取范式：与公式A 等值的由若干个小项构成的析取范式。,任一可满足的命题公式的析取范式总是存在的，求主范式只需在求范式的基础上将每个简单合取式化成极小项。,例：求公式PQ的主析取范式。,定理：任何命题公式的主析取范式存在且唯一。,练习：求公式PQ的主析取范式。,1.9 公式的主范式,例：判断有命题变元P,Q的公式中，哪个是主析取范式？(PQ)P，(PQ)(PQ),求主析取范式的方法：1、等价演算方法；2、真值表法。,因为每个小项对应着公式的一个成真赋值，因此只要知道了公式的成真赋

29、值，就可得到其相应的主析取范式。,结论：(1)重言式的主析取范式包含公式的全部2n个极小项。(2)（规定）矛盾式的主析取范式为0。(3)二个等价的公式必有相同的主析取范式。(4)不列真值表，由主析取范式可得公式成真、成假赋值。(5)仅由真值表，可得公式的主析取范式。,练习：求PQ的主析取范式,1.9 公式的主范式,例1：一个命题公式A(P,Q,R)的成真赋值为000,001,010，求其主析取范式。例2：一个命题公式A(P,Q,R)的成假赋值为000,001,100,110，求其主析取范式。例3：不列命题公式的真值表，请求出公式(PQ)P的成真赋值。,主析取范式举例,1.9 公式的主范式,含2

30、个命题变元的公式中，对应p、q的每一组赋值，大项的真值有且仅有一个为0：大项与公式的成假赋值有着一一对应关系，我们用Mi表示在十进制为i的赋值下真值为0的大项。因此，求一个公式的主合取范式，只需知道该公式的成假赋值，并将对应着这个赋值也成假的那些大项合取起来，即得该公式的主合取范式。,例：求公式PQ的主合取范式。,也可用等值演算求主合取范式。,大项：设P1,Pn是命题变元,A是包含它们的简单析取式,如果每个命题变元或其否定之中必有一个且仅有一个出现一次,则称A是由P1,Pn生成的大项。,主合取范式,1.9 公式的主范式,（1）利用主析取范式与主合取范式可以知道命题公式的类型；（根据主范式中小项

31、或大项的个数判断）（2）两个命题公式等价的充要条件是它们的主析取范式或主合取范式相同。,对于任一公式，在它的2n个赋值中，公式的取值非0即1，因此其主析取范式中的极小项和其主合取范式中的极大项的个数之和恰为2n。知道了主析取范式，相应地也就得到了主合取范式，反之亦然。,例：求公式(PQ)P的主析取范式和主合取范式。,1.9 公式的主范式,小结,主析取范式和主合取范式的求法,1、等价演算方法；2、真值表法。,证明两个命题公式等价的第三种方法：,求主范式,作业：P45 19,1.10 命题逻辑推理理论,在传统数学中定理的证明均是由前提（已知条件，全是真命题）推出结论（亦全是真命题），这样的结论称为

32、合法结论。数理逻辑着重研究的是推理过程，这种过程称为演绎或形式证明。在过程中使用的推理规则必须是公认的且要明确列出，而对于作为前提和结论的命题并不一定要求它们全是真命题，这样的结论称为有效结论。,推理是前提结论的思维过程。在命题逻辑中，前提是已知的命题公式，结论是从前提出发应用推理规则推出的命题公式。,1、真值表法2、等值演算法3、主析取范式法,例：推证(PQ)(QR)PR,A B的充要条件是AB为永真式。,目前可证明推理的方法,证明推理的另一方法：构造证明法构造证明法构造证明可以看作公式的序列，其中的每个公式都是按照事先规定的规则得到的，且需将所用的规则在公式后写明，该序列的最后一个公式正是

33、所要证明的结论。,1.10 命题逻辑推理理论,推理规则P规则(前提引入规则)：在证明的任何步骤上，都可以引入前提。T规则(结论引入规则)：在证明的任何步骤上，所得到的结论均可作后续证明的前提加以引用。,1.10 命题逻辑推理理论,直接证明法：由一组已知的前提，利用公认的推理规则，根据基本等价式和基本蕴涵式推导有效结论。,例：PQ，QR，R P,1.10 命题逻辑推理理论,推理过程中，引入前提的两个优先原则：简单前提优先、关系密切的前提优先,归谬证明法（反证法）：把结论的否定作为附加前提与给定的前提一起推证，若能推出矛盾的结果，则说明结论是有效的。,例：证明PQ,(QR)R,(PS)S,1.10

34、 命题逻辑推理理论,CP规则：若有效结论为RC，则可将R加入到前提中作为附加前提，推导结论C即可。,例：证明：RS是PQ，QS，PR的有效结论。,1.10 命题逻辑推理理论,应用举例：判断下列推理是否正确如果今天下雨，要进行C语言或离散数学考试。如果C语言教师出差，则今天不考C语言。今天下雨了，C语言教师出差了，所以今天进行离散数学考试。,第一章 掌握要点,1.掌握命题的概念，五个联结词及其真值表。2、掌握命题公式的组成规则，会判断符号串是否是命题公式。3.会列命题公式的真值表，并会根据真值表列出命题公式的主析取范式与主合取范式。4.证明等价式的方法。5.等价式符号与等价联结词的区别；蕴涵式符

35、号与条件联结词的区别。6.推理的方法。,练 习,1.下列句子中，（）是命题。a.我是教师。b.禁止吸烟！c.蚊子是鸟类动物。d.上课去！e.月亮比地球大。,a,c,e,2.设P：张三可以做这件事，Q：李四可以做这件事。命题“张三或李四可以做这件事”符号化为（）。,PQ,3.设P：现在张三在图书馆，Q：现在张三在宿舍。命题“现在张三在图书馆或在宿舍”符号化为（）。,P Q,3.判断下列符号串是否是命题公式，若是判定命题公式类型。a.PP b.PP c.PQ d.Q(P),是，永真式,是，永假式,是，可满足式,不是,e.(PQ)(PR),练 习,是，永真式,证明P(QP)与P是等值命题公式,2.判

36、断下列哪组命题公式不等值？A.(AB)，AB B.(AB)，(AB)(AB)C.A(BC)，A(BC)D.A(BC)，(AB)C,C,3.下列命题公式,()与P(PQ)不等值。A.P(PQ)B.(P Q)QC.(PQ)Q D.(PQ)Q,D,异或,练 习,练习,1.下列各组公式中，哪组是互为对偶的？(其中p为命题变元，A为含有联结词的命题公式)A.p,p B.p,p C.A,(A*)*D.A,A,A,2.一个命题公式A(P,Q,R)的真值为0的真值指派为001,则其主析取范式为（），其主合取范式为（）,PQR,练习,3.构造下列推理的证明：前提：P Q,P R,QR 结论：R,4.符号化下列命题，并进行推理证明：甲、乙、丙、丁四人参加拳击比赛，若甲获胜，则乙失败；若丙获胜，则乙也获胜；若甲失败，则丁获胜。所以若丙获胜，则丁获胜。,反证法,第一章 小 测 验,1.证明等价式 PQ(PQ)2.求命题公式(R(PQ)(Q(PR)的主析取范式和主合取范式。3.用尽可能多的方法判断命题公式(PQ)(QP)的类型4.证明D是前提AB,BC,C,DA的有效结论。（试着用2种不同的方法证明）,5.证明:(PQ)(RS),(QP)R,R PQ 提示：PQ（PQ）（QP）,