《离散数学》期末考试题22222

本文格式为Word版，下载可任意编辑——《离散数学》期末考试题222222023年黑河学院期末模拟试题

《离散数学》期末考试题(A)

一、填空题(每题3分，共15分)

A?{{a,b},{c}}，B?{{a},{b,c},{c}}，则A?B?()，

A?B?()，P(A)?().

2.集合A?{a,b,c}，其上可定义()个封闭的1元运算，()个封闭的2元运算，()

1.设

个封闭的3元运算.

3.命题公式(p?q)?1的对偶式为().4.所有6的因数组成的集合为().5.不同构的5阶根树有()棵.二、单项选择题(每题3分，共15分)

1.设A,B是集合，若A?B?A，则

?A

(A)B=?(B)A=?(C)A?B??(D)A?B2.谓词公式?x(P(x)??yQ(y))?R(x)中量词?x的辖域为(A)?x(P(x)??yQ(y))?R(x)(B)P(x)??yQ(y)

(C)(P(x)??yQ(y))?R(x)(D)P(x)??yQ(y)和R(x)

3.任意6阶群的子群的阶一定不为

(A)4(B)6(C)2(D)34.设n是正整数，则有限布尔代数的元素个数为

(A)2n(B)4n(C)2(D)n5.对于以下序列，可构成简单无向图的度数序列为

(A)3,3,4,4,5(B)0,1,3,3,3(C)1,1,2,2,3(D)1,1,2,2,2三、判断题(每题3分，共15分):正确打“√〞，错误打“×〞.1.设

n2f:N?N?N，f(x)?(x,x?1)，则f是满射.()

2.5男5女圆桌交替就座的方式有2880种.()3.设(L,?)是格，对于x,y,z?L，若x?y?x?z且x?y?x?z，则y?z.()

4.任何树都至少2片树叶.()5.无向图G有生成树的充要条件是G为连通图.()四、(10分)设

A,B,C和D是集合，证明(A?B)?(C?D)?(A?C)?(B?D)，并举例说明上

式中不能将?改为=.

五、(15分)设N是自然数集合，定义N上的关系R如下：

(x,y)?R?x?y是偶数，

1.证明R是N上的等价关系.

2.求出N关于等价关系R的所有等价类.3.试求出一个N到N的函数

f，使得R?{(x,y)|x,y?N,f(x)?f(y)}.

六、(10分)在实数集合R中证明以下推理的有效性:

由于R中存在自然数，而所有自然数是整数，所以R中存在整数.

?{(a,b)|a,b?R,a?0}，定义G上的运算如下:

对于任意(a,b),(c,d)?G，(a,b)?(c,d)?(ac,ad?b)，证明(G,?)是非Abel群.八、(10分)若简单平面图G的节点数n?7且边数m?15，则G是连通图，试证明之.

七、(10分)设R是实数集合，令G

2023年黑河学院期末模拟试题

《离散数学》期末考试题(A)参考答案

一、1.A?B?{{a},{{c}},{{a,b},{c}}}.

