离散数学

课程代码：02324

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

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

三、填空题(本大题共10小题，每小题2分，共20分)

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

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

四、证明题（本大题共3小题，每小题7分，共21分）

五、综合应用题（本大题共2小题，每小题7分，共14分）

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

课程代码：02324

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

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

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

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

全国2010年7月高等教育自学考试离散数学试题 课程代码：02324

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

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

1．下列句子不是命题的是（ ） A．中华人民共和国的首都是北京 B．张三是学生 C．雪是黑色的 D．太好了！

2．下列式子不是谓词合式公式的是（ ） 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 B．P∨Q∧R→┐R C．P∨(P∧Q) 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是自由变元 B．y是约束变元 C．($x)的辖域是R(x, y)

D．(\"x)的辖域是($y)(P(x)∧Q(y))→($x)R(x,y)

6．设论域为{1,2}，与公式(\"x)A(x)等价的是（ ） A．A(1)∨A(2) B．A(1)→A(2) C．A(1)∧A(2) D．A(2)→A(1)

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

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

9．设R1和R2是集合A上的相容关系，下列关于复合关系R1°R2的说法正确的是（ ） A．一定是等价关系 B．一定是相容关系 C．一定不是相容关系

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

10．下列运算不满足交换律的是（ ） A．a*b=a+2b B．a*b=min(a,b) C．a*b=|a-b| D．a*b=2ab

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

D．, ,都不是群

12．设*是集合A上的二元运算，下列说法正确的是（ ） A．在A中有关于运算*的左幺元一定有右幺元 B．在A中有关于运算*的左右幺元一定有幺元 C．在A中有关于运算*的左右幺元，它们不一定相同 D．在A中有关于运算*的幺元不一定有左右幺元

15．一棵树的3个4度点，4个2度点，其它的都是1度，那么这棵树的边数是（ ） A．13 B．14 C．15 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．若一条___________中，所有的___________均不相同，称为迹。 三、计算题（本大题共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)))的真值。

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年4月自学考试离散数学试题

课程代码：02324

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

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均不得分。 1.下列句子为命题的是( ) A.全体起立! C.我在说谎

2.下列式子不是谓词合式公式的是( ) ．．A.(x)(P(x,y)Q(x,z))(z)R(x,z) B. (x)(y)P(x,y)Q(x,z)(x)P(x,y) C. (x)P(x)Q(x))(x)(P(x)Q(x)) D. (x)P(x)Q(y,z)

3.下列式子为矛盾式的是( ) A.PP C.PP

B.P(PQ)

D.(PQ) PQ B.x=0

D.张三生于1886年的春天

4.设给定赋值N如下：个体域为自然数集；特定元素a=0；特定函数f(x,y)=x+y,g(x,y)=xy；特定谓词F(x,y)为x=y。在赋值N下，下列公式为真的是( ) A. (x)F(g(x,a),x)

B. (x)(y)(F(f(x,a),y)F(f(y,a),x)) C. (x)(y)(z)F(f(x,y),z) D. (x)(y)F(f(x,y),g(x,y))

5.对于公式(x)(P(x,y)Q(x,z))(z)R(x,z)，下列说法正确的是( ) A.y是自由变元 B.x是约束变元

C. (x)的辖域是(P(x,y)Q(x,z))(z)R(x,z) D. (x)的辖域是P(x,y)

6.设论域为{l，2}，与公式(x)A(x)等价的是( ) A.A(1)A(2) C.A(1)

B. A(1)A(2) D. A(2)A(1)

7.设Z+是正整数集合，f:Z+→Z+，f(n)=2n-2,则f( ) A.仅是入射 C.是双射

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

8.下列关系矩阵所对应的关系具有反自反性的是( ) 101A.011 100001001C. 

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

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

1009.设R1和R2是集合A上的相容关系，下列关于R1R2的说法正确的是( ) A.一定是相容关系

C.可能是也可能不是相容关系

B.一定不是相容关系 D.一定是等价关系

10.设A是奇数集合，下列构成独异点的是( ) A. C.

B. D.

11.设A是整数集，下列说法正确的是( ) A.有零元 C.有幺元

12.下列说法不正确的是( ) ．．．A.在实数集上，乘法对加法是可分配的 B.在实数集上，加法对乘法是可分配的 C.在某集合的幂集上，∪对∩是可分配的 D.在某集合的幂集上，∩对∪是可分配的 13.右图的最大入度是( ) A.0 B.1 C.2 D.3

14.下列可一笔画成的图形是( )

B.有零元 D.有幺元

15.一棵树有5个3度结点，2个2度结点，其它的都是l度结点，那么这棵树的结点数是 ( ) A.13

B.14

C.16 D.17

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

请在每小题的空格中填上正确答案。错填、不填均不得分。 16.请写出表示分配律的两个命题公式等价定理________,________。

17.n个命题变元的________称为大项，其中每个变元与它的否定不能同时出现，但两者必须________。

18.在谓词推理过程中，由(x)P(x)得到P(a)，其中a为论域的某个个体，用的是________规则，记为________规则。

19.请用联结词，表示联结词和联结词：________，________。 20.设A={1，2，3，4}，B={2，4，6}，则A-B=________，AB=________。 21.给出A={l，2}上的一个等价关系________，并给出其对应的划分________。

22.设A={l，2，3，4}，A上的二元关系R={<1，2>，<2，3>，<3，2>}，S={，<2，3>，<4，3>}，则R∩S=________，(R—S)-1=________。

23.代数系统是域，则________和________都是交换群。

24.若图中存在________，它经过图中所有的________，则称该图为汉密尔顿图。 25.n点完全图记为Kn，那么当________时，Kn是平面图，当_____时，Kn是非平面图。 三、计算题(本大题共6小题，每小题5分，共30分) 26.列出(QP) ((PR)Q)的真值表。

27.用等值演算求P(Q R)的主析取范式。

28.设A={1,2,3,4}，给定A上的二元关系R={<1,2>,<2,1>,<2,3>,<3,4>}，求R的传递闭包。

29.求右图所示格的所有5元和6元子格。

30.求的所有生成元及所有2阶、3阶子群，其中为模7乘法。

31.用矩阵的方法求右图中结点v1，v3之间长度为2的路径的数目。

四、证明题(本大题共3小题，第32小题8分，第33、34小题各6分，共20分) 32.用推理方法证明：PQ,QR,R,(PS) S。

33.设H是G的非空子集，则是群的子群当且仅当对任意a,bH有a·b-1H。

34．证明整数集Z上的大于等于关系“”是一个偏序关系。

五、综合应用题(本大题共2小题，第35小题6分，第36小题9分，共15分) 35．将下面命题符号化，并构造推理证明：

所有有理数是实数，有些有理数是整数，所以有些实数是整数。

36．某城市拟在六个区之间架设有线电话网，其网点间的距离如下列有权矩阵给出，请绘出有权图，给出架设线路的最优方案，并计算线路的总长度。

010290104080403029083007700510 60051060

全国2009年7月自考离散数学试题 课程代码：02324

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

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下列句子为命题的是( ) A.走，看电影去

C.空集是任意集合的真子集

B.x+y>0 D.你明天能来吗?

2.下列式子不是谓词合式公式的是( ) ．．A.(x)(P(x)→(x)(Q(x) ∧A(x，y))) C.(x)P(x)→R(y)

3.下列式子为重言式的是( ) A.P→P∨Q C.﹁ (P Q)

B.(﹁P∧Q)∧(P∨﹁Q) D.(P∨Q) (P→Q) B.(x)∧(y)∨P(x，y) D.(x)P(x)∧Q(y，z)

4.设个体域为实数集，特定元素a=0，函数f(x，y)=x-y，特定谓词F(x，y)为xC.(x)(y)(z)(F(x，y)→F(f(x，z)，f(y，z))) D.(x)F(f(a，x)，a)

5.对于公式(x)(y)P(x，y)∨Q(x，z)∧(x)P(x，y)，下列说法正确的是( ) A.x是自由变元

C.( x)的辖域是P(x，y)∨Q(x，z)

B.x是约束变元 D.(x)的辖域是P(x，y)

6.设论域为{1，2}，与公式(x)﹁A(X)等价的是( ) A. ﹁A(1) ∨﹁A(2) C. ﹁A(1) ∧﹁A(2)

B. ﹁A(1)→﹁(A2) D. A(1) →A(2)

