离散数学期末考试试题及答案[5篇范文]

第一篇：离散数学期末考试试题及答案

离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。下面是小编整理的离散数学期末考试试题及答案，欢迎阅读参考！

一、【单项选择题】

(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。

1、在由3个元素组成的集合上，可以有()种不同的关系。

[A] 3 [B] 8 [C]9 [D]272、设A1,2,3,5,8,B1,2,5,7,则AB()。

[A] 3,8 [B]3 [C]8 [D]3,83、若X是Y的子集，则一定有()。

[A]X不属于Y [B]X∈Y

[C]X真包含于 Y [D]X∩Y=X4、下列关系中是等价关系的是()。

[A]不等关系 [B]空关系

[C]全关系 [D]偏序关系

5、对于一个从集合A到集合B的映射，下列表述中错误的是()。

[A]对A的每个元素都要有象 [B] 对A的每个元素都只有一个象

[C]对B的每个元素都有原象 [D] 对B的元素可以有不止一个原象

6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为()。

[A]p→q [B]q→p [C]┐q→┐p [D]┐p→q7、设A={a,b,c},则A到A的双射共有()。

[A]3个 [B]6个 [C]8个 [D]9个

8、一个连通G具有以下何种条件时，能一笔画出：即从某结点出发，经过中每边仅一次回到该结点()。

[A] G没有奇数度结点 [B] G有1个奇数度结点

[C] G有2个奇数度结点 [D] G没有或有2个奇数度结点

9、设〈G,*〉是群，且|G|>1，则下列命题不成立的是()。

[A] G中有幺元 [B] G中么元是唯一的[C] G中任一元素有逆元 [D] G中除了幺元外无其他幂等元

10、令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为()

[A] p→┐q [B] p∨┐q

[C] p∧q [D] p∧┐q11、设G=的结点集为V={v1,v2,v3},边集为E={,}.则G的割(点)集是()。

[A]{v1} [B]{v2} [C]{v3} [D]{v2,v3}

12、下面4个推理定律中，不正确的为()。

[A]A=>(A∨B)(附加律)[B](A∨B)∧┐A=>B(析取三段论)

[C](A→B)∧A=>B(假言推理)[D](A→B)∧┐B=>A(拒取式)

13、在右边中过v1,v2的初级回路有多少条()

[A] 1 [B] 2 [C] 3 [D]

414、若R，是环，且R中乘法适合消去律，则R是()。

[A]无零因子环

[C]整环 [B]除环 [D]域

15、无向G中有16条边，且每个结点的度数均为2，则结点数是()。

[A]8 [B]16 [C]4 [D]

32二、【判断题】

(本大题共8小题，每小题3分，共24分)正确的填T，错误的填F，填在答题卷相应题号处。

16、是空集。()

17、设S,T为任意集合，如果S—T=，则S=T。()

18、在命题逻辑中，任何命题公式的主合取范式都是存在的，并且是唯一的。()

19、关系的复合运算满足交换律。()

20、集合A上任一运算对A是封闭的。()

21、0,1,2,3,4,max,min是格。()

22、强连通有向一定是单向连通的。()

23、设都是命题公式，则(PQ)QP。()

三、【解答题】

(本大题共3小题，24、25每小题10分，26小题11分，共31分)请将答案填写在答题卷相应题号处。

24、设集合A={a, b, c}，B={b, d, e}，求

(1)BA;(2)AB;(3)A-B;(4)BA.25、设非空集合A，验证(P(A)，,~，A)是布尔代数

26、如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而且学过C++语言。只要他学过DELPHI语言或者C++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。

离散数学试题答案

一、【单项选择题】(本大题共15小题，每小题3分，共45分)

BDDCCCBABDADCBB

二、【判断题】(本大题共8小题，每小题3分，共24分)

FFTFTTTF

三、【解答题】(本大题共3小题，24、25每小题10分，26小题11分，共31分)

24、设集合A={a, b, c}，B={b, d, e}，求(1)BA;(2)AB;(3)A-B;(4)BA.标准答案：(1)BA={a, b, c}{b, d, e}={ b }

(2)AB={a, b, c}{b, d, e}={a, b, c, d, e }

(3)A-B={a, b, c}-{b, d, e}={a, c}

(4)BA= AB-BA={a, b, c, d, e }-{ b }={a, c, d, e }

复习范围或考核目标：考察集合的基本运算，包括交集，并集,见课件第一章第二节,集合的运算。

25、设非空集合A，验证(P(A)，,~，A)是布尔代数

标准答案：证明 因为集合A非空，故P(A)至少有两个元素，显然，是P(A)上的二元运算.由定理10，任给B,C,DP(A), H1 BD=DC CD=DC

H2 B(CD)=(BC)(BD)B(CD)=(BC)(BD)

H3 P(A)存在和A，BP(A), 有B=B，BA=B

H4，BP(A), BA，存在A~B，有

BA~B)= A B(A～B)=

所以(P(A)，,~，A)是布尔代数.复习范围或考核目标：考察布尔代数的基本概念，集合的运算，见课件代数系统中布尔代数小节。

26、如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而且学过C++语言。只要他学过DELPHI语言或者C++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。

标准答案：令p：他是计算机系本科生

q：他是计算机系研究生 r：他学过DELPHI语言

s:他学过C++语言

t:他会编程序

前提：(p∨q)→(r∧s),(r∨s)→t

结论：p→t

证①p P(附加前提)

②p∨q T①I

③(p∨q)→(r∧s)P(前提引入)

④r∧s T②③I

⑤r T④I

⑥r∨s T⑤I

