国开电大《离散数学》形考任务四参考答案

1、姓 名： 学 号： 得 分： 教师签名： 离散数学下载作业提交作业方式有以下三种，请务必与辅导教师沟通后选择：将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅.在线提交word文档.自备答题纸张，将答题过程手工书写，并拍照上传.一、公式翻译题(每小题4分，共16分)将语句“我会英语，并且会德语.”翻译成命题公式. 答：设P：我会英语Q：我会德语则命题公式为PAQ将语句“如果今天是周三，则昨天是周二.”翻译成命题公式. 答：设P:今天是周三Q：昨天是周二则命题公式为：PQ将语句“C3次列车每天上午9点发车或者10点发车”翻译成命题公式. 答：设P

2、： C3次列车每天上午9点发车Q： C3次列车每天上午10点发车 则命题公式为：r (P Q)将语句“小王是个学生，小李是个职员，而小张是个军人.”翻译成命题公式. 答：设：P：小王是个学生Q：小李是个职员R：小张是个军人则命题公式为：PAQAR二、计算题(每小题12分，共84分)1 设集合 A-a, a,b, B-a, b),试计算ACB； (2)(3) A-(AnB)答：(1) AcB=aAu8=a,a,bbA-(AnB)=(a),a,b-a=a,b)2.设集合*=2,3,6,12,24,36, B为A的子集，其中B=6, 12, R是厶上 的整除关系，试写出R的关系表达式；画出关系R的哈

3、斯图；求出B的最大元、极大元、最小上界.答：(1) R=(, , , , , , , , , , , , , )关系R的哈斯图3624/12IA（3）B的最大元素：12极大元素：12最小上届：123.设 G=, V=vlt v2, vs, V4, =（儿,捲），（功,捲），（功,）,（曷,捲），（捲,）, 试（1）给出G的图形表示；（2）写出其邻接矩阵；（3）求出每个结点的度数；（4）画出其补图的图形.答：（1） G的图形表示邻接矩阵 TOC o 1-5 h z 0111101011011010每个结点的度数Deg(vl)=3Deg(v2)=2Deg(v3)=3Deg(v4)=2其补图的图形求

4、P0AR）的合取范式与主析取范式.答：P-（QAR）=r PV（QAR）=（-PVQ） A （r PVR）合取范式=(-1 PVQ) V (RA-i R) A (-1 PVR)=(-1 PVQ) V (RA-i R) A (-1 PVR) V (QAn Q)=(-1 PVQVR) A (-1 PVQV-i R) A (i PV-)QVR)主合取范式=(-1 PA-i QA-i R) V (-1 PAn QAR) V (-)PAn QAi R) (r PAQAR) V (PA-| QAR) V (PAQAn R)V (PAQAR)主析取范式试画一棵带权为1,2, 3, 3, 4的最优二叉树，并计

5、算该最优二叉树的权.最优二叉树的权为 1 X 3+2 X 3+3 X 2+3 X 2+4 X 2=29试利用Kruskal算法求出如下所示赋权图中的最小生成树(要求写出求 解步骤)，并求此最小生成树的权.答：W (v2, v6) =1,选(v2, v6)W (v4, v5) =1,选(v4, v5)W(vl, v6) =2,选(vl, v6)W (v3, v5) =2,选(v3, v5)W (v2, v3)=4,选(v2, v3) 最小生成树，如图V5 丄 V4生成树的权 w (T) =1+1+2+2+4=10设谓词公式(Bx)P(x, y)一(Vz)Q(x, y, z),试(1)写出量词的辖域；(2)指出该公式的自由变元和约束变元.答：(1)女的辖域为 P(x, y) VzQ(x, y,