7.设Z+是正整数集，f：Z+×Z+→Z+，f(n，m)=nm，则f( ) A.仅是入射 C.是双射

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

8.下列哪个关系矩阵所对应的关系具有自反性( )

101100A.111

B.011100

101001101C.001 D. 1000101009.设R1和R2是集合A上的相容关系，下列关系哪个可能不是．．相容关系( ) A.R1R2 B.RlR2 C.R1-1

D.RlR2

10.在整数集上，下面哪个运算不是．．二元运算( ) A.加法 B.减法 C.乘法

D.除法

11.设A是奇数集合，×为乘法运算，则是( ) A.半群 B.群 C.循环群

D.交换群

12.下面不满足．．．结合律的运算是( ) A.a*b=min(a，b) B.a*b=max(a，b) C.a*b=2(a+b)

D.a*b=2ab 13.右图的最小入度是( ) A.0 B.1 C.2 D.3

14.下面既是汉密尔顿图又是欧拉图的图形是( )

15.一棵树有3个5度点、1个4度点、3个2度点，其它的都是1度，那么它的边数是( A.17

B.18

) C.19 D.20

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

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

16.设命题变元为P，Q，R，则小项m100=________，大项M010=________。

17.置换规则：在证明的任何步骤上，命题公式中的任何子命题公式都可以________，记为________规则。

18.一个公式，如果量词均在全式的________，其作用域延伸到整个公式的________，则该公式称为前束范式。

19.请用联结词﹁，∧表示联结词∨和联结词 ：________，________。

20.设A={l，2，3，4}，A上的二元关系R={<1，2>，<3，4>，<4，3>}，S={，<3，4>，<4，1>}，则R～S=________，(RS)-1=________。

21.代数系统是整环，则是________，是________，且无零因子。 22.在实数集R上定义运算ab=a+b+ab，则幺元为________，元素2的逆元为________。 23.若回路中，除________外________各不相同，则此回路称为圈(或初级回路)。 24.偶图记为Kn,m那么当________时，Kn,m是平面图，当________时，Kn,m是非平面图。 25.若图中存在________，它经过图中所有的边恰好________次，则称该图为欧拉图。 三、计算题(本大题共6小题，每小题5分，共30分) 26.用等值演算求(P→Q)→R的主合取范式。

27.列出(P→(Q∨R)) (P→Q)的真值表。

28．设A={a,b,c,d}，R={，，，，}，求R的传递闭包。

29.设A={2，3，6，12，24，36}，请画出A上整除关系的哈斯图，并给出子集{6，12，24，36}的下界、下确界、极大元、最大元。

30.求右图所示格的所有5元子格。

31.用矩阵的方法求右图中结点u2，u5之间长为2的路径的数目。

四、证明题(本大题共3小题，第32小题8分，第33、34小题各6分，共20分) 32.用推理方法证明：P∨Q，P→R，Q→S├R∨S。

33.设A={|a，b∈Z+，Z+为整数集}，A上的关系R={<,>|ad=bc}，证明R是等价关系。

34．证明：一个图是强连通的，当且仅当图中有一个回路，它至少包含每个结点一次。

五、综合应用题（本大题共2小题，第35小题6分，第36小题9分，共15分） 35．符号化下面命题，并构造推理证明：人是要死的，苏格拉底是人，所以苏格拉底是要死的。

36．设H是G的有限子集，则是群的子群当且仅当是群的子代数。

全国2009年4月高等教育自学考试离散数学试题

课程代码:02324

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

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

1.下列为两个命题变元P,Q的小项是（ ） A.P∧Q∧ù P B.ù P∨Q C.ù P∧Q D.ù P∨P∨Q

2.下列语句中是真命题的是（ ） A.我正在说谎 B.严禁吸烟

C.如果1+2=3,那么雪是黑的 D.如果1+2=5,那么雪是黑的

3.设P:我们划船,Q:我们跑步.命题\"我们不能既划船又跑步\"符号化为（ A.ù P∧ù Q B.ù P∨ù Q C.ù（P«Q） D.ù（ù P∨ù Q）

4.命题公式（P∧（P→Q））→Q是（ ） A.矛盾式 B.蕴含式 C.重言式 D.等价式

5.命题公式ù（P∧Q）的成真指派是（ ） A.000,001,110, B.001,011,101,110,111 C.全体指派 D.无

6.在公式（）F（x,y）→（ y）G（x,y）中变元x是（ ）A.自由变元

）

B.约束变元

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

7.集合A={1,2,…,10}上的关系R={|x+y=10,x∈A,y∈A},则R的性质是（ ） A.自反的 B.对称的

C.传递的、对称的 D.反自反的、传递的

8.若R和S是集合A上的两个关系,则下述结论正确的是（ ） A.若R和S是自反的,则R∩S是自反的 B.若R和S是对称的,则RS是对称的 C.若R和S是反对称的,则R

S是反对称的

D.若R和S是传递的,则R∪S是传递的

9.R={<1,4>,<2,3>,<3,1>,<4,3>},则下列不是t（R）中元素的是（ A.<1,1> B.<1,2> C.<1,3> D.<1,4>

10.设A={{1,2,3},{4,5},{6,7,8}},下列选项正确的是（ ） A.1∈A B.{1,2,3}A C.{{4,5}}A

D.Æ∈A

11.在自然数集N上,下列运算是可结合的是（ ） A.a*b=a-2b B.a*b=min{a,b} C.a*b=-a-b D.a*b=|a-b|

12.在代数系统中,整环和域的关系是（ ） A.整环一定是域 B.域不一定是整环

）C.域一定是整环 D.域一定不是整环

13.下列所示的哈斯图所对应的偏序集中能构成格的是（ ）

A.

B.

C.

D.

14.设G为有n个结点的简单图,则有（ ） A.Δ(G)＜n B.Δ(G)≤n C.Δ(G)＞n D.Δ(G)≥n

15.具有4个结点的非同构的无向树的数目是（ ） A.2 B.3 C.4 D.5

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

）（

y）（P（x,y）Q（y,z））∧xP（x,y）中

的辖域为________,

x的辖域为

________.

17.两个重言式的析取是________式,一个重言式与一个矛盾式的析取是________式.

18.设N是自然数集合,f和g是N到N的函数,且f（n）=2n+1,g（n）=n2,那么复合函数（f=________（gf）（n）

f）（n）=________.

19.设复合函数gf是从A到C的函数,如果gf是满射,那么________必是满射,如果gf是入射,

那么________必是入射.

20.设A={1,2},B={2,3},则A-A=________,A-B=________.

21.设S是非空有限集,代数系统中,其中P（S）为集合S的幂集,则P（S）对∪运算的单位元是_

_______,零元是________. 22.在>中,2的阶是________.

23.设是格,其中A={1,2,3,4,6,8,12,24},≤为整除关系,则3的补元是________. 24.在下图中,结点v2的度数是________.

25.设图D=,V={v1,v2,v3,v4},若D的邻接矩阵A=长度为2的路有________条.

,则deg-（v1）=________,从v2到v4

三、计算题（本大题共5小题,第26、27小题各5分,第28、29小题各6分,第30小题8分,共30分） 26.已知A={{Æ},{Æ,1}},B={{Æ,1},{1}},计算A∪B,A

B,A的幂集P（A）.

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

28.下图给出了一个有向图.（1）求出它的邻接矩阵A；（2）求出A,A,A及可达矩阵P.

2

3

4

29.求下列公式的主合取范式和主析取范式:P∨（ù P→（Q∨（ù Q→R）））

30.设A={1,2,3,4,6,8,12,24},R为A上的整除关系,试画的哈斯图,并求A中的最大元、最小元、极大元、极小元.

四、证明题（本大题共3小题,第31、32小题各6分,第33小题8分,共20分） 31.在整数集Z上定义:

,证明:>是一个群.

32.R是集合A上自反和传递的关系,试证明:R

R=R.

33.证明:边e是图G的一条割边,当且仅当图G中不存在包含边e的简单回路.

五、应用题（本大题共2小题,第34小题6分,第35小题9分,共15分） 34.构造下面推理的证明.

如果小张和小王去看电影,则小李也去看电影.小赵不去看电影或小张去看电影.小王去看电影.所以,当小赵去看电影时,小李也去.

35.今有n个人,已知他们中任何2人的朋友合起来一定包含其余n-2人.试证明:

