您的当前位置：首页离散数学(西安交大版)习题解第一部分(集合论部分)

离散数学(西安交大版)习题解第一部分(集合论部分)

来源：爱go旅游网

离散数学辅助教材

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

第一部分

集合论

刘国荣

交大电信学院计算机系

离散数学习题解答

习题一（第一章集合）

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}}的元素；

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的下列子集：

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，，}，故此

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

30，32，}

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，} 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））

=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 （∪的结合律）

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}。显然有

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） [解]

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 ０００００１０１００１１１００１０１１１０１１１

x A C (A∩C) \\B

B A

C B

(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，„„}

习题二（第二章关系）

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

1）A×B 2）B×A 3）B×B 4）2B×B [解] 1）A×B={（1，a），（1，b），（2，a），（2，a），（3，a），（3，b）}

2）B×A={（a，1），（a，2），（a，3），（b，1），（b，2），（b，3）} 3）B×B={（a，a），（a，b），（b，a），（b，b）} 4）2B={，{a}，{b}，{a，b}}

2B×B{（，{a}），（，b），（{a}，a），（{a}，b），（{b}，a），（{b}，b），（{a，b}，b）}

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

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

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

[证] 必要性：即证A×B=B×AA=∨B=∨A=B

若A×B=，则A=或者B=

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

充分性：即证A=∨B=∨A=BA×B=B×A 这是显然的。 4．证明（A∩B）×（C∩D）=（A×C）∩（B×D）

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

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

综合这两个方面有（A∩B）×（C∩D）=（A×C）∩（B×D）。证法二：（逻辑法）对任何x,y (x,y)∈(A∩B)×(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)∈A×C(x,y)∈B×D (x,y)∈(A×C)∩(B×D)

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

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

出反例。

1）（A∪B）×（C∪D）=（A×C）∪（B×D） 2）（A\\B）×（C\\D）=（A×C）\\（B×D） 3）（AB）×（CD）=（A×C）（B×D） 4）（A\\B）×C=（A×C）\\（B×C） 5）（AB）×C=（A×C）（B×C）

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

（C∪D），但（a，-d）（A×C）∪（B×D）。所以（A∪B）×（C∪D）=（A×C）∪（B×D）不成立。事实上有：（A×C）∪（B×D）（A∪B）×（C ）（A∪B）×（C∪D）。

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

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

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

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

y）∈A×C，且（x，y）∈（A\\B）×C，且（x，y）B×C（否则x∈B），所以（x，y）∈（A×C）\\（B×C）。因而（A\\B）×C（A×C）\\（B×C）。

又对任一（x，y）∈（A×C）\\（B×C），有（x，y）∈A×C，且（x，y）B×C从而x∈A，y∈C及xB。即x∈A\\B，y∈C，故此（x，y）∈（A\\B）×C。所以（A×C）\\（B×C）（A×B）×C。

因而（A\\B）×C=（A×C）\\（B×C）。另一种证明方法：（A×B）×C

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

=（A×C）∩（B′×C）（叉积对交运算的分配律） =（A×C）∩（B×C）′

（因（B×C）′=（B′×C））∩（B×C′）∪（B′×C′）但（A×C）∩（B×C）′=（（A×C）∩（B′×C））∪

=（A×C）∩（B′×C））

=（A×C）∩（B′×C）（差集的定义）证法三：（逻辑法）对任何x,y (x,y)∈(A×C) \\ (B×C) (x,y)∈A×C(x,y)B×C (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)×C

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

5）成立。证明如下：对任一（x，y）∈（AB）×C，故此x∈AB，y∈C于是x∈A且xB，或者xA且x∈B。因此（x，y）∈（A×C）（B×C）。所以（AB）×C（A×C）（B×C）。

对任一（x，y）∈（A×C）（B×C）。则（x，y）∈A×C且（x，y）B×C，或者（x，y）A×C且（x，y）B×C。因此x∈A，yC，xB，或者x

∈B，y∈C，xA。所以x∈A\\B，或x∈B\\A，并且y∈C，故此 x∈AB，y∈C。因此（x，y）∈（AB）×C，即（A×C）（B×C）（AB）×C。综合两方面、就有（AB）×C=（A×C）（B×C）

另一种证明方法：（AB）×C

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

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

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′=（A×A）\\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）。

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=A×A，R7=

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

1）

1 0 0 2

