《离散数学》题库及答案

（3）若xyz; （4）存在x，对任意y 使得xy=y; （5）对任意x，存在y使x+y=x。

答：

（1）?x（G(x,0)?M（0,0,x）） 或??x L(x,0) （2）?x?y?z ((L(x,y)?L(y,z))?L(x,z)) （3）?x?y ((L(x,y)??z(L(z,0)?G(xz,yz))) （4）?x?yM（x,y,y） （5）?x?yA(x,y,x)

3、列出下列二元关系的所有元素：

（1）A={0,1,2}，B={0,2,4}，R={|x,y?A?B};

（2）A={1,2,3,4,5}，B={1,2}，R={|2?x+y?4且x?A且y?B}; （3）A={1,2,3}，B={-3,-2,-1,0,1}，R={||x|=|y|且x?A且y?B};

解：

(1) R={<0,0>,<0,2>,<2,0>,<2,2>} (2) R={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>}; (3) R={<1,1>,<1,-1>,<2,-2>,<3,-3>}。

4、对任意集合A,B，证明：若A?A=B?B，则B=B。

证明：

若B=?，则B?B=?。从而A?A =?。故A=?。从而B=A。

若B??，则B?B??。从而A?A??。

37

对?x?B, ?B?B。因为A?A=B?B，则?A?A。从而x?A。故B?A。 同理可证，A?B。 故B=A。

5、对任意集合A,B，证明：若A??，A?B=A?C，则B=C。

证明：

若B=?，则A?B=?。从而A?C =?。因为A??，所以C=?。即B=C。

若B??，则A?B??。从而A?C??。

对?x?B,因为A??，所以存在y?A, 使?A?B。因为A?B=A?C，则?A?C。从而x?C。故B?C。

同理可证，C?B。 故B=C。

6、设A={a,b}, B={c}。求下列集合：

(1) A?{0,1}?B； (2) B2?A； (3) (A?B)2; (4) P(A)?A。

解：

（1） A?{0,1}?B={,,,}; （2） B2?A={,};

（3） (A?B)2={,,,}; （4） P(A)?A={,,<{a},a>,<{a},b>,<{b},a>,<{b},b>

,,}。

7、设全集U={a,b,c,d,e}, A={a,d}, B={a,b,c}, C={b,d}。求下列各集合：

38

（1）A?B?C； （2）A?B?C；（3）(A?B)?C; （4）P(A)-P(B); （5）(A-B)?(B-C); （6）(A?B)?C;

解 ：

(1) A?B?C={a}; (2) A?B?C={a,b,c,d,e}; (3) （A?B）?C={b,d}; (4) P(A)-P(B)={{d},{a,d}}; (5) (A-B)?(B-C)={d,c,a}; (6) (A?B) ?C={b,d}。

8、设A,B,C是任意集合，证明或否定下列断言： （1）若A?B，且B?C，则A?C； （2）若A?B，且B?C，则A?C; （3）若A?B，且B?C，则A?C； （4）若A?B，且B?C，则A?C；

证明：

(1) 成立。

对?x?A, 因为A?B，所以x?B。又因为B?C，所以x?C。即A?C。 (2) 不成立。反例如下：A={a}, B={a,b},C={a,b,c}。虽然A?B，且B?C，但A?C。

(3) 不成立。反例如下：A={a}, B={{a},b},C={{{a},b},c}。虽然A?B，且B?C，但A?C。

(4) 成立。因为A?B, 且B?C，所以A?C。

9、A上的任一良序关系一定是A上的全序关系。

证明：

39

?a，b∈A，则{a,b}是A的一个非空子集。?≤是A上的良序关系，?{a,b}有最小元。若最小元为a，则a≤b；否则b≤a。从而≤为A上的的全序关系。

10、若R和S都是非空集A上的等价关系，则R?S是A上的等价关系。

证明：

?a∈A，因为R和S都是A上的等价关系，所以xRx且xSx。故xR?Sx。从而R?S是自反的。

?a,b∈A，aR?Sb，即aRb且aSb。因为R和S都是A上的等价关系，所以bRa且bSa。故bR?Sa。从而R?S是对称的。

?a,b,c∈A，aR?Sb且bR?Sc，即aRb，aSb,bRc且bSc。因为R和S都是A上的等价关系，所以aRc且aSc。故aR?Sc。从而R?S是传递的。

故R?S是A上的等价关系。

11、设R?A×A，则R自反 ?IA?R。

证明：

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

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

证明：

???R ，?R是对称的，?yRx。即?R，故?R_1 。从而R?R-1。

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

故R=R-1。

??x，y?A，若?R ，即?R-1。? R=R-1，??R。即yRx，

40