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

离散数学辅助教材

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

第一部分

集合论

刘国荣

交大电信学院计算机系

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

3）MR2?R1?MR2?0?0?MR1??0??0000010001??1?00????0??0??0??0100000001??0?01????0??0??0??0000000000?0?? 0??0?1?2?3?4?

1?2?3?4?

1?2?3?4? 无论从复合关系图还是从复合关系矩阵 都可得R1оR2оR1=?

MR3?MR1?MR1?MR11?11?00???00??0000??11?0001????00??00??00??0001??11?0001????00??00??00??0000?01??00??00?

4）

?11?00???00??00

01??11?0000????00??00??00??0000??11?0001?0???00??00??0??0000000?0??0??0?1?2?3?4?

????

????

?1?2?3?4

无论从复合关系图还是从复合关系矩阵

3都可得R1оR1оR1={（1，1），（1，2）， （1，4）}

R1 R1 R1

15）设R1，R2，R3是A上的二元关系，如果R1?R2，证明

1）R1?R3?R2?R3 2）R3?R1?R3?R2

[证明] 1）对任何（x，y）∈R1R3，由复合关系之定义，必存在z∈A，使得（x，z）

∈R1且（z，y）∈R3，利用R1?R2可知（x，z）∈R2且（z，y）∈R3，再次利用复合关系之定义，有（x，y）∈R2?R3。所以R1?R3?R2?R3。 2）对任何（x，y）∈R3?R1，由复合关系之定义，必有z∈A，使得（x，z）

21

∈R3且（z，y）∈R1，再由复合关系之定义，有（x，y）∈R3?R2。所以R3?R1?R3?R2。

16．设A是有限个元素的集合，在A上确定两个不同的关系R1和R2，

2使得R1=R1，R22=R2

2因为，令R1=?，则R1?R1=?，故此R1=R1=?。

22令R2=A3A，则R2=R2?R2?A3A=R2，故需证明R2?R2οR2=R2。为此，

对任何x，y∈A，（x，y）∈A3A=R2，一定存在着z∈A（至少有z=x或z=y存在），使（x，z）∈A3A=R2且（z，y）∈A3A=R2，故此（x，y）R2?R2=R2，所以R2?R2?R2=R2。于是R2=R2=A3A。

2）由于A是有限个元素的集合，是不心设A={a1，a2，??an}

令R1={（ai，aj）|ai∈A∧aj∈A∧|≤i≤n∧|≤j≤n-|} R2={（an，an）∪R1}

则R1R2，即R1与R1是不同的关系。我们来证明R1=R1，R2=R2， （a）先征R1=R1

若（ai，aj）∈R1，则由R1的定义必定1≤i≤n，1≤i≤n-1，并且一定存在着1≤k≤n-1（至少有k=j存在），使（ai，ak）∈R1且（ak，aj）∈R1，从而（ai，aj）∈R1?R1=R1。故此R1?R1。

若（ai，aj）∈R1= R1?R1，则存在着k，1≤k≤n-1，使（ai，ak）∈R1且（ak，aj）∈R1，于是由R1的定义，必有1≤i≤n，1≤j≤n-1，从而根据R1的定义，有（ai，aj）∈R1。故此R1= R1 综合两个方面，可得R1= R1。 （b）次证R2=R2

若（ai，aj）∈R2，则由R2的定义，要么1≤i≤n，1≤j≤n-1，要么I=n，j=n 若1≤i≤n，1≤j≤n-1，则一定存在着1≤k≤n-1（至少有k=j存在），使（ai，ak）∈R2且（ak，aj）∈R2，从而（ai，aj）∈R2οR2=R2；若i=n，j=n，则（ai，aj）=（an，an）∈R2，那么（an，an）∈R2，所以（ai，aj）=（an，an）∈R2οR2=R2因此R2=R2。

若（ai，aj）∈R2= R2οR2，则存在着k，使（ai，ak）∈R2且（ak， ai）∈R2，于是由R2的定义，有k=n或者1≤k≤n-1。

若k=n，则由（ai，ak）∈R2必有I=n，所以无论1≤j≤n-1还是j=n，由R2

的定义，有（ai，aj）=（an，aj）∈R2；

若1≤k≤n-1，则由（ai，ak）∈R2必有1≤j≤n-1故此（ai，aj）∈R2总之

2222222222222222 22

?17．设R是集合A上的反对称关系，|A|=h，指了在R∩R的关系矩阵中有多少个非

零值？

的关系矩阵中非零值最多不超过n个。

18．设R1和R2是集合A上的关系，判断下列命题的真假性，并阐明理由。

