交大离散数学复习课.ppt

复习 重点章节 第1 2 3 5章选择复习章节 第4 7 8章 考试形式 闭卷 90分钟题型 选择题 30分 15 2分 计算 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 A x BB x A x BC A x BD x A x x B3 设G是连通简单平面图 G中有11个顶点5个面 则G中的边是 A 10B 12C 16D 14 计算题1 假设p为真 q为假 并且r为真 求下列表达式的真值 1 p q r 2 p q r a 用ABCDE五个字母可以组成多少个不重复的长度为4的字符串 a 中有多少个字符串以字母B开头 考题示例 知识点提示 1逻辑与证明 6 1 2命题 命题是一个陈述句 或真或假 不可以既真又假 命题是逻辑的基本构成单元下列句子 a e 哪个为真 哪个为假 不能既真又假 a 能整除7的正整数只有1和7本身 b 多伦多是加拿大的首都 c 对于每个正整数n 存在一个大于n的素数 d 地球是宇宙中惟一存在生命的星球 e 买两张星期五去 大剧院 音乐会的票 a 真 b 假 c 真 d 不知真假 但一定是非真即假 因此是命题 e 不是命题 7 真值表 复合命题的真值可以由真值表来表达 用T代表真 F代表假 复合命题p q p q的真值由下列真值表 8 p 天正在下雨q 天很冷p q 天正在下雨并且天很冷p q 天正在下雨或者天很冷 例如 命题 天正在下雨 与 天很冷 可以连接成单一命题形式 天正在下雨与天很冷 与 和 或 的形式化定义 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翻译语句 形式化表示 只有你主修计算机科学或不是新生 才可以从校园网访问因特网 设 a 你可以从校园网访问因特网c 你主修计算机科学f 你是个新生问题 该语句的等价说法 A 如果你主修计算机科学 或者你不是新生 那么你可以从校园网访问因特网 B 如果你可以从校园网访问因特网 那么你主修了计算机科学 或者你不是新生 所以 形式化表示为 a c f 13 证明命题 p q r 与 p q p r 等价 14 1 2 3德摩根定律的运用 用德摩根律表达 麦克有一部手机和一台电脑 的否定解 p麦克有一部手机 q麦克有一台电脑那么原命题表示为 p q则其否定 p q 等价于 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 表示语句 x2 0 论域为不超过4的正整数 xP x 的真值是什么 解 论域为 1 2 3 4 P 1 P 2 P 3 为真 17 例P x 表示语句 x2 0 论域为不超过4的正整数 则 xP x 的真值是什么 解 xP x 就是合取式P 1 P 2 P 3 P 4 由于P 4 为假 所以 xP x 为假 18 1 3 5约束论域量词 x0 x x0 y 0 y3 0 y y 0 y3 0 全称量词的约束等价于一个条件语句的全称量化 z 0 z2 2 z z 0 z2 2 存在量词的约束等价于一个合取的存在量化 19 1 3 8涉及量词的逻辑等价 定义3 涉及量词的语句是逻辑等价的 当且仅当无论什么谓词代入这个语句 也不论用哪个个体论域于这些命题函数里的变量上 它们都有相同的真值 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将数学语句翻译成嵌套量词语句 翻译语句 两个正整数的和是正数 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的和为零 22 例 确定论证pq p q是否有效 注意 只要前提p q和p为真 结论q就为真 所以论证过程是有效的 23 1 5 3命题逻辑的推理规则 假言推理 分离定律 合取 拒取 附加 化简 假设 段论 析取 段论 qp q p pp q q Pq p q p q p p p q p qq r p r p q p q p q 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 反例证明法 反驳 xP x 只需在论域内找到一个x 使P x 为假 例1 5 19命题 n 2n 1 是素数 为假 反例为n 3时 23 9 不是素数 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元组 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 30 例 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 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 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是一对一的 例 定义序列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 3 计数 乘法原理 乘积法则 假定一个过程可以被分解成两个任务 完成第一个任务有n1种方式 在第一个任务完成之后有n2种方式完成第二个任务 那么完成这个过程有n1n2种方式 如果一种活动由连续t步组成 第一步有n1种方法 第二步有n2种方法 第t步有nt种方法 那么不同的活动数目有n1 n2 nt 当一活动由连续几步组成时 把每一步的方法数乘起来 例题讲解 例1用一个字母和一个不超过100的正整数给礼堂的座位编号 那么不同编号的座位最多有多少 解 给一个座位编号的过程分两个任务 从26个字母中选取一个字母 从100个正整数中选取一个整数 根据乘法原理 座位的编号方式可以有 26 100 2600种例2有多少个不同的7位二进制串 解 7位二进制串的每一位都可以有两种选择 因此有27 例 如果不允许重复 用ABCDE可以组成多少长度为4的字符串 其中有多少是以B开头的 1 4 3 2 24 例 如果不允许重复 用ABCDE可以组成多少长度为4的字符串 其中有多少不是以B开头的 4 4 3 2 96120 24 加法原理 假设X1 Xt是集合且第i个集合有ni个元素 如果X1 Xt两两不相交 则可以从X1或X2或 Xt选择元素的可能性有n1 nt 当被计数的元素可以被分解到不相交的子集时 可将每个子集的元素数相加得到总的元素数 例 由A B C D E F6人委员会要选一个主席 一个秘书 一个书记有多少种选法 如果A或B必须是主席 有多少种 如果E必须任3职之一 有多少种 如果D和F必须任职 有多少种 3 2 1鸽巢原理 定理1 如果k 1个或更多的物体放入k个盒子 那么至少有一个盒子包含了2个或更多的物体第一种形式如果n只鸽子飞入k个巢且k n 则某些巢至少有两只鸽子 解题关键 鸽子 鸽巢 一组367个人中一定至少有2个人有相同的生日 有366个不同的生日 367人 鸽子 366个生日 鸽巢 27个英文单词中一定至少有2个单词以同一个字母开始 26个英文字母如果考试给分从0 100 班上必须有多少学生才能保证这次期末考试中至少有2个学生得到相同的分数 101个分数 至少102个学生 3 2 3巧妙使用鸽巢原理 例 在30天的一个月里 某棒球队一天至少打一场比赛 但至多打45场 证明一定有连续的若干天内这个对恰好打了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 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个物体的集合允许重复的r排列数是nr 3 5 3有重复的组合 例 考虑3本书 计算机 数学 历史 每本书图书馆有6本拷贝 选择6本书有多少种可能 分析计算机 数学 历史 计算机 数学 历史 8个元素中6个 2个 的排列数 例 1 满足x1 x2 x3 x4 29的非负整数解有多少种 解 每一个解相当于从4类元素中选取29个 其中从第i类元素中选取xi个 i 1 2 3 4 29个1 4 1个 C 29 4 1 4 1 可辨别的物体 可辨别的盒子例 有多少种方式把52张标准的扑克牌发给4个人使得每人5张牌 不可辨物体 可辨的盒子例 将10个相同的球放入8个可辨别的桶 共有多少种方法 解 从8个元素的集合中取出的10组合的个数 可辨别的物体 不可辨别的盒子例 将4个不同的雇员安排在3间不可辨别的办公室 有多少种方式 其中每间办公室可以安排任意个数的雇员 解 C 4 4 C 4 3 C 4 2 C 3 1 不可辨别的物体 不可辨别的盒子例 将同一本书的6个副本放到4个相同的盒子里 其中每个盒子都能放下6个副本 5 高级计数问题 60 4 1递推关系基础 以5开始给定了某一项 3得到下一项 581114172023 a1 5an an 1 3n 2a2 a1 3 5 3 8a3 a2 3 8 3 11递推关系是由数列第n项前的若干项确定第n项 并由此确定数列 例 确定 an 是否为递推关系an 2an 1 an 2 n 2 3 4 的解 其中an 3n n是非负整数 解 2an 1 an 2 2 3 n 1 3 n 2 3n an若an 2n2an 1 an 2 2 2n 1 2n 2 2n 2n 2 an若an 5 2an 1 an 2 2 5 5 5 an 61 62 例 投资 1000 利息12 An第n年底的总金额 An An An 1 0 12 An 1 1 12An 1n 1A0 1000A3 1 12A2 1 12 1 12A1 1 12 1 12 1 12A0 1 123 1000 An 1 12An 1 1 12n 1000 通项公式 63 4 2求解线性递推关系 数列a0 a1 的通项公式an代入法定义 一个k阶常系数线性齐次递推关系 an c1an 1 c2an 2 ckan k其中c1 c2 ck是实数 ck 0例 cn 1 12cn 1是一阶线性齐次递推关系fn fn 1 fn 2是二阶线性齐次递推关系an 2an 5是5阶线性齐次递推关系an an 1 an 12不是线性的 Hn 2Hn 1 1不是齐次的 求递推关系的显示表达式an an 1 2an 2 其中a0 2 a1 7 解 递推关系的特征方程是 r2 r 2 0r1 2 r2 1因此an b 2n d 1 n根据初始条件可得 b d 22b d 7得出b 3 d 1因此an 3 2n 1 n 64 65 an 5an 1 6an 2其中a0 7a1 16 解 递推关系的特征方程为 t2 5t 6 0t 2 t 3an b2n d3n是解根据初始条件 7 a0 b20 d30 b d16 a1 b21 d31 2b 3db 5 d 2因此 an 5 2n 2 3n 66 例 鹿群n 0 200n 1 220从n 1到n的增长头数为n 2到n 1的增长头数的两倍 写出递推关系 求通项公式 解 设dn为时间n时数目d0 200 d1 220dn dn 1 2 dn 1 dn 2 递推关系 dn 3dn 1 2dn 2t2 3t 2 0r1 1 r2 2dn br1n dr2n b1n d2n200 d0 b d220 d1 b 2db 180 d 20 dn 180 20 2n 4 5 2容斥原理 A B A B A B 例 一个离散数学班包括25个计算机专业的学生 13个数学专业的学生 8个同时主修计算机和数学两个专业的学生 如果每个学生主修数学专业 计算机专业或者同时主修这两个专业 那么班里有多少个学生解 25 13 8 30 67 5关系 5 1 4关系的性质 集合X上的关系R 如果对于每个x X都有 x x R 则称R是自反的 例7 下面是集合 1 2 3 4 上的关系R1 1 1 1 2 2 1 2 2 3 4 4 1 4 4 R2 1 1 1 2 2 1 R3 1 1 1 2 1 4 2 1 2 2 3 3 4 1 4 4 R4 2 1 3 1 3 2 4 1 4 2 4 3 R5 1 1 1 2 1 3 1 4 2 2 2 3 2 4 3 3 3 4 4 4 R6 3 4 其中R3 R5是自反的 对称关系 反对称关系 集合A上的关系R 如果对于每个a b A 如 a b R必有 b a R 则称R是对称的 集合A上的关系R 如果对于每个a b A 仅当a b时 a b A有 b a R 则称R是反对称的 反对称 如果对于每个a b A 如 a b R且a b 必有 b a R 例11下列关系哪些是对称的 哪些是反对称的 R1 a b a b R2 a b a b R3 a b a b或a b R4 a b a b R5 a b a b 1 R6 a b a b 3 解 R3 R4 R6是对称的R1 R2 R4 R5是反对称的 传递关系 集合A上的关系R 如果对于每个a b c A 如 a b R 且 b c R 必有 a c R 则称R是传递的 例 正整数集合上的 整除 关系是自反的 对称的 反对称的 传递的 解 对于任意正整数a a a 自反的对于任意两个正整数 a b 如果a b 那么b不能整除a 不是对称的 是反对称的 对于三个正整数a b c 如果a b b c 那么a c 所以是传递的 例 X 1 2 3 4 到Y a b c d 的关系R 1 b 1 d 2 c 3 c 3 b 4 a 关系矩阵为 关系矩阵依赖于X和Y的顺序 例 a b c d 上的关系R a a b b c c d d b c c b 对应于顺序a b c d的矩阵是其平方是可见 只要A2的ij项非零 A的ij项就非零 所以R是传递的 76 5 4关系的闭包 R是集合A上的关系 如果存在包含R的具有性质P的关系S 并且S是包含R且具有性质P的每个关系的子集 S叫做R的关于P的闭包 自反闭包 对称闭包传递闭包 例1 整数集上的关系R a b a b 的自反闭包是什么 包含R的自反闭包是R a b a b a a a Z a b a b 集合A 1 2 3 上的关系R 1 1 1 2 2 2 2 3 3 1 3 2 不是对称的 产生一个包含关系R的尽可能小的对称关系R 1 1 1 2 2 2 2 3 3 1 3 2 2 1 1 3 R的自反闭包为 R R 1R 1 b a a b R 例 正整数集合上的关系R a b a b 的对称闭包 R R 1 a b a b b a a b a b a b 5 5等价关系基础 等价关系等价类划分 例 1 2 3 4 5 6 上的一个等价关系R 1 1 1 3 1 5 3 1 3 3 3 5 5 1 5 3 5 5 2 2 2 6 6 2 6 6 4 4 定义3 4 3 5 5 2等价关系定义1 集合X上的一个自反的 对称的和传递的关系称为X上的等价关系定义2 等价元素 a b 例 考虑 1 2 3 4 5 上的关系R 1 1 1 3 1 5 2 2 2 4 3 1 3 3 3 5 4 2 4 4 5 1 5 3 5 5 因为 1 1 2 2 3 3 4 4 5 5 R 所以R是自反的 因为只要 x y 在R中 则 y x 也在R中 所以R是对称的 最后 因为只要 x y 和 y z 在R中 则 x z 也在R中 所以R是传递的 所以R是 1 2 3 4 5 上的等价关系 例 X 1 2 3 4 5 6 上的关系R 1 1 1 3 1 5 3 1 3 3 3 5 5 1 5 3 5 5 2 2 2 6 6 2 6 6 4 4 是等价关系 包含的等价类 1 由所有使得 x 1 R的x组成 所以 1 1 3 5 类似地可以找出其余的等价类 3 5 1 3 5 2 6 2 6 4 4 5 6偏序 定义1 集合S上的关系R 如果它是自反的 反对称的 传递的 那么就称之为偏序 集合S和偏序R一起叫做偏序集 记作 S R 例 证明 大于等于 关系R是整数集合上的偏序 证明 自反的 a a反对称的 a b R a b 那么b不大于等于a 即 b a R传递的 a b b c 则a c 例 正整数集合上的 整除 关系R是偏序 自反的 反对称的和传递的 如果R是集合X上的一个偏序 有时用符号x y来表示 x y R 这个符号表示将这种关系看做X中元素的序 5 6 2字典顺序 例 确定在偏序集 Z Z 中是否有 3 5 4 8 3 8 4 5 4 9 4 11 例 1 2 3 5 1 2 4 3 例 discreet discrete discrete discretion 5 6 3哈塞图 考察 1 2 3 4 上的偏序 a b a b 的有向图一个包含足够表示偏序信息的图 哈塞图去掉换 由于传递性而出现的边 方向 默认自下向上 1 1 1 3 2 4 2 2 3 3 4 4 表示 1 2 3 4 6 8 12 上的偏序 a b a整除b 的哈塞图 5 6 4极大元素与极小元素 例 偏序集 2 4 5 10 12 20 25 的哪些元素是极大的 哪些是极小的 极大元素 12 20 25极小元素