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

《形式语言与自动机理论-蒋宗礼-第一章参考答案.docx》由会员分享，可在线阅读，更多相关《形式语言与自动机理论-蒋宗礼-第一章参考答案.docx（22页珍藏版）》请在优知文库上搜索。

1、第一章参考答案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

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、素个数为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,且IXl4(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)

4、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,

5、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那么由集合相等的定义知对于任何xA,有xB,A为B的子集同理，B为A的子集必要条件：.A为B的子集对于任何xA,都有xB又TB为A的子集，J对于任何XeB有，xA由集合相等的定义知，A=B2如果A为B的子集，那么IAl=O.,.A(=B3如果A为B的真子集，那么IAl=B证明：(1)当A为有穷集合时，因为A为B的真子集，且那么对于任何xA有xB,且存在B的X,此X不A存在一个非空集合C,使B=AIJC且AC为空集那么IBl=I

6、A+Cl且IeD=1.,.AB(2)当A为无穷集合，因为A为B的真子集，那么B-定也为无穷集合，A=8,B=IAI=IBI综合(1),(2)所述，IAlV=IBl4如果A是有穷集且A为B的真子集那么IAlB证明：见上题证明(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,且，又对于任何yB,那么yC,；对于任何*人，xC.A为

7、C的子集8如果A为B的真子集，B为C的真子集，那么A为C的真子集证明：A为B的真子集，B为C的真子集那么对于任何X七A,那么X都B,且，存在xB但次X不七A,又对于任何yB,那么yC,存在yC但此y不B,，对于任何xA,xC,存在xC.x不EA.A为C的真子集9如果A为B的子集，B为C的真子集，那么A为C的真子集证明：因为A为B的子集，B为C的真子集那么对于任何xA,X都B,且X都C又对于任何yB,那么yC,存在yC但此y不B,那么y不A对于任何x0A,xC,存在xC.x不EA,A为C的真子集10如果A为B的真子集，B为C的子集，那么A为C的真子集证明：A为B的真子集，B为C的子集那么对于任何

8、xA,那么X都B,且存在xB但次X不A,又对于任何yB,那么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

9、,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) .ABAC=ABC=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,xAUBxAVxBxBvxAOXeBIJA故AUBqBUA且B

10、UAAUB那么AUB=BUAo(2) (AUB)Uc=AU(BUC)证：对任意的X,x(AUB)UCx(AUB)VxC(xAvxB)VxCOXAvxBVxCxAv(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,xAUBzxAvxBzxA故AUBA,又AqAUB,所以AUB=Ao综合得到AUB=AiffBoA0(4) A(BUC)=(AB)U(AUC)证：对任意的有序对(a,b),(a,b)A(BUC)

11、aAb(BUC)aA(bBvbC)O(aAbB)v(aAbC)(a,b)ABv(a,b)AC(a,b)(AB)U(AC)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)Ab(BC)aA(bBbC)aA(bBaA)(bCaA)(b,a)BA(b,a)CA(b,a)(BA)(CA)故(BCC)XA(BA)(CA)且(BXA)(CXA)(BC)A那么(BgC)XA=(BXA)G(CXA)O(6) AX(B-C)=(AXB)-(AXC)证

12、：对任意的有序对(a,b),(a,b)A(B-C)aAab(B-C)aA(bBbC)(aAbB)(aAbC)(a,b)AB(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只能得到(aAvbC)o但是(a,b)AXB,故aA,这样，必须b足C。(7)如果AqB,那么2A2B证：对任意的C,C2a=CqA由于AqB,故CqB,那么C2ij,从而2Aq2B.ArB(8) 2=2a2b证：对任意的C,C2CABCACBC2aC2bC2a2bAoBAcBArtB那么2c2A2B且2A2ij=2,故2=2a2b0(9) IAUBIIAI+IBI证：由容斥原理，IAUBI=IAIIBI-IABI当ABW时，IAUBIIAI+IBI当AB=时，IAUBl=IAl+B由知IAUBIIAI+IBIo(10) (B-C)XA=(BXA)-(C