发布时间 : 2024/5/24 23:14:21 星期五 文章2002年4月至2011年7月历次自考离散数学试题汇总（打印版） - 图文更新完毕开始阅读7283236bb84ae45c3b358c9c

33．（6分）设n阶无向树G=中有m条边，证明m=n-1。 34．（8分）设P={?,{1},{1,2},{1,2,3}}，?是集合P上的包含关系。

（1）证明：是偏序集。

（2）在（1）的基础上证明是全序集

五、应用题（本大题共2小题，第35小题9分，第36小题6分，共15分） 35．（9分）在谓词逻辑中构造下面推理的证明：每个在学校读书的人都获得知识。所以如果没有人获得知识

就没有人在学校读书。（个体域：所有人的集合） 36．（6分）设有a,b,c,d,e,f,g等七个人，已知a会讲英语；b会讲英语、汉语；c会讲英、俄语；d会讲日、

汉语；e会讲德语、俄语；f会讲法语、日语；g会讲法语、德语。试用图论方法安排园桌座位，使每人都能与其身边的人交谈。

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

离散数学试题

课程代码：02324

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

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

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

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

3.公式(?x)(?y)(P(x,z)→Q(y))S(x,y)中的(?x)的辖域是( )。 A.(?y)(P(x,z)→Q(y)) B.P(x,z)→Q(y) C.P(x,z) D.S(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的幂集) B.{a}?p(A) C.{{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

17

8.设N是自然数集，R是实数集，函数f：Ｎ→R，f(n)=lgn是( )。 A.入射 B.满射 C.双射 D.非以上三种的一般函数

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

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

11.设S是自然数集，则下列运算中不满足交换律的是( )。 A.a*b=|a-b| B.a*b=ab C.a*b=max{a,b} D.a*b=min{a,b}

12.设图G′=是图的生成子图，则必须( )。 A.V′=V B.V′≠V但E′=E C.E′=E D.E′≠E且V′≠V 13.设有向图G有5个结点，4条边，且有一条有向路经过每个结点一次，则图G满足的最大连通性是( )。 A.不连通 B.弱连通 C.单侧连通 D.强连通

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

A.G没有奇数度结点 B.G有1个奇数度结点 C.G有2个奇数度结点 D.G没有或有2个奇数度结点 二、填空题(每小题2分，共30分)

1.设P：a2+b2=a2,Q:b=0,则PQ意思是说______. 2.合式公式┐(Q→P)∧P是永______式.

3.合式公式(PQ)∧(QR)与PR的关系是______.(等价或蕴含选一) 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).

18

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至少有两片树叶。

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

离散数学试题 课程代码：02324

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

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

1.下列各图是平面图的是( )

2.设G是n个顶点的无向简单图，则下列说法不正确的是 ) ．A.若G是树，则其边数等于n-1 B.若G是欧拉图，则G中必有割边

C.若G中有欧拉路，则G是连通图，且有零个或两个奇度数顶点

D.若G中任意一对顶点的度数之和大于等于n-1，则G中有汉密尔顿路 3.格L是分配格的充要条件是L不含与下面哪一个选项同构的子格( ) ．．A.链 C.五角格

B.钻石格

D.五角格与钻石格

19

4.设是有限循环群，则下列说法不正确的是( ) ．

A.的生成元是唯一的

B.有限循环群中的运算*适合交换律

C.G中存在一元素a，使G中任一元素都由a的幂组成

D.设a是的生成元，则对任一正整数i，存在正整数j使a-i=aj 5.在实数集合R上，下列定义的运算中是可结合的只有( ) A.a*b=a+2b B.a*b=a+b-2ab C.a*b=a-b+2ab D.a*b=a-b-2ab

6.设群G=中,A的元素个数大于1，若元素a∈A的逆元素为b∈A，则a*b的运算结果是( ) A.a B.b C.G中零元素 D.G中幺元

7.非空集合A上的二元关系R若是自反和对称的，则R是( ) A.偏序关系 B.等价关系 C.相容关系 D.拟序关系

8.下面的图是A=｛1,2,3｝上关系R的关系图G(R),从G(R)可判断R所具有的性质是( )

1。

2。 3。

A.自反，对称，传递 B.反自反，非对称

C.反自反，对称，非传递

D.反自反，对称，反对称，传递 9.设A=｛1，2，3｝，B=｛a,b｝，下列二元关系R为A到B的函数的是( ) A.R=｛<1,a>,<2,a>,<3,a>｝ B.R=｛<1,a>,<2,b>｝

C.R=｛<1,a>,<1,b>,<2,a>,<3,a>｝ D.R=｛<1,b>,<2,a>,<3,b>,<1,a>｝

10.设φ为空集，P(x)是集合x的幂集，下列论断不．正确的是( ) A. φ∈P(φ), φ?P(φ) B.{φ}∈P（φ），{φ}?P（φ） C. φ∈P（P（φ）），φ?P（P（φ）） D.{φ}∈P（P（φ））,{φ}?P（P（φ））

11.利用谓词的约束变元改名规则和自由变元代入规则，可将如下公式： (?x)(p(x,y)?(?z)Q(x,z))?(?y)R(x,y)改写成( )

A. (?z)(p(z,y)?(?y)Q(z,y))?(?s)R(z,s) B. (?z)(p(z,y)?(?s)Q(x,s))?(?y)R(z,y) C. (?x)(p(x,m)?(?y)Q(x,y))?(?m)R(m,m) D. (?x)(p(y,y)?(?y)Q(x,y))?(?s)R(y,s)

12.设论域为整数集，下列谓词公式中真值为假的是( ) A.(?x)(?y)(x?y?0)

20