（1）当n≥3时,这n个人能排成一列,使得中间任何人是其两旁的人的朋友,而两头的人是其左边（或右边）的人的朋友.

（2）当n≥4时,这n个人能排成一圆圈,使得每个人是其两旁的人的朋友.

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

课程代码：02324

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

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

1．设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化正确的是（A． P∧Q B．P∧ Q C．P→ Q D．P∨ Q

2．下面联结词运算不可交换的是（ ） A．∧ B．→ C．∨ D．

3．下列命题公式不是重言式的是（ ） A．Q→（P∨Q）

B．（P∧Q）→P

C．（P∧ Q）∧（ P∨Q） D．（P→Q）（ P∨Q） 4．下列等价式不正确的是（ ） 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

5．设A（x）:x是人，B（x）：x犯错误，命题“没有不犯错误的人”符号化为（A．x(A(x)B(x)) B．x(A(x) B（x）） C．x(A(x)B(x)) D．x(A(x) B(x))

6．设M={x|f1(x)=0},N={x|f2(x)=0}，则方程f1(x)·f2(x)=0的解为（ ） A．M∩N B．M∪N C．MN

D．M-N

7．设A-B=，则有（ ） A．B= B．B≠

） ） C．AB

D．AB

8．A，B是集合，P（A），P（B）为其幂集，且A∩B=，则P(A)∩P(B)为（ ） A．

B．{}

D．{，{}}

C．{{}}

9．设集合A={1，2，3，……，10}，下列定义的运算关于集合A是不封闭的是（ ） A．x*y=max{x,y} B．x*y=min{x,y}

C．x*y=GCD{x,y},即x,y的最大公约数 D．x*y=LCM{x,y},即x,y的最小公倍数

10．设H，K是群（G，）的子群，下面代数系统是（G，）的子群的是（ ） A．（H∩K，） B．（H∪K，） C．（K-H，） D．（H-K，）

11．设A={1，2，3，4，5}，B={6，7，8，9，10}，以下关系是从A到B的入射函数的是 （ ）

A．f ={<1,8>,<3,9>,<4,10>,<2,6>,<5,7>} B．f ={<1,7>,<2,6>,<4,8>,<1,9>,<5,10>} C．f ={<1,6>,<2,7>,<4,9>,<3,8>} D．f ={<1,10>,<5,9>,<3,6>,<4,6>,<2,8>}

12．设简单图G所有结点的度数之和为12，则G一定有（ ） A．3条边 C．5条边

B．4条边 D．6条边

13．下列不一定是树的是（ ）

A．无回路的连通图 B．有n个结点，n-1条边的连通图 C．每对结点之间都有通路的图

D．连通但删去一条边则不连通的图

14．下面关于关系R的传递闭包t(R)的描述最确切的是（ ） A．t(R)是包含R的二元关系 B．t(R)是包含R的最小传递关系 C．t(R)是包含R的一个传递关系 D．t(R)是任何包含R的传递关系 15．欧拉回路是（ ）

A．路径 B．迹

C．既是初级回路也是迹 D．既非初级回路也非迹

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

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

16．设A={1，2}，B={2，3}，则AA=__________，AB=__________。

17．设A={1，2，3，4}上关系R={<1,2>,<2,4>,<3,3>,<1,3>}，则R的自反闭包r(R)= _________，对称闭包S（R）=__________。

18．命题公式（PQ）→ P的成真指派为__________，成假指派为__________。 19．公式（x）（F（x）→G(y)）→(y)(H(x)L(x,y,z))中的自由变元为_________，约束变元为__________。

20．设f :R→R,f (x)=x2-2,g :R→R,g(x)=x-1,那么复合函数

(fg)(x)=__________，(gf)(x)=__________。

21．有理数集Q中的*运算定义如下：a*b=a+b-ab，则*运算的单位元是__________，设a有逆元，则其逆元a-1=__________。

22．设A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>},那么dom(A∪B)=_______,ran(A∩B)= __________。

23．如下图的有补格中，c的补元是__________，b的补元是__________。

24．在根树中，若每一个结点的出度__________m,则称这棵树为m叉树。如果每一个结点的出度__________m或0，则称这棵树为完全m叉树。

25．是一个群，其中Zn={0,1,2,……,n-1},xy=(x+y)mod n，则在中，1的阶是__________，4的阶是__________。

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

26．构造命题公式（PQQR）→P R的真值表。

27．若集合A={1，{2，3}}的幂集为P（A），集合B={{，2}，{2}}的幂集为P（B），求

P(A)∩P(B)。

28．设X={1，2，3，4}，R是X上的二元关系，

R={<1,1>,<3,1>,<1,3>,<3,3>,<3,2>,<4,3>,<4,1>,<4,2>,<1,2>}。 （1）画出R的关系图； （2）写出R的关系矩阵；

（3）说明R是否具有自反、反自反、对称、传递性质。

29．求下列公式的主析取范式和主合取范式：（P→（QR））（ P→（ Q→R））。

30．设A={a,b,c},P(A)是A的幂集，R为A上的包含关系，试给出的哈斯图，

并给出子集{{a,b},{a,c},{c}}的极大元、极小元、最大元、最小元。

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

1x31．设H是形如01的2×2阶矩阵的集合，H中定义通常的矩阵乘法运算。验证H1x1x01=01。 是群，132．设R为N×N上的二元关系，a,b,c,d∈N×N，a,bRc,dbd,证明R为等价关系。

133．简单图G有n个结点，m条边，设m>2(n-1)(n-2)，证明：G是连通的。

五、应用题（本大题共2小题，第34小题7分，第35小题8分，共15分） 34．构造下面推理的证明。

只要A曾到过受害者房间并且11点以前没离开，A就犯了谋杀罪。A曾到过受害者房间。如果在11点以前离开，看门人会看见他。看门人没有看见他。所以A犯了谋杀罪。

35．在某次国际会议的预备会中，共有8人参加，他们来自不同的国家。已知他们中任何两个无共同语言的人中的每一个，与其余有共同语言的人数之和大于或等于8，问能否将这8个人排在圆桌旁，使其任何人都能与两边的人交谈。

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

课程代码：02324

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

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

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

B.P→Q D.P→Q

2.下列命题联结词集合中，是最小联结词组的是（ ） A.{， } C.{，∧}

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

A.如果2是偶数，那么一个公式的析取范式惟一 B.如果2是偶数，那么一个公式的析取范式不惟一 C.如果2是奇数，那么一个公式的析取范式惟一 D.如果2是奇数，那么一个公式的析取范式不惟一 4.谓词公式x(P(x)∨yR(y))→Q(x))中变元x是（ ） A.自由变元

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

B.约束变元

D.既是自由变元也是约束变元 B.{，∨，∧} D.{∧，→}

5.若个体域为整数减，下列公式中值为真的是（ ） A.xy(x+y=0) C.xy(x+y=0)

6.下列命题中不正确的是（ ） ．A.x∈{x}-{{x}}

C.A={x}∪x,则x∈A且xA

B.{x}{x}-{{x}} D.A-B=A=B B.yx(x+y=0) D.xy(x+y=0)

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

8.下列表达式中不成立的是（ ） ．A.A∪(BC)=(A∪B)  (A∪C) C.(AB)×C=(A×C)  (B×C)

9.半群、群及独异点的关系是（ ） A.{群}{独异点}{半群}

B.{独异点}{半群}{群} B.A∩(BC)=(A∩B)  (A∩C) D.(A-B) ×C=(A×C)-(B×C) B.PQ D.Q=P

C.{独异点}{群}{半群} D.{半群}{群}{独异点}

10.下列集合对所给的二元运算封闭的是（ ） A.正整数集上的减法运算

B.在正实数的集R+上规定为ab=ab-a-b

+

a,b∈R

C.正整数集Z+上的二元运算为xy=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) C.f：Z→N,f(j)=|2j|+1

1,j是奇数B.f：N→N,f(j)=

0,j是偶数D.f：R→R,f(r)=2r-15

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

B.R={,} D.R={}

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

B.3个 D.5个

15.设D的结点数大于1，D=是强连通图，当且仅当（ ） A.D中至少有一条通路

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

B.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,则复合函数(fg)(x)____________,

(gf)(x)__________________。

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

图。

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

Δ(G)=_____________，G的最小度δ(G)=_____________。 0123.设图G,V={v1,v2,v3,v4},若G的邻接矩阵A11101011，则deg-(v1)=_ ________, 100000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>}，则RS_______________，SR_______________。 三、计算题（本大题共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）你能给出几种不同的分组方案？

