离散数学练习题(含答案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页

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4