离散数学(本)2012年1月试题解答.doc

中央广播电视大学2011--2012学年度第一学期“开放本科”期末考试 离散数学（本） 试题解答及评分标准 (供参考) 一、单项选择题（每小题3分，本题共15分） 1．C 2．C 3．B 4．A 5．D 二、填空题（每小题3分，本题共15分） 6．{(,{a}} 7．4 8．1 9．3 10．(A (a)∧B (b))∧(A（a）∧B（b）） 三、逻辑公式翻译（每小题6分，本题共12分） 11．设P：今天有联欢活动，Q：明天有文艺晚会， （2分） P∧Q． （6分） 12．设 P：小王来，Q：小李去 （2分） P → Q． （6分） 四、判断说明题（每小题7分，本题共14分） 13．错误． （3分） 对于集合A的任意元素x，均有x, a(R（或xRa），所以a是集合A中的最大元．（5分） 但按照极小元的定义，在集合A中b,c,d均是极小元． （7分） 14．错误． （3分） ┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式， 如果P的值为真，则┐P∧（P→┐Q）∨P为真， （5分） 如果P的值为假，则┐P与P→┐Q为真，即┐P∧（P→┐Q）为真， 也即┐P∧（P→┐Q）∨P为真， 所以┐P∧（P→┐Q）∨P是永真式． （7分） 另种说明： ┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式， 只要其中一项为真，则整个公式为真． （5分） 可以看到，不论P的值为真或为假，┐P∧（P→┐Q）与P总有一个为真， 所以┐P∧（P→┐Q）∨P是永真式． （7分） 或用等价演算┐P∧（P→┐Q）∨P(T 五．计算题（每小题12分，本题共36分） 15．（1）R={1,1,2,2,3,3,4,4,1,2,2,1,2,3,3,2,3,4,4,3} （3分） （2）关系图如图二： 图二 （6分） （3）因为1,1,2,2,3,3,4,4均属于R，即A的每个元素构成的有序对均在R中，故R在A上是自反的． （9分） 因有2,3与3,4属于R，但2,4不属于R，所以R在A上不是传递的． （12分） 16．（1）关系图如图三： （3分） （2）邻接矩阵 （6分） （3）deg(v1)=2 deg(v2)=2 deg(v3)=2 deg(v4)=2 deg(v5)=2 （9分） （4）补图如图四 （12分） 17．P→（R∧Q） (┐P∨(R∧Q) （4分） ( （┐P∨Q）∧（┐P∨R） （合取范式） （6分） P→（R∧Q） (┐P∨(R∧Q) ((┐P∧(┐Q∨Q) )∨(R∧Q)