⑦(r∨s)→t P(前提引入)

⑧t T⑤⑥I

第二篇：离散数学期末考试

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

1、设集合M={a，}，N ={{a}，}则MN=（）。A、 B、{} C、{a} D、{{a}，，a}

2、设关系F={<1，a >，<2，2>，}，G={，，<1，2>}则 FG=（）。

A、{<1，b>，<1，c>，}

B、{，，<1，b>} C、{，<1，2>}

D、{，<2，2>，<1，b>}

3、设集合H={1，2，3，4}，则H上的关系R={

。x +y是偶数}具有（）A、自反性、反对称性和传递性

B、反自反性、反对称性和传递性

C、反自反性、对称性和传递性

D、自反性、对称性和传递性

4、设T是一棵完全二叉树，则T的每个结点都（）。

A、至少有两个子结点

B、至多有两个子结点

C、恰有两个子结点

D、可以有任意多个子结点

5、设R是实数集，“+，—，A、

>是群

B、是群

 >是半群

D、是独异点

6、下面关系中，函数关系是（）。

A、{，，}

B、{，，<1，x>} C、{<1，y>，<1，x>，}

D、{，，}

7、设是一个代数系统，若多任意的x，yS，都有xy=yx，则称运算在S上满足（）。

A、结合律

B、交换律

C、分配律

D、幂等律

8、设Z是整数集，“—”是整数减法，则下列说法正确的是（）。A、不是代数系统

B、的单位元是0

C、是代数系统

D、的单位元是1

9、设L是无向图G中的一条通路，L中的顶点各不相同，则L是一条（）。A、简单通路

B、初级通路

C、简单回路

D、初级回路

10、设G有6个3度点，2个4度点，其余顶点的度数均为0，则G的边数是（）。A、10

B、13

C、11

D、6

二、填空题(本大题共8题，共10个空，每空2分，共20分)

1、设关系R={，<2，1>，<2，b>}，则R逆关系R1=_______________________________。

2、在代数系统（Q是有理数集，“+”是有理数加法）中，单位元是______，2的逆元是___________。

3、设集合M={1，2，3，5}，则M的幂集P（M）包含___________个元素。

4、设T是一棵有n(n2)个顶点的树，则T有_____________条边。

5、设是一个代数系统，是S上的二元运算，若存在S，对任意xS，有x=x=，则称是的_______________。

6、设是一个代数系统，若满足结合律且中有单位元，则称为一个___________________。

7、设D是有向图，若D的基图是连通图，则称D是_________________图

8、既不含________________也不含____________________的无向图称为简单图。

三、计算题(本大题共3小题，每小题10分，共30分)

1、用等值演算法求公式A=(pq)(pr)的主析取范式。

2、求公式x(Q(x)G(x，s))(yP(y)zH(y，z))的前束范式。

3、设集合A={1，2，3，4，5}，关系R={（1）列出R的所有元素；（2）写出R的关系矩阵Mx，y A且x整除y}，要求：

R；

（3）求偏序集的极大元、极小元和最小元。

四、应用题(本大题共2小题，每小题5分，共10分)

1、用命题公式将下列命题符号化： 2和5是偶数，当且仅当5>2。

2、用谓词公式将下列命题符号化：

每个计算机专业的学生都要学《编译原理》，但有些计算机专业的学生不学《经济学》。

五、证明题（本大题共2小题，每小题10分，共20分）

1、在命题逻辑系统中用归结法证明下列推理是有效的： 前提：sq，pq，s 结论：p

2、在谓词逻辑系统中写出下列推理的（形式）证明：

前提：x(M(x)P(x))，x(M(x)G(x))，x(G(x))结论：xP(x)

计算题

6.设命题公式G = (P→Q)∨(Q∧(P→R)), 求G的主析取范式。

7.(9分)设一阶逻辑公式：G =(xP(x)∨yQ(y))→xR(x)，把G化成前束范式.9.设R是集合A = {a, b, c, d}.R是A上的二元关系, R = {(a,b),(b,a),(b,c),(c,d)},(1)求出r(R), s(R), t(R)；(2)画出r(R), s(R), t(R)的关系图.11.通过求主析取范式判断下列命题公式是否等价：

(1)G =(P∧Q)∨(P∧Q∧R)

(2)H =(P∨(Q∧R))∧(Q∨(P∧R))13.设R和S是集合A＝{a, b, c, d}上的关系，其中R＝{(a, a),(a, c),(b, c),(c, d)}，S＝

{(a, b),(b, c),(b, d),(d, d)}.(1)试写出R和S的关系矩阵；(2)计算R•S, R∪S, R1, S1•R1.－

－

－证明题

1.利用形式演绎法证明：{P→Q, R→S, P∨R}蕴涵Q∨S。2.设A,B为任意集合，证明：(A-B)-C = A-(B∪C).3.(本题10分)利用形式演绎法证明：{A∨B, C→B, C→D}蕴涵A→D。4.(本题10分)A, B为两个任意集合，求证：

A－(A∩B)=(A∪B)－B.答案：

1-5

BADBB 6-10 BBABB

1.{<1，a>，<1，2>，} 2.0，-2 3.16 4.n-1 5.零元 6.半群 7.弱连通 8.平行边

环 三．

(pq)(pr)(pq)(pr)1.(pqr)(pqr)(pqr)(pqr)m011m010m111m1012.x(Q(x)G(x,s))yz(P(y)H(y,z))

