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

第一篇：全国2008年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={<1,1>,<2,2>,<3,3>}

B.R={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>}）

C.R={<1,1>,<2,2>,<3,3>,<1,2>}

D.R={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>} 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={<1,2>，<3,4>,<2,2>}，则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={<1,2>,<3,4>,<2,2>}, S={<4,2>,<2,5>,<3,1>,<1,3>}，则。

三、计算题（本大题共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 < 2, xR},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ ,.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 < 0, xR};{x | 1 < x < 2, xR};{x | 0≤x≤1, x12.12;6.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是整数，<30}，Ｂ={x|x是质数，x<20}，C={1,3,5}，则① =_____;② =_____;③ =_____;④ =_____。(1){1,2,3,5}(2)(3){0}(4){1,3,5,7,11,13,17,19}(5){1,3,5,7}(6){7,11,13,17,19} 5．设A、B、C是集合，下列四个命题中，_____在任何情况下都是正确的。(1)若A B且B∈C，则A∈C(2)若A B且B∈C，则A C(3)若A∈B且B C，则A C(4)若A∈B且B C，则A∈C 6．设集合Ａ={a,b,c,d,e,f,g}，Ａ的一个划分 ={{a,b},{c,d,e},{f,g}}，则 所对应的等价关系有_____个二元组。

(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

11(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＝{<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－1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>}

R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>}

R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2

t(R)＝ Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，5>}。

五、（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是对称和传递的，当且仅当 < a, b> 和在R中有<.b , c>在R中。（8分）

2、f和g都是群到< G2, *>的同态映射，证明是的一个子群。其中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={ ,< b , a > ,< b, c > , < c , d >}用矩阵运算求出R的传递闭包t(R)。（9分）

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

试卷一答案：

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

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

2、；

3、1；

4、； 5、1；

6、{<1,1>, <1,3>, <2,2>, <2,4> }；

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、证，有，又

★ ★

★ < C , ★> 是 < G1 , ★>的子群。

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)={ , , < a , c> , , , < b ,b > , < b , c.> , < b , d > , < c , d > }

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

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

第二篇：全国2006年4月高等教育自学考试离散数学试题

全国2006年4月高等教育自学考试

离散数学试题

课程代码：02324

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

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

1．下列命题公式为重言式的是（）A．p→(p∨q)C．q∧┐q 2．下列语句中不是命题的只有（）．．A．这个语句是假的。C．飞碟来自地球外的星球。

B．1+1=1.0

D．凡石头都可练成金。B．(p∨┐p)→q D．p→┐q 3．设p：我很累，q：我去学习，命题：“除非我很累，否则我就去学习”的符号化正确的是

（）

A．┐p∧q C．┐p→┐q 4．下列等价式正确的是（）A．┐(x)A(x)┐A B．(x)(y)A(x)(y)A C．┐(x)A(x)┐A

D．(x)(A(x)B(x))(x)A(x)(x)B(x)

5．在公式(x)(y)(P(x,y)Q(z))(y)P(y,z)中变元y是（）A．自由变元 B．约束变元

C．既是自由变元，又是约束变元 D．既不是自由变元，又不是约束变元

6．设A={1，2，3}，A上二元关系S={<1，1>，<1，2>，<3，2>，<3，3>}，则S是（）A．自反关系 C．对称关系

B．反自反关系 D．传递关系 B．┐p→q D．p→┐q 7．设集合X为人的全体，在X上定义关系R、S为R={|a，b∈X∧a是b的母亲}，那么关系{|a，b∈x∧ a是b的祖母}的表达式为（）A．RS C．SR

B．R-1S D．RS-1

8．设A是正整数集，R={(x，y)|x，y∈A∧x+3y=12}，则R∩({2，3，4，6}×{2，3，4，6})=（）A． O /

