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

离散数学辅助教材

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

第一部分

集合论

刘国荣

交大电信学院计算机系

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

7 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 A ′∩ B ′ A \ (B ∪ C ) ′ B C A ∩ (B ′∪ C ) A C B A X X X

8

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

14. 试用成员表法证明

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

B ⊕

C A ⊕（B ⊕Ｃ）

０ ０ ０ ０ ０ ０ ０ ０ ０ １ ０ １ １ １ ０ １ ０ １ １ １ １ ０ １ １ １ ０ ０ ０ １ ０ ０ １ １ ０ １ １ ０ １ １ ０ １ ０ １ １０ ０ ０ １ ０ １ １ １

０ １ ０ １

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

A B C A ∪B （B ∪C ） (B ∪C)′

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

B ′ A ∩B ′ ０ ０ ０ ０ ０

1 ０ 1 0 ０ ０ １ ０ １ 0

0 1 0 ０ １ ０ １ １

0 0 0 0 ０ １ １ １

1 0 ０ 0 0 １ ０ ０ １

0 1 １ 1 1 １ ０ １ １ 1 0 ０ 1 1 １ １０ 1 1 0 ０ 0 0 １ １ １

1 １ 0 0 0 0

A

C B

x

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

B

C A

x

(A ∩C) \B

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

10

综合这两个方面有（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）不成立。

11

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

12

