内容发布更新时间 : 2024/5/1 3:32:36星期一 下面是文章的全部内容请认真阅读。
全国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 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，若30.(5分)设带权无向图G如下，求G的〈x,y〉∈R，则 最小生成树T及T的权总和，要求写 〔x〕R与〔y〕R的关系是______，而若 出解的过程。 x,y〉R，则〔x〕R∩〔y〕R=______。 〈 个人，他们各自认识的人的数目之 和不小于20。问能否把这20个人排 在圆桌旁，使得任意一个人认识其 旁边的两个人 ?根据是什么? 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的幂集， 是对称差运算，可以验证 ({a-{a } 1{b}{a}) n } -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)的主 合取范式并给出所有使命题为真的赋值。 31.(4 分)求公式┐((x)F(x,y)→ x)H(x( y)G(x,y))∨( ) 的前束范 式。 四、证明题(共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 个人参加，他们之间有的相互认识但有的相互不认识。但对任意两 专业资料整理 答案： 一、单项选择题(本大题共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) 24.可满足式 永假式(或矛盾 式) 25.陈述句 真值 三、计算 题 1 1 0 0 1 0 1 0 26.M= 1 0 1 1 0 0 1 1 2 1 1 0 M2=2 1 1 1 2 1 2 1 1 0 1 1