离散数学（第三版）课后习题答案

离散数学辅助教材

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

第一部分

集合论

刘国荣

交大电信学院计算机系

离散数学习题解答

习题一 （第一章集合）

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

=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）

[解]

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

[解]

14. 试用成员表法证明

1）（A B） C=A（B C）

2）（A∪B）∩（B∪C） AB′

[解] 1）成员表如下

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

（Ａ Ｂ） Ｃ＝Ａ （Ｂ Ｃ）

1） 成员表如下：

成员表中运算结果（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）

R1是反对称的，传递的。

2）

R2是反自反的，对称的。

3）

R3是自反的，对称的，传递的，因此是等价关系。循环的 综合这两方面，就有（R1∪R2）=ℛ（R1）∪ℛ（R2）。

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）

R4是反对称的，循环的。

5）

R5是反自反的，反对称的，传递的。

6）

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

7）

12．设A是A上的关系，证明

1）R是自反的当且反当IA⊆R

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

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

4） R是反对称的当且仅当R∩⊆IA

5）R是传递的当且仅当RR⊆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⊆；对任何（x，y）∈，由逆关系的定义，可得（y，x）∈R。再次利用R的对称性有（y，x）∈R，于是⊆R；综合两方面，有R=。

充分性

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

4）必要性

若R是反对称的，则对任何（x，y）∈，即有（x， y）∈R及（x，y）∈，从逆关系的定义，就有（x， y）∈R及（y，x）∈R，因此，利用R的反对称性，可得x=y。于是就有（x，y）=（x，x）∈IA，所以R∩⊆IA。

充分性

若R∩ ⊆IA，则对任何（x，y）∈R及（y，x）∈R，从逆关系的定义，可得（x，y）∈R及（x，y）∈，也即（x，y）∈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 (IA是幺关系，因此是自反关系)

(x,x)∈IA R

(x,x)∈ (因IA R= )

则与空集不含任何元素，(x,x) 矛盾。

故对任何x∈A，(x,x) R ；

所以，R是反自反关系；

3) )对任何x，y∈A

(x,y)∈R

(y,x)∈R (R是对称关系)

(x,y)∈

所以，R=；

):对任何x,y∈A

(x,y)∈R

(x,y)∈ (R=)

(y,x)∈R

所以，R是对称的；

4) )对任何x，y∈A

(x,y)∈R

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

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

x=y (R是反对称关系)

(x,y)∈IA (IA是自反关系)

所以，R IA ；

):对任何x,y∈A

(x,y)∈R

(x,y)∈ (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。从而