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

离散数学辅助教材

概念分析结构思想与推理证明

第一部分

集合论

刘国荣

交大电信学院计算机系

1

离散数学习题解答

习题一 （第一章集合）

1. 列出下述集合的全部元素：

1）A={x | x ∈N∧x是偶数∧ x＜15}

2）B={x|x∈N∧4+x=3} 3）C={x|x是十进制的数字} [解] 1）A={2，4，6，8，10，12，14}

2）B=?

3）C={0，1，2，3，4，5，6，7，8，9} 2. 用谓词法表示下列集合：

1）{奇整数集合}

2）{小于7的非负整数集合}

3）{3，5，7，11，13，17，19，23，29} [解] 1）{n?n?I?(?m?I)(n=2m+1)}；

2）{n?n?I?n?0?n<7}；

3）{p?p?N?p>2?p<30??(?d?N)(d?1?d?p?(?k?N)(p=k?d))}。 3. 确定下列各命题的真假性： 1）??? 2）?∈? 3）??{?} 4）?∈{?}

5）{a，b}?{a，b，c，{a，b，c}} 6）{a,b}∈(a，b，c，{a，b，c}) 7）{a，b}?{a，b，{{a，b，}}} 8）{a，b}∈{a，b，{{a，b，}}} [解]1）真。因为空集是任意集合的子集； 2）假。因为空集不含任何元素； 3）真。因为空集是任意集合的子集； 4）真。因为?是集合{?}的元素；

5）真。因为{a，b}是集合{a，b，c，{a，b，c}}的子集； 6）假。因为{a,b}不是集合{a，b，c，{a，b，c}}的元素；

2

7）真。因为{a，b}是集合{a，b，{{a，b}}}的子集； 8）假。因为{a,b}不是集合{a，b，{{a，b}}}的元素。 4. 对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B∈C，则A∈C。 2）如果A∈B∧B∈C，则A∈C。 3）如果A?B∧B∈C，则A∈C。

[解] 1）假。例如A={a}，B={a，b}，C={{a}，{b}}，从而A∈B∧B∈C但A∈C。 2）假。例如A={a}，B={a，{a}}，C={{a}，{{a}}}，从而A∈B∧B∈C，但、A

∈C。

3）假。例如A={a}，B={a，b}，C={{a}，a，b}，从而ACB∧B∈C，但A∈C。 ．5．对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B?C，则A∈C。 2）如果A∈B∧B?C，则A?C。 3）如果A?B∧B∈C，则A∈C。 3）如果A?B∧B∈C，则A?C。

[解] 1）真。因为B?C??x（x∈B?x∈C），因此A∈B?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，{a，b}}，从而A?B∧B∈C，但A?C。 4）假。例如A={a}，B={{a，b}}，C={{a，b}，b}，从而A?B∧B∈C，但A?C。 6．求下列集合的幂集：

1）{a，b，c} 2）{a，{b，c}} 3）{?} 4）{?，{?}}

5）{{a，b}，{a，a，b}，{a，b，a，b}}

[解] 1）{?，{a}，{b}，{c}，{a，b}，{a，c}，{b，c}，{a，b，c}}

2）{，{a}，{{b，c}}，{a，{a，b}}} 3）{?，{?}}

4）{?，{?}，{{?}}，{?，{?}}} 5）{?，{{a，b}}}

7．给定自然数集合N的下列子集：

3

A={1，2，7，8} B={ x|x2＜50}

C={x|x可以被3整除且0≤x≤30} D={x|x=2K，K∈I∧O≤K≤6} 列出下面集合的元素： 1） A∪B∪C∪D 2） A∩B∩C∩D 3） B\\（A∪C） 4） （A′∩B）∪D

[解] 因为B={1，2，3，4，5，6，7}，C={3，6，9，12，15，18，21，24，27，30}，

D={1，2，4，8，16，32，64，}，故此

1）A∪B∪C∪D={1，2，3，4，5，6，7，8，9，12，15，16，18，21，24，27，

30，32，64}

2）A∩B∩C∩D=? 3）B\\（A∪C）={4，5}

