2024年离散数学形成性考核作业离散数学综合练习书面作业.docx

离散数学形成性考核作业4

姓

姓名：

学号：

得分：

教师签名：

离散数学综合练习书面作业

规定：学生提交作业有如下三种方式可供选择：

1.可将本次作业用A4紙打印出来，手工书写答題，字迹工整，解答題要有解答过程，完毕作业后交給辅导教师批阅．

2.在线提交word文档．

3.自备答題紙张，将答題过程手工书写，并拍照上传．

一、公式翻译題

1．請将語句“小王去上課，小李也去上課．”翻译成命題公式．

设Ｐ：小王去上課

Ｑ:小李去上課

则：命題公式Ｐ∧Ｑ

2．請将語句“他去旅游，仅当他有時间．”翻译成命題公式．

设Ｐ：他去旅游

Ｑ：他有時间

则命題公式為Ｐ→Ｑ

3．請将語句“有人不去工作”翻译成谓詞公式．

设Ａ（x）:x是人

Ｂ（x）：去工作

则谓詞公式為?x（A(x)∧－B（x）)

4．請将語句“所有人都努力学习．”翻译成谓詞公式．

设A（x）:x是人

B（x）:努力学习

则谓詞公式為?x（A（x）∧B（x））

二、计算題

1．设A={{1},{2},1,2}，B={1,2,{1,2}}，试计算

（1）(A?B)；（2）(A∩B)；（3）A×B．

解：

（A-B）＝{{1}，{2}}

（A∩B）＝{1，2}

A×B＝{{1},1,{1},2,{1},{1,2},{2},1,{2},2,{2},{1,2},1,1,1,2,1,{1,2},2,1,2,2,2,{1,2}}

2．设A={1，2，3，4，5}，R={x，y|x?A，y?A且x+y?4}，S={x，y|x?A，y?A且x+y0}，试求R，S，R?S，S?R，R-1，S-1，r(S)，s(R)．

解：

R＝{1,1,1,2,1,3,2,1,2,2,3,1}

S=空集

R?S=空集

S?R=空集

R-1={1,1,2,1,3,1,1,2,2,2,1,3}

S-1=空集

r(S)={1,1,2,2,3,3,4,4,5,5}

s(R)={1,1,1,2,1,3,2,1,2,2,3,1}

3．设A={1,2,3,4,5,6,7,8}，R是A上的整除关系，B={2,4,6}．

(1)写出关系R的表达式；(2)画出关系R的哈斯图；

(3)求出集合B的最大元、最小元．

4．设G=V，E，V={v1，v2，v3，v4，v5}，E={(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5)}，试

(1)給出G的图形表达；(2)写出其邻接矩阵；

(3)求出每个結点的度数；(4)画出其补图的图形．

答：（1）

（2）

（3）

?

deg(v1)=1,deg(v2)=2,deg(v3)=4,deg(v4)=3,deg(v5)=2

(4)

5．图G=V,E，其中V={a,b,c,d,e}，E={(a,b),(a,c),(a,e),(b,d),(b,e),(c,e),(c,d),(d,e)}，对应边的权值依次為2、1、2、3、6、1、4及5，试

（1）画出G的图形；（2）写出G的邻接矩阵；

（3）求出G权最小的生成树及其权值．

解：

（1）

（2）

（3）

其中权值是：7

6．设有一组权為2,3,5,7,17,31，试画出对应的最优二叉树，计算该最优二叉树的权．

解：

权值：65

7．求P?Q?R的析取范式，合取范式、主析取范式，主合取范式．

解：

8．设谓詞公式．

（1）试写出量詞的辖域；

（2）指出该公式的自由变元和约束变元．

9．设个体域為D={a1,a2}，求谓詞公式(?y)(?x)P(x,y)消去量詞后的等值式；

三、证明題

1．对任意三个集合A,B和C，试证明：若A?B=A?C，且A?，则B=C．

证明：设x∈A,y∈B,则x,y∈A?B

由于A?B＝A?C，故x,y∈A?C,则有y∈C

因此B?C

设x∈A,z∈C，则x,z∈A?C

由于A?B＝A?C，故x,z∈A?B,则有z∈B

因此C?B

故得A＝B

2．试证明：若R与S是集合A上的自反关系，则R∩S也是集合A上的自反关系．

证明：

R和S是自反的，?x∈A,x,x∈R,x,x∈S

则x,x∈R?S

因此R?S是自反的

3．设连通图