离散数学讲义

,*,Discrete Mathematics,离散数学讲义,（电子版）,1,课程概况,教材：,离散数学（第三版），耿素云等编著,清华大学出版社，2004年3月,参考书：,（1）,离散数学(第二版)及其配套参考书离散,数学题解作者：屈婉玲，耿素云，张立昂,清华大学出版社,（2） 离散数学焦占亚主编 电子工业出版社,2005年1月,2,课程概况,选修课/必修课：,选修,周学时：,3（学时）,上课周：,116周,总学时：,48（学时）,3,课程内容及学时安排,第一篇 数理逻辑（14学时）,第一章 命题逻辑（8）,第二章 谓词逻辑（6）,第二篇 集合论（12学时）,第三章 集合（4）,第四章 二元关系与函数（8）,第四篇 图论（14学时）,第七章 图论（8）,第八章 一些特殊图（4）,第九章 树 （2）,4,课程考核,考核方式：,闭卷笔试,第四篇 代数系统（8学时）,第5、6章 图论（8）,5,课程要求,（1）上课认真听讲,（2）课后及时复习,（3）独立、认真地完成作业,（4）有问题及时提出，不要积累问题,6,什么是离散数学？,是研究离散对象和它们之间的关系 的现代数学。,它为计算机科学中的数据结构、编,译理论、操作系统、算法分析、人,工智能等提供了必要的数学知识。,其内容较广，主要包括数理逻辑、 集合论、图论、代数结构等四个基本部分。,7,什么是离散数学？,离散数学,将日常的概念、判断、推理用数学符号来表示，用数学方法进行思维。其,目标是掌握严密的思维方法、严格证明的推理能力和演算能力，掌握处理各种具有离散结构的事物的描述工具与方法，适应学习其他专业课程的各种需要，为学习其它计算机课程提供必要的数学工具。,8,什么是离散数学？,本课程将学习,数理逻辑,、,集合论,以及,图论、代数系统,的部分内容,。,数理逻辑的重点是公式演 算与推理证明；集合论的重点是关系理论与映射的描述；图论则着重于讨论结点之间的关系以及图论方法的各种实际应用。,9,课程内容,第一篇,数理逻辑,10,第一篇 数理逻辑,数理逻辑是用数学方法来研究推理过程的科学。主要是指引进一套,符号体系,的方法，因此数理逻辑一般又叫符号逻辑。,基本内容是：命题逻辑（演算）和谓词逻辑（演算）。,11,第一章 命题逻辑,命题演算是数理逻辑的基本组成部分，是谓词演算的基础。,本章包括以下内容：,1-1,命题及其表示法,1-2,连结词,1-3,命题公式及翻译,1-4,真值表与等价公式,1-5,其它连结词,1-6,对偶与范式,1-7,重言式与蕴涵式,1-8,推理理论,1-9,应用,12,命题：,能够判断真假的陈述语句。,例：中国是一个国家，,9,为素数。,原子命题：,不能分解成更简单的陈述语句的命题。,复合命题：,由连结词、标点符号和原子命题复合构成的命题。,一般,用字母“,T”,表示“真”,，“,F”,表示,“假”。也经常用“,1”表示“真”，“0”表示“假”。,1-1 命题及其表示法,13,习惯上，命题用小写字母,p，q，r，,或用带下标,小,写字母表示。,例如：,命题,p：,中国人们是伟大的。,命题,q：,别的星球上有生物。,命题,p,1,：1+101=102（,在十进制或二进制数范围内）。,命题,P,2,：,今天下雨。,命题,r：,我去看电影。,1-1 命题及其表示法,（续）,14,判断下列句子哪些是命题？,地球是圆的。,2+3=5,2+3=6,你会讲英语吗？,3-x=5,是命题，真值为T,是命题，真值为T,是命题，真值为F,不是命题,（,疑问句不是命题）,。,不是命题，它的真值不确定。,1-1 命题及其表示法,（续）,15,判断下列句子哪些是命题（续）？,请关上门！,除地球外的星球,有生物。,太阳明天会出来。,不是命题，,祈使句不是命题。,是命题，它的真值是唯一确定的，只是目前人们不知道,是命题，它的真值是唯一确定的，到明天就知道了。,再次注意：,命题是具有,唯一真值,的,陈述句,。,1-1 命题及其表示法,（续）,16,我正在说谎,悖论(paradox),是一种矛盾命题。,悖论是,自相矛盾,的,命题,。即如果承认这个命题成立，就可推出它的否定命题成立；反之，如果承认这个命题的否定命题成立，又可推出这个命题成立,。,paradox来自,希腊,语“,para+dokein,”，意思是“多想一想”。,悖论是属于领域广阔、定义严格的数学分支的一个组成部分，这一分支以“趣味数学”知名于世。这就是说它带有强烈的游戏色彩。然而，切莫以为大数学家都看不起“趣味数学”问题。欧拉就是通过对bridge-crossing之谜的分析打下了拓扑学的基础。莱布尼茨也写到过他在独自玩插棍游戏（一种在小方格中插小木条的游戏）时分析问题的乐趣。,17,希尔伯特证明了切割几何图形中的许多重要定理。冯纽曼奠基了博弈论。最受大众欢迎的计算机游戏生命是英国著名数学家康威发明的。爱因斯坦也收藏了整整一书架关于数学游戏和数学谜的书。,古今中外有不少著名的悖论，它们震撼了,逻辑,和数学的基础，激发了人们求知和精密的思考，吸引了古往今来许多思想家和爱好者的注意力。解决悖论难题需要创造性的思考，悖论的解决又往往可以给人带来全新的观念。,18,例如比较有名的,理发师悖论,：某乡村有一位,理发师,，一天他宣布：只给不自己刮胡子的人刮胡子。这里就产生了问题：理发师给不给自己刮胡子？如果他给自己刮胡子，他就是自己刮胡子的人，按照他的原则，他不能给自己刮胡子；如果他不给自己刮胡子，他就是不自己刮胡子的人，按照他的原则，他就应该给自己刮胡子。这就产生了矛盾,历史上著名的悖论NO.1 说谎者悖论(1iar paradox or Epimenides paradox) 最古老的语义悖论。公元前6世纪古希腊,哲学家,伊壁孟德 所创的四个悖论之一。是关于“我正在撒谎”的悖论。具体为：如果他的确正在撒谎，那么这句话是真的，所以伊壁孟德不在撤谎，如果他不在撒谎，那么这句话是假的，因而伊壁孟德正在撒谎。,19,NO.2 伊勒克特拉悖论(Eletra paradox) 逻辑史上最早的内涵悖论。由古希腊斯多亚学派提出。它的基本内容是：伊勒克特拉有位哥哥奥列斯特回家了尽管伊勒支持拉知道奥列斯特是她的哥哥但她并不认识站在她面前的这个男人。 写成一个推理即： 伊勒克持拉不知道站在她面前的这个人是她的哥哥。 伊勒克持拉知道奥列期特是她的哥哥。 站在她面前的人是奥列期特。 所以，伊勒克持拉既知道并且又不知道这个人是她的 哥哥。,20,NO.3 M：著名的理发师悖论是伯特纳德罗素提出的。一个理发师的招牌上写着： 告示：城里所有不自己刮脸的男人都由我给他们刮脸，我也只给这些人刮脸。 M：谁给这位理发师刮脸呢？ M：如果他自己刮脸，那他就属于自己刮脸的那类人。但是，他的招牌说明他不给这类人刮脸，因此他不能自己来刮。 M：如果另外一个人来给他刮脸，那他就是不自己刮脸的人。但是，他的招牌说他要给所有这类人刮脸。因此其他任何人也不能给他刮脸。看来，没有任何人能给这位理发师刮脸了！,21,NO.4,唐吉诃德,悖论 M：小说唐吉诃德里描写过一个国家它有一条奇怪的法律：每一个旅游者都要回答一个问题。 问，你来这里做什么？ M：如果旅游者回答对了。一切都好办。如果回答错了，他就要被绞死。 M：一天，有个旅游者回答 旅游者：我来这里是要被绞死。 M：这时，卫兵也和鳄鱼一样慌了神，如果他们不把这人绞死，他就说错了，就得受绞刑。可是，如果他们绞死他，他就说对了，就不应该绞死他。,22,下一句话是真的；,上一句话是假的。,命题常项（常元）：具有唯一真值的命题；,命题变项（变元）：泛指任意一个命题或者类似x+y5根据条件不同真值不同的命题。,注意：命题变项不是命题，它不具有唯一真值,23,1-2 联结词,1、否定,设P为一命题，则新命题“P是不对的”称为P的否定。,记作：,P,如：P：2是常数。,P：2不是常数。,Q：今天是星期四。,Q：今天不是星期四。,P与,P的真值关系：,1,0,P,0,1,P,24,1-2 联结词,（续）,2、合取,设P，Q是两命题，新命题“P并且Q”称为命题P，Q的合取。,记作：PQ,如：P：北京是中国的首都。 Q：北京是一个古都。,PQ：北京是中国的首都并且是一个古都。,0,0 0,0,0 1,0,1,P,Q,1 0,1 1,P Q,P,Q的真值关系：,25,1-2 联结词,（续）,3、析取,设P，Q为两个命题，则新命题“P或者Q”称为命题P，Q的析取。,记作：PQ,如：P：北京是中国的首都。 Q：北京是一个故都。,PQ：北京是中国的首都或者是一个故都。,规定：PQ的真值为1当且仅当P，Q中至少有一个真值为1。,P,Q的真值关系：,0,0 0,1,0 1,1,1,P,Q,1 0,1 1,P Q,26,1-2 联结词,（续）,注意：析取联结词,与汉语中的“或”的意义不完全相同。,汉语中的“或”既可以表示“排斥或”，也可以表示,“可兼或”。,例如：,P：今天晚上我在家看电视或去剧场看戏。,Q：他可能是100米或400米赛跑的冠军。,“排斥或”,“可兼或”,27,1-2 联结词,（续）,4、条件,设P，Q是两命题，其条件命题是一个复合命题，记做P,Q，读做“如果P，则Q”。,1,1,0,1,P,Q,0 0,0 1,1 0,1 1,P Q,真值关系：,“善意的推定”,28,1-2 联结词,（续）,5、双条件,设P，Q是两命题，其双条件命题是一个复合命题，,记做P,Q，读做“如果P，则Q”。,真值关系：,1,0,0,1,0 0,0 1,1 0,1 1,P Q,P,Q,29,1-2 联结词,（续）,在命题演算中，五个联结词的含义由真值表唯一确定。,T,T,F,T,P,Q,F F,F T,T F,T T,P Q,F,T,T,T,P,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,P,F,T,P,T,F,F,T,F F,F T,T F,T T,P Q,P,Q,30,1-3 命题公式及其赋值,定义：合式公式,（,1,）单个命题变元本身是一个合式公式。,（,2,）如果,A,是一个合式公式，那么,A,是合式公式。,（,3,）如果,A、B,是合式公式，那么（,A,B）、,（A,B）、（A,B）、 （A,B,）,都,是合式公,式。,（,4,）当且仅当能够有限次地应用上面,（,1,）、（,2,）、,（,3,）,所得到的包含命题变元、联结词合括号的 符号串是合式公式。,递归定义,基础,归纳,界限,31,1-3 命题公式及其赋值,（续）,例如：,合式公式：,(,PQ),(PQ),(P(PQ),(PQ)(QR)(ST),非合式公式：,(,PQ)(,Q,),(PQ,(PQ)Q),括号不匹配,括号不匹配,应,是双目运算符,32,1-3 命题公式及翻译,联结词的运算优先级：,高,低, ,命题公式的层（描述公式的复杂程度）,命题公式的赋值（解释、翻译）,真值表,33,1-3 命题公式及翻译,（续）,请看教材,Page 10-11,。,例题,1：,我们要做到身体好、学习好、工作好，为祖,国的四化建设而奋斗。,解,找出原子命题：,A：我们要做到身体好。,B：我们要做到学习好。,C：我们要做到工作好。,P；我们要为祖国的四化建设而奋斗。,命题的形式化描述：,(A,B,C),P。,34,1-3 命题公式及翻译,（续）,例题,2：,上海到北京的14次列车是下午五点半或六点,开。,解,找出原子命题：,P：上海到北京的14次列车是下午五点半开。,Q：上海到北京的14次列车是下午六点开。,排斥或：,（,PQ）（P Q）,P,Q,原命题,P,Q,P,Q,(P,Q),T,T,F,T,T,F,T,F,T,T,F,T,F,T,T,T,F,T,F,F,F,F,T,F,命题的形式化描述：,(P,Q),。,35,1-3 命题公式及翻译,（续）,例题3： （自学）,例题4： （自学）,例题5： （自学）,例题6： （自学）,36,习题：,*各章节后习题中的双号大题中的双,号小题。,37,1-4 真值表与等价公式,定义：,在命题公式中，对于分量指派真值的各种可能组合，就确定了这个命题公式的各种真值情况，把它们汇列成表，就是命题公式的真值表。,含,n,个命题变元的命题公式，共有,2,n,组赋值。,例题1：,PQ的真值表,。,P,Q,P,PQ,0,0,1,1,0,1,1,1,1,0,0,0,1,1,0,1,38,1-4 真值表与等价公式,（续）,例题2：(P,Q) P的真值表。,P,Q,P,Q,P,(P,Q) P,0,0,0,1,0,0,1,0,1,0,1,0,0,0,0,1,1,1,0,0,例题3： (P,Q) v(PQ)的真值表。,P,Q,P,Q,P,Q,P,Q,(P,Q)v(PQ),0,0,1,1,0,1,1,0,1,1,0,0,0,0,1,0,0,1,0,0,0,1,1,0,0,1,1,1,永假公式,39,1-4 真值表与等价公式,（续）,例题4：,(,P,Q),(PQ)的真值表。,P,Q,P,Q,(P,Q),P,Q,P,vQ,(P,Q)(PvQ),0,0,0,1,1,1,1,1,0,1,0,1,1,0,1,1,1,0,0,1,0,1,1,1,1,1,1,0,0,0,0,1,永真公式,40,1-4 真值表与等价公式,（续）,定义：,给定两个命题公式A和B，设P,1,，,P,2,，,P,n,，为所有出现在A和B中的原子变元。若给,P,1,，,P,2,，,P,n,任意一组真值指派，A和B的真值都相同，则称A和B是等价（或逻辑相等），记做A,B。,例题5：证明P,Q,(P,Q)(Q,P) 。,P,Q,P,Q,P,Q,QP,(P,Q)(QP),0,0,1,1,1,1,0,1,0,1,0,0,1,0,0,0,1,0,1,1,1,1,1,1,41,1-4 真值表与等价公式,（续）,两个公式,（1）,P, Q,P,Q,P,Q,P,P,Q,PQ,0,0,1,1,1,0,1,1,1,1,1,0,0,0,0,1,1,0,1,1,（2） (P,Q),(,P,Q),P,Q,P,Q,P,Q,P,Q,P,Q,(P,Q),(,P,Q),P,Q,0,0,1,1,0,1,1,1,0,1,1,0,0,0,0,0,1,0,0,1,0,0,0,0,1,1,0,0,1,0,1,1,42,1-4 真值表与等价公式,（续）,10个命题定律：,序号,定律,表达式,1,双重否定律,P,P,2,幂等律,P,P,P,P,P,P,3,结合律,(P,Q),R,P,(Q,R),(P,Q),R,P,(Q,R),4,交换律,P,Q, Q P,P,Q, Q P,5,分配律,P,(Q,R),(P,Q),(P,R),P,(Q,R),(P,Q),(P,R),43,1-4 真值表与等价公式,（续）,10个命题定律：,序号,定律,表达式,6,吸收律,P,(P,Q),P,P,(P,Q),P,7,德.摩根律,(P,Q),P,Q,(P,Q),P,Q,8,同一律,P,0,P,P,1,P,9,零律,P,1,1,P,0,0,10,排中律,矛盾律,P,P,1,P,P,0,44,11,蕴涵等值式,A,B,A,B,12,等价等值式,A,B,(A,B),(B,A),13,假言易位,A,B B A,14,等价否定等值式,A,B,A,B,15,归谬论,(A,B),(A, ,B),A,1-4 真值表与等价公式,（续）,45,1-4 真值表与等价公式,（续）,例题6 验证吸收律：,P,(P,Q),P,P,(P,Q),P,P,Q,(P,Q),P,(P,Q）,(P,Q),P,(P,Q),T,T,T,T,T,T,T,F,F,T,T,T,F,T,F,F,T,F,F,F,T,F,F,F,验证：列出真值表,46,1-4 真值表与等价公式,定义：,如果,X,是合式公式,A,的一部分，且,X,本身也是一个合式公式，则称,X,为公式,A,的一个子公式。,例题7：,证明Q,(P,(P,Q) Q,P,。,证明：,由吸收律， (P,(P,Q) P,因此，根据上面的定理，有,Q,(P,(P,Q) Q,P,。,证毕。 此定理也称为置换定理,定理：,设,X,是合式公式,A,的子公式，若,X,Y，,如果将,A,中的,X,用,Y,来置换，则所得到的公式,B,与公式,A,等价，即,A,B。,47,1-4 真值表与等价公式,例题8 证明：(P,Q),(P,Q),P,证： (P,Q),(P,Q),P, (,Q, ,Q),分配律,P, 1,否定律,P,同一律,48,1-4 真值表与等价公式,例题9 证明：P, (,Q, R,),Q, (P, R,),R, (Q, P,),证： P, (,Q, R,),P,(,Q, R,) 蕴涵等值式, ,Q,(,P, R,) 结合律,Q, (P, R,) 蕴涵等值式,（第二个等价公式类似可证。）,49,1-5 其它连结词,定义：,设,P,和,Q,是两个命题公式，复合命题,P 、Q,恰有一个成立称为,P,与,Q,的排斥或或异或。,P Q,的真值为,T，,当且仅当,P,与,Q,的真值不相同时为,T，,否则为,F。,P,Q,P Q,T,T,F,T,F,T,F,T,T,F,F,F,定理：,设,P,Q,R,为任意命题公式。如果,P Q,R，,则,P R,Q，Q R,P,且,P Q R,为一矛盾式。,50,1-5 其它连结词,定义：,设,P,和,Q,是两个命题公式，复合命题,P Q,称为,P,和,Q,的条件否定，,P Q,的真值为,T，,当且仅当,P,的真值为,T，Q,的真值为,F；,否则，,P Q,的真值为为,F。,P,Q,P Q,T,T,F,T,F,T,F,T,F,F,F,F,51,1-5 其它连结词,定义：,设,P,和,Q,是两个命题公式，复合命题,PQ,称为,P,和,Q,的“与非”，当且仅当,P,和,Q,的真值都为,T,时，,PQ,的真值为,F；,否则，,PQ,的真值为为,T。,P,Q,PQ,T,T,F,T,F,T,F,T,T,F,F,T,52,1-5 其它连结词,定义：,设,P,和,Q,是两个命题公式，复合命题,PQ,称为,P,和,Q,的“或非”，当且仅当,P,和,Q,的真值都为,T,时，,PQ,的真值为,F；,否则，,PQ,的真值为为,T。,P,Q,PQ,T,T,F,T,F,F,F,T,F,F,F,T,53,1-5 其它连结词,命题公式：,1,2,3,4,5,6,7,8,P,Q,T,F,P,Q,P,Q,P,Q,PQ,T,T,T,F,T,T,F,F,T,F,T,F,T,F,T,F,F,T,F,T,F,T,T,F,F,T,T,F,F,T,F,F,T,F,F,F,T,T,F,T,9,10,11,12,13,14,15,16,P,Q,P,Q,PQ,P,Q,P,Q,P,Q,P Q,Q,P,Q P,T,T,T,F,T,F,T,F,T,F,T,F,T,F,F,T,F,T,T,F,F,T,T,F,T,F,F,T,F,T,F,F,F,T,T,F,T,F,T,F,54,1-5 其它连结词,等价公式：,1.,P,Q, (,P,Q) (,Q,P,),2.,(,P,Q) ,P, Q,3.,P, Q (,P, ,Q)，P, Q (,P, ,Q),4. P Q, (,P,Q),5. P,Q,(,P,Q),6. PQ, (,P,Q,),7. PQ, (,P,Q,),最小联结词组：,，,或,，,或或,55,回顾表1-4.8的10个命题定律：,序号,定律,表达式,1,对合律,P,P,2,幂等律,P,P,P,P,P,P,3,集合律,(P,Q),R,P,(Q,R),(P,Q),R,P,(Q,R),4,交换律,P,Q, Q P,P,Q, Q P,5,分配律,P,(Q,R),(P,Q),(P,R),P,(Q,R),(P,Q),(P,R),1-6 对偶与范式,56,序号,定律,表达式,6,吸收律,P,(P,Q),P,P,(P,Q),P,7,德.摩根律,(P,Q),P,Q,(P,Q),P,Q,8,同一律,P,F,P,P,T,P,9,零律,P,T,T,P,F,F,10,否定律,P,P,T,P,P,F,1-6 对偶与范式（续）,回顾表1-4.8的10个命题定律：,57,1-6 对偶与范式（续）,定义：,在给定的命题中，将联结词,换成，将换成，若有特殊变元,F,和,T,也相互替代，所得公式,A*,称为,A,的对偶式。,显然，,A*,与,A,互为对偶式。,例题,1.,例题,2.,定理：,设,A*为A的对偶式,，P,1,P,2,P,n,是出现在A和A*中的,原子变元，则,A(P,1,P,2, P,n,),A*(,P,1,P,2,P,n,),A(,P,1,P,2,P,n,),A*(P,1,P,2, P,n,),58,1-6 对偶与范式（续）,例题,4：,p,q,的对偶式是,p,q ; p,q,的对偶式是,p,q,永真式的对偶式是永假式，反之亦然；,定理：,设,A*为A的对偶式,，P,1,P,2,P,n,是出现在公式A和B中,的原子变元，如果A,B，则A*,B*。,59,1-6 对偶与范式（续）,定义：,一个命题称为,合取范式,，当且仅当它具有如下的形式：,A,1,A,2,A,n,，(n1),其中A,1,A,2,A,n,都是由命题变元或其否定所组成的析取式。,定义：,一个命题称为,析取范式,，当且仅当它具有如下的形式：,A,1,A,2,A,n,，(n1),其中A,1,A,2,A,n,都是由命题变元或其否定所组成的合取式。,注意：一个命题的合取范式或析取范式不是唯一的。,60,1-6 对偶与范式（续）,求一个命题的合取范式或析取范式的步骤：,将公式中的联结词化归成,，,及,。,利用德,.,摩根定律将否定联结词,直接移到各命题变元之前。,利用分配律、结合律将公式归约为合取范式或析取范式。,61,1-6 对偶与范式（续）,定义：,n个命题变元的合取式称为,布尔合取,（或,小项,），其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。,例如：两个变元P和Q，其小项为：P,Q，P,Q，,P,Q，,P,Q。,三个变元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个命题变元共有2,n,个小项。,62,1-6 对偶与范式（续）,两个变元P和Q的小项的真值表：,P,Q,P,Q,P,Q,P,Q,P,Q,1,1,1,0,0,0,1,0,0,1,0,0,0,1,0,0,1,0,0,0,0,0,0,1,63,1-6 对偶与范式（续）,三个变元P，Q，R的小项的真值表：,P,Q,R,P,Q,R,P,Q,R,P,Q,R,P,Q,R,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,1,1,0,0,0,1,1,0,0,0,0,0,0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,1,1,1,0,0,0,0,64,1-6 对偶与范式（续）,三个变元P，Q，R的小项的真值表:,P,Q,R,P,Q,R,P,Q,R,P,Q,R,P,Q,R,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,1,0,0,1,0,0,0,1,0,1,0,1,0,0,1,1,0,0,0,1,0,1,1,1,0,0,0,1,65,1-6 对偶与范式（续）,三个变元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,P,Q,R,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,1,1,0,0,0,0,0,0,0,1,0,1,1,1,0,0,0,0,0,0,0,1,66,1-6 对偶与范式（续）,三个变元P，Q，R的小项的编码表:,m,000,P,Q,R,m,001,P,Q,R,m,010,P,Q,R,m,011,P,Q,R,m,100, P,Q,R,m,101, P, ,Q,R,m,110, P,Q,R,m,111, P,Q,R,67,1-6 对偶与范式（续）,小项的性质:,（1）每一个小项当其真值指派与编码相同时，其真值为T，在其余2,n,-1中指派情况下均为F。,（2）任意两个不同小项的合取式为永假。,（3）全体小项的析取式为永真，记为：,68,1-6 对偶与范式（续）,定义：,对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等式称为原式的主析取范式。,定理：,在真值表中，一个公式的真值为T的指派所对应的小项的析取，即为此公式的主析取范式。,例题6：,给定P,Q，P,Q和,(P,Q)，求这些公式的主析取范式。,例题7：,例题8：,例题9：,69,1-6 对偶与范式（续）,对于给定命题公式的主析取范式，如果将其命题变元的个数和出现自许固定后，则此公式的主析取范式就是,唯一,的。,定义：,n个命题变元的析取式称为,布尔析取,或,大项,。其中每个变元与它的否定不能同时存在，但两者必须且仅出现一次。,70,1-6 对偶与范式（续）,大项的二进制编码：,n=2:,M,00, P,Q,M,01, P,Q,M,10,P,Q,M,11,P,Q,71,1-6 对偶与范式（续）,大项的二进制编码：,n=3:,M,000, P,Q,R,M,001, P,Q,R,M,010, P,Q,R,M,011, P,Q,R,M,100,P,Q,R,M,101,P,Q,R,M,110,P,Q,R,M,111,P,Q,R,72,1-6 对偶与范式（续）,大项的性质:,（1）每一个大项当其真值指派与编码相同时，其真值为F，在其余2,n,-1中指派情况下均为T。,（2）任意两个不同大项的析取式为永真。,（3）全体大项的合取式为永假，记为：,73,1-6 对偶与范式（续）,定义：,对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等式称为原式的主合取范式。,定理：,在真值表中，一个公式的真值为F的指派所对应的大项的合取，即为此公式的主合取范式。,74,1-6 对偶与范式（续）,例题10：利用真值表技术求,(P,Q),(,P,R),的主析取范式和主合取范式。,解：,公式(P,Q),(,P,R)的真值表如下：,P,Q,R,P,P,Q,P,R,(P,Q),(,P,R),T,T,T,F,T,F,T,T,T,F,F,T,F,T,T,F,T,F,F,F,F,T,F,F,F,F,F,F,F,T,T,T,F,T,T,F,T,F,T,F,F,F,F,F,T,T,F,T,T,F,F,F,T,F,F,F,主和取范式：,主析取范式：,75,1-6 对偶与范式（续）,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,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,1,1,0,0,0,0,0,0,0,1,0,1,1,1,0,0,0,0,0,0,0,1,76,1-6 对偶与范式（续）,例题11：将,(P,Q),(,P,R),化为主合取范式。,77,1-7 重言式与蕴涵式,定义：,给定一个命题，若无论对分量作怎样的指派，其对应的真值永远为,T，,则称该命题公式为重言式或永真公式。,定义：,给定一个命题，若无论对分量作怎样的指派，其对应的真值永远为,F，,则称该命题公式为矛盾式或永假公式。,定理：,任何两个重言式的合取或析取仍然是一个重言式。,定理：,一个重言式，对同一分量都用任何公式置换，其结果仍然是一个重言式。,定理：,设,A，B,为两个命题公式，,A,B,当且仅当,A,B,为一个重言式。,78,1-7 重言式与蕴涵式,定义：,A、B,是,命题公式，当,A,B,为一个重言式时，我们称“,A,蕴涵,B”，,并且记做,A,=,B 。,注：,P =Q,与,Q,=,P,是不等价的。,对,P =Q,来说：,Q,=,P,称为它的,逆换式,。,P,=,Q,称为它的,反换式,。,Q,=,P,称为它的,逆反式,。,P,Q, ,Q,P,Q,P, P,Q,逆反命题,79,1-7 重言式与蕴涵式,14个常用蕴涵命题：,序号,表达式,1,P,P,P,2,P,P = P,3,P = P,Q,*4,P = P,Q,*5,Q,= P,Q,*6,(,P,Q) = P,*7,(,P,Q) =,Q,8,P,(,P,Q) = Q,9,Q ,(,P,Q) =,P,80,1-7 重言式与蕴涵式,14个常用蕴涵命题（续）：,序号,表达式,10,P,(P, Q),Q,11,(P,Q),(Q,R) = P,R,12,(P,Q),(P,R),(Q,R) = R,13,(P,Q),(R,S) = (P,R),(Q,S),14,(P,Q),(Q,R) = (P,R),81,1-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。,82,1-8 推理理论,定义：,设A和C是两个命题公式，当且仅当A-C为一个重言式，即A=C，称C是A的有效结论。或C可以由A逻辑地推出。,推广：,定义：,设H,1,H,2,H,n,C是命题公式，当且仅当,H,1,H,2,H,n,=C,称C是一组前提H,1,H,2,H,n,的有效结论。或称C可以由H,1,H,2,H,n,逻辑地推出。,判断有效结论的过程叫做,论证过程,。,83,1-8 推理理论,（续）,三种基本论证过程方法：,真值表法、直接证法、间接证法。,（1）真值表法,例题1. 一个统计表格的错误或者是由材料不可靠，或者是由于计算有错误。这份统计表格的错误不是由于材料不可靠，所以这统计表格的错误是由于计算有错误。,解：设,P：统计表格的错误是由于材料不可靠。,Q：统计表格的错误是由于计算有错误。,前提：,P,(,P,Q,),结论：Q,P,(,P,Q,)=Q,84,1-8 推理理论,（续）,解：,公式,P,(,P,Q,),的真值表如下：,P,Q,P,P,Q,P,(,P,Q,),T,T,F,T,F,T,F,F,T,F,F,T,T,T,T,F,F,T,F,F,所以有,P,(,P,Q,)=Q。,85,1-8 推理理论,（续）,（2）直接证法,P规则：前提在推导过程中的任何时候都可以引入使用。,T规则：在推导过程中，如果有一个或多个公式重言蕴涵这公式S，则公式S可以引入推导之中。,86,蕴涵命题,序号,表达式,I1,P,P,P,I2,P,P = Q,I3,P = P,Q,I4,P = P,Q,I5,Q,= P,Q,I6,(,P,Q) = P,I7,(,P,Q) =,Q,I8,P,(,P,Q) = Q,I9,Q ,(,P,Q) =,P,I10,P,(P, Q),Q,I11,(P,Q),(Q,R) = P,R,I12,(P,Q),(P,R),(Q,R) = R,I13,(P,Q),(R,S) = (P,R),(Q,S),I14,(P,Q),(Q,R) = (P,R),87,等价定律,序号,表达式,E1,P,P,E2,P,P,P，P,P,P,E3,(P,Q),R,P,(Q,R)，(P,Q),R,P,(Q,R),E4,P,Q, Q P，,P,Q, Q P,E5,P,(Q,R),(P,Q),(P,R)，P,(Q,R),(P,Q),(P,R),E6,P,(P,Q),P，P,(P,Q),P,E7,(P,Q),P,Q，,(P,Q),P,Q,E8,P,F,P，P,T,P,E9,P,T,T，P,F,F,E10,P,P,T，P,P,F,88,1-8 推理理论,（续）,例题1,. 证明(P,Q),(P,R),(Q,S)=S,R,证法1：,（1）P,Q,P规则,（2）,P,Q,T规则作用于（1），E等价性,（3）Q,S,P规则,（4）,P,S,T规则作用于（2）、（3），I蕴涵关系,（5）,S,P,T（4），E,（6）P,R,P,（7）,S,R,T（5）、（6），I,（8）S,R,T（7），E,89,1-8 推理理论,（续）,证法2：,（1）P,R,P规则,（2）P,Q,R,Q,T规则作用于（1），I蕴涵关系,（3）Q,S,P规则,（4）Q,RSR,T规则作用于（3），I蕴涵关系,（5）P,Q,SR,T(2)、（4），I,（6）P,Q,P,（7）S,R,T（5）、（6），I,90,1-8 推理理论,（续）,例题2,. 证明(W,R),V,V,C,S,S,U,C,U=W,（请同学们自学）,91,1-8 推理理论,（续）,（3）间接证法,定义：,设H,1,H,2,H,m,是命题公式，其中的命题变元是P,1,P,2,P,n,，对于P,1,P,2,P,n,的某些真值指派，如果能使H,1,H,2,H,m,的真值为T，则称公式H,1,H,2,H,m,是相容的。如果对于P,1,P,2,P,n,的每一组真值指派都使得H,1,H,2,H,m,的真值为F，则称H,1,H,2,H,m,是不相容的。,不相容的概念用于命题公式的证明：,要证明H,1,H,2,H,m,=C，只需证明H,1,H,2,H,m,与,C是不相容的。,92,1-8 推理理论,（续）,例题3. 证明(A,B)，,(B,C)=A,证明：,（1）A,B,P规则,（2）A,P规则（附加前提）,（3）,(B,C),P规则,（4）,B, ,C,T规则作用于（3）,（5）B,T（1）、（2）,I,（6）,B,T（4）,I,（7）B,B（,矛盾！）T（5）、（6），I,93,1-8 推理理论,（续）,例题4. 证明(P,Q),(P,R),(Q,S)=S,R,（请同学们自学）,94,1-8 推理理论,（续）,间接证明方法的另外一种情况（,CP规则,）：,若要证明要H,1,H,2,H,m,=（R,C）， 设H,1,H,2,H,m,为S，即要证明S=（R,C）或证明S=（,R C,），也即证明S,（,R C,）为永真式。,因为,S,（,R C,）, S （ R C）, （S R） C, （S R） C, （S R） C,因此，若将R作为附加前提，如果有,（S R）= C，即证明了S=,（R,C）。,95,1-8 推理理论,（续）,例题5. 证明A,（,B,C），,D,A，B重言式蕴涵D,C。,证明：,（1）D,P规则（附加前提）,（2）,D,A,P规则,（3）,A,T（1）、（2）,I,（4）A,（,B,C）,P规则,（5）B,C,T（3）、（4）,I,（6）B,P,（7）C,T（5）、（6），I,（8）D,C,CP规则,96,1-8 推理理论,（续）,例题6. 设有下列情况，结论是否成立？,(a)或者是晴天。或者是下雨。,(b)如果是晴天，我去看电影。,(c)如果我去看电影，我就不看书。,我看书了，所以今天下雨,（请同学们自学）,97,第二章 谓词逻辑,谓词演算(一阶谓词演算）是命题演算的扩充和发展,其本质同命题演算,是把数学中的逻辑论证加以符号化,从而推动了这个数学分支的发展.,98,第二章 谓词逻辑,2-1,谓词的概念与表示,2-2,命题函数与量词,2-3,谓词公式与翻译,2-4,变元的约束,2-5,谓词演算的等价式与蕴涵式,2-6,前束范式,2-7,谓词演算的推理理论,99,在命题演算中，基本研究单位是原子命题，也就是对原子命题不再分解，对研究命题间的关系而言是较适合的。,命题演算的推演中存在很大的局限性，有些简单的推断不能用命题演算进行推证。,例如， 三段论推理。,2-1 谓词的概念与表示,谓词演算是对原子命题进行分解，它刻划了命题内部的逻辑结构，从而可以深入研究形式逻辑中的推理问题。,100,在谓词演算中，将原子命题分解为,谓词,和,个体 （客体）,两部分。,个体：可以独立存在的东西,它可以是一个具体的事物，也可以是一个抽象的概念。,谓词：用于刻划客体的性质或客体与看客体之间的关系。,2-1 谓词的概念与表示,（续）,101,2-1 谓词的概念与表示,（续）,谓词,客体,例如：,（1）,李明,是,三好学生,（客体属性）,属性,（2）,5,大于,3,。（客体关系）,谓词,客体,客体,102,谓词记号：,大写字母：表示谓词，如：F、G、H。,小写字母：表示客体（个体）如a、b、c。,例如：用A表示“是个大学生”，c表示“张三”，d表示“李四”，则：,A(c)：张三,是个大学生。,A(d)：李四是个大学生。,用B表示“大于”，e代表“5”，f代表“3”，则：,B(e,f)：5大于3。,2-1 谓词的概念与表示,（续）,103,记号：,一元谓词：,A(c)。,二元谓词：A(c,d)。,三元谓词：A(c,d,e)。,n元谓词： A(c,1,c,2,c,n,)。,2-1 谓词的概念与表示,（续）,一元谓词表达了客体的“性质”，多元谓词表达了客体之间的“关系”。,104,个体常项：表示具体的或特定的个体，常用a、b、c表示,个体变项：表示抽象或泛指的个体词，常用x、y、z表示,个体域（论域）：个体变项的取值范围,全总个体域：无特别声明时，在此范畴讨论,谓词常项：表示具体性质或关系的谓词,谓词变项：抽象或泛指的谓词,谓词常项、变项根据上下文确定,谓词中包含的个体词数n称为元数，相应地n元谓词。如：,P（x1,x2,xn）是一个以x1xn的个体域为定义域，以0、1为值域的n元函数,注意：n元谓词P不是命题,105,量词：全称量词和存在量词,全称量词(for all)：,xF(x),存在量词(exist)：,xG(x),举例：书中例子,特性谓词,使用量词时需注意的地方：见书page40,谓词公式（一阶逻辑合式公式）定义,量词,106,定义1：,由一个谓词和一些变元所组成的表表达式称为,简单命题函数,。,由一个或多个简单命题函数以及逻辑联结词组合而成的表达式称为,复合命题函数,。,说明：,逻辑联结词,、 的意义与命题演算中的解释相同。,107,一阶逻辑中的命题符号化,例：0元谓词符号化,(1) 2是素数且是偶数。,解：设,F(x)：x是素数。,G(x)：x是偶数。,a： 2，,则,命题符号化为F(a),G(a),。,(2) 如果2大于3，则2大于4。,解：设,L(x,y)：x大于y，,a：2， b：3， c：4，,则,命题符号化为L(a,b),L(a,c),。,108,一阶逻辑中的命题符号化,教材Page 39-40：,例题2.2：,例题2.3：,例题2.4：,例题：(P(x,y),P(y,z),P(x,z),P(x,y)的不同解释：,（1） P(x,y),解释,为“x小于y”,（永真）,（2）,P(x,y)解释为“x为y的儿子”,（永假）,（3）,P(x,y)解释为“x距离y10米”,（不定）,109,一阶逻辑中的命题符号化,注意：,命题函数最终表示什么样的命题是与客体变元的论述范围有关的。在命题函数中，客体变元的论述范围称作,个体域,。个体域可以是有限的，也可以使无限的。我们把各种个体域综合作一起作为论述范围的域称为,全总个体域,。,全称量词：,：,表示“对所有的”，“每一个”，“对任意一个”,存在量词,：,表示“存在一些”，“至少有一个”，“对于一些”,110,一阶逻辑中的命题符号化,例1：有如下命题：,（a）所有人都是要呼吸的。,（b）每个学生都要参加考试。,（c）任何整数或者是正的或者是负的。,设：,M(x)：x是人。P(x)：x是学生。,I(x)：x是整数。H(x)：x要呼吸。,Q(x)：x要参加考试。R(x)：x是正数。,N(x)：x是负数。,则上述三个命题可以表述为：,（a）(,x)(M(x)H(x),（b）(,x)(P(x)Q(x),（c）(,x)(I(x)(R(x) N(x),111,一阶逻辑中的命题符号化,例2：有如下命题：,（a）存在一个数是质数。,（b）一些人是聪明的。,（c）有些人早饭吃面包。,设：,M(x)：x是人。P(x)：x是质数。,R(x)：x是聪明的。E(x)：x早饭吃面包。,则上述三个命题可以表述为：,（c）(,x)(P(x),（d）(,x)(M(x),R(x),（e）(,x)(M(x),E(x),112,例题1：,并非每个实数都是有理数。,解：,设R(x)：x是实数； Q(x)：x是有理数,；,谓词公式,：,(,x)(R(x),Q(x),例题2：（不讲）,例题3：,（不讲）,例题