第Ⅰ部分 选择题
一、单项选择题(在每小题列出的四个备选项中只有一个是符合题目要求的) 第Ⅱ部分 非选择题
二、填空题1. 设集合A={1,3,4}以及A上的一个二无关系R={〈1,3〉,〈3,4〉,〈3,3〉},则自反闭包r(R)=______,R
-1=______。
{〈1,1〉,〈1,3〉,〈3,4〉,〈3,3〉,〈4,4〉};{〈3,1〉,〈4,3〉,〈3,3〉}
2. 设A={1,2,3,4},B={1,2,4,5},A到B的关系R={〈2,4〉,〈1,1〉,〈4,2〉},B到A的关系S={〈4,1〉,〈1,4〉,〈2,3〉},则
{〈4,1〉,〈1,2〉}
[解析] R={〈2,4〉,〈1,1〉,〈4,2〉},S={〈4,1〉,〈1,4〉,〈2,3〉},则
。
3. 设A={3,2,4},B={2,5,3},则A
B=______,A-B=______。
4. 若连通平面图G有10条边,4个面,则G有______个顶点。
5. 设R={〈3,1〉,〈2,3〉,〈5,3〉,〈3,4〉}是集合A={1,2,3,4,5}上的关系,则domR=______,ranR=______。
6. 设集合A有3个元素,则A上的等价关系有______个。
7. 设A={2,4,6,12},a*b=gcd(a,b),即a、b的最大公约数。代数系统〈A,*〉的幺元是______,零元是______。
8. 命题公式﹁P∧Q∧﹁R的小项编码为______。
9. 一个具有10个顶点的简单连通无向图的边数至少为______,至多为______。
9;45
[解析] 连通图的必要条件是至少有n-1条边,即10-1=9;至多有
条边。
10. 设S(x):x是人,G(x):x会思考,则命题“人都会思考”可符号化为______。
三、计算题(每小题6分,共30分)1. 构造命题公式(P∨Q)→(Q∧R)的真值表。
P
|
Q
|
R
|
P∨Q
|
Q∧R
|
(P∨Q)→(Q∧R)
|
0 0 0 0 1 1 1 1
|
0 0 1 1 0 0 1 1
|
0 1 0 1 0 1 0 1
|
0 0 1 1 1 1 1 1
|
0 0 0 1 0 0 0 1
|
1 1 0 1 0 0 0 1
|
2. 利用等值演算法求命题公式(P∧(Q→R))→Q的主合取范式。
设,R为A上的包含关系。3. 画出R的哈斯图;
哈斯图:
4. 设B={{b},{a,b},{b,c}},求B的极大元、极小元、上界和下界。
B的极大元:{a,b},{b,c};
极小元:{b};
上界:{a,b,c};
下界:
设图G如下图所示。
5. 写出图G的邻接矩阵;
G的邻接矩阵
6. G中长为4的通路有几条?
G中长为4的通路有26条;
8. 设解释I如下:D={2,3},已知f(2)=3,f(3)=2,F(2)=0,F(3)=1,G(2,2)=G(2,3) =0,G(3,2)=G(3,3)=1。
求谓词公式
在I下的真值。
四、证明题(每小题7分,共21分)1. 设G是无向简单图,有2n个结点且每个结点度数均为n。证明:G是连通图。
证明:假设G不是连通图,设H是G的一个连通分支。
由于图G是简单图且每个结点的度数为n,
所以子图H与G-H也是简单图且每个结点的度数为n。
因此,H与G-H中的结点数均至少为n+1。
于是G的结点数大于等于2n+2,
这与G的结点数为2n矛盾。
因此假设为谬,所以G是连通图。
2. 设〈S,·〉是独异点,e是单位元,且S中任意x,有x·x=e。证明:〈S,·〉是交换群。
证明:由于〈S,·〉是独异点,e是单位元,且S中任意x,有x·x=e。
所以〈S,·〉是群,且每个元素的逆元等于它本身。
于是,对任意x,y∈S,有xy=x-1y-1=(yx)-1=yx。
所以,〈S,·〉是交换群。
3. 设A,B,C是集合。证明:A∩(B∪C)=(A∩B)∪(A∩C)。
证明:
(1)若x∈A∩(B∪C),则x∈A且x∈B∪C;
即x∈A且x∈B,或者x∈A且x∈C;
即x∈(A∩B)∪(A∩C);
所以
(2)若x∈(A∩B)∪(A∩C),则x∈A∩B或者x∈A∩C;
即x∈A且x∈B,或者x∈A且x∈C;
即x∈A且x∈B∪C;
即x∈A∩(B∪C);
所以
综合(1)与(2),因此A∩(B∪C)=(A∩B)∪(A∩C)。
五、综合应用题(每小题7分,共14分)1. 符号化下列命题,并构造推理证明。
中华牙防组委员会成员都是教授,并且是牙医;有些中华牙防组委员会成员是资深专家。所以,有的中华牙防组委员会成员是牙医,且是资深专家。
(1)符号化:设个体域为全总个体域。
M(x):x是中华牙防组委员会成员;
H(x):x是教授;
G(x):x是牙医;
R(x):x是资深专家。
(2)
(3)证明:
2. 用Kruskal算法求下图中的一棵最小生成树。要求写出详细过程,并画出该最小生成树。
解:根据Kruskal算法,
①取权为1的边e
1=(v
1,v
2);②取权为3的边e
2=(v
2,v
3);
③取权为4的边e
3=(v
3,v
4);④取权为4的边e
4=(v
3,v
5);
⑤取权为7的边e
5=(v
5,v
6);
最小生成树如下图所示。