资源描述
第二章 二元关系第一章 集合习题1.11. a) 0, 1, 2, 3, 4b) 11, 13, 17, 19c) 12, 24, 36, 48, 642. a) x | x N 且x 100b) Ev = x | x N 且2整除x Od = x | x N 且2不能整除x c) y | 存在x I 使得 y = 10 x 或 x | x/10 I 3. 极小化步骤省略a) 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 A ；若a, b A，则ab A 。或0, 1, 2, 3, 4, 5, 6, 7, 8, 9 A ；若a A 且 a 0, 1, 2, 3, 4, 5, 6, 7, 8, 9，则aa A 。或0, 1, 2, 3, 4, 5, 6, 7, 8, 9 A ；若a A 且 a 0, 1, 2, 3, 4, 5, 6, 7, 8, 9，则aa A 。b)0, 1, 2, 3, 4, 5, 6, 7, 8, 9 A ；若a, b A 且 a 0，则 ab A 。c)若a 0, 1, 2, 3, 4, 5, 6, 7, 8, 9，则 a. A ；若a A 且 a 0, 1, 2, 3, 4, 5, 6, 7, 8, 9，则aa A ；若a A 且 a 0, 1, 2, 3, 4, 5, 6, 7, 8, 9，则aa A 。或0., 1., 2., 3., 4., 5., 6., 7., 8., 9. A ；若a A 且 a 0, 1, 2, 3, 4, 5, 6, 7, 8, 9，则aa A ；若a A 且 a 0, 1, 2, 3, 4, 5, 6, 7, 8, 9，则aa A 。d)0, 10 A ；若a A，则1a A ；若a, b A 且 a 0，则 ab A 。e)Ev定义如下：0 Ev 或0 Ev ；若a Ev，则a+2 Ev 。Od定义如下：1 Od 或1 Od ；若a Od，则a+2 Od 。f)0 A 或 0 A ；若a A，则 A 。4. A = G；C = F；B = E。5. 题号 是否正确 a) b)（空集不含任何元素） c) d) e) f) g) h) 6. 题号 是否正确 a) （ 反例：A = a；B = ；C = a ） b)（ 反例：A = ；B = ；C = ） c)（ 反例：A = ；B = a；C = ） d)（ 反例：A = ；B = ；C = ）7. 能。例如：B = A A 。8.a) ；1；2；3；1, 2；1, 3；2, 3；1, 2, 3；b) ；1；2, 3；1, 2, 3；c) ；1, 2, 3；d) ；e) ；, ；f) ；1, 2；g) ；, 2；2；, 2, 2；9.a) ，a，b，a, b；b) ，1，1, ；c) ，x，y，z，x, y，x, z，y, z，x, y, z；d) ，a，a，, a，, a，a, a，, a, a。习题1.21.a) A B = 4；b) (A B) C = 1, 3, 5；c) (A B) = 2, 3, 4, 5；d) A B = 2, 3, 4, 5；e) (A B) C = ；f) A (B C) = 4；g) (A B) C = 5；h) (A B) (B C) = 1, 2。2.a) B C 或 B E ；b) A D ；c) (A B) C ；d) C B 或C A ；e) (A C) (E B) 或 (A E) (E B)；3.a) 证明：对于任意x A C，因为x A C，所以x A或x C。若x A，则由于A B，因此x B；若x C，则由于C D，因此x D。所以，x B或x D，即x B D。所以，A C B D。类似可证A C B D。d)A (B C) = A (B C) = A ( B C) = (A A) ( B C)= (A B) (A C) = (A B) (A C)f)A (A B) = A (A B) = A (A B) = A ( A B)= (A A) (A B) = (A B) = A B4. a) ) 若A = B，则A B = A且 A B = A。因此，A B = (A B) (A B) = A A = 。)若A B = ，则A B = A B。又因为A B A A B且A B B A B，所以A B = A = B = A B。所以A = B。5. 证明略。 a) b) c)（反例：A = a, b，B = a，C = b） d)（反例：A = a，B = a, b，C = a, c） e) f) （反例：A = a, b，B = a，C = b） g) （反例：A = a，B = a, b，C = a, c）6. a) B C A；b) A B C；c) A (B C)，即B C A；d) A B C；e) (A B) (A C) = (A B) (A C) = (A B) (A C) (A B) (A C) = (A B) (A C) (A B) (A C) =(A B) (A C) ( (A B) (A C) =(A B) (A C) ( ( A B) (A C) =(A (B C) ( A (B C) =(A (B C) (B C) =A ( (B C) (B C) ) =A (B C) 因此，若(A B) (A C) = A，则A (B C) = A。所以，A (B C)。f) 由上题，(A B) (A C) = A (B C) 因此，若(A B) (A C) = ，则A (B C) = 。g) A = B；h) A = B = ；i) A = B；j) B = ；k) B A 或 A B。7. a) 对于任意x (A) (B)，则x (A) 或x (B)。若x (A)，则x A。因为A A B，所以，x A B。因此，x (A B)。若x (B)，则x B。因为B A B，所以，x A B。因此，x (A B)。所以，总有x (A B)。因此，(A) (B) (A B)。b) 对于任意x (A) (B)，则x (A) 且x (B)。x (A)，因此x A。x (B)，因此x B。所以，x A B。因此，x (A B)。所以，(A) (B) (A B)。8. a) = ， = ；b) , = ，, = ；c) a, b, a, b = a, b，a, b, a, b = 。9. 证明：i) 若x R0，则x R且x 1。所以对于任意iI+均有x 1+1/i。即对于任意iI+均有x Ri。所以，x。ii) 若x ，则对于任意iI+均有x Ri。所以对于任意iI+均有x 0。首先，甲扳倒r根，然后每当乙扳倒x（1 x m）根，因为1 (m+1) x m，所以此时甲可扳倒(m+1) x根，故甲总能获胜。证明：对q（即n除以m+1的商）用第一归纳法。i)当q = 0时，因为n = r且m r 1，所以甲可一次将r根全部扳倒，则甲获胜。ii)对任意的k 0，假设当q = k时命题为真，则当q = k+1时，即存在r使得n = (m+1) (q+1) + r，m r 0 ，由于此时甲可扳倒r根，然后乙只能扳倒x（1 x m）根，此时剩下n = (m+1)q+(m+1)-q根， 因为1 (m+1) x m，则根据归纳假设可知甲总能获胜。即当q = k+1时命题也为真。由i) ii)可知，对于任意q 0均有甲总能获胜。5. 证明：用第一归纳法对于每个i i0，用Q(i)表示下列命题：对于任意j j0，P (i, j)皆真。下面验证：Q(i)满足第一归纳法的条件。i)Q(i0)为真，因为（对j用第一归纳法）：a) P(i0, j0)为真；b) 若P(i0, j)为真，则P (i0, j+1)为真；由归纳法可知，Q(i0)为真。ii)若Q(i)为真（i i0），即对于任意i i0，j j0，P (i, j)为真。则对于任意j j0，P(i+1, j)为真，即Q (i+1)为真。由i)和ii)可知，对于任意i i0，Q (i)皆真。所以，对于任意i i0，j j0，P (i, j)为真。6.证明：假设有n N使n n ，即 n n ，故n+ = nn n ，同时n n+ ，所以n = n+。矛盾！（与皮亚诺公理矛盾）10. 证明：假设有m N使n m，则由“”定义可知n m，所以由习题7有n m。因为n m 且n m，所以 nn m，即n+ m。而m n+，则由“”定义可知m n+，由习题7有m n+。n+ m与m n+矛盾，所以假设不成立，即不可能有m N使n m n+。习题1.41. a)A 1 B = , , , b)A2 B = , , , , , , , c) (B A)2 = , , , , , , , , , , , , , , 2. 题号 是否正确 a) （反例：A=D=a，B=C=，则左边=，而右边=） b) c)（反例：A=C=D=N，B=，则左边=，而右边=NN） d)（反例：A=C=1, 2，B=1，D=2，则左边=，而右边=, , ）7.证明：题目等价于证明：若 = ，则a = c且b = d。设 = ，则a, A, b, B = c, A, d, Ba, A = c, A且b, B = d, B所以，a = c且b = d。a, A = d, B且b, B = c, A则因为AB，所以a = B, d = A, b = A且c = B。所以，a = c且b = d。故总有：a = c且b = d。第二章 二元关系习题2.11. d) R = , , , e) R = , 2. R1 R2 = , , , , R1 R2 = dom R1 = 1, 2, 3dom R2 = 1, 2, 4ran R1 = 2, 3, 4ran R2 = 2, 3, 4dom (R1 R2) = 1, 2, 3, 4ran (R1 R2)= 43. 证明：（根据定义域和值域的定义进行证明）因为x dom (R1 R2) 当且仅当有y B使得 (R1 R2)当且仅当有y B使得 R1 或 R2当且仅当有y B使得 R1 或有y B使得 R2当且仅当x dom (R1) 或 x dom (R2)当且仅当x dom (R1) dom (R2)所以，dom (R1 R2) = dom (R1) dom (R2) 。因为若x ran (R1 R2)，则有x A使得 (R1 R2) ；有x A使得 R1 且 R2 ；有x A使得 R1 且 有x A使得 R2 ；x ran (R1) 且 x ran (R2) ；x ran (R1) ran (R2) 。所以，ran (R1 R2) ran (R1) ran (R2) 。4. L = , , , , , ；D = , , , , , , , , ；L D = , , , , 。5. a) 上的空关系；b) 集合 1, 2 上的二元关系 ；c) 集合 1, 2 上的二元关系 ；d) 集合 1, 2, 3 上的二元关系 , , ；6.若R, S自反，则R S , R S自反，R S , R S必不自反。若R, S反自反，则R S , R S , R S , R S反自反。若R, S对称，则R S , R S , R S , R S对称。若R, S反对称，则R S , R S反对称，R S , R S不一定反对称。若R, S传递，则R S传递，, R S , R S , R S不一定传递。8.a) S是对称的、传递的；b) S是自反的、对称的；c) S是反对称的、传递的；d) S是反自反的、反对称的、传递的；8.n ( Am ) = nm ；n ( Am ) ) = ；因为R Am，所以A上共有个m元关系。10.证明： 用反证法。假设R不是反对称的，即存在a, b A，使得 A, A 且a b。因为R是传递的，所以由 A且 A可知 A。这与R反自反性质矛盾。所以假设不成立。即R是反对称的。11.证明：因为R = | x, y A 且 R = x, x, y | x, y A 且 R 所以， R = x, x, y | x, y A 且 R 。所以，(R) = x | x A且有y A使得 R y | y A且有x A使得R 。 = dom R ran R 。即：fld R = dom R ran R 。12.证明：因为dom R fld R = ( R )，ran R fld R = ( R )，所以，R dom R ran R ( R ) ( R ) 。习题2.21.R是自反的、对称的、传递的。2.(1) 自反的；(2) 反对称的、传递的；(3) 自反的、对称的、传递的；(4) 自反的、传递的；(5) 无；(6) 对称的；(7) 自反的、反对称的、传递的；(8) 对称的；(9) 对称的；(10) 反对称的；(11) 自反的、反对称的；(12) 反对称的、传递的。4.b) A上共有个不相同的自反关系；c) A上共有个不相同的反自反关系；d) A上共有个不相同的对称关系；e) A上共有个不相同的反对称关系；f) A上共有个不相同的既是对称的又是反对称的关系；习题2.31. 最多能有n(A) 个元素为1。2. 证明：i)R R-1为A上包含R的最小对称关系R R R-1。所以，RR-1包含R。因为对于任意 R R-1，有 R或 R-1。若 R，则 R-1；若 R-1，则 R。因此， R R-1。所以，RR-1为A上的对称关系。 设R为任意的A上包含R的对称关系，则对于任意 R R-1，有 R或 R-1。若 R，由于R包含R，所以 R；若 R-1，则 R，由于R包含R，所以 R，而R对称，所以 R。因此，总有 R。所以，R R-1 R。由可知，R R-1为A上包含R的最小对称关系。ii)R R-1为A上包含在R中的最大对称关系R R-1 R。所以，R R-1包含在R中。因为对于任意 R R-1，有 R且 R-1。 R，所以 R-1； R-1，所以 R。因此， R R-1。所以，R R-1为A上的对称关系。 设R为任意的A上包含在R中的对称关系，则对于任意 R，由于R包含在R中，所以 R；又由于R对称，所以 R，而R包含在R中，所以 R，因此， R-1；因此，总有 R R-1。所以，R RR-1。由可知，R R-1为A上包含在R中的最大对称关系。习题2.41. R2 O R1 = ；R1 O R2 = , ；R12 = , , ；R22 = , ；2. m = 1, n = 16。4. A = 1, 2, 3令R1 = , ；R2 = ；R3 = ；则R1 O ( R2 R3 ) = ；( R1 O R2 ) ( R1 O R3 ) = ；所以，R1 O ( R2 R3 ) ( R1 O R2 ) ( R1 O R3 ) 。令R2 = ；R3 = ；R4 = , ；则( R2 R3 ) O R4 = ；( R2 O R4 ) ( R3 O R4 ) = ；所以，( R2 R3 ) O R4 ( R2 O R4 ) ( R3 O R4 ) ；5.a) 正确。b) 不正确。令A = 1, 2，则R1 = , R2 = 都是反自反的，但R1 O R2 =不是反自反的。c) 不正确。令A = 1, 2, 3，则R1 = , , R2 = , 都是对称的，但R1 O R2 = 不是对称的。d) 不正确。令A = 1, 2, 3，则R1 = , , R2 = , 都是反对称的，但R1 O R2 = , 不是反对称的。e) 不正确。令A = 1, 2, 3，则R1 = , , , R2 = , 都是传递的，但R1 O R2 = , , 不是传递的。9. 证明：a)对于任意k N，因为Rs = Rt ，所以Rs+k = Rs Rk = Rt Rk = Rt+k 。b)用关于k的归纳法证明。i)当k=0时，Rs+i = Rs+i。所以命题成立。ii)假设当k=m时命题成立，即Rs + mp + i = Rs + i。则当k=m+1时，因为Rs + (m+1) p + i=Rs + p + mp+ i=Rt + mp + i=Rt Rmp+i =Rs Rmp+i =Rs + mp + i。由归纳假设，Rs + (m+1) p + i = Rs + mp + i = Rs + i。由i) ii)可知对于任意k, i N，均有Rs + kp + i = Rs + i 。f) 若k t-1，则Rk R0, R1, , Rt-1；若k t，则k = s + (t-s)q + r，即k = s + pq + r；（其中，q N, 0 r t-s = p）此时，由b)可知Rk = Rs + pq + r = Rs + r R0, R1, , Rt-1。所以，若k N，则Rk R0, R1, , Rt-1。习题2.52. 使t (R1 R2) t ( R1 ) t ( R2 ) 的R1 和R2 的具体实例如下：A = 1, 2，R1 = ，R1 = ；则t ( R1 ) = R1 ，t ( R2 ) = R2 ，t (R1 R2) = , , , ， 故真包含。4. b) 使s (R1 R2) s ( R1 ) s ( R2 ) 的R1 和R2 的具体实例如下：A = 1, 2，R1 = ，R1 = ；则s ( R1 ) = s ( R2 ) = , ，s (R1 R2) = s() = 。 故真包含：s (R1 R2) s ( R1 ) s ( R2 )。b) 使t (R1 R2) t ( R1 ) t ( R2 ) 的R1 和R2 的具体实例如下：A = 1, 2, 3，R1 = , ，R1 = , ；则t ( R1 ) = , , , ，t ( R2 ) = , , , ，t (R1 R2) = s() = 。 故真包含：t (R1 R2) t ( R1 ) t ( R2 )。6.令A = 1, 2，R = ，则ts(R) = t (, ) = , , , st(R) = s () = , 所以，st(R) ts(R)。习题2.61. a) 正确；b) 正确；c) 不正确；（不自反）d) 不正确；（不自反）e) 不正确；（不一定对称）f) 正确。2.R的所有极大相容类为：x1, x2, x3，x1, x3, x6，x3, x4, x5，x3, x5, x6。3.A上共有个不相同的相容关系。习题2.71. a) 不正确；（不自反）b) 不正确；（不自反）c) 不正确；（不自反）d) 不正确；（不传递， R, R, 但 R）e) 不正确；（不对称）f) 不正确；（不对称）g) 不正确；（不传递）h) 正确；i) 不正确。（不自反，i = 10k时， R）2.不对。应加上条件：对于任意xA，总存在yA使得 R。3.证明： 已知条件：若 R， R，则 R。先证对称性：若 R，则由于R自反，所以 R，由上式有 R。所以R对称。再证传递性：若 R， R，则因为R对称，所以 R。由已知条件，因为 R且 R，所以 R。所以R传递。因此，R时等价关系。 已知条件：R是等价关系。若 R， R，则因为R对称，所以 R。又由于R传递，所以， R。因此，若 R， R，则 R。习题2.81. a) 半序；b) 半序、全序、良序；c) 无；（不是反对称的）d) 无；（不是传递的）e) 半序；f) 无；（不是传递的）g) 无；（不是传递的）h) 拟序。4.设R是集合A上的二元关系，证明：a)R是A上的半序，当且仅当R R-1 = IIA且R = R*。自反、反对称_ _传递b)R是A上的拟序，当且仅当R R-1 = 且R = R+。反自反_ _传递6.a)断言中为真的有：x4Rx1, x1Rx1。b)P的最小元：无；P的最大元：x1 ；P的极小元：x4和x5；P的极大元：x1 。c)x2, x3, x4的上界：x1；下界：x4；上确界：x1；下确界：x4。x3, x4, x5的上界：x1, x3；下界：无；上确界：x3；下确界：无。x1, x2, x3的上界：x1；下界：x4；上确界：x1；下确界：x4。7.a) 中的非空子集I无最小元。b) （“|”为整除关系）中的非空子集x | x 4无最大元。c) 中的非空子集(0, 1)由下确界0，但无最小元。d) 书上例4中的非空子集4有上界8和12，但无上确界。8.归纳法。9.归纳法。第三章 函数习题3.11. g) 不是部分函数；原因：存在, f，但1 2 。h) 部分函数；i) 不是部分函数。原因：存在, f，但2 -2 。2. a) 部分函数；定义域为：1, 2, 3, 4，值域为：, , 。b) 部分函数；定义域为：1, 2, 3，值域为：, , 。c) 不是部分函数；d) 部分函数。定义域为：1, 2, 3，值域为：。3. 证明：证明分两部分： 部分函数之单值性； dom f = (A) (A) 。5. e) 证明：对于任意y f A f B，则y f A 且 y f B 。因为y f A ，所以存在x A 使得 f (x) = y 。又因为y f B，所以x B。（用反证法，假设x B，则f (x) f B，而y = f (x)，所以y f B。矛盾）所以，x A - B 。因此，y = f (x) f A-B。于是，f A-B f A f B。“=”不能代替“”的反例，令X = x1, x2 ，Y = y ，f = , 。A = x1, x2 ，B = x1 。则f A-B = y，而f A f B = 。6.e) f = , 0, , -1, , -2, , 1, , 0, , -1, , 2, , 1, , 0 ；f) ran f = -2, -1, 0, 1, 2；g) f 0, 12 = , 0, , -1, , 1, , 0 ；h) 参见下题。7.a) m n，个； m n，0个。b) m n，0个； n = 0且m 0，0个； n = 0且m = 0，1个； m n 1，第二类Stirling数。8.a) 证明：f (99) = f ( f (110) ) = f (100) = f ( f (111) ) = f (101) = 91。b) 证明： f (100) = f (99) = 91； i 1, 2, , 9，f (89 + i) = f (90 + i)，所以f (89) = f (90) = = f (99) = 91。f (89 + i) = f ( f (89 + i + 11) ) = f (90 + i)。 假设当k+1 x 100时，f (x)均等于91。(0 k 89)则当x = k ( k 0 ) 时，则有 f (k) = f ( f (k+11) )。而0 k 89，所以 k+1 k+11 100，由归纳假设有f (k+11) = 91，即f (k) = f (91) = 91。所以，f (x) = 91对于0 k 89也成立。习题3.24.归纳法。5.证明： 因为f : AA为满射，所以 a A . $ xa A使得f ( xa ) = a。又因为f o f = f，所以f (a) = f ( f ( xa ) ) = f o f ( xa ) = f ( xa ) = a ，即 f (a) = a。所以 II A f 。 对于任意 f ，因为II A f ，所以 f 。而f为部分函数，即“单值”，于是，x = y 。所以 = II A 。所以f II A 。 另证下面要证明II A f不可能。用反证法，假设II A f，则存在a a使得f (a) = a。因为f为满射，所以必存在x a A使得f (x a) = a。因为f o f = f，所以a = f (x a) = f o f (x a) = f ( f (x a) ) = f (a ) = a ，即 a = a。这与a a矛盾。所以假设不成立，即II A f不可能。由可知II A = f 。6.证明：首先，dom (g o f ) = f -1 dom g。因为ran f dom g ，所以dom f = f 1 ran f f 1 dom g 。又因为dom g Y，而f -1 Y = domg f，所以f 1 dom g f 1 Y = dom f。所以，dom (g o f ) = dom f 。8.a) 因为f o f = f ，所以对于任意i A，均有f (f (i) ) = f (i) 。即若f (i) = j ( j i )，则f (j) = i。设m为集合 i | i A且f (i) = i 的元素个数，即m为f中对应到自身的二元序偶个数。则对m求累加和得到满足f o f = f的函数个数为个。b) f o f = II A，所以f为双射，并且对于任意i A，均有f (f (i) ) = i（即若f且ij，则f ）。（特征：未对应到自身的二元序偶个数必为偶数个。）设k为集合 i | i A且f (i) = i 的元素个数/2，即2k为f中对应到自身的二元序偶个数。则对k求累加和得到满足f o f = II A的函数个数：当n为偶数时，有个；当n为奇数时，有个。c) f o f o f = II A ，所以f为双射，因此满足f o f o f = II A的函数个数：当n = 3k+1 ( k N ) 时，有个；当n = 3k+2 ( k N ) 时，有个；当n = 3k ( k N ) 时，有个。9.a) 证明：因为g o f 为满射，所以g为满射。而g又是内射，所以g为双射。假设f不是满射，则存在y Y使得 y ran f。而g是双射，所以g (y) Z，又g o f 为满射，所以ran (g o f ) = Z。即g (y) ran (g o f )。所以存在x X使得 g (y) = g o f (x) = g ( f (x) )。因为g为内射，所以y = f (x)。因此，y ran f。这与y ran f矛盾。所以假设不成立，即f 是满射。b) 证明：因为g o f 为内射，所以f为内射。而f又是满射，所以f为双射。假设g不是内射，则存在y1, y2 Y使得 y1 y2并且 g (y1) = g (y2) 。因为f为双射，所以存在x1, x2 X使得 x1 x2并且 f (x1) = y1，f (x2) = y2 。而g o f 为内射，则 g o f (x1) g o f (x2) ，即 g (y1) g (y2)。这与g (y1) = g (y2)矛盾。所以假设不成立，即g 是内射。习题3.33. a) k (x) = x / 3 ；b) k (x) = (x+1) / 3 ；c)4. f左可逆，但g不一定左可逆。证明：因为g o f左可逆，则g o f为内射，所以f为内射。g不一定左可逆，反例如下：A = a， B = b1, b2， C = c。f = ，g = , ，g o f = 。所以，g o f是内射，即是左可逆的；但g不是内射，即不是左可逆的。5.证明：f是可逆的，则易证f又唯一的左（右）逆。另一边证明以“f有唯一左逆，则f可逆。”为例。a A，g = f-1 ( Y ran f ) a)就是f的一个左逆。而f仅有唯一左逆且n(A)2 ，这说明Y ran f = ，即ran f = Y。所以，
展开阅读全文