A.〈Q，*〉Q是全体有理数集，*是数B.(?x)A(x)→B 的乘法运算 C.A(x)→B
离散数学试题
全国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.下列各代数系统中不含有零元素的
是( )
.. ..
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 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的幂集，?是对称差运算，可以验证 ({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个人排在圆桌旁，使得任意一个人认识其旁边的两个人?根据是什么? 答案： 一、单项选择题(本大题共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.陈述句 真值 三、计算题 ??1100?26. M=??1010???1011? ???0011????2110? M2=??2111???2121? ???1011??44 ?M2ij?18, 2ij?6 i?1?j?1?4Mi?1 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) 此F非空 e5=(v2,v3), e6=(v1,v2) (1)?f,g∈F,因为f和g都是A到 e7=(v1,v4), e8=(v4,v3) A的双射函数，故f?g也是A到A e9=(v3,v5), e10=(v5,v6) 的双射函数，从而集合F关于运算? 令ai为ei上的权，则 是封闭的。 a1 (3)A上的恒等函数IA也是A到A的 双射函数即IA∈F,且?f∈F有 T的总权和=1+2+3+4+5=15 IA?f=f?IA=f,故IA是〈F，?〉中的31.原式?┐(?x1F(x1,y)→ 幺元 ?y1G(x,y1))∨?x2H(x2) (换名) (4)?f∈F,因为f是双射函数，故 ?┐?x1?y1(F(x1,y)→其逆函数是存在的，也是A到A的 G(x,y1))∨?x2H(x2) 双射函数，且有f?f-1=f -1 ?f=IA, ??x1?y1┐(F(x1,y1)→因此f-1 是f的逆元 G(x,y1))∨?x2H(x2) 由此上知〈F，?〉是群 ??x1?y1?x2(┐(F(x1,y1)→34.证明(?x)(A(x)→B(x)) ? G(x,y1))∨H(x2) ?x(┐A(x)∨B(x)) 四、证明题 ?(┐A(a1)∨B(a1))∨(┐A(a2)∨32.设T中有x片树叶，y个分支点。B(a2))∨…∨(┐A(an)∨B(an))) 于是T中有x+y个顶点，有x+y-1 条 ?(┐A(a1)∨A(a2)∨…∨┐A(an)边，由握手定理知T中所有顶点的∨(B(a1)∨B(a2)∨…∨(B(an)) 度数之的 ?┐(A(a1)∧A(a2)∧…∧A(an))∨x?y(┐B(a1)∨B(a2)∨…∨(B(an)) ?d(vi)=2(x+y-1)。 ?┐(?x)A(x)∨(?x)B(x) ? i?1(?x)A(x)→(?x)B(x) 又树叶的度为1，任一分支点的度五、应用题 大于等于2 35.令p：他是计算机系本科生 且度最大的顶点必是分支点，于是 q：他是计算机系研究生 x r：他学过DELPHI语言 ??y d(vi)≥ s:他学过C++语言 i?1 t:他会编程序 x·1+2(y-2)+k+k=x+2y+2K-4 前提：(p∨q)→(r∧s),(r∨s) 从而2(x+y-1)≥x+2y+2k-4 →t x≥2k-2 结论：p→t 33.从定义出发证明：由于集合A是非 证 空的，故显然从A到A的双射函数 ①p P(附加前提) 总是存在的，如A上恒等函数，因 ②p∨q T①I
离散数学自学考试真题附答案打印版
