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