-------------各类专业好文档，值得你下载，教育，管理，论文，制度，方案手册，应有尽有-------------- 全国2002年4月高等教育自学考试
离散数学试题
一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。
1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( B ) A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路
2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( D ) A.10 B.12 C.16 D.14
3.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( A ) 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 ) A.<{1},·> B.〈{-1},·〉 C.〈{i},·〉 D.〈{-i},·〉
5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交运算，下列系统中是代数系统的有( D )
A.〈Z，+，/〉 B.〈Z，/〉 C.〈Z，-，/〉 D.〈P(A)，∩〉 6.下列各代数系统中不含有零元素的是( D ) 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具有的性质是( D )
A.自反性 B.对称性 C.传递性 D.反自反性 8.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉〈,a,c〉}，则关系R的对称闭包S(R)是( C )
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应取( D ) A.｛〈c,a〉，〈a,c〉｝ B.{〈c,b〉，〈b,a〉} C.{〈c,a〉，〈b,a〉} D.{〈a,c〉，〈c,b〉} 10.下列式子正确的是( B )
A. ?∈? B.??? C.{?}?? D.{?}∈?
11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x 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 ) 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( C ) A.是自由变元但不是约束变元 B.既不是自由变元又不是约束变元 C.既是自由变元又是约束变元 D.是约束变元但不是自由变元 14.若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为( B ) A.P∨Q B.P∧┐Q C.P→┐Q D.P∨┐Q 15.以下命题公式中，为永假式的是( C ) A.p→(p∨q∨r) B.(p→┐p)→┐p C.┐(q→q)∧p D.┐(q∨┐p)→(p∧┐p) 二、填空题(每空1分，共20分) 16.在一棵根树中，仅有一个结点的入度为 0 ，称为树根，其余结点的入度均为 1 。 17.A={1,2,3,4}上二元关系R={〈2，4〉，〈3，3〉，〈4，2〉}，R的关系矩阵MR中 m24= 1 ,m34= 0 。 18.设〈s,*〉是群，则那么s中除 单位元 外，不可能有别的幂等元；若〈s,*〉有零元，则 |s|= 1 。 19.设A为集合，P(A)为A的幂集，则〈P(A)，?〉是格，若x,y∈P(A),则x,y最大下界是 x∩y ，最小上界是 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］R=［y］R，而若〈x,y〉?R，则〔x〕R∩〔y〕R=______。 22.使公式(?x)( ?y)(A(x)∧B(y))?(?x)A(x)∧(?y)B(y)成立的条件是 A(x) 不含有y， B(y) 不含有x。 23.设M(x):x是人，D(s):x是要死的，则命题“所有的人都是要死的”可符号化为(?x) (M(x)→D(x)) ,其中量词(?x)的辖域是M(x)→D(x) 。 24.若H1∧H2∧?∧Hn是 可满足式 ，则称H1,H2,?Hn是相容的，若H1∧H2∧?∧Hn是永假式(或矛盾式) ，则称H1,H2,?Hn是不相容的。 25.判断一个语句是否为命题，首先要看它是否为 陈述句 ，然后再看它是否具有唯一的 真值 。 三、计算题 (共30分) 26.(4分)设有向图G=(V,E)如下图所示，试用邻接矩阵方法求长度为2的路的总数和回路总数。 ?1100??1010???答：26. M=?? 1011????0011???2?2?2 M=??2??1110?111??? 121?011??M2ij?18, ij?6 ?M2i?14 ??i?1j?144-------------各类专业好文档，值得你下载，教育，管理，论文，制度，方案手册，应有尽有-------------- -------------各类专业好文档，值得你下载，教育，管理，论文，制度，方案手册，应有尽有-------------- G中长度为2的路总数为18，长度为2的回路总数为6。 27.(5)设A={a,b},P(A)是A的幂集，?是对称差运算，可以验证 (2)令B={1,2,3,5}，求B的最大，最小元，极大、极小元，上界，下确界，下界，下确界。 答：(1)偏序关系R的哈斯图为 (2)B的最大元：无，最小元：无； 极大元：2，5，极小元：1，3 下界：4， 下确界4； 上界：无，上确界：无 29.(6分)求┐(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)∨(P∧┐Q) P∧(Q∨┐Q) P∨(Q∧┐Q) (P∨Q)∧(P∨┐Q) 命题为真的赋值是P=1,Q=0和P=1,Q=1 30.(5分)设带权无向图G如下，求G的最小生成树T及T的权总和，要求写出解的过程。 答：令e1=(v1,v3), e2=(v4,v6) -------------各类专业好文档，值得你下载，教育，管理，论文，制度，方案手册，应有尽有--------------