1） 如果R1和R2都是自反的，那么R1?R2是自反的。 2） 如果R1和R2都是反自反的，那未R1?R2是反自反的。 3） 如果R1和R2都是对称的，那末R1?R2是对称的。 4） 如果R1和R2都是反对称的，那末R1?R2是反对称的。 5） 如果R1和R2都是传递的，那末R1?R2是传递的。

[解] 1）真。由于R1和R2和R2都是自反的，因而对任何，都有（x，x）∈R1，（x，x）

∈R2。因此，对任何x∈A，都有（x，x）∈ R1?R2。所以R1?R2是自反的。 2）假。令A={a，b}，R1={（a，b）}，R2={b，a}。那么R1?R2={（a，a）}，它就不是A上的反自反关系。

3）假。令A={a，b，c}，R1={（a，b），（b，a）}，R2={（b，c），（c，b）}。那末R1?R2={（a，c）}，就不是A的对称关系。 4）假。令A={a，b，c，d}，R1={（a，c），（b，c）}

R2={（c，b），（d，a）}易证R1，R2都是反对称关系。但是R1?R2={（a，b），（b，a）}就不是A上的反对称关系。

5）假。令A={a，b，c}，R1={（a，c），（b，a），（b，c）}，R2={（c，b），（a，c），（a，b）}，易证R1和R2都是传递关系，但R1?R2={（a，b），（b，b），（b，c）}就不是A上的传递关系。

19．设A={1，2，3，4，5}，R?A3A，R={（1，2），（2，3），（2，5），（3，4），（4，3），（5，5）}用作图方法矩阵运算的方法求r（R），s（R），t（R）。 [解] 1）作图法：

R5 的关系图 （R）的关系图

5

2证得R22= R2，综合两方面，我们证明了R2= R2。

[解] 由第12题的4） R是反对称关系当且反当R∩R?IA，及|A|=n可知，在R∩R

??4 1

4 1

3 2

23

3 2 5 5 4

4

1

2 1

3 2 3

S（R）的关系图 t（R）的关系图

因此：

r（R）={（1，1），（1，2），（2，2），（2，3），（2，5），（3，3），（3，4），（4，3），

（4，4），（5，5）}

s（R）={（1，2），（2，1），（2，3），（2，5），（3，2），（3，4），（4，3），（5，2），

（5，5）}

t（R）={（1，2），（1，3），（1，4），（1，5），（2，3），（2，4），（2，5），（3，3），

（3，4），（4，3），（4，4），（5，5）} 2）矩阵运算法：

?0??0??0??0??0?

?1000?0101?001010000?0? ?0??1??MR?

?1?0?MIAVMR=?0??0??00100000100000100??0?00???0?V?0??0??01????01000001010001000??1?01???0???0??0??01????01100000110001100?0??0? ?0?1??Mr（R）=MIAUR?

24

?0?0??=M?=?0MS（R）=MRURRVMR??0??01000001010001000??0?0???10?V?0??0??01????00010000010001000??0?0???10???0??0??01????01010101010001000?1??0? ?0?1??

?0?0?MR2=MRοR=MR?MR=?0??0??01000001010001000??0?00???0???0??0??01????01000001010001000??00?001???0???00??0??001????0010010011001?1??0? ?0?1??

?0?0?MR3=MR2?R=MR2?MR=?0??0??00100010100010101??0?1???00???0??0??01????01000001010001000??00?1???000???00??0??001????0001010101001?1??0? ?0?1??

?0?0???0??0??00000001010101001??0?1???00???0??0??01????01000001010001000??00?1???000???00??0??001????0010100010101?1??0??MR2?0?1??MR4?MR3?R?MR3?MR

25

?0?0?Mt(R)?MRUR2UR3?MRVMR2VMR3??0??0?0??0?0???0??0?0?1111?0111??0110??0110?0001??1000??0?00101???0001?V?0??0100??0?0001???00101??0?00011???0100?V?0??0010??0?0001???00011?0101??0010??0100?0001??

因此r（R），s（R），t（R）与1）作图法一致。 20．设R?A3A，证明

1）（R+）++R+2）=R*

[证明] 1）一方面，由于（R+）+是R+的传递闭包，所以R+?（R+）+；另一方面，

由于R+是R的传递闭包，故此R+是传递的。由于R+?R+及传递闭包（R+）+是包含R+的最小传递关系，就有（R+）+?R+（定理4之3）；所以（R+）+=R+。 2）一方面，由于（R*）*是R*的自反传递闭包，所以R*?（R*）*；另一方面，由于R*是R的自反传递闭包，故此R*是自反的传递的。由于R*?R*及自反传递闭包（R*）*是包含R*的最小自批传递关系，就有（R*）*?R*（定理5的3））。所以（R*）*=R*。

