全国4月自考离散数学试题_自考离散数学历年试题

全国4月自考离散数学试题由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“自考离散数学历年试题”。

全国2008年4月自考离散数学试题

课程代码：02324

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

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

1.设P：天下大雨,Q：他在室内运动,命题“除非天下大雨，否则他不在室内运动”可符合化为（）

A.P∧QB.P→Q C.P→QD.P→Q

2.下列命题联结词集合中，是最小联结词组的是（）

A.{，}B.{，∨，∧} C.{，∧}D.{∧，→}

3.下列命题为假命题的是（）

A.如果2是偶数，那么一个公式的析取范式惟一

B.如果2是偶数，那么一个公式的析取范式不惟一

C.如果2是奇数，那么一个公式的析取范式惟一

D.如果2是奇数，那么一个公式的析取范式不惟一

4.谓词公式 x(P(x)∨yR(y))→Q(x))中变元x是（）

A.自由变元B.约束变元

C.既不是自由变元也不是约束变元D.既是自由变元也是约束变元

5.若个体域为整数减，下列公式中值为真的是（）

A.xy(x+y=0)B.y x(x+y=0)C.x y(x+y=0)D.xy(x+y=0)

6.下列命题中不正确的是（）

A.x∈{x}-{{x}}B.{x}{x}-{{x}}

C.A={x}∪x,则x∈A且xAD.A-B=A=B

7.设P={x|(x+1)2≤4}，Q={x|x2+16≥5x},则下列选项正确的是（A.PQB.PQ C.QPD.Q=P

8.下列表达式中不成立的是（）

A.A∪(BC)=(A∪B)(A∪C)B.A∩(BC)=(A∩B)(A∩C)C.(AB)×C=(A×C)(B×C)D.(A-B)×C=(A×C)-(B×C)9.半群、群及独异点的关系是（）

A.{群}{独异点}{半群}B.{独异点}{半群}{群} C.{独异点}{群}{半群}D.{半群}{群}{独异点} 10.下列集合对所给的二元运算封闭的是（）

A.正整数集上的减法运算

B.在正实数的集R+上规定为ab=ab-a-b a,b∈R+ C.正整数集Z+上的二元运算为xy=min(x,y)x,y∈Z+ D.全体n×n实可逆矩阵集合Rn×n上的矩阵加法

11.设集合A={1，2，3}，下列关系R中不是等价关系的是（）A.R={，}

B.R={，，}）

C.R={，,}

D.R={，，，，} 12.下列函数中为双射的是（）

A.f：Z→Z,f(j)=j(mod)B.f：N→N,f(j)= C.f：Z→N,f(j)=|2j|+1D.f：R→R,f(r)=2r-15

13.设集合A={a,b, c}上的关系如下，具有传递性的是（）

A.R={，,}B.R={,} C.R={，,}D.R={}

14.含有5个结点，3条边的不同构的简单图有（）

A.2个B.3个

C.4个D.5个

15.设D的结点数大于1，D=是强连通图，当且仅当（）

A.D中至少有一条通路B.D中至少有一条回路

C.D中有通过每个结点至少一次的通路D.D中有通过每个结点至少一次的回路

二、填空题(本大题共10小题，每小题2分，共20分)请在每小题的空格中填上正确答案。错填、不填均无分。

16.设A={1,2,3}，B={3,4,5}，则AA=___________，AB=___________。

17.设A={1,2,3,4,5}，RA×A，R={，,}，则R的自反闭包r(R)=__________。

对称闭包t(R)=__________。

18.设P、Q为两个命题，德摩根律可表示为_____________，吸收律可表示为____________。

19.对于公式 x(P(x)∨Q(x))，其中P(x)∶x=1,Q(x)∶x=2,当论域为{1,2}时，其真值为_____________ ,当论域为{0,1,2}时，其真值为_____________。

20.设f∶R→R,f(x)=x+3,g∶R→R,g(x)=2x+1,则复合函数 ,。

21.3个结点可构成_________个不同构的简单无向图，可构成________个不同构的简单有向图。

22.无向图G=如左所示，则G的最大度

Δ(G)=_____________，G的最小度δ(G)=_____________。

