2004—2005学年第1学期试卷。
一、判断题：（10分，在括号内划“√”或“×”
）1．“如果太阳从西边出来，则2+2=4”，此命题值为假。
）2．(1,3,3,3)可以成为无向简单图的度数序列。
）4．（pq）（pq）是永真式。
）5．在某集合上二元运算中，若某元素存在左右逆元，则该元素逆元唯一。
）6．命题公式的主析取范式为0，则其主合取范式为1。
）7．有向图的关联矩阵中所有元素之和为该图度之和 。
）8．初级回路一定是简单回路。
）9．若关系r具有自反性，则一定不具有反自反性。
）10．x(a(x) yh(x,y))在具体的解释中其值是确定的。
二、填空（共30分）
1． 设a=，p(a)表示a的幂集，,则p(a) a
2． 在一阶逻辑中符号化命题：“所有的人都是要死的”（只能用存在量词。
3． p(x) y r(x,y)的前束范式是。
4. n阶有向完全图中所有顶点的度数之和为。
6. 设函数f(x)=2x + 1,g(x)= x2-2,则f o g
9．若|p(a∪b)|=256，|p(a)|=64，| b |=3，则|ab
三、（6分）设a、b、c为任意集合，证明：
((a∪b∪c)∩(a∪b)) a∪(bc))∩a) =ba
4、（8分）求（p∧q） r的主合取范式、主析取范式以及成假赋值。
六、（8分）在一阶逻辑自然推理系统中，构造下面推理的证明。个体域是人的集合。
“每个喜欢步行的人都不喜欢坐汽车，每个人或者喜欢坐汽车或者喜欢骑自行车，有的人不喜欢骑自行车。因而有的人不喜欢步行。”
七、（10分）设集合a= 上的二元关系r1与r2定义如下：
r1=，r2=，1) 写出r1的关系矩阵，并判断r1具有哪些性质？
2) 求出r1ｏr2
3) 画出t(r2)的关系图。
八、（10分）已知a和a上的偏序关系r，设a = r = ia 。
1) 画出此偏序集的哈斯图。
2) 找出最大元与最小元。
九、（10分）若d是具有结点v1,v2,v3,v4的有向图，它的邻接矩阵表示如下：
1) 画出这个图；
2) d是单向连通还是强连通？说明理由。
3) 该图是否存在欧拉通路？说明理由。
4) 求该图中长度小于等于3的通路与回路总数。
一、填空（每空1分）
1.的对偶式。
2.的主析取范式 。
3. 将下列式子的否定联结词从量词前移到量词后，
4. 把公式转化为前束范式。
7. 1到250之间能被2，3，5和7任何一个整除的整数的个数。
8.，,9.,上的关系 ，domran
10. ，为，则。
二、选择题（每题2分， 请将答案写在下面的**中，否则不得分）
1) 下列命题中真值为t的有 。
a. 若2+2=4，则3+36 b. 2+2=4当且仅当3+36
c. 若2+2=4，则3+3=6 d.2+24当且仅当3+3=6
2) 下面命题公式（ ）是重言式。
a. p→q∨r b. (p∨r)∧(p→q) c. (p∨r)(q∨r) d.(p→(q→r))→p→q)→(p→r))
3) 下面蕴含关系成立的是（ ）
x)p(x)∧(x)q(x)(x)(p(x)∨q(x))
x)p(x)→(x)q(x)(x)(p(x)→q(x))
x)p(x)→(x)q(x)(x)(p(x)→q(x))
x)(y)a(x,y)(y)(x)a(x,y)
a. b. c. d. 上述蕴含关系均不成立。
4) 1—100中，有( )个数不能被2，3，5中的任何一个整除。
a. 26 b. 27 c. 28 d. 以上答案均不正确。
5) 集合a上的恒等关系具备的性质是（ ）
a. 自反、对称、传递b. 什么性质也没有。
c. 反自反、反对称、传递 d. 自反、对称、反对称、传递。
6) 设，下列各式中（ ）是正确的。
a. domsb b. domsa c. ransa d. domsrans = s。
(7) 设r为集合a上的相容关系，其简化关系图（如图），则 a的最大相容类为（ ）
a. b. ,
c. ,d. ,
8) 下列关系中能构成函数的是（ ）
a. b.
c. d.
9) 下列命题正确的有（ ）
若g,f是满射，则gf是满射； 若gf是满射，则g, f都是满射；
若gf是单射，则g,f都是单射； 若gf单射，则f是单射。
a. b. c. d.
10) 集合之间的等势关系是一个( )关系。
a. 反对称 b. 等价 c. 反自反 d. 偏序。
证明：(s∧q)→r, ┐r∨p, ┐ps→┐q
2． (10分) 请证明下面的推理是有效的，要求步骤规范完整。
每个学生或是勤奋的或是聪明的，所有勤奋的人都会有所作为，并非每个学生都有所作为，所以有些学生是聪明的。(s(x)：x是学生，q(x) ：
x是勤奋的，i(x)：是聪明的，l(x)：是有所作为的)。
证明：ab a∩b=a。
4. (10分) 设s, r是集合a上的等价关系，试证明：rs是集合a上的等价关系。
5．(12分) 设s=，“为s上整除关系，1) 写出的所有元素、cov s，画出偏序集的hasse图；
2) 偏序集的极小元、最小元、极大元、最大元是什么？
3) 偏序集中s的上确界、下确界？
6．(10分) 设a=，给定a上的两个关系r和l分别是r=，l=
1) 写出r和l的关系矩阵。
2) 求rl及其自反、对称和传递闭包( warshall算法)。（计算闭包要求写出详细步骤）
离散试题练习
1.求下列各公式的主析取范式和主合取范式 p q r pr qr p 2.证明 p q，qr，r，sp s a b c c de f de a b fpq，p r,q s rs 3.设a 下列哪个是a的划分？若是划分，则它们诱导的等价关系是什么？1 b 2 c 3 d 是a 上的等价关系，r ia求...
2019离散试题A
河北科技大学2013 2014 学年第1学期。离散数学 考试试卷。考场号座位号学院。班级姓名学号。一 单项选择题 本题共10小题，每小题2分，共20分 1 下列偏序集中哪个是格。2 下列蕴含式错误的是。a p pqb.ppq c pp q d.pqp 3 若一条路中所有的结点v0,v1,vn均不相同...
离散复习试题
一 选择题。1 下面命题公式不是重言式。ab cd 2 命题 没有不犯错误的人 符号化为。设是人，犯错误。ab c d 3 设a 下列各式中 是错的。ab a c ad a 4 给定下列序列可以构成无向简单图的结点次数序列。a 1，1，2，2，3 b 1，1，2，2，2 c 0，1，3，3，3 d ...