全国2007年7月高等教育自学考试

离散数学试题

课程代码：02324

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

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

1．令P：今天下雪了，Q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ ） ．A．P→Q C．P∧Q

2．下列命题公式为重言式的是（ ） A．Q→（P∧Q） C．（P∧Q）→P

B．P→（P∧Q） D．（P∨Q）→Q B．P∨Q D．P∧Q

3．下列4个推理定律中，不正确的是（ ） ．A．A（A∧B） C．（A→B）∧AB

B．（A∨B）∧AB D．（A→B）∧BA

4．谓词公式x(P(x)∨yR(y))→Q(x)中量词x的辖域是（ ） A．x(P(x)yR(y)) C．(P(x)∨yR(y))

B．P（x） D．P(x), Q(x)

5．设个体域A={a,b}，公式xP(x)∧xS(x)在A中消去量词后应为（ ） A．P(x)∧S(x) C．P(a)∧S(b)

6．下列选项中错误的是（ ） ．．A．ØØ C．Ø{Ø}

B．Ø∈Ø D．Ø∈{Ø}

B．P(a)∧P(b)∧(S(a)∨S(b)) D．P(a)∧P(b)∧S(a)∨S(b)

7．设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}}

8．设R为实数集，函数f：R→R，f(x)=2x，则f是（ ） A．满射函数 C．双射函数

B．入射函数 D．非入射非满射

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

关于数的乘法运算构成该群的子群的是（ ）

A．{R+中的有理数} C．{R+中的自然数}

B．{R+中的无理数} D．{1，2，3}

10．下列运算中关于整数集不能构成半群的是（ ） ．A．ab=max{a, b} C．ab=2ab

B．ab=b D．ab=|a-b|

11．设Z是整数集，+，分别是普通加法和乘法，则（Z，+，）是（ ） A．域 C．整环

B．整环和域 D．含零因子环

12．设A={a, b, c}，R是A上的二元关系，R={, , , }，那么R是（ ） A．反自反的 C．可传递的

B．反对称的 D．不可传递的

13．设D=为有向图，V={a, b, c, d, e, f}, E={, , , , }是 （ ） A．强连通图 C．弱连通图

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

14．在有n个结点的连通图中，其边数（ ） A．最多有n-1条 C．最多有n条

B．至少有n-1条 D．至少有n条

15．连通图G是一棵树，当且仅当G中（ ） A．有些边不是割边 C．无割边集

B．每条边都是割边 D．每条边都不是割边

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

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

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

17．公式x(P(x)→Q(x,y)∨zR(y, z))→S(x)中的自由变元为________________，约束变元为________________。

18．设集合M={x|1≤x≤12,x被2整除，x∈Z},N={x|1≤x≤12,x被3整除，x∈Z}，则 M∩N=________________，M∪N=________________。 19．设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g=________________，gf=________________。

20．设A={a,b,c}，R是A上的二元关系，且给定R={,,}，则R的自反闭包r(R)= ________________，对称闭包s(R)= ________________。

21．设Q为有理数集，笛卡尔集S=Q×Q，*是S上的二元运算，,∈S,

*=, 则*运算的幺元是________________。∈S, 若a≠0，则的逆元是________________。

22．设*是集合S上的二元运算，若运算*满足________________且存在________________，则称为独异点。

23．令A={a, b, c}，是循环群，a是单位元，则b2=________________，c的阶是________________。

24．如下无向图割点是________________，割边是________________。

25．无向图G具有生成树，当且仅当________________。G的所有生成树中________________的生成树称为最小生成树。

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

8分，共30分）

26．集合A={a, b, c, d, e}上的二元关系R为

R={, , , , , , , , , , , , , }

27．利用真值表判断公式（（P∨Q）∧（Q→R））→（P∧R）是否为重言式。

28．给定图G如下所示，（1）写出G的可达矩阵；（2）G中长度为4的路有几条？ （1）写出R的关系矩阵；

（2）判断R是不是偏序关系，为什么？

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

30．设A为54的因子构成的集合，RA×A，x,y∈A, xRyx整除y。画出偏序集的哈斯图，并求A中的最大元，最小元，极大元，极小元。

五、证明题（本大题共3小题，第31、32小题各6分，第33小题8分，共20分） 31．设R是A上的一个自反关系，证明：R是一个等价关系，当且仅当若∈R，∈R，则∈R。

32．设是一个群，x∈G，定义：ab=a*x*b，a,b∈G。证明：也是一个群。

33．设图G是具有6个结点，12条边的无向简单图，证明图G是汉密尔顿图。

五、应用题（本大题共2小题，第34小题8分，第35小题7分，共15分） 34．构造下面推理的证明。

如果今天是星期六，我们就要到颐和园或圆明园去玩。如果颐和园游人太多，我们就不去颐和园玩。今天是星期六，颐和园游人太多，所以我们去圆明园玩。

35．n个城市用k条公路的网络连结。一条公路定义为两个城市间的一条不穿过任何中间城

1市的道路。任意两个城市之间至多修一条公路。证明如果k>(n-1)(n-2)，则人们总能通

2过连结的公路，在任何两个城市间旅行。

全国2007年4月高等教育自学考试离散数学试题

课程代码：02324

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

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

1．下列命题公式中不．是重言式的是（ ） A．p→(q→r) B．p→(q→p)

C．p→(p→p)

D．(p→(q→r))(q→(p→r))

2．下列语句中为命题的是（ ） A．这朵花是谁的？ B．这朵花真美丽啊！ C．这朵花是你的吗？

D．这朵花是他的。 3．设个体域是整数集，则下列命题的真值为真的是（ ） A．yx(x·y=1) B．xy (x·y≠0) C．xy (x·y=y2)

D．yx(x·y=x2)

4．关于谓词公式（x）(y)(P(x,y)∧Q(y,z))∧(x)p(x,y),下面的描述中错误．．的是（ A．（x）的辖域是（y）（P（x,y）∧Q(y,z)） B．z是该谓词公式的约束变元 C．（x）的辖域是P（x,y）

D．x是该谓词公式的约束变元

5．设论域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）

6．集合A={1，2，3}上的下列关系矩阵中符合等价关系条件的是（ ） 101A．010 101B．010 001101110100C．011 D．110 1011117．设A={Ø}，B=P（P（A）），以下不．正确的式子是（ ） A．{{Ø }，{{Ø }}，{Ø ，{Ø }}}包含于B B．{{{Ø }}}包含于B

C．{{Ø ，{Ø }}}包括于B

D．{{Ø }，{{Ø ，{Ø }}}}包含于B

8．设Z是整数集，E={…，-4，-2，0，2，4，…}，f：Z→E，f（x）=2x，则f（ A．仅是满射 B．仅是入射 C．是双射

D．无逆函数

） ）9．设A={1，2，3，4，5}，A上二元关系R={〈1，2〉，〈3，4〉，〈2，2〉}，S={〈2，4〉，〈3，1〉，〈4，2〉}，则S-1R-1的运算结果是（ ） A．{〈4，1〉，〈2，3〉，〈4，2〉} C．{〈4，1〉，〈2，3〉，〈2，4〉}

B．{〈2，4〉，〈2，3〉，〈4，2〉} D．{〈2，2〉，〈3，1〉，〈4，4〉}

10．设有代数系统G=〈A，*〉，其中A是所有命题公式的集合，*为命题公式的合取运算，则G的幺元是（ ） A．矛盾式 C．可满足式

B．重言式 D．公式p∧q

11．在实数集合R上，下列定义的运算中不可结合的是（ ） ．A．a*b=a+b+2ab C．a*b=a+b+ab

B．a*b=a+b D．a*b=a-b

12．下列集合关于所给定的运算成为群的是（ ）

A．已给实数a的正整数次幂的全体，且a{0，1，-1}，关于数的乘法 B．所有非负整数的集合，关于数的加法 C．所有正有理数的集合，关于数的乘法 D．实数集，关于数的除法

13．设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶点数是（ ） A．3 C．5

B．4 D．6

14．下列各图中既是欧拉图，又是汉密尔顿图的是（ ）

A． B． C． D． 15．设无向图G的边数为m，结点数为n，则G是树等价于（ ） A．G连通且m=n+1 C．G连通且m=2n

B．G连通且n=m+1

