至诚学院离散必做习题3

离散数学习题3

一、选择题

1．下列是两个命题变元p，q的小项是（ ） A．p∧┐p∧q B．┐p∨q C．┐p∧q D．┐p∨p∨q 2．令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ ） A．p→┐q B．p∨┐q C．p∧q D．p∧┐q 3．下列语句中是命题的只有（ ） A．1+1=10 B．x+y=10 C．sinx+siny<0 D．x mod 3=2 4．下列等值式不正确的是（ ） A．┐(?x)A?(?x)┐A

B．(?x)(B→A(x))?B→(?x)A(x)

C．(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x)

D．(?x)(?y)(A(x)→B(y))?(?x)A(x)→(?y)B(y)

5．谓词公式(?x)P(x,y)∧(?x)(Q(x,z)→(?x)(?y)R(x,y,z)中量词?x的辖域是（ ）A．(?x)Q(x,z)→(?x)(?y)R(x,y,z)) B．Q(x,z)→(?y)R(x,y,z)

C．Q(x,z)→(?x)(?y)R(x,y,z) D．Q(x,z)

6．设R为实数集，函数f：R→R，f(x)=2x，则f是（ ） A．满射函数 B．单射函数 C．双射函数 D．非单射非满射 7．设A={a,b,c,d}，A上的等价关系R={,}∪IA，则对应于R的A的划分是（ A．{{a},{b,c},{d}} B．{{a,b},{c},{d}} C．{{a},{b},{c},{d}} D．{{a,b},{c,d}} 8．设A={?}，B=P(P(A))，以下正确的式子是（ ） A．{?,{?}}∈B B．{{?,?}}∈B C．{{?},{{?}}}∈B D．{?,{{?}}}∈B

9．设X，Y，Z是集合，一是集合相对补运算，下列等式不正确的是（ ） A．(X-Y)-Z=X-(Y∩Z) B．(X-Y)-Z=(X-Z)-Y C．(X-Y)-Z=(X-Z)-(Y-Z) D．(X-Y)-Z=X-(Y∪Z)

10．设*是集合A上的二元运算，称Z是A上关于运算*的零元，若（ ） A．Z??A，且?x?A,有x*Z=Z*x=Z

B．Z?A，且?x?A有x*Z=Z*x=Z C．Z?A，且?x?A有x*Z=Z*x=x D．Z?A，且?x?A有x*Z=Z*x=Z

11．在自然数集N上，下列定义的运算中不可结合的只有（ ） A．a*b=min(a,b) B．a*b=a+b

C．a*b=GCD(a,b)(a,b的最大公约数)

） D．a*b=a(mod b)

12．设R为实数集，R+={x|x∈R∧x>0}，*是数的乘法运算，是一个群，则下列集

合关于数的乘法运算构成该群的子群的是（ ） A．{R+中的有理数} B．{R+中的无理数} C．{R+中的自然数} D．{1，2，3} 13．设是环，则下列正确的是（ ） A．是交换群 B．是加法群 C．?对*是可分配的 D．*对?是可分配的 14．下列各图不是欧拉图的是（ ）

15．设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（ ） A．2个面 B．3个面 C．4个面 D．5个面

二、填空题

16． 公式为 之充分必要条件是其析取范式之每一析取项中均必同时包含一命题变元

及其否定； 公式为 之充分必要条件是其合取范式之每一合取项中均必同时包含一命题变元及其否定。

17．前束范式具有形式(Q1V1)(Q2V2)?(QnVn)A，其中Qi(1≤i≤n)为 ，A为 的谓词公式。

18．设论域是{a,b,c}，则(?x)S(x)等价于命题公式 ；(?x)S(x)等价于命题公式 。 19．设R为A上的关系，则R的自反闭包r(R)= ，对称闭包s(R)= 。 20．某集合A上的二元关系R具有对称性，反对称性，自反性和传递性，此关系R是 ，

其关系矩阵是 。

21．设是一个偏序集，如果S中的任意两个元素都有 和 ，则称S关于≤

构成一个格。

22．设Z是整数集，在Z上定义二元运算*为a*b=a+b+a·b，其中+和·是数的加法和乘法，

则代数系统的幺元是 ，零元是 。

23．如下平面图有2个面R1和R2，其中deg(R1)= ，deg(R2)= 。

24．无向图G具有一条欧拉回路，当且仅当G是 ，并且所有结点的度数都是 。 25．在下图中，结点v2的度数是 ，结点v5的度数是 。

三、计算题

26．求出从A={1,2}到B={x,y}的所有函数，并指出哪些是双射函数，哪些是满射函数。 27．如果论域是集合{a,b,c}，试消去给定公式中的量词：(?y)(?x)(x?y?0)。

28．设A={a,b,c }，P（A）是A的幂集，?是集合对称差运算。已知是群。在群

中，①找出其幺元。②找出任一元素的逆元。③求元素x使满足{a}?x={b}。 30．画出5个具有5个结点5条边的非同构的无向连通简单图。 31． 在偏序集中，其中Z={1,2,3,4,6,8,12,14}，≤是Z中的整除关系，求集合D={2,3,4,6}

的极大元，极小元，最大元，最小元，最小上界和最大下界。

四、证明题

32．用等值演算法证明((q∧s)→r)∧(s→(p∨r))?(s∧(p→q))→r

五、应用题

35．n个男n个女排成一男女相间的队伍，试问有多少种不同的方案？若围成一圆桌坐下，又有多少种不同的方案？

36．设有a,b,c,d,e,f,g等七个人，已知a会讲英语；b会讲英语、汉语；c会讲英、俄语；d会讲日、汉语；e会讲德语、俄语；f会讲法语、日语；g会讲法语、德语。试用图论方法安排园桌座位，使每人都能与其身边的人交谈。

本文来源：https://www.bwwdw.com/article/scf2.html