北大离散数学chap1

《北大离散数学chap1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学主讲教师:邹复民离散数学是现代数学的一个重要分支。是计算机科学中基础理论的核心课程，为计算机科学提供了有力的理论基础和工具。离散数学的基本思想、概念和方法广泛地渗透到计算机科学与技术发展的各个领域，而且其基本理论和研究成果更是全面而系统地影响和推动着其发展。离散数学的内容十分丰富，最重要，最核心的是：数理逻辑、集合论、代数系统和图论。本课程主要讲授以上四个方面的内容。数理逻辑简介数理逻辑是用数学方法来研究推理的形式结构和推理规律的数学学科，它与数学的其它分支、计算机科学、人工智能、语言学等学科均有密切的联系。命题逻辑和一阶谓词逻辑是数理逻辑

2、中最成熟的部分，在计算机科学中应用最为广泛，其中命题逻辑是数理逻辑的最基础部分，谓词逻辑是在它的基础上发展起来的。本课程在第一，二两章中介绍数理逻辑的内容。第一章命题逻辑第一节命题符号化及联结词内容：命题，逻辑联结词，命题符号化(1)掌握命题概念(2)掌握联结词含义及真值表(3)掌握命题符号化方法重点：一、命题的概念命题：能判断真假的陈述句。例1、判断下列句子中哪些是命题。(1)北京是中国的首都。(2)雪是黑色的。(4)请把门关上！(6)地球外的星球上也有人。(3)。(5)是有理数。例1、判断下列句子中哪些是命题。(7)明天有课吗？(8)本语句是

3、假的。(9)小明和小林都是三好生。(10)小明和小林是好朋友。判断一个语句是否为命题，首先看是否为陈述句，再看其真值是否唯一。表示。命题常项，命题变项均用二、逻辑联结词。这五种常用的联结词有真值表1、“非”称为的否定式，记作例如：：11是素数；：11不是素数取值1，取值0。真值表2、“并且”称为的合取式，记作。在例1.(9)中，：小明是三好生，：小林是三好生则小明和小林是三好生表示为。(1)李平既聪明又用功。(2)李平虽然聪明，但不用功。(3)李平不但聪明，而且用功。(4)李平不是不聪明，而是不用功。例2、设：李平聪明，：李平用功。真值表3、“或者

4、”称的析取式，记作。例如，：小明学过英语，：小明学过日语，则小明学过英语或日语可表示为真值表：4、“如果那么”称的蕴涵式，记作其中为前件，为后件。例3、一位父亲对儿子说：“如果我去书店，就一定给你买本《儿童画报》。”问：什么情况下父亲食言？解：可能情况有四种：(1)父亲去了书店，给儿子买了《儿童画报》。(2)父亲去了书店，却没给儿子买《儿童画报》。(3)父亲没去书店，却给儿子买了《儿童画报》。(4)父亲没去书店，也没给儿子买《儿童画报》。(1)如果天不下雨，我就骑车上班。(2)只要天不下雨，我就骑车上班。(3)只有天不下雨，我才骑车上班。(4)除非

5、天下雨，否则我就骑车上班。(5)如果天下雨，我就不骑车上班。(或)例4、：天下雨，：我骑车上班。真值表：5、“当且仅当”称的等价式，记作。是的充要条件，也是的充要条件。例5、：，：3是奇数(1)当且仅当3是奇数。(2)当且仅当3不是奇数。(3)当且仅当3是奇数。(4)当且仅当3不是奇数。6、逻辑联结词与自然语言中联结词的关系。否定——不是，没有，非，不。合取——并且，同时，和，既…又…，不但…而且…，虽然…但是…。析取——或者，或许，可能。蕴涵——若…则…，假如…那么…，既然…那就…，倘若…就…。等价——当且仅当，充分必要，相同，一样。7、运算顺序

6、逻辑联结词也称逻辑运算符，规定优先级的顺，若有括号时，先进行括号序为内运算。例如：三、命题符号化。步骤：(1)找出各简单命题，分别符号化。(2)找出各联结词，把简单命题逐个联结起来。例6、将下列命题符号化。(1)小王是游泳冠军或百米赛跑冠军。(2)小王现在在宿舍或在图书馆。：小王是游泳冠军，：小王是百米赛跑冠军。设原语句化为。：小王在宿舍，：小王在图书馆。设原语句化为。例6、将下列命题符号化。(3)选小王或小李中的一人当班长。(4)如果我上街，我就去书店看看，除非我很累。：选小王当班长，：选小李当班长。设原语句化为。：我上街，：我很累。：我去书店看

7、看，设原语句化为)。(或(5)小丽是计算机系的学生，她生于1982或1983年，她是三好生。：小丽是计算机系的学生，：小丽生于1982年，：小丽生于1983年，：小丽是三好生。设原语句化为。第二节命题公式及分类内容：命题公式，重言式，矛盾式，可满足公式。重点：(1)掌握命题公式的定义及公式的真值表。(2)掌握重言式和矛盾式的定义及使用真值表进行判断。一、命题公式通俗地说，命题公式是由命题常项，命题变项，联结词，括号等组成的字符串。规定：公式中最外层的括号，及的括号可省略。例1、判断以下字符串中哪些是命题公式。(1)(2)(3)(4)(5)(6)解：

8、(1)、(2)、(6)是公式，(3)、(4)、(5)不是。2、命题公式的层次。5例2、为___层公式。若的最高层次为，则称