D．每对结点之间至少有一条通路

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

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

16．不能再分解的命题称为____________，至少包含一个联结词的命题称为____________。 17．在命题演算中，五个联结词的含义是由其____________表唯一确定的，而不是由其类似的____________语言的含义确定。

18．使公式（x）（y）（A（x）→B（y））（（x）A（x）→（y）B（y））成立的条件是____________不含有y，____________不含有x。

19．设A为任意集合，请填入适当的运算符，使式子A____________A=Ø；A____________~A=Ø成立。

20．设A={0，1，2，3，6}，R={〈x,y〉|x≠y∧(x,y∈A)∧y≡x(mod 3)}，则domR=____________，ranR=____________。

21．称集合S是给定非空集合A的覆盖：若S={S1，S2，…，Sn}，其中SiA，Si≠Ø，i=1，2，…，n，且____________；进一步若____________，则S是集合A的划分。 22．对实数的普通加法和乘法，____________是加法的幂等元，____________是乘法的幂等元。

23．在代数系统〈A，*〉中，A={a}，*是A上二元运算，则该代数系统的单位元是____________，零元是____________。

24．设〈A，≤〉是偏序集，若A中____________都有最小上界和____________则称A关于偏序≤构成格。

25．若一条路中，所有边均不相同，则此路称作____________；若一条路中所有的结点均不相同，则称此路为____________。

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

小题各6分，共30分）

36．试画出结点数为3的（1）强连通图；（2）单向连通图；（3）弱连通图；（4）非连通图。

27．设A={0，1，2，3}，R={〈x,y〉|x,y∈A∧(y=x+1∨y=试求RSR

28．在全体正整数集合Z+中规定∩，∪为：对任意的a,b∈Z+，

a∪b=[a,b]，即求a,b的最小公倍数； a∩b=(a,b)，即求a,b的最大公约数；

则运算∩，∪满足结合律，交换律和吸收律，于是〈Z+，∩，∪〉是一个格。判断下列

x)}，S={〈x,y〉|x,y∈A∧（x=y+2）}。2集合是否是的子格？

1）A={1，2，3，9，12，72} 2）A={1，2，3，12，18} 3）A={5，52，53，…，5n} 4）T=2Z+={2k|k∈Z+}

29．求命题公式（p→q）→（q∨p）的主析取范式。

30．结出命题公式（p∨(p∧q)）∧((p∨q)∧q)的二叉树表示。

31．设A={a,b,c,d}, R={〈a,c〉，〈c,b〉，〈b,a〉，〈a,d〉}，求R，r(R),s(R),t(R)的关系图。

四、证明题（本大题共3小题，第32、33小题各6分，第34小题8分，共20分） 32．设A是非空集合，P（A）是A的幂集，是集合的包含关系，则〈P（A），〉是格，证明：〈P（A），〉是有补格。

33．设〈{a,b},*〉是半群，其中a*a=b，证明：（1）a*b=b*a；（2）b*b=b。

34．若一棵树恰有2个结点的度数为1，则它必是一条欧拉路。

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

35．设I是整数集，<，>，＝，≤，≥，≠是Ｉ上的二元关系，分别表示小于，大于、等于、小于等于，大于等于，不等于，那么这些关系会满足什么性质？试填写下表

< > = ≤ ≥ ≠ ≤∩≥ ≤∪≥

自反 反自反 对称 反对称 传递 2006年7月全国自考离散数学试题试卷真题

课程代码：02324

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

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列语句中不是命题的只有（ ） ．A．鸡毛也能飞上天？ C．不经一事，不长一智。

B．或重于泰山，或轻于鸿毛。 D．牙好，胃口就好。

2．从真值角度看，命题公式的全部类型是（ ） A．永真式 C．永真式，永假式

其中错误的表达式是（ ） ．．A．(x)(M(x)F(x)) C．(x)(M(x)F(x))

4．下列公式是前束范式的是（ ） A．(x)(y)(F(z,x)G(y)) C．(x)F(x,y)(y)G(y)

B．((x)F(x)(y)G(y))H(z) D．(x)(F(x,y)(y)G(x,y)) B．(x)(M(x)F(x)) D．(x)(M(x)F(x)) B．永假式

D．永真式，永假式，可满足式

3．设M（x）：x是人；F（x）：x要吃饭。用谓词公式表达下述命题：所有的人都要吃饭，

5．设论域为整数集，下列真值为真的公式是（ ） A．(x)(y)(xy0) C．(x)(y)(xy0)

B．(y)(x)(xy0) D．(x)(y)(xy0)

6．下列是谓词演算中的合式公式的是（ ） A．(x)(p(x)y) C．(x)P(x,y)Q(y,z) ．（ ） A．B． C．D． ．（ ）

8．下列式子正确的是（ ） A．（A－B）-C=A-（B∪C） C．~（A－B）=~（B－A）

B．A－（B∪C）=（A－B）∪C D．~（A∩B）A B．(x)F(x)G(x,y) D．(x)xP(x,y)

（ ）

9．下列集合对所给的运算是封闭的只有（ ）

A．非零整数集合Z*上的除法运算

B．全体n×n实可逆矩阵集合Mn（R）上的矩阵加法和乘法运算 C．全体n×n实矩阵集合Mn（R）上的矩阵加法和乘法运算 D．A={1，2，…，10}，x*y=LCM（x，y），即x，y最小公倍数

+，*>是环，则下列说法不正确的是（ ） 10．设是交换群 A．+是可分配的 C．*对○

B．是半群

+对*是可分配的 D．○

11．下列四个格，是分配格的是（ ） C．D． ．（ ） A．B．

12．下列各图是无向完全图的是（ ）

13．下列各有向图是强连通图的是（ ）

14．设Ｇ是具有n个结点的无向简单图，若在Ｇ中存在一条汉密尔顿路，则Ｇ中每一对结点的度数之和与n-1的关系为（ ） A．大于 C．等于

B．大于等于 D．小于

15．设连通平面图Ｇ，共有n个结点，e条边，r个面，则欧拉证明成立的公式是（ ） A．e-n+r=2 C．n-r+e=2

B．n+r-e=2 D．n-e-r=2

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

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

16．所谓____是指不能再分解的命题，而复合命题是由一些____经过联结词复合而成的命题。 17．在命题演算中，两个____的合取、析取、条件、双条件均为____。

18．使公式(x)(y)(A(x)B(y))(x)A(x)(y)B(y)成立的条件是____中不含y，____中不含x。

19．设A={1，2，3，4}，R是A上的二元关系，R={|x/y是素数}，则domR=_____; ranR=____。

20．设无向图Ｇ有n个结点m条边，每个结点的度数为k或k+1，记Nk为度数等于k的结点数，则Nk=_____。如果无向简单图C的结点的度数均为相同的偶数，且m=7，则n=____。 21．设X={1，3，5，9，15，45}，R是X上的整除关系，则R是X上的偏序，其最大元是___，极小元是____。

22．设是有界格，a,bL,若ab=0,则a=b=_____；若ab=1,则a=b=____。 23．设e是群G上的幺元，若aG且a2=e,则a-1=____ ,a-2=__________。

24．代数系统，其中A为命题公式集合，。为析取运算，则中零元素是____，幺元是____。

25．树是不包含_____的___图。

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

26．如果论域是集合{a,b,c}，试消去下面公式中的量词：(x)(y)(xy0) 27．求公式（pq)(qr)的主析取范式。

28．设A={a,b,c},A上二元关系R={,,},用关系矩阵法求最小的自然数m,n,m29．根据下列条件如果能画则请画出一个欧拉图，如果不能画则请说明理由。 （1）偶数个顶点，偶数条边 （2）奇数个顶点，奇数条边 （3）偶数个顶点，奇数条边 （4）奇数个顶点，偶数条边

30．下列各整数集合对于整除关系“|”都构成偏序集，判断哪些偏序集能构成格？并说明理由。 1)L={1,2,3,4,5} 2) L={1,2,3,6,12} 3)L={1,2,3,4,6,9,12,18,36} 4)L={1,2,22,23,…,2n}

31．设A={2，3，5，12，19}，等价关系R={|x, yAxy(mod 3)},写出各元素的

等价类，并求A/R。

四、证明题（本大题共3小题，第32、33题各6分，第34题8分，共20分） 32．用等价变换法证明：(PQ)((RQ)((PR)Q))是永真式。 33．若无向图G是欧拉图，G中是否存在割边？为什么？