{a,b},{b,c},{c}}，A?B?{{c}}，P(A)?{?,{{a,b}},

,39,327.3.(p?q)?0.

2.34.{-1，-2，-3，-6，1，2，3，6}.5.9.

二、1(C);2(B);3(A);4(C);5(D).三、1(×);2(√);3(×);4(×);5(√).

四、证对于任意(x,y)?(A?B)?(C?D)，有x?3A?B且y?C?D，于是x?A,x?B且

y?C,y?D，进而(x,y)?A?C,(x,y)?B?D，因此(x,y)?(A?C)?(B?D)，所以(A?B)?(C?D)?(A?C)?(B?D).

例如取A?B?{a,b},C?{c},D?{d}，这时A?B??，进而(A?B)?(C?D)??，

而

(A?C)?(B?D)?{(a,c),(b,c)}?{(a,d),(b,d)}?{(a,c),(b,c)}，

故(A?B)?(C?D)?(A?C)?(B?D).

五、证1.对于任意x?N，由于x?x?2x是偶数，于是(x,x)?R，因此R是N上的自反关系.

对于任意x,y?N，若(x,y)?R，则x?y是偶数，即y?x是偶数，于是(y,x)?R，因此R是N上的对称关系.

x,y,z?N，若(x,y)?R且(y,z)?R，则x?y是偶数且y?z是偶数，于是

x?z?(x?y)?(y?z)?2y是偶数，进而(x,z)?R，因此R是N上的传递关系.

综上所述，R是N上的等价关系.

2.N关于等价关系R的所有等价类为[0]R?{0,2,4,6,...}和[1]R?{1,3,5,7,...}.

对于任意

?0,x是偶数，显然R?{(x,y)|x,y?N,f(x)?f(y)}.f:N?N,f(x)??1,x是奇数?六、证令N(x):x是自然数，Z(x):x是整数，则前提:?xN(x),?x(N(x)?Z(x))结论:?xZ(x)

3.令

构造性证明如下:

(1)?xN(x)P(2)N(c)ES(1)(3)?x(N(x)?Z(x))P

(4)N(c)?Z(c)US(3)(5)Z(c)T(2)(4)I(6)?xZ(x)EG(5)

七、证(1)对于任意(a,b),(c,d)?G，有a,c?0，进而ac?0，于是(ac,ad?b)?G，即“?〞是G上的代数(封闭)运算.

(2)结合律对于任意(a,b),(c,d),(e,f)?G，一方面有((a,b)?(c,d))?(e,f)?(ac,ad?b)?(e,f)

?(ace,ac?f?(ad?b))?(ace,acf?ad?b)，

另一方面有

(a,b)?((c,d)?(e,f))?(a,b)?(ce,cf?d)?(ace,a(cf?d)?b)?(ace,acf?ad?b)，

于是((a,b)?(c,d))?(e,f)?(a,b)?((c,d)?(e,f)).

(3)单位元为(1,0)对于任意(a,b)?G，由于

(1,0)?(a,b)?(a,b?0)?(a,b)且(a,b)?(1,0)?(a,a0?b)?(a,b)，于是(1,0)是单位元.

?1b?(4)每元素均存在逆元对于任意(a,b)?G，由于?,???G且

?aa??1b??1?b??(a,b)??,????a?,a??(1,0)，而????b????aa??a?a???11?1b??b???a,?b??(1,0)，?,???(a,b)????????a?aa??a???a所以，G中每元素均有逆元.

(5)由于(1,2)?(2,1)?(2,3)且(2,1)?(1,2)?(2,5)，即(1,2)?(2,1)?(2,1)?(1,2)，因而“?〞不

可交换.

综上所述，(G,?)是非Abel群.

八、证(反证)设G是不连通的，则G有k(k令Gi是(ni,mi)图.若存在

?2)个连通分支G1,G2,...,Gk.对于任意i(1?i?k)，

j(1?j?k)使得nj?1，则另外6个节点所生成的子图恰15条边.由于G是简单图，K6j(1?j?k)使得nj?2，则另外5个节点所生成的子图恰14条边，这不可能，由于K5,因此对于每个连通分支有

k的边数为15，即G中含K6子图.显然，K6不是平面图，这与已知G是平面图矛盾.

若存在于是

k的边数恰为10.

nj?3,j?1,2,...,kki?1mi?3ni?6(1?j?k)，进而

为

m??mi??(3ni?6)?3?ni?6k?3n?6ki?1i?1.因

n?7,m?15，所以

15?3?7?6k，由此得出k?1，与k?2矛盾.故G是连通图.

2023年黑河学院期末模拟试题

《离散数学》期末考试题(B)

一、填空题(每题3分，共15分)

1.设A?{{a,b},a,b,?}，则A??=()，A?{?}=()，P(A)中的元素个数|P(A)|?().

2.设集合A中有3个元素，则A上的二元关系有()个，其中有()个是A到A的函数.3.谓词公式?x(P(x)4.设D24?Q(x))??y(Q(y)??P(y))中量词?x的辖域为(),量

词?y的辖域为().

，元素()不存在补元.?{1,2,3,4,6,8,12,24}，对于其上的整除关系“|〞

5.当n()时，n阶完全无向图Kn是平面图，当当n为()时，Kn是欧拉图.二、单项选择题(每题3分，共15分)

1.设R是集合A上的偏序关系，R是R的逆关系，则R?R是A上的(A)偏序关系(B)等价关系(C)相容关系(D)以上结论都不成立2.由2个命题变元p和q组成的不等值的命题公式的个数有(A)2(B)4(C)8(D)163.设p是素数且n是正整数，则任意有限域的元素个数为(A)

?1?1p?n(B)pn(C)pn(D)np

4.设R是实数集合，?是其上的小于等于关系，则(R,?)是(A)有界格(B)分派格(C)有补格(D)布尔格5.3阶完全无向图K3的不同构的生成子图有

(A)2(B)3(C)4(D)5三、判断题(每题3分，共15分):正确打“√〞，错误打“×〞.

1.若一个元素a既存在左逆元al，又存在右逆元ar，则al?ar.()

2.命题联结词→不满足结合律.()

3.在Z8={0，1，2，3，4，5，6，7}中，2关于“?8〞的逆元为4.()4.整环不一定是域.()5.任何(n,m)平面图的面数r四、(10分)设单射.五、(15分)设

?m?n?2.()

f:A?B且g:B?C，若f?g是单射，证明f是单射，并举例说明g不一定是

A?{a,b,c,d},A上的关系

R?{(a,a),(a,b),(a,c),(c,a),(c,b),(c,c),(d,a),(d,b),(d,c)},

1.画出R的关系图GR.2.判断R所具有的性质.3.求出R的关系矩阵MR.

六、(10分)利用真值表求命题公式A?(p?(q?r))?(r?(q?p))的主析取范式和主合取

范式.

七、(10分)边数m?30的简单平面图G，必存在节点v使得deg(v)?4.

八、(10分)有六个数字，其中三个1，两个2，一个3，求能组成四位数的个数.

2023年黑河学院期末模拟试题

《离散数学》期末考试题(B)参考答案

一、1.{{a,b},a,b,?}，{{a,b},a,b}，16.2.2,27.

3.P(x)?Q(x),Q(y)??P(y).4.2,4,6,12.5.?4，奇数.

二、1(B);2(D);3(C);4(B);5(C).三、1(×);2(√);3(×);4(×);5(×).四、证对于任意x,y?A，若

9f(x)?f(y)，则g(f(x))?g(f(y))，即(f?g)(x)?(f?g)(y).由于f?g是单射，