离散数学试卷二十三试题与答案

第一篇：离散数学试卷二十三试题与答案

试卷二十三试题与答案

一、单项选择题：（每小题1分，本大题共10分）

1．命题公式P(QP)是（）。

A、矛盾式；B、可满足式；C、重言式；D、等价式。

2．下列各式中哪个不成立（）。

A、x(P(x)Q(x))xP(x)xQ(x)；

B、x(P(x)Q(x))xP(x)xQ(x)；

C、x(P(x)Q(x))xP(x)xQ(x)；

D、x(P(x)Q)xP(x)Q。

3．谓词公式x(P(x)yR(y))Q(x)中的 x是（）。

A、自由变元；B、约束变元；

C、既是自由变元又是约束变元；D、既不是自由变元又不是约束变元。

4．在0 之间应填入（）符号。

A、=；B、；C、；D、。

5．设< A， > 是偏序集，BA，下面结论正确的是（）。

A、B的极大元bB且唯一；B、B的极大元bA且不唯一；

C、B的上界bB且不唯一；D、B的上确界bA且唯一。

6．在自然数集N上，下列（）运算是可结合的。

（对任意a,bN）

A、abab；B、abmax(a,b)；

C、aba5b；D、abab。

7．Q为有理数集N，Q上定义运算*为a*b = a + b – ab ,则的幺元为（A、a；B、b；C、1；D、0。

8．给定下列序列，（）可以构成无向简单图的结点度数序列。

A、（1，1，2，2，3）；B、（1，1，2，2，2）；

C、（0，1，3，3，3）；D、（1，3，4，4，5）。

9．设G是简单有向图，可达矩阵P(G)刻划下列（）关系。

A、点与边；B、边与点；C、点与点；D、边与边。

10．一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为（A、5；B、7；C、9；D、8。

。）。）

二、填空：（每空1分，本大题共15分）

1．在自然数集中，偶数集为N1、奇数集为N2，则N1N2=；

N1N2 =。

2．设X{1,2,3,4},R{1,2,2,4，3,3}，则

r(R)=；s(R)= ；t(R)=。

3．设R为集合A上的等价关系，对aA，集合[a]R=，称

为

元

素

a

形

成的R

等

价

类，[a]R，因

为。

4．任意两个不同小项的合取为，全体小项的析取式为。

5．设Q(x):x为偶数，P(x):x为素数，则下列命题：（1）存在唯一偶素数；（2）至多有一个偶素数；分别形式化：（1）；

（2）。

6．设T为根树，若，则称T为m元树；

若则称T为完全m叉树。

7．含5个结点，4条边的无向连通图（不同构）有 个，它们是。

三、判断改正题：（每小题2分，本大题共20分）

1．命题公式(A(AB))B是一个矛盾式。（）2．任何循环群必定是阿贝尔群，反之亦真。（）3．根树中最长路径的端点都是叶子。（）4．若集合A上的关系R是对称的，则R



1也是对称的。（）

5．数集合上的不等关系（≠）可确定A的一个划分。（）6．设集合A、B、C为任意集合，若A×B = A×C，则B = C。（）7．函数的复合运算“。”满足结合律。（）8．若G是欧拉图，则其边数e合结点数v的奇偶性不能相反。（）9．图G为（n , m）图，G的生成树TG必有n个结点。（）10．使命题公式P(QR)的真值为F的真值指派的P、Q、R值分别是T、F、F。（）

四、简答题（每小题5分，本大题共25分）

1．设H,和K,都是群G,的子群，问HK,和HK,是否是

G,的子并说明理由。

