华侨大学计算机学院09级离散数学(1)试卷B

班级 学号________ 姓名__________ 成绩

一、填空（ 共30分，每小题3分）

1、符号化命题，“老张不是中医”： 。

P?Q真值为0 当且仅当 。2、若P，Q，为二命题，

x?5}有 个元素，它们是 。3、集合{xx是正整数且 4、?xF(x)??(?xG(x))的前束范式为 。

5、集合A={1，2，3，4}上的偏序关系图为：

为 。

, 则它的Hass图

6、若关系R是偏序关系，则R满足性质 。 7、若集合A中有n个元素，则A中有 个不同的二元关系，其中 个是函数。

8、关系R是反对称的，当且仅当关系矩阵中 ，在关系图上 。

9、若g和f都是满射，则g?f是 ，若g和f都是单射，则g?f是 。

10、 集合A={a,b,c}上有 个不同的划分，每一个划分唯一对应一个等价关系，写出其中一个划分 ，其对应的等价关系 ：

二、运算题（共50分）

1. 设集合A={1,2,4}，B={2,3,4,6,8}，全集U={1,2,3,4,5,6,7,8}, 求下列集合：（12分）

(1) A ? B (2) A ? B (3)A - B

(4) A的补集 (5) A?B (6) ?(A)

2. 通过主合取范式，求出使公式?(?P?Q)?R的值为F的真值指派（8分）。

3. 设A?{x1,x2,x3,x4,x5}，偏序集?A,R?的Hass图为

求 ① A中最小元与最大元（2分）；

② {x3,x4,x5}的最大元和最小元，极大元和极小元，上界和上确界，下界

和下确界（8分）。

4. 200人中，有150人喜爱游泳或慢跑或同时喜爱二者。若85人喜爱游泳，60

人同时喜爱游泳或慢跑，问有多少人喜爱慢跑？（10分）。

5. 设集合A={ a ,b , c , d }上关系R={< a, b > , < b , a > , < b , c > , < c , d >}， （1）写出R的关系矩阵和关系图。（4分） （2）用矩阵运算求出R的传递闭包。（6分）

三、 证明题（共20分）

1. 用CP规则证明：(S?Q)?R,?R?P,?P?S??Q。(8分) 2. 设f：A→A，存在整数n使得fn=IA , 证明：f是双射函数。(7分) 3. 设R为集合A上的二元关系，如果R是反自反的和可传递的，则R一定是

反对称的。(5分)