《离散数学》课后习题解答--第4章.doc

第4章 习题解答 PAGE  PAGE 22 习题 4.1 1.设A=ía,by，列出A上的所有二元关系。 解：A×A=ía,a,a,b,b,a,b,by A上的二元关系有2|A×A|=2|A||A|=22×2=24=16。其中： ①空集1个? ②含有1个元素的子集4个：ía,ay，ía,by，íb,ay，íb,by。 ③含有2个元素的子集==6个：ía,a,a,by，ía,a,b,ay，ía,a,b,by， ía,b,b,ay，ía,b,b,by，íb,a,b,by ④含有3个元素的子集==4个：ía,a,a,b,b,ay，ía,a,a,b,b,by，ía,a,b,a,b,by，ía,b,b,a,b,by ⑤含有4个元素的子集1个：ía,a,a,b,b,a,b,by 2.设A和B是有限集???A到B的二元关系有多少种？ 解：A到B的二元关系有|P(A×B)|=2|A||B|种。 3.用列举法表示A到B的二元关系R，写出关系矩阵，画出关系图。 ⑴ A=í1,2,3,4,5y，B=ía,b,cy，R=í?1,a?,?1,b?,?2,b?,?3,a?y ⑵ A=ía,b,cy，B=í1,2,3,4,5y，R=í?a,2?,?c,4?,?c,5?y ⑶ A=í0,1,2y，B=í0,2,4y，R=í?a,b?| a?A∧b?B∧a×b?A∩By，其中×是普通乘法。 ⑷ A=í1,2,3,4,5y，B=í1,2,3y，R=í?a,b?| a?A∧b?B∧a=b2y ⑸ A=P(í0,1y)，B= P(í0,1,2y)－P(í0y)，R=ía,b| a?A∧b?B∧a-b＝?y 解：⑴ MR= R关系图如图4.20所示。 ⑵ MR= R关系图如图4.21所示。 ⑶ MR= R关系图如图4.22所示。 ⑷ MR= R关系图如图4.23所示。 ⑸ A=P(í0,1y)=í??í0y,í1y,í0,1yy B=P(í0,1,2y)－P(í0y) =í??í0y,í1y,í2y,í0,1y,í0,2y,í1,2y,í0,1,2yy－í??í0yy =íí1y,í2y,í0,1y,í0,2y,í1,2y,í0,1,2yy MR= R关系图如图4.24所示。 4.写出A上二元关系R的关系矩阵，画出关系图。 ⑴ A=í0,1,2,3y， R=í?0,0?,?0,3?,?2,0?,?2,1?,?2,3?,?3,2?y ⑵ A=í1,2,4,6y，R=í?a,b?| a?A∧b?A∧b为素数y ⑶ A=í0,1,2,3,4y，R=í?a,b?| a?A∧b?A∧a为奇数∧b≤3y ⑷ A=í0,1,2,3,4y，R=í?a,b?| a?A∧b?A∧0≤a－b＜3y ⑸ A=í2,3,4,5,6y，R=í?a,b?| a?A∧b?A∧a和b是互质的y 解：⑴ MR= R关系图如图4.25所示。 ⑵ MR= R关系图如图4.26所示。 ⑶ MR= R关系图如图4.27所示。 ⑷ MR= R关系图如图4.28所示。 ⑸ MR= R关系图如图4.29所示。 5.设A=í0,1,2,3,4,5,6y，A上二元关系R=í?a,b?| a?A∧b?A∧(a＜b∨b为素数)y，写出R的关系矩阵。 解：MR= 习题 4.2 1.A=í1,2,3,4y，A上二元关系R和S分别为： R=í1,2,2,4,3,3y S=í1,3 ,2,4,4,2y ⑴ 求 R∩S，R∪S，R-S，~R，~S，RS ⑵ 求dom R，ran R，FLD R，dom S，ran S，FLD S ⑶ 求dom ~R，ran ~R，FLD ~R ⑷ 求dom RS，ran RS，FLD RS ⑸ 求RC，SC，(R∩S)C，验证(R∩S)C=RC∩SC 解：⑴R∩S=í2,4y R∪S =í1,2,1,3,2,4,3,3,4,2y R-S =í1,2,3,3y ~R=í1,1,1,3,1,4,2,1,2,2,2,3,3,1,3,2,3,4,4,1,4,2,4,3,4,4y ~S=í1,1,1,2,1,4,2,1,2,2,2,3,3,1,3,2,3,3,3,4,4,1,4,3,4,4y RS =í1,2,1,3,3,3,4,2y ⑵ dom R =í1,2,3y ran R =í2,3,4y FLD R =í1,2,3,4y dom S =í1,2,4y ran S =í2,3,4y FLD S =í1,2,3,4y ⑶ dom ~R =í1,2,3,4y ran ~R=í1,2,3,4y FLD ~R =í1,2,3,4y ⑷ dom RS =í1,3,4y ran RS =í2,3y FLD RS =í1,2,3,4y ⑸ RC=í2,1,3,3,4,2y SC