B．{<3，3>} C．{<3，3>，<6，2>} D．{<3，3>，<6，2>，<9，1>} 9．下列式子不正确的是（）A．(A-B)-C=(A-C)-B C．(A-B)-C=(A-C)-(B-C)10．下列命题正确的是（）A．{l，2}{{1，2}，{l，2，3}，1} B．{1，2}{1，{l，2}，{l，2，3}，2} C．{1，2}{{1}，{2}，{1，2}} D．{1，2}∈{1，2，{2}，{l，2，3}} 11．在下列代数系统中，不是环的只有（）

A．，其中R为实数集，+为实数加法，a*b=a+2b。

D．，其中Mn(R)为实数集n×n阶矩阵结合，+，*是矩阵加法和乘法。12．下列整数集对于整除关系都构成偏序集，而能构成格的是（）A．{l，2，3，4，5} C．{2，3，7}

B．{1，2，3，6，12} D．{l，2，3，7}

B．(A-B)-C=A-(B∪C)D．A-(B∪C)=(A-B)∪ C

13．结点数为奇数且所有结点的度数也为奇数的连通图必定是（）A．欧拉图 C．非平面图

B．汉密尔顿图 D．不存在的

14．无向图G是欧拉图当且仅当G是连通的且（）A．G中各顶点的度数均相等 B．G中各顶点的度数之和为偶数 C．G中各顶点的度数均为偶数 D．G中各顶点的度数均为奇数

15．平面图(如下)的三个面的次数分别是（）

A．11，3，4 C．12，3，6

B．11，3，5 D．10，4，3

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

16．求一个公式的主析取或主合取范式的方法，有______________法和______________法。

17．给定谓词合式公式A，其中一部分公式形式为(x)B(x)或(x)B(x)，则量词，后面所跟的x称为______________，而称B为相应量词的______________。

18．设X，U，V，Y都是实数集，f1：X→U，且fl(x)→ex； f2：U→V，且f2(u)＝u(1+u)；f3：V→Y，且f3(v)=cosv。那么f3f2f1的定义域是______________，而复合函数(f3f2f1)(x)= ______________。

19．集合X={a，b，c，d}上二元关系R={，，，，，}，则R的自反闭包r(R)= ______________，对称闭包s(R)= ______________。

20．已知G=<{l，-1，i，-i}，·>(其中i=1，是数的乘法)是群，则-l的阶是______________；i的阶是______________。21．对代数系统，其中*是S上的二元运算，若a，b∈S，且对任意的x∈S，都有a*x=x*a=x，b*x=x*b=b，则称a为运算“*”的______________，称b为运算“*”的______________。

22．设是群，则满足结合律和______________；若｜S｜>l，S中不可能有______________。23．写出如右有向图的一条初级回路：______________，其长度是______________。24．一个______________且______________的无向图称为树。25．在简单无向图G=中，如果V中的每个结点都与其称为______________，如果V有n个结点，那么它还是

三、计算题(本大题共5小题，第26、27题各5分，第28、29题各6分，第30题8分，共30分)26．若集合A={a，{b，c}}的幂集为P(A)，集合B={ O /

，{ O / }}的幂集为P(B)，求P(A)∩P(B)。

27．构造命题公式(p→(q∧ r))→┐p的真值表。

28．求图G＝的可达矩阵，其中V＝｛v1,v2,v3,v4｝ E＝｛(v1,v2),(v2,v3),(v2,v4),(v3,v2),(v3,v4),(v3,v1),(v4,v1)｝

余的所有结点邻接，则该图______________度正则图。

29．求下列公式的主析取范式和主合取范式：（P∧Q）∨（┐P∧R）

30．设A＝｛2，3，4，6，8，12，24｝，R为A上整除关系，试画的哈斯图，并求A中的最大元，最小元，极大元，极小元。

四、证明题（本大题共3小题，第31、32小题各6分，第33题8分，共20分）31．设M是偶数集，＋和·是数的加、乘运算，证明是一个环。32．设R是集合X上的二元关系，证明R是X上传递关系当且仅当RRR。

33．设G是简单平面图，G有n个顶点m条边，且m<30，证明G中存在一项点v，d（v）≤4。

