离散数学讲义ppt课件.ppt

1、12离散数学（第三版），耿素云等编著 清华大学出版社，2004年3月（1） 离散数学(第二版)及其配套参考书离散 数学题解作者：屈婉玲，耿素云，张立昂 清华大学出版社（2） 离散数学焦占亚主编 电子工业出版社 2005年1月3选修课/必修课：周学时：上课周：总学时：4第一篇第一篇 数理逻辑（数理逻辑（14学时）学时）第一章 命题逻辑（8）第二章 谓词逻辑（6）第二篇第二篇 集合论（集合论（12学时）学时）第三章 集合（4）第四章 二元关系与函数（8）第四篇第四篇 图论（图论（14学时）学时）第七章 图论（8）第八章 一些特殊图（4）第九章 树 （2）5考核方式：考核方式：闭卷笔试第四篇第四篇

2、代数系统（代数系统（8学时）学时）第5、6章 图论（8）6（1）上课认真听讲）上课认真听讲（2）课后及时复习）课后及时复习（3）独立、认真地完成作业）独立、认真地完成作业（4）有问题及时提出，不要积累问题）有问题及时提出，不要积累问题7 是研究离散对象和它们之间的关系是研究离散对象和它们之间的关系 的现代数学。的现代数学。 它为计算机科学中的数据结构、编它为计算机科学中的数据结构、编 译理论、操作系统、算法分析、人译理论、操作系统、算法分析、人 工智能等提供了必要的数学知识。工智能等提供了必要的数学知识。其内容较广，主要包括数理逻辑、其内容较广，主要包括数理逻辑、 集合集合论、图论、代数结构等

3、四个基本部分。论、图论、代数结构等四个基本部分。8 离散数学将日常的概念、判断、推理用数学符号来表示，用数学方法进行思维。其目标是掌握严密的思维方法、严格证明的推理能力和演算能力，掌握处理各种具有离散结构的事物的描述工具与方法，适应学习其他专业课程的各种需要，为学习其它计算机课程提供必要的数学工具。9本课程将学习数理逻辑、集合论以及图论、代数系统的部分内容。 数理逻辑的重点是公式演 算与推理证明；集合论的重点是关系理论与映射的描述；图论则着重于讨论结点之间的关系以及图论方法的各种实际应用。10第一篇 数理逻辑数理逻辑11数理逻辑是用数学方法来研究推理过程的科学。主要是指引进一套符号体系的方法，

4、因此数理逻辑一般又叫符号逻辑。基本内容是：命题逻辑（演算）和谓词逻辑（演算）。12命题演算是数理逻辑的基本组成部分，是谓词演算的基础。本章包括以下内容：1-1 命题及其表示法1-2 连结词1-3 命题公式及翻译1-4 真值表与等价公式1-5 其它连结词1-6 对偶与范式1-7 重言式与蕴涵式1-8 推理理论1-9 应用13命题：能够判断真假的陈述语句。8例：中国是一个国家，89为素数。原子命题：不能分解成更简单的陈述语句的命题。复合命题：由连结词、标点符号和原子命题复合构成的命题。一般用字母“T”表示“真”，“F”表示“假”。也经常用“1”表示“真”，“0”表示“假”。1-1 命题及其表示法命

5、题及其表示法148习惯上，命题用小写字母p，q，r，或用带下标小写字母表示。例如：命题p：中国人们是伟大的。命题q：别的星球上有生物。命题p1：1+101=102（在十进制或二进制数范围内）。命题P2：今天下雨。命题r：我去看电影。1-1 命题及其表示法命题及其表示法（续）（续）15判断下列句子哪些是命题？ 地球是圆的。 2+3=5 2+3=6 你会讲英语吗？ 3-x=5是命题，真值为T是命题，真值为T是命题，真值为F不是命题（疑问句不是命题）疑问句不是命题）。不是命题，它的真值不确定。1-1 命题及其表示法命题及其表示法（续）（续）16判断下列句子哪些是命题（续）？ 请关上门！ 除地球外的星

6、球 有生物。 太阳明天会出来。不是命题，祈使句不是命题。是命题，它的真值是唯一确定的，只是目前人们不知道是命题，它的真值是唯一确定的，到明天就知道了。再次注意：命题是具有唯一真值的陈述句。1-1 命题及其表示法命题及其表示法（续）（续）17我正在说谎悖论(paradox)是一种矛盾命题。悖论是自相矛盾的命题。即如果承认这个命题成立，就可推出它的否定命题成立；反之，如果承认这个命题的否定命题成立，又可推出这个命题成立。paradox来自希腊语“para+dokein”，意思是“多想一想”。悖论是属于领域广阔、定义严格的数学分支的一个组成部分，这一分支以“趣味数学”知名于世。这就是说它带有强烈的游