21．设A={1，2，3，4}，RAA，R={（1，2），（2，4），（3，4），（4，3），（3，3）} 1）证明R不是传递的；

2）求R1，使 R1?R并且R1是传递的；

3）是否存在R2，使R2?R，R2≠R1并且R2是传递的。

[解] 1）由于（1，2）∈R且（2，4）R但（1，4）? R，这说明R不是传递的。

2)由于R+是包含R的最小传递关系，所以，取R1=R+即为所求。现在来R+ R2={（1，4），（2，3），（3，3），（3，4），}（4，3），（4，4）} R3={（1，3），（2，3），（2，4），（3，3），（3，4），（4，3），（4，4）} R4={（1，3），（1，4），（2，3），（2，4），（3，3），（3，4），（4，3），（4，4）} 故此R1=R+=R∪R2∪R3∪R4={（1，2），（1，3），（1，4），（2，3），（2，4），（3，

3），（3，4），（4，3）（4，4）}（因为|A|=4有限） 其关系图如下：

26

1 2

1

2

3 4

3

4

R的关系图 R1的关系图

3）能。因为R1并非全关系（否则，当R1是全关系时，就找不到了），所以只要取

R2=A3A是A上的全关系就可满足R2?R，R2≠R，并且全关系R2显然是一个传递关系。

22．设A={1，2，3，4??，9}，定义A3A上的关系如下：

（a，b）R（c，d）∷ a+d=b+c 1） 证明R是A3A上的等价关系； 2） 求[（2，5）]R；

3） R?A3A对吗？请阐明理由。 1）[证明] （a）R是自反的

对于任何（a，b）∈A3A，由于a+b = b+a，所以（a，b）R（a，b）。

（b）R是对称的

对于任何（a，b），（c，d）∈A3A，若（a，b）R（c，d），则有a+d = b+c从而c+b+a，所以可得（c，d）R（a，b）。 （c）R是传递的

对于任何（a，b），（c，d），（e，f）∈A3A，若（a，b）R（c，d），且（c，d）R（e，f），于是有a+d = b+c及c+f = d+e，二式相加有a+f+c+d = b+e+c+d，两边同时减c+d，可得a+f = b+e，从而可得（a，b）R（e，f）。 综合（a）、（b）、（c）、说明R是A3A上的等价关系。

2）[解] 因为{（2，5）}R = {（a，b）|（a，b）∈A3A（a，b）R（2，5）} = {（a，b）|（a，b）∈A3A∧a+5 = b+2} = {（a，b）|（a，b）∈A3A∧b = a+3}