34．设A是一个集合，X=P（A），R是X上元素之间的包含关系，试证明是偏序集。（注：P（A）为A的幂集）

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

35．设有n个村庄要修路，（1）若要使所有村庄之间都有通路，问需在两村之间至少修几条路？（2）若要使任意两村庄之间有一条直接的路，则至少修几个路？（3）若修一条连接所有村庄的环路，问有多少种修路方案？

36．设有推理：

(a)没有不守信用的人是可信赖的； (b)有些可以信赖的人是受过教育的人； (c)因此有些受过教育的人是守信用的。

试构造推理的证明，要求把推理的前提，结论符号化为谓词形式，并写出推理过程。（个体域：人的集合）

提示：设F（x）表示x是守信用的人；G（x）表示x是可信赖的人；H（x）表示x是受过教育的人。

全国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={S={|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

B．11，3，5

C．12，3，6 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={，，，，， d>}，则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欲修建道路使村村可通。现已有修建方案如下带权无向

图所示，其中边表示道路，边上的数字表示修建该道路所需费用，问应选择修建哪些道路可使得任二个村庄之间是可通的且总的修建费用最低?要求写出求解过程，画出符合要求的最低费用的道路网络图并计算其费用。

全国2005年7月高等教育自学考试离散数学试题

课程代码：02324

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

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

1.数理逻辑是采用（ ）研究抽象思维规律的一门科学。 A.数学方法 C.实践方法

B.逻辑方法 D.抽象方法

2.下列式子正确的是（ ）

3.下列含有命题p，q，r的公式中，是主析取范式的是（ ）

4.设R（x）：x是实数；S（x,y）：x小于y。用谓词表达下述命题：不存在最小的实数。其中错误的表达式是：（ ）

5.在论域D={a,b}中与公式（x）A（x）等价的不含存在量词的公式是（ ） A.A(a)A(b) C. A(a)A(b)

B. A(a)A(b) D. A(b)A(a)

6.对公式(x)(y)(P(x,y)Q(y,z)(x)P(x,y)的说法正确的是（ ） A.x是约束出现，y是约束出现，z是自由出现

B.x是约束出现，y既是约束出现又是自由出现，z是自由出现 C.x是约束出现，y既是约束出现又是自由出现，z是约束出现 D.x是约束出现，y是约束出现，z是约束出现 7.偏序关系具有性质（ ） A.自反、对称、传递 B.自反、反对称 C.反自反、对称、传递 D.自反、反对称、传递

8.下列命题正确的是（ ）

9.以下系统是代数系统的是（ ）

A.，其中Z+是正整数集，-是数的减法运算 B.，其中A={a,b}，*运算定义为

* a b a b a a a b

C. ，其中Z为整数集，÷是数的除法运算 D. ，其中R为实数集，÷是数的除法运算

10.G1,1,i,i　,x(其中x是数的乘法运算i1)是一个群,下列代数系统为G的子群的是(　　　　),x A.1　

B.

i　,x

C.

i,i　,x

1,1　,x D. 11. 若R,,是环，且R中乘法适合消去律，则R是（ ） A.无零因子环 C.整环

B.除环 D.域

12.在简单无向图G=V,E中，如果V中的每个结点都与其余的所有结点邻接，则该图称为（ ） A.正则图 C.连通图

B.完全图 D.强连通图

13.设G是n个结点m条边的连通平面图，则当n≥3时必有（ ）成立。

n(n1)A.m≤ B.n=2m

2C.m≤3n-6

D.n-1=m

14.在下列关于图论的命题中，为真的命题是（ ） A.一个强连通的有向图一定是欧拉图

B.一个连通的无向图，且所有结点度数都是偶数，则它一定有欧拉回路 C.一定能构造一个欧拉图，使得结点数和边数的奇偶性相反 D.无向欧拉图中一定存在有一条边是割边

15.给定n个结点的一个图，它还是一个树的下列说法中，（ ）是不对的。 A.无回路的连通图

B.无回路但若增加一条新边就会变成回路 C.连通且e=v-1，其中e是边数，v是结点数 D.所有结点的度数≥2

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

16.含有n个命题变元（n>0）的命题公式的真值是___________，它共有___________组真值指派，只有对各命题变元指定一个真值后，该命题公式才能成为命题。

17.在个体域D中，公式xG(x)的真值为假当且仅当___________，公式xG(x)的真值为假，当且仅当___________。

18.给定个体域为整数域，若F（x）：表示x是偶数，G（x）：表示x是奇数；那么，(x)F(x)(x)G(x)是一个 语句；而(x)(F(x)G(x))是一个

语句。

19.设X是所有三角形的集合，Y是所有圆的集合，映射是:XY,且XX的内切圆，则它的定义域是 ，值域是 。

0,1,0,2,0,3,1,2,1,3,2,3，若20.设A={0，1，2，3}，A上的关系R=　Rm=

0,3,Rn,则最小m= ，最小n= 。

,A上的二元关系Ra,b,b,c,则r(R) ；21.设Aa,b,c　s(R)= 。

22.若群G中存在一个元素a，使得G中的任意元素都由a的幂组成，则称G是 ，a称为G的 。

23.设G,是群,a,bG，则（a-1）-1= ，（ab）-1= 。

24.设图G1=V1,E1,G2V2,E2,且E2E1，如果 ，则称G2是G1的子图，如果 ，则称G2是G1的生成子图。

25.一个结点为n的无向完全图，其边的数目为 ；并且它是 度正则图。

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

26.已知命题A含有命题变元R，Q，R，且按P、Q，R的顺序A的主合取范式为M001∧M100∧M010，试求A的主析取范式，并按P、Q，R的顺序写出完整的范式表达式。

27.设集合A有n个元素和集合B有m个元素，且AB,求P(A)P(B)的元素个数。（表示对称差）

28.有向图D如下图所示，用邻接矩阵法求D中长度为3的路径的数目和长度为3的回路数。

29.设Gn0,1,2,,n1　,n11,Gn上二元运算定义为a,bGn,ab，　　若abn,　　ab则Gn,是群,在Gn中求元素y,使满足:

abn,　　　若abn,y10n2,要求写出求解过程。30.设解释Ⅰ如下：D={0，1，2}，f (0)=1;f (1)=2;f (2)=0;F(0,0)=1,F(0,1)=0,F(1,0)=1,F(1,2)=0, F(1,1)=1,F(2,0)=1,F(0,2)=0,F(2,1)=1,F(2,2)=1,试求出下列公式在Ⅰ下的真值。 （1）F（f(0),f(2)）∧F(f(1),f(0))∨F(F(2,2),F(f(2),F(0,2))) (2)(x)(y)(F(x,y)F(f(x),f(y)))

31.公安人员审理某珠宝商店的钻石项链的失窃案，已知侦察结果如下： （1）营业员A或B盗窃了钻石项链 （2）若B作案，则作案时间不在营业时间 （3）若A提供的证词正确，则货柜未上锁

（4）若A提供的证词不正确，则作案发生在营业时间 （5）货柜上了锁

试问：作案者是谁？要求写出推理过程。

四、证明题（本大题共3小题，第32、33小题每小题7分，第34小题8分，共22分） 32.已知前提：(x)(Fx)(y)((F(y)Q(y))R(y)),(x)F(x);结论(x)R(x) 33.证明无向图G具有生成树当且仅当G是连通图。

34.设R是集合A上的自反、传递的二元关系，又设T也是A上的二元关系，且满足： x,yTx,yRy,xR。求证：T是A上的等价关系。

全国2004年7月高等教育自学考试离散数学试题

课程代码：02324

一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填

在题干的括号内。每小题1分，共14分) 1.下列语句不是命题的是( )。 ．．A.黄金是非金属。

B.要是他不上场，我们就不会输。

C.他跑100米只用了10秒钟，你说他是不是运动健将呢? D.他跑100米只用了10秒钟，他是一个真正的运动健将。 2.关于命题变元P和Q的大项M01表示( )。 A.┐P∧Q C.P∨┐Q

B.┐P∨Q D.P∧┐Q

S(x,y)中的(x)的辖域是( )。 B.P(x,z)→Q(y) D.S(x,z)

3.公式(x)(y)(P(x,z)→Q(y))A.(y)(P(x,z)→Q(y)) C.P(x,z)

4.下列等价式不成立的是( )。 ．．．A.┐(x)A(x)(x)┐A(x) B.┐(x)A(x)(x)┐A(x)

C.(x)(A(x)∧B(x))(x)A(x)∧(x)B(x) D.(x)(A(x)∨B(x))(x)A(x)∨(x)B(x) 5.公式(x)(y)(P(x,y)∧Q(z))→R(x)中的x( )。 A.只是约束变元 B.只是自由变元

C.既是约束变元又是自由变元 D.既非约束变元又非自由变元

6.设A={a,{a}}，则下列各式正确的是( )。 A.{a}∈p(A)(A的幂集) C.{{a}}p(A)

B.{a}p(A) D.{a,{a}}p(A)

7.集合的以下运算律不成立的是( )。 ．．．A.A∩B=B∩A C.AB=BA

B.A∪B=B∪A D.A-B=B-A

8.设N是自然数集，R是实数集，函数f：Ｎ→R，f(n)=lgn是( )。 A.入射

B.满射

C.双射 D.非以上三种的一般函数

9.设实数集R上的二元运算o为：xoy=x+y-2xy,则o不满足( )。 A.交换律

B.结合律 D.有零元

C.有幂等元

10.若(A，*)是一个代数系统，且满足结合律，则(A，*)必为( )。 A.半群 C.群

B.独异点 D.可结合代数

11.设S是自然数集，则下列运算中不满足交换律的是( )。 A.a*b=|a-b|

B.a*b=ab D.a*b=min{a,b}

C.a*b=max{a,b}

12.设图G′=是图的生成子图，则必须( )。 A.V′=V C.E′=E

B.V′≠V但E′=E D.E′≠E且V′≠V

13.设有向图G有5个结点，4条边，且有一条有向路经过每个结点一次，则图G满足的最大连通性是( )。 A.不连通

B.弱连通 D.强连通

C.单侧连通

14.一个连通图G具有以下何种条件时，能一笔画出：即从某结点出发，经过图中每边仅一次回到该结点。( )。 A.G没有奇数度结点 C.G有2个奇数度结点

B.G有1个奇数度结点 D.G没有或有2个奇数度结点

二、填空题(每小题2分，共30分) 1.设P：a2+b2=a2,Q:b=0,则P

Q意思是说______.

2.合式公式┐(Q→P)∧P是永______式. 3.合式公式(P

Q)∧(Q

R)与P

R的关系是______.(等价或蕴含选一)

4.命题“所有的猫都是动物”的谓词表达式为__________. 5.公式(x)A(x)→B(y)的前束范式为______.

6.设个体域为D={-2,3,6},F(x):x3,G(x):x>5.则在此解释下公式(x)(F(x)∧G(x))的真值为______.

7.设R是有限集A中的关系，若其关系矩阵MR的主对角线上的元素全为0，则R至少是______关系.

8.设A={a,b,c}中的关系R={,}，则R的对称闭包为S(R)=______. 9.设X={1,2,3},Y={a,b}，则从X到Y的不同的函数共有______个.

10.设A={0,1,2,3}，A中的序关系“”定义为：aba整除b，则a的最小元是 ，最大元是______.

11.只有两个元素的群有且只有______个子群.

12.一个格称为布尔代数，如果它是______格和______格.

01113.设图G的邻接矩阵为M=110，则G的可达性矩阵为______.

10014.设一个平面图有v个结点，e条边，r个面，则它们的数量关系是______. 15.一个无向树中有6条边，则它有______个结点. 三、计算题(每小题6分，共24分)

1.求合式公式A=P→((P→Q)∧┐(┐Q∨┐P))的主析取范式和主合取范式.

2.设集合A={a,b,c},A中的关系R={,,,}.利用矩阵方法求R的传递闭包t(R).

3.设(S，*)是代数系统，其中S={a,b,c}，*的运算表为

* a b c a a b c b b a a c c a a 讨论(S，*)是否构成独异点，并验证你的结论.

4.已知一算式的根树(如图)，试分别写出按中序行遍法、前序行遍法和后序行遍法的算式.

四、证明题(每小题8分，共32分) 1.利用CP规则证明

A→(B→C)，(C∧D)→E,┐D∨E→H├(A∧B)→H 2.利用推理规则证明

(x)(G(x)∨Q(x))，┐(x)G(x)(x)Q(x)

3.设R1，R2为集合A中的两个等价关系，且R1R2=R2R1，试证R1R2也是A上的等价关系.

4.试证：任一棵非平凡树G至少有两片树叶。

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

课程代码：02324

一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有

一个选项符合题目要求的。请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下列不是平面图的是( )

2.无向图G中有16条边，且每个结点的度数均为2，则结点数是( ) A.8 B.16 C.4 D.32

3.如下图所示的有界格中，元素b的补元是( ) A.a B.0 C.c D.d

4.设〈G,*〉是群，且|G|>1，则下列命题不成立的是( ) A.G中有幺元 B.G中有零元 C.G中任一元素有逆元

D.G中除了幺元外无其他幂等元

5.设Z是整数集合，则下面定义的二元运算不能使Z与构成代数系统的是( ) A.i j=|i-j|,i,j∈Z B.i j=i·j-j2，i,j∈Z C.i j=i/j,i,j∈Z D.i j=i2+j2+1,i,j∈Z

6.设A是非空集合，P(A)是A的幂集，∩是集合交运算，则代数系统〈P(A),∩〉的幺元是( A.P(A) B.φ

C.A D.|φ|

)

7.设N为自然数集(含0)，函数F：N→N×N,F(n)=是( ) A.满射，不是入射

B.入射，不是满射 C.双射

D.不是入射，不是满射

8.设A={a,b,c}，则下列是集合A的划分的是( )

A.{{b,c},{c}} B.{{a,b},{a,c}} C.{{a,b},c} D.{{a},{b,c}} 9.

设

集

合

X={0,1,2,3}

，

R

是

X

上

的

二

元

关

系

，

R={<0,0>,<0,2>,<1,2>,<1,3>,<2,0>,<2,1>,<3,3,>}，则R的关系矩阵MR是( )

11A．0001010100 B.10010110010011 C. 1000010101001010 D. 1011101001110011 00101010.下列命题中，不正确的是( ) A.{φ}∈{φ,{φ}} B.{φ}∈{φ,{{φ}}} C.{φ}{φ,{φ}} D.φ{φ,{ φ}}

11.设个体域是正整数集，则下列公式中真值为真的公式是( ) A.(x)(y)(x·y=0) B.(x)(y)(x·y=1) C.( x)(y)(x·y=2) D.(x)(y)(z)(x-y=z)

12.令F(x):x是金属，G(y):y是液体，H(x,y):x可以溶解在y中，则命题“任何金属可以溶解在某种液体中”可符号化为( ) A.(x)(F(x)∧(y)(G(y)∧H(x,y))) B.(x)((x)F(x)→(G(y)→H(x,y))) C.(x)(F(x)→(y)(G(y)∧H(x,y))) D.(x)(F(x)→(y)(G(y)→H(x,y))

13.在个体域D={a,b}中，与公式(x)A(x)等价又不含量词的公式是( ) A.A(a)∧A(b) B.A(a)→A(b) C.A(a)∨A(b) D.A(b)→A(a) 14.下列句子是命题的是( ) A.水开了吗? B.x>1.5

C.再过5000年，地球上就没水了。 D.我正在说谎

15.下列是命题公式p∧(q∨┓r)的成真指派的是( ) A.110，111，100 B.110，101，011 C.所有指派 D.无 二、填空题(本大题共20个空，每空1分，共20分)

16.有向图D如下：D的邻接矩阵A=(aij)3×3,则a11=____,a32=____。

17.一个连通平面图G有10条边，G中度为1的顶点有2个，其余是度为6的顶点，则G中共有___个顶点，____个面。

18.设〈B,∧,∨,′，0，1〉是布尔代数，对任意的a∈B,有a∨a′=____,a∧a′=______。 19.设〈G，*〉是群，若G中存在一个元素a，使得G中任意元素都可由a的幂生成，则称该群是____，元素a称为该群的________。

20.设X={1,2,3}上的关系R的关系图如下，从关系图可知R具有________________，________和传递性等性质。

21.设A={2,3,6,12},≤是A上的整除关系，则偏序集〈A，≤〉的最大元是________，极小元是________。

22.设A={φ,{φ}},B={0,1},所有从A到B的双射函数是f1=________,f2=________。 23.谓词公式(x)( y)（P(x,y)∨R(y))→Q(y)，则其约束变元是________，自由变元是________。

24.合取范式具有形式A1∧A2∧…∧An(n≥1)，其中A1，A2，…，An是由________及其________所组成的析取式。

25.设命题P为“明天上午8点下雨”，Q为“明天上午8点下雪”，R为“我去学校”，则“如果明天上午8点不下雨且不下雪则我去学校”可表示为公式________；而“只有当明天上午8点不下雪并且不下雨时我才去学校”可表示为公式________。 三、计算题(本大题共6小题，共30分)

26.(5分)一棵树有2个4度结点，3个3度结点，其余结点是叶子，求该树的叶子数。 27.(6分)设A={a,b,c,d},G=是交换群,a是G的单位元。G的运算表如下：

* a b c d a a b c d b b a x4 x5 C C x1 A X6 d d x2 x3 a 求x1,x2,x3,x4,x5,x6并说明道理

28.(4分)设集合A={1,3,5,7,9,11,13,15},A上的一个划分S={{1,15},{3,9,11,13},{5,7}}。 试求由S导出的A上的等价关系R。

29.(4分)设A={a,b,c,d},R={,,,}。试用关系图表示R及R的传递闭包。 30.(5分)求公式(x)(F(x)→(y)G(,xy,z))→(z)H(x,y,z)的前束范式。 31.(6分)作出命题公式(p→(q∨r))→┓q的真值表，并写出其主析取范式。 四、证明题(本大题共3小题，共20分)

32.(8分)证明A→(B→C),(C∧D)→E, ┓F→(D∧┓E)|-A→(B→F)成立。

33.(6分)证明：如果一个有向图G是弱连通图且是欧拉图，则G是强连通图。

34.(6分)设〈G,*〉是群，a∈G，N={ah-1a|h∈G},证明〈N，*〉是〈G,*〉的子群。

五、应用题(本大题共2小题，共15分)

35.(6分)某发电厂a要向b,c,d,e四个地点送电，已知发电厂可以和b,c,d直接架接电线，地点e可以和b与d直接架设电线，其他由于地理原因无法直接架设电线，在a,b,c,d和e之间架设电线时不能有回路存在，否则会造成浪费。请找出所有电线架设方案，使从a可向b，c，d，e供电。

36.(9分)对下面推理进行符号化，并作证明。会操作计算机的人都认识26个英文字母。文盲都不认识26个英文字母。有的文盲是很聪明的。所以有的很聪明的人不会操作计算机。(个体域：所有人的集合)

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

离散数学试题

课程代码：02324

一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。

1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( ) A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路

2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( ) A.10 B.12 C.16 D.14

3.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( ) A.b∧(a∨c) B.(a∧b)∨(a’∧b)

C.(a∨b)∧(a∨b∨c)∧(b∨c) D.(b∨c)∧(a∨c)

4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是( ) A.<{1},·> B.〈{-1},·〉 C.〈{i},·〉 D.〈{-i},·〉

5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交运算，下列系统中是代数系统的有( ) A.〈Z，+，/〉 B.〈Z，/〉 C.〈Z，-，/〉 D.〈P(A)，∩〉 6.下列各代数系统中不含有零元素的是( ) A.〈Q，*〉Q是全体有理数集，*是数的乘法运算

B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算 C.〈Z，Z是整数集，定义为xxy=xy,

x,y∈Z

D.〈Z，+〉，Z是整数集，+是数的加法运算 7.设A={1,2,3}，A上二元关系R的关系图如下： R具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性

8.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉〈,a,c〉}，则关系R的对称闭包S(R)是( ) A.R∪IA B.R C.R∪{〈c,a〉} D.R∩IA

9.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的等价关系，R应取( )

A.｛〈c,a〉，〈a,c〉｝ B.{〈c,b〉，〈b,a〉} C.{〈c,a〉，〈b,a〉} D.{〈a,c〉，〈c,b〉} 10.下列式子正确的是( ) A. ∈ B. C.{} D.{}∈

11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):xA.(  x)( y)( z)(A(x,y))→A(f(x,z),f(y,z)) B.( x)A(f(a,x),a) C.(x)(y)（A(f(x,y),x)) D.(x)(y)(A(x,y)→A(f(x,a),a))

