形式语言与自动机理论-蒋宗礼-第一章参考答案.docx

第一章参考答案1.1请用列举法给出下列集合。(吴贤瑁 02282047) 你知道的各种颜色。解：红，橙，黄，绿，青，蓝，紫大学教师中的各种职称。解：助教，讲师，副教授，教授你所学过的课程。解：语文，数学，英语，物理，化学，生物，历史，地理，政治(4)你的家庭成员。解：父亲，母亲，妹妹，我你知道的所有交通工具。解：汽车，火车，飞机，轮船，马车(6)字母表a, b上长度小于4的串的集合。解：a,b,aa,bb,ab,ba,aaa,aab,aba,abb,baa,bab,bba,bbb(7)集合1,234的募集。解：中,1,2,3,4,1,2,1,3,1,4,2,3,2,4,3,4,1,2,3,1,2,4,1,3,4,2,3,4,123,4 (8)所有的非负奇数。解：135,7,(9) 0100的所有正整数。解：1,2,3,100(10) 110之间的和为10的整数集合的集合。解：设所求的集合为A,集合A中的元素为Ai (仁1,2,3,)，Ai也是集合，A中的元素在1 10之间，并且和为10。根据集合元素的彼此可区分性，可以计算出Ai中元素的最多个数，方 法是：把1开始的正整数逐个相加，直到等于10 (即10=1+2+3+4),这样，A中最多有4个元 素。原因是：从最小的1开始，每次加入新的元素都只依次增加1,这样相加的和最小，要加 到10,元素个数就最多。求出最大的I Ai I =4后，再求出元素个数为3, 2, 1的集合就可以了。故人=1。,1,9,2,8,3,7,4,6,127,1,3,6,1,4,5,2,3,5,123,41.2 请用命题法给出下列集合1.3 给出下列集合的幕集.(02282075冯蕊)(1)(2) 中，(4) £ Q00091解答："(3) ,中,中，中(4) , £ ,0,00, £ ,0, £ ,00,0,00, *0,00(5) 中,0,1,0,114列出集合0, 1, 2, 3, 4中(褚颖娜02282072)(1) 所有基数为3的子集0, 1, 2, 0, 1, 3, 0, 1, 4, 0, 2, 3, , 0, 2, 4, .1, 2, 3, 1, 2, 4,(2)如果对于任给的x,y £ Z* ,如果xRLy,故对于Vz e Z*，xze L与yzL同时成立或同时不成立，对于X/p e Z*，如果xzp£ L,因为zpw Z*，又因为xRly故yzpeL,同理,可以证明如果xzpe "因为zp£ Z*，又因为xRl、故yzpeL,因此，对于X/p £ Z*，xzp£ L 与yzpeL同时成立或同时不成立，故如果对于任给的x,y e Z*，如果xRLy,则必有xzRi,yz。综上，该关系的等价性和右不变性均得以证明。1.17设0*上的语言1=便卜|叫11120,请给出0,1*关于L所确定的等价关系Rl的 等价类.设L是2上的一个语言,2 *上的二元关系Rl定义为:对任给的x,ye S *，如果对于X/ze S*，均有xzeL与yzeL同时成立或者同时不成立，则xRij.根据上述定义可知，0*关于L所确定的等价关系Rl的等价类有三个.(1) Vx,y£Onlm|no,m0,都有Vz£2*，均有 xzeL与yzeL同时成立或者同时不成(只有当ze Pln'O的时候，才同时成立，否则不成立)(2)立,丫£0。严|口20,111=0,都有72£2*，均有xzgL与yzeL同时成立或者同时不成(只有当zeUimgm。的时候，才同时成立，否则不成立)(3) Vx,ye0nim|n,m0,都有Vzw X*，均有xzeL与yzeL同时成立或者同时不成立 (无论z取何值，都不同时成立)三个等价类为Onim|nO,m>O()nim|no,m=O和除此之外的0,1*上的字符1.18 RL确定的0, 1*的等价分类为：10 = xl0y | x, y G 0, 1* U ln|nl0=0丁 I mn=0二OT | n101 = Omln|ni-n=l2 = 0mln|ni-n=2h = Omrim-n=h其中，n, m均为非负整数。（02282072 褚颖娜）L19 .给出下列对象的递归定义1 . n个二元关系的合成(1) RiR2=(a,c)|3(a,b)e R】且玉b,c) e R2(2) R1R2Rn = (d,g)|3(d,e)eRiR2Rn-i 且士f,g) e Rn 2 .无向图中路的长度在无向图G中，若两顶点V1,V2之间存在一条无向边，则V1,V2是G的一条长位1的路若V1,V2Vn.l为一条长度为k-1的路，且Vn-l,Vn存在一条无向边，则Vi，V?.Vn-l,Vn为G的一 条长度为k的路3 .有向图中路的长度在有向图G中，若两顶点Vi,V2之间存在一条有向边，则V1,V2是G的一条长位1的路若V1,V2Vn.l为一条长度为k-1的路,且Vn-l,Vn存在一条有向边，则V" V2Vn-l,Vn为G的一 条长度为k的路4 . n个集合的乘积SixS2=(a,b)|ae SiMbe S2Six S2Sn=(d,e)|dG Six S2Sn.i 且 ew S” 5 .字母a的n次幕(1) a0=l;(2) an=an-1a;6 .字符串x的倒序若X为单字符，则X的倒序是它本身若X的倒序为y,若X后跟一字符a,则xa的倒序为ay;7 .字符串x的长度若x为空串j贝i|x|二。；若字符串x的长度为k,其xa或ax的长度为k+18 .自然数。为自然数，如果x为自然数，则x+1为自然数L20 .使用归纳法证明下列各题。(吴玉涵02282091)1. 21下列集合中哪些是字母表。(2) a,b,c,.,zo(3) a,b,a,co(4) 0, 1, 2, 3,n,.0(5) a,d,f n a,b,c,.,zo解答：字母表为(1) (2) (6)(3)不满足字母表的非空性，(4)不满足字母表的可区分性，(5)是无穷集合不满足字母表的有穷性。22.设工=匕，b,求字符串aaaaabbbba的所有前缀的集合，后缀的集合，真前缀的集合，真后Z的集合。(吴贤瑞02282047)解：前缀：e,a,aa, aaa, aaaa, aaaaa, aaaaab, aaaaabb, aaaaabbb, aaaaabbbb, aaaaabbbba)(2)后缀： e , a, ba, bba, bbba, bbbba, abbbba, aabbbba, aaabbbba, aaaabbbba, aaaaabbbba (3) 真前缀： e , a, aa, aaa, aaaa, aaaaa, aaaaab, aaaaabb, aaaaabbb, aaaaabbbb(4) 真后缀： e , a, ba, bba, bbba, bbbba, abbbba, aabbbba, aaabbbba, aaaabbbba)23. E=aa,ab9bb,ba),求字符串aaaaabbbba的所有前缀的集合、后缀的集合、真前（02282015 郭会）缀的集合、真后缀的集合。解:由前缀、后缀、真前缀、真后缀的集合可以有：其前缀集合为： £ ,aa,aaaa,aaaaab,aaaaabbb,aaaaabbbba 其真前缀集合为： £ ,aa,aaaa,aaaaab,aaaaabbb其后缀集合为： £ ,ba,bbba,abbbba, aaabbbba, aaaaabbbba ) 其真后缀集合为： £ ,ba,bbba,abbbba, aaabbbba1.25抽象技术为什么对计算机技术特别重要？(段季芬)对于计算机技术方面的人来说，计算思维能力是必需的，这是学科本身决定的。计算机科学与技术学科所要解决的根本问题是什么能被有效的自动化。现代计算机技术认为，要想有效的实现自动化，必须经过抽象进行形式化。1. 26为什么要求字母表示非空有穷集？(唐明珠02282084)解答：字母表是非空有穷集合，由字母表中的元素连接而成的字符串叫做字母表上的句子。假设字母表为空集，则字母表中唯一的元素就是而e不论如何组合，其组成的句子都为空，其研究就失去了意义，所以字母表要具有非空性。1.27 .考虑一下，为什么要研究句子的前缀，后缀？解：形式语言是研究自然语言和人工语言的数学工具，只研究组成规则，不研究语义。而我们将语 言看做句子的集合，句子看做字母按照一定规则组成的字符串,故主要根据规则的形式区分语言类，大 部分问题都可转化为判定某个句子是否属于某个语言的问题.而这就要求从一个句子的结构出发，而 一个整体的句子在结构上将其划成几个部分，对于我们的研究会有很大的帮助.事实上研究句子的前 缀，后缀，也就是为了将句子结构进行有意识的划分而更加方便的研究句子，看其是否符合某个形式语 言的组成规则.1.28 工=1, 0,下列语言在结构上有什么样的特点？(吴贤培02282047)L =0nln I nlo解：该语言的每一个句子由二部分构成，这二部分的组成依次为：0、1。其中，每部分的0 或1的个数相等，且都不小于1个。(2)乙2=0“/ I解：该语言的每一个句子由二部分构成，这二部分的组成依次为：0、1。其中，每部分的0 或1的个数不一定相等，但都不小于1个。(3)£3=OnlnOn| nlo解：该语言的每一个句子由三部分构成，这三部分的组成依次为：0、1、0o其中，每部分的 0或1的个数相等，且都不小于1个。(4)£4 = 0nlm0k| n, m,kl。解：该语言的每一个句子由三部分构成，这三部分的组成依次为：0、1、0o其中，每部分的 0或1的个数不一定相等，但都不小于1个。L5=°'T°n I nNO。解：该语言的每一个句子由三部分构成，这三部分的组成依次为：0、1、0o其中，每部分的 0或1的个数相等，并且可以都为0。上6 =X3XT | X,。解：该语言的每一个句子从前向后看和从后向前看时，有一部分是对称相等的。而且，这对称 相等的两个串中间一定有另外一个串。乙=x x% I X, 3 £ k 。解：该语言的特点是在其句子中一定可以找到这样的一个串：该串是从句子的第一个字符开始 的连续的串，且紧跟该串之后的连续一段字符串恰好是该串从后往前看是的那个串，而且 这样的两个串之后一定还有另外一个字符串。£8=a3a |, 冲金 27解：该语言的每一个句子有这样的特点：该句子的第一个字符和最后一个字符都是0或都是b 且该句子的长度不小于3o乙=£，° J I 01，2。解：该语言的句子是所有由0和1构成的串，包括空串oo）£10 = o, 1,00,01, 10, 11,000,-o解：该语言的句子是所有由0和1构成的串，不包括空串£。L29 设 LL L2, L3, L4 分别是 21, 2 2, 2 3, 2 4 上的语言,能否说 LL L2, L3, L4 都是某个字母表2上的语言？如果能，请问这个字母表2是怎么样的？（刘钮 02282083）答：能 S = S1U S2U S3U S41.30 设右，小右人分别是X，£，工，£ 上的语言，证明下面的等式成立。（1）设 X/a £ LiUZ' = a £L或a e L2a e4或 £ 4=> /a £故原式得证（2）l1（J（l2|Jl3）=（l1Ul2）U4设 Va £ Lj|J（L2|jL3） na £ La e La e L3 V6z e Lj|J（L2|jL3）故，原式得证* 比*如果 L =（D，W ） =<!> = £如果L1 w，彳取设L = 6,a?力之1,贝ij L；= £.aa2.an.axax.axa2.axan.,而（4 ）个=£,ax.a2.an.aax.axa2.axan.故.；)*=£/，原式得证(4) (LJ)+=LJ如果右二O),(Lj)+ =中=上/如果L。，假设£ = %,g,21,则 LJ = ax,a2.an.axax.axa2.jaxan.,而(£)+ = ax.a2.故(Lj )+二£/,原式得证(5) (LjL2)L3=)“3)(LjL2)L3 = xy | x ee L2£3= xyz | % e Lj,e L2, z e L3=x x Lxyz y g L2,z g L3 = L (L2L3)故，原式得证(6)乙(乙2U 乙3)=乙1乙2U 乙1乙3故,原式得L1(L2|jL3) = x|xeL1y | ye % 或 > e L3 = xy x e Ly e = xyxe Ly e L2Jxyxe L,y e L3 =故，原式得证(7) (L2|jL1)*=(L2*L1*)*设Va £ (力2|<>|4)"，假设1 =玉12%，贝12/2，“7贝1£乙2或占 £乙 ，当k=l,2,n* * * * *又因为e e L2, £ e L、=> L L L2 , L2 c L L2故 x* e Lx L2，因此 q = x/2苟 e L L2 => (£2JLj) c (£2Lx )同理可证(4Ij4)*卫综上 gUl)* = &£*)*故，原式得证wU)*=1当£之L时，原式显然成立 当£2七1时,设卜=冗I，/因为 = X n (jLUe)* = s.X,X2.XhY= £：, Xj, x2 .xn,%1%!，XjX2.所以WU£)*=4 故，原式得证(10)* =£因为，中°二仿所以，* =<D°|J'kJ之二故，原式得证(11)wu<UjU")*= wZZZ*)*设Da eeULiUAU4)，假设片2/七，则%I2，-2UU3U4则乙£ 乙或乙 £乙，或%£ 右，曲女 £乙，因此4 £七'的女 £垢a £ L：，当* * * *k=l,2,.n、£ e L)£ 6 L »£ 6 L3,26 Lq L)L3 L，, L? C L L L3 L4力.& * * «L* 七止 * 土 >>L3 c Zq L? L3 L4 , L，= Zq L2 L3 L4故£厂以工工*，因此a = xlx2.jcn e L：L；L；L； => wUMIJ/UA)*工 WZZD同理可证 wUU4U4)* 卫 wZZL")*综上(入口乙1>141>14)*=(乙"2*4工*)* 故，原式得证/、 z -r * -r *、*/v *y*、*(12) (L L2 ) = (L2 L)由8小题结论可以推得故，原式得证1.31 设 LL L2, L3, L4 分别是 1, 2, 3, 4 上的语言，证明下列等式成立否(段季芬)(1) (L1L2) *= (L2L1) *不成立例如: Ll=a, L2=b,则(L1L2) *=(ab) *=, ab,abab,ababab,.而(L2L1 ) *= ( ba )*= C,ba.baba,bababa,显然不等。(2) L1+=L1+L1 +不成立例如: Ll=0,那么 L1+=L1UL12UL13U。=0, 00, 000,ooo 而 Ll+Ll+=00, 000, 0000, ooo ), 比L1+少基本项LI可得知L1+L1+是L1+的子集(3) L1*=L1*L1*正确因 为 L1*L1*= ( L1°UL1UL12UL13U。) (Ll°ULlULl2ULl3Uooo)=(L10UL1UL12UL13U ooo) L1°U(Ll°ULlULl2ULl3Uooo) LlUoooo=(Ll°ULlULl2ULl3Uooo) UAUBUoooo从观察可知 A (Ll°ULlULl2ULl3Uo o o) 的真子集，B是A的真子集，推知后面一项是前面的一项的真子集，根 据吸收规则所以原式二LIOULIULFULU。=L1*(1) (L1UL2) *=L2*UL1*不正确例如： Ll=a ,L2=b,左边= a,b*= ,a,b,aa,ab,bb,.右 边 =,b,bb,bbb, .U C,a,aa,aaa, .= C,a,b,aa,bb,aaa,bbb, 没有a*b*项肯定不等(2) (L1L2UL1) *L1=LI (L2L1UL1) *正确(3) L2 (L1L2UL2) *L1=L1L1*L2 (L1LPL2) *不正确假设 Ll = a, L2=b, L2 (L1L2UL2) *L1 表示的 语言肯定以b打头，而L1L1*L2 (L1LPL2) * 表示的语言肯定以a开头(4) (L1 + ) *= (LI*) +=L1* 正确(L1+ ) *= ( L1UL12UL13U o o o ) *=£ ,(L1UL12UL13U o o o ) , ( LIUL-UL-U )2, (LlULl2ULl3Uooo) 3ooo 由于(LIULyUL-U。)11是(L1UL12UL13U。) 的子集(li+)*表示的语言就是 e, (LlULl2ULl3Uooo) 表示的语言即L1*,所以 (L1+) *=L1*(L1* )+=(L1°L1UL12UL13U o o o )+= (Ll°LlULl2ULl3Uooo), (Ll°LlULl2ULl3Uooo)2, (Ll°LlULl2ULl3Uooo) 3,OOO )由 于 (LlOULlULPULU o o o ) n 是 (Ll°ULlULl2ULl3Uooo) m的子集(LI*) + 表示的语言就是(L1()UL1UL12UL13U。) 表示的语言即LI*,所以(LI*) +=L1*所以(L1 + ) *= (LI*) +=L1*(5) L1*L1+=L1+L1*=L1 + 正确L1*L1+ = (L1°UL1UL12UL13U 。 。 。 ) U (LlULl2ULl3Uooo)=(L1°UL1UL12UL13U o o o ) LIU (Ll°ULlULl2ULl3Uooo) Ll2Uooo=(LlULl2ULl3Uooo) U (Ll2ULl3ULl4ooo) Uooo (后面的项都被第一项吸收)=(LlULl2ULl3Uooo) =L1 + 同理可证得L1+L1*=L1 +1.32设Z = 0,l,请给出上Z的下列语言的形式表示。(1)所有以。开头的串。解答：00,1*。(2)所有以。开头，以1结尾的串。解答：00,1*1。(3)所有以11开头，以11结尾的串。解答：010,1*11。(4)所有最多有一对连续的。或者最多有一对连续的1的串。解答：01,1*仿,0010,1*1110,0*£,1101,0*。(5)所有最多有一对连续的。并且最多有一对连续的1的串。解答：按照实际情况分成4类:1)只有一对连续的 0： 0191：1：0010,12)只有一对连续的 1： 10,0*1101903)没有连续的。并且没有连续的1：10* U1。*。4)有一对连续的0和一对连续的1：01*0010*1101* U10)*ll)01*0010* O(6)所有长度为偶数的串。解答：0,1产, =1,2.(7)所有长度为奇数的串解答：012T,n=l,2.(8)所有包含子串01011的串。解答：1,0*010111,0*。(9)所有包含3个连续0的子串。解答:0,1*0000,1*(10)所有不包含3个连续0的串。解答：001, 01, 1(11)所有正数第10个字符是0的串。解答：0,1900,1*。(12)所有倒数第10个字符是。的串。1, 3, 4, 0, 3, 4, 2, 3, 4)(2) 所有基数不大于3的子集,0, 1, 2, 3, 4, 3, 4, 2, 4, 2, 3, 1, 4, 1, 3, 0, 4, 0, 3, 0, 2, 1, 2, 0, 1, 0, 1, 2, 0, 1, 30, 1, 4, 0, 2, 3, , 0, 2, 4, .1, 2, 3, 1, 2, 4, 1, 3, 4, 0, 3, 4, 2, 3, 4)1.5解答：1、3、8、10、11、12、16 正确L6证明下列各题目（02282081 刘秋雯）1） A=B, iff A是B的子集且B是A的子集证明：充分条件： . A=B则由集合相等的定义知对于任何x£A,有x£B A为B的子集同理，B为A的子集必要条件：,A为B的子集 对于任何x£A,都有x£B又B为A的子集，,对于任何x £ B有，x £ A由集合相等的定义知，A=B2）如果A为B的子集，则|A|二|B|证明：A为B的子集，则对于任何x£A有 x£B, 存在一个集合C使B=A U C 且A G C为空集则 |B|二|A|+|C|C|） =0 |A|二|B|3）如果A为B的真子集，则|A| < = |B|证明：（1）当A为有穷集合时，因为A为B的真子集，且则对于任何x£ A有 x£B,且存在£B的x,此*不£人存在一个非空集合C ,使B=AUC且AGC为空集则|B|二|A|+|C| 且|C|=1A|A| <|B|（2）当A为无穷集合，因为A为B的真子集，则B一定也为无穷集合，|A| = 8,回=8|A|=|B|综合（1）, （2）所述,|A|<=|B|4）如果A是有穷集且A为B的真子集则| A| <|B|证明：见上题证明（1）5）如果A为B的子集，则对于任何x£A,有x£B证明：若A为B的子集，则由子集定义可知，对于任何*£人，有x£B6）如果A是B的真子集，则对于任何x£A,有x£B,并且存在x£B,但乂不£人证明：由真子集的定义可证7）如果A为B的子集，B为C的子集，则A为C的子集证明：A为B的子集，B为C的子集则对于任何x£A,则乂都£8,且，又对于任何y£B,则丫£（2, 对于任何x£A, x£C.A为C的子集8）如果A为B的真子集，B为C的真子集，则A为C的真子集证明：A为B的真子集，B为C的真子集则对于任何x£A,则x都£B,且，存在x£B但次*不£人，又对于任何y£B,则y£C,存在y£C但此丫不£8,对于任何x£A, x£C,存在x£C.x不£AA为C的真子集9）如果A为B的子集，B为C的真子集，则A为C的真子集证明：因为A为B的子集，B为C的真子集则对于任何x£A, x者B£B,且*都£©又对于任何y£B,则y£C,存在y£C但此y不£B,则y不£A对于任何x£A, xec,存在x£C.x不£AA为C的真子集10）如果A为B的真子集，B为C的子集，则A为C的真子集证明：A为B的真子集，B为C的子集则对于任何x£A,则x都£B,且存在x£B但次乂不£人，又对于任何y£B,则y£C.二对于任何x£A, x£C,存在*£（2次不£人A为C的真子集11）如果 A=B,则 |A| 二 |B|证明：A=B,则A与B所含元素相同12）如果A为B的子集，B为C的真子集，或如果A为B的真子集，B为C的子集，则 A为C的真子集证明：证明见9, 101.7 A = 1,2,345,6 B = 1,3,5 C = 2,4,6 U = 0,12,3,4,5,6,7,8,9(1) .= 1,3,5 =B(2) .(ApB)|JC= 1,3,5|J(2,4,6)二1,2,3,4,5,6二 A(3) .(Af|B)|J(C7-C)= 1,3,5 |J 0,135,7,8,9二0,1,3,578,9二 C(4) .A-B-C= 2,4,6-2,4,6)二中(5) .A X B 义 C X 二A X二(6) .(aQb)U4Jc|Ja二 1,3,5 U 0,7,8,9|J 0,7,8,9= 0,135,7,8,9二 C(7) . AxBx AQC=AxBxC= Ax(a,b) | (a e Bb e C)或(a e B,b e C)或(a e B.b e C)二(a/,c) | (a e A.b e B,c g C)或(a e A.b e B.c e C)或(a g A.b ee C)(8) .4jBp|(A|jB)UC=4Jc=A=b 2, 3, 4, 5, 61. 8对论域U上的集合A、B、C,证明以下结论成立。(02282047吴贤培)(1) AUB=BUA证：对任意的x,xEAUBOx£ Av x£BOx£B v x£ AOx£B U A故AUB = BUA 且 BUAcAUB则 AUB = BUAo(2) (AUB)UC = AU(BUC) 证：对任意的x,xe(AUB)UC<=>xe(AUB)VxecO(x£Avx£B)Vx£COx£AvxWBVx£COx£Av(x£B Vx£C)<>xeAvxe(BUC)<=>xeAU(BUC)故(AUB)UC c AU(BUC)且 A U (B U C) c (A U B) U C则(AUB)UC = AU(BUC)o(3) AUB = AiffBoA证： 由B = AUB及 人口8 =人知BcAo由 BcA 知 X/x£B,x£A 则对任意的x,xeAUB nx£Av x£B =>xGA故 AUB = A,又 A = AUB,所以 AUB = Ao 综合得到AUB = AiffBcAo(4) AX(BUC) = (AXB)U(AUC) 证：对任意的有序对(a, b),(a, b)GAX(BUC) <=>aeAAbe(BUC) Oa£A/(b£Bvb£C)(a£A/b£B)v(a£A/b£C) O(a, b)eAXBv(a, b)eAXC <=>(a, b)G(AXB)U(AXC)故 AX(BUC) c (AXB)U(AUC)且(AXB)U(AUC)屋 AX(BUC) 则 A X (B U C) = (A X B) U (A U C)o(5) (BnC)XA = (BXA)A(CXA) 证：对任意的有序对(b, a),(b, a)e(BAC)XA<>be(B AC)AaeA<>(beB AbeQAaeA (b£B/a£A)/(b£C/a£A)O(b, a)eBXAA(b, a)ecXA<=>(b, a)e(BXA)n(CXA)故(BAC)XA = (BXA)A(CXA)且(BXA)A(CXA) = (BAC)XA 则(BnC)XA = (BXA)A(CXA)o(6) AX(B-C) = (AXB)-(AXC) 证：对任意的有序对(a, b),(a, b)eAX(B-C)<=>aeAAbe(B-C)<=> aAA(bBAbC)<>(aeAAbeB)A(aeAAbgC) O(a, b)eAXBA(a, b)AXC O(a, b)e(AXB)-(AXC)故 AX(BUC) c (AXB)U(AUC)且(AXB)U(AUC) c AX(BUC)则 A X (B U C) = (A X B) U (A U C)o需要说明的是：对于 (a,b)£AXB/(a,b)AXC=>(a A a b B) a (aAAbC本来，由(a, b)AXC 只能得到(aAvbC)o 但是(a, b)£AXB,故 a£A,这样，必须beC。如果AcB,则2Ac2B证：对任意的C, C£2A =>CcA由于 A = B,故 C = B,则 C&2B,从而 2A = 2B。AcB(8) 2 =2aP2b证：对任意的C,AcBCe2OC = AAB<=>CcA aCcB<=>Ce2AACe2B<=>Ce2AA2BAcBAcBAryB则 2 =2AQ2B 且 2AA2B，故 2 =2aA2bo(9) | AUB | W | A | + | B |证：由容斥原理，I AUB | = | A | + |B| -|AAB |当 AGBW 时、| AUB |< | A|+|B|当AGB=时，| AUB |= | A|+|B|由知 I AUB | | A | +| B | o(10) (B-C)XA=(BXA)-(CXA)证：对任意的有序对(b, a),(b, a)e(B-C)XA<>b£(BC)/ a£ A(bBAbC)AaAO(b£B/a£A)/(beC/a£A) O(b, a)eBXAA(b, a)CXA O(b, a)e(BXA)-(CXA)故(B-C)XA o (BXA)-(CXA)且(B*A) (CXA) Q (B-C)XA则(B-C)XA=(BXA)-(CXA)o需要说明的是：对于 (b,a)£BXA/(b,a)eCXA=>(b£B/a£A)/(beC/a£A)本来，由(b, a)CXA 只能得到(aAvbC)o 但是(b, a)£BX A,故 a£A, 这样，必须bee。(11)如果 A = B,则 B = A证：对任意的x, x£3-xeB由于A = B,故xeA,即x£A。因此，B o A o(12) B= A。AUB = U且 AGB=©证： 由B=N 以及N的定义知，AUB=AU A =U, AAB = An A=0o 由AGB=知，对任意的x£B, x电A,即Vx£B, xe A ,故B之久。又由AUB = U知，对任意的x£入，xA ,贝lx£B,故N =B。这样，B= A o综合得，B= A AUB=U JBL AAB=0o(13) AnB = A U B证：对任意的x,xe AcB<=>x(A AB)OxE Av xBOx£ A v x£ 8oxe(A u B)则 AcBqAuB且 A u B c ArB故Ac5 = A u B o(14) AuB = A n B证：对任意的x,xG AjB<=>x(AUB)OxE A axeBOx£ A ax£ B<>xe(A A B)则 = 且 A A B c A<jB故= A n B o1.9解答(6) R=(a,a),(b,b),(c,c),(d,d),(e,e),(a,b),(b,c),(a,c)(9) R= (a,a),(b,b),(c,c),(d,d),(e,e), (a,b),(b,c),(a,c),(b,a),(c,b),(c,a)1.10设Ri和R2是集合a,b,c,d,e上的二元关系淇中，Ri=(a,b),(c,d),(b,d),(b,b),(d,e), R2=(a,a),(b,c),(d,c),(e,d),(c,a) 求:R1R2,R2R1,R1+,R2+,R1*,R2*.解答：RiR2=(a,c),(c,c),(b,c),(d,d)R2R 尸(a,b),(b,d),(d,d),(e,e),(c,b)Ri+= (a,b),(c,d),(b,d)(b,b),(d,e),(a,d),(a,e),(b.e),(c,e)R2+= (a,a),(b,c),(d,c),(e,d),(c,a)(b,a),(d,a),(e,c),(e,a)Ri*= Ri+U (a,a),(b,b),(c,c),(d,d),(e,e)R2*= R2+U (a,a),(b,b),(c,c),(d,d),(e,e)LIL设R=(别卜仁私叫是集合但心斓同上的二元关系京：(敖雪峰)(1) R的传递闭包.(2) R的自反传递闭包.解：(1) R 的传递闭包是(a,b),(c,d),(b,d),(a,d).(2) R 的自反传递闭包是(e,e),(a,a),(b,b),(c,c),(d,d),(a,b),(c,d),(b,d),(a,d)L 12设q和R2是集合Ab,c,d,e上的二元关系，请证明下列关系。(唐明珠 02282084)(1) RR。w R)R o证明：用反证法，假设为尺2=&飞。设=(a,Z?),(c,d),/?2 =S，c)，S，e)。则氏2 =(©,尺2)=(,"),这与凡/?2 =足2用相矛盾，所以 RR?。R?R0(2)(尺|尺2)& = R1(&&)。证明：任取(x.,y),其中 x,y£