1 0 R103 0 0 4 0R1是反对称的，传递的。 2）

1000001000 1001R100R2是反自反的，对称的。 3）

1000000000 0011R100（R1∪R2）=ℛ（R1）∪ℛ（R2）。

1100001100 11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}因此

ℛ（R1）∩⊈ℛ（R2）⊈（R1∩R2）

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

[解] A上有2n2个元关系。因为叉积A×A有n2个元素，因而A×A有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21000001001 00R4是反对称的，循环的。 5）

12300 R50411000110011 10R5是反自反的，反对称的，传递的。 6）

123

11 R614115

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

12300 R70400000000000 00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⊆

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，若

(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

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

(R=R)

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

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

13．设A、B为有穷集合，R，S⊆A×B，MR=（xij）m×n，MS=（yij）m×n

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

2）设MR∪S=（Zij）m×n，那么Zij=xijVyij，I=1，2„„，m，j=1，2，„„n. 3）设MR∩S=（tij）m×n，那么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）m×n中第I行第j列元素xij=1，根据R⊆S，可得（ai，bj）∈S，从而得S的关系矩阵MS=（yij）m×n中第I行第j列元素yij=1，由于是1≤1故此xij≤yij；若（ai，bj）R，则R的关系矩阵MR=（xij）m×n中第i行第j列元素xij=0，因此由S的关系矩阵MS=（yij）m×n中第j列元素yij≥0，可得xij≤yij。总之，有（i）(j)（xij≤yij）。 2）充分性

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

矩阵MR=（xij）m×n中第i行第j列元素xij=1，由于xij≤yij，所以yij≥1，故此yij≥1这说明S的关系矩阵MS=（yij）m×n中第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

是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0100000000001 ，MR20000001011 100000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234 无论从复合关系图还是从复合关系矩阵都可得R2оR1={（3，4）}

R2 R1

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）

∈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=A×A，则R2=R2R2⊆A×A=R2，故需证明R2⊆R2οR2=R2。为此，

对任何x，y∈A，（x，y）∈A×A=R2，一定存在着z∈A（至少有z=x或z=y存在），使（x，z）∈A×A=R2且（z，y）∈A×A=R2，故此（x，y）R2R2=R22，

2所以R2⊆R2R2=R22。于是R2=R2=A×A。

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

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

2则R1R2，即R1与R1是不同的关系。我们来证明R1=R1，R22=R2， 2（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，

22aj）∈R1R1=R1。故此R1⊆R1。

2若（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的定义，

2有（ai，aj）∈R1。故此R1= R1 2综合两个方面，可得R1= R1。

（b）次证R22=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总之

2222 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⊆A×A，R={（1，2），（2，3），（2，5），（3，4），（4，3），（5，5）}用作图方法矩阵运算的方法求r（R），s（R），t（R）。 [解] 1）作图法：

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

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

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

4 1

4 1

3 2

3 2 5 5 4

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

010 01MR100000101000100

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

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

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⊆A×A，证明

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有限）其关系图如下：

1 2

3 4

R的关系图 R1的关系图

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

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

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

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

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

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

（b）R是对称的

对于任何（a，b），（c，d）∈A×A，若（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）∈A×A，若（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是A×A上的等价关系。

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

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

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

23．设A是一个非空集合，R⊆A×A。如果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

所以，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。

综合（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

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=A×A={（a，b）|a∈A∧b∈A}因此有n2

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

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

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

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

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

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

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

23) R1

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

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

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）是。

2证法一：因R1是等价关系，因而R1是传递的，故此由第12题之5）有R1=

R1R1⊆R1。另一方面，结任何（a，b）∈R1，由于R1是自反的，故此（b，

2b）∈R1，从而由复合关系之定义，有（a，b）∈R1R1，所以R1⊆R1，从22而R1=R1，因此由R1是等价关系，知R1也是等价关系。

证法二：

2 一方面，对任何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。

2222 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，

利用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的划分？哪些不

是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} [解]

3 2 1 12

6 2

3 36

1）的Hasse图 2）的Hass图

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

10 4 6 9 12 35

7 5 2 3 11 素也为6；极汴元素为2和3；上确界为6；下确界为1；没有最小元素。 ②{2，4，6}的极大元素为4和6；最小素为2；极小元素也为2；上确界为12；下确界为2；

③{4，8，12}的极大元素为8，12；最小元素为4；极小元素也为4；下确界为4；没有最大元素；没有上确界。