12.设B是不含变元x的公式，谓词公式(x)(A(x)→B)等价于( ) A.(x)A(x)→B B.(x)A(x)→B C.A(x)→B D.(x)A(x)→(x)B 13.谓词公式(x)(P(x,y))→(z)Q(x,z)∧(y)R(x,y)中变元x( ) A.是自由变元但不是约束变元 B.既不是自由变元又不是约束变元 C.既是自由变元又是约束变元 D.是约束变元但不是自由变元

14.若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为( ) A.P∨Q B.P∧┐Q C.P→┐Q D.P∨┐Q 15.以下命题公式中，为永假式的是( )

A.p→(p∨q∨r) B.(p→┐p)→┐p C.┐(q→q)∧p D.┐(q∨┐p)→(p∧┐p) 二、填空题(每空1分，共20分)

16.在一棵根树中，仅有一个结点的入度为______，称为树根，其余结点的入度均为______。 17.A={1,2,3,4}上二元关系R={〈2，4〉，〈3，3〉，〈4，2〉}，R的关系矩阵MR中m24=______,m34=______。

18.设〈s,*〉是群，则那么s中除______外，不可能有别的幂等元；若〈s,*〉有零元，则|s|=______。 19.设A为集合，P(A)为A的幂集，则〈P(A)，〉是格，若x,y∈P(A),则x,y最大下界是______，最小上界是______。

