2010年7月自考离散数学试题及答案

第一篇：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月自学考试离散数学试题

第三篇：离散数学试题+答案

www.xiexiebang.com 专注于收集各类历年试卷和答案

一、单项选择题(本大题共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):x

www.xiexiebang.com 专注于收集各类历年试卷和答案

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;

www.xiexiebang.com 专注于收集各类历年试卷和答案

(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个人排在圆桌旁，使得任意一个人认识其旁边的两个人?根据是什么?

参考答案

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

1.B

2.D

3.A

4.A

5.D

6.D

7.D

8.C

9.D

10.B

11.A

12.A

13.C

14.B

15.C

二、填空题 16.0 17.1

0 18.单位元

19.x∩y

x∪y 20.入射

满射

21.［x］R=［y］R

 22.A(x)

B(y)23.(M(x)→D(x))

M(x)→D(x)

www.xiexiebang.com 专注于收集各类历年试卷和答案

24.可满足式

永假式(或矛盾式)25.陈述句

真值

三、计算题

1100101026.M=

1011001122M=21110111

121011M2ij18,ij6 M2i1i1j144

G中长度为2的路总数为18，长度为2的回路总数为6。

27.当n是偶数时，x∈P(A),xn=

当n是奇数时，x∈P(A),xn=x

于是：当n是偶数，(｛a｝-1｛b｝｛a｝)n｛a｝-n｛b｝n｛a｝n

=(｛a｝-1)n｛b｝n｛a｝n=

当n是奇数时，(｛a｝-1｛b｝｛a｝)n｛a｝-n｛b｝n｛a｝n

=｛a｝-1｛b｝｛a｝(｛a｝-1)n｛b｝n｛a｝n

=｛a｝-1｛b｝｛a｝｛a｝-1｛b｝｛a｝= 28.(1)偏序关系R的哈斯图为

(2)B的最大元：无，最小元：无；

极大元：2，5，极小元：1，3

下界：4，下确界4；

上界：无，上确界：无

29.原式(┐(P→Q)→(P→┐Q))∧((P→┐Q)→┐(P→Q))

((P→Q)∨(P→┐Q))∧(┐(P→┐Q)∨┐(P→Q))

(┐P∨Q∨┐P∨┐Q)∧(┐(┐P∨┐Q)∨(P∧┐Q))

(┐(P∧┐Q)∨(P∧┐Q))

(P∧Q)∨(P∧┐Q)

P∧(Q∨┐Q)

P∨(Q∧┐Q)

(P∨Q)∧(P∨┐Q)

命题为真的赋值是P=1,Q=0和P=1,Q=1

www.xiexiebang.com 专注于收集各类历年试卷和答案

30.令e1=(v1,v3)，e2=(v4,v6)

e3=(v2,v5)，e4=(v3,v6)

e5=(v2,v3)，e6=(v1,v2)

e7=(v1,v4)，e8=(v4,v3)

e9=(v3,v5)，e10=(v5,v6)

令ai为ei上的权，则

a1

取a1的e1∈T,a2的e2∈T,a3的e3∈T,a4的e4∈T,a5的e5∈T,即，T的总权和=1+2+3+4+5=15 31.原式┐(x1F(x1,y)→y1G(x,y1))∨x2H(x2)

(换名)

┐x1y1(F(x1,y)→G(x,y1))∨x2H(x2)

x1y1┐(F(x1,y1)→G(x,y1))∨x2H(x2)

x1y1x2(┐(F(x1,y1)→G(x,y1))∨H(x2)

四、证明题

32.设T中有x片树叶，y个分支点。于是T中有x+y个顶点，有x+y-1 条边，由握手定理知T中所有顶点的度数之的

xy

d(vi)=2(x+y-1)。

i又树叶的度为1，任一分支点的度大于等于2

且度最大的顶点必是分支点，于是

xy

d(vi)≥x·1+2(y-2)+k+k=x+2y+2K-4 i1

从而2(x+y-1)≥x+2y+2k-4

x≥2k-2 33.从定义出发证明：由于集合A是非空的，故显然从A到A的双射函数总是存在的，如A上恒等函数，因此F非空

(1)f,g∈F,因为f和g都是A到A的双射函数，故fg也是A到A的双射函数，从而集合F关于运算是封闭的。

(2)f,g,h∈F,由函数复合运算的结合律有f(gh)=(fg)h故运算是可结合的。

(3)A上的恒等函数IA也是A到A的双射函数即IA∈F,且f∈F有IAf=fIA=f,故IA是〈F，〉中的幺元

(4)f∈F,因为f是双射函数，故其逆函数是存在的，也是A到A的双射函数，且有ff-1=f-1f=IA,因此f-1是f的逆元

由此上知〈F，〉是群

34.证明(x)(A(x)→B(x)) x(┐A(x)∨B(x))

www.xiexiebang.com 专注于收集各类历年试卷和答案

(┐A(a1)∨B(a1))∨(┐A(a2)∨B(a2))∨„∨(┐A(an)∨B(an)))

(┐A(a1)∨A(a2)∨„∨┐A(an)∨(B(a1)∨B(a2)∨„∨(B(an))

┐(A(a1)∧A(a2)∧„∧A(an))∨(┐B(a1)∨B(a2)∨„∨(B(an))

┐(x)A(x)∨(x)B(x)(x)A(x)→(x)B(x)

五、应用题

35.令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 36.可以把这20个人排在圆桌旁，使得任一人认识其旁边的两个人。

根据：构造无向简单图G=,其中V={v1,v2,„，V20}是以20个人为顶点的集合，E中的边是若任两个人vi和vj相互认识则在vi与vj之间连一条边。

Vi∈V,d(vi)是与vi相互认识的人的数目，由题意知vi,vj∈V有d(vi)+d(vj)20,于是G中存在汉密尔顿回路。

设C=Vi1Vi2„Vi20Vi1是G中一条汉密尔顿回路，按这条回路的顺序按其排座位即符合要求。

第四篇：2006年7月全国自考离散数学试题试卷真题及答案（精选）

www.xiexiebang.com 专注于收集各类历年试卷和答案

2006年7月全国自考离散数学试题试卷真题

一、单项选择题（本大题共15小题，每小题1分，共15分）1．下列语句中不是命题的只有（）．A．鸡毛也能飞上天？ C．不经一事，不长一智。

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

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

A．永真式

B．永假式

C．永真式，永假式

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

3．设M（x）：x是人；F（x）：x要吃饭。用谓词公式表达下述命题：所有的人都要吃饭，其中错误的表．．达式是（）A．(x)(M(x)F(x))C．(x)(M(x)F(x))

B．(x)(M(x)F(x))D．(x)(M(x)F(x))

4．下列公式是前束范式的是（）A．(x)(y)(F(z,x)G(y))B．((x)F(x)(y)G(y))H(z)C．(x)F(x,y)(y)G(y)D．(x)(F(x,y)(y)G(x,y))5．设论域为整数集，下列真值为真的公式是（）A．(x)(y)(xy0)

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

6．下列是谓词演算中的合式公式的是（）

A．(x)(p(x)y)

B．(x)F(x)G(x,y)

C．(x)P(x,y)Q(y,z)

D．(x)xP(x,y)．（）A．B． C．D． ．（）

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

（）

B．A－（B∪C）=（A－B）∪C C．~（A－B）=~（B－A）D．~（A∩B）A 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．

B．是半群

+对*是可分配的 D．○11．下列四个格，是分配格的是（）

www.xiexiebang.com 专注于收集各类历年试卷和答案

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

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

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

A．大于

B．大于等于

C．等于

D．小于

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

B．n+r-e=2

C．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=____。

2-1-223．设e是群G上的幺元，若aG且a=e,则a=____ ,a=__________。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,m

（2）奇数个顶点，奇数条边

（3）偶数个顶点，奇数条边

（4）奇数个顶点，偶数条边

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

2)L={1,2,3,6,12}

www.xiexiebang.com 专注于收集各类历年试卷和答案

3)L={1,2,3,4,6,9,12,18,36}

4)L={1,2,2,2,„,2} 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是受过教育的人。

23n 3

www.xiexiebang.com 专注于收集各类历年试卷和答案

www.xiexiebang.com 专注于收集各类历年试卷和答案

www.xiexiebang.com 专注于收集各类历年试卷和答案

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

《离散数学》试题及答案

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

三、证明题（共30分）

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

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

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

四、解答题(共35分)

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

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

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

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

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

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

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

1.B2.C3.C4.A5.B

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

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

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

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

10.见

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

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

14.85 1 2 7 6

填对每个格得1分。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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