性质集合最大元最小元极大元极小元上界下界上确界下确界 6 无无无 2 4 6 4,6 8,12 2,3 2 4 6,12 12 无 1 1,2 1,2,4 6 12 无 1 2 4 {2,3,6} {2,4,6} {4,8,12}

3)的特殊元素表

5 6 2 3 4 34．对下面半序集合（A，≼）的哈斯图，写出集合A及半

序关系≼的所有元素。 [解] A={0，1，2，3，4，5，6}

≼={（0，0），（0，1），（0，2），（0，3），（0，4），（0，5），（0，6），（1，1），92，20，（2，5），（3，3），（3，5），（4，4），（4，6），（5，5），（6，6）}第34题

第34题 35．设R是集合X上的半序关系，AX，证明R∩（A×A）是A上的半序关系。 [证].证法一：令R1=R∩（A×A），则R1A×A，所以R1是A上的关系，我们只需

证明在A上R是自反的，反对称的，传递的即可。（a）R1是自反的

对任何a∈A，由于AX，所以a∈X，由于R在X上是自反的，故此（a，a）∈R；由于a∈A，显然（a，a）∈A×A；所以（a，a）∈R∩（A×A），即（a，a）R1。

（b）R1是反对称的

对任何（a，a）∈R1且（b，a）∈R1，由R1= R∩（A×A），故有（a，b）∈R且（b，a）∈R，以及a，b，c∈A。利用R的传递性，可得（a，c）∈R，利用a，c∈A可得（a，c）∈A×A，所以（a，c）∈R∩（A×A），即（a，c）∈R1。

证法二：令R1=R(AA)，由于R(AA)AA，所以R1AA，因此R1是A上的关系。

①R1是自反的对任何a， aA

(a,a)R(a,a)AA (R是X上的自反关系及AX) (a,a)R(AA)

(a,a)R1 (R1的定义)

所以，R1是自反的； ②R1是反对称的对任何a,bA

(a,b)R1(b,a)R1

(a,b)R(AA)(b,a)R(AA) (R1的定义) ((a,b)R(a,b)AA)((b,a)R(b,a)AA)

((a,b)R(b,a)R)((a,b)AA(b,a)AA) (的结合律、交换律) ((a,b)R(b,a)R) (基本逻辑蕴涵式：pqp) a=b (R是反对称的) 所以，R1是反对称的； ③R1是传递的对任何a,b,cA

(a,b)R1(b,c)R1

(a,b)R(AA)(b,c)R(AA) (R1的定义) ((a,b)R(a,b)AA)((b,c)R(b,c)AA)

