广东海洋大学_2010-2011_1离散数学

一、将下列命题或谓词符号化（每题1分，共5分） 1、刘晓月跑得快，跳得高。

2、因为天气冷，所以我穿了羽绒服。 3、2＋2＝4的充要条件是3＋3≠6。 4、所有的人都长着黑头发。 5、兔子比乌龟跑得快。

二、计算（每小题5分，共45分）

1、化简并判断公式 (p→q)→(┐q→┐p)的类型

2、求p→q的主析取范式

3、已知 = <5，2x+y>，求x和y。

4、A={1，2，3}，求P(A)

5、A＝{{a,b,c},{a,c,d},{a,e,f}}，计算∪A

第 1 页 共 7 页

6、A={1,2,…,8}，R={|x，y∈A∧x≡y(mod 3)}；求A的等价类和A/R。 7、

设A={a，b，c，d}，R1，R2为A上的关系，其中R1={，，}；R2={，

-13

，，}。求R1，R1R2，R2

8、已知偏序集的哈斯图如图所示：

（1）求集合A；

（2）求该偏序集的极大元和极小元。

9、无向树T有3个3度顶点，2个4度顶点，其余的都是树叶，则T有几片树叶？

第 2 页 共 7 页

三、设A={1，2，3，4}，A上的关系R={x,y|xkykN}（6分） （1）用列元素法表示R； （2）用关系图表示R； （3）用关系矩阵表示R。

四、代数系统VZ6,，其中Z6{0,1,2,3,4,5}，为模6加法（15分） 1）运算是否满足结合律和交换律？说明理由。 2）求幺元e；

3）xZ6，求x；

4）计算3，3和3；

5）解方程4x2。

五、证明题（15分）

1、在自然推理系统P中构造下面推理的证明（7分） 前提：p∨q，q→r，p→s，┐s 结论：r∧(p∨q)

2010051第 3 页 共 7 页

2、设R1和R2为A上的关系，则(R1∪R2)=R1∪R2（8分）

六、综合题（14分）

A={1，2，3，4}，R={<1，1>，<1，2>，<2，3>，<2，4>，<4，2>} （1）求R的关系矩阵MR； （2）求R的关系图G； （3）求G的邻接矩阵A；

（4）顶点1到顶点2长度为3的通路有几条？说明理由；

（5）关系矩阵与邻接矩阵在什么条件下相等，在什么条件下不等？

-1-1-1

第 4 页 共 7 页

计科B 1、老王是山东人或河北人。

2、若地球上没有树木，则人类不能生存。 3、2＋2＝4当且仅当3＋3＝6。 4、有的人登上过月球。 5、有的人用左手写字。

二、（每小题5分，共45分）计算与说明题 1、用等值演算法判断┐(p→q)∧r∧p的类型

2、求p→q的主合取范式

3、已知 = <4，x-y>，求x和y。

4、B={a，b}，求P(B)

5、A＝{{a，b，c},{a，c，d},{a，e，f}}；求∩A

-1

6、R={，，，}；求R

7、说明以下三个关系的性质：

8、已知A={2，3，4，5，6，7，8，9，10，12，20}，R为A上的整除关系，求 偏序集的哈斯图：

第 5 页 共 7 页

9、无向树T有1个2度顶点，3个3度顶点，4个4度顶点，1个5度顶点，其余的都是树叶，则T有几片树叶？

三、（6分）A={1，2，3}, R={|x，y∈A且x+3y<8}，S={<2，3>，<4，2>} 1、R的集合表达式；

-1

2、R

3

3、RS，R；

四、（15分）代数系统VP(A),，其中A{a,b,c}，为对称差运算： 1、运算是否满足结合律和交换律？请说明理由； 2、求幺元e；

3、xP(A)，求x； 4、计算{a}，{a}和{a,b}； 5、解方程a,b

2010031xa。

第 6 页 共 7 页

五、（7+8=15分）证明题

1、在自然推理系统P中构造下面推理的证明 前提：┐p∨q, r∨┐q ,r→s 结论：p→s 2、-1-1-1 设R1和R2为A上的关系，则(R1∩R2)=R1∩R2

10六、（14分）A={1，2，3，4}上的关系R的关系矩阵MR00100011，求： 0001001、R

2、R的关系图G；

3、图G的邻接矩阵A；

4、顶点2到顶点3长度为3的通路有几条？说明理由。

5、对于有向图来说，其关系矩阵和邻接矩阵在什么条件下相等，在什么条件下不等？

第 7 页 共 7 页