4）（A′∩B）∪D={1，2，3，4，5，6，7，8，16，32，64} 8．设A、B、C是集合，证明：

1）（A\\B）=A\\(B\\C)

2）（A\\B）\\C=（A\\C）\\（B\\C） 3）（A\\B）\\C=(A\\C)\\B [证明] 1）方法一：（A\\B）\\C

=（A∩B′）∩C′ （差集的定义） =A∩（B′∩C′） （交运算的结合律） =A∩（B∪C）′ （deMorgan律） =A\\（B∪C） （差集的定义） 方法二：对任一元素x∈（A\\B）\\C，则x?C，同时，x∈A\\B，x∈A，x?B，

所以，x∈A，x?B∪C，即x∈A\\（B∪C），由此可见（A\\B）\\C?A\\（B∪C）。 反之，对任一元素x∈A\\（B∪C），则x∈A，且x?B∪C，也就是说x?A，x?B，x?C。所以x∈（A\\B）\\C，由此可见A\\（B∪C）?（A\\B）\\C。 因此A\\（B\\C）。 2）方法一：（A\\B）\\C

=A\\（B∪C） （根据1））

4

=A\\（C∪B） （并运算交换律） =A\\（（C∪B）∩Ⅹ） （0—1律） =A\\（（C∪B）∩（C∪C′）） （0—1律） =A\\（C∪（B∩C′） （分配律） =（A\\C）\\（B∩C′） （根据1） =（A\\C）\\（B∩C） （差集的定义） 方法二：对任一元素x∈（A\\B）\\C，可知x∈A，x?B，x?C，x∈A\\C。又由x?B，x?B\\C，x∈（A\\C）\\（B\\C）\\（B\\C）。所以（A\\B）\\C?（A\\C）\\（B\\C）。 反之，对任x∈（A\\C）\\（B\\C），可知x∈A\\C，x?B\\C。由x∈A\\C，可知x∈A， x?C。又因为x?B\\C及x?C，可知x?B。所以，x∈（A\\B）\\C。因此（A\\B）\\C?（A\\B）\\C。

由此可得（A\\B）\\（B\\C）?（A\\B）\\C。

3）方法一：（A\\C）\\C

=A\\（B∪C） (根据1)) =A\\（C∪B） （并运算交换律） =（A\\C）\\B （根据1））

方法二：对任一元素x∈（A\\B）\\C，可知x∈A，x?B，x?C。由为x∈A，x?C，所以，x∈A\\C。又由x?B，x∈（A\\C）\\B。所以，（A\\B）\\C?（A\\C）\\B。 同理可证得 （A\\C）\\B?（A\\B）\\C。 9. 设A、B是Ⅹ全集的子集，证明： A?B?A′∪B=X?A∩B′=? [解](采用循环证法) (1)先证A?B?A′∪B=X；

方法一：A′∪B=A′∪(A∪B) （因为条件A?B及定理4）

=(A′∪A)∪B （∪的结合律） =(A∪A′)∪B （∪的交换律） =X∪B （互补律） =X （零壹律）

方法二：A?B?A∪B=B （定理4）

?B=A∪B （等号=的对称性） ?A′∪B=A′∪(A∪B) （两边同时左并上A′） ?A′∪B==(A′∪A)∪B （∪的结合律）

5

?A′∪B=(A∪A′)∪B （∪的交换律） ?A′∪B=X∪B （互补律） ?A′∪B=Ｘ （零壹律）

方法三：因为A′?X且B?X，所以根据定理2的3?）就有A′∪B?Ｘ；

另一方面，由于B?A′∪B 及根据换质位律可得B′?A′?A′∪B，因此，由互补律及再次应用定理2的3?），可得X=B∪B′?A′∪B，即X?A′∪B；

所以，A′∪B=Ｘ。 (2)次证A′∪B=X?A∩B′=?；

A′∪B=X?(A′∪B)′=X′ （两边同时取补运算′）

?(A′)′∩B′=X′ （de Morgan律） ?A∩B′=X′ （反身律） ?A∩B′=X′ （零壹律）