((a,b)R(b,c)R)((a,b)AA(b,c)AA) (的结合律、交换律) ((a,c)R(a,c)AA (R是传递的，全关系AA是传递的) (a,c)R(AA)

(a,c)R1 (R1的定义) 所以，R1是传递的；

综合①、②、③，可知R1是A上的半序关系。

36．设（A，≼1）和（A，≼2）是两个半序集合，定义A×B上的关系≼3如下：对于

a1，a2∈A，，b2∈B

（a1，b1），（a2，b2）∈≼3（a1，a2）∈≼1∧（b1，b2）∈≼2 证明≼3是A×B上的半序关系。

[证].证法一：对于任何（a，b）∈A×B，就有a∈A及b∈B，从而利用≼1及的自反性，可得（a，a）∈≼1且（b，b）∈≼2因此由≼3的定义，可知（（a，b），（a，b））∈≼3。（b）≼3是反对称的

对任何（（a1，b1），（a2，b2））∈≼3及（（a2，b2），（a1，b1））∈，由≼3的定义，可知（a1，a2）∈≼1且（a2，a1）∈≼1及（b1，b2）∈≼2且（b2，b1）∈≼2利用≼1及≼2的反对称性，可得a1=a2及b1=b2，因此（a1，b1）=（a2，b2）。（c）≼3是传递的

对任何（（a1，b1），（a2，b2））∈≼3及（（a2，b2），（a3，b3）））∈≼3，由≼3

的定义，可知（a1，a2）∈≼1且（a2，a3）∈≼1及（b1，b2）∈≼2且（b2，b3）∈≼2。利用≼1及≼2的传递性，可得（a1，a3）∈≼1及（b1，b3）∈≼2。再次利用≼3的定义，可得（（a1，b1），（a3，b3）））∈≼3。证法二： ① ≼3是自反的对任何(a,b)，(a,b)AB

aAbB

(a,a)≼1(b,b)≼2 (≼1，≼2都是自反的) ((a,b),(a,b))≼3 (≼3的定义)

所以，≼3是自反的； ②≼3是反对称的对任何(a,b)，(c,d)AB

((a,b), (c,d))≼3((c,d), (a,b))≼3

((a,c)≼1(b,d)≼2)((c,a)≼1(d,b)≼2) (≼3的定义) ((a,c)≼1(c,a)≼1)((b,d)≼2(d,b)≼2) (的结合律、交换律) a=cb=d (≼1，≼2都是反对称的) (a,b)=(c,d)

所以，≼3是反对称的； ③≼3是传递的

对任何(a,b)，(c,d)，(e,f)AB

((a,b), (c,d))≼3((c,d), (e,f))≼3

((a,c)≼1(b,d)≼2)((c,e)≼1(d,f)≼2) (≼3的定义) ((a,c)≼1(c,e)≼1)((b,d)≼2(d,f)≼2) (的结合律、交换律) (a,e)≼1(b,f)≼2 (≼1，≼2都是反对称的) ((a,b), (e,f))≼3 (≼3的定义) 所以，≼3是传递的；

综合①、②、③，可知≼3是AB上的半序关系。

37．对于非空集合A，是否存在这样的关系R，它即是等价关系又是半序关系？若有，

请举出例子。

[解] 有。只有一种，那就是A上的幺关系IA，它即是等价关系，又是半序关系。

证法一：否则，如果有a∈A及b∈A且a≠b，使得（a，b）∈R，那么由R是对我的就将有（b，a）∈R，再由R是反对称的，就得到a=b，矛盾。这个矛盾说明同时为等价关系和半序关系的R只能是幺关系IA。

证法二：设R即是一等价关系，又是一半序关系。则一方面，对任何元素a,bA，

(a,b)R(a,b)R(b,a)R (R的对称性)

a=b (R的反对称性) (a,b)IA

所以，RIA；

另一方面，对任何元素aA，

(a,a)IA(a,b)R (R的自反性) 所以，IAR；

综合这两方面，有 R=IA 。

38．对于下列每一种情况，举出有限集合和无限集合的例子各一个。

1）非空半序集合，其中某些子集没有最大元素；

2）非空半序集合，其中有一子集存在最大下界，但没有最小元素； 3）非空序集合，其中有一子集存在上界，但没有最小上界。 [解] 1）（a）令A={a，b，c}，则（2A，）为半序集，其中子集

B1={{c}，{a，b}} B2={{b}，{a，c}} 等均没有最大元素；（b）半序集（N，≤）的子集B1={x|x=2n∧n∈N} B2={P|P∈N∧P为素数} 等均没有最大元素；

2）（a）令={1，2，3，4，9，14，15} “1”为整除关系，a|b∷＝a整除b 则（A，1）为半序集合，其中子集 B={4，9，14，15}有最大下界1，但没有界小元素。（b）半序集（R，≤）的子集B=（0，1）={ x|x∈R∧o＜x≤1 } 有最大下界0，但没有最小元素。 3）（a）令A={1，2，3，30，42}，“1”仍为2）的（a）所定义的整除关系。则（A，

31 2）（a）的Hasse图 2

3）的（a）的Hasse

3 42 3 4

 1）的（a）的Hasse图 {c} {a} {b} {a，c} {b,c} {a，b} {a，b，c}

1）为半序集，其中子集

B={2，3}有上界30，42，但没有最小上界。半序集（Q，≤）的子集 B={ x|x∈Q∧0＜x2 ＝有上界2，。 2，但2Q）

39．指出下面的集合中，哪些是半序集合，线序集合或良序集合？

1）（2N，） 2）（2{a}，） 3）（2，） [解] 结果如下表（2N，）（2{a}，）（2，）半序集合 Y Y Y 线性序集合 N Y Y 良序集合 N Y Y 3等，但无界小上界（若有最小上界，必为2其中：Y—yes；N—not。

40．设R是A上的二元关系，若R是自反的，对称的，则称R为一个相容关系。．．．．

1）举出两个相容关系的例子

2）设R1，R2是A上的相容关系，那么R1∩R2，R1∪R2是A上的相容关系吗？请阐明理由。

[解]1）（a）令A={ba||，bed，dog，let，egg}

R={（x，y）|x，y∈A∧x和y含有相同的字母}则R是A上的相容关系。（b）令A={2166，243，375，8，455}

R={（x，y）|x，y∈A∧x和y含有相同的数字}则R是A上的相容关系。 2）证法一（a）R1∩R2是A上的相容关系。因为 ①R1∩R2是自反的

对任何a∈A，由于R1，R2都是相容关系，所以R1，R2都是自反的，从而（a，a）R1，（a，a）∈R2故（a，a）∈R1∩R2。 ②R1∩R2是对称的

对任何（a，b）∈R1∩R2，可得（a，b）∈R1且（a，b）∈R2。由于R1，R2都是相容关系，所以R1，R2都是对称的，从而（b，a）∈R1且（b，a）∈R2，故此（b，a）∈R1∩R2。

（b）R1∪R2是A上的相容关系。因为 ①R1∪R2是自反的

对任—aA，由于R1，R2都是相容关系，所以R1，R2都是自反的，从而（a，a）∈R1，（a，a）∈R2，故此（a，a）∈R1∪R2。 ②R1∪R2是对称的

对任何（a，b）∈R1∪R2，可得（a，b）∈R1或（a，b）∈R2。由于R1，R2都是相容关系，所以R1，R2都是对称的，从（b，a）∈R1或（b，a）∈R2，故此（b，a）∈R1∪R2。完（1996年1月20日）证法二（a）R1∩R2是A上的相容关系。因为 ①R1∩R2是自反的

对任何a，aA(a,a)R1(a,a)R2 (R1，R2都是自反的)

(a,a)R1R2

所以，R1R2是自反的； ②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是对称的；

综合①、②，可知R1R2是相容关系；

（b）R1R2是A上的相容关系。因为 ①R1R2是自反的

对任何a，aA(a,a)R1(a,a)R2 (R1，R2都是自反的)

(a,a)R1R2

所以，R1R2是自反的； ②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是对称的；

综合①、②，可知R1R2是相容关系；

习题三（第三章函数）

1．在下列关系中，哪些级构成函数？ 1）{（x，y）|x，y∈N，x+y＜10} 2）{（x，y）|x，y∈R，y=x2} 3）{（x，y）|x，y∈R，x=y2} [解] 1）不能；1）能；3）不能。

2．下列集合能否定义函数？若能，指出它的定义域和值域。 1）{（1，（2，3），（2，（3，4）），（3，（3，20））} 2）{（1，（2，3），（2，（3，4）），（1，（2，4））} 3）{（1，（2，3），（2，（3，4）），（3，（2，3））}

4）{（1，（2，3），（2，（3，4）），（3，（1，4）），（4，（1，4））} [解] 1）能，（f）={1，2，3}，（f）={（2，3），（3，4），（1，4）。}；

2）不能；

3）能，（f）={1，2，3}，（f）={（2，3）}；

4）能，（f）={1，2，3，4}，（f）={（2，3），（3，4），（1，4）}。 3．在下列函数中，哪些是单射的、满射的、双射的？ 1）f：N→N，f（n）=n2+1

0 2）f：N→{0，1}，f（n）=10 3）f：N→N，f（n）=1 5）f：R→R，f（x）=3x-17 6）f：N\\→{0}R，f（n）=log10n

n为奇数n为偶数

n为奇数n为偶数 4）f：N2→N，f（m，n）=mn

7）f：（2x）2→（2A）2，f（A1，A2）=（A1∪A2，A1∩A2）

[解] 1）单射；2）满射；3）即不是单射，也不是满射；4）满射；5）双射；6）单射；

7）即不是单射，也不是满射。

4．设A，B为有限集合，|A|=m，|B|=n，为使下面的结论为真，m，n应满足怎样的

条件？

1）存在从A到B的单射函数； 2）存在从A到B的满射函数； 3）存在从A到B的双射函数；

[解] 1）mn；2）mn；3）m=n。

5．对下称每一组集合X，Y，构造从X到Y的双射函数。

1） X=（0，1），Y=（0，2） 2） X=I，Y=N 3） X=N，Y=N×N 4） X=I×I，Y=N 5） X=R，Y=（0，∝）

6） 6）X=（-1，1），Y=R

7） 7）X=[0，1]，Y=（1，1）

42{a，b，c}{a，b，c}

8） 8）X=2，Y={0，1}

[解] 1）构造f：（0，1）→（0，2），f（x）=2x，x∈（0，1）则f-1：（0，2）→（0，1），f-1（x）=x，x∈（0，2）

22n1,当n0 n∈I 2）构造f：I→N，f（n）=2n1,当n0n21,当n为偶数--1—1

则f：N→I，f（n）= n∈N

n1,当n为奇数23）构造f1：N→N×N，f1（n）=（k+1，L+1），n∈N

这里k满足2|n，22|n，„，2K|n及2K+1n（k∈N∪{0}）

l=1[（n/2K）-1] （l=N∪{0}） 21则f1：N×N→N，（k，l）=n， k，l∈N 这里n=2k-1（2（l-1）+1）

编码方法如下图所示： 1 （1，1） 2 （2，1） 4 （3，1） 8 （4．1） 16 （5，1） 32 （6，1）（7，1） 3 （1，2） 6 （2，2） 12 （3，2） 24 （4，2） 48 （5，2） 96 （6，2） 192 （7，2） 5 （1，3） 10 （2，3） 20 （3，3） 40 （4，3） 80 （5，3） 160 （6，3） 320 （7，3） 7 （1，4） 14 （2，4） 28 （3，4） 56 （4，4） 112 （5，4） 224 （6，4） 448 （7，4） 9 （1，5） 18 （2，5） 36 （3，5） 72 （4，5） 144 （5，5） 288 （6，5） 576 （7，5） 11 （1，6） 22 （2，6） 44 （3，6） 88 （4，6） 176 （5，6） 352 （6，6） 704 （7，6） 13 （1，7） 26 （2），7 52 （3，7） 104 （4，7） 208 （5，7） 416 （6，7） 832 （7，7） 15

（1，8）„„ 30 （2，8）„„ 60 （3，8）„„ 120 （4，8）„„ 240 （5，8）„„ 480 （6，8）„„ 960 （7，8）„„ …

… …

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

构造f2：f1：N→N×N

(k,l)f2(n)(l,k),当m为奇数,nN

,当m为偶数22其中：m满足不等式1m（m+1）＜n≤1（m+1）（m+2），m∈N∪{0}

1k:nm(m1)2l:mk21则f2:NNN,f21(Y,S)n,k,lN

r,SN

当rs为偶数当rs为奇数12(rs1)(rs2)s,其中：n1(rs1)(rs2)r,245

编码方法如下图所示

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→I×I，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

则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}

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)

