离散数学练习题(含答案2)(1)

易自考

R＝{，，，} R＝{，，，} R＝{，，，}＝R

t(R)＝?R＝{，，，，，，，，

i?1?i4

2

3

2

d>}

7．已知集合A和B且|A|=n，|B|=m，求A到B的二元关系数是多少？A到B的函数数是多少？

解：因为|P(A×B)|=2|A×B|=2|A||B|=2mn，所以A到B的二元关系有2mn个。因为|BA|=|B||A|=mn，所以A到B的函数mn个。 四、证明题

?1?1?1(R?S)?R?S1．设R和S是二元关系，证明

2．设A={a,b,c},R={(a,a),(a,b),(b,c)},验证rs(R)=sr(R)。

2R?R，其中R2表示R?R。 3．设R是A上的二元关系，试证：R是传递的当且仅当

02324# 离散数学试题 第 5 页 共4页

易自考

4．证明下列结论：

（1）P?Q?R?P?Q?R

（2）(A?B)?(A?C),?(B?C),D?A?D 解：（1）1 P∧Q

2 P 3 P∨Q

P附加前提 T，1，I2 T，2，I1 P

T，3，4，I3 CP P假设前提 P

T，1，2，I5

P

4 P∨Q→R 5 R

6 P∧Q→R

?D

（2）1

2 3 4 5 6 7 8 9 10 11

D∨A A

(A→B)∧(A→C) A→B B

T，4，I2 T，3，5，I3 T，4，I2 T，3，7，I3 T，6，8 ，合取式 P

A→C C

B∧C

?（B∧C）

（B∧C）∧?（B∧C） T，9，10，合取式，矛盾

02324# 离散数学试题 第 6 页 共4页

5. 已知R和S是非空集合A上的等价关系，试证：1）R∩S是A上的等价关系；2）对a∈A，

易自考

[a]R∩S=[a]R∩[a]S。

解：?x∈A，因为R和S是自反关系，所以∈R、∈S，因而∈R∩S，故R∩S是自反的。

?x、y∈A，若∈R∩S，则∈R、∈S，因为R和S是对称关系，所以因∈R、∈S，因而∈R∩S，故R∩S是对称的。

?x、y、z∈A，若∈R∩S且∈R∩S，则∈R、∈S且∈R、∈S，因为R和S是传递的，所以因∈R、∈S，因而∈R∩S，故R∩S是传递的。

总之R∩S是等价关系。

2）因为x∈[a]R∩S?∈R∩S?

∈R∧∈S? x∈[a]R∧x∈[a]S? x∈[a]R∩[a]S

所以[a]R∩S=[a]R∩[a]S。 五、应用题

1．所有的主持人都很有风度。李明是个学生并且是个节目主持人。因此有些学

生很有风度。请用谓词逻辑中的推理理论证明上述推理。（论述域：所有人的集合）

02324# 离散数学试题 第 7 页 共4页