23.设图G,V={v1,v2,v3,v4},若G的邻接矩阵，则deg-(v1)=_ ________, deg+(v4)=____________。

24.格L是分配格，当且仅当L既不含有与_______同构的子格，也不含有与______同格的子格。

25.给定集合A={1,2,3,4,5}，在集合A上定义两种关系：R={，}, S={，,}，则。

三、计算题（本大题共5小题，第26、27题各5分，第28、29题各6分，第30题8分，共30分）

26.设A={a,b,c,d}，A上的等价关系R={，,}∪IA，画出R的关系图，并求出A中各元素的等价类。

27.构造命题公式（P∨Q）（P∧Q）的真值表。

28.求下列公式的主析取范式和主合取范式：P→（（Q→P）∧（P∧Q））

29.设A={a, b, c, d, e}，R为A上的关系，R={，, , ， }∪IA，试画的哈斯图，并求A中的最大元，最小元，极大元，极小元。

30.给定图G如图所示，（1）G中长度为4的路有几条？其中有几条回路？（2）写出G的可达矩阵。

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

31.设（L，≤）是格，试证明： a, b, c ∈L, 有a∧（b∨c）≥（a∧b）∨（a∧c）；

a∨（b∧c）≤（a∨b）∧（a∨c）。

32.设R是A上的自反和传递关系，如下定义A上的关系T，使得 x, y∈A，∈T ∈R∧(y, x)∈R。

证明T是A上的等价关系。

33.设有G=, V的结点数|V|=n，称该图为n阶图，若从结点vi到vj存在路，证明从vi到vj必存在长度小于等于n-1的一条路。

五、应用题（本大题共2小题，第34题7分，第35题8分，共15分）

34.构造下面推理的证明。

每个喜欢步行的人都不喜欢坐汽车，每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车，因而有的人不喜欢步行。

35.今要将6人分成3组（每组2个人）去完成3项任务。已知每个人至少与其余5个人中的3个人能相互合作。

（1）能否使得每组的2个人都能相互合作？

（2）你能给出几种不同的分组方案？

《离散数学》试题及答案3

一、填空题设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A(B)＝ __________________________.2.设有限集合A, |A| = n, 则 |(A×A)| = __________________________.3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________.4.已知命题公式G＝(PQ)∧R，则G的主析取范式是_______________________________

