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

《离散数》期末考试题(A)一、填空(小题3，共15)设

A{{},{}}，{{a},{b},{}}，则A

)

，A)，())

.集合

A

b}

其上可定义()封闭的元运算()个闭的2运算()个封闭的元运算.命题公式

p

q)

的对偶式为().所6因数组成的集合为().不同构的根树有()棵二、单选(小题3，共15)设B是集合，若A，则(A)B(B)=(C)(D)BA谓词公P)(y))()中量的辖域为

(P(xy))()(B)(x)(y)(C)

(P()

(y))()

(D)

(x)()和(x)任6群的子群的阶一定不为(A)4(B)6(C)2(D)3设是正整数，则有限布尔代数的元素个数为(A)2(B)4n(C)

(D)n对于下列序列，可构成简单无向图的度数序列为(A)3,3,4,53,3,31,31,2,2三、判断(小题3，共15):正确打“错误打“”.设

f:NNN，()x,，则f

是满射()5男5女圆桌交替就座的方式有种.(L是，对于x,zL，若x

()yxxy，则.()任何树都至少片树叶()无向生成树的充要条件G连通图.()四、(10分)设

,和D

是集合，证明

(A

)CDD

，并举例说明上式中不能将改为.五、(15分)设是自然数集合，定义上的关系R如下：(xy)y

是偶数，证明R是N上的等价关系求出N关于等价关所有等价类.试求出一个N到N的函数f，使R

{(y)yN,()f(y)}

.六、(10分)在实数集合证明下列推理的有效性:因为R存在自然数，而所有自然数是整数，所以R存在整数七、(10分)设是实数集合，令,b|aR,a0}定的运算如下:对于任意

(a,b(c)G，,)d)

,ad)，证(G

是非Abel群.八、(10分)若简单平面图

G

的节点数n且边数15G是连通图，试证明之《离散数》期末考试题(A)参考答案一1.

A{{},

{},{,},{}}，B{{c}}，P(A

{{b}},{{}},{{,},{}}}.

,3

,3

.p){-1，，，-612，3，6}二、2(B);3(A);4(C);三、1(×2(√);3(×);×);5(√).四证对于任(xy)()C)，xB且于A,x

且y,D，进而x,)A,(x,)D，因此x,y(A)word

，所以

aaaa()C)(A))

.例如取

AB{,b},Cc},{}这时(B)C)

而故

(A))c()}(,d)}c(,)}()C)()B).

，五、证1.于任意xN由于2

是偶数，于是

(x)因此R是N的自反关系对于任意

xy，(xy)R，x

是偶数，即y是偶数，于是

(y,)因R是N上的对称关系对于意y,z若xy)且(y,R则是偶数且y数，是xy)y

是偶数，进而

(x,，因此R是N上的传递关系.综上所述，是N的等价关系N关于等价关系的所有等价类[0]Rx是偶数令:NN,f()

[1]{1,3,5,7,...}.R，显然R{(,)N,f(xf()}

.六、证令

N(x:

是自然数，

(x):

是整数，则前提:结论:

(x(N(x(x))()构造性证明如下:()

N(c)

(()Z(xN(c()

(c)(x)

T(2)(4)IEG(5)七、证(1)对任意

(ab()G，ac0，进ac0，于(acad)G

，即“∙”上代数(封闭)运算.合律对于任意a(c,d),(,f)

，一方面有((a,b))f),ad)f),ad))acf)另一方面有

，(a)f)),b)),cf))于是

)，((,)))f)a,),d)f))

.位元为(1,对于任意

(ab

，由于b)

且

(ba)b)