3，4，9}，B{2，4，7，10,12}，从A到B的关系 2．设A{2，R{a,baA,bB,且a整除b}，试给出R的关系图和关系矩阵，并说明此

关系是否为函数？为什么？

3．设S,是半群，OL是左零元，对任xS,xOL是否是左零元？为什么？

4．某次会议有20人参加，其中每人至少有10个朋友，这20人拟围一桌入席，用图论知识说明是否可能每人邻做的都是朋友？（理由）

5．通过主合取范式，求出使公式(PQ)R的值为F的真值指派。

五、证明题：（共30分）

1．设R为集合A上的二元关系，如果R是反自反的和可传递的，则R一定是反对称的。

2．试证明若G,是群，HG，且任意的aH，对每一个xG，有axxa，则H,是G,的子群。

3．设G是每个面至少由k（k3）条边围成的连通平面图，试证明为结点数，e为边数。

4．符号化下列各命题，并说明结论是否有效（用推理规则）。任何人如果他喜欢美术，他就不喜欢体育。每个人或喜欢体育，或喜欢音乐，有的人不喜欢音乐，因而有的人不喜欢美术。答案

e

k(v2)k

2，其中v

一、单项选择题：

1．N

2;

。r(R){1,2,2,4,3,3,1,1,2,2,4,4}，2．

s(R){1,2,2,4,3,3,2,1,4,2}，RRR{1,4,3,3}，RRR{3,3}，RRR{3,3}，所以，t(R){1,2,2,4,3,3,1,4}。

3．[a]R{xxA,aRx}；a[a]R。4．永假式（矛盾式），永真式（重言式）。5．（1）x((Q(x)P(x))y(Q(y)P(y)xy))。（2）xy(Q(x)P(x)Q(y)P(y)xy)。

6．每个结点的出度都小于等于m；除叶子外，每个结点的出度都等于m。7．3。

三、判断改正题：

1．×命题公式(A(AB))B是一个重言式。2．×任何循环群必定是阿贝尔群，但反之不真。3．×根树中最长路径的端点不都是叶子。

4．√5．×≠不能确定A的一个划分。6．√7．√

8．×欧拉图其边数e和结点数v的奇偶性可以相反。9．√10．√

四、简答题

1．解：HK,是 G,的子群，HK,不一定是G,的子群。a,bHK,则的子群，a,bH,a,bK,由

H,和K,都是G,



ab



1H且ab

1

K,ab

1

HK,HK,是G,的子群。

如：G = {1，5，7，11}，：模12乘，则G,为群。且H = {1，5}，K = {1，7}，H,和K,皆为G,的子群，但HK{1,5,7}，HK,不是G,的子群。因为 5711HK，即运算不封闭。

2．解：R{2,2,2,4,2,10,2,12,3,12,4,4,4,12}则R的关系图为： R的关系矩阵为

10

00

1010

0000

1000

1110

M

R

关系R不是A到B的函数，因为

元素2，4的象不唯一（或元素9无象）

3．解：xOL仍是左零元。因为yS，由于OL是左零元，所以，OLyOL，又S,为半群，所以*可结合。

所以，(xOL)yx(OLy)xOL，所以，xOL仍是左零元。

4．解：可能。将人用结点表示，当两人是朋友时相应结点间连一条边，则得一个无向图

GV,E，20人围一桌，使每人邻做都是朋友，即要找一个过每个点一次且仅

一次得回路。由题已知，u,vV,deg(u)10,deg(v)10，deg(u)deg(v)20，由判定定理，G中存在一条汉密尔顿回路。即所谈情况可能。

5．解：

原式(PQ)R(PQ)R(PR)(QR)

(PQR)(PQR)(PQR)(PQR)M100M110M

010

∴使公式(PQ)R的值为F的真值指派为：

P:1



Q:0R:0；

P:1



Q:1R:0；

P:0



Q:1R:0。

五、证明题：

1．证明：假设R不是反对称的，则 x,yR,性，∴ x,xR 此与R反自反矛盾，∴R反对称。

y,xR,xy 由R的传递

2．证明：（1）设群G,的幺元为e，则xG有 xeex，∴eH即H非空。（2）a,bH，则 xG 有 axxa,bxxb，从而

(ab

1)x(ab

1

11)x(bb

1)

a(bb)xb

1

(ax)b

1

1

x(ab),abH

故 H,是G,的子群。

3．解：设连通平面图G有t个面：r1,r2,,rt则有 ver2，deg(ri)k,2k



tt

又有题意，deg(ri)kt

i1

又

e

deg(r)2e

i

i1，∴2ekt，teve

2k

e2

kk2

(v2)

。从而，∴。

4．解：设P(x)：x喜欢美术，Q(x)：x喜欢体育，R(x)：x喜欢音乐。论域：人。

命题形式化为：前提：x(P(x)Q(x))，x(Q(x)R(x))，xR(x)结论：xP(x)。证明：（1）xR(x)P(2)R(a)ES(1)(3)x(Q(x)R(x))P(4)Q(a)R(a)US(4)(5)Q(a)T(2)(4)I(6)x(P(x)Q(x))P(7)P(a)Q(a)US(6)(8)P(a)T(5)(7)I(9)xP(x)EG(8)∴ 结论有效。

第二篇：离散数学试卷1（范文）

离散数学试题（1）

一、单项选择题（本大题共15小题，每小题1分，共15分）

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1．下列是两个命题变元p，q的小项是（）

A．p∧┐p∧qB．┐p∨q

C．┐p∧qD．┐p∨p∨q

2．令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）

A．p→┐q

C．p∧q

B．p∨┐q D．p∧┐q B．x+y=10 D．x mod 3=2 3．下列语句中是命题的只有（）A．1+1=10C．sinx+siny<0

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．满射函数

C．双射函数B．入射函数 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

C．{{Ø},{{Ø}}}∈BB．{{Ø,Ø}}∈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．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

离散数学试题（1）

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中的有理数}

