离散数学-期末考试---模拟练习题答案

练习题答案一、填空题1.仅用和┐写出下列表达式的等价形式a)RQP)()(RQPb))(EDAEDA2.仅用和┐写出下列表达式的等价形式a)RQP)(RQPb))(QPQ))((QQP；3.构造公式QQPP)(的真值表PQQQPP)(0010101001114.公式A有三个命题变元P、Q、R组成，其主合取范式为A710MMM，则其主析取范式为：65432mmmmm5.公式A有三个命题变元P、Q、R组成，其主析取范A6520mmmm，则其主合取范式为：7431MMMM6.设AdcbaA,,,,上的二元关系：ccacdbbaaaR,,,,,,,,,，ddccbcbbcaS,,,,,,,,,则RS1},,,,,,,,,,,,,{ccaccbabdbbcacSR},,,,,,,,,,,{ccbcccdbbaca)(Rr},,,,,,,,,,,,,{ddbbccacdbbaaa)(Rs},,,,,,,,,,,,,{ddcccbbcbbacca)(St},,,,,,,,,,,{baddccbcbbca7.2},,{},2,1{BAbaBA=},,2,,,1,,,2,,,1,,,2,,,1,,,2,,,1{bbbbababbabaaaaa8.设解释I如下：D={1，2}P(1，1)P(1，2)P(2，1)P(2，2)0110确定下列各式的真值：)2,(xxP1;),1(yyP0;),(yxyPx)__0___。xyPxy(,)1___;9.集合}}2{},2,{{A的幂集)(A}}}2{},2,{{}},2{{}},2,{{,{。10.设全集U={1,2,3,4,5,6,7,8,9,10},A={1,2,4,5,6},B={2,4,6,8,10},则：(A∪B)-B={1,5},BA={2,4,6},BA={1,5,8,10},BA={2,3,4,6,7,9}11.BAbaBA},,{}},2,1{{={{1,2},a,{1,2},b}12.给定集合S={a,b,c,d}，S上的等价关系R能产生划分{{a},{b},{c,d}}，则R＝{a,a,b,b,c,c,d,d,c,d,d,c}13.指出下列映射是单射、满射、双射还是既非单射也非满射：a)xxfRZfln)(,:；(Z+:表示正整数集)双射。b)RRf:，1)(2xxf（R表示不小于0的实数）既非单射也非满射。c)RRf:，2)(xxf（R表示不小于0的实数）满射。d):,:,fABgBCgf是双射，则f是单射e)RRf:，2132)(xxf双射14.请说出以下二元关系是否满足自反性、反自反性、对称性、反对称性和传递性。ABCCBACBAABC(a)(b)(b)(b)(a)：反自反、对称、反对称、传递(b)：自反、反对称、传递(c)：自反、反对称、传递(d)：自反、对称、传递15.设无向图中有6条边，有一个3度结点和一个5度结点，其余结点的度数为2，则该图的结点数为：4。二、命题符号化：1.李明和王平是大学同学。解：命题符号化为：P:李明和王平是大学同学。2.不是所有的哺乳动物都是胎生的。解：设F(x)：:x都是胎生的，M(x)：:x是哺乳动物。则原命题可符号化为：))()((xFxMx或者))()((xFxMx3.任何一个公式总存在一个与之等价的主析取范式。解：设F(x)：:x是公式，M(x)：x是主析取范式，H(x,y)：x与y等价。则原命题可符号化为：)),()(()((yxHyMyxFx4.有些人对某些药品过敏。解：设F(x)：:x是人，M(x)：:x是药物。H(x,y)：x对y过敏。则原命题可符号化为：)),()()((yxHyMxFyx5.参加考试的人不一定取得好成绩。解：设F(x)：:x参加考试；M(x)：:x是人；H(x):x取得好成绩。则原命题可符号化为：))()()((xHxFxMx6.发光的不都是金子。解：设F(x)：:x是发光的，M(x)：:x是金子。则原命题可符号化为：))()((xMxFx7.有的兔子比所有的乌龟跑的快。解：设F(x)：:x是兔子，M(x)：:x是乌龟，H(x,y)：x比y跑得快。则原命题可符号化为：))),()(()((yxHyMyxFx8.所有猫都是动物，但有些动物不是猫。解：设F(x)：:x是动物，M(x)：:x是猫。则原命题可符号化为：))()(())()((xMxFxxFxMx四、证明题：1.GAGEDDCBA,证明：（1）AP规则附加前提（2）DCBAP规则（3）DCT（1）（2）（4）DT（3）（5）GEDP规则（6）GT（4）（5）2.证明下列论证：如果甲参加球赛，则乙或丙也将参加球赛；如果乙参加球赛，则甲不参加球赛；如果丁参加球赛，则丙不参加球赛；所以，如果甲参加球赛，则丁不参加球赛。证明：首先对命题进行符号化如下：P：甲参加比赛；Q：乙参加比赛；R：丙参加比赛；S：丁参加比赛。则由题设可得前提组如下：RQP;PQ;RS;结论则为：SP则构造证明过程如下：（1）RQPP规则（2）P附加前提（3）RQT(1)(2)(4)PQP规则（5）QPT（4）（6）QT（2）（5）（7）RT（3）（6）（8）RSP规则（9）SRT（8）（10）ST(7)(9)3.设R为二元关系，},,,|,{RbcRcacbaS，证明，若R是等价关系，则S也是等价关系。证明：设R是某集合A上等价关系，则（1）证明S有自反性：具有自反性。所以成立。成立也即应有成立，应有对具有自反性，SSxxxRxxRxxxRxxAxR,,,,（2）证明S具有对称性：具有对称性。所以成立。的定义，应有则由成立性，所以有是等价关系，具有对称又因为，则即意味着若有SSabSRacRcbRRbcRcacSba,,,,,,,,（3）证明S具有传递性：具有传递性。所以成立。的定义，可得则再由成立。和性，所以应有是等价关系，具有传递又因为成立。和定义，则由，若有SScaSRcbRbaRRceRebeRbdRdadSScbSba,,,,,,,,,,,综上，若R是等价关系，S也必定为等价关系。五、计算题：1.设集合A＝{2,3,4,5,6,8,12,18,36}，R是A上的整除关系，(1)画出偏序集(A,R)的哈斯图；(2)写出集合A的最大元，最小元，极大元，极小元。(3)写出A的子集{2,3,6}的上界，下界，最小上界，最大下界；(4)写出A的子集{2,4,6}的上界，下界，最小上界，最大下界；解：（1）A,R的哈斯图如下：368121846523（2）A的最大元和最小元均不存在；极大元为5,8,36，极小元为2,3,5。（3）{2,3,6}的上界为6,12,18,36；最小上界为6；下界和最大下界均为无。（4）{2,4,6}的上界为12,36；最小上界为12；下界为2，最大下界也为2。2.用迪克斯特拉算法求从a到z最经济道路的长度以及该道路所经过的结点，并给出求解过程。（此类型求解参见P269例8.2-1）