(完整word版)离散数学试卷及答案(24)

1、离散数学试卷（24）1583.下图描述的偏序集中，子集b,e, f的上界为 （一、填空题：（每空 1 分，本大题共 15 分）1设A =2,a,3 ,4,B =a ,3,4,1，请在下列每对集合中填入适当的符号：，。(1)a_B,a ,4,30，x 是奇数，2设A=0,1，N为自然数集，f（x，是偶数。若TA，则f是3.设图 G = 中有 7 个结点，各结点的次数分别为2，4, 4，6，5，5，2，则 G 中有_条边，根据 _ 。4两个重言式的析取是 _，一个重言式和一个矛盾式的合取是 _。5 设个体域为自然数集，命题“不存在最大自然数”符号化为_。6设 S 为非空有限集，代数系统：2S，一

2、中幺元为 _，零元为 _ 。7 .设 P、Q 为两个命题，其 De-Morden 律可表示为 _ 。&当G| =8时，群cG严 只能有_ 阶非平凡子群，不能有 _阶子群，平凡子群为 _。二、单项选择题：（每小题 1 分，本大题共 15 分）1设A=x x 是整数且 x21$，下面哪个命题为假（）。B、-3, -2, -1 A;D、x x 是整数且 x : 4 A。2设A = A , B=，：，则 B A 是（）。A、：； B、;C、,：; D、门。_ 射的，若 f:N A，贝U f是射的。A、0,1,2,4 A;离散数学试卷（24）1594设f和g都是 X 上的双射函数，则（f g）-

3、为（）。A、f gJ； B、（gf）J；C、gJf；D、gf_1。5.下面集合（）关于减法运算是封闭的。A、N ； B、2X Xl；C、2X+1 XE 1；D、XX 是质数。6. 具有如下定义的代数系统:G ，（）不构成群。A、G =1,10, * 是模 11 乘；B、G =1,3,4,5,9, * 是模 11 乘；）关于整除关系构成格。C、G = Q（有理数集），*是普通加法D、G=Q（有理数集），*是普通乘法。7.设G二2m3n则代数系统:G , 的幺元为（A、不存在B、e=23； C、e=2 39.A、2 , 3,C、1 , 2,12, 24, 36;5, 6, 15, 30;设V =a

4、,b,c,d,e, f,B、1 , 2, 3,D、3 , 6, 9 ,4, 6,12。8, 12;离散数学试卷（24）16012.含有 3 个命题变元的具有不同真值的命题公式的个数为（E = : a , b，: b , c , : c , a，: a , d，: d , ef , e ,则有向图G =：V , ED、不连通的。C、度数为奇数的结点出度为奇数的结点A、 度数为偶数入度为奇数的结点B、;C、弱连通的A、强连通的； B、单侧连通的离散数学试卷（24）16113.下列集合中哪个是最小联结词集（14.下面哪个命题公式是重言式（15在谓词演算中，下列各式哪个是正确的A2B二：0,1, 1,

5、：0,1,2 , (Q(x)R(x) ,-(Q(a)R(a) , S(a) ,-x(S(x)G(x)的有效结论。3.若有 n 个人，每个人都恰有三个朋友，则n 必为偶数。4设 G 是(11 , m)图，证明 G 或其补图G是非平面图。一、填空题1.( 1),(2)冬。2双射，满射。 3. 14deg(vJ=：2E4.重言式，矛盾式。 5.-xTy(y . x), 6. ：,S。离散数学试卷(24)1647.(P Q)二一P Q , -(P Q)= P Q;P(P Q)=P, P(P Q) =P。& 2, 4;3,5, 6, 7;: e,，:G,。、单项选择题题号123456789101

6、112131415答案ACBCBDBCCACCABA三、判断改正题1.x2A-B=2A一 2B。2.xA2x B =0,0, A , 0,0,2 a , , 0,1,2 A , , 1,0,，a , Q(x)。四、简答案题1.解r()=：a,a，:：a,b，:：b,c，: c,b，:：b, b，:：c, c,s(;?) =a, a，:：a, b，:：b,c，:：c,b，:b, a,2二=：a, a，:：a,b，:：a,c，:b, b，:c,c,3二；2 =：a, a，:a,b，: a, c，:a, b，: b,c，:c, b ,离散数学试卷（24）1652t（町 彳:a,a ,：a,b，: a

7、, c，: b,b，: c,c，:b, c，:c,b 。2解：的哈斯图为3解此问题的最优设计方案即要求该图的最小生成树, 由破圈法或避圈法得最小生成树为：其权数为 1 + 1+3+4 = 9。4.解：:G,7既构成群，又构成循环群，其生成元为沢71234561123456224613533625144415263553164266543211 ）由运算表知，7封闭；2）7可结合（可自证明）集合最大兀极大兀下界上确界A无24, 36无无B12126, 2, 312C66无63，5。因为：7的运算表为:32离散数学试卷(24)1663） 1 为幺元；4）11,2仁4, 3-5 ,4仁2, 5 3

8、, 6仁6 ,离散数学试卷(24)167综上所述，G,7.构成群。由31=3,32= 2,33=6,34=4,35,36=1。所以，3 为其生成元，3 的逆元 5 也为其生成元。故:G，7-为循环群。5. 解：命题公式对应的二元树见右图。五、证明题1 .证明：(1)-a A,；R , S 自反,：:：a, a三R ,：a, aS ,:a, a，二R S , ” R S自反。(2)一a, b A，若:a, bER S，则：:：a,b沁R ,：a, b沁S ,由 R , S 对称， 所以，：:b,a沙R ,：b,a沁S , :b,aR S，所以R S对称。(3)一a,b,c A，若：a,b三RS

9、,：b,c沁R S ,贝U：a,b三R ,：a,b匕三S ,:b,c三R ,：b,c H S ,由 R , S 传递性知，：:：a,c三R，:a,c三S ,从而:a,c R - S,所以，R- S传递。综上所述，R-S是 A 上的等价关系。2证明：(1)-xP(x) (Q(x)P(x)P(2)P(a) (Q(a)P(a)US(1)-(Q(a)R(a)P离散数学试卷(24)168P(a)T(2)(3)I-x(S(x)，G(x)PS(a)G(a)US(5)S(a) G(a)T(6)E,I(8)S(a)P(9)G(a)T(8)1(10)一 P(a) G(a)T(4)(9)1所以，结论有效。3证明：将每个人用结点表示，当两个人是朋友时，则对应两结点连一条边，则得一无向图G=V,E。因为每个人恰有三个朋友，所以，deg(u)=3,(-u V)，由任意图奇数度结点一定是偶数个，可知，此图结点数一定是偶数。14证明：因为 G 为(11，m)图，.G 为(11, m)图，且m m 11 10 = 55。设2G =： V, E，任v V，则v在 G 中度数与v在G度数之和定为n -1 = 10，若有某点v在G