+C．{R中的自然数}

A．是交换群 +++

B．{R中的无理数} D．{1，2，3} B．是加法群 D．*对是可分配的 +13．设是环，则下列正确的是（）C．对*是可分配的14．下列各图不是欧拉图的是（）

15．设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（）

A．2个面B．3个面

C．4个面D．5个面

第二部分非选择题（共85分）

二、填空题（本大题共10小题，每空1分，共20分）

请在每小题的空格中填上正确答案。错填、不填均无分。

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的自反闭包。

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的度数是。

三、计算题（本大题共6小题，第26—27小题每小题4分，第28、30小题每小题5分，第29、31小题每小题6分，共30分）

26．（4分）求出从A={1,2}到B={x,y}的所有函数，并指出哪些是双射函数，哪些是满射函

数。

27．（4分）如果论域是集合{a,b,c}，试消去给定公式中的量词：(y)(x)(xy0)。

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

是群。

在群

中，①找出其幺元。②找出任一元素的逆元。③求元素x使满足{a}x={b}。

29．（6分）用等值演算法求公式┐(p→q)

(p→┐q)的主合取范式

30．（5分）画出5个具有5个结点5条边的非同构的无向连通简单图。

31．（6分）在偏序集中，其中Z={1,2,3,4,6,8,12,14}，≤是Z中的整除关系，求集合D={2,3,4,6}的极大元，极小元，最大元，最小元，最小上界和最大下界。

四、证明题（本大题共3小题，第32~33小题每小题6分，第34小题8分，共20分）

32．（6分）用等值演算法证明((q∧s)→r)∧(s→(p∨r))(s∧(p→q))→r

33．（6分）设n阶无向树G=中有m条边，证明m=n-1。

34．（8分）设P={Ø,{1},{1,2},{1,2,3}}，是集合P上的包含关系。

（1）证明：

是偏序集。

（2）在（1）的基础上证明

是全序集

