离散数学 练习题及答案ppt课件

2020/6/12,总复习,1of65,例3给出下列公式的真值表,成真指派：100，101，110，111,2020/6/12,总复习,2of65,例4,试求下面公式的主析取（主合取）范式，并写出成真指派和成假指派。,成真指派：00，10，11成假指派：01,2020/6/12,总复习,3of65,例5试证,证明,2020/6/12,总复习,4of65,例1符号化下列命题,a)不是所有的男人都比女人高。M(x):x是男人，W(x):x是女人，H(x,y):x比y高。,2020/6/12,总复习,5of65,例2证明,证明,2020/6/12,总复习,6of65,例1求集合的幂集,2020/6/12,总复习,7of65,例2,n个元素的集合上，可以定义多少个关系？设集合X,Y,|X|=m,|Y|=n，可以定义多少个从X到Y的函数？,nm(|Y|X|),2020/6/12,总复习,8of65,例3对任意两个集合A,B,试证,2020/6/12,总复习,9of65,例4判断关系的性质,2020/6/12,总复习,10of65,例5求关系的闭包,解：,2020/6/12,总复习,11of65,例5（续）,2020/6/12,总复习,12of65,例7设A=1,2,3,求出A上所有的等价关系,解：,先求A的各种划分：,设对应于i的等价关系为Ri,则：,R1=,=IAR2=,IAR3=,IAR4=,IAR5=,IA,2020/6/12,总复习,13of65,例8画出哈斯图,2020/6/12,总复习,14of65,例9求极大（小）元，最大（小）元、上（下）界，上（下）确界,极大元：j,k极小元:a,b,e最大元：无最小元：无,B=a,b,c,d,e,f,g上界：h,i,j,k下界：无无上（下）确界,2020/6/12,总复习,15of65,例10判断函数的类型,入射,映射函数,双(入、满)射,满射,2020/6/12,总复习,16of65,例11求复合函数,2020/6/12,总复习,17of65,例12求复合函数,2020/6/12,总复习,18of65,例:求幺元、零元、逆元,N,I,Q,R上的普通加法+和乘法*+：幺元0，a-1=-a；*：幺元1，零元0，a-1=1/a；命题公式集合上的和：幺元F，零元T：幺元T，零元F幂集P(S)上的和：幺元，零元S：幺元S，零元,2020/6/12,总复习,19of65,例1,G是一个有15条边的简单图，有13条边，请问G中有多少个结点?,2020/6/12,总复习,20of65,例3,请画出4个顶点3条边的所有可能不同构的无向简单图？,2020/6/12,总复习,21of65,例4,若无向图G中恰有两个奇数度结点，则这两个结点必是连通的。,设G中两个奇数度结点分别为u,v。若u与v不连通,则至少有两个连通分支G1和G2，uG1,vG2。于是G1和G2各含一个奇数度结点，这与握手原理的推论矛盾，因此u与v必是连通的。,证明,试证,2020/6/12,总复习,22of65,例6判断下列图哪些是E图、H图？,2020/6/12,总复习,23of65,例7证明,设G有r个面，当v=3,e=2时，3v-6显然成立。若e3,则每一个面至少由3条边围成，所以,设G是一个有v个结点,e条边的连通简单平面图，若v3，则有v。,证明,2020/6/12,总复习,24of65,例10求图的最小生成树,2020/6/12,总复习,25of65,例11,无向树T有7片树叶,3个3度顶点,其余的都是4度顶点，则T有几个4度