国开电大2021年春《离散数学》形考四作业答案

离散数学下载作业

姓名：____________

学号：____________

得分：____________

教师签名：____________

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

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

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

2.在线提交word文档.

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

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

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

式.P：我会英语

Q：我会德语

命题符号化为pAq

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

P：如果今天是周三

q：昨天是周二

命题符号化为p->q

3.将语句“C3次列车每天上午9点发车或者10点发车”翻译成命题公

式.P:C3次列车每天上午9点发车

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

命题符号化为P或q

4.将语句“小王是个学生，小李是个职员，而小张是个军人."翻译成命题公

式.设P：小王是个学生，

Q：小李是个职员，

R：小张是个军人。

则命题公式为：PAQAR

1

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

1•设集合集={{a},a,b},B={a,{6}}>试计算

⑴ACB；(2)⑶A-(ACB)

解：(1)AcB={a}

(2)AuB=[{a},a,b{b}}

(3)A-(AnB)={{a},a,b}-{a}={a,b}

2.设集合集={2,3,6,12,24,36},B为A的子集,其中B={6,12},R是/上

的整除关系，试

(1)写出R的关系表达式；

(2)画出关系R的哈斯图；

(3)求出B的最大元、极大元、最小上

界.解：

(1)R=

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

<6,24>,<12,12>,<12,24>,<24,24>}

(2)关系R的哈斯图

（3）B的最大兀素：12

极大元素：12

最小上界：12

2

3.设G=<V,E>,V={vi，v,v,vbE={(v,v),(v,v),(v,v),(v,v),(v,v)},

2341213142334

试

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

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

形.解(1)G的图形表示

a

v2v3

(2)邻接矩阵

0111

[1010]

L1101J

1010

(3)求出每个结点的度数

Deg(vl)=3

Deg(v2)=2

Deg(v3)=3

Deg(v4)=2

(4)画出其补图的图形

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

解：

P->(QAR)

3

=-iPv(QAR)

=JPvQ)A(-nPvR)合取范式

=(-,PvQ)v(RA-IR)A(-IPVR)

=(-.PvQ)v(RA-.R)AJPVR)v(QA-IQ)

=(「PvQvR)A(「PvQv「R)A(「Pv「QvR)主合取范式

=(—>PA-IQA-,R)V(-IPA~IQAR)V(—IPA-IQA-1R)(—,PAQAR)V

(PA->QAR)V(PAQA「R)V(PAQAR)主析取范式

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

权.解：

13

最优二叉树的权为1x3+2x3+3x2+3x2+4x2=29

6.试利用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)

4

W(v2,v3)=4,选(v2,v3)

最小生成树，如图

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

7.设谓词公式0x)P(x,y)—(Vz)0(x,y,z),试

(1)写出量词的辖域；(2)指出该公式的自由变元和约束变

元.解

(1)玉的辖域为P(x,y)—VzQ(x,y,z)

Vz的辖域为Q(x,y,z)

(2)自由变元