离散数学习历年真题

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

1、 P Q；P Q2、T 3、B31 B00011111 {a4,a5,a6,a7,a8}4、

R={<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,2>,<5,3>,<5,4>,<5,5>,<5,6>}；

1 1 0 1 0

1111

1111 0011

1111 0000 5、R={<1,2>,<1,3>,<2,1>}；R={<1,1>,<2,2>,<3,3>} 6、a ；否；有 7、Klein四元

1

n(n 1)2群；循环群 8、 B 9、；图中无奇度结点且连通 10 、

二、

三、 证明 46%

1、（9分）

（1） S自反的

a A，由R自反， ( a,a R) ( a,a R)， a,a S

（2） S对称的

a,b A

a,b S ( a,c R) ( c,b R)

( a,c R) ( c,b R) b,a S

（3） S传递的

S定义 R对称 R传递

a,b,c A

a,b S b,c S

( a,d R) ( d,b R) ( b,e R) ( e,c R) ( a,b R) ( b,c R) a,c S

R传递 S定义

由（1）、（2）、（3）得；S是等价关系。 2、11分

证明：设P(x)：x 是个舞蹈者； Q(x) ：x很有风度； S(x)：x是个学生； a：王华 上述句子符号化为：

前提： x(P(x) Q(x))、S(a) P(a) 结论： x(S(x) Q(x)) 3分

①S(a) P(a) ② x(P(x) Q(x)) ③P(a) Q(a) ④P(a)

P P US② T①I