={（1，4），（2，5，（3，6），（4，7），（5，8），（6，9））

27

3）[答] R?A3A不对。因为R是A3A上的关系，所以R?（A3A）3（A3A）=(A?A)2。

23．设A是一个非空集合，R?A3A。如果R在A上是对称的，传递的，下面的推

导说明R在A上是自反的：

对任意的a，b∈A，由于R是对称的，有： aRb?bRa

于是aRb?aRb∧bRa，又利用R是传递的，得： aRb∧bRa?aRa 从而说明R是自反的。 上述推导正确吗？请阐明理由。

[答] 上述推导不正解。推殖民地的谬论误在于假设A的每个元素都由R关联着A的某一别的元素。如果这不是真的，那么对称性的条件的假设就始终是假的，因此结论当然是假的。因而在一个空集上的空关系都是平凡的对称和可传递，但不是自反的。另外关系{（a，a），（b，b），（a，b），（b，a）}是自反的和传递的，但在集合{a，b，c}上不是自反的。

24．设R是集合A上的等价关系，证明R也是集合A上的等价关系。 [证明] 证法一：

?? （a）R是自反的

对任意的a∈A，由于R是自反的，所以（a，a）∈R，再由逆关系的定义有（a，a）∈R

??对任何（a，b）∈R由逆关系的定义，有（b，a）∈R,由R的对称性，可

?得（a，b）∈R，再由逆关系的定义，就有（b，a）∈R。

?（c）R是传递的

??对任何（a，b）∈R及（b，c）∈R，由逆关系的定义，有（b，a）∈R

及（c，b）∈R，根据R的传递性，可得（c，a）∈R，再次由逆关系的定义，就有（a，c）∈R。 证法二：

?（b）R是对称的

?综合（a）（b）（c）可知R是等价关系。

??R（a）是自反的：

对任何a，a?A

?(a,a)?R (R都是自反的)

??(a,a)?R

28

?所以，R是自反的；

?R（b）是对称的：

对任何a，b?A，(a,b)?R?

?(b,a)?R

?(a,b)?R (R是对称的)

所以，R是对称的；

???(b,a)?R

?（c）R是传递的：

对任何a，b，c?A，

??(a,b)?R?(b,c)?R

?((b,a)?R?(c,b)?R

?((c,b)?R?(b,a)?R (?的交换律) ?(c,a)?R (R是传递的)

?R?(a,c)? (R是对称的)

?所以，R是对称的；

?综合（a）、（b）、（c），可知R是A上的等价关系。

25．设R1和R2都是集合A上的等价关系

1）证明R1∩R2也是A上的等价关系；

2）用例于证明R1∪R2不一定是A上的等价关系（要尽可能小地选取集合A）。 [证] 1）证法一：

（a）R1∩R2是自反的

对任何a∈A，由于R1，R2都是A上的自反关系，所以（a，a）∈R1（a，a）∈R2，因此（a，a）∈R1∩R2

（b）R1∩R2是对称的

对任何的（a，b）∈R1∩R2，就有（a，b）∈R1且（a，b）∈R2，由R1，R2都是A上的对称关系，所以（a，b）∈R1且（b，a）∈R2，所以（b，a）∈R1∩R2。

（c）R1∩R2是传递的

对任何的（a，b）∈R1∩R2及（b，c）∈R1∩R2，就有（a，b）∈R1，（a，b）∈R2及（b，c）∈R1，（b，c）∈R2，于是（a，b）∈R1且（b，c）∈R1及（a，b）∈R2且（b，c）∈R2由于R1，R2都是A上的传递关系，所以（a，c）∈R1及（a，c）∈R2，因此（a，c）∈R1∩R2。

29

综合（a），（b），（c），可知R1∩R2是等价关系。 证法二：

（a）R1∩R2是自反的： 对任何a，a?A

?(a,a)?R1?(a,a)?R2 (R1，R2都是自反的) ?(a,a)?R1?R2

所以，R1?R2是自反的； （b）R1∩R2是对称的： 对任何a，b?A，(a,b)?R1?R2

?(a,b)?R1?(a,b)?R2

?(b,a)?R1?(b,a)?R2 (R1，R2都是对称的) ?(b,a)?R1?R2

所以，R1?R2是对称的； （c）R1∩R2是传递的： 对任何a，b，c?A，

(a,b)?R1?R2?(b,c)?R1?R2

?((a,b)?R1?(a,b)?R2)? ((b,c)?R1?(b,c)?R2)

?((a,b)?R1?(b,c)?R1)? ((a,b)?R2?(b,c)?R2) (?的结合律、交换律) ?(a,c)?R1?(a,c)?R2 (R1，R2都是传递的) ?(a,c)?R1?R2 所以，R1?R2是对称的；

综合（a）、（b）、（c），可知R1?R2是A上的等价关系。

2）两个自反的（对称的）关系的并将是自反的（对称的），但是，两个传递关系的并却未必是传递的。我们就从破坏传递性出发来构造反例： 令R1={（a，a），（b，b），（c，c），（a，b），（b，a）} R2={（a，a），（b，b），（c，c），（b，c），（c，b）} 当A={a，b，c}时，R1，R2显然都是等价关系。但是

R1∪R2={（a，a），（b，b），（c，c），（a，b），（b，a）（b，c），（c，b）}都不是A上的等价关系，因为R1∪R2不传递：（a，b）∈R1∪R2且（bc，但（a，c）?R1∪R2；同样（c，b）∈R1∪R2且（b，a）∈R1∪R2，但（c，a）?R1∪R2。

a a

c

a b b 30 c b c

R1关系图 R2关系图 R1∪R2关系图

而且|A|不可能再少了。因为任何少于3个元素的集合上的自反，对称关系一定是传递的！

26．设R是A上的等价关系，将A的元素按R的等价类顺序排列，请指出此等价关

系R的关系矩阵MR有何特征？

[解] 将A的元素按其上的等价关系R的等价类顺序排列，这样产生的等价关系R的

关系矩阵MR，经过适当的矩阵分块，MR的分块矩阵将成为准对角阵，准对角阵的对角线上的每一块都是一个全1方阵，它正好对应于等价关系R的一个等价块。

27．设A是n个元素的有限集合，请回答下列问题，并阐明理由。

1） 有多少个元素在A上的最大的等价关系中？ 2） A上的最大的等价关系的秩是多少？ 3） 有多少个元素在A上的最小的等价关系中？ 4） A上的最小的等价关系的秩是多少？

[答] 1）A上最大的等价关系是全关系R1=A3A={（a，b）|a∈A∧b∈A}因此有n2

个元素在A上的最大的等价关系R1中，因为所有n2个二元组都在R1=A3A中。

2）A上的最大的等价关系R1的秩是1。这是因为A中任何两个元素都有全关系R1=A3A，因此R1的等价块包含了A的所有元素，A的所有元素都在同一个等价块中。

3）A上的最小的等价关系是么关系R2=IA={（a，a）a∈A}因此它中有n个元素，即n自反对。

4）A上的最小的等价关系的秩是n，因为么关系的每一个元素都自成一个等价

块，每一等价块中也只有一个元素。

28．设R1和R2是非容集合A上的等价关系，对下列各种情况，指出哪些是A上的

等价关系；若不是，用例子说明。 1) A3A\\R1 2) R1\\R2 3) R1