(3)再证A∩B′=??A?B；

方法一：A=A∩X (零壹律)

=A∩(B∪B′) (互补律) =(A∩B)∪(A∩B′) (分配律) =(A∩B)∪? (条件A∩B′=?) =A∩B (零壹律) ?B （定理2的3)）

方法二：A∩B′=??B=B∪? (零壹律)

=B∪(A∩B′) （条件A∩B′=?） =(B∪A)∩(B∪B′) (分配律) =(A∪B)∩(B∪B′) (∪的交换律) =(A∪B)∩X (互补律) =A∪B (零壹律) ?A?B （定理4的2)）

10. 对于任意集合A，B，C，下列各式是否成立，为什么？

1） A∪B=A∪C?B=C 2） A∩B=A∩C?B=C

[解] 1）不一定。例如：A={a}，B={a，b}，C={b}。显然有

A∪B=A∪C，但B≠C。

2）不一定。例如：A={a}，B={a，b}，C={b，c}。显然有

6

A∩B=A∩C，但B≠C。

11．设A，B为集合，给出下列等式成立的充分必要条件：

1） A\\B=B 2） A\\B=B\\A 3） A∩B=A∪B 4） A?B=A

[解] 1）A\\B=A∩B′，由假设可知A\\B=B，即A∩B′=B。由此可知B=A∩B′?B′，

故此B=B∩B′=?。

由假设可知A=A\\?=A\\B=B=?。所以当A\\B=B时有A=B=??。 反之，当A=B=?时，显然A\\B=B。 因此A\\B=B的充分必要条件是A=B=?。

2）设A\\B≠∈?，则有元素a∈A\\B，那么，a∈A，而由假设A\\B=B\\A。所以a∈B\\A，从而a?A，矛盾。所以A\\B=，故A?B。另一方面由B\\A=A\\B=?。可得B?A。因此当A\\B=B\\A时，有A=B。 反之，当A=B时，显然A\\B=B\\A=? 因此，A\\B=B\\A的充要条件是A=B。

3）由于A∪B=A∩B，从而A?A∪B=A∩B?B，以及B?A∪B=A∩B?A故此A∪B=A∩B，有A=B。

5） 根据定理6的1）有A??=A，由已知条件A?B=A，可得A?B=A??。 从而由对称差的消去律可得B=?。 反之，若B=?，则A?B=A??=A。 所以A?B=A的充分必要条件为B=?。 12. 对下列集合，画出其文图：

1） A′∩B′ 2） A\\（B∪C）′ 3） A∩（B′∪C） [解]

7

A B X A B C X A B C X A′∩ B′

A \\ (B∪ C ) ′ A∩ (B′∪ C )

13. 用公式表示出下面图中的阴影部分 [解]

14. 试用成员表法证明

1）（A?B）?C=A（B?C） 2）（A∪B）∩（B∪C）?AB′ [解] 1）成员表如下 A B C ０ ０ ０ ０ ０ １ ０ １ ０ ０ １ １ １ ０ ０ １ ０ １ １ １０ １ １ １

成员表中运算结果?Ｃ及Ａ?（Ｂ?Ｃ）的两列状态表明，全集中的每一个体对它俩有相同的从属关系，故 （Ａ?Ｂ）?Ｃ＝Ａ?（Ｂ?Ｃ） 1） 成员表如下：

A B C ０ ０ ０ ０ ０ １ ０ １ ０ ０ １ １ １ ０ ０ １ ０ １ １ １０ １ １ １

8

x A C (A∩C) \\B

B A

C B

x

(A∪B∪C)∪(A∩B∩C)′

