国防科大版离散数学习题答案.doc

第二章 二元关系第一章 集合习题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) 不正确；（