五、应用题（本大题共2小题，第34题6分，第35题9分，共15分）34．判断下面推理是否正确，并证明你的结论。如果小王今天家里有事，则他不会来开会。如果小张今天看到小王，则小王今天来开会了。小张今天看到小王。所以小王今天家里没事。

35．有6个村庄Vi，i=l，2，…，6欲修建道路使村村可通。现已有修建方案如下带权无向图所示，其中边表示道路，边上的数字表示修建该道路所需费用，问应选择修建哪些道路可使得任二个村庄之间是可通的且总的修建费用最低?要求写出求解过程，画出符合要求的最低费用的道路网络图并计算其费用。

第三篇：离散数学试题

中央电大离散数学试题

月

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

1．若集合A={1，{2}，{1，2}}，则下列表述正确的是()．

A．2AB．{1}A

C．1AD．2  A

2．已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为

()．

A．6B．4C．3D．

53．设无向图G的邻接矩阵为

0111110011100001100111010

则G的边数为()．

A．1B．7C．6D．14 4．设集合A={a}，则A的幂集为()．

A．{{a}}B．{a，{a}}

C．{，{a}}D．{，a}

5．下列公式中()为永真式．

A．AB  ABB．AB  (AB)

C．AB  ABD．AB  (AB)

二、填空题（每小题3分，本题共15分）

6．命题公式PP的真值是

7．若无向树T有5个结点，则T的边数为．

8．设正则m叉树的树叶数为t，分支数为i，则(m-1)i

9．设集合A={1，2}上的关系R＝{<1, 1>,<1, 2>}，则在R中仅需加一个元素，就可使新得到的关系为对称的．

10．(x)(A(x)→B(x，z)∨C(y))中的自由变元有．

三、逻辑公式翻译（每小题6分，本题共12分）

11．将语句“今天上课．”翻译成命题公式．

12．将语句“他去操场锻炼，仅当他有时间．”翻译成命题公式．

四、判断说明题（每小题7分，本题共14分）

判断下列各题正误，并说明理由．

13．设集合A={1，2}，B={3，4}，从A到B的关系为f={<1, 3>}，则f是A到B的函数．

14．设G是一个有4个结点10条边的连通图，则G为平面图．

五．计算题（每小题12分，本题共36分）

15．试求出（P∨Q）→（R∨Q）的析取范式．

16．设A={{1}, 1, 2}，B={ 1, {2}}，试计算

（1）（A∩B）（2）（A∪B）（3）A （A∩B）．

17．图G=，其中V={ a, b, c, d }，E={(a, b),(a, c),(a, d),(b, c),(b, d),(c, d)}，对应边的权值依次为1、2、3、1、4及5，试

（1）画出G的图形；

（2）写出G的邻接矩阵；

（3）求出G权最小的生成树及其权值．

六、证明题（本题共8分）

18．试证明：若R与S是集合A上的自反关系，则R∩S也是集合A上的自反关系．

中央电大2010年7月离散数学

试题解答

(供参考)

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

1．B2．D3．B4．C5．B

二、填空题（每小题3分，本题共15分）

6．假（或F，或0）

7．48．t-

19． <2, 1>

10．z，y

三、逻辑公式翻译（每小题6分，本题共12分）

11．设P：今天上课，（2分）则命题公式为：P．（6分）

12．设 P：他去操场锻炼，Q：他有时间，（2分）则命题公式为：P Q．（6分）

四、判断说明题（每小题7分，本题共14分）

13．错误．（3分）因为A中元素2没有B中元素与之对应，故f不是A到B的函数．（7分）

14．错误．（3分）不满足“设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．”（7分）

五．计算题（每小题12分，本题共36分）

15．（P∨Q）→（R∨Q） ┐(P∨Q)∨（R∨Q）（4分）

(┐P∧┐Q)∨（R∨Q）（8分）

(┐P∧┐Q)∨R∨Q（析取范式）（12分）

16．（1）（A∩B）={1}（4分）

