第三章习题二第三章习题二 1 、 已 知A=, ， 求AP(A) ， 如 果 不 好 理 解 ， 可 以 换 成 A=a,b,P(A)= ,a,b,a,b。 解：P(A)=A00,A01,A10,A11=, AP(A)=, , =, , 如果不好理解，可以换成 A=a,b,P(A)= ,a,b,a,b AP(A)=a,b ,a,b,a,b =, 再将 a 换成，b 换成则以结果为 AP(A)= , , , , , , , 2、设 A=1,2,4,6，列出下列关系所包含的序偶，并判断关系所属的类型(自反、反自 反、对称、反对称、传递)。 (1)R=|x,yAx+y2 (2) R=|x,yAx/yA (1)R=|x,yAx+y2 解 R=, , , (2)R=|x,yAx/yA 解 R=, 3、设 A=0,1,2,3 R 是 A 上的关系，且 R=,，给 出 R 的关系矩阵和关系图，并判断关系所属的类型(自反、反自反、对称、反对称、传递)。 解： 0123 01001 10000 21101 30100 A 上的关系可以只用一排结点来表示 0 11 d 3 4、给定 A=1,2,3,4，A 上的关系 R=,，试画出 R 的关 系图、关系矩阵，并判断关系所属的类型(自反、反自反、对称、反对称、传递)。 解： 1 234 不是自反的，是反自反的（因为没有任何结点有自旋） 不是对称的，是反对称的（因为都只有单有向边） 1 可到 3，3 可到 4，1 可传递到 4，确实 1-4 直达边 2 可到 3，3 可到 3，2 可传递到 4，确实 2-4 直达边。因此是可的传递 或者 RR=, =, R，所以它是可传递的。 5 、 A=a,b,c,d ， R1,R2为 A 上 的 关 系 ， 其 中 R1=, ， R2=,，求R1R2,R2R1,R12,R23，要求直接利用序偶即定义进行复后， 基于关系进行复合。 解：R1R2=,=, R2R1=,= R1R1=,=, R2R2=,=, R22R2=,=, 也可用矩阵运算 = = = = = 0000 0010 1100 0000 0000 0010 1100 1000 0000 1100 0010 0000 0000 1100 0010 0000 0000 0010 1100 1000 0000 0010 1100 1000 0000 0000 0000 1011 0000 0000 1000 0011 0000 0000 1000 0011 0000 1000 0000 0000 0000 0000 1000 0011 0000 0010 1100 1000 0000 0000 0000 1100 0000 0010 1100 1000 0000 0000 1000 0011 6、 R 的关系图如图 3.47， 写出 R 的关系矩阵与所包含的序偶、 利用关系图求出 r(R),s(R)， 利用关系图、关系矩阵及 WarShall 算法求 t(R)。 a b c de a b c de a b c de a b c de R=, RR=, =, R2R=, = R3R=,没有新增的序偶 7、设 A=1,2,3,4,5,6，R 为 A 上的关系，R 的关系图如图 3.48。 (1)利用关系矩阵求R2,R3表达式。 (2)利用关系矩阵求 t(R),s(R),r(R)的集合表达式。 1 2 3 4 5 6 图 3.48 R=, R2=,=, R2R=,=, = = 000000 000000 000000 010101 000000 000000 000000 000000 010000 000101 010000 010000 000000 000000 000000 010101 000000 000000 000000 000000 000000 010101 000000 000000 000000 000000 010000 000101 010000 010000 000000 000000 010000 000101 010000 010000 o o r(R)=,I =, s(R)= , =, t(R)=RR2R3=, =, 1 2 3 4 5 6 8、设A=a,b,c,d，A上的等价关系R=,IA，画出R的关系图， 并求出A中各元素的等价类。 解： b b1 d 1 d aR=a,b, cR=c,d 9、设 A=1,2,3,4，在 A A 上定义二元关系 R：,Ru+y=v+x 证明 R 是 A A 上的等价关系，确定由 R 引起的对 A A 的划分。 证明： (1.1)R 是自反关系：任取元素A A，由于 u+v=v+u 则,R (1.2)R 是对称关系：,Ru+y=v+xx+v=y+u,R (1.3)R 是可传递关系： ,R, ,R u+y=v+x (1) x+s=y+r (2) 在(1)式两边各加 s 得到(3)式，在(2)式两边各加 v 得到(4)式。 u+s+y=v+x+s (3) x+s+v=y+r+v (4) 则 u+s+y= y+r+v，故 u+s=r+v，故,R AA=1,2,3,41,2,3,4=,=16 个元素，其可能的组合有 256 个。 ,Ru+y=v+xu-v=x-y第一个序偶的差=第二个序偶差，因此 R= 第一个序偶的差=第二个序偶差=0 第一个序偶的差=第二个序偶差=1 第一个序偶的差=第二个序偶差=2 第一个序偶的差=第二个序偶差=3 第一个序偶的差=第二个序偶差=-1 第一个序偶的差=第二个序偶差=-2 第一个序偶的差=第二个序偶差=-3 第一个序偶的差=第二个序偶差=0：, 第一个序偶的差=第二个序偶差=-1:, 第一个序偶的差=第二个序偶差=-2:, 第一个序偶的差=第二个序偶差=-3: 第一个序偶的差=第二个序偶差=1:, 第一个序偶的差=第二个序偶差=2:, 第一个序偶的差=第二个序偶差=3: 10、对于下列集合与整除关系，画出哈斯图。 (1) 1,2,3,4,6,8,12,24 (2)1,2,3,4,5,6,7,8,9,10,11,12 解： 1 可以整除所有的数，1 与所有的整数都有关系，1 在所有的元素的左边，1 是最小元。 1 2 3 4 6 8 12 24 1 235711 46 8 910 12 11、针对图 3.49、图 3.50 二个哈斯图，分别写出其偏序关系。 1 2 3 4 5 1 2 3 4 5 图 3.49 图 3.50 哈斯图去掉了自旋，去掉可传递的直达边、方向为向上，因此重构关系时，需要加上自旋对 应的相等序偶，加上传递所得到的序偶，第一个元素在左边。 (a) 集合=1,2,3,4,5 关系 R=, , , (b) 集合=a,b,c,d,e,f 关系 R=, (c) 集合=1,2,3,4,5 关 系R=,