7、戏色彩。然而，切莫以为大数学家都看不起“趣味数学”问题。欧拉就是通过对bridge-crossing之谜的分析打下了拓扑学的基础。莱布尼茨也写到过他在独自玩插棍游戏（一种在小方格中插小木条的游戏）时分析问题的乐趣。18希尔伯特证明了切割几何图形中的许多重要定理。冯纽曼奠基了博弈论。最受大众欢迎的计算机游戏生命是英国著名数学家康威发明的。爱因斯坦也收藏了整整一书架关于数学游戏和数学谜的书。古今中外有不少著名的悖论，它们震撼了逻辑和数学的基础，激发了人们求知和精密的思考，吸引了古往今来许多思想家和爱好者的注意力。解决悖论难题需要创造性的思考，悖论的解决又往往可以给人带来全新的观念。19例如比较有名

8、的理发师悖论：某乡村有一位理发师，一天他宣布：只给不自己刮胡子的人刮胡子。这里就产生了问题：理发师给不给自己刮胡子？如果他给自己刮胡子，他就是自己刮胡子的人，按照他的原则，他不能给自己刮胡子；如果他不给自己刮胡子，他就是不自己刮胡子的人，按照他的原则，他就应该给自己刮胡子。这就产生了矛盾历史上著名的悖论NO.1说谎者悖论(1iarparadoxorEpimenidesparadox)最古老的语义悖论。公元前6世纪古希腊哲学家伊壁孟德所创的四个悖论之一。是关于“我正在撒谎”的悖论。具体为：如果他的确正在撒谎，那么这句话是真的，所以伊壁孟德不在撤谎，如果他不在撒谎，那么这句话是假的，因而伊壁孟德正

9、在撒谎。20NO.2伊勒克特拉悖论(Eletraparadox)逻辑史上最早的内涵悖论。由古希腊斯多亚学派提出。它的基本内容是：伊勒克特拉有位哥哥奥列斯特回家了尽管伊勒支持拉知道奥列斯特是她的哥哥但她并不认识站在她面前的这个男人。写成一个推理即：伊勒克持拉不知道站在她面前的这个人是她的哥哥。伊勒克持拉知道奥列期特是她的哥哥。站在她面前的人是奥列期特。所以，伊勒克持拉既知道并且又不知道这个人是她的哥哥。21NO.3M：著名的理发师悖论是伯特纳德罗素提出的。一个理发师的招牌上写着：告示：城里所有不自己刮脸的男人都由我给他们刮脸，我也只给这些人刮脸。M：谁给这位理发师刮脸呢？M：如果他自己刮脸，那他

10、就属于自己刮脸的那类人。但是，他的招牌说明他不给这类人刮脸，因此他不能自己来刮。M：如果另外一个人来给他刮脸，那他就是不自己刮脸的人。但是，他的招牌说他要给所有这类人刮脸。因此其他任何人也不能给他刮脸。看来，没有任何人能给这位理发师刮脸了！22NO.4唐吉诃德悖论M：小说唐吉诃德里描写过一个国家它有一条奇怪的法律：每一个旅游者都要回答一个问题。问，你来这里做什么？M：如果旅游者回答对了。一切都好办。如果回答错了，他就要被绞死。M：一天，有个旅游者回答旅游者：我来这里是要被绞死。M：这时，卫兵也和鳄鱼一样慌了神，如果他们不把这人绞死，他就说错了，就得受绞刑。可是，如果他们绞死他，他就说对了，就不

11、应该绞死他。23下一句话是真的；上一句话是假的。命题常项（常元）：具有唯一真值的命题；命题变项（变元）：泛指任意一个命题或者类似x+y5根据条件不同真值不同的命题。注意：命题变项不是命题，它不具有唯一真值241-2 联结词联结词1、否定设P为一命题，则新命题“P是不对的”称为P的否定。记作： P如：P：2是常数。 P：2不是常数。Q：今天是星期四。 Q：今天不是星期四。 P与 P的真值关系： 10 P0 1 P 251-2 联结词联结词（续）（续）2、合取设P，Q是两命题，新命题“P并且Q”称为命题P，Q的合取。记作：PQ如：P：北京是中国的首都。 Q：北京是一个古都。 PQ：北京是中国的首都