（2）（A∪B）={1, 2, {1}, {2}}（8分）

（3）A（A∩B）={{1}, 1, 2}（12分）

17．（1）G的图形表示如图一所示：ad1

5b c（3分）图一

（2）邻接矩阵：

01101111（6分）1101

1110

（3）最小的生成树如图二中的粗线所示：

a 3d5

b图二1c

权为：1+1+3=5

六、证明题（本题共8分）

18．证明：设xA，因为R自反，所以x R x，即< x, x>R；

又因为S自反，所以x R x，即< x, x >S．即< x, x>R∩S故R∩S自反．

10分）12分）（4分）（6分）（8分）（（

第四篇：2010年7月自考离散数学试题及答案

全国2010年7月自学考试离散数学试题

课程代码：02324

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

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

1．下列句子不是命题的是（D）．．A．中华人民共和国的首都是北京 C．雪是黑色的

B．张三是学生 D．太好了！

2．下列式子不是谓词合式公式的是（B）．．A．（x）P(x)→R(y)B．(x)┐P（x）(x)(P(x)→Q(x))C．(x)(y)(P(x)∧Q(y))→(x)R(x)D．(x)(P(x,y)→Q(x,z))∨(z)R(x,z)3．下列式子为重言式的是（）A．(┐P∧R)→Q C．P∨(P∧Q)

B．P∨Q∧R→┐R D．(┐P∨Q)(P→Q)4．在指定的解释下，下列公式为真的是（）A．(x)(P(x)∨Q(x)),P(x):x=1,Q(x):x=2,论域:{1,2} B．(x)(P(x)∧Q(x)),P(x):x=1,Q(x):x=2,论域: {1,2} C．(x)(P(x)→Q(x)),P(x):x>2,Q(x):x=0,论域:{3,4} D．(x)(P(x)→Q(x)),P(x):x>2,Q(x):x=0,论域:{3,4} 5．对于公式(x)(y)(P(x)∧Q(y))→(x)R(x,y)，下列说法正确的是（）A．y是自由变元 C．(x)的辖域是R(x, y)

B．y是约束变元

D．(x)的辖域是(y)(P(x)∧Q(y))→(x)R(x,y)6．设论域为{1,2}，与公式(x)A(x)等价的是（）A．A(1)∨A(2)C．A(1)∧A(2)

B．A(1)→A(2)D．A(2)→A(1)7．设Z+是正整数集，R是实数集，f:Z+→R, f(n)=log2n ,则f（）A．仅是入射 C．是双射

B．仅是满射 D．不是函数

8．下列关系矩阵所对应的关系具有反对称性的是（）

1A．0101011 01B．0101001 1

全国2010年7月自学考试离散数学试题

0C．0100011 01D．0101010 09．设R1和R2是集合A上的相容关系，下列关于复合关系R1R2的说法正确的是（）A．一定是等价关系 C．一定不是相容关系

10．下列运算不满足交换律的是（）．．．A．a*b=a+2b C．a*b=|a-b|

B．a*b=min(a,b)D．a*b=2ab B．一定是相容关系

D．可能是也可能不是相容关系

11．设A是偶数集合，下列说法正确的是（）A．是群 C．是群

B．是群

D．, ,都不是群

12．设*是集合A上的二元运算，下列说法正确的是（）A．在A中有关于运算*的左幺元一定有右幺元 B．在A中有关于运算*的左右幺元一定有幺元 C．在A中有关于运算*的左右幺元，它们不一定相同 D．在A中有关于运算*的幺元不一定有左右幺元 13．题13图的最大出度是（）A．0 C．2 14．下列图是欧拉图的是（）

B．1 D．3

15．一棵树的3个4度点，4个2度点，其它的都是1度，那么这棵树的边数是（）A．13 C．15

B．14 D．16

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

16．请写出表示德摩根律的两个命题公式等价定理___________，___________。

17．n个命题变元的___________称为小项，其中每个变元与它的否定不能同时出现，但两者必须___________。18．前提引入规则：在证明的任何步骤上都可以___________，简称___________规则。

