离散数学专题培训市公开课一等奖百校联赛特等奖课件.pptx

离散数学离散数学第1页节日高兴！节日高兴！l用数学归纳法证实哥德巴赫猜测：每个大于6偶数都是两个奇素数之和l证实P(2n),n3ln=3，6=3+3，P(6)成立。l假设for all 3kn，P(2k)成立，l现在证实P(2(n+1)成立。l第2页l7.1.2.列出集合1,2,3,4,5,6上关系R=(a,b)|a整除b中全部有序对l注意整除含义l(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)-10-8software security laboratory USTC第3页l7.1.4.确定全部些人集合上关系R是否自反，对称，传递，反对称，其中(a,b)R当且仅当l(a)a比b高l传递l(b)a和b生在同一天l自反，对称，传递 l(c)a和b同名l自反，对称，传递l(d)a和b有共同祖父母l自反，对称，传递-10-8software security laboratory USTC第4页l7.1.30.设R是关系(1,2),(1,3),(2,3),(2,4),(3,1),S是关系(2,1),(3,1),(3,2),(4,2)，求S R。l注意次序l(1,1),(1,2),(2,1),(2,2)-10-8software security laboratory USTC第5页l7.3.2(a)-10-8software security laboratory USTC第6页l7.3.4-10-8software security laboratory USTC第7页l7.3.4.-10-8software security laboratory USTC第8页l7.3.4.-10-8software security laboratory USTC第9页l7.3.14.-10-8software security laboratory USTC第10页-10-8software security laboratory USTC第11页-10-8software security laboratory USTC第12页l7.3.26.-10-8software security laboratory USTC第13页l7.4.2.-10-8software security laboratory USTC第14页l7.4.16.-10-8software security laboratory USTC第15页l7.4.22.-10-8software security laboratory USTC第16页l7.4.26.-10-8software security laboratory USTC第17页l7.4.26.-10-8software security laboratory USTC第18页l7.5.2.下面是全部些人集合上关系，其中哪些是等价关系？确定一个等价关系性质，这些性质是其它关系所欠缺。l等价关系：自反、对称、传递二元关系la)a,b)|a与b有相同年纪l是lb)a,b)|a与b有相同父母l是lc)a,b)|a与b有一个相同父亲或者一个相同母亲l否，不满足传递性，2次重组家庭。ld)a,b)|a与b相识l否，不满足传递性。le)a,b)|a与b说同一个语言l否，不满足传递性，一个人能够说各种语言。第19页l7.5.30.判断集合划分。l答案：a)和c)是划分。l7.5.32.判断集合划分。l答案：a)c)d)是划分。l7.5.48.4元集上不一样等价关系个数：15。l其实就是集合可能划分个数，同一个集合中元素等价，不一样集合中不等价。l猜测n元集不一样等价关系个数2n-1？No！第20页S上自然数次序，上自然数次序，SXS上字典次序上字典次序l7.6.4 设S=1,2,3,4，考虑通常字典次序，l(a)全部SS中小于(2,3)对l(1,1),(1,2),(1,3),(1,4),(2,1),(2,2)l(c)画出偏序集(SS,)哈塞图l注意集合元素是序对-10-8software security laboratory USTC（1，1）（1，2）（1，3）第21页l7.6.14.画出0,1,2,3,4,5上“大于或等于”关系哈塞图l注意5是“最小”元素-10-8software security laboratory USTC第22页l7.6.16.画出下述集合上整除关系哈塞图l(a)1,2,3,4,5,6 l(b)3,5,7,11,13,16,17l(c)2,3,5,10,11,15,25l(d)1,3,9,27,81,243l一些问题l层次相同元素尽可能画在一行l规划下布局，降低交叉-10-8software security laboratory USTC第23页l7.6.16.l(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-10-8software security laboratory USTC第24页l7.6.18 集合P(S)上包含关系哈塞图，其中S=a,b,c,d-10-8software security laboratory USTC第25页l7.6.22.1,2,3,4,6,12上偏序(a,b)|a整除b覆盖关系是什么。l(1,2),(1,3),(2,4),(2,6),(3,6),(4,12),(6,12)-10-8software security laboratory USTC第26页l极大元素 l,ml极小元素 a,b,cl最大元素 无l最小元素 无la,b,c全部上界，最小上界？lk,l,m 最小上界klf,g,h全部下界，最小下界？l无 无-10-8software security laboratory USTC第27页l7.6.30.给出满足下述条件偏序集l(a)有一个极小元素但没有极大元素l(N,)l(c)既没有极大元素也没有极小元素l(Z,)-10-8software security laboratory USTC第28页l7.6.36.假如偏序集子集存在最小上界话，则是唯一。l证实：假设子集存在最少两个最小上界a、b，则若a，b不满足偏序关系，则与存在最小上届矛盾。设偏序关系为，有a b或b a，故最小上届只能为a和b之一。l综上，这个最小上界是唯一。-10-8software security laboratory USTC第29页l7.6.38.下面偏序集是否为格l格：每对元素都有最小上界最大下界偏序集l(a)(1,3,6,9,12,|)l考虑9和12，不是格l(b)(1,5,25,125,|)l一个全序偏序集，是格l(c)(Z,)l是格l(d)(P(S),)l是格，最小上界是ab,最大下界ab-10-8software security laboratory USTC第30页l7.6.46.给出一个无限格例子使得l(a)既没有最小元素也没有最大元素l(Z,)l(b)有一个最小元素但没有最大元素l(N,)l(d)有一个最小元素也有一个最大元素l(1,2,)-10-8software security laboratory USTC第31页l7.6.48.确定下述偏序集是否为良序集l(a)(S,),S=10,11,12,是l(b)(Q 0,1,)l不是，如子集(0,1)没有最小元素l存在无限递减序列 1,1/2,1/4,1/8,1/2n,l(c)(S,),S是分母不超出3正有理数集合l是l(d)(Z-,)l是，最小元素是-1-10-8software security laboratory USTC第32页l7.6.50.证实最少有两个相关元素稠密偏序集不是良基。l证实：设两个相关元素为x,y且xy。因为偏序集是稠密，故存在z，使得xzy。同理对x和z，存在xz1 1,m=1e)ambm+nan|m,n=0第34页-10-8software security laboratory USTCl11-1-12.结构生成以下集合短语结构文法：a)012n|n=0。b)0n12n|n=0c)0n1m0n|m=0,n=0。答案：a)S0A,A11A,A。b)SA,A0A11,A。c)SA,A0A0,AB,B1B,B。第35页-10-8software security laboratory USTCl11-1-24.a)结构一个短语结构文法，使其生成全部形如a/b分数组成集合，其中a为带符号十进制数，b是正整数。b)给出这个文法巴克斯-诺尔范式。c)结构此文法中+311/17派生树。答案：分数带符号十进制数/正整数带符号十进制数符号 正整数符号+|-正整数非零数字 十进制数|非零数字十进制数数字|数字 十进制数数字非零数字|0非零数字1|2|3|9第36页-10-8software security laboratory USTCl11-1-27.给出C语言中生成全部标识符巴克斯-诺尔范式产生式规则。在C语言中，标识符以一个字母或者下划线开始，后跟一或多个小写字母、大些字母、下划线和数字。答案：:=|:=|_:=|:=|:=a|b|c|z:=A|B|C|Z:=0|1|2|9 第37页-10-8software security laboratory USTCl11-1-28.描述由以下EBNF产生式集合定义串集合。a)string:=L+D?L+b)string:=sign D+|D+L:=a|b|c sign:=+|-D:=0|1 D:=0|1|9c)string:=L*(D+)?L*L:=x|yD:=0|1第38页-10-8software security laboratory USTCl11-3-12.求所给确实定型有限状态机所识别语言。答案：1，01*00，1*第39页