北大离散数学chap1

离散数学主讲教师:邹复民离散数学是现代数学的一个重要分支。是计算机科学中基础理论的核心课程，为计算机科学提供了有力的理论基础和工具。离散数学的基本思想、概念和方法广泛地渗透到计算机科学与技术发展的各个领域，而且其基本理论和研究成果更是全面而系统地影响和推动着其发展。离散数学的内容十分丰富，最重要，最核心的是：数理逻辑、集合论、代数系统和图论。本课程主要讲授以上四个方面的内容。数理逻辑简介数理逻辑是用数学方法来研究推理的形式结构和推理规律的数学学科，它与数学的其它分支、计算机科学、人工智能、语言学等学科均有密切的联系。命题逻辑和一阶谓词逻辑是数理逻辑中最成熟的部分，在计算机科学中应用最为广泛，其中命题逻辑是数理逻辑的最基础部分，谓词逻辑是在它的基础上发展起来的。本课程在第一，二两章中介绍数理逻辑的内容。第一节命题符号化及联结词内容：命题，逻辑联结词，命题符号化(1)掌握命题概念(2)掌握联结词含义及真值表(3)掌握命题符号化方法重点：一、命题的概念命题：能判断真假的陈述句。TF真（记为或1）真值假（记为或0）例1、判断下列句子中哪些是命题。(1)北京是中国的首都。(2)雪是黑色的。(4)请把门关上！(6)地球外的星球上也有人。3412(3)。x(5)是有理数。例1、判断下列句子中哪些是命题。(7)明天有课吗？(8)本语句是假的。(9)小明和小林都是三好生。(10)小明和小林是好朋友。判断一个语句是否为命题，首先看是否为陈述句，再看其真值是否唯一。,,,,,,iiipqrpqr表示。命题常项，命题变项均用二、逻辑联结词。简单命题（不能再分解成更简单的命题）命题复合命题（由简单命题用联结词联结而成的命题）,,,,这五种常用的联结词有真值表ppp1、“非”称为的否定式，记作pp例如：：11是素数；：11不是素数pp取值1，取值0。真值表pq,pqpq2、“并且”称为的合取式，记作。pqpq在例1.(9)中，：小明是三好生，：小林是三好生则小明和小林是三好生表示为。(1)李平既聪明又用功。pq(2)李平虽然聪明，但不用功。pq(3)李平不但聪明，而且用功。pq(4)李平不是不聪明，而是不用功。()pqpq例2、设：李平聪明，：李平用功。真值表pq,pqpq3、“或者”称的析取式，记作。pqpq例如，：小明学过英语，：小明学过日语，则小明学过英语或日语可表示为真值表：pq,pqpqpq4、“如果那么”称的蕴涵式，记作其中为前件，为后件。例3、一位父亲对儿子说：“如果我去书店，就一定给你买本《儿童画报》。”问：什么情况下父亲食言？解：可能情况有四种：(1)父亲去了书店，给儿子买了《儿童画报》。(2)父亲去了书店，却没给儿子买《儿童画报》。(3)父亲没去书店，却给儿子买了《儿童画报》。(4)父亲没去书店，也没给儿子买《儿童画报》。(1)如果天不下雨，我就骑车上班。pq(2)只要天不下雨，我就骑车上班。pq(3)只有天不下雨，我才骑车上班。(4)除非天下雨，否则我就骑车上班。pq(5)如果天下雨，我就不骑车上班。pqqp(或)pqpq例4、：天下雨，：我骑车上班。真值表：pq,pqpq5、“当且仅当”称的等价式，记作。ppqq是的充要条件，也是的充要条件。pqpqpqpq224pq例5、：，：3是奇数224(1)当且仅当3是奇数。224(2)当且仅当3不是奇数。224(3)当且仅当3是奇数。224(4)当且仅当3不是奇数。6、逻辑联结词与自然语言中联结词的关系。否定——不是，没有，非，不。合取——并且，同时，和，既…又…，不但…而且…，虽然…但是…。析取——或者，或许，可能。蕴涵——若…则…，假如…那么…，既然…那就…，倘若…就…。等价——当且仅当，充分必要，相同，一样。7、运算顺序逻辑联结词也称逻辑运算符，规定优先级的顺,,,,，若有括号时，先进行括号序为内运算。()()pqpqrq例如：三、命题符号化。步骤：(1)找出各简单命题，分别符号化。(2)找出各联结词，把简单命题逐个联结起来。例6、将下列命题符号化。(1)小王是游泳冠军或百米赛跑冠军。(2)小王现在在宿舍或在图书馆。：小王是游泳冠军，p：小王是百米赛跑冠军。q设原语句化为pq。：小王在宿舍，p：小王在图书馆。q设原语句化为pq。例6、将下列命题符号化。(3)选小王或小李中的一人当班长。(4)如果我上街，我就去书店看看，除非我很累。：选小王当班长，p：选小李当班长。q设原语句化为()()pqpq。：我上街，pq：我很累。r：我去书店看看，设原语句化为()rpq()rpq)。(或(5)小丽是计算机系的学生，她生于1982或1983年，她是三好生。：小丽是计算机系的学生，：小丽生于1982年，：小丽生于1983年，：小丽是三好生。pqrs设原语句化为()pqrs。第二节命题公式及分类内容：命题公式，重言式，矛盾式，可满足公式。重点：(1)掌握命题公式的定义及公式的真值表。(2)掌握重言式和矛盾式的定义及使用真值表进行判断。一、命题公式通俗地说，命题公式是由命题常项，命题变项，联结词，括号等组成的字符串。规定：公式中最外层的括号，及()A的括号可省略。例1、判断以下字符串中哪些是命题公式。(1)()pqr()pqr(2)pqr(3)(4)(pqr(5)pq(6)()pqr解：(1)、(2)、(6)是公式，(3)、(4)、(5)不是。2、命题公式的层次。5ppqrpr例2、为___层公式。kAAk若的最高层次为，则称为层公式。3、真值表。AA成真赋值（使为真的赋值）赋值成假赋值（使为假的赋值），()Apqr1,1,0pqrAA如公式，110(按字典序)为的成假赋值，111，011，010……等是的成真赋值。个命题变项的命题公式，共有(1)nn2n含组不同赋值。A公式的解释或赋值3、真值表。(3)对应每个赋值，计算各层次的值，直至整个公式。的真值表——指AA在所有赋值之下取值列成的表。构造A的真值表步骤：(1)列出所有命题变项的所有赋值(2,3n2n个，掌握)。(2)从低到高写出A的各层次。例3、求下列命题公式的真值表。(1)()qpp解：例3、求下列命题公式的真值表。(2)()()pqqp解：二、重言式、矛盾式，可满足式。重言式可满足式命题公式其它矛盾式2、判定方法:真值表法。1、定义例4、给定命题公式如下，请判断哪些是重言式，哪些是矛盾式，哪些是可满足式？(1)()()pqpq(2)()pqpqqp(3)()pqq(4)()ppq(5)()ppq例4、给定命题公式如下，请判断哪些是重言式，哪些是矛盾式，哪些是可满足式？(6)pqpp(7)()()pqpq(8)()ppqqr(9)()()pqrpqr(10)()pqr解：列出各题真值表如下(步骤简略)(1)、(2)、(5)、(6)、(9)为重言式；(3)、(8)为矛盾式；(4)、(7)、(10)及以上的重言式均为可满足式。第三节等值演算内容：等值关系，24个重要等值式，等值演算。重点：(1)掌握两公式等值的定义。(2)掌握24个重要等值式，并能利用其进行等值演算。一、两命题公式间的等值关系。2、判定。,ABABABAB1、定义：设为两命题公式，若等价式是重言式，则称与是等值的，记作。,ABAB是否重言式。是否等值，即判断判断两公式(1)，()ApqBpq解：作真值表如下：例1、判断,AB两公式是否等值。解：作真值表如下：(2)，Apq()()Bpqqp例1、判断,AB两公式是否等值。二、重要等值式。2、结合律()()ABCABC()()ABCABC，3、分配律()()()ABCABAC()()()ABCABAC，1、交换律ABBAABBA，二、重要等值式。4、德摩根律()ABAB()ABAB，6、吸收律()AABA()AABA，5、等幂律AAAAAA，二、重要等值式。10、双重否定律()AA9、互否律1AA0AA(矛盾律)(排中律)，7、零律11A00A，8、同一律0AA1AA，二、重要等值式。11、蕴涵等值式ABAB12、等价等值式()()ABABBA13、假言易位ABBA14、等价否定等值式ABAB15、归谬论()()ABABA三、等值演算。例2、验证下列等值式。(1)()()pqrpqr(2)()()pqrpqrqr(3)()1qpqp置换定理：如果AB()()AB。，则例2、验证下列等值式。(1)()()pqrpqr解：()pqr()pqr蕴涵等值式()pqr蕴涵等值式()pqr结合律()pqr德摩根律()pqr蕴涵等值式例2、验证下列等值式。(2)()()pqrpqrqr()()pqrpqr解：()()qrpqrp交换律()()qrpp分配律()1qr排中律qr同一律(3)()1qpqp解：()qpqp()()qppqp分配律0()qqp矛盾律()qqp同一律()qqp德摩根律()qqp结合律1p排中律1零律考虑问题:能否利用等值式来化简，或判断公式的类型(重言，矛盾，可满足)。判断一个公式是否重言式，矛盾式，可满足式，或者判断两个命题公式是否等值。有两种方法，即真值表法和等值演算法。例3、用两种方法证明:()()pqpqpq[证法一]用真值表法由最后两列真值完全相同，于是命题成立。例3、用两种方法证明:()()pqpqpq[证法二]用等值式法()()pqpqpqpq蕴涵等值式()()pqpq双重否定律()()pqpq交换律pqpq结合律pq吸收律例4、将下图所示的逻辑电路简化rqp解：将上述逻辑电路写成命题公式：pqprqr利用等值式将公式化简pqprqrpqrqr分配律pqrqr结合律()pqr等幂律所以，该电路可简化为下图：rqp第四节联结词的全功能集内容：联结词的全功能集，极小功能集。了解：全功能集，极小功能集。真值表：由定义知：()()pqpqpq一、联结词,,。,pq,pq记作pq1、“的排斥或(异或)，之间恰有一个成立”称。真值表：()pqpq的与非式，记作pq,pqpq并且2、“的否定”称。真值表：()pqpq的或非式，记作pq,pqpq3、“或者的否定”称。二、全功能集，极小功能集。全功能集：若干个联结词的集合，其余的联结词均可由它们表示。最小全功能集：不含冗余联结词的全功能集。{,,,,},{,,,,},{,}例如：等都是全功能集。{,},{,},{},{}等都是极小全功能集。第五节对偶与范式内容：对偶原理，命题公式的范式。重点：(1)掌握对偶式，对偶原理。(2)掌握析取范式和合取范式的定义和求法步骤。(3)掌握极小项，极大项的概念及主范式的求法。一、对偶原理。1、对偶式。pq例如：与pq，与，