离散数学习历年真题

三、 用CP规则证明 16% （每小题 8分）

1、A B C D,D E F

A F

2、 x(P(x) Q(x)) xP(x) xQ(x)

四、（14%）

集合X={<1,2>, <3,4>, <5,6>, }，R={<<x1,y1>,<x2,y2>>|x1+y2 = x2+y1} 。 1、 证明R是X上的等价关系。 （10分） 2、 求出X关于R的商集。（4分）

五、（10%）

设集合A={ a ,b , c , d }上关系R={< a, b > , < b , a > , < b , c > , < c , d >} 要求 1、写出R的关系矩阵和关系图。（4分） 2、用矩阵运算求出R的传递闭包。（6分）

六、（20%）

1、（10分）设f和g是函数，证明f g也是函数。 2、（10分）设函数g:S T答案：

五、 填空 20%（每空2分） 1

、

2(x+1)

；

2

、

f:T S，证明 f:T S有一左逆函数当且仅当f是入射函数。

{ a ,a , a ,b , a ,c , c ,c , b ,a , c ,a }

；3、

{ 2,1 , 3,1 , 5,1 , 4,2 , 6,2 , 6,3 ；

4、

反对称性、反自反性；4、{ ,{{ ,2}},{{2}},{{ ,2},{2}}}；5、1；

6、(P Q R) ( P Q R) (P Q R)；7、任意x，如果x是素数则存在一个y，y是奇数且y整除x ；8、 x y z u( P(x,z) P(y,z) Q(x,y,u))。

六、 选择 20%（每小题 2分）

七、 证明 16%(每小题8分) 1、

离散数学习历年真题

①A ②A B

③A B C D ④C D ⑤D ⑥D E ⑦D E F ⑧F ⑨A F 2、

P（附加前提） T①I P T②③I T④I T⑤I P T⑥⑦I CP

xP(x) xQ(x) ( x)P(x) xQ(x)本题可证 x(P(x) Q(x)) ( xP(x) xQ(x)

① ( xP(x)) ② x( P(x)) ③ P(a)

④ x(P(x) Q(x)) ⑤P(a) Q(a) ⑥Q(a) ⑦ xQ(x)

⑧ ( xP(x) xQ(x) 八、 14% （1） 证明：

1、

自反性： x,y X,由于x y x y x,y , x,y R2、

P（附加前提） T①E ES② P US④ T③⑤I EG⑥ CP

R自反

对称性： x1,y1 X, x2,y2 X

当 x1,y1 , x2,y2 R时 即x1 y2 x2 y1也即x2 y1 x1 y2

故 x2,y2 , x1,y1 R R有对称性

3、

传递性： x1,y1 X, x2,y2 X

x3,y3 X

当 x1,y1 , x2,y2 R且 x2,y2 , x3,y3 R时

x1 y2 x2 y1即

x2 y3 x3 y2

(1)(2)