《离散数学.ppt》由会员分享，可在线阅读，更多相关《离散数学.ppt（39页珍藏版）》请在三一文库上搜索。
1、离散数学,节日快乐！,用数学归纳法证明哥德巴赫猜想：每个不小于6的偶数都是两个奇素数之和 证明P(2n), n3 n=3，6=3+3，P(6)成立。 假设for all 3kn，P(2k)成立， 现在证明P(2(n+1)成立。 ,7.1.2 . 列出集合1,2,3,4,5,6上的关系R=(a,b)|a整除b中所有的有序对 注意整除的含义 (1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6),2008-10-8,software security laboratory USTC,7.
2、1.4. 确定所有人的集合上的关系R是否自反，对称，传递，反对称，其中(a,b) R当且仅当 (a)a比b高 传递 (b)a和b生在同一天 自反，对称，传递 (c)a和b同名 自反，对称，传递 (d)a和b有共同的祖父母 自反，对称，传递,2008-10-8,software security laboratory USTC,7.1.30. 设R是关系(1,2),(1,3),(2,3),(2,4),(3,1), S是关系(2,1),(3,1),(3,2),(4,2)，求S R。 注意顺序 (1,1),(1,2),(2,1),(2,2),2008-10-8,software security l
3、aboratory USTC,7.3.2 (a),2008-10-8,software security laboratory USTC,7.3.4,2008-10-8,software security laboratory USTC,7.3.4.,2008-10-8,software security laboratory USTC,7.3.4.,2008-10-8,software security laboratory USTC,7.3.14.,2008-10-8,software security laboratory USTC,2008-10-8,software security
4、 laboratory USTC,2008-10-8,software security laboratory USTC,7.3.26.,2008-10-8,software security laboratory USTC,7.4.2.,2008-10-8,software security laboratory USTC,7.4.16.,2008-10-8,software security laboratory USTC,7.4.22.,2008-10-8,software security laboratory USTC,7.4.26.,2008-10-8,software secur
5、ity laboratory USTC,7.4.26.,2008-10-8,software security laboratory USTC,7.5.2. 下面是所有人集合上的关系，其中哪些是等价关系？确定一个等价关系的性质，这些性质是其他关系所欠缺的。 等价关系：自反、对称、传递的二元关系 a) a, b) | a与b有相同的年龄 是 b) a, b) | a与b有相同的父母 是 c) a, b) | a与b有一个相同的父亲或者一个相同的母亲 否，不满足传递性，2次重组的家庭。 d) a, b) | a与b相识 否，不满足传递性。 e) a, b) | a与b说同一种语言 否，不满足传递性
6、，一个人可以说多种语言。,7.5.30. 判断集合划分。 答案：a)和c)是划分。 7.5.32. 判断集合划分。 答案：a) c) d)是划分。 7.5.48. 4元集上的不同等价关系个数：15。 其实就是集合可能的划分个数，同一个集合中的元素等价，不同集合中的不等价。 猜想n元集的不同等价关系个数2n-1？No！,S上自然数顺序，SXS上字典顺序,7.6.4 设S=1,2,3,4，考虑通常的字典顺序， (a)所有SS中小于(2,3)的对 (1,1),(1,2),(1,3),(1,4),(2,1),(2,2) (c) 画出偏序集(SS, )的哈塞图 注意集合的元素是序对,2008-10-8,
7、software security laboratory USTC,（1，1）,（1，2）,（1，3）,7.6.14. 画出0,1,2,3,4,5上“大于或等于”关系的哈塞图 注意5是“最小”的元素,2008-10-8,software security laboratory USTC,7.6.16. 画出下述集合上整除关系的哈塞图 (a) 1,2,3,4,5,6 (b) 3,5,7,11,13,16,17 (c) 2,3,5,10,11,15,25 (d) 1,3,9,27,81,243 一些问题 层次相同的元素尽量画在一行 规划下布局，减少交叉,2008-10-8,software sec
8、urity laboratory USTC,7.6.16. (a) 4 6 (b) 3 5 7 11 13 16 17 2 3 5 243 1 81 (c) 10 25 15 (d) 27 2 5 3 11 9 3 1,2008-10-8,software security laboratory USTC,7.6.18 集合P(S)上包含关系的哈塞图，其中S=a,b,c,d,2008-10-8,software security laboratory USTC,7.6.22. 1,2,3,4,6,12上的偏序(a,b)|a整除b的覆盖关系是什么。 (1,2),(1,3),(2,4),(2,6)
9、,(3,6),(4,12),(6,12),2008-10-8,software security laboratory USTC,极大元素 l,m 极小元素 a,b,c 最大元素 无 最小元素 无 a,b,c的所有上界，最小上界？ k,l,m 最小上界k f,g,h的所有下界，最小下界？ 无 无,2008-10-8,software security laboratory USTC,7.6.30. 给出满足下述条件的偏序集 (a)有一个极小元素但没有极大元素 (N,) (c)既没有极大元素也没有极小元素 (Z,),2008-10-8,software security laboratory U
10、STC,7.6.36. 如果偏序集的子集存在最小上界的话，则是唯一的。 证明：假设子集存在至少两个最小上界a、b，则若a，b不满足偏序关系，则与存在最小上届矛盾。设偏序关系为，有a b或b a，故最小上届只能为a和b之一。 综上，这个最小上界是唯一的。,2008-10-8,software security laboratory USTC,7.6.38. 下面的偏序集是否为格 格：每对元素都有最小上界最大下界的偏序集 (a) (1,3,6,9,12, |) 考虑9和12，不是格 (b) (1,5,25,125, |) 一个全序的偏序集，是格 (c) (Z, ) 是格 (d) (P(S), )
11、是格，最小上界是ab,最大下界ab,2008-10-8,software security laboratory USTC,7.6.46. 给出一个无限格的例子使得 (a)既没有最小元素也没有最大元素 (Z,) (d)有一个最小元素也有一个最大元素 (1,2,),2008-10-8,software security laboratory USTC,7.6.48. 确定下述偏序集是否为良序集 (a) (S, ),S=10,11,12, 是 (b) (Q 0,1, ) 不是，如子集(0,1)没有最小元素 存在无限递减序列 1,1/2,1/4,1/8, , 1/2n, (c) (S, ), S是分
12、母不超过3的正有理数集合 是 (d) (Z-, ) 是，最小元素是-1,2008-10-8,software security laboratory USTC,7.6.50. 证明至少有两个相关元素的稠密的偏序集不是良基的。 证明：设两个相关元素为x,y且xy。因为偏序集是稠密的，故存在z，使得xzy。同理对x和z，存在xz1z。这样迭代可以得到一个无限的递减序列，故不是良基的。,2008-10-8,software security laboratory USTC,2008-10-8,software security laboratory USTC,11-1-4. 设V=S,A,B,a,b
13、, T=a,b。当产生式集为下列情形之一时，求文法V,T,S,P生成的语言。 a) SAB, Aab, Bbb。 b) SAB, SaA, Aa, Bba。 c) SAB, SAA, AaB, Aab, Bb。 d) SAA, SB, AaaA, Aaa, BbB, Bb。 e) SAB, AaAb, BbBa, A, B 。 答案： a) abbb b) aba, aa c) abb, abab d) a2n , bm | n 1, m = 1 e) ambm+nan | m, n = 0,2008-10-8,software security laboratory USTC,11-1-12
14、. 构造生成下列集合的短语结构文法： a) 012n | n=0。 b) 0n12n | n=0 c) 0n1m0n | m=0, n=0。 答案： a) S0A, A11A, A。 b) SA, A0A11, A。 c) SA, A0A0, AB, B1B, B。,2008-10-8,software security laboratory USTC,11-1-24. a) 构造一个短语结构文法，使其生成所有形如a/b的分数构成的集合，其中a为带符号十进制数，b是正整数。b) 给出这个文法的巴克斯-诺尔范式。c) 构造此文法中+311/17的派生树。 答案： 分数带符号十进制数 / 正整数
15、带符号十进制数符号 正整数 符号+ | - 正整数非零数字 十进制数 | 非零数字 十进制数数字 | 数字 十进制数 数字非零数字 | 0 非零数字1 | 2 | 3 | | 9,2008-10-8,software security laboratory USTC,11-1-27. 给出C语言中生成所有标识符的巴克斯-诺尔范式产生式规则。在C语言中，标识符以一个字母或者下划线开始，后跟一或多个小写字母、大些字母、下划线和数字。 答案： := | := | _ := | := | := a | b | c | | z := A | B | C | | Z := 0 | 1 | 2 | | 9,
16、2008-10-8,software security laboratory USTC,11-1-28. 描述由下列EBNF产生式集合定义的串的集合。 a) string := L+D?L+ b) string := sign D+ | D+ L := a | b | c sign := + | - D := 0 | 1 D := 0 | 1 | | 9 c) string := L* (D+)? L* L := x | y D := 0 | 1,2008-10-8,software security laboratory USTC,11-3-12. 求所给的确定型有限状态机所识别的语言。 答案： 1，01*00，1*,