∈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）}，R s={（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）。

13

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

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

R 5={（1，2），（1，3），（1，4），（2，3），（2，4），（3，4）} R 6=A ×A ，R 7=?

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

[解]：

1）

???

???????????=0000

1100

00000011

1R R 1是反对称的，传递的。

2） ???

???????????=0000

0000

000100101R R 2是反自反的，对称的。

3） ??????????????=1100

1100

001100111R R3是自反的，对称的，传递的，因此是等价关系。循环的 综合这两方面，就有

（R1∪R2）=?（R1）∪?（R2）。 2）由于R 1∩R 2?R 1，R 1∩R 2?R 2，根据定理1，有?（R 1∩R 2）??（R 1），?

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

1 0 0

2

3 0 0 4

15

?（R 1）∩??（R 2）?（R 1∩R 2）

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

[解] A 上有2n2个元关系。因为叉积A ×A 有n2个元素，因而A ×A 有2n2个子集，而每个子集都是A 上的一个二元关系。

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

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

Y

Y

Y

Y

4）

οο

31 42

οο ?

?

???

??

??

???=0001

0100

1000

00104R R4是反对称的，循环的。 5）

432

1οο

οο ?

?

???

?

?

??

???=000110001100

11105R R5是反自反的，反对称的，传递的。 6）

432

1οο

οο ??

???

?

?

??

???=1111

11111111

11116R

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

7）

432

1οοοο ????????????=00000000000000007R 12．设A 是A 上的关系，证明

1）R 是自反的当且反当I A ?R

2）R 是反自反的当且仅当I A ∩R=? 3）R 是对称的当且反当R=R (

4） R 是反对称的当且仅当R ∩R (?I A

5）R 是传递的当且仅当R οR ?R

[证] 1）必要性

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

充分性

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

2）必要性

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

充分性

若I A ∩R=?，则R 是反自反的。否则，不是反自反的，那么应存在某一x 0∈A ，使得（x 0，x 0）∈R 。但是（x 0，x 0）∈I A ，从而（x 0，x 0）?。这不可能，矛盾。

3）必要性，

若R 是对称的，则对任何（x ，y ）∈R ，就有（y ，x ）∈R 。于是根据逆关系的定义，可得（x ，y ）∈R (，于是R ?R (；对任何（x ，y ）∈R (，由逆关系的定义，可得（y ，x ）∈R 。再次利用R 的对称性有（y ，x ）∈R ，于是R (?R7是反自反的对称的，传递的，循环的，反传递的，反

对称的。

17 R ；综合两方面，有R=R (。

充分性

若R= R (，则对任何（x ， y ）∈R ，由R=R (可得（x ，y ）∈R (

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

4）必要性 若R 是反对称的，则对任何（x ，y ）∈R (，即有（x ， y ）∈R 及（x ，y ）∈R (，从逆关系的定义，就有（x ， y ）∈R 及（y ，x ）∈R ，因此，利用R 的反对称性，可得x=y 。于是就有（x ，y ）=（x ，x ）∈I A ，所以R ∩R (?I A 。 充分性 若R ∩R ( ?I A ，则对任何（x ，y ）∈R 及（y ，x ）∈R ，从逆R (关系的定义，可得（x ，y ）∈R 及（x ，y ）∈R (，也即（x ，y ）∈R ∩R (，利用R ∩R ( =I A 可得（x ，y ）∈I A ，于是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)∈I A (I A 是幺关系，因此是自反关系) ?(x,x)∈R (R 是自反关系) 所以 I A ?R ；

?):对任何x ∈A ，

x ∈A

?(x,x)∈I A (I A 是幺关系，因此是自反关系) ?(x,x)∈R (因I A ?R) 所以，R 是自反关系；

2)?)首先 ??I A ?R ；

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

18

(x,y)∈I A ?R ?(x,y)∈I A ∧(x,y)∈R

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

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

(x,x)∈R

?(x,x)∈I A ∧(x,x)∈R (I A 是幺关系，因此是自反关系) ?(x,x)∈I A ?R

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

(x,y)∈R

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

?(x,y)∈R (

所以，R=R (

；

?):对任何x,y ∈A

(x,y)∈R

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

)

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

(x,y)∈R ?R (

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

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

?x=y (R 是反对称关系) ? (x,y)∈I A (I A 是自反关系) 所以，R ?R (

?I A ； ?):对任何x,y ∈A

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

?(y,x)∈R

所以，R 是对称的；

13．设A 、B 为有穷集合，R ，S ?A ×B ，M R =（x ij ）m ×n ，M S =（y ij ）m ×n

1）为了R ?S ，必须且只须?i ?j （x ij ≤ y ij ）

2）设M R ∪S =（Z ij ）m ×n ，那么Z ij =x ij Vy ij ，I=1，2……，m ，j=1，2，……n.

3）设M R ∩S =（t ij ）m ×n ，那么t ij =x ij ^y ij

i=1，2，……m ；j=1，2，……，n.

[证] 由于A 、B 是有穷集合，不妨设

A={a 1，a 2……，a m }，B={b 1，b 2，……，b n }

1）必要性

若R ?S ，则对任何i ∈{1，2，……，m}，对任何j ∈{1，2，……n}，若（a i ，b j ）∈R ，则R 的关系矩阵M R =（x ij ）m ×n 中第I 行第j 列元素x ij =1，根据R ?S ，可得（a i ，b j ）∈S ，从而得S 的关系矩阵M S =（y ij ）m ×n 中第I 行第j 列元素y ij =1，由于是1≤1故此x ij ≤y ij ；若（a i ，b j ）?R ，则R 的关系矩阵M R =（x ij ）m ×n 中第i 行第j 列元素x ij =0，因此由S 的关系矩阵MS=（y ij ）m ×n 中第j 列元素y ij ≥0，可得x ij ≤y ij 。总之，有（?i ）(?j )（x ij ≤y ij ）。

2）充分性

若（?i ）(?j )（x ij ≤y ij ），则对任何（a i ，b j ）∈R ，就有R 的关系 矩阵M R =（x ij ）m ×n 中第i 行第j 列元素xij=1，由于x ij ≤y ij ，所以y ij ≥1，故此y ij ≥1这说明S 的关系矩阵M S =（y ij ）m ×n 中第i 行第j 列元素y ij 为1，因此必有

（a i ，b j ）∈S ，所以R ?S 。

2）对任何i ∈{1，2，……，m}，对任何j ∈{1，2，……，n}若Z ij =1，则（ai ，bj ）∈R ∪S ，故此（a i ，b j ）∈R 或者（a i ，b j ）∈S ，于是x ij =1或者y ij =1。从而 b j ）?S ，于是x ij =0且yij=0。从而x ij ∨y ij =0。因而Z ij =x ij ∨y ij =0； 综合上述两种情况，就有z ji =x ij ∨y ij ，i=1，2，……，m ，j=1,2,……n ，。

3）对任何i ∈{1，2，……m}，对任何j ∈{1，2，……，n}。若t ij =1，则（a i ，b j ）∈R ∩S ，故此（a i ，b j ）∈S 且（a i ，b j ）∈S ，于是x ij =1，且y ij =1从而x ij ∧y ij =1。因而t ij =x ij ∧y ij =1；若tij=0，则（a i ，b j ）?R ∩S ，故此（a i ，b j ）?S ，于

20

是x ij =0或者y ij =0，从而x ij ∧y ij =0。因而t ij =x ij ∧y ij =0。

综合上述两种情况，就有t ij =x ij ∧y ij ，i=1，2，……，m ，j=1，2，……，n 。 14．设A={1，2，3，4}，R 1，R 2为A 上的关系，R1={（1，1），（1，2），（2，4）}，

R 2={（1，4），（2，3），（2，4），（3，2）}，求R 1оR 2，R 2оR 1，R 1оR 2оR 13

1R

[解] ??

??????????=0000000010000011

1

R M ，?????

??

?????=00

0010110

00100

2

R M 1）

??

???

????

???=???????????????????

??

???=000

0000

00001100

0000001011001000000

00000100000

1

121

21οοοR R

R R M M M οοο

ο

4321 ο

ο

οο

4321 οοο

ο4321

R 1 R 2

2）?????

???????=?????????????????????

???=00

100000000000

00

000010001011

00

00101100100012

1

2οοοR R R R M M M

οοο

ο

4321 ο

ο

οο

4321 οοο

ο4321 R 2 R 1

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

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

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

21

3）?????

???????=?????????????????????

???=00

000000000000

00

000010001011

00

00000000110012

1

2οοοR R R R M M M

οοο

ο

4321 ο

ο

οο

4321 οοο

ο4321

4）

?????

????

???=???????

??

??????????

??

???=??

???

??

??

??????????

??

??????????

??

???==00

0000

0000000

1

10000000

01000001

1000

00000000010110000000

01000001

10000000

01000101

100000000100000111

1131

οοοοοR R R R M M M M

ο

οο

ο4321 ο

οο

ο οοοο 4

321

οοοο R1 R1 R1

15）设R 1，R 2，R 3是A 上的二元关系，如果R 1?R 2，证明

1）R 1οR 3?R 2οR 3 2）R 3οR 1?R 3οR 2

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

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

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

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

都可得R 1оR 1о3

1R ={（1，1），（1，2）， （1，4）}

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