__________________________________________________________.5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________.6 设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从AB＝_________________________;AB＝_________________________;A－B＝ _____________________.7.设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________, ________________________, _______________________________.8.设命题公式G＝(P(QR))，则使公式G为真的解释有__________________________，_____________________________, __________________________.9.设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则R1•R2 = ________________________,R2•R1 =____________________________,R12 =________________________.10.设有限集A, B，|A| = m, |B| = n, 则| |(AB)| = _____________________________.11 设A,B,R是三个集合，其中R是实数集，A = {x |-1≤x≤1, xR}, B = {x | 0≤x

13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________.14.设一阶逻辑公式G = xP(x)xQ(x)，则G的前束范式是__________________________ _____.15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。

16.设谓词的定义域为{a, b},将表达式xR(x)→xS(x)中量词消除，写成与之对应的命题公式是__________________________________________________________________________.17.设集合A＝{1, 2, 3, 4}，A上的二元关系R＝{(1,1),(1,2),(2,3)}, S＝{(1,3),(2,3),(3,2)}。则RS＝_____________________________________________________, R2＝______________________________________________________.二、选择题 设集合A={2,{a},3,4}，B = {{a},3,4,1}，E为全集，则下列命题正确的是()。

(A){2}A(B){a}A(C){{a}}BE(D){{a},1,3,4}B.设集合A={1,2,3},A上的关系R＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，则R不具备().(A)自反性(B)传递性(C)对称性(D)反对称性 设半序集(A,≤)关系≤的哈斯图如下所示，若A的子集B = {2,3,4,5},则元素6为B的()。

(A)下界(B)上界(C)最小上界(D)以上答案都不对下列语句中，()是命题。

(A)请把门关上(B)地球外的星球上也有人

(C)x + 5 > 6(D)下午有会吗？ 设I是如下一个解释：D＝{a,b}, 则在解释I下取真值为1的公式是().(A)xyP(x,y)(B)xyP(x,y)(C)xP(x,x)(D)xyP(x,y).6.若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是().(A)(1,2,2,3,4,5)(B)(1,2,3,4,5,5)(C)(1,1,1,2,3)(D)(2,3,3,4,5,6).7.设G、H是一阶逻辑公式，P是一个谓词，G＝xP(x), H＝xP(x),则一阶逻辑公式GH是().(A)恒真的(B)恒假的(C)可满足的(D)前束范式.设命题公式G＝(PQ)，H＝P(QP)，则G与H的关系是()。

(A)GH(B)HG(C)G＝H(D)以上都不是.9 设A, B为集合，当()时A－B＝B.(A)A＝B(B)AB(C)BA(D)A＝B＝.设集合A = {1,2,3,4}, A上的关系R＝{(1,1),(2,3),(2,4),(3,4)}, 则R具有()。

(A)自反性(B)传递性(C)对称性(D)以上答案都不对下列关于集合的表示中正确的为()。

(A){a}{a,b,c}(B){a}{a,b,c}(C){a,b,c}(D){a,b}{a,b,c} 12 命题xG(x)取真值1的充分必要条件是().(A)对任意x，G(x)都取真值1.(B)有一个x0，使G(x0)取真值1.(C)有某些x，使G(x0)取真值1.(D)以上答案都不对.13.设G是连通平面图，有5个顶点，6个面，则G的边数是().(A)9条(B)5条(C)6条(D)11条.14.设G是5个顶点的完全图，则从G中删去()条边可以得到树.(A)6(B)5(C)10(D)4.15.设图G的相邻矩阵为，则G的顶点数与边数分别为().(A)4, 5(B)5, 6(C)4, 10(D)5, 8.三、计算证明题

1.设集合A＝{1, 2, 3, 4, 6, 8, 9, 12}，R为整除关系。

(1)画出半序集(A,R)的哈斯图；

(2)写出A的子集B = {3,6,9,12}的上界，下界，最小上界，最大下界；

(3)写出A的最大元，最小元，极大元，极小元。

2.设集合A＝{1, 2, 3, 4}，A上的关系R＝{(x,y)| x, yA 且 x  y}, 求

(1)画出R的关系图；

(2)写出R的关系矩阵.3.设R是实数集合，,,是R上的三个映射，(x)= x+3, (x)= 2x, (x)＝ x/4,试求复合映射•，•, •, •，••.4.设I是如下一个解释：D = {2, 3}, abf(2)f(3)P(2, 2)P(2, 3)P(3, 2)P(3, 3)32320011

试求(1)P(a, f(a))∧P(b, f(b));(2)xy P(y, x).5.设集合A＝{1, 2, 4, 6, 8, 12}，R为A上整除关系。

(1)画出半序集(A,R)的哈斯图；

(2)写出A的最大元，最小元，极大元，极小元；

(3)写出A的子集B = {4, 6, 8, 12}的上界，下界，最小上界，最大下界.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, R－1, S－1•R－1.四、证明题

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.{3};{{3},{1,3},{2,3},{1,2,3}}.2..3.1= {(a,1),(b,1)}, 2= {(a,2),(b,2)},3= {(a,1),(b,2)}, 4= {(a,2),(b,1)};3, 4.4.(P∧Q∧R).5.12, 3.6.{4}, {1, 2, 3, 4}, {1, 2}.7.自反性；对称性；传递性.8.(1, 0, 0),(1, 0, 1),(1, 1, 0).9.{(1,3),(2,2),(3,1)};{(2,4),(3,3),(4,2)};{(2,2),(3,3)}.10.2mn.11.{x |-1≤x

13.{(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)}.14.x(P(x)∨Q(x)).15.21.16.(R(a)∧R(b))→(S(a)∨S(b)).17.{(1, 3),(2, 2)};{(1, 1),(1, 2),(1, 3)}.二、选择题

1.C.2.D.3.B.4.B.5.D.6.C.7.C.8.A.9.D.10.B.11.B.13.A.14.A.15.D

三、计算证明题

1.(1)

(2)B无上界，也无最小上界。下界1, 3;最大下界是3.(3)A无最大元，最小元是1，极大元8, 12, 90+;极小元是1.2.R = {(1,1),(2,1),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4)}.(1)

(2)

3.(1)•＝((x))＝(x)+3＝2x+3＝2x+3.(2)•＝((x))＝(x)+3＝(x+3)+3＝x+6,(3)•＝((x))＝(x)+3＝x/4+3,(4)•＝((x))＝(x)/4＝2x/4 = x/2，(5)••＝•(•)＝•+3＝2x/4+3＝x/2+3.4.(1)P(a, f(a))∧P(b, f(b))= P(3, f(3))∧P(2, f(2))= P(3, 2)∧P(2, 3)= 1∧0 = 0.(2)xy P(y, x)= x(P(2, x)∨P(3, x))

R}.6 =(P(2, 2)∨P(3, 2))∧(P(2, 3)∨P(3, 3))=(0∨1)∧(0∨1)= 1∧1 = 1.5.(1)

