离散数学试卷和答案VIP专享

一、填空题：1.设 A=｛2,a，⑶，4｝,B=｛｛a｝,3,4,1｝，请在下列每对集合中填入适当的符号：e,—（1）｛a｝B,（2）｛a,4,｛3｝｝A。[0,x 是奇数，2•设 A=｛0,1｝，N 为自然数集，f（x）=1x 是偶数若 f：TA，则 f 是射的，若 f：TA，则 f 是射的。3.设图 G=＜V，E〉中有 7 个结点，各结点的次数别离为 2,4,4,6，5，5，2，则 G 中有条边，按照。4._________________________________两个重言式的析取是，一个重言式和一个矛盾式的合取是。5.___________________________________________________________________________________设个体域为自然数集，命题“不存在最大自然数”符号化为。6. 设 S 为非空有限集，代数系统＜2S,u＞中幺元为，零元为。7•设 P、Q 为两个命题，其 De-Morden 律可表示为。8.当|G=8 时，群＜G,*＞只能有阶非普通子群，不能有阶子群，普通子群为。二、单项选择题：（每小题 1 分，本大题共 15 分）1.设 A=｛x|x 是整数且 X2＜16｝，下面哪个命题为假（）。A、｛0,1,2,4｝匸 A；B、｛一 3,—2,—1｝匸 A；,5。因为：x 了的运算表为:x712345611234562246135336251444152631 为幺元；4)1-1=1，2-1=4，3-1=5，4-1=2，5-1=3，6-1=6，553164266543211）由运算表知，x 封锁;7综上所述，＜G,x＞组成群。7由 31=3,32=2,33=6,34=4,35=5,36=1。所以，3 为其生成元，3 的逆元 5 也为其生成元。故＜G,x＞为循环群。71. 解：命题公式对应的二元树见右图。五、证明题1.证明：(1)\/aeAR,S 自反，••ER,eS,••••<>wRcS,••RcS 自反。(2)Va,Z?eA,若wRcS,则wR,wS，由 R,S 对称，所以，wR,wS,••wRcS,所以 RcS 对称。(3) Va,Z?,ceA,若wRcS,wRcS,则<>w7?,<>wS,wR,wS，由 R,S 传递性知，w 人，eS,从而wRcS,所以，Rr>S 传递。综上所述，RcS 是 A 上的等价关系。2.证明：（1）VxP(x)T(2(x)AP(x))P(2)P(a)T(Q(a)AP(a))US(1)(3)^(2(a)A/?(«))P(4)T(2)(3)I(5)Vx(S(x)oG(x))P(6)S(a)oG(a)US(5)⑺ S(a)TG(a)T(6)E,I(9)G(a)T(7)(8)I(10)「P(a)AG(a)T(4)(9)I所以，结论有效。3．证明：将每一个人用结点表示，当两个人是朋友时，则对应两结点连一条边，则得一无向图G=。因为每一个人恰有三个朋友，所以，deg(u)=3,(VueV),由任用意奇数度结点必然是偶数个，可知，此图结点数必然是偶数。14.证明：因为 G 为(11,m)图，「.G'为(11,m')图，且 m+m'=厅 x11x10=55。设厶G=，任 veV，则 v 在 G 中度数与 v 在 G'度数之和定为 n—1=10，如有某点 v 在G 中 deg(v)<4，则在 G'中 deg(v)>6，由定理，G'为非平面图。易证 G、G'存在汉密尔顿路，所以，连通。若 Vdeg(v)>5，则由定理，假设 G、G'都为简单连通平面图，则 m<3x11—6=27，m'<3x11—6=27，于是 m+m'<54 与 m+m'=55 矛盾。所以 G、G'至少有一个非平面图。