一、单项选择题(本大题共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是整数集，定义为xxy=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.{}∈
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的幂集，是对称差运算，可以验证<P(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;
(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.陈述句 真值
三、计算题
26. M=
M2=
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的哈斯图为
发布评论