五、应用题(15分）

35．（9分）在谓词逻辑中构造下面推理的证明：每个在学校读书的人都获得知识。所以如

果没有人获得知识就没有人在学校读书。（个体域：所有人的集合）

第三篇：离散数学试卷

诚信应考,考试作弊将带来严重后果！华南理工大学期末考试 《离散数学》试卷A 注意事项：1.考前请将密封线内填写清楚；2.所有答案请直接答在试卷上；3．考试形式：闭卷；4.本试卷共五大题，满分100分，考试时间120分钟

一、填空题(本大题共12小题，每小题2分，共24分)1．求合式公式xP(x)→xQ(x,y)的前束范式________________。2．设集合A={a, b, {a,b}, }, B = {{a,b}, }，求B-A=_____________． 3．设p与q的真值为0,r,s的真值为1则命题(s(q(rp)))(rp)的真值是__________.4．设R是在正整数集合Z上如下定义的二元关系Rx,y(x,yZ)(xy1，0)则它一共有个有序对，且有自反性、对称性、传递性、反自反性和反对称性各性质中的性质。5．公式x(P(x)→Q(x,y))→S(x)中的自由变元为________________，约束变元为________________。6．设有命题T(x): x 是火车，C(x): x是汽车，Q(x, y): x跑得比y快，那么命题“有的汽车比一些火车跑得快”的逻辑表达式是______________________.7．设G是n阶m条边的无向图，若G连通且m=__________则G是无向树.8．设X={1，2，3}，f：X→X，g：X→X，f={<1, 2>,<2,3>,<3,1>},g={<1,2>,<2,3>,<3,3>}，则f-1g=________________，gf=________________。9.不能再分解的命题称为________________，至少包含一个联结词的命题称为《离散数学》试卷A

________________．

10.连通无向图G含有欧拉回路的充分必要条件是 11．设集合A={,{a}}，则A的幂集P(A，|P(A)|=_____________________________。

12.设G = , G’ = 为两个图(同为无向图或有向图), 若E’  E且_______________, 则称G’是G的子图, 若E’  E且_______________, 则称G’是G的生成子图。

二、单选题(本大题共12小题，每小题2分，共26分)

1．下列命题公式为重言式的是（）

A.(p∨┐p)→q．B．p→(p∨q)C．q∧┐qD．(p→p)→q

2．下列语句中为命题的是()

A．你好吗？

B．人有6指.C．我所说的是假的.D．明天是晴天.3.设D=为有向图，V={a, b, c, d, e, f}, E={, , , ,}是（）

A．强连通图

C．弱连通图 B．单向连通图 D．不连通图

4．集合A＝{a，b，c}上的下列关系矩阵中符合偏序关系条件的是()

10

1011A．

001

11001011011110 B．010C．110D．010 11010010111

5．设A={1，2，3}，A上二元关系S={<1，1>，<1，2>，<3，2>，<3，3>}，则S是（）

A．自反关系 B．传递关系C．对称关系D． 反自反关系

6.设A={a,b,c,d}，A上的等价关系R={, , , }∪IA，则对应于R的A的划分是（）

A．{{a},{b, c},{d}}

C．{{a},{b},{c},{d}} B．{{a, b},{c}, {d}} D．{{a, b}, {c,d}}

7.以下非负整数列可简单图化为一个欧拉图的是()

A.{2, 2, 2, 2, 0}B.{4, 2, 6, 2, 2}

C.{2, 2, 3, 4, 1}D.{4, 2, 2, 4, 2}

8.设论域D＝{a，b }，与公式xA(x)等价的命题公式是()

A．A(a)∧A(b)B．A(a)→A(b)C．A(a)∨A(b)D．A(b)→A(a)

9.一棵树有3个4度顶点，4个2度顶点其余都是树叶，求这棵树有多少个树叶顶点()

A.12B.8C.10D.1

310.有ABC三个人猜测甲乙丙三个球队中的冠军.各人的猜测如下:

A: 冠军不是甲,也不是乙.B: 冠军不是甲,而是丙.C: 冠军不是丙,而是甲.已知其中有一个人说的完全正确.一个人说的都不对,而另外一人恰有一半说对了.据此推算,冠军应该是()

A．甲B.乙C.丙D.不确定

11．如第11题图所示各图，其中存在哈密顿回路的图是()

12．设C(x): x是国家级运动员，G(x): x是健壮的，则命题“没有一个国家级运动员不是健壮的”可符号化为()

(A)x(C(x)G(x))(B)x(C(x)G(x))

(C)x(C(x)G(x))(D)x(C(x)G(x))

三．计算题(30分)

1．用等值演算法求取求下列公式：(PQ)(P∨Q)的合取范式（5分）

2．图G如下图所示，求图G的最小生成树.（5分）

3．有向图D如图所示，求D的关联矩阵M(D)（5分）

4.化简表达式(((A(BC))

A)(B(BA)))(CA)（7分）

5．设R={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)和s(R)，并作出它们及R的关系图(8分)

五．证明题(22分)

1．构造下面推理的证明(5分)

前提：pq，pr，st，sr，t

结论：q

2．设A={1, 2, 3, 4}, 在AA定义的二元关系R，u,v,x,yAA, uRxuy +xv

证明R是AA上的等价关系。(5分)

3．已知A、B、C是三个集合，证明A-(B∪C)=(A-B)∩(A-C)（6分）

4． 无向图G = ，且|V|=n, |E|=m, 试证明以下两个命题是等价命题

1）G中每对顶点间具有唯一的通路，2）G连通且n=m+1。（6分）

第四篇：离散数学试题与答案

《离散数学》试题及答案

一、选择题：本题共5小题，每小题3分，共15分，在每小题给出的四个选项中，只有一项是符合题目要求的。

1.命题公式(PQ)Q为()

(A)矛盾式(B)可满足式(C)重言式(D)合取范式

2．设P表示“天下大雨”，Q表示“他在室内运动”，则命题“除非天下大雨，否则他不在室内运动”符号化为（）。

(A)． PQ；(B)．PQ；(C)．PQ；(D)．PQ．

3.设集合A={{1,2,3}, {4,5}, {6,7,8}}，则下式为真的是()

(A)1A(B){1,2, 3}A

(C){{4,5}}A(D)A

4.设A＝{1,2},B={a,b,c},C={c,d}, 则A×(BC)=()

(A){<1,c>,<2,c>}(B){,<2,c>}(C){,}(D){<1,c>,}

5.设G如右图：那么G不是().(A)哈密顿图；(B)完全图；

(C)欧拉图；(D)平面图.二、填空题：本大题共5小题，每小题4分，共20

6.设集合A={,{a}}，则A的幂集P(A7.设集合A={1,2,3,4 }, B={6,8,12}, A到B的关系R＝{x,yy2x,xA,yB},那么R1＝－

8.在“同学，老乡，亲戚，朋友”四个关系中_______是等价关系.9.写出一个不含“”的逻辑联结词的完备集.10.设X＝{a,b,c}，R是X上的二元关系，其关系矩阵为

101，那么R的关系图为 MR＝100100

三、证明题（共30分）

11.（10分）已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C)

12.（10分）构造证明：(P(QS))∧(R∨P)∧QRS

（0,1）13.（10分）证明与[0,1)，[0,1)与[0,1]等势。

四、解答题(共35分)

14.（7分）构造三阶幻方（以1为首项的9个连续自然数正好布满一个33方阵，且方阵中的每一行, 每一列及主、副对角线上的各数之和都相等.）

15.（8分）求命题公式(PQ)(PQ)的真值表.16.（10分）设R1是A1＝{1,2}到A2＝(a,b,c)的二元关系，R2是A2到A3＝{,}的二元关系，R1= {<1,a>,<1,b>,<2,c>}, R2={,}

毕节学院《离散数学 》课程试卷

求R1R2的集合表达式.17.（10分）某项工作需要派A、B、C和D 4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？

三个条件：(1)若A去，则C和D中要去1个人；(2)B和C不能都去；

(3)若C去，则D留下。

一、单项选择题(每小题3分，共15分)

1.B2.C3.C4.A5.B

二、填空题(每小题4分，共20分)

6.{,{},{{a}},{,{a}}}

7.{<6,3>,<8,4> }8.老乡

9.{,}或{,} 或 {}或 {}

10.见

f(0)0111························································································ 10分 ,n1,A ·f()n1nn

f(x)x,x[0,1)A

14.85 1 2 7 6

填对每个格得1分。

15.表中最后一列的数中，每对1个数得2分.11016.MR1,(2分)001

MR201(4分)0100

010101(6分)0000110 MR1R2001

R1R2{1,}(10分)

17.解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。······························································································ 2分 因此(ACD)∧(B∧C)∧(CD)

(A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D)

(A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D))

(A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D)

∨(C∧ D∧B∧C)∨(C∧ D∧B∧D)∨(C∧ D∧C)∨(C∧ D∧C∧D)

∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D∧C∧D)

