内容发布更新时间 : 2024/5/22 4:37:45星期一 下面是文章的全部内容请认真阅读。

对B?A，C?A，A ?D应用容斥原理，得

x1=4。

同理可求出：x2=3，x3=3，x4=2。

1.3.2习题1.2解答

1.设A，B是两个集合，问在什么条件下有A?B?A成立？等号能成立吗？ 解：当A或B为空集时能够成立；当A为空集时等号能够成立。

2.设A是m元集合，B是n元集合。问A到B共有多少个不同的二元关系？设A={a，b}，B={1， 2}，试写出A到B上的全部二元关系。

解：A到B上共有2mn个二元关系。本题中A?B的全部子集?，{(a,1)}，{(a,2)}，{(b,1)}，{(b,2)}， {(a,1),(a,2)}，{(a,1),(b,1)}，{(a,1),(b,2)}，{(a,1),(b,2)}，{(a,2),(b,1)}，{(a,2),(b,2)}，{(a,1),(a,2),(b,1)}，{(a,1),(a,2),(b,2)}，{(a,1),(b,1),(b,2)}，{(a,2),(b,1),(b,2)}，{(a,1),(a,2),(b,1),(b,2)}为A到B的全部二元关系。

3.R，S是集合A上的两个关系。试证明下列等式：

-1-1-1

（1）(R?S)= S?R

-1-1

（2）(R)= R

-1-1-1

（3）(R∪S)= R∪S

-1-1-1

（4）(R∩S)= R∩S 证明：

-1-1-1-1

（1）先证(R?S)? S?R，对任意(x，y) ?(R?S)，则(y，x) ?(R?S)，则存在a?A，满

-1-1-1-1-1

足(y，a) ?R且(a，x) ?S，那么(x，a) ?S且(a，y) ?R，所以(x，y) ? S?R，因此(R?S)? -1-1-1-1-1-1-1-1

S?R；再证S?R ?(R?S)，对任意(x，y) ? S?R，则存在a?A，满足(x，a) ?S且(a，

-1-1-1-1

y) ?R，所以(y，a) ?R且(a，x) ?S，所以(y，x) ?(R?S)，所以(x，y) ?(R?S)，因此S?R

-1

?(R?S)。

-1-1-1-1-1-1-1

（2）先证(R)? R，对任意(x，y) ?(R)，则(y，x) ? R，则(x，y) ? R，所以(R)?

-1-1-1-1-1-1-1

R；再证R ?(R)，对任意(x，y) ? R，则(y，x) ? R，则(x，y) ?(R)，所以R ?(R)。

-1-1

故(R)= R得证。

-1-1-1-1

（3）先证(R∪S)? R∪S，对任意(x，y) ?(R∪S)，则(y，x) ? R∪S，则(y，x) ? R

-1-1-1-1-1-1-1

或(y，x) ?S，则(x，y) ?R或者(x，y) ?S，所以(x，y) ? R∪S，所以(R∪S)? R∪S；

-1-1-1-1-1-1-1

再证R∪S ?(R∪S)，对任意(x，y) ? R∪S，则(x，y) ?R或者(x，y) ?S，则(y，x) ?

-1-1-1-1

R或(y，x) ?S，所以(y，x) ? R∪S，所以(x，y) ?(R∪S)，所以R∪S ?(R∪S)。故(R

-1-1-1

∪S)= R∪S得证。

-1-1-1-1

（4）先证(R∩S)? R∩S，对任意(x，y) ?(R∩S)，则(y，x) ? R∩S，则(y，x) ? R

-1-1-1-1-1-1-1

且(y，x) ?S，则(x，y) ?R且(x，y) ?S，所以(x，y) ? R∩S，所以(R∩S)? R∩S；

-1-1-1-1-1-1-1

再证R∩S?(R∩S)，对任意(x，y) ? R∩S，则(x，y) ?R且(x，y) ?S，则(y，x) ? R

-1-1-1-1-1

且(y，x) ?S，所以(y，x) ? R∩S，所以(x，y) ?(R∩S)，所以R∩S?(R∩S)。故(R∩S)= -1-1