yzx((Q(x)G(x,s))(P(y)H(y,z))3.(1)R{1,1,2,2,3,3,4,4,5,5,1,2,1,3,1,4,1,5,2,4}

12(2)MR345123451111101010

（3）最小元=1 极小元=1 极大元=5 001000001000001四

1.令p表示2是偶数；令q表示5是偶数；r表示5>2；

(pq)r

2.S（x）：x是计算机专业的学生；G（x）：x要学《编译原理》； F（x）：x学经济学；

x(S(x)G(x))x(S(x)F(x))

五 1，（1）

s

前提引入（2）

sq

前提引入（3）

qs

置换规则

（4）

q

1,3析取三段论（5）

pq

前提引入（6）

p

4,5拒取

（1）

x(M(x)G(x))

前提引入（2）

M（x）v G（x）

EI规则（3）

x(G(x))

前提引入（4）

G(x)（5）

M(x)

AI规则

2,4析取三段论

（6）

x(M(x)P(x))

前提引入（7）

M(x)→P（x）

AI规则（8）

P（x）

5,7假言推理（9）

xP(x)

EG规则

6.G = (P→Q)∨(Q∧(P→R))

= (P∨Q)∨(Q∧(P∨R))=(P∧Q)∨(Q∧(P∨R))=(P∧Q)∨(Q∧P)∨(Q∧R)=(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)=(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)= m3∨m4∨m5∨m6∨m7 = (3, 4, 5, 6, 7).7.G =(xP(x)∨yQ(y))→xR(x)

= (xP(x)∨yQ(y))∨xR(x)=(xP(x)∧yQ(y))∨xR(x)=(xP(x)∧yQ(y))∨zR(z)= xyz((P(x)∧Q(y))∨R(z))9.(1)r(R)＝R∪IA＝{(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d)}, s(R)＝R∪R1＝{(a,b),(b,a),(b,c),(c,b)(c,d),(d,c)}, －t(R)＝R∪R2∪R3∪R4＝{(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)}；(2)

关系图: abr(R)dcabs(R)dabt(R)dc c

11.G＝(P∧Q)∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝m6∨m7∨m3 ＝(3, 6, 7)H =(P∨(Q∧R))∧(Q∨(P∧R))＝(P∧Q)∨(Q∧R))∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝m6∨m3∨m7 ＝(3, 6, 7)G,H的主析取范式相同，所以G = H.1013.(1)MR00000011000000

MS10001000010001 01(2)R•S＝{(a, b),(c, d)}, R∪S＝{(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d)}, R1＝{(a, a),(c, a),(c, b),(d, c)}, －S1•R1＝{(b, a),(d, c)}.－－四 证明题

1.证明：{P→Q, R→S, P∨R}蕴涵Q∨S

(1)P∨R

(2)R→P(3)P→Q(4)R→Q(5)Q→R(6)R→S

P Q(1)P Q(2)(3)Q(4)P

(7)Q→S(8)Q∨S Q(5)(6)Q(7)2.证明：(A-B)-C =(A∩~B)∩~C

3.= A∩(~B∩~C)= A∩~(B∪C)= A-(B∪C)证明：{A∨B, C→B, C→D}蕴涵A→D(1)A D(附加)P(2)A∨B(3)B Q(1)(2)P Q(4)(4)C→B(5)B→C(6)C

Q(3)(5)P(7)C→D(8)D Q(6)(7)D(1)(8)(9)A→D

所以 {A∨B, C→B, C→D}蕴涵A→D.1.证明：A－(A∩B)

= A∩~(A∩B)＝A∩(~A∪~B)＝(A∩~A)∪(A∩~B)＝∪(A∩~B)＝(A∩~B)＝A－B 而(A∪B)－B =(A∪B)∩~B =(A∩~B)∪(B∩~B)=(A∩~B)∪ = A－B 所以：A－(A∩B)=(A∪B)－B.

第三篇：离散数学期末复习试题及答案(二)

第二章 二元关系

1.设A={1,2,3,4},A上二元关系

R={(a,b)|a=b+2}，S={(x,y)|y=x+1 or y=

x2} 求RS,SR,SRS,S2,S

3,SRc。

RS={(3,2),(4,3),(4,1)} SR={(2,1),(3,2)} SRS={(2,2),(3,3),(3,1)} S2={(1,1),(1,3),(2,2),(2,4),(3,2),(4,1),(4,3)} S3={(1,2),(1,4),(2,1),(2,2),(2,3),(3,1),(3,3),(4,2),(4,4)} SRc={(1,4),(2,3),(4,4)}

2．A={a,b,c,d,e,f,g,h}，给定A上关系R的 关系图如下：

图3－14 求最小正整数ｍ，ｎ，ｍ＜ｎ，使Ｒm＝Ｒn。

Ｒ1＝Ｒ16

这是因为R15是8个顶点以及8个自回路，相 当于左图的点各走了5圈，左图的点各走了3圈，R16就成了原来的R．

３．证明：

(1)(InA)IA(a,a)I2nA,aA,(a,a)IA,...,(a,a)IA, (b,b)InA,bA,(b,b)IA.(2)IARRIAR(a,b)R,a,bA,(a,a)IA,(b,b)IA,(a,b)IAR,(a,b)RIA,即RI

AR,RRIA;(a,b)IAR,若(a,b)R,则(a,b)IAR,矛盾,得IARR;同理,RIAR.事实上，当|A|有限时，R与IA复合，相当于矩阵与 单位矩阵相乘，不会变化。

(3)(RIn2nA)IARR...Rn1(RIA)IAR;设(RIk2A)IARR...Rk

(RIk1(I2A)...RkARR)(RIA)(RR2...Rk1)(I2ARR...Rk)IR2...RkRk1AR

