形式语言与自动机理论-蒋宗礼-第一章参考答案.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,2,3,4的辕集。解：,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,1,2,3,4(8)所有的非负奇数。解：1,3,5,7,(9)0100的所有正整数。解：1,2,3,，100(10)110之间的和为10的整数集合的集合。解：设所求的集合为A,集合A中的元素为Ai(i=l,2,3,)，Ai也是集合，Ai中的元素在110之间，并且和为10。根据集合元素的彼此可区分性，可以计算出Ai中元素的最多个数，方法是：把1开始的正整数逐个相加，直到等于10(即IO=I+2+3+4),这样，Ai中最多有4个元素。原因是：从最小的1开始，每次参加新的元素都只依次增加1,这样相加的和最小，要加到10,元素个数就最多。求出最大的IAiI=4后，再求出元素个数为3,2,1的集合就可以了。故A=10,1,9,2,8,3,7,4,6,1,2,7),1,3,6,1,4,5,2,3,5,1,2,3,4)1.2请用命题法给出以下集合2.(l)x0x100iLxz(2)xx,且IXl<4(3)BB1,2,3,4)(4)LL,M*(5)xx=2n-l,nN(6)(,力I+b=10且4b4,9(7)xx0,l且x的个数是1的个数的两倍(8)xx0,l*,且冲1的个数是10(9)xx0,l且X中倒数第十个字符为1IAIl(10)A.Ax.l,101,A,.=101.3给出以下集合的器集.(02282075冯蕊)(1)(2) (3) ,)(4) ,0,00(5) 0,1解答：(1) (2) ,)(3) ,)(4) ,£,0,00),0),00),0,00,0,00)(5) ,0,l,0,l14.列出集合0,L2,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),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,3)(0,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正确1.6证明以下各题目1JA=B,iffA是B的子集且B是A的子集证明：充分条件：VA=B那么由集合相等的定义知对于任何x£A,有xB,A为B的子集同理，B为A的子集必要条件：.A为B的子集对于任何x£A,都有xB又TB为A的子集，J对于任何XeB有，xA由集合相等的定义知，A=B2如果A为B的子集，那么IAl<=B证明：A为B的子集，那么对于任何xA有xB,存在一个集合C使B=AUC且AC为空集那么IBl=IA|+|ClC>=O.,.A(=B3如果A为B的真子集，那么IAl<=B证明：(1)当A为有穷集合时，因为A为B的真子集，且那么对于任何xA有xB,且存在B的X,此X不A存在一个非空集合C,使B=AIJC且AC为空集那么IBl=IA+Cl且IeD=1.,.A<B(2)当A为无穷集合，因为A为B的真子集，那么B-定也为无穷集合，A=8,B=IAI=IBI综合(1),(2)所述，IAlV=IBl4如果A是有穷集且A为B的真子集那么IAl<B证明：见上题证明(1)5如果A为B的子集，那么对于任何xA,有xB证明：假设A为B的子集，那么由子集定义可知，对于任何xA,有xB6如果A是B的真子集，那么对于任何xA,有xB,并且存在xB,但X不A证明：由真子集的定义可证7如果A为B的子集，B为C的子集，那么A为C的子集证明：A为B的子集，B为C的子集那么对于任何X七A,那么X都B,且，又对于任何y£B,那么y£C,；对于任何*£人，xC.A为C的子集8如果A为B的真子集，B为C的真子集，那么A为C的真子集证明：A为B的真子集，B为C的真子集那么对于任何X七A,那么X都B,且，存在xB但次X不七A,又对于任何yB,那么yC,存在yC但此y不B,，对于任何x£A,xC,存在x£C.x不EA.A为C的真子集9如果A为B的子集，B为C的真子集，那么A为C的真子集证明：因为A为B的子集，B为C的真子集那么对于任何xA,X都B,且X都C又对于任何y£B,那么yC,存在y£C但此y不B,那么y不A对于任何x0A,xC,存在xC.x不EA,A为C的真子集10如果A为B的真子集，B为C的子集，那么A为C的真子集证明：A为B的真子集，B为C的子集那么对于任何xA,那么X都B,且存在xB但次X不A,又对于任何y£B,那么yC对于任何x6A,xC,存在xC.x不EA.A为C的真子集11如果A=B,那么IAl=IBl证明：A=B,那么A与B所含元素相同.,.A=B12如果A为B的子集，B为C的真子集，或如果A为B的真子集，B为C的子集，那么A为C的真子集证明：证明见明IO1.7A=1,2,3A5,6B=1,3,5C=2,4,6U=0,1,2,3,4,5,6,7,8,9(1) .ApP=1,3,5)=B(2) .(App)IjC=1,3,5J2A6二1,2,3,4,5,6二A(3) .(4PP)U(U-C)=15JO,15,7,8,9)=0,l,3,5,7,8,9二C(4) .A-B-C=2,4,6)-2A6)二(5) .AXBXCX二AX=(6)XB)4JcJa=1,3,5U0,7,8,9U0,7,8,9)=O,1,3,5J,8,9)=C(7) .A×B×AC=A×B×C=A×(a,b)I(aB,bC)或(B,bC)或(B,bC)=(,aC)I(aA,bB,cC)或(,bB,cC)或(A,bB,cC)(8) .4J(AjB)UC=a114Jc=AUC=A=1,2,3,4,5,61. 8对论域U上的集合A、B、C,证明以下结论成立。(02282047吴贤瑜(1) AUB=BUA证：对任意的X,xAUB<z>xAVxB<=>xBvxAOXeBIJA故AUBqBUA且BUAAUB那么AUB=BUAo(2) (AUB)Uc=AU(BUC)证：对任意的X,x(AUB)UC<=>x(AUB)VxC<=>(xAvxB)VxCOXAvxBVxC<z>xAv(xBVxC)<=>xAvx(BUC)<=>xAU(BUC)故(AUB)UCAU(BUC)且AU(BUC)(AUB)UC那么(AUB)UC=AU(BUC)°(3) AUB=AiffBeA证：由BqAUB及AUB=A知BAo由BA知VWB,xA那么对任意的X,xAUBz>xAvxBz>xA故AUBA,又AqAUB,所以AUB=Ao综合得到AUB=AiffBoA0(4) A×(BUC)=(A×B)U(AUC)证：对任意的有序对(a,b),(a,b)A×(BUC)<z>aAb(BUC)<>aA(bBvbC)O(aAbB)v(aAbC)<=>(a,b)A×Bv(a,b)A×C<=>(a,b)(A×B)U(A×C)AX(BUC)(AXB)U(AUC)且(AXB)U(AUC)AX(BUC)那么AX(BUC)=(AXB)U(AUC)o(5) (BnC)XA=(BXA)CI(CXA)证：对任意的有序对(b,a),(b,a)(BC)×A<z>b(BC)aA<z>(bBbC)aA<>(bBaA)(bCaA)<=>(b,a)B×A(b,a)C×A<=>(b,a)(B×A)(C×A)故(BCC)XA(B×A)(C×A)且(BXA)(CXA)(BC)×A那么(BgC)XA=(BXA)G(CXA)O(6) AX(B-C)=(AXB)-(AXC)证：对任意的有序对(a,b),(a,b)A×(B-C)<>aAab(B-C)<>aA(bBb¢C)<z>(aAbB)(aAb¢C)<=>(a,b)A×B(a,b)史AXC<=>(a,b)(AXB)-(AXC)AX(BUC)(AXB)U(AUC)且(AXB)U(AUC)AX(BUC)那么AX(BUC)=(AXB)U(AUC)o需要说明的是：对于(a,b)AXBA(a,b)eAXC本来，由（a,zz>(aAabB)(aAbCb)走AXC只能得到(a¢AvbC)o但是(a,b)£AXB,故aA,这样，必须b足C。(7)如果AqB,那么2A±2B证：对任意的C,C2a=>CqA由于AqB,故CqB,那么C2ij,从而2Aq2B.Ar>B(8) 2=2a2b证：对任意的C,C2<=>CAB<>CACB<=>C2aC2b<z>C2a2bAoBAcBArtB那么2c2A2B且2A2ij=2,故2=2a2b0(9) IAUBIIAI+IBI证：由容斥原理，IAUBI=IAI÷IBI-IABI当ABW时，IAUBI<IAI+IBI当AB=时，IAUBl=IAl+B由知IAUBIIAI+IBIo(10) (B-C)XA=(BXA)-(C