离散数学习历年真题

四、逻辑推演 16%

用CP规则证明下题（每小题 8分） 1、A B C D,D E F A F 2、 x(P(x) Q(x)) xP(x) xQ(x)

五、计算 18%

1、设集合A={a，b，c，d}上的关系R={<a , b > ,< b , a > ,< b, c > , < c , d >}用矩阵运算求出R的传递闭包t (R)。 （9分）

2、如下图所示的赋权图表示某七个城市v1,v2, ,v7及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。 （９分）

试卷一答案：

一、填空 20% （每小题2分）

1、{0，1，2，3，4，6}； 2、(B C) A；3、1； 4、( P S R) ( P S R)； 5、1；6、{<1,1>,

<1,3>, <2,2>, <2,4> }；7、{<a.b>,<a,c>,<a,d>,<b,d>,<c,d>} IA ；8、

9、a ；a , b , c ,d ；a , d , c , d ；10、

c; 二、选择 20% （每小题 2分）

三、证明 26%

1、 证：

“ ” a,b,c X 若<a,b>,<a,c> R由R对称性知<b,a>,<c,a R，由R传递性得

<b,c> R