20.设函数f:X→Y,如果对X中的任意两个不同的x1和x2，它们的象y1和y2也不同，我们说f是______函数，如果ranf=Y，则称f是______函数。

21.设R为非空集合A上的等价关系，其等价类记为〔x〕R。x,y∈A，若〈x,y〉∈R，则 〔x〕R与〔y〕R的关系是______，而若〈x,y〉R，则〔x〕R∩〔y〕R=______。 22.使公式(x)( y)(A(x)∧B(y))(x)A(x)∧(y)B(y)成立的条件是______不含有y，______不含有x。

23.设M(x):x是人，D(s):x是要死的，则命题“所有的人都是要死的”可符号化为(x)______,其中量词(x)的辖域是______。

24.若H1∧H2∧…∧Hn是______，则称H1,H2,…Hn是相容的，若H1∧H2∧…∧Hn是______，则称H1,H2,…Hn是不相容的。

25.判断一个语句是否为命题，首先要看它是否为 ，然后再看它是否具有唯一的 。 三、计算题 (共30分)

26.(4分)设有向图G=(V,E)如下图所示，试用邻接矩阵方法求长度为2的路的总数和回路总数。

27.(5)设A={a,b},P(A)是A的幂集，是对称差运算，可以验证是群。设n是正整数，求({a}-1{b}{a})n{a}-n{b}n{a}n 28.(6分)设A={1,2,3,4,5},A上偏序关系

R={〈1，2〉，〈3，2〉，〈4，1〉，〈4，2〉，〈4，3〉，〈3，5〉，〈4，5〉}∪IA; (1)作出偏序关系R的哈斯图

(2)令B={1,2,3,5}，求B的最大，最小元，极大、极小元，上界，下确界，下界，下确界。 29.(6分)求┐(P→Q)(P→┐Q)的主合取范式并给出所有使命题为真的赋值。

30.(5分)设带权无向图G如下，求G的最小生成树T及T的权总和，要求写出解的过程。

31.(4分)求公式┐((x)F(x,y)→(y)G(x,y))∨(x)H(x)的前束范式。 四、证明题 (共20分)

32.(6分)设T是非平凡的无向树，T中度数最大的顶点有2个，它们的度数为k(k≥2),证明T中至少有2k-2片树叶。

33.(8分)设A是非空集合，F是所有从A到A的双射函数的集合，是函数复合运算。 证明：〈F, 〉是群。

34.(6分)在个体域D={a1,a2,…，an}中证明等价式： (x)(A(x)→B(x))(x)A(x)→(x)B(x)

五、应用题(共15分)

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

36.(6分)一次学术会议的理事会共有20个人参加，他们之间有的相互认识但有的相互不认识。但对任意两个人，他们各自认识的人的数目之和不小于20。问能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人?根据是什么?