五证明解答(一逻辑集合关系)

??x?A，?IA?R，??R。即xRx，故R是自反的。

12、设A是集合，R?A×A，则R是对称的?R＝R－1。

证明：

_1

???R ，?R是对称的，?yRx。即?R，故?R 。从

而R?R-1。

反之??R-1,即?R 。?R是对称的，?yRx。即?R，

R_1?R。

故R=R-1。

-1-1

??x，y?A，若?R ，即?R。? R=R，??R。即

yRx，故R是对称的。

13、设A,B,C和D均是集合，R?A×B，S?B×C，T?C×D，则 (1) R?(S?T)=(R?S)?(R?T)； (2) R?(S?T)?(R?S)?(R?T)；

证明：

（1）??R?(S?T)，则由合成关系的定义知?y?B，使得?R且?S?T。从而?R且?S或?R且?T，即?R?S或?R?T。故?（R?S）（R?T） 。从而R?(S?T)??（R?S）?（R?T）。

同理可证（R?S）?（R?T）?R?(S?T)。 故R?(S?T)=（R?S）?（R?T）。

(2) ??R?(S?T)，则由合成关系的定义知?y?B，使得?R且?S?T。从而?R且?S且?T，即?R?S且?R?T。故?（R?S）?（R?T） 。从而R?(S?T)?(R?S）。 ?（R?T）

14、设〈A,≤〉为偏序集，??B?A，若B有最大(小)元、上(下)确界，则它们是惟一的。

证明：

设a,b都是B的最大元，则由最大元的定义a?b，b?a。??是A上的

偏序关系，?a=b。即B如果有最大元则它是惟一的。

15、设A={1,2,3},写出下列图示关系的关系矩阵，并讨论它们的性质：

1 1 1

2 3 2 3 2 3 解：

?000???（1）R={<2,1>,<3,1>,<2,3>};MR=?101?;它是反自反的、反对称的、传

?100???递的；

?011???101（2）R={<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>};MR=??;它是反自?110???反的、对称的；

?011???（3）R={<1,2>,<2,1>,<1,3>,<3,3>};MR=?100?;它既不是自反的、反自

?001???反的、也不是对称的、反对称的、传递的。

16、设A={1,2,…,10}。下列哪个是A的划分？若是划分，则它们诱导的等价关系是什么？

（1）B={{1,3,6},{2,8,10},{4,5,7}}; （2）C={{1,5,7},{2,4,8,9},{3,5,6,10}};

（3）D={{1,2,7},{3,5,10},{4,6,8},{9}}

解：

（1）和（2）都不是A的划分。 （3）是A的划分。其诱导的等价关系是

I

10>,

<10,3>,<10,5>,<5,10>,<4,6>,<6,4>,<4,8>,<8,4>,<6,8>,<8,6>}

。

A?{<1,2>,<2,1>,<1,7>,<7,1>,<2,7>,<7,2>,<3,5>,<5,3>,<3,

17、R是A={1,2,3,4,5,6}上的等价关系，

R=IA?{<1,5>,<5,1>,<2,4>,<4,2>,<3,6>,<6,3>} 求R诱导的划分。

解：

R诱导的划分为{{1,5},{2,4},{3,6}}。

18、A上的偏序关系?的Hasse图如下。

（1） 下列哪些关系式成立：a?b,b?a,c?e,e?f,d?f,c?f； （2） 分别求出下列集合关于?的极大（小）元、最大（小）元、上

（下）界及上（下）确界（若存在的话）： (a) A; (b) {b,d}; (c) {b,e}; (d) {b,d,e} a e f

b d c

解：

(1) b?a,c?e,d?f,c?f成立；

(2) (a)的极大元为a,e,f,极小元为c;无最大元，c是最小元；

无上界，下界是c;无上确界，下确界是c。

(b)的极大元为b,d,极小元为b,d;无最大元和最小元；

上界是e，下界是c;上确界是e，下确界是c。

(c)的极大元为e,极小元为b;最大元是e，b是最小元；

上界是e，下界是b;上确界是e，下确界是b。

(d)的极大元为e,极小元为b,d;最大元是e，无最小元；

上界是e，下界是c;上确界是e，下确界是c。