2002年4月至2011年7月历次自考离散数学试题汇总（打印版） - 图文

全国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):x

1

A.( ? 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;

2

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

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

离散数学试题参考答案

课程代码：02324

一、单项选择题(本大题共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 1 17.1 0

18.单位元 1

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)

3

24.可满足式 永假式(或矛盾式) 25.陈述句 真值 三、计算题 ?1?1?26. M=??1??0100001110??2?0??2?2? M=?1??2?1???1ij?6 ?M2i?14111011210?1??? 1?1??

??i?1j?144M2ij?18,

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 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)

4

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 又树叶的度为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))

?(┐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))

5

二、填空题(本大题共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)成立。

11

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个英文字母。有的文盲是很聪明的。所以有的很聪明的人不会操作计算机。(个体域：所有人的集合)

浙江省2003年7月高等教育自学考试

离散数学试题

课程代码：02324

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

每小题1分，共14分) 1.给定如下4个语句:

(1)我不会游泳。 (2)如果天不下雨,我就去踢足球。 (3)我每天都看新闻联播。 (4)火星上有人吗? 其中不是复合命题的是( )。 A.(1)(4) B.(1)(3)(4) C.(1)(3) D.(3)(4)

2.设P,Q,R是命题公式,则P→R，Q→R，P∨Q?( )。 A. P B. Q C. R D. ┐R

3.下列公式中正确的等价式是( )。 A. ┐(?x)A(x)?(?x)┐A(x) B. ┐(?x)A(x)?(?x)┐A(x)

C. (?x)(?y)A(x,y)?(?y)(?x)A(x,y)

D. (?x)(?(x)∧B(x))?(?x)A(x)∨(?x)B(x)

4.谓词公式(?x)(P(x)∨(?y)R(y))→Q(x)中的x( )。 A.只是约束变元 B.只是自由变元

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

5.设个体域为整数集,则下列公式中值为真的是( )。 A. (?y)(?x)(x·y=2) B. (?x)(?y)(x·y=2) C. (?x)(x·y=x)

D. (?x)( ?y)(x+y=2y)

6.设A={a,b,c},则A中的双射共有( )。 A.3个 B.6个 C.8个 D.9个

7.设S={a,b,c},则S的幂集的元素的个数有( )。 A.3个 B.6个

12

C.8个 D.9个

8.设A={a,b,c},则A×A中的元素有( )。 A.3个 B.6个 C.8个 D.9个

9.设(G,+,*)是一个除环,则它不满足的运算律是( )。 A.加法交换律 B.乘法交换律 C.乘法消去律 D.加法消去律

10.对于一个代数系统,以下命题成立的是( )。 A.每个元素必有左逆元

B.一个元素有左逆元,则它也是右逆元 C.一个元素的左右逆元不一定相等 D.一个元素的左逆元存在时必唯一

11.若一个代数系统(A,*)满足运算封闭性及结合律,且有幺元,则它是( )。 A.独异点 B.群

C.格 D.布尔代数

12.在有3个结点的图中,奇结点的个数为( )。 A.0 B.1

C.1或3 D.0或2

13.设图G=的结点集为V={v1,v2,v3},边集为E={,}.则G的割集是( )。 A.{v1} B.{v2} C.{v3} D.{v2,v3}

14.若图G有一条路经过图中每个结点恰好一次,则G( )。 A.有一条欧拉路 B.是欧拉图 C.有一条汉密尔顿路 D.是汉密尔顿图 二、填空题(每小题2分，共30分)

1.设P:你陪伴我;Q:你代我叫车子;R:我出去.则命题“如果你不陪伴我或不代我叫车子,我就不出去.”的符号化形式为_______。

2.合式公式(P∨┐P)→((Q∧┐Q)∧R)是永_______式。 3.合式公式Q→(P∨(P∧Q))与Q→P的关系是_______。（等价或蕴含选一） 4.设P(x)：x非常聪明；Q(x):x非常能干；a：小李；则命题“小李非常聪明和能干”的为谓词表达式为_______。 5.公式A→(?x)B(x)的前束范式为_______。

6.设论域为集合{a,b,c}，则(?x)P(x)∨(?x)Q(x)?_______。 7.集合A上的关系“?”称为偏序关系，如果?满足_______。 8.设A={a,b,c}，B={a,b,c,d},则A?B=_______。

9.集合A={a,b,c}上的关系R={,,}的对称闭包为_______。

10.设A={1,2}，A上的二元运算定义为x*y=min{x,y}，则*的运算表为_______。

