《离散数学练习题及答案》由会员分享，可在线阅读，更多相关《离散数学练习题及答案（26页珍藏版）》请在金锄头文库上搜索。
1、例3 给出下列公式的真值表成真指派：100，101，110，1112021/6/161总复习例4 试求下面公式的主析取（主合取）范式，并写出成真指派和成假指派。成真指派：00，10，11成假指派：012021/6/162总复习例5 试证证明证明2021/6/163总复习例1 符号化下列命题a)不是所有的男人都比女人高。 M(x):x是男人，W(x):x是女人，H(x,y):x比y高。2021/6/164总复习例2 证明证明明2021/6/165总复习例1 求集合的幂集2021/6/166总复习例2n 个元素的集合上，可以定义多少个关系？设集合X,Y, |X|=m, |Y|=n，可以定义多少个从
2、X到Y的函数？nm (|Y|X| )2021/6/167总复习例例3 对任意两个集合对任意两个集合A, B,试证试证证明证明对于任意的x因为 x 是任意的,所以有的真值为T,因此2021/6/168总复习例4 判断关系的性质R1 是自反的、反对称、传递的。2021/6/169总复习例5 求关系的闭包 解：2021/6/1610总复习例5（续）2021/6/1611总复习例7 设 A=1,2,3, 求出A上所有的等价关系解：先求A的各种划分：12351232123312341231设对应于 i 的等价关系为Ri ,则：R1=, = = IAR2=, IAR3=, IAR4=, IAR5=, ,
3、IA 2021/6/1612总复习例8 画出哈斯图2021/6/1613总复习例9 求极大（小）元，最大（小）元、上（下）界，上（下）确界极大元：j,k极小元:a,b,e最大元：无最小元：无B=a,b,c,d,e,f,g上界： h,i,j,k下界：无无上（下）确界2021/6/1614总复习例10 判断函数的类型入 射 映射函数双(入、满)射满射2021/6/1615总复习例11 求复合函数2021/6/1616总复习例12 求复合函数2021/6/1617总复习例: 求幺元、零元、逆元N, I, Q, R上的普通加法 + 和乘法 *+：幺元 0，a-1 = -a；*：幺元 1，零元 0， a
4、-1 = 1/a；命题公式集合上的 和 ：幺元F，零元T ：幺元T，零元F幂集P(S)上的和：幺元 ，零元S：幺元S，零元2021/6/1618总复习例1G 是一个有是一个有 15 条边的简单图，条边的简单图， 有有 13 条边，请问条边，请问 G 中有多少个结点中有多少个结点? 解：共有共有 15 + 13 = 28 条边，条边， 是一个完全图，它的是一个完全图，它的结点数与结点数与 G 相同，设为相同，设为 n，根，根据定理据定理4，n(n-1)/2 = 28n = 82021/6/1619总复习例3请画出请画出 4 个顶点个顶点 3 条边的所有可能不同构条边的所有可能不同构的无向简单图？
5、的无向简单图？2021/6/1620总复习例4若无向图若无向图 G 中恰有两个奇数度结点，则这中恰有两个奇数度结点，则这两个结点必是连通的。两个结点必是连通的。设 G 中两个奇数度结点分别为 u ,v。 若 u 与 v 不连通,则至少有两个连通分支 G1 和 G2，u G1,v G2。 于是 G1 和 G2 各含一个奇数度结点，这与握手原理的推论矛盾，因此 u 与 v 必是连通的。证明试证试证2021/6/1621总复习例6 判断下列图哪些是 E 图、H图？2021/6/1622总复习例7 证明设设 G 有有 r 个面，个面，当当v = 3, e = 2时，时， 3v-6 显然成立。显然成立。若若 e 3, 则每一个面至少由则每一个面至少由 3 条边围成，所以条边围成，所以 设 G 是一个有 v 个结点, e 条边的连通简单平面图，若 v 3，则有 v。证明2021/6/1623总复习例10 求图的最小生成树2021/6/1624总复习例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=12021/6/1625总复习 结束束语若有不当之处，请指正，谢谢！若有不当之处，请指正，谢谢！