A?B ０ ０ １ １ １ １ ０ ０ （A?B）?C ０ １ １ ０ １ ０ ０ １ B?C ０ １ １ ０ ０ １ １ ０ A?（B?Ｃ） ０ １ １ ０ １ ０ ０ １ A∪B （B∪C） (B∪C)′ 1 ０ ０ 0 ０ １ 0 １ １ 1 0 １ 0 1 １ 1 0 １ 1 1 0 1 0 １ (A∪B)∩(B∪C)′ ０ 0 0 ０ １ ０ ０ 0 B′ 1 1 0 0 1 1 0 0 A∩B′ 0 0 0 0 1 1 0 0 成员表中运算结果（A∪B）∩（B∪C）′及A∩B′的两列状态表明，全集中的每一个体，凡是从属（A∪B）∩（B∪C）′的，都从属A∩B′，故 （A∪B）∩（B∪C）′?A∩B

注：自然数集N取为{1，2，3，??，n，??}

9

习题二（第二章 关系）

1．设A={1，2，3，}，B={a，b}求

1）A3B 2）B3A 3）B3B 4）2B3B [解] 1）A3B={（1，a），（1，b），（2，a），（2，a），（3，a），（3，b）}

2）B3A={（a，1），（a，2），（a，3），（b，1），（b，2），（b，3）} 3）B3B={（a，a），（a，b），（b，a），（b，b）} 4）2B={?，{a}，{b}，{a，b}}

2B3B{（?，{a}），（?，b），（{a}，a），（{a}，b），（{b}，a），（{b}，b），（{a，b}，b）}

2．使A?A3A成立的集合A存在吗？请阐明理由。

[解] 一般地说，使A?A3A成立的集合A不存在，除非A=?。

否则 A≠?，则存在元素x∈A3A，故有y1，y2∈A，使x=（y1，y2），从而y1，y2∈A3A，故此有y1，y2，y3，y4，使y1=（y1，y2），y2=（y3，y4），??。这说明A中每个元素x，其结构为元组的无穷次嵌套构成，这不可能。我们讨论的元素的结构必须是由元组的有限次嵌套构成。 3．证明A3B=B3A?A=?∨B=?∨A=B

[证] 必要性：即证A3B=B3A?A=?∨B=?∨A=B

若A3B=?，则A=?或者B=?

若A3B≠?，则A≠?且B≠?，因此对任何x∈A及任何y∈B就有（x，y）∈A3B，根据A3B=B3A，可得（x，y）∈B3A，故此可得x∈B，y∈A，因此而得A?B且B?A，所以由?的反对称性A=B。

充分性：即证A=?∨B=?∨A=B?A3B=B3A 这是显然的。 4．证明（A∩B）3（C∩D）=（A3C）∩（B3D）

[证]证法一：（元素法）对任一（x，y）∈（A∩B）3（C∩D） 有x∈A∩B，y∈C∩D，于是x∈A，x∈B，y∈C，y∈D。因而（x，y）∈A3C，且（x，y）∈B3D，所以（x，y）∈（A3C）∩（B3D）。因而（A∩B）3（C∩D）?（A3C）∩（B3D）

另一方面，对任一（x，y）∈（A3C）∩（B3D），于是有（x，y）∈A3C且（x，y）∈B3D，因而x∈A，y∈C，x∈B y∈D。所以x∈A∩B，y∈（C∩D）。所以（x，y）∈（A∩B）3（C∩D）。因而（A3C）∩（B3D）?（A∩B）3（C∩D）。

10

综合这两个方面有（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个子集，而每个子集都是A上的一个二元关系。

10．定义在整数集合I上的相等关系、“≤”关系、“＜”关系，全域关系，空关系，

是否具有表中所指的性质，请用Y（有）或N（元）将结果填在表中。 性质 关系 相等关系 ≤关系 ＜关系 全域关系 空关系 4）

自反的 Y Y N Y N 反自反的 N N Y N Y 对称的 Y N N Y Y 反对称的 Y Y Y N Y 传递的 Y Y Y Y Y 1??0?0 R4???03??4??1?2100?001?? 010??000?R4是反对称的，循环的。 5）

1??23??0?0 R5???0??4?1111?011?? 001??000?R5是反自反的，反对称的，传递的。 6）

1??23?

?1?1 R6???1??4?115

111?111?? 111??111?

R6是自反的，对称的，传递的，循环的。从而是等价关系。 7）

1??23??0?0 R7???0??4?0000?000?? 000??000?R7是反自反的对称的，传递的，循环的，反传递的，反对称的。