４．判断下列等式是否成立（Ｒ,Ｒ1,Ｒ2均是Ａ到Ｂ的 二元关系）

(1)(Rccc1R2)R1R2对,(a,b)(Rc1R2)(b,a)R1R2(b,a)R

1or(b,a)R2(a,b)Rc1or(a,b)Rc2(a,b)Rcc1R2

(2)(Rcc1R2)R1Rc2对(a,b)(Rc1R2)(b,a)R1R2(b,a)R

1and(b,a)R2(a,b)Rcc1and(a,b)R2(a,b)Rcc1R2

(3)(R1R2)R1R2对cccc(a,b)(R1R2)(R1R2)c(b,a)R1R2(b,a)R1,(b,a)R2

(a,b)Rc1,(a,b)Rc2(a,b)Rcccc1R2R1R2(4)(AB)cAB否,例:A{1,2},B{3,4},AB{(1,3),(2,3),(1,4),(2,4)}

(AB)c{(3,1),(3,2),(4,1),(4,2)}(5)c否,c

与的定义域,值域对换了一下.(6)(R)c(Rc)对,(a,b)(R)c(b,a)R(b,a)R(a,b)Rc(a,b)Rc(7)(Rcc1R2)R2Rc1否,R2的定义域不一定与R1的值域相同(8)如果Rcc1R2,则R1R2对,(a,b)Rc1,(b,a)R1R2,(a,b)Rc2.(9)如果R1Rcc2,则R1R2对,(a,b)Rc1,(b,a)R1R2,(a,b)Rc2，R1R2,(c,d)R2,(c,d)R1,(d,c)Rc2,而(d,c)Rc1..

(10)R1R2R2R1否,R

2的定义域不一定与R1的值域相同.5.设R1,R2是集合A上的二元关系，如果R2R1，其中r,s,t分别是自反闭包，对称闭包，传递闭包的 记号。试证明:(1)r(R2)r(R1)R2R1,IAIA, R2IAR1IA

(2)s(R2)s(R1)R2Rcc1,R2R1

Rcc2R2R1R1

(3)t(R2)t(R1)R222R1(R2)1(R1)1(即R2R2R1R1)(a,b)R(a,b)(R2R1(R1)1b)R22)1(a,2,cA,(a,c),(c,b)R2R1,(a,b)R21,(a,b)(R1)1(a,b)t(R2),k,使(a,b)(R2)k(R1)kt(R1).6.设R1,R2,R3,R4分别是A到B，B到C，B到C，Ｃ到D的二元关系，证明

(1)R1(R2R3)R1R2R1R3(x,y)R1(R2R3)z,(x,z)R1,(z,y)R2or(z,y)R3z,(x,z)R1,(z,y)R2or(x,z)R

1,(z,y)R3(x,y)R1R2or(x,y)R1R3(x,y)R1R2R1R3

(2)R1(R2R3)R1R2R1R3(x,y)R1(R2R3)z,(x,z)R1,(z,y)R2and(z,y)R3z,(x,z)R

1,(z,y)R2and(x,z)R1,(z,y)R3(x,y)R1R2and(x,y)R1R3(x,y)R1R2R1R3(3)(4)类(1)(2)证明。

7.设R是A上的二元关系，证明对任意自然数m,n，(1)RmRnRmn(2)(Rm)nRmn

由归

(1)1)n1,Rm1RmR2)假定RmRnRmn{(a,b)|cA,(a,c)Rm,(c,b)Rn}n1RmR{(a,b)|cA,(a,c)Rm,(c,b)Rn1}其中,Rn1{(c,b)|dA,(c,d)Rn,(d,b)R}RmRn1{(a,b)|c,dA,(a,c)Rm,(c,d)Rn,(d,b)R}{(a,b)|dA,(a,d)Rmn,(d,b)R}RmnRR(mn)1Rm(n1)

(2)1)n1,RmRm2)假定(Rm)nRmn(Rm)n1(Rm)nRmRmnRm

由(1)RmnmRm(n1)8.设R是A上的二元关系，｜A｜＝n，证明存在 自然数s,t，使RsRt,且0st2n2，其中定义

R0{(a,a)|aA}。

0(ai,aj)R证:R(rij)nn,rij1(ai,aj)R至多有2n2个不同的Rk(kN)出现,

0k2n2,由鸽洞原理,(2n21)个Rk中必存在s,t,0st2n2,RsRt.9.R1，R2是Ａ上的二元关系，判别下列命题正确与否

(1)如果R1，R2自反，则R1R2也自反。

对,aA,(a,a)R1,(a,a)R2,(a,a)R

1R2

(2)如果R1，R2反自反，则R1R2也反自反。

否,若(a,b)R1,(b,a)R2,(a,a)R1R2

(3)如果R1，R2对称，则R1R2也对称。

否,例:A{1,2,3},R1{(1,2),(2,1)},R2{(2,3),(3,2)},(1,2)R

1,(2,3)R2,(1,3)R1R2,而(3,1)R1R2

(4)如果R1，R2反对称，则R1R2也反对称。