，于是(是单位元元素均存在逆元对于任意

(ab

，因为

a

且b1b(a,ba

，而,

1,b)a

，所以G中每元素均有元.于

(2,3)

且

(2,1)

，即

(2,1)

，因“∙不可交换word

RR综上所述，

(G

是非Abel群八、证(反证)不连通的，有k(连通分GG,...,.对于任ikkG是(,m).iii若存在j(1j)得n另外6个节点所生成的子图恰条边由G是简单图Kj

，的边数为15，G含子图显然，不是平面图，这与已知G是平面图矛盾若存在j(1j)使n，则另外个节点所生成的子恰条边，这不可能，因为j的边数恰为10.

于是

n3,jj

,因此对于每连通分支有

m6(1j)ii

，进而

i

i

ki

.

因

为

n7,

，

所

以iii，由此得出，与k矛盾.

G连通图《离散数》期末考试题(B)一、填空(小题3，共15)设

A{{,},,,

}则

A

()，A}=()，

()

中的元素个数

()

(设集合有3元素，则A上的二元关系有()个其中有()个函数谓词公P(x)Q())Q(y))中词的域为(),量词辖域为(设D，对于其上的整除关系“素()不存在补元n()时，n完全无向图K是平面图，当n为()时，K是欧拉图.n二、单选(小题3，共15)设是集合的偏序关系，的逆关系，则是A的(A)偏序关系(B)等价关系相容关系(D)以上结论都不成立2命题变元p组成的不等值的命题公式的个数有(A)2(B)4(C)8(D)16设是素数n是正整数，则任有限域的元素个数为

p

(B)

(C)

(D)

设是实数集合上的小于等于关系，则((A)有界格(B)分配格有补格(D)布尔格5.3阶全无向图K的不同构的生成子图有(A)2(B)3(C)4(D)5三、判断(小题3，共15):正确打“错误打“”.若一个元素既存在左逆元，又存在右逆元a，则lr

l

r

.()命题联结词→不满足结合律()在Z{0，1，2，34567}中2于“逆元为4.()整环不一定是域()任(,)平面图的面r.()四、(10分)设

f:且C，g

是单射，证明

f

是单射，并举例说明g一定是单射五、(15分)设

Ab,d}

,

A

上的关系Ra,(a,b(a,c),(ca(,),(c(,a(,b(d,c)}画出R的系图判断所具有的性质

,求出R的系矩阵六、(10分)利真值表求命题公式

A

(qr(r(qp

的主析取范式和主合取范式word

RR1111七、(10分)边数

的简单平面图G，必存在节v使deg()4

.八、(10分)有六个数字，其中三个两个一个，求能组成位数的个.《离散数》期末考试题(参考答案一、1.{{,b},b,}，{{,b},a},27.(x)(),Q(y)(y).4,6,，数.二、1(B);2(D);4(B);5(C).三、1(×2(√);3(×);4(××四证对于任意,yf(x)()

(f())g(f(y))(g)(x)f)()

.由于是单射，因此，于是是单射.例如取

ab},(1,2,3},C

，令

fa,1),(,2)}

，，这时f{(,(,)}

是单射，而g不是单射.五、解1.

的关系如下：Rc

由于

)，所以不是自反的于为

(a)，所以不是反自反的.(,R，()，因此不是对称的

(,),(c,a，是R是反对称的.计算知

R

R{(a),(a),(,c(,),c,b(c,),(d(d,)}，进而R是传递的.

综上所述，所给是传递的的关系矩阵

110

.六、解命题公式

A(r(r(qp))

的真值表如下:p,,r

(qr)r(p)

10101010

10111111

11110111

10110111由表可知，

(r(r(q

的主析取范式为word

……2!Aqr)())q)r)(主合取范式为

A)p)

.七证妨G的阶则结论是显然的.根据推论1知.任意节点度数均有

deg(v)

，由握手定理知2mv5n

.于是

n

2m进mnm5

.

因此

，与已知矛盾.

所以必存在节点

使得

deg(v)

4

.八、解设满足要求的r数的个数有种，r01，2，，则排列计数生成函数rx3x2(xxx

2

1919xxx61212

6

,因而

a

4

1912

.《离散数》期末考试题(C)一、填空(小题3，共15)若

Amn||

()，到2关系共有()个，上的元关系共有()个.A={1,2,3},=(2,1),(3,1)},={(1,(2,(3,2)}h={(1,3),1),(3,1)})是单射，()满射，()双射.下列5个命题公式中，是永真式的有()(选择正确答案的番)qq；

pp(q)

；；

q

；

(

q

.D24的所有正因数组成的集合上的整除关系的补元()的元()6补元().设是(7,简单平面图则G定是()且其每个面恰由()条边围成的面数为().二、单选(小题3，共15)设B,C是集合，则下述论断正确的是((A)若ABC，则A.(B)若AB，则.(C)若，C，则(D)若AB，则设AA，A，则下述结论正确的是(A)若R和S是自反的，则R是自反的.(B)若R和S是对称的，RS是对称.(C)若R和S反对称的，则是反对称的.(D)若和是递的，则是传递.在谓词逻辑中，下列各式中不正确的().((x)(x))()(x)(B)(C)

(A)(x))(x)()A)(x))(x)()(D)

(x)

x,域与整环的关系为().(A)整环是域(B)是整环word

(C)整环不是域

(D)域不是整环

设是(n,)图，且中每个节点的度数不是就是+1，则G中度数为的节点个数为(

n2

.(B)(n+1).(D)

(k

.三、判断(小题3，共15):正确打“错误打“”.设f:ZZ，

f(xx，则f

是单射.()设是群到群的同态映射，若G是Abel群，则是Abel群.()(是格，对于xyL若yx，则y()元素个数同的有限布尔代数都是同构的.()设是n(n11)阶简单图，则或是非平面图.四、(15分)和B是集合，下列各式(1)AB())A成的充要条件是什么，并给出理由.

；

()AB

；五、(10分)设S是实数集合R上的关系，其定义如下Sx,)xy

R且是

y3

是整数}证明:S是R上的等价关系六、(10分)求谓词公(x)

(B())(x)))

的前束范式七、(10分)若n人，每个人恰有个朋友，则必为偶数，试证明之.八、(10分)

利用生成函数求解递归关

aa2(na2

.《离散数》期末考试题(C)参考答案一、1.

mn,2,2

.g,g4.8不存在，不存在.连通，310.二、2(A);4(A);5(D).三、1(√);2(×);3();4(√);5(√).四、证显然，A

.以证明：BB()当A=B时，B==于是AA.()定ABA证明AB:任意xA若xB则xA

而B故A=B

根据差运算定义知与矛盾.所以因此B.同理可证BA.易证明：

(A

)(B)AB

()显然()(反证)若，则存在B分种情况讨论：若xA则xA，由()(BAA是盾若xx且x,进而x，矛盾证毕五、证1.对于任意R,因为

x3

是整数，所以(x,xS，即是R上的自反关系.对于任意x,yR若(x,)S，则

xyxy是整数，而33

也是整数，