离散数学讲义

1、discrete mathematics,离散数学讲义（电子版）,2,课程概况,教材： 离散数学（第三版），耿素云等编著 清华大学出版社，2004年3月,参考书： （1） 离散数学(第二版)及其配套参考书离散 数学题解作者：屈婉玲，耿素云，张立昂 清华大学出版社 （2） 离散数学焦占亚主编 电子工业出版社 2005年1月,3,课程概况,选修课/必修课：选修 周学时：3（学时） 上课周：116周 总学时：48（学时）,4,课程内容及学时安排,第一篇 数理逻辑（14学时） 第一章 命题逻辑（8） 第二章 谓词逻辑（6） 第二篇 集合论（12学时） 第三章 集合（4） 第四章 二元关系与函数（8）

2、第四篇 图论（14学时） 第七章 图论（8） 第八章 一些特殊图（4） 第九章 树 （2）,5,课程考核,考核方式： 闭卷笔试,第四篇 代数系统（8学时） 第5、6章 图论（8）,6,课程要求,（1）上课认真听讲 （2）课后及时复习 （3）独立、认真地完成作业 （4）有问题及时提出，不要积累问题,7,什么是离散数学？,是研究离散对象和它们之间的关系 的现代数学。,它为计算机科学中的数据结构、编 译理论、操作系统、算法分析、人 工智能等提供了必要的数学知识。,其内容较广，主要包括数理逻辑、 集合论、图论、代数结构等四个基本部分。,8,什么是离散数学？,离散数学将日常的概念、判断、推理用数学符号来

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

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

5、其表示法,14,习惯上，命题用小写字母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 说谎者悖论(1iar paradox or epimenides paradox) 最古老的语义悖论。公元前6世纪古希腊哲学家伊壁孟德 所创的四个悖论之一。是关于“我正在撒谎”的悖论。具体为：如果他的确正在撒谎，那么这句话是真的，所以伊壁孟德不在撤谎，如果他不在撒谎，那么这句话是假的，因而伊壁孟德

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

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

11、错了，就得受绞刑。可是，如果他们绞死他，他就说对了，就不应该绞死他。,23,下一句话是真的； 上一句话是假的。 命题常项（常元）：具有唯一真值的命题； 命题变项（变元）：泛指任意一个命题或者类似x+y5根据条件不同真值不同的命题。 注意：命题变项不是命题，它不具有唯一真值,24,1-2 联结词,1、否定,设p为一命题，则新命题“p是不对的”称为p的否定。记作： p,如：p：2是常数。, p：2不是常数。,q：今天是星期四。, q：今天不是星期四。,p与 p的真值关系：,25,1-2 联结词（续）,2、合取,设p，q是两命题，新命题“p并且q”称为命题p，q的合取。记作：pq,如：p：北京是中国

12、的首都。 q：北京是一个古都。 pq：北京是中国的首都并且是一个古都。,p q的真值关系：,26,1-2 联结词（续）,3、析取,设p，q为两个命题，则新命题“p或者q”称为命题p，q的析取。记作：pq,如：p：北京是中国的首都。 q：北京是一个故都。 pq：北京是中国的首都或者是一个故都。,规定：pq的真值为1当且仅当p，q中至少有一个真值为1。,pq的真值关系：,27,1-2 联结词（续）,注意：析取联结词与汉语中的“或”的意义不完全相同。 汉语中的“或”既可以表示“排斥或”，也可以表示 “可兼或”。,例如： p：今天晚上我在家看电视或去剧场看戏。 q：他可能是100米或400米赛跑的冠军

13、。,“排斥或”,“可兼或”,28,1-2 联结词（续）,4、条件,设p，q是两命题，其条件命题是一个复合命题，记做pq，读做“如果p，则q”。,真值关系：,“善意的推定”,29,1-2 联结词（续）,5、双条件,设p，q是两命题，其双条件命题是一个复合命题， 记做pq，读做“如果p，则q”。,真值关系：,30,1-2 联结词（续）,在命题演算中，五个联结词的含义由真值表唯一确定。,31,1-3 命题公式及其赋值,定义：合式公式 （1）单个命题变元本身是一个合式公式。 （2）如果a是一个合式公式，那么a是合式公式。 （3）如果a、b是合式公式，那么（ab）、 （ab）、（ab）、 （ab）都是合