F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F

(A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D)

(A∧C)∨(B∧C∧ D)∨(C∧D)

T ··································································································································· 8分

毕节学院《离散数学 》课程试卷

故有三种派法：B∧D，A∧C，A∧D。······································································· 10分

毕节学院《离散数学 》课程试卷

第五篇：离散数学考试试题(A卷及答案)

离散数学考试试题（A卷及答案）

一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？ 1)((PQ)∧Q)((Q∨R)∧Q)2)((QP)∨P)∧(P∨R)3)((P∨Q)R)((P∧Q)∨R)解：1)永真式；2）永假式；3)可满足式。

二、（8分）个体域为{1，2}，求xy（x+y=4）的真值。

解：xy（x+y=4）x（（x+1=4）∨（x+2=4））

（（1+1=4）∨（1+2=4））∧（（2+1=4）∨（2+1=4））（0∨0）∧（0∨1）1∧10

三、（8分）已知集合A和B且|A|=n，|B|=m，求A到B的二元关系数是多少？A到B的函数数是多少？

解：因为|P(A×B)|=2|A×B|=2|A||B|=2mn，所以A到B的二元关系有2mn个。因为|BA|=|B||A|=mn，所以A到B的函数mn个。

四、（10分）已知A={1,2,3,4,5}和R={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>}，求r(R)、s(R)和t(R)。

