一、单项选择题（每小题2分，共10分）
1、下列是假命题的语句是（ ）
A. x+y > 100 B. 如果西南财经大学坐落在成都，那么7是偶数
C. 2+2 ≠ 4当且仅当雪是黑的 D. 请努力学习
2、下列命题公式中不．是重言式的是（ ）
A. P®((R«Q)∨P) B. ((P∧Q)®R)«(P®(Q®R))
C. Q®(P∨Q∨R) D. (P∨R)®(P∧R∧Q)
3、“所有极大项的合取式”与“所有极小项的合取式”的析取运算结果为（ ）
A. 可满足式 B. 重言式 C. 矛盾式 D. 无法判定公式的类别
4、下列二元关系中满足传递性的是（ ）
A. 同学关系 B. 父子关系
C. 命题公式之间的重言蕴涵关系 D. 实数之间的不相等关系
5、关于图，下列说法不．正确的是（ ）
A. 图的邻接矩阵不一定是布尔矩阵。
B. 两个图同构当且仅当结点数目、边数及度数相同的结点数目相等。
C. 通路一定是迹，但迹不一定是通路。
D. 任何图中，结点度数的总和等于边数的 2 倍。二、填空题(每小题3分，共15分)
1、设 P：明天有课，Q：我去运动，R：我去图书馆，则命题“若明天没课，我就去运动， 否则在图书馆。”可符号化为： 。 2、设 S(x)：x 是学生；L(x,y)：x 喜欢 y；a：离散数学。“虽然有学生喜欢离散数学， 但是未必所有学生都喜欢离散数学。”这一命题可符号化为：
。
3、设 Q={a,b,c,d}，定义 Q 上的二元关系 R={
,,}，S={,,}，则 R2oS= ，(R-1)2= 。 4、请将“含有 4 个结点，3 条边的不．同构的简单图”画在下述横线上
。
0
1
5、设有向图 G=，V={v1,v2,v3,v4}，若 G 的邻接矩阵为𝐴𝐺 = (0
1
1 0 1
0 0 0)，则
1 1 1
0 0 0
deg-(v3)= ，deg+(v4) = 。
三、计算题（共30分）
1、（7 分）求命题公式 G(P, Q, R) = Ø(ØP®Q)∨(Q∧R)的主合取范式和主析取范式，求解结果用 mi 和 Mi 的编码形式表示。
2、（6 分）求谓词公式($x)(("y)($z)P(x, y, z)®($z)("t)(Q(x, z)∨R(x, t, z)))的前束范式， 其前束范式与原公式之间的关系满足什么性质？
3、（10 分）设由 4 个元素组成的集合 A={a, b, w+1, Æ}，定义 A 上的二元关系
R={, , , <Æ, a>}，
试解答以下问题：
（1）（4 分）求 r(R)与 s(R)。
（2）（6 分）分别用关系矩阵的运算和 Warshall 算法这两种方法来求 t(R)。
4、（7 分）设有向图 G=，V={v1,v2,v3,v4}，如下图所示，试解答以下问题：
（1）图 G 中长度为 3 的路总共有几条？其中回路有几条？
（2）图论中，哪类图的可达性矩阵一定是对称的？计算 G 的可达性矩阵，判断其是否是对称矩阵。
四、证明题（共45分）
1、（10 分）设 I 为整数集，定义 I 上的二元关系为
R＝{|x, y, kÎI 且 x-y 能被 k 整除}， 证明：R 为 I 上的等价关系。
2、（10 分）用命题逻辑推理方法证明下面推理的有效性：
明天下午或者是天晴，或者是下雨；仅当我去登山，明天下午才是天晴；只有我不学习， 我才去登山。因此，如果我在学习，则天在下雨。
3、（10 分）用谓词逻辑推理方法证明下面推理的有效性：
所有的年轻人或者喜爱下国际象棋或者喜爱弹钢琴；每一个喜爱下国际象棋的人都在学离散数学，但并非所有年轻人都在学离散数学。所以，有些年轻人是喜爱弹钢琴的。
2
4、（8 分）试问：下面整数列是否可图化？若可图化，请说明理由，并把相应的图画出来；若不能图化，请说明理由。
(1) (7, 5, 5, 4, 3); (2) (6, 6, 3, 3, 5)。
5、（7分）在关系理论中，为何需要研究闭包运算？计算传递闭包有哪些方法，在这些方法中，Warshall算法的优势是什么？在图论中，Warshall算法有怎样的应用？（可以结合叙述、举例等多种方式解答）
