洪帆《离散数学基础》第三版课后习题答案.pdf

1 第 1 章 集合 1、列举下列集合的元素 (1) 小于 20 的素数的集合 (2) 小于 5 的非负整数的集合 (3) 2 | , 10 24 0 5 15 ii Ii i i < 且 答：(1) 1,3,5,7,11,13,17,19 (2) 0,1, 2,3, 4 (3) 5, 6, 7,8,9,10,11 2、用描述法表示下列集合 (1) 12345 , aaaaa 答： | ,1 5 i ai I i (2) 2, 4,8, 答：2 | i iN (3) 0, 2, 4, 100 答：2 | , 0 50 ii Z i 3、下面哪些式子是错误的？ (1) aa 答：正确 (2) aa 答：错误 (3) , a aa 答：正确 (4) , a aa 答：正确 4 、 已给 2, , 3, 4 Sa = 和 ,3,4,1 Ra = ，指出下面哪些论断是正确的？哪些是 错误的？ (1) aS 错误 2 (2) aR 正确 (3) , 4, 3 aS 正确 (4) ,1,3,4 aR 正确 (5) RS = 错误 (6) aS 正确 (7) aR 错误 (8) R 正确 (9) aR 正确 (10) S 错误 (11) R 错误 (12) 3,4 正确 5、 列举出集合 , ABC 的例子，使其满足 AB ， BC 且 AC 答： Aa = ， Ba = ，显然 AB ， Ca = ，显然 BC ，但是 AC 。 6、 给出下列集合的幂集 (1) , ab 答：幂集 , , , , a b ab (2) , , aa 答：幂集 , , , , , , , , , , , , a a a a aa aa 7、设 Aa = ，给出 A 和 2 A 的幂集 答： 2 , A a = 2 2 , , , , A aa = 8 、 设 12 8 , , , A aa a = 由 17 B 和 31 B 所表示的 A 的子集各是什么？应如何表示子 集 2, 6 7 , aa a 和 13 , aa 答： 17 00010001 4 8 , B B aa = = 3 31 00011111 4 5 6 7 8 , , , , B B aaaaa = = 2, 6 7 01000110 70 , aa a B B = = ， 1 3 10100000 160 , aa B B = = 9、 设 1, 2,3, 4,5 U = ， 1, 4 A = ， 1, 2, 5 B = ， 2, 4 C = ，确定集合： (1) AB (2) () AB C (3) () A BC (4) ( )( ) AB AC (5) () AB (6) AB (7) () BC (8) BC (9) 22 AC (10) 22 AC 答：(1) 3, 4 B = ， 4 AB = (2) 1 AB = ， 1 ,3 ,5 C = ， ( ) 1 ,3 ,5 AB C = (3) 2 BC = ， ( ) 1 ,2 ,4 A BC = (4) 1, 2, 4,5 AB = ， 1 ,2 ,4 AC = ， ( ) ( ) 1 ,2 ,4 AB AC = (5) ( ) 2,3, 4,5 AB = (6) 2,3 ,5 A = ， 2,3, 4,5 AB = (7) 1, 2, 4,5 BC = ， ( ) 3 BC = (8) 3, 4 B = ， 1 ,3 ,5 C = ， 3 BC = (9) 2 , 1 ,4, 1,4 A = ， 2 ,2,4 2 4 C = ， ， ， 2 2 1 , 1,4 AC = (10) 2 2 ,4 AC = 10、 给定自然数集 N 的下列子集： 1, 2, 7 , 8 A = ， 2 | 50 B ii = < ， | 3 30 C ii i = 可 被 整数 ，0 | 2 , , 0 6 k D ii k Z k = = 求下列集合： (1) ( ( ) A B CD 答： 1, 2,3, 4,5, 6, 7 B = ， 0,3,6,9,12,15,18,21,24,27,30 C = ， 1, 2, 4,8,16,32, 64 D = ( ( ) 0,1, 2,3, 4,5, 6, 7,8,9,12,15,16,18, 21, 24, 27,30,32,64 A B CD = (2) ( ( ) A B CD = 4 (3) () B AC 解： 0,1,2,3,6,7,8,9,12,15,18,21,24,27,30 AC = ， ( ) 4, 5 B AC = (4) () AB D 解： 3, 4, 5, 6 A BBA = ， ( ) 1, 2,3, 4,5, 6,8,16,32, 64 AB D = 11 、 给定自然数集 N 的下列子集 | 12 A nn = 是偶 数且 或 是奇数 且 (6) | 6 nn 是 的倍数 答： 1, 2,3, 4,5, 6, 7,8,9,10,11 A = ， 1, 2,3, 4,5, 6, 7,8 B = 2, 4, 6,8, C = ， 3, 6,9,12, D = ， 1 ,3 ,5 ,7, E = 2, 4, 6,8 BC = 3, 6, 9 = AD 1 0 = ( ) ) AB D E (4) | 369 nn n n = = = 或 或 3 6 9,10,11,12, 3, 6,9,10,11,12, ( ) AD B = = (5) 2, 4, 6,8,10,11,13,15, ( ) ( ) ( ) ) AE EB A D B = (6) | 6 6,12,18, 24,30 nn = = 是 的倍数 CD 12、 判断以下哪些论断是正确的，哪些论断是错误的，并说明理由。 (1) 若 aA ，则 aAB 5 答：正确，根据集合并的定义 (2) 若 aA ，则 aAB 答：显然不正确，因为根据集合交运算的定义，必须 a 同时属于 A 和 B (3) 若 aAB ，则 aB 答：正确 (4) 若 AB ，则 ABB = 答：错误 (5) 若 AB ，则 ABA = 答：正确 (6) 若 aA ，则 aAB 答：错误 (7) 若 aA ，则 aAB 答：正确 13、 设 , ABC 是任意的集合，下述论断哪些是正确的？哪些是错误的？说明理 由 (1) 若 ABAC = ，则 BC = 答： 不正确， 反例， 设 A = ， 则不论 , BC 是什么集合， 都有 ABAC = ， 但显然 , BC 不一定相等。 (2) 当且仅 当 ABB = ，有 AB ； 答： 正确， 证明如下： 若 ABB =，则 对 aA ，有 aABB =，则 有 aB ， 因此有 AB 。反之，若 AB ，则 ABB = 显然成立。 (3) 当且仅 当 ABA = ，有 AB 答：正确，证明如下：若 ABA = ，则对 aA ，因此 aAB ，则 aB ， 则有 AB 。若 AB ，则 aA ，有 aB ， 因此由 aA ， 可以得出 aAB ， 因此 A AB ，又 AB A ，有 ABA = 。 6 (4) 当且仅 当 AC ，有 () A BC = 答：不正确，因为 () A BC A B C = ，因此不一定需要满足 AC ，而若 AB = 也可以满足。 例如： , A abc = ， , B de = ， , C ab = ， () A BC = 成立，而 AC 不成立。 (5) 当且仅 当 BC ，有 () AB C A = 答：不正确，因为若 BC ，有 () AB C A = 成立，但是反之不成立，反例如 下: 1, 2,3, 4,5 A = ， 1, 6 B = ， 1, 2 C = ，而 2,3, 4,5 AB = ， ( ) 1, 2,3, 4,5 AB C = ，但是 BC 不成立。 14、 设 , ABCD 是集合，下述哪些论断是正确的？哪些是错误的？说明理由。 (1) 若 , A BC D ，则 () AC BD 答： 正确， 证明： 对 aAC ，则 aA 或 aC ，因 为 , A BC D ，因 此 aB 或 aD ，因此 aBD ，即 () AC BD 成立。 (2) 若 , A BC D ，则 () AC BD 答：正确 (3) 若 AB ，CD ，则 () AC BD 答：正确 (4) 若 , A BC D ，则 () AC BD 答：不正确。例如若 , A BC D ，但是 AC = ， BD = ，则 () AC BD = 。 15、 设 , AB 是两个集合，问： (1) 如果 AB B = ，那么 A 和 B 有什么关系？ 答：因为 AB B = ，而 AB A B B = ，即对 aB 有 , a Aa B ，因此7 AB = = 。 (2) 如果 AB BA = ，那么 A 和 B 有什么关系？ 答： 充要条件是 AB = 。 证明： 因为 AB BA = 的 () () AB A BA A = ，从 而有 AAB = ，即 AB ，同理可证明 BA ，因此 AB = 。 16、 设 , AB 是任意集合，下述论断哪些是正确的？哪些是错误的？说明理由。 (1) 2 22 AB A B = 答：不正确。例如 , A ab = ， , B bc = ，则 , A B abc = 2 , , , , , , , , , , , , AB a b c ab ac bc abc = 2 , , , , A a b ab = ， 2 , , , , B b c bc = 显然 2 22 AB A B = 不成立。 (2) 2 22 AB A B = 答：成立。证明：对 22 AB C ，则 2 A C 且 2 B C ，则 , C AC B ，则 C AB ，因 此 2 AB C 。反 之 ，若 2 AB C ，则 C AB ，则 CA 且CB ， 因此 2 A C ，且 2 B C ，因此 22 AB C ，即 2 22 AB A B = 。 (3) 2 (2 ) AA = 答：显然不成立，因为左边集合肯定含有 ，而右边不含有。 17、 在一个班级的 50 个学生中，有 26 人在离散数学的考试中取得了优秀的成 绩；21 人在程序设计的考试中取得了优秀的成绩。 假如有 17 人在两次考试中都 没有取得优秀成绩，问有多少人在两次考试中都取得了优秀成绩? 答： 分别用 , AB 表示在离散和程序设计的考试中取得优秀成绩的学生集合， U 表 示全体学生集合： 则 #( ) 26 A = ，#( ) 21 B = ，#( ) 50 17 33 AB = ， 则两次考试 中都取得了优秀成绩的学生人数为 26+21-33=14 人。 18、 设 , ABC 是任意集合，运用成员表证明： (1) ( )( )( )( ) AB A C AC A B = 证明： 8 A B C A AC AB AC AB 左边 右边 0 0 0 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 1 0 1 1 1 0 1 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 1 1 1 0 1 1 (3) ( )( )( ) A B C AB AC = 证明： A B C AB AC ( )( ) AB AC BC () A BC 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 1 0 0 1 1 1 0 1 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 0 1 1 1 0 0 0 1 0 由上得证左右两边相等。 19、由 S 和T 的成员表如何判断 ST ？应用成员表证明或否定 ( )( ) AB BC AB 答：先分别给出集合 ( )( ) AB BC 和 AB 的成员表如下： A B C AB BC () BC ( )( ) AB BC B AB 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 1 0 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 1 0 1 1 1 1 1 0 1 1 1 0 0 1 1 1 1 0 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 观察上述表格，我们发现 ( )( ) AB BC 所标记的列中，仅在第五列为 1，这9 意味着当元素 , u Au B 且 uC 时， ( )( ) u AB BC ，而在其他情形下， 元素 ( )( ) u AB BC 。而集合 AB 所标记的列中，第五和第六行均为 1 ， 这意味着 , u Au B 且uC 时，uAB ，当 , u Au B ，且uC 时，也有 uAB 。所以当元素 ( )( ) u AB BC 时也有uAB ，反之不然，因 此 ( )( ) AB BC AB 成立。 20、 12 , r AA A 为U 的子集， 12 , r AA A 至多能产生多少不同的子集？ 答： 构造由 12 , r AA A 所产生的集合的成员表， 显然该成员表由 2 r 个行所组成。 在该成员表中不同的列可由 2 r 为的二进制数 000 01111 1 分别表示， 而不同 的列所标记的集合 不相同的，因此由 12 , r AA A 至多可以产生 2 2 r 个不同的集 合。 21、证明分配律、等幂律和吸收律9 1 分配律 () () () A BC AB AC = 证明： 对 () aA BC ，则 有 aA 且 aBC ，即 有 aA ，且 aB 或 aC ， 也即有 aAB 或 aAC ，即 ( )( ) a AB AC ，因此左边 右边。 对 ( )( ) a AB AC ，则 aAB 或 aAC ，即 aA 且 aB ， 或 aA 且 aC ，即有 aA 或 aBC ，因此 () aA BC ，因此右边 左 边。 2 吸收律 () A AB A = 证明： () A AB A 显然成立，对 aA ，则显然有 aAB ，因此有 () aA AB ，因此有 () A A AB 成立。 22、设 , ABC 是任意集合，运用集合运算定律证明： (1) ( ) ) B AB A U = 10 证明： () () ( () () ) ( () )() B AB A B AB A B A A A B BU AB B ABU = = = 左边 右 边 (2) ( )( )( )( )( )( ) AB BC C A AB BC C A = 证明： ( () ) () ( ) ) ( ) ( ) ( )( )( ( )( ) ( )( )( )( ) B AC C A CA B CA A C C B B A AC A ACC C B B A AC AC = = = = 左 边 右边 (3) ( )( )( )( )( )( ) AB BC AC AB A BC AB C = 证明： ( ( ) ) ( ) ( ( )( ) )( ) ( ( ) ( ) ( )( )( ) ( ) ( ( ) ) ( )( ( )( ) ) () ( () ) ( )( )( ) B A C A AB C B A A AC AB C B AC AB C BA BC AB C BC A B C B BC A B B BC BC A BC BC AB AC = = = = = = = = 右边 由上题的证明可知左边= 右边，得证。 23、用得摩根定律证明 ( ) ( ( ) AB A BC 补集是 ( )( )( ) A B AB AC 。 证明： ( ) ( ( ) ( ) ) ( ( ) ( ) ( ( ) ( ) ( ( ) ( )( )( ) AB A BC AB A BC A B A BC AB A BC A B AB AC = = = = 24、设 i A 为某些实数的集合，定义为 0 | 1 1 | 1 ( 1, 2, ) i A aa A aa i i = < = = 试证明： 0 1 i i AA = = 11 证明：设 1 i i aA = ，则比存在整数 k ，使得 k aA ，因此有 1 1 a k ，于是 1 a < , 因此 0 aA 。 另一方面， 设 0 aA ，则 有 1 a < ，若 0 a ，则 有 1 aA ，因 此 1 i i aA = 。 若 01 a < ，因 此 11 11 1 a k b = 解： 定义域 6,5, 4,3, 2 D = ， 5, 4,3, 2,1 R = (5) ( , ) | ij i j = < (1,1),(2, 2),(3,3),(4, 4),(5,5),(6,6),(2,1), (3,1) (4,1),(5,1),(6,1),(4, 2),(6, 2),(6,3) = (6,5), (6, 4), (6,3), (6, 2), (6,1) (5, 4),(5,3),(5, 2),(5,1) (4,3), (4, 2), (4,1) (3, 2),(3,1) (2,1) = 100 000 000 010 000 111 110 100 M = 14 解：定义域 5, 4,3, 2,1 D = ， 6,5, 4,3, 2 R = (6) ( , ) | , 10 i j i j ij = < 解： 定义域 6,5, 4,3, 2,1 D = ， 6,5, 4,3, 2,1 R = (7) 2 ( , ) | ,( ) ij i j i j A = 解： 定义域 DA = ， RA = (8) ( , ) | / ij i j = 是素数 解： (2,1),(3,1),(5,1),(4, 2),(6,3),(6, 2) = 定义域 2,3, 4,5, 6 D = ， 1, 2, 3 R = 6 、 设 1 (1, 2),(2, 4),(3,3) = 和 2 (1,3),(2, 4),(4, 2) = ，试求出 12 12 , ， 1 D ， ， ， 和 ， 并证明： 12 () D = 1 2 DD 12 1 2 () R RR 解： 12 (1, 2),(2, 4),(3,3),(1,3),(4, 2) = 12 (2, 4) = 1 1, 2, 3 D = ， 2 1 ,2 ,4 D = ， 1 2, 4,3 R = ， 2 3 ,4 ,2 R = 12 () 1 ,2 ,3 ,4 D = 12 () 4 R = 证明： 12 () D = 1 2 DD 设 12 () xD ，则必存在 y ，使得 12 (, ) xy ，所以 1 (, ) xy 或者 2 (, ) xy ， 因此， 1 xD 或者 2 xD ，即 12 xD D ，所 以 12 () D 1 2 DD ； 反之， 设 x 1 2 DD ，则 x 1 D 或者 2 xD ， 所以存在 1 y ，使 得 1 (, ) xy ( 1 ,1 ),( 1 ,2),( 1 ,3 ),( 1 ,4),( 1 ,5),( 1 ,6),(2,1), (2, 2), (2,3) (2, 4),(3,1),(3, 2),(3,3),(4,1),(4, 2),(5,1),(6,1) = (1,1),(1, 2),(1,3),(2,1),(2, 2),(2,3),(2, 4),(3,1) (3, 2),(3,3),(3, 4),(3,5),(4, 2),(4,3),(4, 4), (4,5) (4,6) (5,3),(5, 4),(5,5),(5,6),(6, 4),(6,5),(6,6) = ， (1, 2),(1,3),(1, 4),(1,5),(1,6), (2,3),(2, 4), (2,5), (2, 6) (3, 4),(3,5),(3,6),(4,5),(4,6),(5,6) = 12 () D 2 D 1 R 2 R 12 () R 15 1 ，或者存在 2 y ，使得 2 (, ) xy 2 ，由 并集的定义 知， 1 (, ) xy 12 ，或者 2 (, ) xy 12 ，总之有 12 xD ，故 12 DD 12 () D 。 证明： 12 1 2 () R RR 设 12 yR ，则必存在 x ，使得 (, ) xy 1 ， (, ) xy 2 ，因此 1 bR 且 2 bR ，由交集的定义 11 bR R ，故 12 1 2 () R RR 。 7、 1 A 和 2 A 是分别具有基数 1 n 和 2 n 的有限集， 试问有多少个 1 A 到 2 A 的不同关系？ 答： 2 1 A A 的所有子集都是 1 A 到 2 A 的一个关系， 所以共有 ) 2 1 ( # 2 A A 个不同的关系。 8 、 找出集合 , , , 2 1 n a a a A = 上普遍关系和恒等关系的关系矩阵和关系图的特 征。 答：A 上的普遍关系 2 A = 的关系矩阵是全 1 矩阵， 而恒等关系的关系矩阵是单 位矩阵。 9 、 下列是集合 3 , 2 , 1 , 0 = A 上的关系： 2 / 1 | ) , ( 1 i j i j j i = + = = 或者 ， 2 | ) , ( 2 + = = j i j i ，试确定如下的复合关系： （1） 2 1 （2） 1 2 （3） 1 2 1 （4） 3 1 解 ：（ 1） ) 1 , 2 ( ), 0 , 0 ( ), 3 , 2 ( ), 2 , 1 ( ), 1 , 0 ( 1 = ， ) 1 , 3 ( ), 0 , 2 ( 2 = ) 1 , 2 ( ), 0 , 1 ( 2 1 = （2） ) 1 , 3 ( ), 0 , 2 ( ), 1 , 2 ( 1 2 = （3） ) 2 , 2 ( ), 0 , 1 ( ), 1 , 1 ( 1 2 1 = （4） ) 2 , 2 ( ), 0 , 0 ( ), 1 , 0 ( ), 1 , 1 ( ), 3 , 1 ( ), 2 , 0 ( 2 1 = ) 1 , 2 ( ), 3 , 2 ( ), 1 , 0 ( ), 0 , 0 ( ), 2 , 0 ( ), 2 , 1 ( ), 1 , 0 ( ), 3 , 0 ( 3 1 = 10、 设 3 2 1 , , 是集合 A 上的关系，试证明：如果 2 1 ，则有： （1） 3 2 3 1 （2） 2 3 1 3 （3） 2 1 证明： （1）对 3 1 ) , ( y x ， 由复合关系的定义， A z ， 使得， 1 ) , ( z x ， 3 ) , ( y z ，因为 2 1 ，所以 2 ) , ( z x ，所以 3 2 ) , ( y x ，所以 3 2 3 1 （2）对 1 3 ) , ( y x ， 由 复合关系的定义， A z ，使 得 ， 3 ) , ( z x ， 1 ) , ( y z ， 因为 2 1 ，所以 2 ) , ( y z ，所以 2 3 ) , ( y x ，所以 2 3 1 3 。 （3）对 1 ) , ( y x ，有 1 ) , ( x y ，因 为 2 1 ，所 以 2 ) , ( x y ，所 以 2 ) , ( y x ，16 也即 2 1 。 11 、 给定 ) 4 , 3 ( ), 2 , 1 ( ), 1 , 0 ( 1 = ， ) 3 , 3 ( ), 4 , 1 ( ), 3 , 1 ( 2 1 = 求一个基数最小的关系， 使满足 2 的条件。一般地说，若给定 1 和 2 1 ， 2 能被唯一的确定吗？基数 最小的 2 能被唯一确定吗？ 答： ) 3 , 4 ( ), 4 , 2 ( ), 3 , 2 ( 2 = 。 一般地说， 若给定 1 和 2 1 ， 2 不能被唯一的确 定。基数最小的 2 也不能被唯一确定。 12 、 给定集 合 3 2 1 , , A A A ，设 1 是由 2 1 A A 到 得关系， 2 和 3 是由 3 2 A A 到 得关系 ， 试证明： （1） ) ( 3 2 1 = ) ( ) ( 3 1 2 1 证明：根据并集和复合关系的定义， ) ( 3 2 1 和 ) ( ) ( 3 1 2 1 都是 3 1 A A 到 上的关系，下只需要证明它们由完全相同的序偶组成。 设 ) ( ) , ( 3 2 1 c a ，必存在 2 A b ，使得 1 ) , ( b a ， 3 2 ) , ( c b ，所以 有 2 ) , ( c b 或者 3 ) , ( c b ，所以有 2 1 ) , ( c a 或者 3 1 ) , ( c a ，也即 ) ( ) ( ) , ( 3 1 2 1 c a ，也即 ) ( 3 2 1 ) ( ) ( 3 1 2 1 ；反之，若 ) , ( c a ) ( ) ( 3 1 2 1 ，也即 ) , ( c a ) ( 2 1 或者 ) , ( c a ) ( 3 1 ，若 ) , ( c a ) ( 2 1 ， 则存在 2 A b ，使 得 1 ) , ( b a ， 2 ) , ( c b ，则 1 ) , ( b a ， 3 2 ) , ( c b ， 则 ) ( ) , ( 3 2 1 c a ，若 ) , ( c a ) ( 3 1 同理可得， 因此有 ) ( ) ( 3 1 2 1 ) ( 3 2 1 。则 ) ( 3 2 1 = ) ( ) ( 3 1 2 1 。 （2） ) ( ) ( ) ( 3 1 2 1 3 2 1 证明： 设 ) ( ) , ( 3 2 1 c a ， 则存在 2 A b ， 使得， 1 ) , ( b a ， 3 2 ) , ( c b ， 则 2 ) , ( c b ，且 3 ) , ( c b ，所以 2 1 ) , ( c a ，且 3 1 ) , ( c a ，即 ) ( ) ( ) , ( 3 1 2 1 c a ，所以 ) ( ) ( ) ( 3 1 2 1 3 2 1 。 13、给定 n i j I j i j i , 1 , , | ) , ( = = 是什么？ 答： , 3 , 2 , 1 , 0 , 1 , 2 , 3 , = I ， ), 4 , 3 ( ), 3 , 2 ( ), 2 , 1 ( ), 1 , 0 ( ), 0 , 1 ( ), 1 , 2 ( , = ), 5 , 3 ( ), 4 , 2 ( ), 3 , 1 ( ), 2 , 0 ( ), 0 , 2 ( ), 1 , 3 ( , 2 = ，则 , , | ) , ( n i j I j i j i n = = 14、对第 9 题中的关系，构造关系矩阵 （1） 1 M （2） 1 M 解： ) 1 , 2 ( ), 0 , 0 ( ), 3 , 2 ( ), 2 , 1 ( ), 1 , 0 ( 1 = ) 1 , 3 ( ), 0 , 2 ( 2 = 1 1100 0010 0101 0000 M = 2 0000 0000 1000 0100 M = 17 (3) 1 2 M 解： ) 1 , 3 ( ), 0 , 2 ( ), 1 , 2 ( 1 2 = 15、 设 A 是有 n 个元素的有限集， 是 A 上的关系， 试证明必存在两个正整数 t k, ， 使得 t k = 。 证明： 因为 是 A 上的关系， 所以对于任意正整数 r ， r 也是 A 上的关系， 另 一 方面， 因为 n A = ) ( # ，所 以 2 ) ( # n A A = ， 2 2 2 ) 2 ( # ) ( # n A A A A = = ，也 即 A 上只有 2 2 n 个不同的关 系，因此在 关系 1 2 2 3 2 2 2 , , , , , + n n 中必有 两个是相同 的，也 即存在两个正整数 t k, ，使得 t k = ，其中 1 2 1 2 + ，则在 A 中必存在 1 k 个元素 1 2 1 , , , k i i i a a a ，使得： b a a a a a k i i i i 1 2 1 1 , , , 因为 n k > ，所以在 b a a a a k i i i , , , , , 1 2 1 这 1 + k 个元素中必有两个元素 t r i i a a = （ k t r < 0 ，记 a 为 0 i a ，记b 为 k i a ） ，因此下述关系 b a a a a a a a k t r r r i i i i i i 1 1 1 1 , , , , , + 成立，这表明 b a k ， k k r t k k 1 ，用类似的方法又可找到 1 2 k k 时，有 2 1 n n ； 答： 非自反的， 因为 1 1 不成立， 但 N 1 。 对 称的， 非可传递的， 因为 10 1 ， 2 10 ， 但是 2 1 不成立。 （3）当且仅当 ) , ( | | 2 1 2 1 R r r r r 时，有 2 1 r r 。 答：自反的，非对称的，非可传递的，因为 ) 8 ( 5 ， 1 8 ，但是 1 5 不成立。 23 + = 1 n i i = 1 n i i = 1 i i = 19 21 、 设 1 和 2 是集合 A 上的任意两个关系，判断下列命题是否正确，并说明理 由： （1）若 1 和 2 是自反的，则 2 1 也是自反的； 答： 正确。 因 为 1 和 2 是自反的， 因此对任意 A a ，有 a a a a 2 1 , ，因 此 a a 2 1 ， 所以 2 1 也是自反的。 （2）若 1 和 2 是非自反的，则 2 1 也是非自反的； 答： 错误； 例如 , , c b a A = ， ) , ( ), , ( ), , ( 1 a c b b a a = ， ) , ( ), , ( ), , ( 2 c a b b a a = ， 1 和 2 都是非自反的，但是 ) , ( ), , ( ), , ( 2 1 c c b b a a = 是自反的。 （3）若 1 和 2 是对称的，则 2 1 也是对称的； 答： 错误， 设 , , c b a A = ， ) , ( ), , ( 1 a b b a = ， ) , ( ), , ( 2 a c c a = ，显 然 1 和 2 是对称的，但是 ) , ( 2 1 c b = 是非对称的。 （4）若 1 和 2 是反对称的，则 2 1 也是反对称的； 答： 错误， 设 , , c b a A = ， ) , ( ), , ( 1 c c b a = ， ) , ( ), , ( 2 a c c b = ，显 然 1 和 2 是 反对称的，但是 ) , ( ), , ( 2 1 a c c a = 不是对称的。 （5）若 1 和 2 是可传递的，则 2 1 也是可传递的； 答： 错误， 设 , , c b a A = ， ) , ( ), , ( ), , ( 1 c a c b b a = ， ) , ( ), , ( ), , ( 2 a b a c c b = ，显 然 1 2 是可传递的，但是 ) , ( ), , ( ), , ( 2 1 a b a a c a = 却是不可传递的。 22、证明若 是对称的，则对任何整数 1 k ， k 也是对称的。 证明： 数学归纳法， 当 2 = k 时 ，若 2 ) , ( b a ， 则根据复合关系的定义， 存在元 素 c ，使 得 ) , ( , ) , ( b c c a ，因 为 是对称的， 所以 ) , ( , ) , ( c b a c ，所 以 2 ) , ( a b ，因此 2 是对称的，假设当 k n = 时成立，则当 1 + = k n 时，若 1 ) , ( + k b a ， 则存在元素 1 c ，使 得 ) , ( , ) , ( 1 1 b c c a k ，因 为 和 k 是对称的， 因此 ) , ( , ) , ( 1 1 c b a c k ，所以 1 ) , ( + k a b ，因此： 1 + = k n 时成立，即得证。 23 、 已知 1 ,2 ,3 ,4 A = 和定义在 A 上的关系 (1, 2),(4,3),(2, 2),(2,1),(3,1) = ，试 证明 不是可传递的。求出一个关系 1 ，使得 1 是可传递的，你能求出另 一个关系 2 也是可传递的嘛？ 答：证明： 显然不是可传递的，因为 (1, 2) ， (2,1) ，但是 (1,1) 。 1 (1, 2),(4,3),(2, 2),(2,1),(3,1),(1,1),(4,1),(4, 2) = ，能找出另一个关系。 1 (1, 2),(4,3),(2, 2),(2,1),(3,1),(1,1),(4,1),(4, 2),(3,3) = 。 20 24、 图 2-10 表示在1, 2, 3 上的 12 个关系的关系图。 试对每一个这样的图， 确定 其表示的关系是自反的还是非自反的； 是对称， 非对称还是反对称； 是可传递的 还是不可传递的？ 答： 自反的、非对称的、非反对称的，非可传递的 自反的、对称的，非反对称的、可传递的 非自反的、非对称的、反对称的、可传递的 21 自反的、非对称的、反对称的、可传递的 25、图 2-11 给出了1, 2, 3 上的两个关系的关系图，这些关系是等价的吗？ 答： (a) (b) 答 ：图 (a) 表 示的关系 (1,1),(2, 2),(3,3),(1, 2),(2,1),(1,3),(3,1) = 具有自反性， 对称 性， 但是不具有传递性， 因为有 (2,1), (1, 3) ，但 是 (2,3) ， 因此不是等价关 系。 图(b) 表示 的关系 (1,1),(2, 2),(3,3),(1, 2),(2,1) = ， 具有自反性， 对称性， 传递性， 因此是等价关系。 26 、 在 N 上的关系 定义为当且仅当 / ij nn 可以用形式 2 m 表示时，有 ij nn ，这 里 m 是任意整数： (1) 证明 是等价关系 证明：对 nN ， 0 / 12 nn = = ，因此 nn ，所以关系 具有自反性。 对 , ij N ，若 ij ， 即存在 m ，使 得 /2 m ij = ，则 有 /2 m ji = ， 因此有 ji 。 所以关系 具有对称性。 对 , i jk N ，若 ij ，且 jk ，即 存 在 12 , mm ，使 得 1 /2 m ij = ， 2 /2 m jk = ， 则 12 /2 mm ik + = ，因此有ik ，所以关系 具有传递性。 综上可得关系 是等价关系。 (2) 找出 的所有等价类 答： 1 ,3 ,5 , ,2 1 N k = + 27 、 有人 说 ，集合 A 上的 关系 ，如果 是对称的 且 可传递的 ， 则它也是 自 反的 ， 1 1, 2, 4,8,16, 2 , 0,1, 2,3, 4, 3 3, 6,12, 24, 3 2 , 0,1, 2,3, 4, 5 5,10, 20, 40, 5 2 , 0,1, 2,3, 4, k k k k k k = = = = = = = 22 其理由是，从 ij aa ，由对称性得 ji aa ，再由可传递性便得 ii aa 。 答：这种说法是错误的。例如， 1, 2, 3 A = ， (1, 2),(2,1),(1,1) = ，显然 是对 称的，且 是可传递的，但是它不是自反的。 28、 设有集合 A 和 A 上的关系 ， 对于所有的 , i jk aa a A ，若 由 ij aa 和 jk aa 可 推得 ki aa ，则称 关系 是循环 的，试证 明 当且仅当 是等 价 关 系时， 是自 反 且循环的。 证明：先证充分性 若 是等价关系， 则 是自反的， 对称的， 可传递的。 对于所有的 , i jk aa a A ， 若 ij aa 且 jk aa ，则 ik aa ，由对称性则有 ki aa ，因此关系 是循环的。 再证必要性 若对于所有的 , i jk aa a A ，若有 ij aa ，又由自反性，有 jj aa ，则由 是循环 的，可得 ji aa 成立，即 具有对称性。 若对于所有的 , i jk aa a A ，若 由 ij aa 和 jk aa ，由 是循环的有 ki aa ， 由对称 性可得 ik aa ，因此 具有可传递性。 又由 是自反的，则 是等价的。 29、 设 1 和 2 是 A 上的等价关系， 试证明： 当且仅当 1 A 中的每一等价类都包含 于 2 A 的某一等价类中时，有 12 。 证明：先证充分性 设 1 A 中的每一个等价类都包含于 2 A 的某一个等价类中， 对任一 1 (, ) ij aa ，有 1 ij aa ，因此 11 , ii ji aaa a 。又由假设必有某元素bA 存在，使得 12 i ab ，因此有 2 i ab ， 2 j ab ，所以 2 (, ) ij aa ，故有 12 。 再证必要性： 设 12 ，并设 1 i a 是 1 A 中任一等价类，对任一 1 i xa ，有 1 i ax ，即 1 ( ,) i ax ，由假设 2 ( ,) i ax ，即 2 i xa ，故有 12 ii aa 。 30、 已知 1 和 2 是集合 A 上分别有秩 1 r 和 2 r 的等价关系， 试证明 2 1 也是 A 上的等价关系，它的秩最多为 2 1 r r ，再证明 2 1 不一定是 A 上的等价关系。 证明：由交集的定义 12 1 2 (,) | (,) (,) ab ab ab = 且 对于 aA ，因为 12 , 都是自反的，所以 1 (,) aa ，且 2 (,) aa ，因为 12 (,) aa ，所以 12 是自反的。 对于 , ab A ，若 12 (,) ab ，则 1 (,) ab ， 2 (,) ab ，由 1 和 2 的对称 性知 1 (, ) ba ，且 2 (, ) ba ，因而有 12 (, ) ba ，故 12 是对称的。 23 对于 , abc A ，若 12 (,) ab ， 12 (,) bc ，则 有 1 (,) ab ， 1 (,) bc ， 2 (,) ab ， 2 (,) bc ，由 12 , 的传递性知 1 (,) ac ， 2 (,) ac ，因而 12 (,) ac ，故 12 是可传递的。所以 2 1 也是 A 上的等价关系。 对于 12 ，由并集的定义知 12 1 2 (,) | (,) (,) ab ab ab