否,例:A{1,2,3},R1{(1,2),(3,2)},R2{(2,3),(2,1)},(1,2)R,3)R，1,(22,(1,3)R1R2(3,2)R1,(2,1)R2,(3,1)R1R2

(5)如果R1，R2传递，则R1R2也传递。

否,例:A{1,2,3,4},R1{(1,1),(2,3)},R2{(1,2),(3,3)},(1,1)R1,(1,2)R2,(1,2)R1R2，(2,3)R1,(3,3)R2,(2,3)R1R2,但(1,3)R1R2

10.设A={a,b,c}，以下分别给出一个P(A)上的二元 关系，确定它们哪些是自反的，反自反的，对称的，反对称的，传递的。

P(A)={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}（１）ｘ是ｙ的一个真子集

R1{(x,y)|xy,x,yP(A)}

反自反，不对称，反对称，传递（２）ｘ与ｙ不相交

R2{(x,y)|xy,x,yP(A)}

不自反，也不反自反()，对称，不传递（３）xyA

R3{(x,y)|xyA,x,yP(A)}

不自反，也不反自反{a,b,c}{a,b,c}A，对称，不传递。

11.设R是A上二元关系，证明R是传递的当且仅当

R2R。

任(a,b)∈R2,C,(a,c)(c,b)∈R ,由R传递(a,b)∈R , 即R2  R;若(a,b)∈R,(b,c)∈R , 即(a,c)∈R2 R , 所以R传递。

12.R是A上反对称的二元关系，问t(R)总是反对称 的吗？

010111否, 例： R001,t(R)111

100111

13．设R是A上的一个自反关系，证明当且仅当(a,b)和(a,c)属于R推出(b,c)属于R时，R是一个等价 关系。

若(a,b)∈R，又自反(a,a)∈R, 推出(b,a)∈R, 所以对称；

若(a,b)(b,c)∈R , 由对称(b,a)(b,c)∈R , 推出(a,c)∈R ,所以传递。若R等价,(a,b)(a,c)∈R , 由对称性(b,a)(a,c)∈R , 由传递性 ,(b,c)∈R。

14.设R是A上的一个对称和传递的关系，证明如果对A中的每个a，在A中存在b，使得(a,b)∈R，则R是一个等价关系。 aA,bA,(a,b)R,由对称性,(b,a)R,又由传递性,(a,a)R.15.设R是A上的一个传递和自反的关系，设T是 A上的一个二元关系，使得当且仅当(a,b)和(b,a)同时 属于R时，(a,b)∈T，证明T是一个等价关系。 a(a,a)∈R,(a,a)∈R =>(a,a)∈T 若(a,a)∈T,(a,b)(b,a)∈R , 即(b,a)(a,b)∈R

=>(b,a)∈T 若(a,b)(b,c)∈T,(a,b)(b,a)(b,c)(c,b)∈R

=>(a,c)∈R,(c,a)∈R

=>(a,c)∈T

16.设R是A上一个二元关系，设

S={(a,b)｜对某个C，(a,c)∈R且(c,b)∈R｝

证明如果R是等价关系，则Ｓ也是等价关系。

a,(a,a)∈R,(a,a)∈R

=>(a,a)∈S 若(a,b)∈S , 存在c,(a,c)(c,b)∈R 由R对称,(b,c)(c,a)∈R , 所以(b,a)∈S 若(a,b)(b,c)∈S

存在d,e

(a,d)(d,b)(b,e)(e,c)∈R

由R传递(a,b)(b,c)∈R 所以(a,c)∈S

17.设R是A上的二元关系，对所有的xi,xj,xk∈A，如果xiRxj∧xjRxkxkRxi，则称R为循环关系，试证明当且仅当R是等价关系时，R才是自反的和循环的。（其中aRb表示(a,b)∈Ｒ）。

R等价, 当然自反，如果xiRxj且xjRxk则由传递性，xiRxk, 由对称性xkRxi，R是自反, 循环的；

若(a,b)∈R, 由R自反 a,(a,a)∈R, 又(a,b)∈R, 由循环(b,a)∈R，对称，若(a,b)(b,c)∈R，由循环(c,a)∈R, 由对称(a,c)∈R，传递。

18．设R1，R2是A上二元关系，证明(1)r(R1R2)r(R1)r(R2)(2)s(R1R2)s(R1)s(R2)(3)t(R1R2)t(R1)t(R2)(1)r(R1R2)(R1R2)IAR1IAR2R1(IAIA)R2(R1IA)(IAR2)(R1IA)(R2IA)r(R1)r(R2)(2)s(Rc1R2)(R1R2)(R1R2)Rcc1R2R1R2

(Rcc1R1)(R2R2)s(R1)s(R2)(3)(R1R2)2{(a,b)|c,(a,c)R1orR2,(c,b)R1orR2}R221R2R1R2R2R1 29 R2221R2(R1R2)用归纳法可证RnRnn12(R1R2)

n,可得t(R1)t(R2)t(R1R2)

19.设A={a,b,c,d},A上二元关系

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

（１）用矩阵算法和作图法求r(R),s(R),t(R)。（２）用Warshall算法求t(R)。

110001001111 r(R)=1110101011110011 s(R)= 0101 t(R)=0001000100100000

010010011101010i10110i211100001100010001

0000j20000j1,20000i3111111111111110i311111i41111j20001000100010000j20000j1,2,30000

20.讨论正实数集上二元关系Ｒ的几何意义。（１）Ｒ是自反的（２）Ｒ是对称的（３）Ｒ是传递的

（提示：以第一象限的点讨论）

(1)第一象限角平分线

(2)关于对角平分线对称的点对集合

(3)若有P1(x1,y1)、P2(x2,y2), 若x2=y1，必有第三个点P3(x1,y2)

第四篇：离散数学期末复习试题及答案(一)

离散数学习题参考答案

第一章 集合

１．分别用穷举法，描述法写出下列集合（１）偶数集合

（２）36的正因子集合（３）自然数中3的倍数（４）大于１的正奇数

(1)E={，-6，-4，-2，0，2，4，6，}

={2 i | i I }

(2)D= { 1, 2, 3, 4, 6, } = {x>o | x|36 }

(3)N3= { 3, 6, 9, ```} = { 3n | nN }

(4)Ad= {3, 5, 7, 9, ```} = { 2n+1 | nN }

２．确定下列结论正确与否（１）φφ

×（２）φ｛φ｝√（３）φφ√（４）φ｛φ｝√（５）φ｛ａ｝×（６）φ｛ａ｝√

（７）｛ａ，ｂ｝｛ａ，ｂ，ｃ，｛ａ，ｂ，ｃ｝｝×（８）｛ａ，ｂ｝｛ａ，ｂ，ｃ，｛ａ，ｂ，ｃ｝｝√（９）｛ａ，ｂ｝｛ａ，ｂ，｛｛ａ，ｂ｝｝｝×（１０）｛ａ，ｂ｝｛ａ，ｂ，｛｛ａ，ｂ｝｝｝√

３．写出下列集合的幂集（１）｛｛ａ｝｝

{φ, {{ a }}}

(2)φ

{φ}（３）｛φ，｛φ｝｝

{φ, {φ}, {{φ}}, {φ,{φ}} }（４）｛φ，ａ，｛ａ，ｂ｝｝

{φ, {a}, {{a,b }}, {φ}, {φ, a }, {φ, {a,b }}，{a, {a b }}, {φ,a,{ a, b }} }（５）Ｐ（Ｐ（φ））

{φ, {φ}, {{φ}}, {φ,{φ}} }

４．对任意集合Ａ，Ｂ，Ｃ，确定下列结论的正确与否（１）若ＡＢ，且ＢＣ，则ＡＣ√（２）若ＡＢ，且ＢＣ，则ＡＣ×（３）若ＡＢ，且ＢＣ，则ＡＣ×（４）若ＡＢ，且ＢＣ，则ＡＣ ×

５．对任意集合Ａ，Ｂ，Ｃ，证明

(1)A(BC)(AB)(AC)左差A(BC)差A(BC)D.MA(BC)

分配(AB)(AC)右(2)A(BC)(AB)(AC)1)左差A(BC)(1)的结论(AB)(AC)差(AB)(AC)右

2)左差A(BC)D.MA(BC)分配(AB)(AC)差(AB)(AC)右(3)A(BC)(AB)(AC)左差A(BC)D.MA(BC)幂等(AA)(BC)

