离散数学 练习题及答案

2023/7/25总复习1of65例3给出下列公式的真值表成真指派：100，101，110，1112023/7/25总复习2of65例4

试求下面公式的主析取（主合取）范式，并写出成真指派和成假指派。成真指派：00，10，11成假指派：012023/7/25总复习3of65例5试证证明2023/7/25总复习4of65例1符号化下列命题a)不是所有的男人都比女人高。

M(x):x是男人，W(x):x是女人，H(x,y):x比y高。2023/7/25总复习5of65例2证明证明2023/7/25总复习6of65例1求集合的幂集2023/7/25总复习7of65例2n个元素的集合上，可以定义多少个关系？设集合X,Y,|X|=m,|Y|=n，可以定义多少个从X到Y的函数？nm

(|Y||X|)2023/7/25总复习8of65例3对任意两个集合A,B,试证证明对于任意的x因为x是任意的,所以有的真值为T,因此2023/7/25总复习9of65例4判断关系的性质R1是自反的、反对称、传递的。2023/7/25总复习10of65例5求关系的闭包

解：2023/7/25总复习11of65例5（续）2023/7/25总复习12of65例7设A={1,2,3},求出A上所有的等价关系解：先求A的各种划分：12351232123312341231设对应于i

的等价关系为Ri,则：R1={<1,1>,<2,2>,<3,3>}=

IAR2={<1,2>,<2,1>}∪

IAR3={<1,3>,<3,1>}∪

IAR4={<2,3>,<3,2>}∪

IAR5={<1,2>,<1,3>,<2,1>,<2,3>,<3,1>,<3,2>}∪

IA2023/7/25总复习13of65例8画出哈斯图2023/7/25总复习14of65例9求极大（小）元，最大（小）元、上（下）界，上（下）确界极大元：j,k极小元:a,b,e最大元：无最小元：无B={a,b,c,d,e,f,g}上界：h,i,j,k下界：无无上（下）确界2023/7/25总复习15of65例10判断函数的类型入射

映射函数双(入、满)射满射2023/7/25总复习16of65例11求复合函数2023/7/25总复习17of65例12求复合函数2023/7/25总复习18of65例:求幺元、零元、逆元N,I,Q,R上的普通加法+和乘法*+：幺元0，a-1=-a；*：幺元1，零元0，a-1=1/a；命题公式集合上的和：幺元F，零元T

：幺元T，零元F幂集P(S)上的∪和∩∪：幺元，零元S∩：幺元S，零元2023/7/25总复习19of65例1G是一个有15条边的简单图，有13条边，请问G

中有多少个结点?解：共有15+13=28条边，

是一个完全图，它的结点数与G相同，设为n，根据定理4，n(n-1)/2=28n=82023/7/25总复习20of65例3请画出4个顶点3条边的所有可能不同构的无向简单图？2023/7/25总复习21of65例4若无向图G中恰有两个奇数度结点，则这两个结点必是连通的。设G

中两个奇数度结点分别为u,v。若u

与v

不连通,则至少有两个连通分支G1

和G2，u

G1,v

G2。于是G1

和G2各含一个奇数度结点，这与握手原理的推论矛盾，因此u与v

必是连通的。证明试证2023/7/25总复习22of65例6判断下列图哪些是E图、H图？2023/7/25总复习23of65例7证明设G

有r

个面，当v=3,e=2时，ｅ

3v-6显然成立。若e

3,则每一个面至少由3条边围成，所以

设G

是一个有v

个结点,e条边的连通简单平面图，若v

3，则有ｅ３v－６。证明2023/7/25总复习24of65例10求图的最小生成树2023/7/25总复习25of65例11无向树T有7片树叶,3个3度顶点,其余的都是4度顶点，则T有几个4度