2005离散数学试题B参考答案

１321计算机应用专业《离散数学》试题B参考答案2005年3月一、填空题(每小题3分，本题共15分)1.自反性、对称性、传递性.2.PQR.3.{(1,1),(1,2),(2,1),(2,2)}。.4.连通无回路（或任一等价定义）.5.10.二、选择题(每小题3分，本题共15分)1.D.2.D.3.A.4.C.5.D.三、计算题(本题共60分)1.(本题12分)R＝{(1,1),(1,2),(2,2),(3,2),(3,3)}.(1)R的关系图(2)110010011RM２(3)R具有自反性、传递性、反对称性。2.(本题12分)集合A＝{1,2,3,4,6,8,12}(1)半序集(A,R)的哈斯图(2)子集{2,4,6,8}无上界，下界是1,2，无最小上界，最大下界是2.(3)A无最大元，最小元是1，极大元是8,12，极小元是1。3.(本题12分)求有限权图的最短路AB12AB1AB1422AB122AB14221AB14221212483612３A到B的最短路的权值为6.4.(本题12分)(()())()PQQRPR(()())()PQQRPR(()())()PQQRPR(()())PQQRPR(())(())PQPQRR()()QPQR()QQPR11PR所以是恒真公式。5.(本题12分)前束范式：((,)(()()))GxyPxyzQzRx((,)(()()))xyPxyzQzRx((,)(()()))xyPxyzQzRx((,)(()()))xyPxyzQzRx.((,)()())xyzPxyQzRx。四.(本题10分)证明：111()RSRS.1(,)()xyRS(,)()yxRS((,))((,))yxRyxS４11((,))((,))xyRxyS11(,)xyRS所以111()RSRS.