结合,交换(AB)(AC)右(4)(AB)BAB 左差(AB)B对称差((AB)B)((AB)B)

分配,结合((AB)(BB))(A(B)B))

互补((AB)U)(A)

零一

(AB)(AB)右(5)(AB)CA(BC)左差(AB)C结合A(BC)

D.MA(BC)差A(BC)(6)(AB)C(AC)B左差(AB)C结合A(BC)交换A(CB)结合(AC)B

差(AC)B右(7)(AB)C(AC)(BC)右(5)A(C(BC))差A(C(BC))分配A((CB)(CC))互补A((CB)U)

零一A(CB)交换A(BC)(5)(AB)C左

６．问在什么条件下，集合Ａ，Ｂ，Ｃ满足下列等式

(1)A(BC)(AB)C左(AB)(AC)右若要右左,须CA(BC)，CA时等式成立

(2)ABA左右是显然的,AABAB,AB，AB时等式成立

(3)ABBABB,BB,B,代入原式得A，AB时等式成立

(4)ABBAABBA,只能AB,AB, BA,BA,AB时等式成立

(5)ABAB,若B,bB，当bA,bABA矛盾;当bA,bABA矛盾

(6)ABAB右左是显然的,ABAB,AAB,ABBAB,BAABAB时等式成立

(7)(AB)(AC)A左(AB)(AC)A(BC)A(BC)A(BC)A

ABC时等式成立

(8)(AB)(AC)左(AB)(AC)A(BC)A(BC)A(BC)

A(BC),AB,AC时等式成立

(9)(AB)(AC)左(AB)(AC)A(BC)A(BC)A(BC)

A(BC)时等式成立

(10)(AB)(AC)((AB)(AC))((AB)(AC))(AB)(AC)(AB)(AC)

由(6)知,(AB)(AC),ABAC,ABAC时等式成立

(11)A(BA)BA(BA)(AB)(AA)(AB)U(AB)B

AB时等式成立

７．设Ａ＝｛ａ，ｂ，｛ａ，ｂ｝，｝，求下列各式（１）φ∩｛φ｝=φ（２）｛φ｝∩｛φ｝={φ} （３）｛φ，｛φ｝｝－φ={φ,{φ}}（４）｛φ，｛φ｝｝－｛φ｝= {{φ}}（５）｛φ，｛φ｝｝－｛｛φ｝｝={φ}（６）Ａ－｛ａ，ｂ｝={{a,b}, φ}（７）Ａ－φ = A（８）Ａ－｛φ｝={a,b,{a,b}}（９）φ－Ａ=φ（１０）｛φ｝－Ａ=φ

８．在下列条件下，一定有Ｂ＝Ｃ吗？（１）ABAC

否，例：A={1，2，3}，B={4}，C={3,4}, ABAC{1,2,3,4},而BC。

（２）ABAC

否，例：A={1，2，3}，B={2，3}，C={2，3，4} ABAC{2,3},而BC。

（３）ABAC

对,若BC,不妨,aB,aC,若aA,aAB,aAB,aAB,aAC,aAC,aAC;若aA,aAB,aAB,aAB,aAC,aAC,aAC矛盾（４）ABAC且ABAC