14、式公 式。 （4）当且仅当能够有限次地应用上面（1）、（2）、 （3）所得到的包含命题变元、联结词合括号的 符号串是合式公式。 递归定义,基础,归纳,界限,32,1-3 命题公式及其赋值（续）,例如： 合式公式： (pq), (pq) (p(pq) (pq)(qr)(st) 非合式公式： (pq)(q) (pq (pq)q),括号不匹配,括号不匹配,应是双目运算符,33,1-3 命题公式及翻译,联结词的运算优先级：,高,低, ,命题公式的层（描述公式的复杂程度） 命题公式的赋值（解释、翻译） 真值表,34,1-3 命题公式及翻译（续）,请看教材page 10-11。,例题1：我们要做到身体好、

15、学习好、工作好，为祖 国的四化建设而奋斗。 解 找出原子命题： a：我们要做到身体好。 b：我们要做到学习好。 c：我们要做到工作好。 p；我们要为祖国的四化建设而奋斗。 命题的形式化描述： (a b c) p。,35,1-3 命题公式及翻译（续）,例题2：上海到北京的14次列车是下午五点半或六点 开。 解 找出原子命题： p：上海到北京的14次列车是下午五点半开。 q：上海到北京的14次列车是下午六点开。 排斥或： （ pq）（p q）,命题的形式化描述：(pq)。,36,1-3 命题公式及翻译（续）,例题3： （自学） 例题4： （自学） 例题5： （自学） 例题6： （自学）,37,习题

16、：,*各章节后习题中的双号大题中的双 号小题。,38,1-4 真值表与等价公式,定义：在命题公式中，对于分量指派真值的各种可能组合，就确定了这个命题公式的各种真值情况，把它们汇列成表，就是命题公式的真值表。,含n个命题变元的命题公式，共有2n组赋值。,例题1：pq的真值表。,39,1-4 真值表与等价公式（续）,例题2：(pq) p的真值表。,例题3： (pq) v(pq)的真值表。,永假公式,40,1-4 真值表与等价公式（续）,例题4：(pq)(pq)的真值表。,永真公式,41,1-4 真值表与等价公式（续）,定义：给定两个命题公式a和b，设p1， p2， pn，为所有出现在a和b中的原子

17、变元。若给p1， p2， pn任意一组真值指派，a和b的真值都相同，则称a和b是等价（或逻辑相等），记做ab。,例题5：证明pq (pq)(qp) 。,42,1-4 真值表与等价公式（续）,两个公式 （1） p q pq,（2） (p q) (p q) pq,43,1-4 真值表与等价公式（续）,10个命题定律：,44,1-4 真值表与等价公式（续）,10个命题定律：,45,1-4 真值表与等价公式（续）,46,1-4 真值表与等价公式（续）,例题6 验证吸收律： p (p q) p p (p q) p,验证：列出真值表,47,1-4 真值表与等价公式,定义：如果x是合式公式a的一部分，且x本

18、身也是一个合式公式，则称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。,48,1-4 真值表与等价公式,例题8 证明：(p q) (p q) p,证： (p q) (p q) p (q q) 分配律 p 1 否定律 p同一律,49,1-4 真值表与等价公式,例题9 证明：p (q r) q (p r) r (q p),证： p (q

19、r) p (q r) 蕴涵等值式 q (p r) 结合律 q (p r) 蕴涵等值式 （第二个等价公式类似可证。）,50,1-5 其它连结词,定义：设p和q是两个命题公式，复合命题p 、q恰有一个成立称为p与q的排斥或或异或。 p q的真值为t，当且仅当p与q的真值不相同时为t，否则为f。,定理：设p,q,r为任意命题公式。如果p q r，则 p r q，q r p,且p q r为一矛盾式。,51,1-5 其它连结词,定义：设p和q是两个命题公式，复合命题p q称为p和q的条件否定， p q的真值为t，当且仅当p的真值为t，q的真值为f；否则，p q的真值为为f。,52,1-5 其它连结词,定

20、义：设p和q是两个命题公式，复合命题pq称为p和q的“与非”，当且仅当p和q的真值都为t时， pq 的真值为f；否则， pq的真值为为t。,53,1-5 其它连结词,定义：设p和q是两个命题公式，复合命题pq称为p和q的“或非”，当且仅当p和q的真值都为t时， pq 的真值为f；否则， pq的真值为为t。,54,1-5 其它连结词,命题公式：,55,1-5 其它连结词,等价公式： 1. pq (pq) (qp) 2. (pq) p q 3. 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),最小联结词组：

