2022年秋国开《离散数学》形考任务4各章综合练习

离散数学下载作业

姓名：____________

学号：____________

得分：____________

教师签名：____________

提交作业方式有以下三种，请务必与辅导教师沟通后选择：

1.将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有

解答过程，完成作业后交给辅导教师批阅.

2.在线提交word文档.

3.自备答题纸张，将答题过程手工书写，并拍照上传.

一、公式翻译题（每小题4分，共16分）

1.将语句"我会英语，并且会德语.”翻译成命题公式.

设P：我会英语Q：我会德语

则命题公式为：PAQ

2.将语句“如果今天是周三，则昨天是周二翻译成命题公式.

设P：今天是周三Q：明天是周二

则命题公式为：P-Q

3.将语句“小王是个学生，小李是个职员.”翻译成命题公式.

设P：C3次列车每天上午9点发车

Q：C3次列车每天上午10点发车

4.将语句“如果明天下雨，我们就去图书馆.“翻译成命题公式.

设P:小王是个学生

Q：小李是个职员

R：小张是个军人

则命题公式为：PAQAR

二、计算题(每小题12分，共84分)

1.设集合A={a,4c},B={{a,b},b},试计算

⑴ACB；(2)A-B；(3)4X8.

⑴AB={a}

⑵AB={{a},a,b,{b}}

⑶A-(AB)={{a},b,b}

2.设6=<，，E>,IZ=｛vi,V2,V3,V4,V5）,^｛（VbVs）,（VI,V5）,（V2,V3）,（V3,V4）,

（V4,V5）｝,试

（1）给出G的图形表示；

（2）求出每个结点的度数；

（3）画出其补图的图形.

(1)R={<2,2>,<3,3>,<6,6>,<12,12>,<24,24>,<36,36>,<2,6>,<3,6>,

<2,12>,<3,12>,<6,12>,<2,24>,<3,24>,<6,24><12,24>,

<2,36><3,36>,<6,36>,<12,36>}

(2)R的哈斯图

(3)集合B的最大元为12,极大元为12,最小上界为12

3.试画一棵带权为1,2,3,3,4的最优二叉树,并计算该最优二叉树的权.

(1)G的图形表示如图所示：

(2)邻接矩阵：

(3)deg(v1)=3

deg(v2)=2

deg(v3)=3

deg(v4)=2

(4)补图如图所示：

V3V4

4.求出如下所示赋权图中的最小生成树（要求写出求解步骤），并求此最

小生成树的权.

解：P-(RAQ)PV(RAQ)(PVQ)八(PVR)(合

取范式)

P—(RAQ)

1PV(RAQ)

(-1PA(QVQ))V(RAQ)

(-IPA-1Q)V(PAQ)V(RAQ)

((-1PAnQ)A(RVR))V(PAQ)VRAQ)

(-1PAnQA7R)VPA-iQAR)VPAQ)V(RAQ)

(PA-iQA-iR)V(PA-)QAR)

V((-|PAQ)A(-|RVR))V(RAQ)

(-1PA-iQA-iR)V(-)PA-)QAR)V(nPAnQAnR)V(-|PAQAR)V(RA

Q)

(-1PAnQA-iR)V(-|PAnQAR)V(-|PAnQAqR)V(-)PAQAR)V(n

PVP)ARAQ)

(nPA-iQA-iR)V(-jPA-iQAR)V(nPAnQAnR)V(nPAQAR)V(PA

RAQ)(主析取范式)

5.求出如图所示赋权图中的最小生成树（要求写出求解步骤），并求此最小生

成树的权.

最优二叉树如图所示:

权为13+23+32+32+42=29

6.求P-(QAR)的析取范式与合取范式.

解：用Kruskal算法求产生的最小生成树。步骤为:

w(v2,V6)=l,选(V2,V6)

w(V4,v5)=l,选(V4,V5)

w(Vl,V6)=2^(Vl,V6)

w(V3,V5)=2,选(v3,V5)

w(V2,V3)=4,选(V2,V3)

最小生成树如图所示：

最小生成树的权w(T)=1+1+2+2+4=10.

7.求(PVQ)-R的析取范式与合取