4）r（R1\\R2） （R1\\R2的自反闭包） 5）R1?R2

2 31

[解] 1）不是。设A={a}，并且R1={（a，a）}，则R1是A上的等价关系，但A3

A\\R1={（a，a）\\（a，a）}=?就不是A上的等价关系，因为空关系不是自反的。

2）不是。设A={（a，b）}并且R1={（a，a），（b，b），（a，b），（b，a）}，

R2={（a，a），（b，b）}，则R1，R2都是A上的等价关系，但是，R1\\R2={（a，b），（b，a）}就不是A上的等价关系，因为R1\\R2不自反。 3）是。

证法一：因R1是等价关系，因而R1是传递的，故此由第12题之5）有R1= R1?R1?R1。另一方面，结任何（a，b）∈R1，由于R1是自反的，故此（b，b）∈R1，从而由复合关系之定义，有（a，b）∈R1?R1，所以R1?R1，从而R1=R1，因此由R1是等价关系，知R1也是等价关系。 证法二：

一方面，对任何a，b?A，(a,b)?R1

?(?c?A)((a,c)?R1?(c,b)?R1)

?(?c?A)((a,b)?R1) (R1是传递的) ?(a,b)?R1(带量词的基本逻辑等价式：(?x)p?p)

所以，R1?R1 ；

另一方面，对任何a，b?A，(a,b)?R1

?(a,b)?R1?(b,b)?R1) (R1是自反的) ?(a,b)?R1

所以，R1?R1 ；

综合这两方面，就有R1=R1 ；

4）是。设A={a，b，c}，R1={（a，a），（b，b），（c，c），（a，b），（b，a），（a，c）（c，a），（b，c），（c，b）}。R1={（a，a），（b，b）（c，c）（a，a）（c，a）}，则R1，R2都是A上的等价关系。 R1\\R2={（a，b），（b，a），（b，c），（c，b）}

r（R1\\R2）={（a，a），（b，b），（c，c），（a，b），（b，a），（b，c），（c，b）}因此r（R1\\R2）不是A上的等价关系，因为r（R1\\R2）不是传递的，（a，b）∈r（R1\\R2）且（b，c）∈r（R1\\R2），但是（a，c）?r（R1\\R2）。

5）不是。令A={a，b，c}，R1={（a，a），（b，b），（c，c），（a，b），（b，a）}，R2={（a，a），（b，b），（c，c），（a，b），（b，a），（b，c），（c，b），（a，c）}不上的等价关系，因为R1?R2不对称，（a，c）∈R1?R2，但（c，a）?R1?R2。

222222222 32

29．设A={1，2，3，4}，请指出A上所有等价关系是多少？并阐明理由。

[解] A上的等价关系共有14个。根据A上的划分与A上的等价关系一一对应的原理，

我们只需求出A上有多少个划分就行了。

{{a}，{b}，{c}，{d}}型划分，一个； {{a，b}，{c}，{d}}型划分，六个； {{a，b，}，{c，d}}型划分，三个； {{a，b，c}，{d}}型划分，四个； {{a，b，c，d}}型划分，一个。 总计：1+6+3+4+1=15 。

30．设A={1，2，3，4，5，6}，确定A上的等价关系R，使此R能产生划分{{1，2，

3，}，{4}，{5，6}}

[解] 这样的R={（1，1），（2，2），（3，3），（1，2），（2，1），（1，3），（3，1），（2，3），（3，2），（4，4），（5，5），（6，6），（5，6），（6，5）}

1 4 5 6 2 3

R的关系图 31．设R是集合A上的关系

R是循环∷＝（?a∈A）（?b∈A）（?c∈A）（aRb∧bRc?cRa） 证明：R是自反的和循环的，当且仅当R是等价关系。 [证] 证法一：

必要性

若R是自反的和循环的，我们来证R是等价关系，为此证明 （a）R是自反的。

必要性条件所给。 （b）R是对称的

对任何（a，b）∈R，由于R是自反的，所以（b，b）∈R，再根据R是循环的可得（b，a）∈R。 （c）R是传递的

对任何（a，b）∈R，（b，c）∈R，由于R是循环的，所以（c，a）∈R，