bB,若bA,bABAC,bC,若bA,bABAC,bC，BC,同理,CB,BC

9.(1)(AB)(BC)AB

证:a左,a(BC),aB,aB;a(AB),而aB,aA,aAB

(2)若A(BC)且B(AC),则B。

若B,aB(AC)(AC),aA(BC),aC,aB即aB,矛盾

10．化简

((ABC)(AB))((A(BC))A)(AB)A(AB)A

(AA)(BA)(BA)BA11.设A={2，3，4}，B={1，2}，C={4，5，6}，求（１）AB{1, 3, 4} （２）ABC{1,3,5,6}（３）(AB)(BC){2,3,5,6}

12.设A={1，2，3，4}，B={1，2，5}，求

(1)P(A)P(B){φ,{1},{2},{1,2}}

(2)P(A)P(B)

{φ,{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}, {1,2,3,},{1,2,4,},{1,3,4,},{2,3,4},{1,2,3,4,},{5},{1,5}, {2,5},{1,2} }

(3)P(A)P(B)

{ {3},{4},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4}，{2,3,4},{1,2,3,4} }

(4)P(A)P(B)

{{3},{4},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4}, {2,3,4},{1,2,3,4},{5},{1,5},{2,5},{1,2,5} }

第五篇：离散数学习题及答案

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

一、（10分）某项工作需要派A、B、C和D 4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？

(1)若A去，则C和D中要去1个人；

(2)B和C不能都去；

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

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

(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

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

二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。

解：论域：所有人的集合。S(x)：x是专家；W(x)：x是工人；Y(x)：x是青年人；则推理化形式为：

x(S(x)∧W(x))，xY(x)x(S(x)∧Y(x))

下面给出证明：

(1)xY(x)P

(2)Y(c)T(1)，ES

(3)x(S(x)∧W(x))P

(4)S(c)∧W(c)T(3)，US

(5)S(c)T(4)，I

(6)S(c)∧Y(c)T(2)(5)，I

(7)x(S(x)∧Y(x))T(6)，EG

三、（10分）设A、B和C是三个集合，则AB(BA)。

证明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA)

x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB)

(x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A))

(BA)。

四、（15分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。

解r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>}

s(R)＝R∪R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>} R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}

R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>}

R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R

t(R)＝Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，i14232－

15>}。

五、（10分）R是非空集合A上的二元关系，若R是对称的，则r(R)和t(R)是对称的。

证明对任意的x、y∈A，若xr(R)y，则由r(R)＝R∪IA得，xRy或xIAy。因R与IA对称，所以有yRx或yIAx，于是yr(R)x。所以r(R)是对称的。

下证对任意正整数n，R对称。

因R对称，则有xRyz(xRz∧zRy)z(zRx∧yRz)yRx，所以R对称。若Rn对称，则xRn1yz(xRnz∧zRy)z(zRnx∧yRz)yRn1x，所以Rn1对称。因此，对任意正整数n，Rn对称。对任意的x、y∈A，若xt(R)y，则存在m使得xRy，于是有yRx，即有yt(R)x。因此，t(R)是对称的。

六、（10分）若f：A→B是双射，则f：B→A是双射。

证明因为f：A→B是双射，则f是B到A的函数。下证f是双射。

对任意x∈A，必存在y∈B使f(x)＝y，从而f(y)＝x，所以f是满射。

对任意的y1、y2∈B，若f(y1)＝f(y2)＝x，则f(x)＝y1，f(x)＝y2。因为f：A→B是函数，则y1＝y2。所以f是单射。

综上可得，f：B→A是双射。

七、（10分）设是一个半群，如果S是有限集，则必存在a∈S，使得a*a＝a。

证明因为是一个半群，对任意的b∈S，由*的封闭性可知，b＝b*b∈S，b＝b*b∈S，…，bn∈S，…。

因为S是有限集，所以必存在j＞i，使得bi＝bj。令p＝j－i，则bj＝bp*bj。所以对q≥i，有bq＝bp*bq。

因为p≥1，所以总可找到k≥1，使得kp≥i。对于bkp∈S，有bkp＝bp*bkp＝bp*(bp*bkp)＝…＝232－1－1－1－1－1－1－1－1－1mm222nbkp*bkp。

令a＝bkp，则a∈S且a*a＝a。

八、（20分）（1）若G是连通的平面图，且G的每个面的次数至少为l(l≥3)，则G的边数m与结点数n有如下关系：

m≤

rl(n－2)。l2l证明设G有r个面，则2m＝

