离散数学PPT

离散数学2015年3月联系方法姓名：袁堃手机：13914766289E-mail：kyuan@seu.edu.cn考核方式期末考试（开卷）平时作业：大概10次作业，分成A、B两组，每次上交一组。学习离散数学能学到什么？1、数理逻辑（Ch1、Ch2）抽象思维、严格的逻辑能力的培养2、集合论(Ch3、Ch4)是第三部分的基础3、代数结构(Ch5、Ch6)离散结构之间的关系4、图论(Ch7、Ch8、Ch9)在网络理论、信息论、控制论和计算机科学等领域有广泛的应用第1章命题逻辑1.1命题及联结词1.2命题公式与分类1.3等值演算1.4联结词全功能集1.5对偶与范式1.6推理理论1.1命题及联结词命题的定义在数理逻辑中把能判断真假的陈述句称为命题。命题的表示一般用小写英文字母或带下标的小写英文字母表示。Remark：⑴只有陈述句才有可能成为命题⑵能判断真假的陈述句⑶虽然要求命题能判断真假，但不要求现在就能确定真假，将来可以确定真假也可以。命题的真值：一个命题表达的判断结果称为命题的真值。任何命题的真值是惟一的。真值为“真”TrueT1(真)真命题真值为“假”FalseF0(假)假命题【例1.1】判断以下语句是否为命题。若是命题，确定其真值。⑴上海是个小村庄。⑵存在外星人。⑶禁止吸烟！⑷北京是中国的首都。⑸4是素数或6是素数。⑹今天你吃了吗？⑺11+1=100⑻我正在说谎。解：⑴命题(F)，⑵命题(待定)，⑶不是命题(祈使句)，⑷命题(T)，⑸命题(F)，⑹不是命题(疑问句),⑺命题(由上下文确定),⑻不是命题(悖论)。命题常量与命题变元表示命题的小写英文字母或带下标的小写英文字母常称为命题标识符。如果命题标识符表示一个具体、确定的命题，称为命题常元。如果命题标识符表示任意一个命题，称为命题变元。？命题变元是命题吗？不是命题变元代表任意的命题，其真值是不确定的。因而不是命题。简单命题与复合命题（将命题完整分类）简单命题:如果一个命题不能再分解成更简单的命题复合命题:如果一个命题不是原子命题思考：简单命题和复合命题之间有什么样的关系呢？在自然语言中，可以通过“如果…，那么…”，“不但…，而且…”这样的连词将简单的陈述句联结成复合语句，同样在命题逻辑当中，也可以通过命题联结词将简单命题联结起来表示复合命题。命题联结词常用的逻辑联结词有五种：否定、合取、析取、条件和双条件（等价）。1.否定联结词（否）设p为命题，则p的否定是一个复合命题.记作：¬p，读作“非p”或“p的否定”。定义为：若p为T，则¬p为F；若p为F，则¬p的真值为T。p¬p0110【例1.2】否定下列命题。p：中国的每一个城市都是沿海城市。¬p：??中国的每一个城市都不是沿海城市。中国的每一个城市不都是沿海城市。2.合取联结词（与）设p和q均为命题，则p和q的合取是一个复合命题记作p∧q，读作“p与q”或“p合取q”。定义：当且仅当p和q均为T时，p∧q的才为T。联结词“∧”是二元逻辑运算。pqp∧q000010100111【例1.3】(1)王晓既用功又聪明.(2)王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功.(4)张辉与王丽都是三好生.(5)张辉与王丽是同学.解令p：王晓用功，q：王晓聪明，则(1)p∧q(2)p∧q(3)q∧p.令r:张辉是三好学生，s:王丽是三好学生(4)r∧s.(5)令t:张辉与王丽是同学，t是简单命题.3.析取联结词（或者）设p和q均为命题，则p和q的析取是一个复合命题，记作p∨q，读作“p或q”或者“p析取q”。定义为：当且仅当p和q均为F时，p∨q才为F。联结词“∨”是二元逻辑运算。pqp∨q000011101111“∨”与汉语中的“或”相似，但又不相同。【例1.4】下列两个命题中的“或”，哪个是可兼或？哪个是不可兼或？⑴在电视上看这场杂技或在剧场里看这场杂技。(不可兼)⑵灯泡有故障或开关有故障。(可兼,“∨”是可兼或)4.条件联结词（如果…那么…）设p和q均为命题，其条件命题是个复合命题。记为：p→q。读作“如果p，那么q”或“若p，则q”。定义为：当且仅当p为T，q为F时，p→q才为F。pqp→q00011011p称为条件命题p→q的前件，q称为条件命题p→q的后件。联结词“→”是二元逻辑运算。【例1.4】（1）只要不下雨，我就骑自行车上班。（2）除非下雨，否则我就骑自行车上班。（3）只有不下雨，我才骑自行车上班。（4）如果下雨，我就不骑自行车上班。令p:天下雨，q:我骑自行车上班5.双条件联结词(当且仅当)设p和q均为命题，其复合命题p↔q称为双条件命题。读作：“p双条件q”或者“p当且仅当q”。定义为：当且仅当p和q的真值相同时，p↔q为T。联结词“↔”是二元逻辑运算。pqp↔q00011011双条件联结词表示的是一个充分必要关系，可以不必顾及其前因后果，而只根据联结词的定义来确定其真值。复合命题符号化：第一步：找出各简单命题，并将它们符号化第二步：用合适的联结词，把简单命题逐个联结起来例1.小王是游泳冠军或百米赛跑冠军2.小王现在在宿舍或在图书馆里3.选小王或小李中的一人当班长4.如果我上街，我就去书店看看，除非我很累r（pq）或（r∧p)q5.小王是计算机系学生，他生于1985年或1986年，他是三好学生。在对复合命题进行符号化的时候应注意：（1）具有否定意义的命题一定不是原子命题（2）对于不可兼或的表示，可用¬(p↔q)（3）联结词的优先顺序为：,,,,;如果出现的联结词同级，又无括号时，则按从左到右的顺序运算;若遇有括号时，应该先进行括号中的运算.本节学习目标：（1）理解并掌握命题的概念，学会判断一个语句是否为命题并确定其真值。（2）牢固掌握五类联结词的定义。（3）会熟练将复合命题符号化。1.2命题公式与分类把命题常量，命题变量按照一定的逻辑顺序用命题联结词连接起来就构成了命题演算的合式公式，也叫命题公式。定义1.2.1按下列规则构成的符号串称为命题演算的合式公式。（基础）⑴单个命题变元和常元是合式公式。（归纳）⑵如果A是合式公式，那么¬A是合式公式。（归纳）⑶如果A和B是合式公式，那么(A∧B)、(A∨B)、(A→B)和(A↔B)是合式公式。（界限）⑷当且仅当有限次地应用了⑴、⑵、⑶所得到的符号串是合式公式。命题公式一般的用大写的英文字母A，B，C，…表示。为方便起见，对命题公式约定如下：⑴最外层括号可以省略。⑵规定联结词的优先级由高到低依次为¬，∧，∨，→，↔。按此优先级别，如果去掉括号，不改变原公式运算次序，也可以省掉这些括号。？命题公式是命题吗？一般地说，命题公式中包含命题变元，因而无法计算其真值，所以不是命题。命题公式的真值表定义1.8设pl，p2，…，pn是出现在公式A中的全部命题变元，给pl，p2，…，pn各指定一个真值，称为对公式A的一个赋值或解释。若赋值使A的真值为T，则称这个赋值为A的成真赋值，若赋值使A的真值为F，则称这个赋值为A的成假赋值。在命题公式A中，对A的每一个赋值，就确定了A的一个真值，把它们汇列成表，称该表为命题公式A的真值表。构造真值表的几点注意：[1]先找出公式中所含的所有命题变元[2]第1行：命题变元；排列：由小到大；字典顺序[3]前n列：赋值；排列：从00…0到11…1递增【例1.7】构造命题公式¬p∨q的真值表，并求成真赋值和成假赋值。解：pq¬p¬p∨q001011100110如果公式A有n个命题变元，那么A的真值表应该有多少行？定义1.9设A是任一命题公式。⑴若对A的任意赋值，其真值永为真，则称命题公式A为重言式或永真式。⑵若对A的任意赋值，其真值永为假，则称命题公式A为矛盾式或永假式。⑶若A不是矛盾式，则称命题公式A为可满足的。命题公式的分类Remark：1.任何重言式都是可满足的。2.重言式的真值表的最后一列全为1，矛盾式的真值表的最后一列全为0，可满足的公式真值表的最后一列至少有一个1。3.亦可以用等价演算法判断公式的类型。n个命题变项能生成多少个不同的命题公式呢？1.3等值演算定义1.3.3设A和B是两个命题公式，对A和B的任一赋值，A和B的真值都相同，则称A和B等价的或逻辑相等的（也就是说），记为AB命题公式等价有下面的三条性质：⑴自反性，AA⑵对称性，若AB，则BA⑶传递性，若AB，BC，则ACAB当且仅当A↔B是重言式。所谓两个命题公式等价即为两个公式的真值表相同，所以我们可以用真值表来验证两个命题公式是否等价.【例1.12】根据等价的定义，用真值表证明p→(q→p)¬p→(p→¬q)证明：构造p→(q→p)和p→(p→q)的真值表表1.10pq¬p¬qq→pp→(q→p)p→¬q¬p→(p→¬q)00111111011001111001111111001101证明等价的另外一种方法叫做等价演算法，其基本思想是：先用真值表证明一组基本等价式，以它们为基础进行公式之间的演算。基本等价式常叫命题定律。下面是常用的命题定律。1.双重否定律A¬¬A2.交换律A∨BB∨A，A∧BB∧A3.结合律(A∨B)∨CA∨(B∨C)(A∧B)∧CA∧(B∧C)4.分配律A∧(B∨C)(A∧B)∨(A∧C)A∨(B∧C)(A∨B)∧(A∨C)5.德摩根律¬(A∨B)¬A∧¬B¬(A∧B)¬A∨¬B6.幂等律A∧AA，A∨AA7.吸收律A∨(A∧B)A，A∧(A∨B)A8.零律A∨11，A∧009.同一律A∨0A，A∧1A10.排中律A∨¬A111.矛盾律A∧¬A012.条件等价式A→B¬A∨B13.双条件等价式A↔B(A→B)∧(B→A)14.假言易位式A→B¬B→¬A15.双条件否定等价式A↔B¬A↔¬B16.归谬论(A→B)∧(A→¬B)¬A定义（子公式）如果X是合式公式A的一部分且X本身也是合式公式，则称X为公式A的子公式。例如，Aq→(p∨(p∧q))，Xp∧q，则X是A的子公式。定理1.1（置换定理）设X是合式公式A的子公式，若XY，如果将A中的X用Y来置换，得到的公式记为B，则B与A等价，即AB例1证明p(qr)(pq)r证p(qr)p(qr)（蕴涵等值式）(pq)r（结合律）(pq)r（德摩根律）(pq)r（蕴涵等值式）本小节学习目标：能熟练地应用命题定律来验证两个命题公式的等价。不可兼析取有下列性质:(1)交换律(2)结合律定义1.6.2(与非)设p和q是两个命题，复合命题p↑q称作p和q的与非。定义为：当且仅当p和q真值都是真时，p↑q才为假。由定义可以看出下式成立：p↑q¬(p∧q)表1.19pqp↑q001011101110联结词“↑”还有以下几个性质：⑴p↑p¬(p∧p)¬p⑵(p↑q)↑(p↑q)¬(p↑q)¬¬(p∧q)p∧q⑶(p↑p)↑(q↑q)(¬p)↑(¬q)¬(¬p∧¬q)p∨q定义1.6.3(或非)设p和q是两个命题，复合命题p↓q称作p和q的或非。定义为：当且仅当p、q的真值都为假时，p↓q的真值为真。表1.20pqp↓q001010100110由此定义可得：p↓q¬(p∨q)联结词↓还有下面的几个性质：⑴p↓p¬(p∨p)¬p⑵(p↓q)↓(p↓q)¬(p↓q)¬¬(p∨q)p∨q⑶(p↓p)↓(q↓q)¬p↓¬q¬(¬p∨¬q)p∧q定义1.6.4设S是一个联结词集合，如果任何n(n≥1)个变元组成的公式，都可以由S中的联结词来表示，则称S是全功能联结词集。¬，∧，∨¬，∧和¬，∨定义1.6.5(最小全功能联结词集)设S是全功能联结词集，如果去掉其中的任何联结词后，就不是全功能联结词集.¬，∧，¬，∨，↑，↓是最小全功能联结词集。n个命题变元可以构成多少个不等价的命题公式??上述问题就转化为n个命题变元构成的命题公式有多少个不同的真值表？表1.21pq公式001或0011或0101或0111或0n221.5对偶