交大离散数学_复习课课件.ppt

重点章节：第1、2、3、5章 选择复习章节：第4、7、8章 命题是一个陈述句，或真或假，不可以既真又假。 命题是逻辑的基本构成单元 下列句子(a) ~ (e)哪个为真，哪个为假（不能既真又假） (a) 能整除7 的正整数只有1 和7 本身。 (b) 多伦多是加拿大的首都。 (c) 对于每个正整数n，存在一个大于n 的素数。 (d) 地球是宇宙中惟一存在生命的星球。 (e) 买两张星期五去“大剧院”音乐会的票。 p: 天正在下雨 q: 天很冷 p∧q: 天正在下雨 并且天很冷 p∨q: 天正在下雨或者天很冷 量化：谓词在一定范围内的取值 谓词演算：处理谓词和量词的逻辑领域 全称量词：P(x)的全称量化表示语句“P(x)对x在其论域中的所有值都为真” 存在量词：P(x)的存在量化表示语句“论域中至少有一个值满足P(x)为真” ?x0 (x20) ?x(x0 →x20) ?y≠0 (y3 ≠ 0) ?y(y≠0 →y3 ≠ 0) 全称量词的约束等价于一个条件语句的全称量化 ?z0 (z2=2) ?z(z0 ∧z2=2) 存在量词的约束等价于一个合取的存在量化 翻译语句“两个正整数的和是正数” ?x?y ((x＞0) ∧ (y ＞0) → (x+y ＞0)) 嵌套语句翻译成数学语句： 考虑命题? x ? y (x＋ y＝0) 论域为实数域。这个命题为真，因为对每个实数x，至少存在一个y（可选取y = -x），使x + y = 0为真。这个命题用文字表达为： 对每个实数x，存在一个实数y，可使x 与y 的和为零。 确定论证p q,p/∴q是否有效 如X是Y的子集但X不等于Y, 则X是Y的一个真子集 空集是任何集合的子集 定义7：集合X的所有子集的集合，称为X的幂集，用P(X)表示 如A={a,b,c} P(A)的成员：? ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c} ︱A︱=3，︱P(A) ︱=23=8 一个由两个元素组成的有序对(或序偶)，写为(a,b) (a,b)=(c,d)当且仅当a=c,b=d. 定义8：有序n元组（a1,a2,…,an）是以a1为第一个元素，a2为第二个元素，…，an为第n个元素的有序组 定义9：X,Y集合，X?Y称为X和Y的笛卡儿积，是所有有序对(x,y)的集合，其中x∈X, y∈Y。即 X?Y={(x,y)| x∈X, y∈Y} X={1,2,3} Y={a,b} X?Y={{1,a},{1,b},{2,a},{2,b},{3,a},{3,b}} Y?X={{a,1},{a,2},{a,3},{b,1},{b,2},{b,3}} X?X={{1,1},{1,2},{1,3},{2,1},{2,2},{2,3},{3,1},{3,2},{3,3}} Y?Y={{a,a},{a,b},{b,a},{b,b}} 一个由集合X的非空子集的整体组成的S，如X的每个元素都只属于S的某一个元素，S就称为X的一个划分。 证明从正整数集合到正整数集合的函数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 + 4·3n， n ≥ 0 (a) 求s0。 (b) 求s1。 (c) 求si 的公式。 (d) 求sn-1 的公式。 (e) 求sn-2 的公式。 (f) 证明序列{sn}满足 sn = 5sn-1 - 6sn-2， 对所有n≥ 2 乘积法则：假定一个过程可以被分解成两个任务，完成第一个任务有n1种方式，在第一个任务完成之后有n2种方式完成第二个任务，那么完成这个过程有n1n2种方式。 如果一种活动由连续t步组成， 第一步有n1种方法， 第二步有n2种方法， . . . 第t步有nt种方法， 那么不同的活动数目有 n1 * n2* . . . * nt 如果不允许重复，用ABCDE可以组成多少长度为4的字符串？其中有多少是以B开头的？ 1* 4 * 3 * 2 =24 如果不允许重复，用ABCDE可以组成多少长度为4的字符串？其中有多少不是以B开头的？ 4 * 4 * 3 *2 = 96 120 - 24 假设X1, . . . , Xt是集合且第i个集合有 ni个元素，如果X1, . . .