12、并且是一个古都。 0 0 0 0 0 1 0 1 P Q 1 0 1 1 P Q P Q的真值关系：261-2 联结词联结词（续）（续）3、析取设P，Q为两个命题，则新命题“P或者Q”称为命题P，Q的析取。记作：PQ如：P：北京是中国的首都。 Q：北京是一个故都。 PQ：北京是中国的首都或者是一个故都。规定：PQ的真值为1当且仅当P，Q中至少有一个真值为1。 PQ的真值关系： 0 0 0 1 0 1 1 1 P Q 1 0 1 1 P Q271-2 联结词联结词（续）（续）注意：析取联结词与汉语中的“或”的意义不完全相同。 汉语中的“或”既可以表示“排斥或”，也可以表示 “可兼或”。例如：P：

13、今天晚上我在家看电视或去剧场看戏。Q：他可能是100米或400米赛跑的冠军。“排斥或排斥或”“可兼或可兼或”281-2 联结词联结词（续）（续）4、条件设P，Q是两命题，其条件命题是一个复合命题，记做PQ，读做“如果P，则Q”。 1 1 0 1P Q 0 0 0 1 1 0 1 1 P Q真值关系：“善意的推定善意的推定”291-2 联结词联结词（续）（续）5、双条件设P，Q是两命题，其双条件命题是一个复合命题，记做PQ，读做“如果P，则Q”。真值关系： 1 0 0 1 0 0 0 1 1 0 1 1 P QPQ301-2 联结词联结词（续）（续）在命题演算中，五个联结词的含义由真值表唯一确定

14、。 T T F TP Q F F F T T F T T P Q F T T TP Q F F F T T F T T P Q F F F F F T F T P Q T F T T P Q T F PF T P T F F T F F F T T F T T P QPQ311-3 命题公式及其赋值命题公式及其赋值定义：合式公式（1）单个命题变元本身是一个合式公式。（2）如果A是一个合式公式，那么A是合式公式。（3）如果A、B是合式公式，那么（AB）、 （AB）、（AB）、 （AB）都是合式公 式。（4）当且仅当能够有限次地应用上面（1）、（2）、 （3）所得到的包含命题变元、联结词合括号的