解：r(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>} s(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<3,2>,<4,3>,<4,5>} t(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<1,3>,<2,2>,<2,4>,<1,4>}

五、(10分)75个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都乘过，其中55人至少乘坐过其中的两种。若每样乘坐一次的费用是0.5元，公园游乐场总共收入70元，求有多少儿童没有乘坐过其中任何一种。

解 设A、B、C分别表示骑旋转木马、坐滑行铁道、乘宇宙飞船的儿童组成的集合，|A∩B∩C|＝20，|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|＝55，|A|＋|B|＋|C|＝70/0.5＝140。

由容斥原理，得

|A∪B∪C|＝|A|＋|B|＋|C|―|A∩B|―|A∩C|―|B∩C|＋|A∩B∩C| 所以

|A∩B∩C|＝75－|A∪B∪C|＝75－(|A|＋|B|＋|C|)＋(|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|)＋|A∩B∩C|＝75－140＋55＋20＝10 没有乘坐过其中任何一种的儿童共10人。

六、（12分）已知R和S是非空集合A上的等价关系，试证：1）R∩S是A上的等价关系；2）对a∈A，[a]R∩S=[a]R∩[a]S。

解：x∈A，因为R和S是自反关系，所以∈R、∈S，因而∈R∩S，故R∩S是自反的。

x、y∈A，若∈R∩S，则∈R、∈S，因为R和S是对称关系，所以因∈R、∈S，因而∈R∩S，故R∩S是对称的。x、y、z∈A，若∈R∩S且∈R∩S，则∈R、∈S且∈R、∈S，因为R和S是传递的，所以因∈R、∈S，因而∈R∩S，故R∩S是传递的。

总之R∩S是等价关系。

2）因为x∈[a]R∩S∈R∩S∈R∧∈S x∈[a]R∧x∈[a]S x∈[a]R∩[a]S 所以[a]R∩S=[a]R∩[a]S。

七（10分）设A、B、C、D是集合，f是A到B的双射，g是C到D的双射，令h：A×CB×D且∈A×C，h()＝。证明h是双射。

证明：1）先证h是满射。

∈B×D，则b∈B，d∈D，因为f是A到B的双射，g是C到D的双射，所以存在a∈A，c∈C，使得f(a)=b，f(c)=d，亦即存在∈A×C，使得h()＝＝，所以h是满射。

2）再证h是单射。

、∈A×C，若h()＝h()，则＝，所以f(a1)＝f(a2)，g(c1)＝g(c2)，因为f是A到B的双射，g是C到D的双射，所以a1＝a2，c1＝c2，所以＝，所以h是单射。综合1）和2），h是双射。

八、（12分）是个群，u∈G，定义G中的运算“”为ab=a*u-1*b，对任意a,b∈G，求证：也是个群。

证明：1）a,b∈G，ab=a*u-1*b∈G，运算是封闭的。

2）a,b,c∈G，（ab）c=（a*u-1*b）*u-1*c=a*u-1*（b*u-1*c）=a（bc），运算是可结合的。3）a∈G，设E为的单位元，则aE=a*u-1*E=a，得E=u，存在单位元。

4）a∈G，ax=a*u-1*x=E，x=u*a-1*u，则xa=u*a-1*u*u-1*a=u=E，每个元素都有逆元。所以也是个群。

九、（10分）已知：D=，V={1,2,3,4,5}，E={<1,2>,<1,4>,<2,3>,<3,4>,<3,5>,<5,1>}，求D的邻接距阵A和可达距阵P。

解：D的邻接距阵A和可达距阵P如下：

A= 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0

0 0 1 0 0

P= 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1

十、（10分）求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。

解：最优二叉树为

权＝148

离散数学考试试题（B卷及答案）

一、（10分）求命题公式(P∧Q)(PR)的主合取范式。

解：(P∧Q)(PR)（(P∧Q)(PR)）∧（(PR)(P∧Q)）（(P∧Q)∨(P∧R)）∧（(P∨R)∨(P∨Q)）(P∧Q)∨(P∧R)(P∨R)∧（Q∨P）∧（Q∨R）

(P∨Q∨R)∧(P∨Q∨R)∧（P∨Q∨R）∧（P∨Q∨R）M1∧M3∧M4∧M5