12．设A是A上的关系，证明 1）R是自反的当且反当IA?R

2）R是反自反的当且仅当IA∩R=?

?3）R是对称的当且反当R=R

4） R是反对称的当且仅当R∩R?IA 5）R是传递的当且仅当R?R?R [证] 1）必要性

若R是自反的，则对任何x∈A，都有（x，x）∈R，但是IA={（x，x）|x∈A}，所以IA?R。

充分性

若IA?A则由IA={（x，x）|x∈A}，可知对任何x∈A，都有（x，x）∈R，所以R是自反的。 2）必要性

若R是反自反的，则对任何x∈A，都是（x，x）?R，从而（x，x）∈R′，由IA={（x，x）|x∈A} 可知IA?R′。于是IA∩R?R′∩R=?，另外??IA∩R，所以IA∩R=?。

充分性

若IA∩R=?，则R是反自反的。否则，不是反自反的，那么应存在某一x0

∈A，使得（x0，x0）∈R。但是（x0，x0）∈IA，从而（x0，x0）?。这不可能，矛盾。 3）必要性，

若R是对称的，则对任何（x，y）∈R，就有（y，x）∈R。于是根据逆

????关系的定义，可得（x，y）∈R，于是R?R；对任何（x，y）∈R，由逆关

?系的定义，可得（y，x）∈R。再次利用R的对称性有（y，x）∈R，于是R?

16

?R；综合两方面，有R=R。

充分性

若R= R，则对任何（x， y）∈R，由R=R可得（x，y）∈R。从而由逆关系的定义，可知（y，x）∈R这说明R是对称的。 4）必要性

???∈R，从逆关系的定义，就有（x， y）∈R及（y，x）∈R，因此，利用R的反对称性，可得x=y。于是就有（x，y）=（x，x）∈IA，所以R∩R?IA。 充分性

??若R是反对称的，则对任何（x，y）∈R，即有（x， y）∈R及（x，y）

???若R∩R ?IA，则对任何（x，y）∈R及（y，x）∈R，从逆R关系的定

???义，可得（x，y）∈R及（x，y）∈R，也即（x，y）∈R∩R，利用R∩R =IA

可得（x，y）∈IA，于是x=y。所以R是反对称的。 5）必要性

若R是传递的，则对任何（x，y）RоR，由复合关系的定义可知，存在着y∈A，使（x，y）∈R且（y，y）∈R，从而利用R的传递性，可知（x，y）∈R。所以

RоR?R。

充分性

RоR。从而利用RоR?R可得（x，y）∈R。所以R是传递的。 证法二： 1)?):对任何x，

x∈A

?(x,x)∈IA (IA是幺关系，因此是自反关系) ?(x,x)∈R (R是自反关系) 所以 IA?R ； ?):对任何x∈A，

x∈A

?(x,x)∈IA (IA是幺关系，因此是自反关系) ?(x,x)∈R (因IA?R) 所以，R是自反关系； 2)?)首先 ??IA?R ；

其次，对任何x，y∈A，若

17

(x,y)∈IA?R ?(x,y)∈IA?(x,y)∈R

?x=y?(x,y)∈R (IA是幺关系，因此是自反关系) ?(x,x)∈R

则与R是反自反关系，(x,x)?R矛盾。故IA?R?? ； 因此，由包含关系?的反对称性，可得 IA?R=? ； ?):对任何x∈A，若

(x,x)∈R

?(x,x)∈IA?(x,x)∈R ?(x,x)∈IA?R

?(x,x)∈? 则与空集不含任何元素，(x,x)??矛盾。 故对任何x∈A，(x,x)?R ； 所以，R是反自反关系； 3)?)对任何x，y∈A

(x,y)∈R

?(y,x)∈R ?(x,y)∈R?

所以，R=R?；

?):对任何x,y∈A

(x,y)∈R

?(x,y)∈R? ?(y,x)∈R 所以，R是对称的； 4)?)对任何x，y∈(x,y)∈R?R?A