33

利用R是对称的，就得到（a，c）∈R。 充分性

若R是等价关系，我们来证R是自反的和循环的。 1）R是自反的。

因R是等价关系，故R是自反的。 2）R是循环的

对任何（a，b）∈R，（b，c）∈R，由于R是传递的，所以（a，c）∈R。 由于R是对称的，（c，a）∈R。 证法二： ?)：

（a）R是自反的：已知； （b）R是对称的： 对任何a，b?A，(a,b)?R

?(a,b)?R?(b,b)?R (R是自反的) ?(b,a)?R (R是循环的)

所以，R是对称的； （c）R是传递的：

对任何a，b，c?A，(a,b)?R?(b,c)?R

?(c,a)?R (R是循环的) ?(a,c)?R (R是对称的)

所以，R是传递的；

综合（a），（b），（c）可知R是等价关系； ?)：

（a）R是自反的：

因为R是等价关系，所以R是自反的； （b）R是循环的：

对任何a，b，c?A，(a,b)?R?(b,c)?R

?(a,c)?R (R是传递的) ?(c,a)?R (R是对称的)

所以，R是循环的；

32．设∏1和∏2是非空集合A的划分，说明下面各种情况哪些是A的划分？哪些不

34

是A的划分？哪些可能是A的划分？并阐明理由。 1）∏1∪∏2 2）∏1∩∏2 3）∏1\\∏2

4)（∏1∩（∏2\\∏1））∪∏1

[解] 1）可能。如果∏1=∏2，则∏1∪∏2是A的划分；如果，∏1≠∏2，则∏1∪∏2

不是A的划分；例如A={a，b}，∏1={{a}，{b}}，∏2={{a，b}}，但∏1∪∏

2={{a}，{b}，{a，b}}就不是

A的划分，因为{a}∩{a，b}={a}≠?，就不是

A的划分，因为{a}∩{a，b}={a}≠?。

2）可能。如果∏1=∏2，则∏1∩∏2是A的划分；如果，∏1≠∏2，则∏1∩∏2

不是A的划分；例如A={a，b}，∏1={{a}，{b}}，∏2={{a，b}}，∏1∩∏2=?，就不是A的划分。

3）可能。如果∏1∩∏2=?，则∏1\\∏2=∏1是A的划分；如果∏1∩∏2≠?，则

∏1\\∏2不是A的划分；例如A={a，b，c}，∏1={{a}，{b}，{c}}，∏2={{a}，{b，c}}，∏1∩∏2={{a}}因此∏1\\∏2={{b}，{c}}就不是A的划分。因为{b}∪{c}={b，c}≠A。

4）是。因为（∏1∩（∏2\\∏1））∪∏1=?∪∏1=∏1，是A的划分。

33．对下列集合上的整除关系画出哈斯图，并对3）中的子集{2，3，6}，{2，4，6}，

{4，8，12}找出最大元素，最小元素，极大元素，极小元素，上确界，下确界。 1）{1，2，3，4}

2）{2，3，6，12，24，36}

3）{1，2，3，4，5，6，7，8，9，10，11，12} [解]

24

4

3 2 1 12

6 2

3 36

1）的Hasse图 2）的Hass图

在3）的Hasse图中可以看出， ①{2，3，6}的最大元素为6；极大元

8

10 4 6 9 12 35

7 5 2 3 11

编码方法如下图所示

1

2

6

7

15 16

28 （1，1） （1，2） （1，3） （1，4） （1，5） （1，6） （1，7） 3 5 8 14 17 27 30 （2，1） （2，2） （2，3） （2，4） （2，5） （2，6） （2），7 4 9 13 18 26 31 43 （3，1） （3，2） （3，3） （3，4） （3，5） （3，6） （3，7） 10 12 19 25 32 42 49 （4．1） （4，2） （4，3） （4，4） （4，5） （4，6） （4，7） 11 20 24 33 41 50 62 （5，1） （5，2） （5，3） （5，4） （5，5） （5，6） （5，7） 21 23 34 40 51 61 72 （6，1） （6，2） （6，3） （6，4） （6，5） （6，6） （6，7） 22 35 39 52 60 73 85 （7，1） （7，2） （7，3） （7，4） （7，5） （7，6） （7，7） …

… …

… … … …… 第5题3）的图（b）

4）构造f：IIN，f（r，s）=n r，s∈I

其中：k=| r |+| s | l=1+2k（k+1）

(l?3k?1)?r,当S?0时 n=???(l?k?1)?r,当S?0时 则f-1：N→I3I，f-1（n）=（r，s），n∈N

其中：寻找k满足不等式1+2k（k-1）＜n≤1+2k（k+1）

