一、填空题（每小题 2 分，合计 20 分）
1、合式公式 的为真的赋值有 。 (q p) p
2、谓词公式(x)(P(x, y) Q(x, y)) P( y, x) ，则其约束变元是______，自由变元是
______。
3、设 A {1,2,3,4}， B {2,4,6}，则 A B =________， A B =________。
4、公式 的主合取范式为 。 (P R) (S R) P
5、设 f : R R, f (x) x 3 ，g : R R,g(x) 2x 1，则复合函数( f g)(x)
，(g f )(x) __________________ 。
6、设 A {2,3,6,12}， 是 A 上的整除关系，则偏序集 A, 的最大元是________，
极小元是________。
7、设e 是群G 上的幺元，若 aG 且 a
2 e ,则 a
1
=____， a
2
=__________。
8、 设 <G,*>是 由 元 素 a G 生 成 的 循 环 群 ， 且 |G|=n， 则
G= 。
9、一棵有 6 个叶结点的完全二叉树，有_____个内点；而若一棵树有 2 个结点度数为
2，一个结点度数为 3，3 个结点度数为 4，其余是叶结点，则该树有_____个叶结点。
10、无向图 Km,n是一个完全二部图，当且仅当满足 时，G 是一个欧
拉图。当满足 时，Km,n是一个汉密尔顿图。
二、选择题（每小题 2 分，合计 20 分）
1、下列语句中为命题的是（ ）。
A．这朵花是谁的？ B．这朵花真美丽啊！
C．这朵花是你的吗？ D．这朵花是他的。
2、设 p ：天下大雨， q ：他在室内运动，命题“除非天下大雨，否则他不在室内运动”
可符号化为（ ）。
A．p q B．p q C．p q D． p q
3、下列命题公式为重言式的是（ ）。
A． q ( p q) B． p ( p q) C．( p q) p D．( p q) q
4、下列是两个命题变元 p，q 的极大项是（ ）。
A． p q q B．p q C．p q D．p p q
5、设 M (x) ： x 是人； F(x)： x 要吃饭。用谓词公式表达下述命题：所有的人都要吃
饭，其中错误的表达式是（ ）。
A．(x)(M (x) F(x)) B．(x)(M (x) F(x))
C．(x)(M (x) F(x)) D．(x)(M (x) F(x))
6、集合的以下运算律不成立的是（ ）。
A． A B B A B． A B B A C． A B B A D． A B B A
7、设无向图中有 6 条边，有一个 3 度顶点和一个 5 度顶点，其余顶点度为 2，则该图
的顶点数是（ ）。
A．3 B．4 C．5 D．6
8、设 A {a,b,c,d}， A 上的等价关系 R { a,b , b,a , c,d , d,c }，则对
应于 R 的 A 的划分是（ ）。
A．{{a},{b,c},{d}} B．{{a,b},{c},{d}}
C．{{a},{b},{c},{d}} D．{{a,b},{c,d}}
9、 设 集 合 ， 是 上 的 二 元 关 系 ， X {0,1,2,3} R X
R { 0,0 , 0,2 ,1,2 ,1,3 , 2,0 , 2,1 , 3,3 }，则 R 的关系矩阵 MR是
（ ）。
A． B． C． D．
0 0 1 1
0 0 0 1
1 1 0 0
1 0 1 0
0 0 0 1
1 1 0 0
0 0 1 1
1 0 1 0
1 1 1 0
0 1 0 1
1 0 1 0
0 0 0 1
1 0 1 0
0 0 0 1
0 0 1 1
1 1 1 0
10、连通图 G 是一棵树，当且仅当 G 中（ ）。
A．有些边不是割边 B．每条边都是割边 C．无割边集 D．每条边都不是割边
三、计算题（每小题 10 分，合计 40 分）
1、构造命题公式( p q) (p q)的真值表。
2、求公式( p q) (q r) 的主析取范式。
3、设 A {1,2,3,4}， A 上的等价关系 R {1, 2 , 2,1 , 3, 4 , 4,3 } I A
，画
出 R 的关系矩阵，并求出 A 中各元素的等价类。
4、求下图的一颗最小生成树。
四、证明题（每小题 10 分，合计 20 分）
1、用谓词逻辑符号化以下命题，并推证结论的有效性。
“任何人如果他喜欢美术，他就不喜欢体育。每个人或喜欢体育，或喜欢音乐，有的人
不喜欢音乐，因而有的人不喜欢美术。”
2、设 R 是集合 A 上的二元关系，如果对于任意的 a, b, c∈A，若 aRb 且 bRc，则有 cRa，
那么称 R 是循环的。
证明：R 是等价关系当且仅当 R 是自反的和循环的。
1、合式公式 的为真的赋值有 。 (q p) p
2、谓词公式(x)(P(x, y) Q(x, y)) P( y, x) ，则其约束变元是______，自由变元是
______。
3、设 A {1,2,3,4}， B {2,4,6}，则 A B =________， A B =________。
4、公式 的主合取范式为 。 (P R) (S R) P
5、设 f : R R, f (x) x 3 ，g : R R,g(x) 2x 1，则复合函数( f g)(x)
，(g f )(x) __________________ 。
6、设 A {2,3,6,12}， 是 A 上的整除关系，则偏序集 A, 的最大元是________，
极小元是________。
7、设e 是群G 上的幺元，若 aG 且 a
2 e ,则 a
1
=____， a
2
=__________。
8、 设 <G,*>是 由 元 素 a G 生 成 的 循 环 群 ， 且 |G|=n， 则
G= 。
9、一棵有 6 个叶结点的完全二叉树，有_____个内点；而若一棵树有 2 个结点度数为
2，一个结点度数为 3，3 个结点度数为 4，其余是叶结点，则该树有_____个叶结点。
10、无向图 Km,n是一个完全二部图，当且仅当满足 时，G 是一个欧
拉图。当满足 时，Km,n是一个汉密尔顿图。
二、选择题（每小题 2 分，合计 20 分）
1、下列语句中为命题的是（ ）。
A．这朵花是谁的？ B．这朵花真美丽啊！
C．这朵花是你的吗？ D．这朵花是他的。
2、设 p ：天下大雨， q ：他在室内运动，命题“除非天下大雨，否则他不在室内运动”
可符号化为（ ）。
A．p q B．p q C．p q D． p q
3、下列命题公式为重言式的是（ ）。
A． q ( p q) B． p ( p q) C．( p q) p D．( p q) q
4、下列是两个命题变元 p，q 的极大项是（ ）。
A． p q q B．p q C．p q D．p p q
5、设 M (x) ： x 是人； F(x)： x 要吃饭。用谓词公式表达下述命题：所有的人都要吃
饭，其中错误的表达式是（ ）。
A．(x)(M (x) F(x)) B．(x)(M (x) F(x))
C．(x)(M (x) F(x)) D．(x)(M (x) F(x))
6、集合的以下运算律不成立的是（ ）。
A． A B B A B． A B B A C． A B B A D． A B B A
7、设无向图中有 6 条边，有一个 3 度顶点和一个 5 度顶点，其余顶点度为 2，则该图
的顶点数是（ ）。
A．3 B．4 C．5 D．6
8、设 A {a,b,c,d}， A 上的等价关系 R { a,b , b,a , c,d , d,c }，则对
应于 R 的 A 的划分是（ ）。
A．{{a},{b,c},{d}} B．{{a,b},{c},{d}}
C．{{a},{b},{c},{d}} D．{{a,b},{c,d}}
9、 设 集 合 ， 是 上 的 二 元 关 系 ， X {0,1,2,3} R X
R { 0,0 , 0,2 ,1,2 ,1,3 , 2,0 , 2,1 , 3,3 }，则 R 的关系矩阵 MR是
（ ）。
A． B． C． D．
0 0 1 1
0 0 0 1
1 1 0 0
1 0 1 0
0 0 0 1
1 1 0 0
0 0 1 1
1 0 1 0
1 1 1 0
0 1 0 1
1 0 1 0
0 0 0 1
1 0 1 0
0 0 0 1
0 0 1 1
1 1 1 0
10、连通图 G 是一棵树，当且仅当 G 中（ ）。
A．有些边不是割边 B．每条边都是割边 C．无割边集 D．每条边都不是割边
三、计算题（每小题 10 分，合计 40 分）
1、构造命题公式( p q) (p q)的真值表。
2、求公式( p q) (q r) 的主析取范式。
3、设 A {1,2,3,4}， A 上的等价关系 R {1, 2 , 2,1 , 3, 4 , 4,3 } I A
，画
出 R 的关系矩阵，并求出 A 中各元素的等价类。
4、求下图的一颗最小生成树。
四、证明题（每小题 10 分，合计 20 分）
1、用谓词逻辑符号化以下命题，并推证结论的有效性。
“任何人如果他喜欢美术，他就不喜欢体育。每个人或喜欢体育，或喜欢音乐，有的人
不喜欢音乐，因而有的人不喜欢美术。”
2、设 R 是集合 A 上的二元关系，如果对于任意的 a, b, c∈A，若 aRb 且 bRc，则有 cRa，
那么称 R 是循环的。
证明：R 是等价关系当且仅当 R 是自反的和循环的。