15、符号串是合式公式。 递归定义递归定义基础归纳界限321-3 命题公式及其赋值命题公式及其赋值（续）（续）例如：合式公式：(PQ),(PQ)(P(PQ)(PQ)(QR)(ST)非合式公式：(PQ)(Q)(PQ (PQ)Q)括号不匹配括号不匹配应是双目运算符331-3 命题公式及翻译命题公式及翻译联结词的运算优先级：高低 命题公式的层（描述公式的复杂程度）命题公式的赋值（解释、翻译）真值表341-3 命题公式及翻译命题公式及翻译（续）（续）请看教材请看教材Page 10-11。例题例题1：我们要做到身体好、学习好、工作好，为祖 国的四化建设而奋斗。解解 找出原子命题： A：我们要做到身体好。 B：

16、我们要做到学习好。 C：我们要做到工作好。 P；我们要为祖国的四化建设而奋斗。命题的形式化描述： (A B C) P。351-3 命题公式及翻译命题公式及翻译（续）（续）例题例题2：上海到北京的14次列车是下午五点半或六点 开。解解 找出原子命题： P：上海到北京的14次列车是下午五点半开。 Q：上海到北京的14次列车是下午六点开。排斥或： （ PQ）（P Q）PQ原命题P QPQ (PQ)TTFTTFTFTTFTFTTTFTFFFFTF命题的形式化描述：(PQ)。361-3 命题公式及翻译命题公式及翻译（续）（续）例题3： （自学）例题4： （自学）例题5： （自学）例题6： （自学）37习

17、题：习题：* 各章节后习题中的双号大题中的双各章节后习题中的双号大题中的双号小题。号小题。381-4 真值表与等价公式真值表与等价公式定义：定义：在命题公式中，对于分量指派真值的各种可能组合，就确定了这个命题公式的各种真值情况，把它们汇列成表，就是命题公式的真值表。含含n个命题变元的命题公式，共有个命题变元的命题公式，共有2n组赋值。组赋值。例题1：PQ的真值表。PQ P P Q0011011110001101391-4 真值表与等价公式真值表与等价公式（续）（续）例题2：(PQ) P的真值表。PQP Q P(P Q) P00010010101000011100例题3： (PQ) v(PQ)的

18、真值表。PQ P QP Q PQ(P Q)v( PQ)0011011011000010010001100111永假永假公式公式401-4 真值表与等价公式真值表与等价公式（续）（续）例题4：(PQ)(PQ)的真值表。PQP Q (P Q) P Q Pv Q(P Q)( Pv Q)00011111010110111001011111100001永真永真公式公式411-4 真值表与等价公式真值表与等价公式（续）（续）定义：定义：给定两个命题公式A和B，设P1， P2， Pn，为所有出现在A和B中的原子变元。若给P1， P2， Pn任意一组真值指派，A和B的真值都相同，则称A和B是等价（或逻辑相等）

19、，记做AB。 例题5：证明PQ (PQ)(QP) 。PQPQPQQP(PQ) (QP)001111010100100010111111421-4 真值表与等价公式真值表与等价公式（续）（续）两个公式（1） P Q PQPQ P P QPQ00111011111000011011（2） (P Q) ( P Q) PQPQ P QP Q P Q(P Q) ( P Q)PQ00110111011000001001000011001011431-4 真值表与等价公式真值表与等价公式（续）（续）10个命题定律：序号定律表达式1双重否定律P P2幂等律PP PPP P3结合律(P Q) R P (Q R)

20、(P Q) R P (Q R)4交换律P Q Q PP Q Q P5分配律P (Q R) (P Q) (P R)P (Q R) (P Q) (P R)441-4 真值表与等价公式真值表与等价公式（续）（续）10个命题定律：序号定律表达式6吸收律P (P Q) PP (P Q) P7德.摩根律(P Q) P Q(P Q) P Q8同一律P 0 PP 1 P9零律P 1 1P 0 010排中律矛盾律P P 1P P 04511蕴涵等值式A B A B12等价等值式A B (A B) (B A)13假言易位A B B A14等价否定等值式A B A B15归谬论(A B) (A B) A1-4 真值

21、表与等价公式真值表与等价公式（续）（续）461-4 真值表与等价公式真值表与等价公式（续）（续）例题6 验证吸收律：P (P Q) PP (P Q) PPQ(P Q)P (P Q）(P Q)P (P Q)TTTTTTTFFTTTFTFFTFFFTFFF验证：列出真值表471-4 真值表与等价公式真值表与等价公式定义：定义：如果X是合式公式A的一部分，且X本身也是一个合式公式，则称X为公式A的一个子公式。例题7：证明Q (P (P Q) Q P 。证明：证明：由吸收律， (P (P Q) P 因此，根据上面的定理，有Q (P (P Q) Q P 。证毕。证毕。 此定理也称为置换定理此定理也称为置

22、换定理定理：定理：设X是合式公式A的子公式，若X Y，如果将A中的X用Y来置换，则所得到的公式B与公式A等价，即A B。481-4 真值表与等价公式真值表与等价公式例题8 证明：(P Q) (P Q) P 证： (P Q) (P Q) P (Q Q) 分配律 P 1 否定律 P同一律491-4 真值表与等价公式真值表与等价公式例题9 证明：P (Q R) Q (P R) R (Q P)证： P (Q R) P (Q R) 蕴涵等值式 Q (P R) 结合律 Q (P R) 蕴涵等值式（第二个等价公式类似可证。）501-5 其它连结词其它连结词定义：定义：设P和Q是两个命题公式，复合命题P 、Q

23、恰有一个成立称为P与Q的排斥或或异或。 P Q的真值为T，当且仅当P与Q的真值不相同时为T，否则为F。PQP QTTFTFTFTTFFF定理：定理：设P,Q,R为任意命题公式。如果P Q R，则P R Q，Q R P,且P Q R为一矛盾式。511-5 其它连结词其它连结词定义：定义：设P和Q是两个命题公式，复合命题P Q称为P和Q的条件否定， P Q的真值为T，当且仅当P的真值为T，Q的真值为F；否则，P Q的真值为为F。PQP QTTFTFTFTFFFF521-5 其它连结词其它连结词定义：定义：设P和Q是两个命题公式，复合命题PQ称为P和Q的“与非”，当且仅当P和Q的真值都为T时， PQ

24、 的真值为F；否则， PQ的真值为为T。PQPQTTFTFTFTTFFT531-5 其它连结词其它连结词定义：定义：设P和Q是两个命题公式，复合命题PQ称为P和Q的“或非”，当且仅当P和Q的真值都为T时， PQ 的真值为F；否则， PQ的真值为为T。PQPQTTFTFFFTFFFT541-5 其它连结词其它连结词命题公式：12345678PQTFPQ P QP QPQTTTFTTFFTFTFTFTFFTFTFTTFFTTFFTFFTFFFTTFT910111213141516PQP QPQPQP QPQP QQPQ PTTTFTFTFTFTFTFFTFTTFFTTFTFFTFTFFFTTFTF

25、TF551-5 其它连结词其它连结词等价公式：等价公式：1. PQ (PQ) (QP) 2. (PQ) P Q3. P Q ( P Q)，P Q ( P Q)4. P Q (P Q)5. P Q ( PQ)6. PQ (P Q)7. PQ (P Q)最小联结词组：最小联结词组： ， 或或 ， 或或或或56回顾表1-4.8的10个命题定律：序号定律表达式1对合律P P2幂等律PP PPP P3集合律(P Q) R P (Q R)(P Q) R P (Q R)4交换律P Q Q PP Q Q P5分配律P (Q R) (P Q) (P R)P (Q R) (P Q) (P R)1-6 对偶与范式对

26、偶与范式57序号定律表达式6吸收律P (P Q) PP (P Q) P7德.摩根律(P Q) P Q(P Q) P Q8同一律P F PP T P9零律P T TP F F10否定律P P TP P F1-6 对偶与范式（续）对偶与范式（续）回顾表1-4.8的10个命题定律：581-6 对偶与范式（续）对偶与范式（续）定义：定义：在给定的命题中，将联结词换成，将换成，若有特殊变元F和T也相互替代，所得公式A*称为A的对偶式。显然，A*与A互为对偶式。例题1. 例题2. 定理：定理：设A*为A的对偶式，P1,P2,Pn是出现在A和A*中的 原子变元，则 A(P1,P2, Pn) A*(P1,P2

27、, Pn) A(P1,P2, Pn) A*(P1,P2, Pn)591-6 对偶与范式（续）对偶与范式（续）例题例题4：p q 的对偶式是的对偶式是p q ; p q 的对偶式是的对偶式是 p q永真式的对偶式是永假式，反之亦然；永真式的对偶式是永假式，反之亦然；定理：定理：设A*为A的对偶式，P1,P2,Pn是出现在公式A和B中 的原子变元，如果A B，则A* B*。601-6 对偶与范式（续）对偶与范式（续）定义：定义：一个命题称为合取范式合取范式，当且仅当它具有如下的形式：A1A2 An，(n1)其中A1,A2,An都是由命题变元或其否定所组成的析取式。定义：定义：一个命题称为析取范式析

28、取范式，当且仅当它具有如下的形式：A1A2 An，(n1)其中A1,A2,An都是由命题变元或其否定所组成的合取式。注意：一个命题的合取范式或析取范式不是唯一的。注意：一个命题的合取范式或析取范式不是唯一的。611-6 对偶与范式（续）对偶与范式（续）求一个命题的合取范式或析取范式的步骤：求一个命题的合取范式或析取范式的步骤：将公式中的联结词化归成，及。利用德.摩根定律将否定联结词直接移到各命题变元之前。(1)利用分配律、结合律将公式归约为合取范式或析取范式。621-6 对偶与范式（续）对偶与范式（续）定义：定义：n个命题变元的合取式称为布尔合取（或小项），其中每个变元与它的否定不能同时存在，

29、但两者必须出现且仅出现一次。例如：两个变元P和Q，其小项为：PQ，PQ，PQ，PQ。三个变元P，Q，R的小项为：P Q R，P Q R，P Q R，P Q R ，P Q R ，P Q R ，P Q R ，P Q R 。一般说来，n个命题变元共有2n个小项。631-6 对偶与范式（续）对偶与范式（续）两个变元P和Q的小项的真值表：PQPQPQPQPQ111000100100010010000001641-6 对偶与范式（续）对偶与范式（续）三个变元P，Q，R的小项的真值表：P QRP Q RP Q RP Q RP Q R0 0 010000 0 101000 1 000100 1 100011

30、0 000001 0 100001 1 000001 1 10000651-6 对偶与范式（续）对偶与范式（续）三个变元P，Q，R的小项的真值表:P Q R P Q RP Q RP Q RP Q R0 0 000000 0 100000 1 000000 1 100001 0 010001 0 101001 1 000101 1 10001661-6 对偶与范式（续）对偶与范式（续）三个变元P，Q，R的小项的真值表:PQRP Q RP Q RP Q RP Q RP Q RP Q RP Q RP Q R0 0 0100000000 0 1010000000 1 0001000000 1 1000

31、100001 0 0000010001 0 1000001001 1 0000000101 1 100000001671-6 对偶与范式（续）对偶与范式（续）三个变元P，Q，R的小项的编码表:m000 P Q Rm001 P Q Rm010 P Q Rm011 P Q Rm100 P Q Rm101 P Q Rm110 P Q Rm111 P Q R 681-6 对偶与范式（续）对偶与范式（续）小项的性质:（1）每一个小项当其真值指派与编码相同时，其真值为T，在其余2n-1中指派情况下均为F。（2）任意两个不同小项的合取式为永假。（3）全体小项的析取式为永真，记为：2101210.nniimm

32、mmT691-6 对偶与范式（续）对偶与范式（续）定义：定义：对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等式称为原式的主析取范式。定理：定理：在真值表中，一个公式的真值为T的指派所对应的小项的析取，即为此公式的主析取范式。例题例题6：给定P Q，P Q和 (P Q)，求这些公式的主析取范式。例题例题7：例题例题8：例题例题9：701-6 对偶与范式（续）对偶与范式（续） 对于给定命题公式的主析取范式，如果将其对于给定命题公式的主析取范式，如果将其命题变元的个数和出现自许固定后，则此公式的命题变元的个数和出现自许固定后，则此公式的主析取范式就是主析取范式就是唯一唯一的。

33、的。定义：定义：n个命题变元的析取式称为布尔析取布尔析取或或大项大项。其中每个变元与它的否定不能同时存在，但两者必须且仅出现一次。711-6 对偶与范式（续）对偶与范式（续）大项的二进制编码：n=2:M00 P QM01 P QM10 P QM11 P Q721-6 对偶与范式（续）对偶与范式（续）大项的二进制编码：n=3:M000 P Q RM001 P Q RM010 P Q RM011 P Q RM100 P Q RM101 P Q RM110 P Q RM111 P Q R 731-6 对偶与范式（续）对偶与范式（续）大项的性质:（1）每一个大项当其真值指派与编码相同时，其真值为F，在

34、其余2n-1中指派情况下均为T。（2）任意两个不同大项的析取式为永真。（3）全体大项的合取式为永假，记为：2101210.nniimmmmF741-6 对偶与范式（续）对偶与范式（续）定义：定义：对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等式称为原式的主合取范式。定理：定理：在真值表中，一个公式的真值为F的指派所对应的大项的合取，即为此公式的主合取范式。751-6 对偶与范式（续）对偶与范式（续）例题例题10：利用真值表技术求：利用真值表技术求(PQ) (PR)的主析取范式的主析取范式和主合取范式。和主合取范式。解：解：公式(PQ) (PR)的真值表如下：PQRPP

35、QP R(PQ) (PR)TTTFTFTTTFFTFTTFTFFFFTFFFFFFFTTTFTTFTFTFFFFFTTFTTFFFTFFF主和取范式：主和取范式：主析取范式：主析取范式：761-6 对偶与范式（续）对偶与范式（续）PQRP Q RP Q RP Q RP Q RP Q RP Q RP Q RP Q R0 0 0100000000 0 1010000000 1 0001000000 1 1000100001 0 0000010001 0 1000001001 1 0000000101 1 100000001771-6 对偶与范式（续）对偶与范式（续）例题例题11：将：将(PQ) (

36、PR)化为主合取范式。化为主合取范式。781-7 重言式与蕴涵式重言式与蕴涵式定义：定义：给定一个命题，若无论对分量作怎样的指派，其对应的真值永远为T，则称该命题公式为重言式或永真公式。定义：定义：给定一个命题，若无论对分量作怎样的指派，其对应的真值永远为F，则称该命题公式为矛盾式或永假公式。定理：定理：任何两个重言式的合取或析取仍然是一个重言式。定理：定理：一个重言式，对同一分量都用任何公式置换，其结果仍然是一个重言式。定理：定理：设A，B为两个命题公式， A B 当且仅当A B为一个重言式。791-7 重言式与蕴涵式重言式与蕴涵式定义：定义：A、B是命题公式，当A B为一个重言式时，我们称

37、“A蕴涵B”，并且记做A = B 。注：注： P =Q 与 Q = P 是不等价的。 对 P =Q 来说： Q = P称为它的逆换式。 P = Q称为它的反换式。 Q = P称为它的逆反式。P Q Q PQ P P Q逆反命题801-7 重言式与蕴涵式重言式与蕴涵式14个常用蕴涵命题：序号表达式1P P P2P P = P3P = P Q*4P = P Q*5Q = P Q*6(P Q) = P*7(P Q) = Q8P (P Q) = Q9Q (P Q) = P811-7 重言式与蕴涵式重言式与蕴涵式14个常用蕴涵命题（续）：序号表达式10P (P Q) Q11(P Q) (Q R) = P

38、 R12(P Q) (P R) (Q R) = R13(P Q) (R S) = (P R) (Q S)14(P Q) (Q R) = (P R)821-7 重言式与蕴涵式重言式与蕴涵式定理：定理：设P，Q为任意两个命题公式， P Q 的充分必要条件是P =Q 且 Q = P 。性质1. 设A,B为合式公式，若A=B且A是重言式，则B也是 重言式。性质2. 若A=B，B=C，则A=C。性质3. 若A=B且A=C，则A=(B C)。性质4. 若A=B且C=B，则(A C)=B。831-8 推理理论推理理论定义：定义：设A和C是两个命题公式，当且仅当A-C为一个重言式，即A=C，称C是A的有效结论

39、。或C可以由A逻辑地推出。推广：定义：定义：设H1,H2,Hn,C是命题公式，当且仅当 H1 H2 Hn=C称C是一组前提H1,H2,Hn的有效结论。或称C可以由H1,H2,Hn逻辑地推出。判断有效结论的过程叫做论证过程。841-8 推理理论推理理论（续）（续）三种基本论证过程方法：真值表法、直接证法、间接证法。（1）真值表法）真值表法例题1. 一个统计表格的错误或者是由材料不可靠，或者是由于计算有错误。这份统计表格的错误不是由于材料不可靠，所以这统计表格的错误是由于计算有错误。解：设P：统计表格的错误是由于材料不可靠。Q：统计表格的错误是由于计算有错误。前提：P (P Q)结论：QP (P

40、Q)=Q851-8 推理理论推理理论（续）（续）解：解：公式P (P Q)的真值表如下：P QPP QP (P Q)T TFTF FT FFTF FF TTTT TF FTFF F所以有所以有P (P Q)=Q。861-8 推理理论推理理论（续）（续）（2）直接证法）直接证法P规则：前提在推导过程中的任何时候都可以引入使用。T规则：在推导过程中，如果有一个或多个公式重言蕴涵这公式S，则公式S可以引入推导之中。87蕴涵命题蕴涵命题序号表达式I1P P PI2P P = QI3P = P QI4P = P QI5Q = P QI6(P Q) = PI7(P Q) = QI8P (P Q) = QI

41、9Q (P Q) = PI10P (P Q) QI11(P Q) (Q R) = P RI12(P Q) (P R) (Q R) = RI13(P Q) (R S) = (P R) (Q S)I14(P Q) (Q R) = (P R)88等价定律等价定律序号表达式E1P PE2PP P，PP PE3(P Q) R P (Q R)，(P Q) R P (Q R)E4P Q Q P，P Q Q PE5P (Q R) (P Q) (P R)，P (Q R) (P Q) (P R)E6P (P Q) P，P (P Q) PE7(P Q) P Q，(P Q) P QE8P F P，P T PE9P T

42、 T，P F FE10P P T，P P F891-8 推理理论推理理论（续）（续）例题例题1. 证明(PQ)(PR)(QS)=SR证法证法1： （1）PQP规则（2）PQT规则作用于（1），E等价性（3）QSP规则（4）PST规则作用于（2）、（3），I蕴涵关系（5）S PT（4），E（6）P RP（7）S RT（5）、（6），I（8）S RT（7），E901-8 推理理论推理理论（续）（续）证法证法2： （1）P RP规则（2）PQRQT规则作用于（1），I蕴涵关系（3）QSP规则（4）QRSRT规则作用于（3），I蕴涵关系（5）PQSRT(2)、（4），I（6）PQP（7）S RT（5）

43、、（6），I911-8 推理理论推理理论（续）（续）例题例题2. 证明(WR)V,VCS,SU, CU=W（请同学们自学）921-8 推理理论推理理论（续）（续）（3）间接证法）间接证法定义：定义：设H1,H2,Hm是命题公式，其中的命题变元是P1,P2,Pn，对于P1,P2,Pn的某些真值指派，如果能使H1 H2 Hm的真值为T，则称公式H1,H2,Hm 是相容的。如果对于P1,P2,Pn的每一组真值指派都使得H1 H2 Hm的真值为F，则称H1,H2,Hm 是不相容的。不相容的概念用于命题公式的证明：不相容的概念用于命题公式的证明： 要证明H1 H2 Hm =C，只需证明H1,H2,Hm与

44、C是不相容的。931-8 推理理论推理理论（续）（续）例题3. 证明(AB)，(BC)=A证明：（1）A BP规则（2）AP规则（附加前提）（3）(BC)P规则（4）B C T规则作用于（3）（5）BT（1）、（2）,I （6）B T（4）,I （7）B B（矛盾！）T（5）、（6），I941-8 推理理论推理理论（续）（续）例题4. 证明(PQ)(PR)(QS)=S R（请同学们自学）951-8 推理理论推理理论（续）（续）间接证明方法的另外一种情况（CP规则规则）： 若要证明要H1 H2 Hm =（R C）， 设H1 H2 Hm为S，即要证明S=（R C）或证明S=（R C），也即证明S

45、（R C）为永真式。因为S （R C） S （ R C） （S R） C （S R） C （S R） C因此，若将R作为附加前提，如果有（S R）= C，即证明了S=（R C）。961-8 推理理论推理理论（续）（续）例题5. 证明A（BC），DA，B重言式蕴涵DC。证明：（1）DP规则（附加前提）（2）DA P规则（3）AT（1）、（2）,I （4）A（BC） P规则（5）BC T（3）、（4）,I （6）B P（7）CT（5）、（6），I（8）DC CP规则971-8 推理理论推理理论（续）（续）例题6. 设有下列情况，结论是否成立？ (a)或者是晴天。或者是下雨。(b)如果是晴天，我去看

46、电影。(c)如果我去看电影，我就不看书。 我看书了，所以今天下雨（请同学们自学）98 谓词演算(一阶谓词演算）是命题演算的扩充和发展,其本质同命题演算,是把数学中的逻辑论证加以符号化,从而推动了这个数学分支的发展.992-1 谓词的概念与表示2-2 命题函数与量词2-3 谓词公式与翻译2-4 变元的约束2-5 谓词演算的等价式与蕴涵式2-6 前束范式2-7 谓词演算的推理理论100 在命题演算中，基本研究单位是原子命在命题演算中，基本研究单位是原子命题，也就是对原子命题不再分解，对研究命题，也就是对原子命题不再分解，对研究命题间的关系而言是较适合的。题间的关系而言是较适合的。 命题演算的推演中

47、存在很大的局限性，命题演算的推演中存在很大的局限性，有些简单的推断不能用命题演算进行推证。有些简单的推断不能用命题演算进行推证。 例如，例如， 三段论推理。三段论推理。2-1 谓词的概念与表示谓词的概念与表示 谓词演算是对原子命题进行分解，它刻划了谓词演算是对原子命题进行分解，它刻划了命题内部的逻辑结构，从而可以深入研究形式逻命题内部的逻辑结构，从而可以深入研究形式逻辑中的推理问题。辑中的推理问题。101在谓词演算中，将原子命题分解为在谓词演算中，将原子命题分解为谓词谓词 和和个体个体 （客体）（客体）两部分。两部分。个体：可以独立存在的东西,它可以是一个具体的事物，也可以是一个抽象的概念。谓

48、词：用于刻划客体的性质或客体与看客体之间的关系。2-1 谓词的概念与表示谓词的概念与表示（续）（续）1022-1 谓词的概念与表示谓词的概念与表示（续）（续）谓词客体例如：例如： （1 1）李明李明是是三好学生三好学生（客体属性）（客体属性）属性（2 2）5 5大于大于3 3。（客体关系）（客体关系）谓词客体客体103谓词记号：谓词记号：大写字母：表示谓词，如：F、G、H。小写字母：表示客体（个体）如a、b、c。例如：用A表示“是个大学生”，c表示“张三”，d表示“李四”，则：A(c)A(c)：张三：张三是个大学生。是个大学生。A(d)A(d)：李四是个大学生。：李四是个大学生。用B表示“大于

49、”，e代表“5”，f代表“3”，则：B(e,f)B(e,f)：5 5大于大于3 3。2-1 谓词的概念与表示谓词的概念与表示（续）（续）104记号：记号：一元谓词：A(c)。二元谓词：A(c,d)。三元谓词：A(c,d,e)。n元谓词： A(c1,c2,cn)。2-1 谓词的概念与表示谓词的概念与表示（续）（续）一元谓词表达了客体的“性质”，多元谓词表达了客体之间的“关系”。105个体常项：表示具体的或特定的个体，常用a、b、c表示个体变项：表示抽象或泛指的个体词，常用x、y、z表示个体域（论域）：个体变项的取值范围全总个体域：无特别声明时，在此范畴讨论谓词常项：表示具体性质或关系的谓词谓词变

50、项：抽象或泛指的谓词谓词常项、变项根据上下文确定谓词中包含的个体词数n称为元数，相应地n元谓词。如：P（x1,x2,xn）是一个以x1xn的个体域为定义域，以0、1为值域的n元函数注意：n元谓词P不是命题106量词：全称量词和存在量词全称量词(for all)： xF(x)存在量词(exist)： xG(x)举例：书中例子特性谓词使用量词时需注意的地方：见书page40谓词公式（一阶逻辑合式公式）定义量词量词107定义定义1：由一个谓词和一些变元所组成的由一个谓词和一些变元所组成的表表达式称为表表达式称为简单命题函数简单命题函数。由一个或多个简单命题函数以及逻辑联结由一个或多个简单命题函数以及