令l：=1+2k（k+1） 若| n1 |≤k，则令 r =n1

n1：=n-（l-3k+1）=（3k-1）-（l-n） s：=k-| r | n2：=n-（l-k+1）=（k-1）-（l-n） 若| n2 |＜k，则令 r：=-n2 s：= -（k-| r |） 5）构造f：R→（0，∞），f（x）=ex，x∈R

46

则f-1：（0，∞）→R，f-1（x）=lnx，x∈（0，∞） 6）构造f：（-1，1）→R， f（x）= -

x，x∈（-1，1）

(x?1)(x?1)则f -1：R→（-1，1）， f -1（x）=

2y4y?1?12， x∈[0，1]

7）构造f：[0，1] →(,)，f=goh 其中：h：[0，1] →，h（x）= g：[,](,)

11421（x+1），x∈[0，1] 411421142??r1??r2 g（x）=???ri?2??x1142141,当x?2,当x?,当x?x?ri(i?1,2),否则

这里r1，r2，?，rn?(,)是该区间内所有的有理数。 于是：f –1=(,)→[0，1] 其中：g-1：(,)→[,]

114211421142?1?4?1?-1

g（x）=?2?r?i?2??x，当x?r1，当x?r2，当x?ri(i?3，4，?)，否则

r1，r2，?，rn?∈(,)为该区间内所有有理数。

1142 47

h –1：[,]→[0，1] h –1（x）=4（x-8）构造：f：2{a

11421）= 4x-1 4，b，c}

{0，I}{a

，b，c}

，b，c}

，b，c}

