离散数学（第三版）陈建明，刘国荣课后习题答案(4)

综合这两个方面有（A∩B）3（C∩D）=（A3C）∩（B3D）。 证法二：（逻辑法）对任何x,y (x,y)∈(A∩B)3(C∩D) ?x∈A∩B?y∈C∩D ?(x∈A?x∈B)?(y∈C?y∈D)

?(x∈A?y∈C)?(x∈B?y∈D) (?的结合律、交换律) ?(x,y)∈A3C?(x,y)∈B3D ?(x,y)∈(A3C)∩(B3D)

由x，y的任意性，可得：(A∩B)3(C∩D)= (A3C)∩(B3D) 。

5．下列各式中哪些成立，哪些不成立？对成立的式子给出证明，对不成立的式子给

出反例。

1）（A∪B）3（C∪D）=（A3C）∪（B3D） 2）（A\\B）3（C\\D）=（A3C）\\（B3D） 3）（A?B）3（C?D）=（A3C）?（B3D） 4）（A\\B）3C=（A3C）\\（B3C） 5）（A?B）3C=（A3C）?（B3C）

[解] 1）不成立。设A={a}，B={b}，C={c}，D={d}，则（a，-d）∈（A∪B）3

（C∪D），但（a，-d）?（A3C）∪（B3D）。所以（A∪B）3（C∪D）=（A3C）∪（B3D）不成立。事实上有：（A3C）∪（B3D）?（A∪B）3（C ）?（A∪B）3（C∪D）。

2）不成立。设A={a}，B={b}，C=D={c}，则（a，c）∈（A3C）\\（B3D）但（a，c）?（A\\B）3（C\\D）。因而（A\\b）3（C\\D）=（A3C）\\（B3D）不成立。事实上有：（A\\B）3（C\\D）?（A3C）\\（B3D）。因为A\\B?A，C\\D?，故有（A3C）\\（B3D）? A3C；又若（x，y）∈（A\\B）3（C\\D）故此x∈A\\B，从而x?B，y∈C\\D，从而y?D，故此（x，y）?B3D综合这两方面，有（A\\B）3（C\\D）?（A3C）\\（B3D）。

3）不成立。设A={a}，B={b}，C={a}，D={b}，则（a，b）∈（A?B）3（C?D），

但（a，b）?（A3C）?（B3D）。所以（A?B）3（C?D）?（A3Ｃ）?（B3D）不成立。又设A={a}，B={b}，C={a}，D={c} 则（a，c）∈（A3Ｃ）?（B3D），但（a，c）?（A?B）3（C?D）。所以（A3Ｃ）?（B3D）?（A?B）3（C?D）不成立。因此（A?B）3（C?D）与（A3Ｃ）?（B3D）无任何包含关系。总之（A?B）3（C?D）=（A3Ｃ）?（B3D）不成立。

11

4）成立。证明如下：对任一（x，y）∈（A\\B）3C，有x∈A，x?B，y∈C 于是（x，

y）∈A3C，且（x，y）∈（A\\B）3C，且（x，y）?B3C（否则x∈B），所以（x，y）∈（A3C）\\（B3C）。因而 （A\\B）3C?（A3C）\\（B3C）。

又对任一（x，y）∈（A3C）\\（B3C），有（x，y）∈A3C，且（x，y）?B3C从而x∈A，y∈C及x?B。即x∈A\\B，y∈C，故此（x，y）∈（A\\B）3C。所以（A3C）\\（B3C）?（A3B）3C。

因而（A\\B）3C=（A3C）\\（B3C）。 另一种证明方法： （A3B）3C

=（A∩B′）3C（差集的定义）

=（A3C）∩（B′3C）（叉积对交运算的分配律） =（A3C）∩（B3C）′

（因（B3C）′=（B′3C））∩（B3C′）∪（B′3C′） 但（A3C）∩（B3C）′=（（A3C）∩（B′3C））∪?

=（A3C）∩（B′3C））

=（A3C）∩（B′3C）（差集的定义） 证法三：（逻辑法）对任何x,y (x,y)∈(A3C) \\ (B3C) ?(x,y)∈A3C?(x,y)?B3C ?(x∈A?y∈C)?(x?B?y?C)

?(x∈A?y∈C?x?B)?(x∈A?y∈C?y?C) (?对?的分配律) ?(x∈A?x?B?y∈C)?(x∈A?y∈C?y?C) (?的结合律、交换律) ?(x∈A?x?B)?y∈C (?及?的零壹律、?的结合律) ?x∈A \\ B?y∈C ?(x,y)∈(A \\ B)3C

由x，y的任意性，可得：(A \\ B)3C=(A3C) \\ (B3C) 。