65 (-4,3) (-3,3) 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) (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）

[证明] 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）且

x∈g（y2），于是f（x）=y1，f（x）=y2，从而y1=y2与y1≠y2的取法矛盾，因此这样的x不存在，g（y1）∩g（y2）=Ø。最后，g（y1）≠g（y2）。否则，g（y1）=g（y2），则g（y1）∩g（y2）=g（y1）Ø ，矛盾。因此g是单射函数 10．设f：R→R，f（x）=x2-1，g：R→R，g（x）=x+2

1）求fog和gof

2）说明上述函数是单射、满射还是双射的？ [解] 1）fog：R→R 对于任意x∈R

（fog）（x）=f（g（x））=f（x+2）=（x+2）2-1=x2+4=3 gof：R→R，对任意x∈R

（gof）（x）=g（f（x））=g（x2-1）=（x2-1）+2=x2+1 2）（a）fog不是单射的

因为（fog）（-（x+4））=（x+4）2-4（x+4）+3

=（x+4）（x+4-4）+3 =（x+4）x+3 =x2+4x+3 =（fog）（x）

但是，除x=2外，一般-（x+4）≠x，故此fog不是单射函数。

（b）fog不是满射的因为（fog）（x）= x2+4x+3 =（x+2）2-1 ≥-1

故此ℛ（fog）=[-1，+∞]≠R。所以fog不是满射的。（c）综合（a）、（b）、fog也不是双射的。（d）gof不是单射的

因为（gof）（-x）=（-x）2+1 =x2+1 =（gof）（x）

但是，除x=0外，一般-x≠x，故此gof不是单射的。（f）gof不是满射的

因为（gof）（x）=x2+1≥1，故此ℛ（gof）=[1，+∞] ≠R。所以gof不是满射的。

（g）综合（d），（f），gof当然也不是双射的。

11．设A={1，2，3，4}

1）作双射函数f：A→A，使f≠IA，并求f 2，f 3，f –1，fof -1 2）是否存在双射函数g：A→A，使g≠IA，但g2=IA

[解]散1）定义f：A→A，f={（1，2），（2，3），（3，4）（4，1）}则显然f是双射的

且f≠IA={（1，1），（2，2），（3，3），（4，4）}。

f=5-x

f2=ff={（1，3），（2，4），（3，1），（4，2）} f2=x f3=ff2={（1，4），（2，1），（3，2），（4，3）} f3=5-x f –1={（1，4），（2，1），（3，2），（4，3）} f –1=5-x ff –1={（1，1），（2，2），（3，3），（4，4）}=IA ff –1= IA

2）存在。定义g：AA，g={（1，2），（2，1），（3，4），（4，3）}则显然gf，gIA且g是双射的，但是有

g2=gg={（1，1），（2，2），（3，3），（4，4）}=IA 。 12．设| X | = n ，从X到X的双射函数P数为集合X上的置换，．．

整数n称为置换的阶。一个n阶置换P：X→X，用如下形式表示：．

P=x2xnx1 ，P（xi）∈X P(x1)P(x2)P(xn)123-1-1-1

，求逆置换P及P与P的复合P◇P 。 312给定三阶置换P=[解] P-1=123 231123123P◇P-1=312◇231

123=123 13．设A是无限集合，B是有限集合，回答下列问题并阐明理由

1） A∩B是无限集合吗？ 2） A∪B是无限集合吗？ 3） A\\B是无限集合吗?

[答] 1）不是。因为A∩B⊆B，而B是有限集合，所以A∩B是有限集合。 2）是。因为A∪B⊆A，而A是无限集合，所以A∪B是无限集合。

3）是。因为A是无穷集合，因此A含有一可数子集A1，从而A=A1∪A2这里A2=A\\A1。于是A\\B=（A1∪A2）\\B=（A1\\B）∪（A2\\B）。由（另一证法否则A\\B有限，则A=（A\\B）∪B两个有限集合之并仍为有限矛盾）于任何可数集中取出有穷个元素之后，剩下的集合仍旧是可数集，故此可数集A1与有限集合的差A1\\B仍是一可数集，因此由A\\B=（A1\\B）∪（A2\\B）⊆A1\\B，即知A\\B中含有一可数子集A1\\B。所以A\\B是无限集合。 14．设A、B、C、D为集合，若A≈C，B≈D，证明A×B≈C×D。

[证明] 由于A≈C，B≈D，所以由等势的定义知存在着二个双射函数g：A→C和h：

B→D。从而我们可构造一个双射函数：

f：A×B→C×D

对于任何（a，b）∈A×B， f（a，b）=（g（a），h（b））于是f是双射函数，其逆函数为

f –1：C×D→A×B

对于任何（c，d）∈C×D，f –1（c，d）=（g –1（c），h –1（d））因此，

A×B≈C×D

15．设a，b为任意实数，a＜b，证明[0，1]≈[a，b] [证明] 构造函数 f：[0，1]→[a，b]

f（x）=（b-a）·x+a ，x∈[0，1]

此函数是双射的，其逆函数为

f –1：[a，b]→[0，1]

f –1（x）=

xa，x∈[a，b]（由于a＜b，故b-a＞0＝ ba因此[0，1]≈[a，b]。 16．计算下列集合的基数

1）{（a，b，c）|a，b，c∈I}； 2）所有整系数的一次多项式集合； 3）{（a，b）|a，b∈R∧a2+b2=1}；

4）实数轴上所有两不相交的有限开区间组成集合。

[解] 1）|{（a，b，c）|a，b，c∈I}|= 因为整数集I是可数的（参见第5题的2）。

又从{a，b，c| a，b，c∈I}=I×I×I为三个（有限个）可数集的叉积，因而是可数的。

2）所有整系数的一次多项式集合={ax+b|a，b∈I}，因此

|{ax+b|a，bI}|=|{（a，b）|a，b∈I}|=|I×I|= 。

3）|{（a，b）|a，b∈R∧a2+b2=1}|=  。因为存在着双射函数： S：{（a，b）|a，b∈R∧a2+b2=1}→[0，1] S（x，y）=

，（x，y）∈{（a，b）| a，b∈R∧a2+b2=1} 2其中arcosx,当y0

2arcosx,当y0其逆函数S-1：[0，1] →{（a，b）|a，b∈R∧a2+b2=1} S-1（x）=（cos2πx，Sin2πx），x∈ 因此|{（a，b）|a，b∈R∧a2+b2=1}=|[0，1]|= 

4）实数轴上所有两两不相交的有限开区间组成的集合的基数是。。因为我们可在每个开区间中任取一有理数与此区间对应，由于这此开区间是两两不相交的，因而不同的区间就对应于不同的有理数（实际上是建立了一个单射），故所述开区间类与有理数集的一子集等势，从而或是有限的或是可当选的；但不可能是有限的。因为已知每个开区间都是有限的，而有限个有限开区间的并仍是有限集（有限开集），从而必能包含在区间与它之内的每个有限开区间的均不相交，符合所述开区间类的条件，故而应在此大区间之内，矛盾。所以这类开区间是可数的。

17．找出三个与N等势的N的真子集。

[解] A={2n | n∈N}N. 双射函数f：A→N f（m）=

m，m∈A，这是所有偶自然数集合。 2m1，m∈B，这是所有奇自然数集合。 2 B={2n=+1|n∈N}⊂N，双射函数g：B→N， g（m）=

C={Pi| i∈N∧PiN∧Pi为第i个素数}⊂N，素数是无限多的。否则，只有有限个，不妨设为P1，„，Pk，从而来考虑

≈M=4P1P2„Pk+1

这个数，因为P1M，P2M，„PkM，从而M不能分解成素数这积，说明M又是一另外的素数，与素数只有P1，P2，„，Pk个矛盾。所以C是可数的，C与N等势。

18．证明 1）设A为有限集，B为可数集，则A×B为可数集。 2）设A、B为可数集，则A×B是可数集。

3）设A是不可数无限集合，B是A的可数子集，则（A\\B）≈A。 4）设A是任意无限集合，B是可数集，则（A∪B）≈A [证明] 1）由于A为有限集，B为可数集，故可设 A={a0，a1，a2，„，an} B={b0，b1，b2，„，bn„}

从而AB={（ai，bj）| ai ∈A∧bj∈B∧1≤i≤n∧j∈N} 从而可建立A×B到N的双射f：A×B→N （n+1）j+i

f（ai，bj）=n（j-1）+i，（ai，bj）∈A×B

其逆函数为：N→A×B

f –1（m）=（ai，bj），m∈N

m(modn),当nm,其中i=

n,当n|m,j=f –1：NAB 寻找k满足 n（k-1）mnk

[mi]n1,当nm,

,当n|mmnimn(k1) jk因此，A×B为可数集。 2）因A、B为可数集，故可设 A={a1，a2，„，an„} B={b1，b2，„，bn„}

从而A×B = {（ai，bj）|ai∈A∧bj∈B∧i∈N∧j∈N}

存在着从A×B到N的双射g：A×B→N，对（ai，bj）∈A×B，

12(ij1)(ij2)j,当ij为偶数g（ai，bj）=

1(ij1)(ij2)i,当ij为奇数2其逆由函数可见第5题3）的函数f2所以AB是可数的。

3）首先A\\B不可能是有限集合，否则由A=（A\\B）∪B及B是可数集合，根据有限集与可当选集之并集为可数集（可数集去掉有限集仍为可数集的逆用），可知A是可数集，与已知A是不可数集矛盾。所以A\\B是无限集合，因此包

含一可数子集C={c1，c2，„cn„}，即C⊆A\\B

由B是可数集，故此不妨设B={b1，b2，„bn，„}可建立从A到A\\B的双射如下： g：AA\\B

czi1g（x）=czix因此A\\B≈A。

,当xbi时(iN),当xci时(iN) ,当x(A\\B)\\C4）由于B是可数集，不妨设B={b1，b2，„bn，„}。由于A是无限集合，因此存在某一可数集C⊆A\\B，不妨设

①若A\\B是有限集合故AB=（A\\B）B是可数集即ABB又A是无穷集，故BA从而ABA但AAB故此

AAB半A∪BxA

②若A\\B是无穷集合则

C=（c1，c2，„cn，„）

从而可建立从AB到A的双射如下： f：A∪B→A

(iN)c2i1,当xbi时f（x）=c2i,当xci时(iN)

x,当x(A\\B)\\C时

所以A∪B≈A（完） 96年1月25日

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文