2)。d(f)≥lr。由欧拉公式得，n－m＋r＝2。于是，m≤l2(n－ii

1（2）设平面图G＝是自对偶图，则| E|＝2(|V|－1)。

证明设G＝是连通平面图G＝的对偶图，则G G，于是|F|＝|V*|＝|V|，将其代入欧拉公式|V|－|E|＋|F|＝2得，|E|＝2(|V|－1)。**

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

一、（10分）证明(P∨Q)∧(PR)∧(QS)S∨R

证明因为S∨RRS，所以，即要证(P∨Q)∧(PR)∧(QS)RS。

(1)R附加前提

(2)PRP

(3)PT(1)(2)，I

(4)P∨QP

(5)QT(3)(4)，I

(6)QSP

(7)ST(5)(6)，I

(8)RSCP

(9)S∨RT(8)，E

二、（15分）根据推理理论证明：每个考生或者勤奋或者聪明，所有勤奋的人都将有所作为，但并非所有考生都将有所作为，所以，一定有些考生是聪明的。

设P(e)：e是考生，Q(e)：e将有所作为，A(e)：e是勤奋的，B(e)：e是聪明的，个体域：人的集合，则命题可符号化为：x(P(x)(A(x)∨B(x)))，x(A(x)Q(x))，x(P(x)Q(x))x(P(x)∧B(x))。

(1)x(P(x)Q(x))P

(2)x(P(x)∨Q(x))T(1)，E

(3)x(P(x)∧Q(x))T(2)，E

(4)P(a)∧Q(a)T(3)，ES

(5)P(a)T(4)，I

(6)Q(a)T(4)，I

(7)x(P(x)(A(x)∨B(x))P

(8)P(a)(A(a)∨B(a))T(7)，US

(9)A(a)∨B(a)T(8)(5)，I

(10)x(A(x)Q(x))P

(11)A(a)Q(a)T(10)，US

(12)A(a)T(11)(6)，I

(13)B(a)T(12)(9)，I

(14)P(a)∧B(a)T(5)(13)，I

(15)x(P(x)∧B(x))T(14)，EG

三、（10分）某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。

解设A、B、C分别表示会打排球、网球和篮球的学生集合。则：

|A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。

因为|(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩

B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，|ABC|＝25－20＝5。故，不会打这三种球的共5人。

四、（10分）设A1、A2和A3是全集U的子集，则形如Ai(Ai为Ai或Ai)的集合称为由A1、A2和

i1

3A3产生的小项。试证由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。

证明小项共8个，设有r个非空小项s1、s2、…、sr(r≤8)。

对任意的a∈U，则a∈Ai或a∈Ai，两者必有一个成立，取Ai为包含元素a的Ai或Ai，则a∈Ai，i13即有a∈si，于是Usi。又显然有siU，所以U＝si。

i1i1i1i1rrrr

任取两个非空小项sp和sq，若sp≠sq，则必存在某个Ai和Ai分别出现在sp和sq中，于是sp∩sq＝。综上可知，{s1，s2，…，sr}是U的一个划分。

五、（15分）设R是A上的二元关系，则：R是传递的R*RR。

证明(5)若R是传递的，则∈R*Rz(xRz∧zSy)xRc∧cSy，由R是传递的得xRy，即有∈R，所以R*RR。

反之，若R*RR，则对任意的x、y、z∈A，如果xRz且zRy，则∈R*R，于是有∈R，即有xRy，所以R是传递的。

六、（15分）若G为连通平面图，则n－m＋r＝2，其中，n、m、r分别为G的结点数、边数和面数。证明对G的边数m作归纳法。

当m＝0时，由于G是连通图，所以G为平凡图，此时n＝1，r＝1，结论自然成立。

假设对边数小于m的连通平面图结论成立。下面考虑连通平面图G的边数为m的情况。

设e是G的一条边，从G中删去e后得到的图记为G，并设其结点数、边数和面数分别为n、m和r。对e分为下列情况来讨论：

若e为割边，则G有两个连通分支G1和G2。Gi的结点数、边数和面数分别为ni、mi和ri。显然n1＋n2＝n＝n，m1＋m2＝m＝m－1，r1＋r2＝r＋1＝r＋1。由归纳假设有n1－m1＋r1＝2，n2－m2＋r2＝2，从而(n1＋n2)－(m1＋m2)＋(r1＋r2)＝4，n－(m－1)＋(r＋1)＝4，即n－m＋r＝2。

若e不为割边，则n＝n，m＝m－1，r＝r－1，由归纳假设有n－m＋r＝2，从而n－(m－1)＋r－1＝2，即n－m＋r＝2。

由数学归纳法知，结论成立。

七、（10分）设函数g：A→B，f：B→C，则：

(1)fg是A到C的函数；

(2)对任意的x∈A，有fg(x)＝f(g(x))。

证明(1)对任意的x∈A，因为g：A→B是函数，则存在y∈B使∈g。对于y∈B，因f：B→C是函数，则存在z∈C使∈f。根据复合关系的定义，由∈g和∈f得∈g*f，即∈fg。所以Dfg＝A。

对任意的x∈A，若存在y1、y2∈C，使得、∈fg＝g*f，则存在t1使得∈g且∈f，存在t2使得∈g且∈f。因为g：A→B是函数，则t1＝t2。又因f：B→C是函数，则y1＝y2。所以A中的每个元素对应C中惟一的元素。

综上可知，fg是A到C的函数。

(2)对任意的x∈A，由g：A→B是函数，有∈g且g(x)∈B，又由f：B→C是函数，得∈f，于是∈g*f＝fg。又因fg是A到C的函数，则可写为fg(x)＝f(g(x))。

八、（15分）设是的子群，定义R＝{|a、b∈G且a1*b∈H}，则R是G中的－

一个等价关系，且[a]R＝aH。

证明对于任意a∈G，必有a1∈G使得a1*a＝e∈H，所以∈R。－－

若∈R，则a1*b∈H。因为H是G的子群，故(a1*b)1＝b1*a∈H。所以∈R。－－－－

若∈R，∈R，则a1*b∈H，b1*c∈H。因为H是G的子群，所以(a1*b)*(b1*c)＝a－－－－

－1*c∈H，故∈R。

综上可得，R是G中的一个等价关系。

对于任意的b∈[a]R，有∈R，a1*b∈H，则存在h∈H使得a1*b＝h，b＝a*h，于是b∈aH，－－

[a]RaH。对任意的b∈aH，存在h∈H使得b＝a*h，a1*b＝h∈H，∈R，故aH[a]R。所以，[a]R－

＝aH。