R∩S得证。

11

4.设R是集合A上的关系，存在自然数i，j(i

解：用定理1.2.3的（2）证明之。

若p?j-1，结论显然成立。设p?j，则p>i，于是存在自然数k，m，使得

p=i+k(j-i)+m (0?m?j-i-1)

=i+kq+m (q=j-i)。 于是，Rp=Ri+kq+m=Ri+m。（由定理1.2.3的（2）得） 而i+m?i+j-i-1=j-1，所以Rp?S。

5.设R是集合A上的关系，令

R+={(x, y)|x?A，y?A，并且存在n>0，使得xRny}，

则称R+是R的传递闭包，证明：R+是包含R的最小具有传递性的关系。 证明：

（1）证明R ? R+，对任意(x，y)?R，即x R y，即存在n=1，使得x Rn y，所以(x，y)?R+，所以R ? R+；

（2）证明R+具有传递性：

++

方法一：（根据传递性的定义）对于任意x，y，z?A，若xRy，yRz，则存在m，n(m>0，n>0)，使得xRmy，yRnz，因此有xRm?Rnz，即xRm+nz，所以xR+z，故R+具有传递性。 方法二：（根据定理1.2.4）对于任意(x，y)?R+?R+，则存在a?A，满足(x，a)?R+，(a，y)?R+，故存在m，n(m>0，n>0)，使得x Rm a，a Rny，因此有xRm?Rny，即x Rm+n y，所以xR+y，所以R+?R+ ? R+，故R+具有传递性。 （3）证明R+的最小性：

方法一：设任意的集合P，P ? R且P具有传递性，往证R+ ? P。

对任意的(x，y)?R+，则存在n(n>0)，使得x Rn y，若n=1，则有x R y，即(x，y)?R，所以(x，y)? P；若n>1，则存在a1,a2,??,an-2,an-1，满足x R a1，a1 R a2，a2 R a3，??，an-2 R an-1，an-1 R y，因为P ? R，所以有x P a1，a1 P a2，a2 P a3，??，an-2 P an-1，an-1 P y，又P具有传递性，所以有x P y，即(x，y)? P，因此R+ ? P。

ｎ

方法二：（用数学归纳法）设集合T(n)＝R∪R2∪R3∪R4∪?∪R (n>0)，根据R+的定义，有R+＝T(∞)，设任意的集合P，P ? R且P具有传递性，往证T(∞)? P。 用数学归纳法：

当ｎ＝１时，显然T(1)＝R ? P成立； 假设当n=k时，结论成立，即有

ｋ

T(k)＝R∪R2∪R3∪R4∪?∪R? P 那么当ｎ＝k+1时

ｋｋ＋１

T(k+1)＝R∪R2∪R3∪R4∪?∪R∪R

ｋ＋１

＝T(k) ∪R

ｋ＋１

根据假设有T(k) ? P，这里只需证明R? P即可。

ｋ＋１ｋｋ

对任意的(x，y)? R，则存在a?A，满足(x，a)? R, (a，y)? R，根据假设，R?T(k)

ｋ

? P，且由已知R ? P，所以(x，a)? P , (a，y)?P，又P具有传递性，所以(x，y)? P，故R＋１

? P，从而T(k+1) ? P成立。

＋

因此，T(∞)? P，故R? P成立得证。

6.若关系R是反自反的，是对称的，试证明R不是传递的。

12

证明：反证法：假设R是传递的，对于任意(a，b)?R，因为R是对称的，所以(a，b)? R，则有(a，a)? R，这与R是不反身的矛盾，故假设不成立，原结论成立。

7.集合A上的关系是对称的，反对称的，试指明关系R的结构。 解：R的结构是A 中元素只可能与自身有关系。

8.若集合A上的关系R具有传递性，则R+=R。

证明：R+是包含R的最小具有传递性的关系，则对任意包含R的且有传递性的关系都包含R+，又因为R?R ，且R具有传递性，所以R+?R，又R+?R，所以R+＝R

9.设R是集合A上的关系，如果 1）对任意a?A，都有a R a ； 2）若aRb，aRc，则bRc ； 证明：R是等价关系。

证明：根据已知，对任意a?A，都有a R a，故R具有反身性； 对任意a、b?A，若aRb，又有a R a，根据2），有bR a，故R具有对称性； 对任意a、b、c?A，若a R b，b R c，又R具有对称性，则有bRa，bRc，根据2），有 a R c，故R具有传递性

因此，R是等价关系。

10.有人说：“等价关系中的反身性可以不要，因为反身性可以从对称性和传递性推出：由对称性，从a ? b可得b ? a，再由传递性得a ? a”。你的意见呢？

解：这种说法是错误的。对于任意a?A，和一个A上的等价关系R，可能不存在a R b，也就推不出a R a了，而反身性则要求对于每一个a?A，都有a R a。

11.若集合A上的关系R，S具有对称性，证明：R?S具有对称性的充要条件为R?S= S?R。

证明：

充分性：若R?S= S?R，往证R?S具有对称性。

对于任意x，y?A，若(x，y)? R?S，则存在a?A，满足(x，a)?R，(a，y)? S，又R，S具有对称性，所以有(y，a)? S，(a，x)? R，所以(y，x)? S?R，又S?R= R?S，故(y，x)? R?S，因此R?S具有对称性；

必要性：若R?S具有对称性，往证R?S= S?R。

先证R?S? S?R：对于任意(x，y)? R?S，因R?S具有对称性，则有(y，x)? R?S，则存在a?A，满足(y，a)?R，(a，x)? S，又R，S具有对称性，所以有(x，a)? S，(a，y)? R，所以(x，y)? S?R，故R?S? S?R；

再证S?R? R?S：对于任意(x，y)?S?R，则存在a?A，满足(x，a)? S，(a，y)? R，又R，S具有对称性，所以有(y，a)?R，(a，x)? S，故(y，x)? R?S，因R?S具有对称性，所以(x，y)? R?S，故S?R? R?S； 因此，R?S= S?R得证。

-1

12.若R是等价关系，试证明R也是等价关系。

-1-1

证明：因为R是等价关系，所以R有对称性，所以有R= R，所以R也是等价关系。

13

13.对于实n阶方阵A，B，C，试证明下列关系是等价关系：

1）矩阵A，B等价，记以A?B，如果存在非奇异矩阵P，Q，使得B=P?A?Q；

-1

2）矩阵A，B相似，记以A ? B，如果存在非奇异矩阵P，使得B=P?A?P；

3）矩阵A，B合同，记以A ? B，如果存在非奇异矩阵P，使得B=P?A?P?，其中P?是P的转置矩阵。

1）证明：对于每一个实n阶方阵A，存在n阶单位矩阵I，满足A=I?A?I，故有A ? A，所以矩阵等价关系具有反身性；

对于任意的实n阶方阵A、B，若A ? B，则存在非奇异矩阵P、Q，满足B=P?A?Q，则

-1-1

A=P?B?Q，所以有B ? A，所以矩阵等价关系具有对称性；

对于任意的实n阶方阵A、B、C，若A ? B，B ?C，则存在非奇异矩阵P、Q、S 、T，满足B=P?A?Q，C=S?B?T，则C= (SP)?A?(QT)，所以有A ? C，所以矩阵等价关系具有传递性。

故矩阵的等价关系是等价关系。

-1

2）证明：对于每一个实n阶方阵A，存在n阶单位矩阵I，满足A=I?A?I，故有A ? A，所以矩阵相似关系具有反身性；

-1-1

对于任意的实n阶方阵A、B，若A ? B，则存在非奇异矩阵P，满足B=P?A?P，则A=P

-1-1-1

?B?P，即A=P?B?(P)，所以有B ? A，所以矩阵相似关系具有对称性；

对于任意的实n阶方阵A、B、C，若A ? B，B ? C，则存在非奇异矩阵P、Q，满足B=P

-1-1-1-1 -1

?A?P，C= Q?B?Q，则C= (QP)?A?(PQ)，即C= (QP)?A?(PQ)，所以有A ? C，所以矩阵相似关系具有传递性。

故矩阵的相似关系是等价关系。

3）证明：对于每一个实n阶方阵A，存在n阶单位矩阵I，满足A=I?A?I?，故有A ? A，所以矩阵合同关系具有反身性；

-1

对于任意的实n阶方阵A、B，若A ? B，则存在非奇异矩阵P，满足B=P?A?P?，则A=P

-1-1-1

?B?(P?)，即A=P?B?(P)?所以有B ? A，所以矩阵合同关系具有对称性；

对于任意的实n阶方阵A、B、C，若A ? B，B ? C，则存在非奇异矩阵P、Q，满足B=P?A?P?，C= Q?B?Q?，则C= (QP)?A?(P?Q?)，即C= (QP)?A?(PQ)?，所以有A ? C，所以矩阵合同关系具有传递性。

故矩阵的合同关系是等价关系。

14.试证明定理1.2.8。 证明：（1）由定理1.2.7和定义1.2.12知A/R为A的一个划分。

（2）由Rc的定义知，对任意的x?C有xRcx，即Rc满足自反性。对任意的x?C，y?C有xRcy且yRcx，即Rc满足对称性。对任意的x?C，y?C，z?C有xRcy，yRcz，并且xRcz也成立，故Rc满足传递性。综上Rc是A上的等价关系。

15.设R是集合A上的关系，A??A，定义A?上的关系R?如下：

R?=R?( A?? A?)

试确定下述断言的真假：

（1） 如果R传递，则R?传递。

（2） 如果R为部分序关系，则R?也是部分序关系。 （3） 如果（A,R）是全序集，则（A?, R?）也是全序集。

14

(4) 如果（A,R）是良序集，则（A?, R?）也是良序集。

解：（1）为真； （2）为真； （3）为真； （4）为真。

1.3.3习题1.3解答

1. 证明：映射的乘法满足结合律，举例说明：映射的乘法不满足交换律。

证明：设?是集合A到集合B内的映射，?是集合B到集合C内的映射，?是集合C到集合D内的映射，对于任意a?A，有

( (???)??)(a)= (???)(? (a) ) = ?(? (? (a) ) ) (??(???))(a)= ?((???) (a) ) = ?(? (? (a) ) )

可见( (???)??)(a)= (??(???))(a)，所以映射的乘法满足结合律。 举例：设映射?：a?b b?c c?a 映射?：a? c b?b c? a

则(???)(a)= ?(? (a) )= ?(b)=b (???)(a)= ? (? (a) )= ? (c)=a

可见(???)(a) ? (???)(a)，映射的乘法不满足交换律。

2.将集合M中元素映射到自身的变换称为同一变换，记为I。设?，?是集合M上的两

-1

个变换，如果???=???=I，则?，?是1–1变换，并且?=?。 证明：（1）先证?、?分别是单映射。

对任意x1，x2?M，如果?(x1)= ?(x2)，则有

x1=I(x1)= (???) (x1)= ?(?(x1) )= ?(?(x2) )= (???) (x2) =I(x2)= x2 所以?是单映射。

同理可证?是单映射。

（2）再证?、?分别是满射。

因为?和?都是M到M的单映射，所以有?(M) ? M，? (M) ? M，于是 M =I (M)= (???) (M)= ? (? (M) ) ??(M)，

同理A=I (M)= (???) (M)= ? (? (M) ) ?? (M)， 所以?(M) = M，? (M)= M，即?、?是满射。 （3）往证?=?-1。

由?是1–1映射，故存在?-1，对任意x ?M， ?-1(x)= I (?-1(x))= (???) (?-1(x))= ?(? (?-1(x))= ?(x) 故?=?-1。

3.设?是集合M到集合N内的映射，证明对M的任意子集A，B，有?( A∩B) ? ? (A)∩? (B)，举例说明：?( A∩B) = ? (A)∩? (B)不成立。

证明：对任意y??(A∩B) ?N，则存在y的原象x，使得?(x)=y，因y??( A∩B)，所以

15