发布时间 : 星期五 文章吉林大学离散数学课后习题答案更新完毕开始阅读
§1.3第一章习题解答
1.3.1习题1.1解答
1设S = {2，a，{3}，4}，R ={{a}，3，4，1}，指出下面的写法哪些是对的，哪些是错的？
{a}?S,{a}?R,{a,4,{3}}?S,{{a},1,3,4}?R,R=S,{a}?S,{a}?R,??R,??{{a}}?R?E,{?}?S,??R,??{{3},4}。
解： {a}?S?，{a}?R?，{a，4，{3}} ? S?，{{a}，1，3，4 } ? R?，R = S?，{a}? S?，{a}? R?，? ? R?，? ? {{a}} ? R ? E?，{?} ? S?，??R?，? ? {{3}，4 }?
2写出下面集合的幂集合 {a，{b}}，{1，?}，{X，Y，Z}
解： 设A={a，{b}}，则?(A)={ ?，{a}，{{b}}，{a，{b}}}； 设B={1，?}，则?(B)= { ?，{1}，{?}，{1，?}}；
设C={X，Y，Z}，则?(C)= { ?，{X}，{Y}，{Z}，{X，Y }，{X，Z }，{ Y， Z }，{X，Y，Z}}；
3对任意集合A，B，证明： (1)A?B当且仅当?(A)? ?(B)； (2)?(A)??(B)??(A?B)； (3)?(A)??(B)=?(A?B)；
(4)?(A-B) ?(?(A)-?(B)) ?{?}。 举例说明：?(A)∪?(B)≠?( A∪B)
证明：(1)证明：必要性，任取x??(A)，则x?A。由于A?B，故x?B，从而x??(B)，于是?(A)? ?(B)。
充分性，任取x?A，知{x}?A，于是有{x}??(A)。由于?(A)? ?(B)，故{x}??(B)，由此知x?B，也就是A?B。
（2）证明：
任取X??(A)∪?(B)，则X??(A)或X??(B) ∴ X?A或X?B ∴ X?(A∪B) ∴ X??(A∪B)
所以?(A)∪?(B) ? ?( A∪B) （3）证明：
先证?(A)∩?(B) ? ?( A∩B)
任取X??(A)∩?(B)，则X??(A)且X??(B) ∴ X?A且X?B ∴ X? A∩B ∴ X??( A∩B)
所以?(A)∩?(B) ? ?( A∩B)
9
再证?( A∩B) ? ?(A)∩?(B) 任取Y??(A∩B)，则Y? A∩B ∴ Y?A且Y?B
∴ Y??(A)且Y??(B) ∴ Y??(A)∩?(B)
所以?( A∩B) ? ?(A)∩?(B) 故?(A)∩?(B) = ?( A∩B)得证。
举例：A={1}，B={a}
则?(A)={ ?，{1}}，?(B)={ ?，{a}} ?(A)∪?(B) = { ?，{1}，{a}} A∪B={1，a}
?( A∪B)={ ?，{1}，{a}，{1，a}}
可见{1，a}??( A∪B)，{1，a}??(A)∪?(B) 所以?(A)∪?(B)≠?( A∪B) (4)对任意的集合x，若x=?，则x??( A-B) 且x?(?( A) -?( B))∪{?}。若x??，则x??( A-B)当且仅当x? ( A-B)当且仅当x? A?x?B当且仅当x??( A) ?x??( B) 当且仅当x?(?(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； （4）若A?B且B?C，则A?C。 解：（1）正确；（2）不正确，举一个反例即可；（3）不正确，举一个反例即可；（4）不正确，举一个反例即可。
5.对24名科技人员进行掌握外语情况的调查，其统计资料如下：会英、日、德、法语的人数分别是13，5，10和9。其中同时会英语、日语的人数为2。同时会说英语、德语或同时会说英语、法语，或同时会说德语、法语两种语言的人数均为4。会说日语的人既不会说法语也不会说德语。试求只会说一种语言的人数各为多少？同时会说英、德、法语的人数为多少？
解：设A，B，C，D分别代表会说英、日、德、法语人的集合。由已知条件知： ?A?=13，?B?=5，?C?=10，?D?=9，?A?B?=2，而?A?C?=?A?D?=?C?D?=4，?B?C?=?B?D?=?A?B?C?=?A?B?D?=?B?C?D?=?A?B?C?D?=0， ?A?B?C?D?=24。
对集合A，B，C，D应用容斥原理，并代如入已知条件得方程
24=37-14+?A?C?D?
于是?A?C?D?=1，这说明同时会说英、德、法语的人只有1人。
设只会说英、日、德、法语的人数分别是x1，x2，x3，x4，则
x1=?A?-?（B?C?D）?A?
=?A?-?（B?A ）?(C?A )?( A ?D)?
10
对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