11.设A={2,3,6,12}，A上的序关系“?”定义为：x?y当且仅当x整除y.令B={2,3,6}，则B的最小上界是_______，B的极小元是______。 12.整数加群的单位元是_______。

?101???13.设图G的邻接矩阵为?010?，则从结点v1到v3的长度为2的路径数为。

??101??14.若一个连通图G有5个结点，连接每两个结点有一条边，则G一定 平面图。（是或不是选一）

13

15.一颗完全二叉树的高为3，则它至少有_______片树叶，至多有 片树叶。 三、计算题(每小题6分,共24分)

1.求公式A=P∧Q∨R的主合取范式。

2.设集合A{a,b,c,d}，B={1,2,3},C={x,y},A到B的关系为R={,,,},B到C的关系为S={<1,x>,<3,y>}.用矩阵求从A到C的合成关系R?S.

3.设G={a,b}，定义G上的一个二元运算*使(G,*)构成一个群，并验证你的结论。 4.给定一棵树（如图），试分别用中序行遍法、前序行遍法和后序行遍法写出运算表达式。

四、证明题(每小题8分,共32分) 1.用推理规则证明以下蕴含式

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

(?x)(M(x)→D(x)),(?x)(S(x)∧M(x))?(?x)(D(x)∧S(x))

3.设正整数的序偶集合为A，在A上定义二元关系R如下：<,>∈R当且仅当xv=yu.R是A上的一个关系。

4.试证：群(G，*)的两个子群(H1，*),(H2，*)的交H1I H2对一于*还是G的一个子群。

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

离散数学试题

课程代码：02324

第一部分 选择题 （共15分）

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

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

1．下列是两个命题变元p，q的小项是（ ） A．p∧┐p∧q B．┐p∨q C．┐p∧q D．┐p∨p∨q

2．令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ ） A．p→┐q B．p∨┐q C．p∧q D．p∧┐q 3．下列语句中是命题的只有（ ） A．1+1=10 B．x+y=10 C．sinx+siny<0 D．x mod 3=2 4．下列等值式不正确的是（ ） A．┐(?x)A?(?x)┐A

B．(?x)(B→A(x))?B→(?x)A(x)

14

C．(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x)

D．(?x)(?y)(A(x)→B(y))?(?x)A(x)→(?y)B(y)

5．谓词公式(?x)P(x,y)∧(?x)(Q(x,z)→(?x)(?y)R(x,y,z)中量词?x的辖域是（ ） A．(?x)Q(x,z)→(?x)(?y)R(x,y,z)) B．Q(x,z)→(?y)R(x,y,z)

C．Q(x,z)→(?x)(?y)R(x,y,z) D．Q(x,z)

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

7．设A={a,b,c,d}，A上的等价关系R={,,,}∪IA，则对应于R的A的划分是（ ） A．{{a},{b,c},{d}} B．{{a,b},{c},{d}} C．{{a},{b},{c},{d}} D．{{a,b},{c,d}} 8．设A={?}，B=P(P(A))，以下正确的式子是（ ） A．{?,{?}}∈B B．{{?,?}}∈B C．{{?},{{?}}}∈B D．{?,{{?}}}∈B

9．设X，Y，Z是集合，一是集合相对补运算，下列等式不正确的是（ ） A．(X-Y)-Z=X-(Y∩Z) B．(X-Y)-Z=(X-Z)-Y C．(X-Y)-Z=(X-Z)-(Y-Z) D．(X-Y)-Z=X-(Y∪Z)

10．设*是集合A上的二元运算，称Z是A上关于运算*的零元，若（ ） A．?x?A,有x*Z=Z*x=Z

B．Z?A，且?x?A有x*Z=Z*x=Z C．Z?A，且?x?A有x*Z=Z*x=x D．Z?A，且?x?A有x*Z=Z*x=Z

11．在自然数集N上，下列定义的运算中不可结合的只有（ ） A．a*b=min(a,b) B．a*b=a+b

C．a*b=GCD(a,b)(a,b的最大公约数) D．a*b=a(mod b)

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

算构成该群的子群的是（ ） A．{R+中的有理数} B．{R+中的无理数} C．{R+中的自然数} D．{1，2，3} 13．设是环，则下列正确的是（ ） A．是交换群 B．是加法群 C．?对*是可分配的 D．*对?是可分配的 14．下列各图不是欧拉图的是（ ）

15

本文来源：https://www.bwwdw.com/article/vv75.html