二、（8分）叙述并证明苏格拉底三段论

解：所有人都是要死的，苏格拉底是人，所以苏格拉底是要死的。符号化：F（x）：x是一个人。G（x）：x要死的。A：苏格拉底。命题符号化为x（F（x）G（x）），F（a）G（a）证明：

（1）x(F(x)G(x))P（2）F(a)G(a)T(1),US（3）F(a)P（4）G(a)T(2)(3),I

三、（8分）已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C)证明：∵x A∩（B∪C） x A∧x（B∪C）

 x A∧（xB∨xC）

（x A∧xB）∨（x A∧xC） x（A∩B）∨x A∩C  x（A∩B）∪（A∩C）

∴A∩（B∪C）=（A∩B）∪（A∩C）

四、（10分）已知R和S是非空集合A上的等价关系，试证：1）R∩S是A上的等价关系；2）对a∈A，[a]R∩S=[a]R∩[a]S。

解：x∈A，因为R和S是自反关系，所以∈R、∈S，因而∈R∩S，故R∩S是自反的。

x、y∈A，若∈R∩S，则∈R、∈S，因为R和S是对称关系，所以因∈R、∈S，因而∈R∩S，故R∩S是对称的。

x、y、z∈A，若∈R∩S且∈R∩S，则∈R、∈S且∈R、∈S，因为R和S是传递的，所以因∈R、∈S，因而∈R∩S，故R∩S是传递的。

总之R∩S是等价关系。

2）因为x∈[a]R∩S∈R∩S

∈R∧∈S x∈[a]R∧x∈[a]S x∈[a]R∩[a]S 所以[a]R∩S=[a]R∩[a]S。

五、(10分)设A＝{a，b，c，d}，R是A上的二元关系，且R＝{，，，}，求r(R)、s(R)和t(R)。

解 r(R)＝R∪IA＝{，，，，，，，} s(R)＝R∪R＝{，，，，，} R＝{，，，} R＝{，，，} R＝{，，，}＝R

t(R)＝R＝{，，，，，，，，} i1i

4232-

1六、(15分)设A、B、C、D是集合，f是A到B的双射，g是C到D的双射，令h：A×CB×D且∈A×C，h()＝。证明h是双射。

证明：1）先证h是满射。

∈B×D，则b∈B，d∈D，因为f是A到B的双射，g是C到D的双射，所以存在a∈A，c∈C，使得f(a)=b，f(c)=d，亦即存在∈A×C，使得h()＝＝，所以h是满射。

2）再证h是单射。

、∈A×C，若h()＝h()，则＝，所以f(a1)＝f(a2)，g(c1)＝g(c2)，因为f是A到B的双射，g是C到D的双射，所以a1＝a2，c1＝c2，所以＝，所以h是单射。

综合1）和2），h是双射。

七、(12分)设是群，H是G的非空子集，证明是的子群的充要条件是若a，bH，则有a*bH。

证明： a,b∈H有b∈H，所以a*b∈H。a∈H，则e=a*a∈H-1-

1-1-1a=e*a∈H ∵a,b∈H及b∈H，∴a*b=a*（b）∈H ∵HG且H≠,∴*在H上满足结合律 ∴是的子群。

八、（10分）设G=是简单的无向平面图，证明G至少有一个结点的度数小于等于5。

解：设G的每个结点的度数都大于等于6，则2|E|=d(v)≥6|V|，即|E|≥3|V|，与简单无向平面图-

1-1

-1-1-1的|E|≤3|V|-6矛盾，所以G至少有一个结点的度数小于等于5。九.G=,A={a,b,c},*的运算表为：(写过程，7分)

（1）G是否为阿贝尔群？

（2）找出G的单位元；（3）找出G的幂等元（4）求b的逆元和c的逆元 解：（1）(a*c)*(a*c)=c*c=b=a*b=(a*a)*(c*c)(a*b)*(a*b)=b*b=c=a*c=(a*a)*(b*b)(b*c)*(b*c)=a*a=a=c*b=(b*b)*(c*c)所以G是阿贝尔群

（2）因为a*a=a a*b=b*a=b a*c=c*a=c 所以G的单位元是a（3）因为a*a=a 所以G的幂等元是a（4）因为b*c=c*b=a，所以b的逆元是c且c的逆元是b

十、(10分)求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。

解：最优二叉树为

权＝148 5