交大离散数学复习课.ppt
《交大离散数学复习课.ppt》由会员分享,可在线阅读,更多相关《交大离散数学复习课.ppt(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)
2、 (x) (A(x)B B) (x)(A(x)B C) A(x) B D) (x)A(x)(x)B 3. 设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)哪个为真,哪个为假(不能既
3、真又假) (a) 能整除7 的正整数只有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) r p (q r) p (q r),1.1.5 复合命题的真值表,构造真值表 (p q) (p q)
5、,12,1.1.6 翻译语句形式化表示,“只有你主修计算机科学或不是新生,才可以从校园网访问因特网” 设:a: 你可以从校园网访问因特网 c: 你主修计算机科学 f: 你是个新生 问题:该语句的等价说法( ): A“如果你主修计算机科学,或者你不是新生,那么你可以从校园网访问因特网” B“如果你可以从校园网访问因特网,那么你主修了计算机科学,或者你不是新生” 所以,形式化表示为: a (c f),13,证明命题: p(q r)与 (pq) (pr) 等价,14,1.2.3 德摩根定律的运用,用德摩根律表达“麦克有一部手机和一台电脑”的否定 解:p麦克有一部手机,q麦克有一台电脑 那么原命题表示
6、为:p q 则其否定(pq)等价于 p q 即:“麦克没有一部手机或没有一台电脑” 用德摩根律表达“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的
7、正整数, x P(x)的真值是什么? 解:论域为1,2,3,4,P(1),P(2),P(3)为真。,17,例 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:涉及量词的语句是逻辑等价的,
8、当且仅当无论什么谓词代入这个语句,也不论用哪个个体论域于这些命题函数里的变量上,它们都有相同的真值。 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)不逻辑等价 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 将
9、数学语句翻译成嵌套量词语句,翻译语句“两个正整数的和是正数” xy (x0) (y 0) (x+y 0) 嵌套语句翻译成数学语句: 考虑命题 x 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,p p q _ q
10、,P q _ pq,pq _ p,p _ pq,p q q r _ pr,pq p _ q,pq p r _ q r,消解,例,给出定理“若3n+2是奇数,则n是奇数”的证明 若用直接法证明,设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)
11、只需在论域内找到一个x,使P(x)为假。 例 1.5.19 命题 “n (2n+1)是素数”为假。 反例为n3时,239,不是素数,25,2.集合、函数、数列与求和,2.1.2 幂集,如X是Y的子集但X不等于Y, 则X是Y的一个真子集 空集是任何集合的子集 定义7:集合X的所有子集的集合,称为X的幂集,用P(X)表示,28,28,例,如A=a,b,c P(A)的成员: ,a,b,c,a,b,a,c,b,c,a,b,c A=3,P(A) =23=8,29,2.1.3 笛卡儿积,一个由两个元素组成的有序对(或序偶),写为(a,b) (a,b)=(c,d)当且仅当a=c,b=d. 定义8:有序n元组
12、(a1,a2,an)是以a1为第一个元素,a2为第二个元素,an为第n个元素的有序组 定义9:X,Y集合,XY称为X和Y的笛卡儿积,是所有有序对(x,y)的集合,其中xX, yY。即 XY=(x,y)| xX, yY,30,例,X=1,2,3 Y=a,b XY=1,a,1,b,2,a,2,b,3,a,3,b YX=a,1,a,2,a,3,b,1,b,2,b,3 XX=1,1,1,2,1,3,2,1,2,2,2,3,3,1,3,2,3,3 YY=a,a,a,b,b,a,b,b,31,Venn图:关于集合的形象化表示,1,2,4,3,A,B,1,2,4,3,A,B,32,划分,一个由集合X的非空子
13、集的整体组成的S,如X的每个元素都只属于S的某一个元素,S就称为X的一个划分。,例: 集合X=1,2,3,4,5,6,7,8 S=1,4,5,2,6,3,7,8 S是X的一个划分,2.3.2 一对一函数和映上函数,单射,满射函数,映上函数,一对一的,例,证明从正整数集合到正整数集合的函数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 是一
14、对一的。,例,定义序列s 为 sn = 2n + 43n, n 0 (a) 求s0。 (b) 求s1。 (c) 求si 的公式。 (d) 求sn-1 的公式。 (e) 求sn-2 的公式。 (f) 证明序列sn满足 sn = 5sn-1 - 6sn-2, 对所有n 2,3、计数,乘法原理,乘积法则:假定一个过程可以被分解成两个任务,完成第一个任务有n1种方式,在第一个任务完成之后有n2种方式完成第二个任务,那么完成这个过程有n1n2种方式。 如果一种活动由连续t步组成, 第一步有n1种方法, 第二步有n2种方法, . . . 第t步有nt种方法, 那么不同的活动数目有 n1 * n2* . .
15、 . * nt,当一活动由连续几步组成时,把每一步的方法数乘起来.,例题讲解,例1 用一个字母和一个不超过100的正整数给礼堂的座位编号。那么不同编号的座位最多有多少? 解:给一个座位编号的过程分两个任务: 从26个字母中选取一个字母; 从100个正整数中选取一个整数。 根据乘法原理,座位的编号方式可以有: 26*100=2600种 例2 有多少个不同的7位二进制串? 解:7位二进制串的每一位都可以有两种选择,因此有 27,例,如果不允许重复,用ABCDE可以组成多少长度为4的字符串?其中有多少是以B开头的? 1* 4 * 3 * 2 =24,例,如果不允许重复,用ABCDE可以组成多少长度为
16、4的字符串?其中有多少不是以B开头的? 4 * 4 * 3 *2 = 96 120 - 24,加法原理,假设X1, . . . , Xt是集合且第i个集合有 ni个元素,如果X1, . . . , Xt两两不相交,则可以从X1或X2或 . . . Xt选择元素的可能性有 n1 + . . . +nt,当被计数的元素可以被分解到不相交的子集时,可将每个子集的元素数相加得到总的元素数.,例,由A、B、C、D、E、F 6人委员会要选一个主席,一个秘书,一个书记 有多少种选法? 如果A或B必须是主席,有多少种? 如果E必须任3职之一,有多少种? 如果D和F必须任职,有多少种?,3.2.1 鸽巢原理,定
17、理1:如果k+1个或更多的物体放入k个盒子,那么至少有一个盒子包含了2个或更多的物体 第一种形式 如果n只鸽子飞入k个巢且kn,则某些巢至少有两只鸽子。 解题关键: 鸽子? 鸽巢?,一组367个人中一定至少有2个人有相同的生日。 有366个不同的生日。 (367人鸽子,366个生日鸽巢) 27个英文单词中一定至少有2个单词以同一个字母开始。 26个英文字母 如果考试给分从0100,班上必须有多少学生才能保证这次期末考试中至少有2个学生得到相同的分数? 101个分数,至少102个学生,3.2.3 巧妙使用鸽巢原理,例:在30天的一个月里,某棒球队一天至少打一场比赛,但至多打45场。证明一定有连续
18、的若干天内这个对恰好打了14场。 解:令aj是第j天之前(包括第j天)所打的场数, 则a1,a2,a30是严格递增序列,且1 aj 45 那么 a1+14, a2+14,a30+14也是严格递增的,且14 aj +14 59 则:在1,59 的60个正整数 a1,a2,a30, a1+14, a2+14,a30+14 根据鸽巢原理,必然有两个正整数相等。 aj +14=ai 也就是说:从第j+1天到第i天,恰好打了14场,3.3.2 排列,n个不同的元素 x1, . . . xn的一个排列就是这n个元素的一个次序。 定理:具有n个不同元素的集合的r排列是 P(n,r)=n(n-1)(n-2)(
19、n-r+1) 推论:如果n和r都是整数,且1 r n ,则,例,字母ABCDEF中有多少个包含DEF的排列?,A,B,C,DEF,例,字母ABCDEF中有多少个包含DEF任意顺序的排列?,A,B,C,DEF,3! * 4!,3.3.3 组合,不考虑顺序的对象的选取叫做组合,例,5个学生想和校长谈奖学金的事,校长办公室安排3个人去谈,问有多少种方法从5选3? C(5,3)= 10,3.5 广义的排列组合,有重复元素 允许重复元素 多重集 的排列组合问题,3.5.2 有重复的排列,当元素允许重复时,使用乘积法则很容易计数排列数 例:用英文字母可以构成多少个r位字符串 26r 定理:具有n个物体的集
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 交大 离散数学 复习
链接地址:https://www.31doc.com/p-3139745.html