《北大离散数学ppt课件.ppt》由会员分享，可在线阅读，更多相关《北大离散数学ppt课件.ppt（169页珍藏版）》请在三一办公上搜索。
1、离散数学,主讲教师:邹复民,离散数学是现代数学的一个重要分支。是计算机科学中基础理论的核心课程，为计算机科学提供了有力的理论基础和工具。离散数学的基本思想、概念和方法广泛地渗透到计算机科学与技术发展的各个领域，而且其基本理论和研究成果更是全面而系统地影响和推动着其发展。,离散数学的内容十分丰富，最重要，最核心的是：数理逻辑、集合论、代数系统和图论。本课程主要讲授以上四个方面的内容。,数理逻辑简介,数理逻辑是用数学方法来研究推理的形式结构和推理规律的数学学科，它与数学的其它分支、计算机科学、人工智能、语言学等学科均有密切的联系。命题逻辑和一阶谓词逻辑是数理逻辑中最成熟的部分，在计算机科学中应用最
2、为广泛，其中命题逻辑是数理逻辑的最基础部分，谓词逻辑是在它的基础上发展起来的。本课程在第一，二两章中介绍数理逻辑的内容。,第一章命题逻辑,第一节 命题符号化及联结词,内容：命题，逻辑联结词，命题符号化,(1)掌握命题概念 (2)掌握联结词含义及真值表 (3)掌握命题符号化方法,重点：,一、命题的概念,命题：能判断真假的陈述句。,例1、判断下列句子中哪些是命题。,(1) 北京是中国的首都。,(2) 雪是黑色的。,(4) 请把门关上！,(6) 地球外的星球上也有人。,例1、判断下列句子中哪些是命题。,(7) 明天有课吗？,(8) 本语句是假的。,(9) 小明和小林都是三好生。,(10) 小明和小林
3、是好朋友。,判断一个语句是否为命题，首先看是否为陈述句，再看其真值是否唯一。,二、逻辑联结词。,真值表,真值表,(1) 李平既聪明又用功。,(2)李平虽然聪明，但不用功。,(3)李平不但聪明，而且用功。,(4)李平不是不聪明，而是不用功。,真值表,真值表：,例3、一位父亲对儿子说：“如果我去书店，就一定给你买本儿童画报。”问：什么情况下父亲食言？,解：可能情况有四种：,(1) 父亲去了书店，给儿子买了儿童画报。(2) 父亲去了书店，却没给儿子买儿童画报。(3) 父亲没去书店，却给儿子买了儿童画报。(4) 父亲没去书店，也没给儿子买儿童画报。,(1) 如果天不下雨，我就骑车上班。,(2) 只要天
4、不下雨，我就骑车上班。,(3) 只有天不下雨，我才骑车上班。,(4) 除非天下雨，否则我就骑车上班。,(5) 如果天下雨，我就不骑车上班。,(或 ),真值表：,6、逻辑联结词与自然语言中联结词的关系。,否定不是，没有，非，不。,合取并且，同时，和，既又，不但而且，虽然但是。,析取或者，或许，可能。,蕴涵若则，假如那么，既然那就，倘若就。,等价当且仅当，充分必要，相同，一样。,7、运算顺序,例如：,三、命题符号化。,步骤：(1) 找出各简单命题，分别符号化。,(2) 找出各联结词，把简单命题逐个联结起来。,例6、将下列命题符号化。,(1) 小王是游泳冠军或百米赛跑冠军。,(2) 小王现在在宿舍或
5、在图书馆。,例6、将下列命题符号化。,(3) 选小王或小李中的一人当班长。,(4) 如果我上街，我就去书店看看，除非我很累。,(5) 小丽是计算机系的学生，她生于1982或1983年， 她是三好生。,第二节 命题公式及分类,内容：命题公式，重言式，矛盾式，可满足公式。,重点：(1) 掌握命题公式的定义及公式的真值表。,(2) 掌握重言式和矛盾式的定义及使用真 值表进行判断。,一、命题公式,通俗地说，命题公式是由命题常项，命题变项，联结词，括号等组成的字符串。,例1、判断以下字符串中哪些是命题公式。,(1),(2),(3),(4),(5),(6),解：(1)、(2)、(6)是公式，(3)、(4)
6、、(5)不是。,2、命题公式的层次。,5,3、真值表。,3、真值表。,(3) 对应每个赋值，计算各层次的值，直至整个公式。,例3、求下列命题公式的真值表。,(1),解：,例3、求下列命题公式的真值表。,(2),解：,二、重言式、矛盾式，可满足式。,2、判定方法:真值表法。,1、定义,例4、给定命题公式如下，请判断哪些是重言式，哪些是矛盾式，哪些是可满足式？,例4、给定命题公式如下，请判断哪些是重言式，哪些是矛盾式，哪些是可满足式？,解：列出各题真值表如下(步骤简略),(1)、(2)、(5)、(6)、(9)为重言式；(3)、(8)为矛盾式；(4)、(7)、(10)及以上的重言式均为可满足式。,第
7、三节 等值演算,内容：等值关系，24个重要等值式，等值演算。,重点：(1) 掌握两公式等值的定义。,(2) 掌握24个重要等值式，并能利用其进行等值演算。,一、两命题公式间的等值关系。,2、判定 。,(1) ，,解：作真值表如下：,解：作真值表如下：,(2) ，,二、重要等值式。,二、重要等值式。,二、重要等值式。,10、双重否定律,二、重要等值式。,11、蕴涵等值式,12、等价等值式,13、假言易位,14、等价否定等值式,15、归谬论,三、等值演算。,例2、验证下列等值式。,例2、验证下列等值式。,(1),解：,蕴涵等值式,蕴涵等值式,结合律,德摩根律,蕴涵等值式,例2、验证下列等值式。,(
8、2),解：,交换律,分配律,排中律,同一律,(3),解：,分配律,矛盾律,同一律,德摩根律,结合律,排中律,零律,考虑问题:能否利用等值式来化简，或判断公式的类型(重言，矛盾，可满足)。,判断一个公式是否重言式，矛盾式，可满足式，或者判断两个命题公式是否等值。有两种方法，即真值表法和等值演算法。,例3、用两种方法证明:,证法一 用真值表法,由最后两列真值完全相同，于是命题成立。,例3、用两种方法证明:,证法二 用等值式法,蕴涵等值式,双重否定律,交换律,结合律,吸收律,例4、将下图所示的逻辑电路简化,解：将上述逻辑电路写成命题公式：,利用等值式将公式化简,分配律,结合律,等幂律,所以，该电路可
9、简化为下图 ：,第四节 联结词的全功能集,内容：联结词的全功能集，极小功能集。,了解：全功能集，极小功能集。,真值表 ：,由定义知：,真值表 ：,真值表：,二、全功能集，极小功能集。,全功能集：若干个联结词的集合，其余的联结词均可由它们表示。,最小全功能集：不含冗余联结词的全功能集。,等都是极小全功能集。,第五节 对偶与范式,内容：对偶原理，命题公式的范式。,重点：(1) 掌握对偶式，对偶原理。,(2) 掌握析取范式和合取范式的定义和求法步骤。,(3) 掌握极小项，极大项的概念及主范式的求法。,一、对偶原理。,1、对偶式。,与,2、对偶原理。,所以可得：,二、范式。,1、简单析取式，简单合取式
10、。,2、析取范式，合取范式。,为合取范式。,2、析取范式，合取范式。,为析取范式。,2、析取范式，合取范式。,求范式步骤：,(2) 否定消去或内移。,(3) 利用分配律。,(1) 消去联结词,解：原式,消去,内移,消去,上式即析取范式,解：原式,消去,内移,消去,上式即合取范式,二、范式。,求范式步骤：,(2) 否定消去或内移。,(3) 利用分配律。,(1) 消去联结词,解：原式,析取范式,析取范式,合取范式,三、主范式。,1、极小项，极大项。,都是极小项，,都是极大项，,极小项,记法,极大项,记法,2、主析取范式，主合取范式。,两种求法，等值式法和真值表法。,定理：任何命题公式的主析取范式、
11、主合取范式 都存在且都是唯一的。,步骤：,(3) 消去重复的及永假项。,解：由例1的析取范式为,解：由例1的析取范式为,步骤：,解：(1) 列真值表,解：(2) 的成真赋值有010，100，101，110，111,(3) 对应的十进制数为2，4，5，6，7,所以的主析取范式为,步骤：,(3) 消去重复的及永真项；,解：由例1，,合取范式,解：由例1，,2.4、利用真值表求命题公式的主合取范式。,步骤：,(3) 对应的十进制数为0，1，3。,由例3、例5知：,(2) 写出与(1)中极小项角码相同的极大项，,3、主范式的用途。,(1) 判断两命题公式是否等值。,(2) 判断命题公式的类型。,3、主
12、范式的用途。,(2) 判断命题公式的类型。,(3) 求成真(假)赋值。,(4) 求真值表。,的成假赋值有010，011，100，101。,解：真值表,第六节 推理规则,内容：,重点：,(1) 理解推理的概念；,(2) 掌握8条推理定律；,(3) 掌握推理规则；,(4) 掌握构造证明法。,了解：,附加前提证明法和归谬法。,一、推理的形式结构。,2、判断推理的方法。,等值演算法，真值表法，主析取范式法。,例1、判断下面各推理是否正确。,结论：,推理形式结构为：,判断此蕴涵式是否为重言式。,方法一 用等值式法。,所以推理正确。,方法二 用真值表法。,其真值表中最后一列全为1，,所以推理正确。,方法三
13、 用主析取范式法。,主析取范式含全部最小项，所以推理正确。,前提：,结论：,推理的形式结构为：,方法一,方法二,蕴涵等值式,吸收律,方法三,二、构造证明法。,1、推理定律有以下8条：,(1) 附加,(2) 化简,(3) 假言推理,(4) 拒取式,(5) 析取三段论,二、构造证明法。,1、推理定律有以下8条：,(6) 假言三段论,(7) 等价三段论,(8) 构造性二难,2、推理规则。,(1) 前提引入规则,(3) 置换规则,3、构造证明法。,依照推理规则，应用推理规律。,(2) 结论引入规则,例2、构造下列推理的证明。,证明：,前提引入,前提引入,前提引入,构造性二难,例2、构造下列推理的证明。
14、,证明：,前提引入,前提引入,拒取式,前提引入,假言推理,例2、构造下列推理的证明。,证明：,前提引入,拒取式,前提引入,析取三段论,例3、写出对应下面推理的证明。,解：,前提：,结论：,证明：,前提引入,前提引入,假言推理,前提引入,前提引入,假言推理,析取三段论,前提：,结论：,解：,前提：,结论：,证明：,前提引入,置换规则,前提引入,假言推理,前提引入,拒取式,前提：,结论：,解：,前提：,结论：,解：,前提：,结论：,证明：,前提引入,置换规则,前提引入,假言三段论,前提：,结论：,3、附加前提证明法和归谬法。,(1) 附加前提证明法。,例如：例3 (3),前提：,结论：,用附加前提
15、证明：,附加前提引入,前提引入,拒取式,例如：例3 (3),前提：,结论：,用附加前提证明：,前提引入,假言推理,化简,由附加前提证明法知推理正确。,(2) 归谬法。,因为,例如：例3 (2),前提：,结论：,用归谬法证明：,否定结论引入,前提引入,假言推理,前提引入,例如：例3 (2),前提：,结论：,用归谬法证明：,析取三段论,前提引入,合取,由归谬法知推理正确。,第一章 小结与例题,一、命题与联结词。,1、基本概念。,2、应用。,(1) 选择适当的联结词将命题符号化。,(2) 判断命题(简单或复合)的真假。,二、命题公式及分类。,1、基本概念。,2、应用。,(2) 用真值表判断给定公式的
16、类型。,三、等值演算。,1、基本概念。,两个公式等值的含义；等值演算。,2、应用。,(1) 灵活运用24个重要等值式。,四、联结词的全功能集。,基本概念,联结词的全功能集，极小全功能集。,五、对偶与范式。,1、基本概念。,五、对偶与范式。,2、应用。,(1) 求给定公式的主析取范式和主合取范式。,(4) 用主析取范式或主合取范式判断公式的类型。,六、推理理论。,1、基本概念。,推理，推理规则，推理定律；构造证明法。,2、应用。,(2) 用8条推理定律构造推理的证明。,(2) 2是素数或是合数，,(4) 只有4是奇数，5才能被3整除。,(5) 明年5月1日是晴天。,解：命题有(2)(5)，,(1
17、),解：我将进城去当且仅当我有空且天不下雪。,(2),解：虽然天正在下雪，但我将进城去。,(3),解：我进城当且仅当我有空。,(4),解：天不下雪且我没空。,(1),解：,(2),解：,(3),解：,(4),解：,例4、简化下列命题公式。,(1),解：,例4、简化下列命题公式。,(2),解：,例4、简化下列命题公式。,(3),解：,例4、简化下列命题公式。,(4),解：,(1),(2),(3),(2)为重言式，(3)为矛盾式，(1)，(2)均为可满足式。,解：先求主析取范式,解：先求主析取范式,故主合取范式为,例7、设,解：,例7、设,解：,例7、设,解：,例8、判断下列推理是否正确。,例8、判断下列推理是否正确。,以上推理即假言推理，所以是正确的。,前提：,结论：,前提引入,附加前提引入,析取三段论,前提引入,假言推理,前提：,结论：,假言推理,前提引入,假言推理,由附加前提证明法知推理正确。,例10、一公安人员审查一件盗窃案，已知的事实如下：,(1) 甲或乙盗窃了录音机；,(3) 若乙的证词正确，则午夜时屋里灯光未灭；,(4) 若乙的证词不正确，则作案时间发生在午夜之前；,(5) 午夜时屋里灯光灭了。,问是谁盗窃了录音机。,：乙盗窃了录音机，,：作案时间发生在午夜前，,：乙的证词正确，,：午夜灯光未灭。,所以是乙盗窃了录音机。,