21、，或，或或,56,回顾表1-4.8的10个命题定律：,1-6 对偶与范式,57,1-6 对偶与范式（续）,回顾表1-4.8的10个命题定律：,58,1-6 对偶与范式（续）,定义：在给定的命题中，将联结词换成，将换成，若有特殊变元f和t也相互替代，所得公式a*称为a的对偶式。 显然，a*与a互为对偶式。 例题1. 例题2.,定理：设a*为a的对偶式，p1,p2,pn是出现在a和a*中的 原子变元，则 a(p1,p2, pn) a*(p1,p2, pn) a(p1,p2, pn) a*(p1,p2, pn),59,1-6 对偶与范式（续）,例题4：p q 的对偶式是p q ; p q 的对偶式是

22、 p q 永真式的对偶式是永假式，反之亦然；,定理：设a*为a的对偶式，p1,p2,pn是出现在公式a和b中 的原子变元，如果a b，则a* b*。,60,1-6 对偶与范式（续）,定义：一个命题称为合取范式，当且仅当它具有如下的形式： a1a2 an，(n1) 其中a1,a2,an都是由命题变元或其否定所组成的析取式。 定义：一个命题称为析取范式，当且仅当它具有如下的形式： a1a2 an，(n1) 其中a1,a2,an都是由命题变元或其否定所组成的合取式。,注意：一个命题的合取范式或析取范式不是唯一的。,61,1-6 对偶与范式（续）,求一个命题的合取范式或析取范式的步骤： 将公式中的联结

23、词化归成，及。 利用德.摩根定律将否定联结词直接移到各命题变元之前。 利用分配律、结合律将公式归约为合取范式或析取范式。,62,1-6 对偶与范式（续）,定义：n个命题变元的合取式称为布尔合取（或小项），其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。 例如：两个变元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个小项。,63,1-6 对偶与范式（续）,两个变元p和q的小项的真值表：,64,1-6 对偶与范式（续）,

24、三个变元p，q，r的小项的真值表：,65,1-6 对偶与范式（续）,三个变元p，q，r的小项的真值表:,66,1-6 对偶与范式（续）,三个变元p，q，r的小项的真值表:,67,1-6 对偶与范式（续）,三个变元p，q，r的小项的编码表: m000 p q r m001 p q r m010 p q r m011 p q r m100 p q r m101 p q r m110 p q r m111 p q r,68,1-6 对偶与范式（续）,小项的性质: （1）每一个小项当其真值指派与编码相同时，其真值为t，在其余2n-1中指派情况下均为f。 （2）任意两个不同小项的合取式为永假。 （3）全

25、体小项的析取式为永真，记为：,69,1-6 对偶与范式（续）,定义：对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等式称为原式的主析取范式。,定理：在真值表中，一个公式的真值为t的指派所对应的小项的析取，即为此公式的主析取范式。,例题6：给定p q，p q和 (p q)，求这些公式的主析取范式。 例题7： 例题8： 例题9：,70,1-6 对偶与范式（续）,对于给定命题公式的主析取范式，如果将其命题变元的个数和出现自许固定后，则此公式的主析取范式就是唯一的。,定义：n个命题变元的析取式称为布尔析取或大项。其中每个变元与它的否定不能同时存在，但两者必须且仅出现一次。,71,

