《交大离散数学_复习课》由会员分享，可在线阅读，更多相关《交大离散数学_复习课（106页珍藏版）》请在金锄头文库上搜索。
1、复习,重点章节：第1、2、3、5章选择复习章节：第4、7、8章,考试 形式,闭卷，90分钟题型： 选择题（30分，152分）计算（50分）证明 （20分）,考题示例,选择题：1、设R 是X = 1, 2, 3, 4上的关系，x, y X，如果x y，则(x, y) R。 R = (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4,4)，则关系R 是（ ） A) 自反的、 B) 传递的、 C) 等价的 D) 对称的 2、设B是不含变元x的公式，谓词公式(x)(A(x)B)等价于（ ） A) (x)
2、(A(x)B B) (x)(A(x)B C) A(x) B D) (x)A(x)(x)B3. 设G是连通简单平面图，G中有11个顶点5个面，则G中的边是（ ）A) 10 B) 12 C) 16 D) 14,计算题1假设p为真，q为假，并且r为真，求下列表达式的真值：（1）pq r（2）pq r(a) 用ABCDE五个字母可以组成多少个不重复的长度为4的字符串？ (a)中有多少个字符串以字母B开头？,考题示例,知识点提示,1 逻辑与证明,6,1.2 命题,命题是一个陈述句，或真或假，不可以既真又假。命题是逻辑的基本构成单元下列句子(a) (e)哪个为真，哪个为假（不能既真又假）(a) 能整除7
3、的正整数只有1 和7 本身。(b) 多伦多是加拿大的首都。(c) 对于每个正整数n，存在一个大于n 的素数。(d) 地球是宇宙中惟一存在生命的星球。(e) 买两张星期五去“大剧院”音乐会的票。,(a)真 (b)假(c)真(d)不知真假，但一定是非真即假。因此是命题(e)不是命题,7,真值表,复合命题的真值可以由真值表来表达。用T 代表真，F 代表假。,复合命题pq，p q的真值由下列真值表,8,p: 天正在下雨 q: 天很冷 pq: 天正在下雨 并且天很冷 pq: 天正在下雨或者天很冷,例如：命题“天正在下雨”与“天很冷”可以连接成单一命题形式“天正在下雨与天很冷”。“与”和“或”的形式化定义
4、。,9,9,条件命题的真值表,10,例,考察： “如果今天天晴，那么我们将去海滩”只有当 今天天晴，而我们不去海滩 时，这个命题为假，否则上述命题成立。考察：“如果今天是星期五，那么2+3=5”该命题总是成立，因为2+3=5总是为真考察“如果今天是星期五，那么2+3=6”该命题 当今天不是星期五 时，成立,11,1.1.4逻辑运算符的优先级,优先级: ( ) 假设：p 真 q假 r真，给出下面每个命题的真值(p q) r(p q) rp (q r)p (q r),1.1.5 复合命题的真值表,构造真值表 (p q) (p q),12,1.1.6 翻译语句形式化表示,“只有你主修计算机科学或不是
5、新生，才可以从校园网访问因特网”设：a: 你可以从校园网访问因特网c: 你主修计算机科学 f: 你是个新生问题：该语句的等价说法（ ）：A“如果你主修计算机科学，或者你不是新生，那么你可以从校园网访问因特网”B“如果你可以从校园网访问因特网，那么你主修了计算机科学，或者你不是新生”所以，形式化表示为： a (c f),13,证明命题: p(q r)与 (pq) (pr) 等价,14,1.2.3 德摩根定律的运用,用德摩根律表达“麦克有一部手机和一台电脑”的否定解：p麦克有一部手机，q麦克有一台电脑那么原命题表示为：p q则其否定（pq）等价于 p q即：“麦克没有一部手机或没有一台电脑”用德摩
6、根律表达“John或者Jessi将去看电影”的否定解：p:John去看电影，q：Jessi去看电影那么原命题表示为：p q则其否定（p q）等价于 p q即：“John和Jessi都不去看电影”,15,16,1.3.3 量词,量化：谓词在一定范围内的取值谓词演算：处理谓词和量词的逻辑领域全称量词：P(x)的全称量化表示语句“P(x)对x在其论域中的所有值都为真”存在量词：P(x)的存在量化表示语句“论域中至少有一个值满足P(x)为真”,17,例：P(x)表示语句“x20”，论域为不超过4的正整数， x P(x)的真值是什么？解：论域为1，2，3，4，P(1),P(2),P(3)为真。,17,例
7、P(x)表示语句“x20”，论域为不超过4的正整数，则： x P(x)的真值是什么？解： x P(x)就是合取式P(1) P(2) P(3) P(4)由于P(4)为假，所以 x P(x)为假,18,1.3.5 约束论域量词,x0) x(x0) y0 (y3 0) y(y0 y3 0)全称量词的约束等价于一个条件语句的全称量化z0 (z2=2) z(z0 z2=2)存在量词的约束等价于一个合取的存在量化,19,1.3.8 涉及量词的逻辑等价,定义3：涉及量词的语句是逻辑等价的，当且仅当无论什么谓词代入这个语句，也不论用哪个个体论域于这些命题函数里的变量上，它们都有相同的真值。x(P(x) Q(x
8、)xP(x) xQ(x) x(P(x) Q(x) xP(x) xQ(x)x(P(x) Q(x)与xP(x) xQ(x)不逻辑等价x(P(x) Q(x)与 xP(x) xQ(x)不逻辑等价,19,1.3.9 否定量化词表达式,考虑语句的否定：“班里每个学生都学过微积分”即 xP(x)其中P(x)：x学过离散数学其否定：“并非班里每个学生都学过微积分”也就是：“班里有学生没有学过微积分”，即 xP(x)等价关系：xP(x) xP(x),20,21,1.4.3 将数学语句翻译成嵌套量词语句,翻译语句“两个正整数的和是正数”xy (x0) (y 0) (x+y 0)嵌套语句翻译成数学语句：考虑命题 x
9、 y (x y0)论域为实数域。这个命题为真，因为对每个实数x，至少存在一个y（可选取y = -x），使x + y = 0为真。这个命题用文字表达为：对每个实数x，存在一个实数y，可使x 与y 的和为零。,22,例,确定论证p q,p/q是否有效,注意：只要前提pq和p为真，结论q就为真。所以论证过程是有效的。,23,1.5.3命题逻辑的推理规则,假言推理/分离定律,合取,拒取,附加,化简,假设段论,析取段论,q p q_p,pp q_q,Pq _pq,pq _p,p _pq,p qq r_pr,pqp _q,pqp r _q r,消解,例,给出定理“若3n+2是奇数，则n是奇数”的证明若用直
10、接法证明，设3n+2是奇数，则存在k使得3n+2=2k+1能否从中得出n是奇数的结论？反正法：第一步：假设条件语句结论是假，即“3n+2是奇数，n不是奇数”，那么n是偶数。即：n=2k+1,第二步：根据上面的假设，则3n+2=3(2k)+2=6k+2=2(3k+1),也就是得出3n+2是偶数，这与原命题的假设“3n+2”是奇数”矛盾所以原来的条件语句为真，定理得证。,24,反例证明法,反驳x P(x)只需在论域内找到一个x，使P(x)为假。例 1.5.19命题“n (2n+1)是素数”为假。反例为n3时，239，不是素数,25,2.集合、函数、数列与求和,2.1.2 幂集,如X是Y的子集但X不
11、等于Y, 则X是Y的一个真子集空集是任何集合的子集定义7：集合X的所有子集的集合，称为X的幂集，用P(X)表示,28,28,例,如A=a,b,cP(A)的成员： ,a,b,c,a,b,a,c,b,c,a,b,cA=3，P(A) =23=8,29,2.1.3 笛卡儿积,一个由两个元素组成的有序对(或序偶)，写为(a,b)(a,b)=(c,d)当且仅当a=c,b=d.定义8：有序n元组（a1,a2,an）是以a1为第一个元素，a2为第二个元素，an为第n个元素的有序组定义9：X,Y集合，XY称为X和Y的笛卡儿积，是所有有序对(x,y)的集合，其中xX, yY。即XY=(x,y)| xX, yY,3
12、0,例,X=1,2,3 Y=a,bXY=1,a,1,b,2,a,2,b,3,a,3,bYX=a,1,a,2,a,3,b,1,b,2,b,3XX=1,1,1,2,1,3,2,1,2,2,2,3,3,1,3,2,3,3YY=a,a,a,b,b,a,b,b,31,Venn图：关于集合的形象化表示,1,2,4,3,A,B,1,2,4,3,A,B,32,划分,一个由集合X的非空子集的整体组成的S，如X的每个元素都只属于S的某一个元素，S就称为X的一个划分。,例：集合X=1,2,3,4,5,6,7,8S=1,4,5,2,6,3,7,8S是X的一个划分,2.3.2 一对一函数和映上函数,单射,满射函数,映上
13、函数,一对一的,例,证明从正整数集合到正整数集合的函数f (n) = 2n + 1是一对一的。张明：必须证明对所有正整数n1 和n2，如果f (n1) = f (n2)，则n1 = n2。 先假定f (n1) = f (n2)，依据f 的定义，将这个等式变形为 2n1 + 1 = 2n2 + 1将两边同时减1，然后同除以2，可得 n1 = n2 所以，f 是一对一的。,例,定义序列s 为 sn = 2n + 43n， n 0(a) 求s0。(b) 求s1。(c) 求si 的公式。(d) 求sn-1 的公式。(e) 求sn-2 的公式。(f) 证明序列sn满足 sn = 5sn-1 - 6sn-
14、2， 对所有n 2,3、计数,乘法原理,乘积法则：假定一个过程可以被分解成两个任务，完成第一个任务有n1种方式，在第一个任务完成之后有n2种方式完成第二个任务，那么完成这个过程有n1n2种方式。如果一种活动由连续t步组成，第一步有n1种方法，第二步有n2种方法， . . . 第t步有nt种方法，那么不同的活动数目有 n1 * n2* . . . * nt,当一活动由连续几步组成时，把每一步的方法数乘起来.,例题讲解,例1 用一个字母和一个不超过100的正整数给礼堂的座位编号。那么不同编号的座位最多有多少？解：给一个座位编号的过程分两个任务：从26个字母中选取一个字母；从100个正整数中选取一个整数。 根据乘法原理，座位的编号方式可以有： 26*100=2600种例2 有多少个不同的7位二进制串？解：7位二进制串的每一位都可以有两种选择，因此有27,