19．自由变元代入规则是指对某___________出现的个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入，且___________。20．设A=,B={2,4}，则((A)=___________，A×B___________。

21．设A={1,2,3,4}, A上的二元关系R={<1,2>,<2,4>,<3,3>},S={<1,3>,<2,4>,<4,2>}，则R2S=___________，全国2010年7月自学考试离散数学试题

(R)=___________。

22．设代数系统是环，则是___________，是___________。

23．在中，元素2的阶为___________，它生成的子群为___________，其中7为模7乘法。24．设是一个___________，如果A中任意两个元素都有___________，则称为格。25．若一条___________中，所有的___________均不相同，称为迹。

三、计算题（本大题共6小题，每小题5分，共30分）

26．给定论域D={1,2}，f(1)=2, f(2)=1, S(1)=F, S(2)=T, G(1,2)=T, G(2,1)=T,在该赋值下，求式子x(S(f(x))∧G(x, f(x)))的真值。

27．请通过等值演算法求┐(P∧Q)→(P∨Q)的主析取范式。

28．设A={1,2,3,4}，给定A上二元关系R={<1,1>,<1,2>,<2,4>,<4,2>}，求R的传递闭包。29．对题29图所示格，找出它的所有的4元子格。

30．用矩阵的方法求题30图中结点ui，u5之间长度为2的路径的数目。

31．求题31图的最小生成树。

四、证明题（本大题共3小题，第32小题8分，第33、34小题各6分，共20分）32．用推理方法证明(A∨B)→(C∧D),(D∨F)→E├A→E。

33．证明：设是一个群，则对于任意a,b∈G，必存在惟一的x∈G使得a·x=b。34．设图G有n个结点，n+1条边，证明：G中至少有一个结点度数≥3。

五、应用题（本大题共2小题，第35小题9分，第36小题6分，共15分）

35．符合化下列命题，并构造推理证明：三角函数都是周期函数，有些三角函数是连续函数，所以有些周期函数是连续函数。

36．两个等价关系的并集不一定是等价关系，试举例说明。-12

全国2010年7月自学考试离散数学试题

2010年7月全国自考离散数学试题参考答案

全国2010年7月自学考试离散数学试题

全国2010年7月自学考试离散数学试题

全国2010年7月自学考试离散数学试题

全国2010年7月自学考试离散数学试题

第五篇：2010年7月自考离散数学试题及答案

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

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

1．下列句子不是命题的是（D）．．A．中华人民共和国的首都是北京 C．雪是黑色的

B．张三是学生 D．太好了！

2．下列式子不是谓词合式公式的是（B）．．A．（x）P(x)→R(y)B．(x)┐P（x）(x)(P(x)→Q(x))C．(x)(y)(P(x)∧Q(y))→(x)R(x)D．(x)(P(x,y)→Q(x,z))∨(z)R(x,z)3．下列式子为重言式的是（）A．(┐P∧R)→Q C．P∨(P∧Q)

B．P∨Q∧R→┐R D．(┐P∨Q)(P→Q)4．在指定的解释下，下列公式为真的是（）A．(x)(P(x)∨Q(x)),P(x):x=1,Q(x):x=2,论域:{1,2} B．(x)(P(x)∧Q(x)),P(x):x=1,Q(x):x=2,论域: {1,2} C．(x)(P(x)→Q(x)),P(x):x>2,Q(x):x=0,论域:{3,4} D．(x)(P(x)→Q(x)),P(x):x>2,Q(x):x=0,论域:{3,4} 5．对于公式(x)(y)(P(x)∧Q(y))→(x)R(x,y)，下列说法正确的是（）A．y是自由变元 C．(x)的辖域是R(x, y)

B．y是约束变元

D．(x)的辖域是(y)(P(x)∧Q(y))→(x)R(x,y)6．设论域为{1,2}，与公式(x)A(x)等价的是（）A．A(1)∨A(2)C．A(1)∧A(2)

B．A(1)→A(2)D．A(2)→A(1)7．设Z+是正整数集，R是实数集，f:Z+→R, f(n)=log2n ,则f（）A．仅是入射 C．是双射

B．仅是满射 D．不是函数

8．下列关系矩阵所对应的关系具有反对称性的是（）101A．011

100001C．001

100100B．011

101101D．010

1009．设R1和R2是集合A上的相容关系，下列关于复合关系R1R2的说法正确的是（）A．一定是等价关系

B．一定是相容关系

全国2010年7月自学考试离散数学试题

C．一定不是相容关系

10．下列运算不满足交换律的是（）．．．A．a*b=a+2b C．a*b=|a-b|

D．可能是也可能不是相容关系

B．a*b=min(a,b)D．a*b=2ab

11．设A是偶数集合，下列说法正确的是（）A．是群 C．是群

B．是群

D．, ,都不是群

12．设*是集合A上的二元运算，下列说法正确的是（）A．在A中有关于运算*的左幺元一定有右幺元 B．在A中有关于运算*的左右幺元一定有幺元 C．在A中有关于运算*的左右幺元，它们不一定相同 D．在A中有关于运算*的幺元不一定有左右幺元 13．题13图的最大出度是（）A．0 C．2 14．下列图是欧拉图的是（）

B．1 D．3

15．一棵树的3个4度点，4个2度点，其它的都是1度，那么这棵树的边数是（）A．13 C．15

B．14 D．16

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

16．请写出表示德摩根律的两个命题公式等价定理___________，___________。

17．n个命题变元的___________称为小项，其中每个变元与它的否定不能同时出现，但两者必须___________。18．前提引入规则：在证明的任何步骤上都可以___________，简称___________规则。

19．自由变元代入规则是指对某___________出现的个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入，且___________。

20．设A=,B={2,4}，则((A)=___________，A×B___________。

21．设A={1,2,3,4}, A上的二元关系R={<1,2>,<2,4>,<3,3>},S={<1,3>,<2,4>,<4,2>}，则R2S=___________，(R-1)2=___________。

22．设代数系统是环，则是___________，是___________。

23．在中，元素2的阶为___________，它生成的子群为___________，其中7为模7乘法。24．设是一个___________，如果A中任意两个元素都有___________，则称为格。25．若一条___________中，所有的___________均不相同，称为迹。

全国2010年7月自学考试离散数学试题

三、计算题（本大题共6小题，每小题5分，共30分）

26．给定论域D={1,2}，f(1)=2, f(2)=1, S(1)=F, S(2)=T, G(1,2)=T, G(2,1)=T,在该赋值下，求式子x(S(f(x))∧G(x, f(x)))的真值。

27．请通过等值演算法求┐(P∧Q)→(P∨Q)的主析取范式。

28．设A={1,2,3,4}，给定A上二元关系R={<1,1>,<1,2>,<2,4>,<4,2>}，求R的传递闭包。29．对题29图所示格，找出它的所有的4元子格。

30．用矩阵的方法求题30图中结点ui，u5之间长度为2的路径的数目。

31．求题31图的最小生成树。

四、证明题（本大题共3小题，第32小题8分，第33、34小题各6分，共20分）32．用推理方法证明(A∨B)→(C∧D),(D∨F)→E├A→E。

33．证明：设是一个群，则对于任意a,b∈G，必存在惟一的x∈G使得a·x=b。34．设图G有n个结点，n+1条边，证明：G中至少有一个结点度数≥3。

五、应用题（本大题共2小题，第35小题9分，第36小题6分，共15分）

35．符合化下列命题，并构造推理证明：三角函数都是周期函数，有些三角函数是连续函数，所以有些周期函数是连续函数。

36．两个等价关系的并集不一定是等价关系，试举例说明。

全国2010年7月自学考试离散数学试题

全国2010年7月自学考试离散数学试题

全国2010年7月自学考试离散数学试题

全国2010年7月自学考试离散数学试题

全国2010年7月自学考试离散数学试题