(2)无最大元，最小元1，极大元8, 12;极小元是1.(3)B无上界，无最小上界。下界1, 2;最大下界2.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)= 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)= xyz((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∪R－1＝{(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)关系图:

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.13.(1)

P∧Q∧R)7

(2)R•S＝{(a, b),(c, d)}，R∪S＝{(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d)}, R－1＝{(a, a),(c, a),(c, b),(d, c)}, S－1•R－1＝{(b, a),(d, c)}.四 证明题

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

(2)R→PQ(1)(3)P→QP

(4)R→QQ(2)(3)(5)Q→RQ(4)(6)R→SP

(7)Q→SQ(5)(6)(8)Q∨SQ(7)

2.证明：(A-B)-C =(A∩~B)∩~C = A∩(~B∩~C)= A∩~(B∪C)= A-(B∪C)

3.证明：{A∨B, C→B, C→D}蕴涵A→D(1)AD(附加)(2)A∨BP(3)BQ(1)(2)(4)C→BP(5)B→CQ(4)(6)CQ(3)(5)(7)C→DP(8)DQ(6)(7)(9)A→DD(1)(8)

所以 {A∨B, C→B, C→D}蕴涵A→D.4.证明：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.8

1.离散数学试题及答案2 离散数学试题

一.多重选择填空题

(本题包括16个空格，每个空格3分，共48分。每道小题都可能有一个以上的正确选项，须选出所有的正确选项，不答不得分，多选、少选或选错都将按比例扣分。)1．命题公式(P∧(P→Q))→Q是_____式。

(1)重言(2)矛盾(3)可满足(4)非永真的可满足 2．给定解释I=(D,)=(整数集，{f(x,y):f(x,y)=x-y；g(x,y):g(x,y)=x+y；P(x,y):x

(1)100(2)99(3)2048(4)1024(5)512 4．集合Ａ={x|x是整数，

(1)14(2)15(3)16(4)17(5)8(6)49(7)512 7．S={1,2,3,4,5,6,7,8,9,10,11,12}，≤是S上的整除关系。S的子集Ｂ＝{2,4,6｝，则在(S，≤)中，Ｂ的最大元是_____；Ｂ的最小元是_____；Ｂ的上确界是_____；Ｂ的下确界是_____。

(1)不存在的(2)36(3)24(4)12(5)6(6)1(7)2 8．设有有限布尔代数(B,+,*,’,0,1)，则 =_____能成立。(1)1(2)2(3)3(4)4(5)5(6)8(7)9 9．G={0,1,2,„,n}，n∈N，定义 为模n加法，即x y=(x+y)mod n，则代数系统(G，)_____。

(1)是半群但不是群(2)是无限群(3)是循环群(4)是变换群(5)是交换群

10．n个结点、m条边的无向连通图是树当且仅当m=_____。(1)n+1(2)n(3)n-1(4)2n-1 二请给出命题公式 的主析取范式。(10分)三假设下列陈述都是正确的：(1)学生会的每个成员都是学生并且是班干部；

(2)有些成员是女生。问是否有成员是女班干部？请将上述陈述和你的结论符号化，并给出你的结论的形式证明。(10分)四设R和S是集合Ｘ上的等价关系,则S∩R必是等价关系。(10分)

参考答案

一、1.1、3 2.4 3.4 4.1；4；2；2 5.4 6.4 7.1；7；4；7 8.2、4、6 9.3、4 10.3

二、分析：求给定命题公式的主析取范式与主合取范式，通常有两种方法——列表法和等值演算法。(1)列表法

列出给定公式的真值表，其真值为真的赋值所对应的极小项的析取，即为此公式的主析取范式。(2)等值演算法 在等值演算中，首先将公式中的蕴涵联结词和等价联结词化去，使整个公式化归为析取范式，然后删去其中所有的永假合取项，再将析取式中重复出现的合取项合并和合并合取项中相同的命题变元，最后对合取项添加没有出现的命题变元，就是合取 ,经过化简整理，即可得到主析取范式。解：（1）列表法 设

000011111 001010100 010010100 011110100 100001000 101000010 110000010 111100111 根据真值表中 真值为1的赋值所对应的极小项的析取，即为 的主析取范式。由表可知

（2）等值演算

三、解：有成员是女班干部。

将命题符号化，个体域为全总个体域。

：x是学生会的成员。：x是学生 ：x是班干部 ：x是女性 前提：，结论： 证明： ① P ② ES①，e为额外变元 ③ P ④ T③ ⑤ T② ⑥ T② ⑦ T④⑤⑥ ⑧ T② ⑨ T⑤⑦⑧ ⑩ EG⑨

离散数学试题及答案1

离散数学考试试题（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分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。

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

(()∧())，()(()∧())下面给出证明：

(1)()P

(2)(c)T(1)，ES(3)(()∧())P

(4)(c)∧(c)T(3)，US(5)(c)T(4)，I

(6)(c)∧(c)T(2)(5)，I(7)(()∧())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＝{，，，}，求r(R)、s(R)和t(R)。

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

s(R)＝R∪R－1＝{，，，，}

R2＝{，，，} R3＝{，，，}

R4＝{，，，}＝R2

t(R)＝ Ri＝{，，，，，}。

五、（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，Rn对称。

因R对称，则有xR2yz(xRz∧zRy)z(zRx∧yRz)yR2x，所以R2对称。若 对称，则x yz(x z∧zRy)z(z x∧yRz)y x，所以 对称。因此，对任意正整数n，对称。

对任意的x、y∈A，若xt(R)y，则存在m使得xRmy，于是有yRmx，即有yt(R)x。因此，t(R)是对称的。

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

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

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

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

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

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

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

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

因为p≥1，所以总可找到k≥1，使得kp≥i。对于 ∈S，有 ＝ * ＝ *(*)＝„＝ *。

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

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

m≤(n－2)。

证明 设G有r个面，则2m＝ ≥lr。由欧拉公式得，n－m＋r＝2。于是，m≤(n－2)。

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

证明 设G*＝是连通平面图G＝的对偶图，则G* G，于是|F|＝|V*| 12 ＝|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R P

(3)P T(1)(2)，I(4)P∨Q P

(5)Q T(3)(4)，I(6)QS P(7)S T(5)(6)，I(8)RS CP(9)S∨R T(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，＝25－20＝5。故，不会 13 打这三种球的共5人。

四、（10分）设A1、A2和A3是全集U的子集，则形如 Ai(Ai为Ai或)的集合称为由A1、A2和A3产生的小项。试证由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。

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

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

任取两个非空小项sp和sq，若sp≠sq，则必存在某个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)fog是A到C的函数；

(2)对任意的x∈A，有fog(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，即∈fog。所以Dfog＝A。

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

综上可知，fog是A到C的函数。

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

八、（15分）设是的子群，定义R＝{|a、b∈G且a－1*b∈H}，则R是G中的一个等价关系，且[a]R＝aH。证明 对于任意a∈G，必有a－1∈G使得a－1*a＝e∈H，所以∈R。

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

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

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

对于任意的b∈[a]R，有∈R，a－1*b∈H，则存在h∈H使得a－1*b＝h，b＝a*h，于是b∈aH，[a]RaH。对任意的b∈aH，存在h∈H使得b＝a*h，a－1*b＝h∈H，∈R，故aH[a]R。所以，[a]R＝aH。

发到哪？给个邮箱啊~~~~~~~

一、填空 20%（每小题2分）

1．设（N：自然数集，E¬¬¬+ 正偶数）则。

2．A，B，C表示三个集合，文图中阴影部分的集合表达式为。

3．设P，Q 的真值为0，R，S的真值为1，则的真值=。

4．公式 的主合取范式为。

5．若解释I的论域D仅包含一个元素，则 在I下真值为。

6．设A={1，2，3，4}，A上关系图为

则 R2 =。

7．设A={a，b，c，d}，其上偏序关系R的哈斯图为

则 R=。

8．图 的补图为。

9．设A={a，b，c，d}，A上二元运算如下：

* a b c d a b c d a b c d b c d a c d a b d a b c

那么代数系统的幺元是，有逆元的元素为，它们的逆元分别为。

10．下图所示的偏序集中，是格的为。

二、选择 20%（每小题 2分）

1、下列是真命题的有（）

A． ； B． ；

C． ； D．。

2、下列集合中相等的有（）

A．{4，3} ；B．{，3，4}；C．{4，3，3}；D． {3，4}。

3、设A={1，2，3}，则A上的二元关系有（）个。

A． 23 ； B． 32 ； C． ； D．。

4、设R，S是集合A上的关系，则下列说法正确的是（）

A．若R，S 是自反的，则 是自反的；

B．若R，S 是反自反的，则 是反自反的；

C．若R，S 是对称的，则 是对称的；

D．若R，S 是传递的，则 是传递的。

5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下

则P（A）/ R=（）

A．A ；B．P(A)；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；

D．{{ }，{2}，{2，3}，{{2，3，4}}，{A}}

6、设A={，{1}，{1，3}，{1，2，3}}则A上包含关系“ ”的哈斯图为（）

7、下列函数是双射的为（）

A．f : I E , f(x)= 2x ； B．f : N N N, f(n)= ；

C．f : R I , f(x)= [x] ； D．f :I N, f(x)= | x |。

（注：I—整数集，E—偶数集，N—自然数集，R—实数集）

8、图 中 从v1到v3长度为3 的通路有（）条。

A． 0； B． 1； C． 2； D． 3。

9、下图中既不是Eular图，也不是Hamilton图的图是（）

10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（）个4度结点。

A．1； B．2； C．3； D．4。

三、证明 26%

1、R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当 和在R中有在R中。（8分）

2、f和g都是群到的同态映射，证明是的一个子群。其中C=(8分)

3、G=(|V| = v，|E|=e)是每一个面至少由k（k 3）条边围成的连通平面图，则，由此证明彼得森图（Peterson）图是非平面图。（11分）

四、逻辑推演 16%

用CP规则证明下题（每小题 8分）

1、2、五、计算 18%

1、设集合A={a，b，c，d}上的关系R={ , , , }用矩阵运算求出R的传递闭包t(R)。（9分）

2、如下图所示的赋权图表示某七个城市 及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。（9分）

试卷一答案：

一、填空 20%（每小题2分）

1、{0，1，2，3，4，6}；

2、；

3、1；

4、；

5、1；

6、{, , , }；

7、{，，} IA ；

8、9、a ；a , b , c ,d ；a , d , c , d ；

10、c;

二、选择 20%（每小题 2分）

题目 1 2 3 4 5 6 7 8 9 10

答案 C D B、C C A D C A D B A

三、证明 26%

1、证：

“ ” 若 由R对称性知，由R传递性得

“ ” 若，有 任意，因 若 所以R是对称的。

若，则 即R是传递的。

2、证，有，又

★ ★

★ 是 的子群。

3、证：

①设G有r个面，则，即。而 故 即得。（8分）

②彼得森图为，这样 不成立，所以彼得森图非平面图。（3分）

二、逻辑推演 16%

1、证明：

① P（附加前提）

② T①I ③ P

④ T②③I ⑤ T④I ⑥ T⑤I ⑦ P

⑧ T⑥⑦I ⑨ CP

2、证明

① P（附加前提）

② US①

③ P ④ US③

⑤ T②④I ⑥ UG⑤

⑦ CP

三、计算 18%

1、解：，t(R)={ , , , , , , , , }

2、解： 用库斯克（Kruskal）算法求产生的最优树。算法略。结果如图：

树权C(T)=23+1+4+9+3+17=57即为总造价。