26、1-6 对偶与范式（续）,大项的二进制编码： n=2: m00 p q m01 p q m10 p q m11 p q,72,1-6 对偶与范式（续）,大项的二进制编码： n=3: m000 p q r m001 p q r m010 p q r m011 p q r m100 p q r m101 p q r m110 p q r m111 p q r,73,1-6 对偶与范式（续）,大项的性质: （1）每一个大项当其真值指派与编码相同时，其真值为f，在其余2n-1中指派情况下均为t。 （2）任意两个不同大项的析取式为永真。 （3）全体大项的合取式为永假，记为：,74,1-6 对偶与范式（续

27、）,定义：对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等式称为原式的主合取范式。,定理：在真值表中，一个公式的真值为f的指派所对应的大项的合取，即为此公式的主合取范式。,75,1-6 对偶与范式（续）,例题10：利用真值表技术求(pq) (pr)的主析取范式和主合取范式。 解：公式(pq) (pr)的真值表如下：,主和取范式： 主析取范式：,76,1-6 对偶与范式（续）,77,1-6 对偶与范式（续）,例题11：将(pq) (pr)化为主合取范式。,78,1-7 重言式与蕴涵式,定义：给定一个命题，若无论对分量作怎样的指派，其对应的真值永远为t，则称该命题公式为重言式

28、或永真公式。 定义：给定一个命题，若无论对分量作怎样的指派，其对应的真值永远为f，则称该命题公式为矛盾式或永假公式。,定理：任何两个重言式的合取或析取仍然是一个重言式。,定理：一个重言式，对同一分量都用任何公式置换，其结果仍然是一个重言式。,定理：设a，b为两个命题公式， a b 当且仅当a b为一个重言式。,79,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

29、 q p p q,逆反命题,80,1-7 重言式与蕴涵式,14个常用蕴涵命题：,81,1-7 重言式与蕴涵式,14个常用蕴涵命题（续）：,82,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。,83,1-8 推理理论,定义：设a和c是两个命题公式，当且仅当a-c为一个重言式，即a=c，称c是a的有效结论。或c可以由a逻辑地推出

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

31、 推理理论（续）,解：公式p (p q)的真值表如下：,所以有p (p q)=q。,86,1-8 推理理论（续）,（2）直接证法 p规则：前提在推导过程中的任何时候都可以引入使用。 t规则：在推导过程中，如果有一个或多个公式重言蕴涵这公式s，则公式s可以引入推导之中。,87,蕴涵命题,88,等价定律,89,1-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

32、rt（7），e,90,1-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）、（6），i,91,1-8 推理理论（续）,例题2. 证明(wr)v,vcs,su, cu=w （请同学们自学）,92,1-8 推理理论（续）,（3）间接证法 定义：设h1,h2,hm是命题公式，其中的命题变元是p1,p2,pn，对于p1,p2,pn的某些真值指派，如果能使h1 h2 hm的真值为t，则称公式h1,h2,hm 是相容的。如果对

33、于p1,p2,pn的每一组真值指派都使得h1 h2 hm的真值为f，则称h1,h2,hm 是不相容的。 不相容的概念用于命题公式的证明： 要证明h1 h2 hm =c，只需证明h1,h2,hm与c是不相容的。,93,1-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），i,94,1-8 推理理论（续）,例题4. 证明(pq)(pr)(qs)=s r （请同学们自学）,95,1-8 推

34、理理论（续）,间接证明方法的另外一种情况（cp规则）： 若要证明要h1 h2 hm =（r c）， 设h1 h2 hm为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）。,96,1-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）

