《离散数学》讲义 - 1

离散数学,离散数学左孝凌上海科学技术文献出版社张一hangyifan考试方式：10%平时，20%期中闭卷，70%期末闭卷,离散数学,1,离散数学：研究离散量的数学特点：是现代数学的一个重要分支，计算机专业核心课程；主要研究离散量的结构和相互之间的关系；研究对象一般为有限个或可数个元素，可用于描述计算机学科研究对象离散性特点。与数据结构、操作系统、编译理论、算法分析、逻辑设计、系统结构等课程联系紧密。,离散数学,2,学习内容：数理逻辑；集合论；图论；学习方法：总体把握课程内容结构理解掌握基本概念及其间的关联了解有关重要结论的含义及应用理解掌握有关数学推导方法及应用适当习题练习,离散数学,3,离散数学,4,第一篇数理逻辑,逻辑学：研究推理的一门学科数理逻辑：用数学方法研究推理的一门数学学科-一套符号体系+一组规则,离散数学,5,数理逻辑的内容,古典数理逻辑：命题逻辑、谓词逻辑现代数理逻辑：公理化集合论、递归论、模型论、证明论,离散数学,6,第一章命题逻辑,本章重点：命题公式（命题、联结词）、命题间的关系、基于命题的推理本章难点：基于命题的推理,离散数学,7,第一章命题逻辑,命题逻辑是数理逻辑的基本组成部分，是谓词逻辑的基础。数理逻辑又名符号逻辑，是一门用数学方法研究推理过程的科学。逻辑学主要是研究各种论证。它可以是有意义的一般论证，也可以是科学理论中的数学证明或结论。建立逻辑学的主要目的在于探索出一套完整的规则，按照这些规则，就可以确定任何特定论证是否有效。这些规则，通常称为推理规则。,离散数学,8,第一章命题逻辑,在逻辑学中，与其说注重的是论证本身，不如说注重的是论证形式。同其它科学理论一样，也可以把推理理论公式化。这样，依据各项规则并使用机械方法，不难确定论证的有效性。使用这种方法进行推理时，所遵循的规则一定不能具有二义性。为了表述任何成套规则或者理论，都需要为它配置一种语言。,离散数学,9,第一章命题逻辑,具有二义性的自然语言，不可能正确地和充分地表述上述的规则或理论。为此，首先应该制定一种形式语言，或者称为客观语言。在这种形式语言中，必须明确地和严格地定义好它的语义和语法。为了避免二义性，在形式语言中将使用一些符号，并给这些符号作出明确的定义。使用符号还有另外的意义，符号很容易书写和处理。,离散数学,10,第一章命题逻辑,由于在逻辑学中使用了符号，故数理逻辑也称为符号逻辑。这一章主要是叙述形式语言的制定和分析。在开关理论和计算机的逻辑设计中，这种形式语言得到了卓有成效的应用。,离散数学,11,1-1命题,定义:能表达判断的语句，并且具有真值的陈述句真值：一个命题总是具有一个“值”，称为真值。真值只有“真”和“假”两种，分别记为T和F例：2为偶数；2比3大；注意：命题真值有时会因时因势决定如：1+1=2；明天会下雨,离散数学,12,1-1命题,命题的语句形式陈述句非命题语句：疑问句祁使句感叹句非命题陈述句：悖论语句（并不是所有陈述句都是命题，如：我正在说谎）,离散数学,13,1-1命题,说明：1.是陈述性语句，而不能是疑问句、祁使句、感叹句等；2.语句或真或假的，二者必取一，不能即真即假；3.T和F分别表示真的和假的,统称为真值，有时也用1和0分别表示它们。因为只有两种真值，所以这种逻辑有时称为二值逻辑。,离散数学,14,1-1命题-实例：说明命题的概念,中国人民是伟大的。雪是黑的。1+101=110别的星球上有生物全体立正！明天是否开大会？天气多好啊！,我正在说谎。我学英语，或着我学日语。如果天气好，那么我去散步。,离散数学,15,1-1命题,几个相关概念：原子命题不能分解成更简单的陈述语句的命题。复合命题多个原子命题由联结词和标点符号联结起来构成的命题。复合命题的真值只与原子命题的真值有关。这两种命题都有确定的真值。,离散数学,16,命题的表示法,在数理逻辑中，用大写字母：A,B,P,Q,或用带下标的大写字母或用数字如Ai,12等表示命题。P：今天下雨12：今天下雨命题标识符的分类命题常量（已知真假值）一个命题标识符表示确定的命题就称为命题常量。命题变元（真假值未知）如果命题标识符只表示任意命题的位置标志，就称为命题变元。（不是命题）指派命题变元不是命题，当命题变元P用一个特定命题取代时，P才能确定真值，这时也称对P进行指派。原子变元当命题变元表示原子命题时，改变元称为原子变元。,1-2联结词,离散数学,17,1-2联结词,复合命题是由原子命题与逻辑联结词组合而成常用的逻辑联结词主要有5个，分别表示逻辑关系中的“非”“且”“或”“如果，则”“当且仅当”等，对应的逻辑符号分别为：，,离散数学,18,离散数学,19,1-2联结词,在命题逻辑中有以下几种基本的联结词：非（），其定义可用如下真值表表示:,昆明是一个四季如春的城市。,一元运算,离散数学,20,1-2联结词,合取(),其定义可用如下真值表表示:,1.今天下雨明天下雨2.我们去看电影房间里有十张凳子,二元运算,离散数学,21,1-2联结词,析取(),其定义可用如下真值表表示,可兼或排斥或,今天我在家看电视或去剧场看戏她可能是100米或400米赛跑的冠军他昨天作了二十或三十道习题,二元运算,离散数学,22,1-2联结词,条件(),其定义可用如下真值表表示,给定两个命题P和Q，其条件命题是一个复合命题，记作PQ，读作“如果P，那么Q”或“若P则Q”。我们称P为前件，Q为后件。,二元运算,离散数学,23,1-2联结词,例题：如果某动物为哺乳动物，则它必为胎生。如果我得到这本小说，那末我今夜就读完它。如果雪是黑的，那末太阳从西方出。命题联结词“”亦可记作“”,善意的推定（可以不顾因果联系）,蕴含,离散数学,24,1-2联结词,双条件(),其定义可用如下真值表表示,给定两个命题P和Q，其复合命题PQ读作“P当切仅当Q”。也可表示为：或iff,二元运算,离散数学,25,习题1-1，1-2,P8(1)(5)bdf(6)def,1-3命题公式与翻译,离散数学,26,离散数学,27,1-3命题公式与翻译,不包含任何联结词的命题叫原子命题至少包含一个联结词的命题称作复合命题。设P和Q是任意两个命题，则：P，PQ，(PQ)(PQ)，P(QP)等都是复合命题。若P和Q是命题变元，则上述各式均称作命题公式。P和Q称作命题公式的分量。,命题公式是没有真假值的,并不是由命题变元、联结词和一些括号组成的字符串都能成为命题公式。,离散数学,28,1-3命题公式与翻译,定义1-3.1命题演算的合式公式（wff），规定为：单个命题变元本身是一个合式公式如果A式合式公式，那么A是合式公式如果A和B是合式公式，那么(AB)，(AB)，(AB)，(AB)都是合式公式。当且仅当能够有限次地应用（1），（2），（3）所得到的包含命题变元，联结词和括号的符号串是合式公式。,离散数学,29,1-3命题公式与翻译,约定：可以省略最外层括号另外根据联结词运算优先级，可以省略部分括号。，,离散数学,30,1-3命题公式与翻译,将自然语言翻译成数理逻辑中的符号形式：他既聪明又用功。除非你努力，否则你将失败。张三和李四都可以做这件事情。昆明到北京的61次列车是下午8点半或9点半开。,离散数学,31,1-3命题公式与翻译,注意：为了便于正确表达命题间的相互关系，有时采用列出“真值表”的方法，进一步分析各原命题，以此寻找逻辑联结词，使原来的命题正确地用形式符号予以表达。,离散数学,32,小结,合式公式（命题公式）及其判定自然语言的翻译（符号化形式）列出原子命题，并符号化不同的原子命题使用不同的符号，符号使用最少选择合适的联结词，根据命题表达的真实含义，而不拘泥于形式,离散数学,33,1-3命题公式与翻译,P12(2)(5)ad(7),离散数学,34,1-4真值表与等价公式,离散数学,35,1、真值表,定义1-4.1在命题公式中，对于分量指派真值的各种可能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表。,离散数学,36,1、真值表,例题2给出(PQ)P的真值表公式不论命题变元做何种指派，其真值永为假，我们把这类公式记为F。,离散数学,37,1、真值表,例题3给出(PQ)(PQ)的真值表,离散数学,38,1、真值表,例题4给出(PQ)(PQ)的真值表公式不论命题变元做何种指派，其真值永为真，我们把这类公式记为T。,离散数学,39,1、真值表列表完整性,回顾二进制n位数能够表示的数的个数排列组合真值表中，真值的数目一般来说：n个命题变元组成的命题公式共有2n种真值情况。定义14“各种组合情况”,离散数学,40,2、等价公式,PQ与PQ从真值表可见，上述两个命题公式在分量的不同指派下，其对应的真值与另一命题公式完全相同。同理如：(PQ)(PQ)与PQ。,离散数学,41,2、等价公式概念,定义：1-4.2给定两个命题公式A和B，设P1，P2，Pn为所有出现于A和B中的原子变元，若给P1，P2，Pn任一组真值指派，A和B的真值都相同，则称A和B是等价的或逻辑相等。记作AB。,离散数学,42,2、等价公式证明(真值表法),例题5证明PQ(PQ)(QP),离散数学,43,2、等价公式汇总,对合律等幂律结合律交换律分配律,吸收律德摩根律同一律零律否定律,下面的命题定理（表1-4.8）都可以用真值表予以验证:,离散数学,44,2、等价公式验证（等价公式表）,例题6验证吸收律P(PQ)PP(PQ)P,离散数学,45,2、等价公式等价置换,在一个命题公式中，如果用公式置换命题的某个部分，一般地，将会产生某种新的公式，例如：Q(P(PQ)中以(PQ)代替(PQ)，则Q(P(PQ)就与原式不同。为了保证取代后的公式与原始公式是等价的，需要对置换作出一些规定。,离散数学,46,2、等价公式等价置换（概念）,定义1-4.3如果X是合式公式A的一部分，且X本身也是一个合式公式，则称X为合式公式A的子公式。定理1-4.1设X是合式公式A的子公式，若XY，如果将A中的X用Y来置换，所得到公式B与公式A等价，即AB。,离散数学,47,命题公式证明利用等价公式,例题7证明Q(P(PQ)QP例题8证明(PQ)(PQ)P例题9证明P(QR)Q(PR)R(QP)例题10证明(PQ)(P(QR)(PQ)(PR)T,离散数学,48,小结,真值表完整性等价公式等价公式表1-4.8等价置换命题公式（合式公式）证明方法列真值表法利用等价公式强调等价公式PQPQPQ(PQ)(PQ),离散数学,49,作业,P18(2)d(4)bd(7)bdf(8)bc,1-5重言式与蕴含式,离散数学,50,离散数学,51,1、重言式概念（重言式）,定义1-5.1给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为T，则称该命题公式为重言式或永真公式。例如：表1-4.4,离散数学,52,1、重言式概念（矛盾式）,定义1-5.2给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为F，则称该命题为矛盾式或永假式。例如：表1-4.2,离散数学,53,1、重言式性质1,定理1-5.1任何两个重言式的合取或析取，仍然是一个重言式。定理1-5.2一个重言式，对同一分量都用任何合式公式置换，其结果仍为一重言式。对于矛盾式，有和定理1-5.1，定理1-5.2同样的结果。,离散数学,54,1、重言式举例,例题1证明(PS)R)(PS)R)是重言式。,离散数学,55,1、重言式性质2,定理1-5.3设A，B为两个命题公式，AB当且仅当AB为一个重言式。证明方法（从两个方面）例题2证明(PQ)(PQ),离散数学,56,2、蕴含式概念,定义1-5.3当且仅当PQ是一个重言式时，我们称“P蕴含Q”，并记作PQ。注意：PQ不是对称式逆换式：QP反换式：PQ逆反式：QP由真值表可见：PQQPQPPQ即：命题公式与其逆反式是等价的。,离散数学,57,2、蕴含式证明方法,根据蕴含式的定义：要证PQ，只需证PQ是重言式。对于PQ来说，只有P的真值取T，Q的真值取F这样一种指派时，PQ的真值为F。证明PQ是重言式方法：证法一：假设前件P为T时，导出后件Q为T。证法二：假设后件Q为F时，前件P为F。,离散数学,58,2、蕴含式证明举例,例题1推证Q(PQ)P表1-5.2（p21）理解识记（可采用上述类似方法）,离散数学,59,2、蕴含式性质1,定理1-5.4设P、Q为任意两个命题公式，PQ的充分必要条件是PQ且QP。总结两个命题公式等价的证明方法？,离散数学,60,2、蕴含式性质2,蕴含的常用性质：（1）设A、B、C为合式公式，若AB且A是重言式，则B必是重言式。（2）若AB，BC，则AC，即蕴含关系是传递的。（3）若AB，且AC，那末A(BC)。（4）若AB，CB，则(AC)B,离散数学,61,小结,重言式概念及基本性质蕴含式概念蕴含式的证明方法理解识记表1-5.2总结等价公式的证明方法,离散数学,62,作业,P23(1)bd(2)b4(b)(8)b,1-6其他联结词,离散数学,63,离散数学,64,主要介绍其他联结词,不可兼析取：条件否定：与非：或非：,离散数学,65,1、其他联结词,定义1-6.1设P和Q是两个命题公式，复合命题PQ称作P和Q的不可兼析取。PQ的真值为T，当且仅当P与Q的真值不相同时为T，否则，PQ的真值为F。性质(1)(6),离散数学,66,1、其他联结词,定理1-6.1设P、Q、R为命题公式。如果PQR，则PRQ，QRP且PQR为一矛盾式。理解、掌握证明方法，不需记忆。,离散数学,67,1、其他联结词,定义1-6.2设P和Q是两个命题公式，复合命题PQ称作命题P和Q的条件否定，PQ的真值为T，当且仅当P的真值为T，Q的真值为F，否则，PQ的真值为F。由定义可知PQ(PQ),离散数学,68,1、其他联结词、,定义1-6.3与非：当且仅当P和Q的真值都是T时，PQ为F，否则PQ的真值都为T。性质（1）（3）PQ(PQ)定义1-6.4或非，当且仅当P和Q的真值都为F时，PQ的真值为T。否则PQ的真值都为F。性质（1）（3）PQ(PQ),离散数学,69,2、最小联结词,由(PQ)(PQ)(QP)，故可把包含的公式等价变换为包含和的公式。由PQPQ，说明包含“”的公式可以变换为包含“”和“”的公式。由PQ(PQ)，PQ(PQ)。故由“”这五个联结词组成的命题公式，必可由，或，组成的命题公式所替代。,离散数学,70,2、最小联结词,对于其他一些联结词，有下列性质：PQ(PQ)PQ(PQ)PQ(PQ)PQ(PQ),离散数学,71,2、最小联结词,任意命题公式都可由仅包含，或，的命题公式等价代换。，或，为最小联接词组。（说明P28）最小联接词组亦可为或。,离散数学,72,小结,其他联结词定义理解其他联结词的一些性质最小联结词,离散数学,73,1-6其他联结词,作业：1-6P29(1)c(2)a(3),1-7对偶与范式,离散数学,74,离散数学,75,序,命题公式常常含有、中的联结词观察p15，1-4.8等价公式联结词符号的特征，找出规律。如：分配律P(QR)(PQ)(PR)P(QR)(PQ)(PR),离散数学,76,1、对偶,定义：1-7.1在给定的命题公式中，将联结词换成，将换成，若有特殊变元F和T亦互相取代，所得公式A*称为A的对偶公式。显然，A也是A*的对偶式。,离散数学,77,1、对偶举例,例题:写出下列表达式的对偶式(PQ)(P(QS)(PQ)R(PQ)TPQPQ,(PQ),(PQ),离散数学,78,1、对偶性质1,定理1-7.1：设A和A*是对偶式，P1,P2,Pn是出现在A和A*中的原子变元，则A(P1,P2,Pn)A*(P1,P2,Pn)A(P1,P2,Pn)A*(P1,P2,Pn)证明：由得摩根定律PQ(PQ),PQ(PQ)故A(P1,P2,Pn)A*(P1,P2,Pn)同理A*(P1,P2,Pn)A(P1,P2,Pn),离散数学,79,1、对偶性质1（验证）,例题3设A*(S,W,R)是S(WR)证明A*(S,W,R)A(S,W,R),离散数学,80,1、对偶性质1,定理1-7.2设P1,P2,Pn是出现在公式A和B中的所有原子变元，如果AB，则A*B*。,离散数学,81,1、对偶举例,例题4如果A(P,Q,R)是P(Q(RP)，求它的对偶式。并求与A及A*等价，但仅包含联结词”、“”、及“”的公式。,离散数学,82,2、范式定义,定义1-7.2一个命题公式称为合取范式，当且仅当它具有型式：A1A2An,(n1)其中A1,A2,An都是由命题变元或其否定所组成的析取式。定义1-7.3一个命题公式称为析取范式，当且仅当它具有型式A1A2An,(n1)其中A1,A2,An都是由命题变元或其否定所组成的合取式。,离散数学,83,2、范式求法,求析取范式或合取范式的步骤：将公式中的联结词化归成,。利用德摩根律将否定符号直接移到各个命题变元之前利用分配律、结合律将公式归约为合取范式或析取范式。,离散数学,84,1-7对偶与范式,例题5：求(P(QR)S的合取范式例题6：求(PQ)(PQ)的析取范式P(QR)(PQ)(PR)(PP)(PR)(QP)(QR)合取范式与析取范式形式不唯一。,离散数学,85,2、范式主范式（小项、大项）,定义1-7.4n个命题变元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。定义1-7.6n个命题变元的析取式，称作布尔析取或大项。其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。,离散数学,86,3、小项（大项）性质,小项有如下几个性质每一个小项当其真值指派与编码相同时，其真值为T，在其余2n-1种指派情况下均为F。任意两个不同小项的合取式永假。m001m100F全体小项的析取式永为真，记为：,大项有如下性质：每个大项当其真值指派与编码相同时，其真值为F，在其余2n-1种指派情况下均为T。任意两个不同大项的析取式为永真。MiMjT全体大项的合取式必为永假，记为：,离散数学,87,4、主析取（合取）范式及性质,定义1-7.5对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称作原式的主析取范式。定理1-7.3在真值表中，一个公式的真值为T的指派所对应的小项的析取，即为此公式的主析取范式。定义1-7.7对于给定的命题公式，如果有一个等价公式，它仅有大项的合取所组成，则该等价式称作原式的主合取范式。定理1-7.4在真值表中，一个公式的真值为F的指派所对应的大项的合取，即为此公式的主合取范式。,离散数学,88,4、主范式的求解应用举例（1）,例题6给定PQ,PQ和(PQ)，求这些公式的主析取（合取）范式。（利用真值表）例题7设一公式A的真值表如表1-7.4所示，求公式A的主析取（合取）范式。,离散数学,89,4、主范式的求解应用举例（1）,离散数学,90,4、主范式的求解应用举例（2）,也可用等价公式构成主析取（合取）范式例题8求(PQ)(PR)(QR)的主析取范式。例题9求P(PQ)(QP)的主合取范式。,离散数学,91,4、主范式的求解步骤(利用等价公式),用等价公式构成主析取范式的推演步骤为：化归为析取范式。除去析取范式中所有永假的析取项。将析取式中重复出现的合取项和相同的变元合并。对合取项补入没有出现的命题变元，即添加(PP)式，然后，应用分配律展开公式。,用等价公式构成主合取范式的推演步骤为：化归为合取范式。除去合取范式中所有永真的合取项。合并相同的析取项和相同的变元。对析取项补入没有出现的命题变元，即添加(PP)式，然后，应用分配律展开公式。,注意：命题变元个数和出现次序固定后，主析取范式是唯一的。因此，利用主析取范式可证明两个命题是否等价。,离散数学,92,5、主范式简化表示,例题10求(PQ)(PR)的主合取范式与主析取范式。主析取范式(PQR)(PQR)(PQR)(PQR)=m001m011m110m111=1,3,6,7主合取范式(PQR)(PQR)(PQR)(PQR)=M000M010M100M101=0,2,4,5,离散数学,93,5、主范式简化表示性质,可以证明，若命题公式P的主析取范式为：i1,i2,ik则P的主合取范式为0,1,2,i1-1,i1+1,ik-1,ik+1,2n-1求(PQ)(PR)的主合取范式与主析取范式。(PQ)(PR)1,3,6,70,2,4,5,离散数学,94,小结,对偶及性质析取（合取）范式及求法小项（大项）及编码和相互转换主析取（合取）范式性质及求法和简化形式,离散数学,95,作业,P39(4)acd(5)b(7),1-8推理理论,离散数学,96,离散数学,97,论证概念,在实际应用的推理中，我们常常把本门学科的一些定理、定律和条件，作为假设前提，尽管这些前提在数理逻辑中实非永真，但在推理过程中，却总是假设这些前提为T，并使用一些公认的规则，得到另外的命题，形成结论，这个过程就是论证。,离散数学,98,1、推理理论概念,定义1-8.1设A和C是两个命题公式，当且仅当AC为一重言式，即AC，称C是A的有效结论。或C可由A逻辑地推出。推广n个前提设H1,H2,Hn，C是命题公式，当且仅当H1H2HnC（A）称C是一组前提H1,H2,Hn的有效结论。判别有效结论的过程就是论证过程，基本方法有真值表法、直接证法和间接证法。,离散数学,99,2、证明方法真值表法,设P1,P2,Pn是出现于前提H1,H2,Hm和结论C中的全部命题变元，假设对P1,P2,Pn作了全部的真值指派，这样就能对应地确定H1,H2,Hm和C的所有真值，列出这个真值表，即可看出(A)式是否成立。1、看H1,H2,Hm真值均为T的行，对于每一个这样的行，若C也为T，则(A)式成立；2、看C的真值为F的行，在每一个这样的行中，H1,H2,Hm的真值中至少有一个为F，则(A)式也成立。,离散数学,100,2、证明方法真值表法（举例）,例题2：如果张老师来了，这个问题可以得到解答，如果李老师来了这个问题可以得到解答，总之张老师或李老师来了，这个问题就可得到解答。解