?(x,y)∈R?(x,y)∈R? ?(x,y)∈R?(y,x)∈R

?x=y ? (x,y)∈IA 所以，R?R??IA ； ?):对任何x,y∈A

18

(IA是幺关系，因此是自反关系) (因IA?R=?) (R是对称关系)

(R=R?)

(R是反对称关系) (IA是自反关系) ???(x,y)∈R (R=R)

?(y,x)∈R 所以，R是对称的；

13．设A、B为有穷集合，R，S?A3B，MR=（xij）m3n，MS=（yij）m3n

1）为了R?S，必须且只须?i?j（xij≤ yij）

2）设MR∪S=（Zij）m3n，那么Zij=xijVyij，I=1，2??，m，j=1，2，??n. 3）设MR∩S=（tij）m3n，那么tij=xij^yij i=1，2，??m；j=1，2，??，n. [证] 由于A、B是有穷集合，不妨设

A={a1，a2??，am}，B={b1，b2，??，bn} 1）必要性

若R?S，则对任何i∈{1，2，??，m}，对任何j∈{1，2，??n}，若（ai，bj）∈R，则R的关系矩阵MR=（xij）m3n中第I行第j列元素xij=1，根据R?S，可得（ai，bj）∈S，从而得S的关系矩阵MS=（yij）m3n中第I行第j列元素yij=1，由于是1≤1故此xij≤yij；若（ai，bj）?R，则R的关系矩阵MR=（xij）m3n中第i行第j列元素xij=0，因此由S的关系矩阵MS=（yij）m3n中第j列元素yij≥0，可得xij≤yij。总之，有（?i）(?j)（xij≤yij）。 2）充分性

若（?i）(?j)（xij≤yij），则对任何（ai，bj）∈R，就有R的关系

矩阵MR=（xij）m3n中第i行第j列元素xij=1，由于xij≤yij，所以yij≥1，故此yij≥1这说明S的关系矩阵MS=（yij）m3n中第i行第j列元素yij为1，因此必有

（ai，bj）∈S，所以R?S。

2）对任何i∈{1，2，??，m}，对任何j∈{1，2，??，n}若Zij=1，则（ai，bj）∈R∪S，故此（ai，bj）∈R或者（ai，bj）∈S，于是xij=1或者yij=1。从而 bj）?S，于是xij=0且yij=0。从而xij∨yij=0。因而Zij=xij∨yij=0； 综合上述两种情况，就有zji=xij∨yij，i=1，2，??，m，j=1,2,??n，。 3）对任何i∈{1，2，??m}，对任何j∈{1，2，??，n}。若tij=1，则（ai，bj）∈R∩S，故此（ai，bj）∈S且（ai，bj）∈S，于是xij=1，且yij=1从而xij∧yij=1。因而tij=xij∧yij=1；若tij=0，则（ai，bj）?R∩S，故此（ai，bj）?S，于

(x,y)∈R

19

是xij=0或者yij=0，从而xij∧yij=0。因而tij=xij∧yij=0。

综合上述两种情况，就有tij=xij∧yij，i=1，2，??，m，j=1，2，??，n。 14．设A={1，2，3，4}，R1，R2为A上的关系，R1={（1，1），（1，2），（2，4）}，

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

[解] MR1?1?0???0??0100??0?0001?? ，MR??2?0000???000??0001010100?1?? 0??0?1）

MR1?R2?MR1?1?0?MR2??0??0100000000??0?01????0??0??0??0001001001??00?001????0??00??0??0010001?0?? 0??0?1?2?3?4?

1?2?3?4?R1 R2

1?2?3?4??0?0?MR1??0??0

无论从复合关系图还是从复合关系矩阵 都可得R1оR2={（1，3），（1，4）}

2）MR2?R1?MR2001001001??1?01????0??0??0??0100000001??0?01????0??0??0??0000000000?0?? 1??0?

1?2?3?4?

1?2?3?4?R2 R1

1?

2?3?4? 无论从复合关系图还是从复合关系矩阵 都可得R2оR1={（3，4）}

20

本文来源：https://www.bwwdw.com/article/bux.html