5）成立。证明如下：对任一（x，y）∈（A?B）3C，故此x∈A?B，y∈C于是x∈A且x?B，或者x?A且x∈B。因此（x，y）∈（A3C）?（B3C）。所以（A?B）3C?（A3C）?（B3C）。

对任一（x，y）∈（A3C）?（B3C）。则（x，y）∈A3C且（x，y）?B3C，或者（x，y）?A3C且（x，y）B3C。因此x∈A，yC，x?B，或者x

12

∈B，y∈C，x?A。所以x∈A\\B，或x∈B\\A，并且y∈C，故此 x∈A?B，y∈C。因此（x，y）∈（A?B）3C，即（A3C）?（B3C）?（A?B）3C。 综合两方面、就有（A?B）3C=（A3C）?（B3C）

另一种证明方法：（A?B）3C

=（（A\\B）∪（B\\A））3C（对称差的定义）

=（（（A\\B）3C）（（B\\A）3C）（叉积对并运算的分配律） =（（A3C）\\（B3C）∪（B3C）\\（A3C））（根据4）） =（A3C）?（B3C）（对称差的定义）

6．设A={1，2，3}，B={a}，求出所有由A到B的关系。?[解]：R0=?，R1={（1，a）}，R2={（2，a）}，R3={（3，a）}，

R4={（1，a），（2，a）}，Rs={（1，a），（3，a）}，R6={（2，a），（3，a）}，

R7={（1，a），（2，a），（3，a）}

7．设A={1，2，3，4}，R1={（1，3），（2，2），（3，4）}，R2={（1，4），（2，3），

（3，4）}，求：R1∪R2，R1∩R2，R1\\R2，R1′，?（R1），?（R2），?（R1），?（R2），?（R1∪R2），?（R1∩R2）

[解]：R1∪R2={（1，3），（1，4），（2，2），（2，3），（3，4）}

R1∩R2={（3，4）} R1\\R2={（1，3），（2，2）}

R1′=（A3A）\\R={（1，1），（1，2），（1，4），（2，1），（2，3），（2，4），（3，1），（3，2），（3，3），（4，1），（4，2），（4，3），（4，4）} （R1）={1，2，3}，?（R1）={2，3，4}， （R2）={1，2，3}，?（R2）={3，4} （R1∪R2）={1，2，3}，?（R1∩R2）={4} 8．对任意集合A及上的关系R1和R2，证明

1）?（R1∪R2）=?（R1）∪?（R2） 2）?（R1∩R2）??（R1）∩?（R2）

[证] 1）一方面，由于R1?R1∪R2，R2?R1∪R2，根据定理1，有?（R1）??（R1

∪R2），?（R2）??（R1∪R2）故

?（R1）∪?（R2）??（R1∪R2）

另一方面，若x∈?（R1∪R2）那么存在着y∈A，使（y，x）∈（R1∪R2）因此（y，x）∈R1，或者（y，x）∈R2，从而x∈?（R1）或者x∈?（R2）于是x∈?(R1) ∪?（R2），所以?（R1∪R2）??（R1）∪?（R2）。

13

11．设A={1，2，3，4}，定义A上的下列关系

R1={（1，1），（1，2），（3，3），（3，4）}，R2={（1，2），（2，1）}

R3={（1，1），（1，2），（2，2），（2，1），（3，3），（3，4），（4，3），（4，4）} R4={（1，2），（2，4），（3，3），（4，1）}

R5={（1，2），（1，3），（1，4），（2，3），（2，4），（3，4）} R6=A3A，R7=?

请给出上述每一个关系的关系图与关系矩陈，并指出它具有的性质。 [解]：

1）

1 0 0 2

?1 ?0? R1???03 0 0 4 ??0R1是反对称的，传递的。 2）

100?000???

011?000???0?1?R1???0??0R2是反自反的，对称的。 3）

100?000???

000?000???1?1?R1???0??0（R1∪R2）=?（R1）∪?（R2）。

100?100???

011?011??R3是自反的，对称的，传递的，因此是等价关系。循环的 综合这两方面，就有2）由于R1∩R2?R1，R1∩R2?R2，根据定理1，有?（R1∩R2）??（R1），?

（R1∩R2）?R2，所以?（R1∩R2）??（R1）∩?（R2）反方向的包含不成立，反全由第7题可得，那里?（R1∩R2）={4}，?（R1）∩?（R2）={2，3，4}∩{3，4}={3，4}因此

14

?（R1）∩??（R2）?（R1∩R2）

9．设A有n个元素的有限集合，请指出A上有多少个二元关系？并阐明理由。

[解] A上有2n2个元关系。因为叉积A3A有n2个元素，因而A3A有2n2 …… 此处隐藏：2065字，全部文档内容请下载后查看。喜欢就下载吧 ……