35、b p （7）ct（5）、（6），i （8）dc cp规则,97,1-8 推理理论（续）,例题6. 设有下列情况，结论是否成立？ (a)或者是晴天。或者是下雨。 (b)如果是晴天，我去看电影。 (c)如果我去看电影，我就不看书。 我看书了，所以今天下雨 （请同学们自学）,98,第二章 谓词逻辑,谓词演算(一阶谓词演算）是命题演算的扩充和发展,其本质同命题演算,是把数学中的逻辑论证加以符号化,从而推动了这个数学分支的发展.,99,第二章 谓词逻辑,2-1 谓词的概念与表示 2-2 命题函数与量词 2-3 谓词公式与翻译 2-4 变元的约束 2-5 谓词演算的等价式与蕴涵式 2-6 前束范式 2-

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

37、词的概念与表示（续）,谓词,客体,例如： （1）李明是三好学生（客体属性）,属性,（2）5大于3。（客体关系）,谓词,客体,客体,103,谓词记号：,大写字母：表示谓词，如：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 谓词的概念与表示（续）,104,记号：,一元谓词：a(c)。 二元谓词：a(c,d)。 三元谓词：a(c,d,e)。 n元谓词： a(c1,c2,cn)。,2-

38、1 谓词的概念与表示（续）,一元谓词表达了客体的“性质”，多元谓词表达了客体之间的“关系”。,105,个体常项：表示具体的或特定的个体，常用a、b、c表示 个体变项：表示抽象或泛指的个体词，常用x、y、z表示 个体域（论域）：个体变项的取值范围 全总个体域：无特别声明时，在此范畴讨论 谓词常项：表示具体性质或关系的谓词 谓词变项：抽象或泛指的谓词 谓词常项、变项根据上下文确定 谓词中包含的个体词数n称为元数，相应地n元谓词。如： p（x1,x2,xn）是一个以x1xn的个体域为定义域，以0、1为值域的n元函数 注意：n元谓词p不是命题,106,量词：全称量词和存在量词 全称量词(for all

39、)： xf(x) 存在量词(exist)： xg(x) 举例：书中例子 特性谓词 使用量词时需注意的地方：见书page40 谓词公式（一阶逻辑合式公式）定义,量词,107,定义1：由一个谓词和一些变元所组成的表表达式称为简单命题函数。,由一个或多个简单命题函数以及逻辑联结词组合而成的表达式称为复合命题函数。,说明： 逻辑联结词、 的意义与命题演算中的解释相同。,108,一阶逻辑中的命题符号化,例：0元谓词符号化 (1) 2是素数且是偶数。 解：设 f(x)：x是素数。 g(x)：x是偶数。 a： 2， 则命题符号化为f(a) g(a)。 (2) 如果2大于3，则2大于4。 解：设 l(x,y)

40、：x大于y， a：2， b：3， c：4， 则命题符号化为l(a,b) l(a,c)。,109,一阶逻辑中的命题符号化,教材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米” （不定）,110,一阶逻辑中的命题符号化,注意： 命题函数最终表示什么样的命题是与客体变元的论述范围有关的。在命题函数中，客体变元的论述范围称作个体域。个体域可以是有限的，也可以使无限的。

41、我们把各种个体域综合作一起作为论述范围的域称为全总个体域。,全称量词： ：表示“对所有的”，“每一个”，“对任意一个” 存在量词 ：表示“存在一些”，“至少有一个”，“对于一些”,111,一阶逻辑中的命题符号化,例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)(

42、r(x) n(x),112,一阶逻辑中的命题符号化,例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),113,例题1：并非每个实数都是有理数。 解：设r(x)：x是实数； q(x)：x是有理数； 谓词公式：(x)(r(x)q(x) 例题2：（不讲） 例题3：（不讲）,例题4：这只大红书柜摆满了那些古书。 解：设f(x,y)：x摆满了y；r

43、(x)：x是大红书柜； q(y)：y是古书；a：这只；b：那些。 谓词公式：r(a) q(b) f(a,b),114,2-2 谓词公式与翻译（续）,例题5. 极限的定义：任给0，存在0，使得当 0|x-a|时有|f(x)-b|，则称 b 是f(x)在xa时的极限，记为f(x)b（当xa）。 下面用谓词公式表示以上定义： 用p(x,y)表示“x大于y”，q(x,y)表示“x小于y”，则以上定义的谓词公式表示如下： ()()(x)(p(,0)p(,0) q(|x-a|,) p(|x-a|,0)q(|f(x)-b|,),115,2-2 谓词公式与翻译,定义：谓词公式的合式公式，可以由下述各条组成：

44、（1）原子谓词公式是合式公式。 （2）若a是合式公式，则a也是合式公式。 （3）若a和b都是合式公式，则(ab)，(ab)、(ab)和(ab)都是合式公式。 （4）若a都是合式公式，x是出现在a中的任何变元，则(x)a和(x)a都是合式公式。 （5）只有经过有限次地应用规则(1)、(2)、(3)、(4)所得到的公式是合式公式。,谓词合式公式简称谓词公式。,见书p41关于字母表、项、原子公式、谓词公式定义 原子公式：a(x1,x2,xn)，这里x1,x2,xn是客体变元。,116,变元的约束,几个名词： （1）指导变项（作用变元） （2）作用域（辖域） （3）约束出现 （4）约束变项、自由变项

45、（5）封闭的合式公式,117,2-4 变元的约束（续）,例题1. 说明以下各公式的作用域与变元的约束情况。 (x)(p(x)q(y) (x)的作用域是p(x)q(y)， x为约束变元。 b) (x)(p(x)(y)(r(x,y) (x)的作用域是(p(x)(y)(r(x,y)， (y)的作用域是r(x,y)。 x,y为约束变元。,指导变元,作用域,118,2-4 变元的约束（续）,c) (x)(y)(p(x,y)q(y,z)(x)p(x,y) (x)(y)的作用域是(p(x,y)q(y,z) x,y为约束变元，z是自由变元。 (x)的作用域是p(x,y) x为约束变元，y是自由变元。,119,

46、2-4 变元的约束（续）,约束变元的换名规则： （1）对于约束变元可以换名，其更改的变元名称范围是量词中的指导变元，以及该量词作用域中所出现的该变元，在公式的其余部分不变。 （2）换名时一定要换为作用域中没有出现过的变元名称。,120,2-4 变元的约束（续）,例题2. 对(x)(p(x)r(x,y) q(x,y)换名。 解：可换名为 (z)(p(z)r(z,y) q(x,y) 但不可换名为 (y)(p(y)r(y,y) q(x,y) 或 (z)(p(z)r(x,y) q(x,y),121,2-4 变元的约束（续）,自由变元的代替规则： （1）对于自由变元可以代入，代入时需对公式中出现该自由变

47、元的每一处进行代入。 （2）用以代入的变元与原公式中的所有变元的名称不能相同。,122,2-4 变元的约束（续）,例题3. 对(x)(p(y)r(x,y)作自由变元代入。 解：对y施行代入，得到： (x)(p(z)r(x,z) 但是 (x)(p(x)r(x,x) 和 (x)(p(z)r(x,y) 都是错误的。,123,合式公式的解释,见书p43例题 定义:逻辑有效式（永真式）、矛盾式（永假）、可满足式 逻辑有效式是可满足式，但反之不成立。 定义：代换实例 定理：命题公式中的重言式的代换实例在谓词公式中仍为重言式，即逻辑有效式；命题公式中的矛盾式的代换实例仍为矛盾式 书p43 例题,124,2-

48、5 谓词演算的等价式与蕴涵式,定义1.给定任何两个谓词公式 a和 b，设它们有共同的个体域e。若对a和b的任意一组变元进行赋值，所得命题的真值相同，则称谓词公式a和b在e上是等价的。记为ab。,定义2.任意给定谓词公式 a，其个体域为e。若对a的任意变元赋值， a都为真，则称该 a在e上是有效的（或永真的）。,定义3.对于一个谓词公式 a，如果在所有赋值下，该公式的真值都为假，则称该 a 为不可满足的。否则，称该 a 为可满足的。,125,2-5 谓词演算的等价式与蕴涵式（续）,（1）命题公式的推广 命题演算中的等价公式表和蕴涵式表都可以推广到谓词演算中。例如：,(x)(p(x)q(x)( x

49、)(p(x)q(x) (x)p(x)(y)(r(x,y)(x)p(x)(y)(r(x,y) (y)(h(x,y)(x)h(x,y)f 另外经过换名和代替规则所得公式和原公式等值,126,2-5 谓词演算的等价式与蕴涵式（续）,（2）量词与联结词之间的关系 约定：出现在量词之前的否定，不是否定该量词，而是否定被量化了的整个命题。,转化公式： 1.(x)p(x)(x)p(x) 2.(x)p(x)(x)p(x),127,2-5 谓词演算的等价式与蕴涵式（续）,上述公式的推广： 设个体域中的客体变元为a1,a2,an，则 1. (x)a(x)(a(a1)a(a2)a(an) a(a1)a(a2)a(a

50、n) (x)a(x) 2. ( x)a(x)(a(a1)a(a2)a(an) a(a1)a(a2)a(an) (x)a(x),128,2-5 谓词演算的等价式与蕴涵式（续）,结论： 当将量词前面的联结词移到量词的后面去时，存在量词改为全称量词，全称量词改为存在量词；反之，如果将量词后面的联结词移到量词的前面去时，也要做相应的改变。,129,2-5 谓词演算的等价式与蕴涵式（续）,（3）量词作用域的扩张与收缩,1. (x)(a(x)b)(x)a(x)b 2. (x)(a(x)b)(x)a(x)b,3. (x)(a(x)b)(x)a(x)b 4. (x)(a(x)b)(x)a(x)b,5. (x)

51、(a(x)b)(x)a(x)b 6. (x)(a(x)b)(x)a(x)b,7. (x)(ba(x)(b(x)a(x) 8. (x)(ba(x)(b(x)a(x),130,2-5 谓词演算的等价式与蕴涵式（续）,（4）量词与命题联结词之间的一些等价关系 量词分配等值式,1. (x)(a(x)b(x)(x)a(x)(x)b(x),2. (x)(a(x)b(x)(x)a(x)(x)b(x),注意：全称量词只对合取有分配； 存在量词只对析取有分配；,131,2-5 谓词演算的等价式与蕴涵式（续）,（5）量词与命题联结词之间的一些蕴涵关系,1.(x)(a(x)b(x)=(x)a(x)(x)b(x),2

52、.(x)(a(x)b(x)=(x)a(x)(x)b(x),3.(x)(a(x)b(x)=(x)a(x)(x)b(x),132,2-5 谓词演算的等价式与蕴涵式（续）,（6）多个量词的使用,对于二元谓词的情况：,1.(x)(y)a(x,y) 2.(x)(y)a(x,y) 3.(x)(y)a(x,y) 4.(x)(y)a(x,y),5.(y)(x)a(x,y) 6.(y)(x)a(x,y) 7.(y)(x)a(x,y) 8.(y)(x)a(x,y),（2种排列情况 4种组合情况）,133,2-5 谓词演算的等价式与蕴涵式（续）,（3）量词与命题联结词的一些等价式与蕴涵式,134,2-5 谓词演算的

53、等价式与蕴涵式（续）,量词与命题联结词的一些等价式与蕴涵式,135,2-5 谓词演算的等价式与蕴涵式（续）,（4）多个量词的使用 以两个量词对于二元谓词的情况为例 (x)(y)a(x,y) (y)(x)a(x,y) (x)(y)a(x,y) (y)(x)a(x,y) (x)(y)a(x,y) (y)(x)a(x,y) (y)(x)a(x,y) (x)(y)a(x,y),136,2-5 谓词演算的等价式与蕴涵式（续）,例 设 a(x,y)表示x和y同姓,论域x是甲村的人,y是乙村的人,则 (x)(y)a(x,y): 甲村和乙村所有的人都同姓。 (y)(x)a(x,y)： 乙村和甲村所有的人都同姓

54、。 显然上述俩语句的含义相同。故 (x)(y)a(x,y) (y)(x)a(x,y),137,2-5 谓词演算的等价式与蕴涵式（续）,(x)(y)a(x,y) (y)(x)a(x,y） 同理 (x)(y)a(x,y)： 甲村与乙村有人同姓。 (y)(x)a(x,y)： 乙村与甲村有人都同姓。 故 (x)(y)a(x,y) (y)(x)a(x,y),138,2-5 谓词演算的等价式与蕴涵式（续）,但是 (x)(y)a(x,y) 表示对于甲村所有的人，乙村都有人和他同姓。 (y)(x)a(x,y) 表示存在一个乙村的人，甲村所有的人和他同姓。 (y)(x)a(x,y) 表示对于乙村所有的人，甲村都

55、有人和他同姓。 (x)(y) a(x,y) 表示存在一个甲村的人，乙村所有的人和他同姓。 上述四种语句，表达的情况各不相同，故全称量词与存在量词的次序，不能随意更换。,139,2-6 前束范式,定理：任何一个谓词公式均等价于某个前束范式。,定义：如果一个谓词公式的量词均在全式的开头，而这些量词的作用域延伸至整个公式的末尾，则该公式叫做前束范式。 前束范式记为：(v1)(v2)(vn)a,例：(x)(y)(z)(q(x,y) r(z)是一个前束范式。,140,2-6 前束范式,例1：把公式(x)p(x)(x)q(x)转化为前束范式。 解： (x)p(x)(x)q(x) 等值代换 (x)p(x)

56、(x)q(x) (x)p(x)(x)q(x) (x)(p(x)q(x),前束范式,(参见教材 page47-48例题） 前束范式不是唯一的 还应注意，公式的前束范式各指导变项应是不同的，原式中自由变项应该仍然以自由变项形式出现，否则就是错误的,141,2-6 前束范式（续）,将一个谓词公式转化为一个与之等价的前束范式的步骤： 第一步：否定深入； 第二步：量词提前。,142,2-6 前束范式（续）,定义：如果一个谓词公式wff a具有如下形式，则称其为一个前束合取范式。 (v1)(v2)(vn)(a11 a12 a1l1) (a21 a22 a2l2) (am1 am2 amlm),定理：任何一

57、个谓词公式都可以转化为与其等价的前束合取范式。,例：(x)(z)(y)p(xa)(z=b)q(y)(a=b) 就是一个前束合取范式。,143,2-6 前束范式（续）,例4.将谓词公式 d: (x)(y)p(x)(z)q(z,y)(y)r(x,y) 化为与之等价的前束合取范式。 解： 第一步，取消多余量词：d(x)p(x)(z)q(z,y)(y)r(x,y) 第二步，约束变量换名： d(x)p(x)(z)q(z,y)(w)r(x,w) 第三步，消去条件联结词： d(x)(p(x)(z)q(z,y)(w)r(x,w),注意，联结词的优先级高于的优先级,144,2-6 前束范式（续）,第四步，将深入

58、： d(x)(p(x)(z)q(z,y)(w)r(x,w) (x)(p(x)(z)q(z,y)(w)r(x,w) 第五步，将量词提前： d(x)(z)(w)(p(x)q(z,y)r(x,w) (x)(z)(w) (p(x)r(x,w)(q(z,y)r(x,w),前束合取范式,145,2-6 前束范式（续）,定义：如果一个谓词公式 a具有如下形式，则称其为一个前束析取范式。 (v1)(v2)(vn)(a11 a12 a1l1) (a21 a22 a2l2) (am1 am2 amlm),定理：任何一个谓词公式都可以转化为与其等价的前束析取范式。,146,2-7 谓词演算的推理理论,谓词演算推理规

59、则,谓词推理定义：见书 p规则：前提在推导过程中的任何时候都可以引入使用。 t规则：在推导过程中，如果有一个或多个公式重言蕴涵这公式s，则公式s可以引入推导之中。 注意：命题逻辑中八个推理定律的代入实例都是谓词逻辑中的推理定律； 命题逻辑中的等值式每个都可对应出两条推理定律,147,2-7 谓词演算的推理理论,关于量词分配的推理定律： (1)(x a(x) x b(x) = x (a(x)b(x) (2) x(a(x)b(x) = x a(x) x b(x) (3) x(a(x)b(x) = x a(x) x b(x) (4) x(a(x)b(x) = x a(x) x b(x) (1)式说明：a(x)表示x有一支铅笔，b(x)表示有一支钢笔，个体域为某班学生。则全班每个学生都有一支钢笔或每个学生都有一支铅