f（B）=g， B∈2 {a g∈{0，1}{a或者更明确地：

（或B?{a，b，c}）

={h | h：{a，b，c}→{0，1}}

g满足{x | x∈{a，b，c}g∧（x）=1}=B f（?）=g 0， g 0（a）=0， g 0（b）=0， g 0（c）=0； f（{a}）=g 1， g 1（a）=1， g 1（b）=0， g 1（c）=0； f（{b}）=g 2， g 2（a）=0， g 2（b）=1， g 2（c）=0； f（{c}）=g 3， g 3（a）=0， g 3（b）=0， g 3（c）=1； f（{a，b}）=g 4，g 4（a）=1，g 4（b）=1， g 4（c）=0； f（{a，c}）=g 5，g 5（a）=1，g 5（b）=0， g 5（c）=1； f（{b，c}）=g 6，g 6（a）=0，g 6（b）=1， g 6（c）=1； f（{a，b，c}）=g 7，g 7（a）=1，g 7（b）=1， g 7（c）=1； 于是f –1：{0，I}{a

，b，c}

→2{a

，b，c}

f –1（g）=B，B={x | x∈{a，b，c}∧g（x）=1}

或者f –1（g0）=? ；f –1（g1）={a}；f –1（g 2）={b} ；f –1（g 3）={c}； f –1（g 4）={a，b}；f –1（g 5）={a，c}；；f –1（g 6）={b，c}；f –1（g 6）={a，b，c} 117 (-5,3) 88 (-5,2) 63 (-5,0) 85 (-5,-1) 112 (-5,-2)

89 65 (-4,3) (-3,3) 64 44 (-4,2) (-3,2) 43 27 (-4,0) (-3,0) 61 41 (-4,-1) (-3,-1) 84 60 (-4,-2-) (-3,-2) 45 (-2,3) 28 (-2,2) 15 (-2,0) 25 (-2,-1) 40 (-2,-2) 29 (-1,3) 16 (-1,2) 7 (-1,0) 13 (-1,-1) 24 (-1,-2) 17 (0,3) 8 (0,2) 3 (0,0) 5 (0,-1) 12 (0,-2) 48

31 (1,3) 18 (1,2) 9 (1,0) 11 (1,-1) 22 (1,-2) 49 (2,3) 32 (2,2) 19 (2,0) 21 (2,-1) 36 (2,-2) 71 (3,3) 50 (3,2) 33 (3,0) 35 (3,-1) 54 (3,-2) 97 (4,3) 72 (4,2) 51 (4,0) 53 (4,-1) 76 (4,-2) 127 (5,3) 98 (5,2) 73 (5,0) 75 (5,-1) 102 (5,-2)

142 (-5,-3) 178 (-5,-4) 111 (-4,-3) 142 (-4.-4) 83 (-3,-3) 110 (-3,-4) 59 (-2,-3) 82 (-2,-4) 39 (-1,-3) 58 (-1,-4) 23 (0,-3) 38 (0,-4) 37 (1,-3) 56 (1,-4) 55 (2,-3) 78 (2,-4) 77 (3,-3) 104 (3,-4) 103 (4,-3) 134 (4,-4) 133 5,-3 168 (5,-4) 第5题4）的图

6．设f和g是由数，f?g并且（g）??（f），证明f = g。

[证明] 因为已知f?g，故只需证明g?f即可得f=g。为此用反证法。

假设g?f，从而存在着（x，y）∈g，使得（x，y）?f。由（x，y）∈g可知x∈?（g），根据已知?（g）??（f），有x∈?（f）。于是存在着y1，使得（x，y）∈f。又从已知f?g，可得（x，y1）∈g。由于g是函数，根据函数是后者唯五的关系这个定义，就得到y=y1。从而（x，y）∈f，与反证假设（x，y）? f矛盾，这个矛盾说明假设错误，于是必有

g?f 。

7．设f和g是函数，证明也是函数。

[证] 只需证明对任何x ?（f∩g）存在着唯一的y，使得（x，y）∈f∩g即可。

（a）存在性

若有x ∈?，由于f及g是由数，因而也是关系，所以也是一个关系，从而应有y存在，使（x，y）∈f∩g.。

若f∩g是空集，自然?（f∩g）=?，从而对任何x，x ? ?（f∩g）。 （b）唯一性

若存在着y1，y2，使（x，y1）∈f∩g，（x，y2）∈f∩g，则（x，y1）∈f且（x，y2）∈f ，由f是由数，后者唯一就可得y1=y2。 8．设f：X→Y是函数，A，B是X的子集，证明：

1）f（A∪B）=f（A）∪f（B） 2）f（A∩B）?f（A）∩f（B） 3）f（A）\\f（B）?f（A\\B）

49

[证明] 1）若y∈f（A∪B）则有x∈A∪B，使f（x）=y。即有x∈A或者x∈B，使f

（x）=y。若x∈A，使f（x）=y，则y∈f（A）；若x∈B，使f（x）=y，则y∈f（B）。总之y∈f（A）或y∈f（B），从而∪f（B）所以，

f（A∪B）?f（A）∪f（B）

若y∈f（A）∪f（B），则y∈f（A）或者y∈f（B），若y∈f（A），则存在着x1∈A，使f（x1）=y，即存在着x1∈A∪B，使f（x1）=y，故y∈f（A∪B）；若y∈f（B），则存在着x2∈B，使y=f（x2），即存在着x2∈A∪B，使y=f（x2），故y∈（A∪B）。总之，y∈f（A∪B）。所以

f（A）∪f（B）?f（A∪B）。

因此 f（A∪B）= f（A）∪f（B）。

2）若y∈（A∪B），则存在着x∈A∩B，使y=f（x）。即x∈A且x∈B，使y=f（x）。从而y∈f（A）且y∈f（B），从而?y∈f（A）∩f（B）。所以

f（A∩B）?f（A）∩f（B）。

令f：X→X，X={1，2，3，4}，f={（1，4），（2，3），（3，4），（4，2）}。并且取A={1，2}，B+{2，3}，则AB={2}，f（A）=f（B）={3，4}，f（A∩B）={3}。从而f（A∩B）?f（A）∩f（B）是严格真包含。因此等号一般不成立。 3）设y是任一使得y∈f（A）\\f（B）的元素。那么有某-x∈A使得f（x）=y，但是，对每个z∈B，都有y≠f（z）。因此x∈A\\B，并且由于y=f（x），这就是推出y∈f（A\\B）。由y是任意的，这就建立了

f（A）\\f（B）?f（A\\B）

令X={1，2，3，4，5}， f：X→X，f={（1，5），（2，4），（3，2），（4，5），（5，1）}。取A={1，2，3}，B={3，4}，则A\\B={1，2}，于是f（A）={5，4，2}，f（B）={2，5}，f（A\\B）={5，4}，f（A）\\f（B）={4}。由于{4}?{5，4}， 故此f（A）\\f（B）?f（A\\B）是真包含，等号不成立。 9．设f：X→Y，定义函数g：Y→2X，使得对任意的y∈Y

g（y）={x∈X | f（x）=y}

证明：如果f是满射函数，则g是单射函数。

[证明] 对于任意的y1，y2∈Y且y1≠y2，我们来证g（y1）≠g（y2）。首先我们来证g

（y1）≠?且g（y2）≠?。由于f：X→Y是满射函数，故此存在着x1，x2∈X，使得f（x1）=y2，因此x1∈g（y1）={x∈X | f（x）=y1}，x2∈g（y2）={x∈X | f（x）=y2}，所以g（y1）≠?，g（y2）≠?。其次来证g（y1）∩g（y2）=?。否则，此交集非空，则存在着x∈X，使x∈g（y1）∩g（y2），从而x∈g（y1）且

50

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