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

1第一章参考答案1.1请用列举法给出下列集合。（吴贤珺02282047）⑴你知道的各种颜色。解：{红，橙，黄，绿，青，蓝，紫}⑵大学教师中的各种职称。解：{助教，讲师，副教授，教授}⑶你所学过的课程。解：{语文，数学，英语，物理，化学，生物，历史，地理，政治}⑷你的家庭成员。解：{父亲，母亲，妹妹，我}⑸你知道的所有交通工具。解：{汽车，火车，飞机，轮船，马车}⑹字母表{a,b}上长度小于4的串的集合。解：{a,b,aa,bb,ab,ba,aaa,aab,aba,abb,baa,bab,bba,bbb}⑺集合{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}}⑻所有的非负奇数。解：{1,3,5,7,…}⑼0～100的所有正整数。解：{1,2,3,…,100}(10)1～10之间的和为10的整数集合的集合。解：设所求的集合为A，集合A中的元素为Ai（i=1,2,3,…），Ai也是集合，Ai中的元素在1～10之间，并且和为10。根据集合元素的彼此可区分性，可以计算出Ai中元素的最多个数，方法是：把1开始的正整数逐个相加，直到等于10（即10=1+2+3+4），这样，Ai中最多有4个元素。原因是：从最小的1开始，每次加入新的元素都只依次增加1，这样相加的和最小，要加到10，元素个数就最多。求出最大的∣Ai∣＝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****2.(1){|0100}(2){|{,}||4}(3){|{1,2,3,4}}(4){|{,}*}(5){|21,}(6){(,)|10,[4,9]}(7){|{01}0}|{01}|{01}xxxzxxabxBBLLabxxnnNabababxxxxxxxxx且且且，，且中的个数是1的个数的两倍（8）{，，且中1的个数是10}(9){，，且中倒数第十个字符|||1,[1,10],[1,||],AiiiixAxiAx为1}（10）{A|=10}1.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},{1},{0,1}}1.4.列出集合{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}，{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正确31.6证明下列各题目（02282081刘秋雯）1）A=B，iffA是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∪C且A∩C为空集则|B|=|A|+|C||C|〉=0∴|A|〈=|B|3）如果A为B的真子集，则|A|〈=|B|证明：（1）当A为有穷集合时，因为A为B的真子集，且则对于任何x∈A有x∈B,且存在∈B的x，此x不∈A∴存在一个非空集合C，使B=A∪C且A∩C为空集则|B|=|A|+|C|且|C|〉=1∴|A|〈|B|（2）当A为无穷集合，因为A为B的真子集，则B一定也为无穷集合，|A|＝∞，|B|＝∞∴|A|=|B|综合（1），（2）所述，|A|=|B|4）如果A是有穷集且A为B的真子集则|A|〈|B|证明：见上题证明（1）5）如果A为B的子集，则对于任何x∈A，有x∈B证明：若A为B的子集，则由子集定义可知，对于任何x∈A，有x∈B6）如果A是B的真子集，则对于任何x∈A，有x∈B，并且存在x∈B，但x不4∈A证明：由真子集的定义可证7）如果A为B的子集，B为C的子集，则A为C的子集证明：A为B的子集，B为C的子集则对于任何x∈A，则x都∈B，且，又对于任何y∈B，则y∈C，∴对于任何x∈A，x∈C∴A为C的子集8）如果A为B的真子集，B为C的真子集，则A为C的真子集证明：A为B的真子集，B为C的真子集则对于任何x∈A，则x都∈B，且，存在x∈B但次x不∈A，又对于任何y∈B，则y∈C，存在y∈C但此y不∈B，∴对于任何x∈A，x∈C，存在x∈C.x不∈A∴A为C的真子集9）如果A为B的子集，B为C的真子集，则A为C的真子集证明：因为A为B的子集，B为C的真子集则对于任何x∈A，x都∈B，且x都∈C又对于任何y∈B，则y∈C，存在y∈C但此y不∈B，则y不∈A∴对于任何x∈A，x∈C，存在x∈C.x不∈A∴A为C的真子集10）如果A为B的真子集，B为C的子集，则A为C的真子集证明：A为B的真子集，B为C的子集则对于任何x∈A，则x都∈B，且存在x∈B但次x不∈A，又对于任何y∈B，则y∈C∴对于任何x∈A，x∈C，存在x∈C.x不∈A∴A为C的真子集11）如果A=B，则|A|=|B|证明：A=B，则A与B所含元素相同∴|A|=|B|12）如果A为B的子集，B为C的真子集，或如果A为B的真子集，B为C的子集，则A为C的真子集证明：证明见9，101.7A={1,2,3,4,5,6}B={1,3,5}C={2,4,6}U={0,1,2,3,4,5,6,7,8,9}(1).BA5={1,3,5}=B(2).CBA)(={1,3,5}}6,4,2{={1,2,3,4,5,6}=A(3).)()(CUBA={1,3,5}}9,8,7,5,3,1,0{={0,1,3,5,7,8,9}=C(4).A-B-C={2,4,6}–{2,4,6}=(5).A×B×C×=A×=(6).ACABA)(={1,3,5}{0,7,8,9}{0,7,8,9}={0,1,3,5,7,8,9}=C(7).CABA=CBA=)},(),(),(|),{(CbBaCbBaCbBabaA或或=)},,(),,(),,(|),,{(CcBbAaCcBbAaCcBbAacba或或(8).CBABA)(=CAA=CA=A={1，2，3，4，5，6}61．8对论域U上的集合A、B、C，证明以下结论成立。（02282047吴贤珺）⑴A∪B＝B∪A证：对任意的x，x∈A∪Bx∈Ax∈Bx∈Bx∈Ax∈B∪A故A∪BB∪A且B∪AA∪B则A∪B＝B∪A。⑵(A∪B)∪C＝A∪(B∪C)证：对任意的x，x∈(A∪B)∪Cx∈(A∪B)x∈C(x∈Ax∈B)x∈Cx∈Ax∈Bx∈Cx∈A(x∈Bx∈C)x∈Ax∈(B∪C)x∈A∪(B∪C)故(A∪B)∪CA∪(B∪C)且A∪(B∪C)(A∪B)∪C则(A∪B)∪C＝A∪(B∪C)。⑶A∪B＝AiffBA证：①由BA∪B及A∪B＝A知BA。②由BA知x∈B,x∈A则对任意的x，x∈A∪Bx∈Ax∈Bx∈A故A∪BA，又AA∪B，所以A∪B＝A。综合①②得到A∪B＝AiffBA。⑷A×(B∪C)＝(A×B)∪(A∪C)证：对任意的有序对(a,b)，(a,b)∈A×(B∪C)a∈Ab∈(B∪C)a∈A(b∈Bb∈C)(a∈Ab∈B)(a∈Ab∈C)(a,b)∈A×B(a,b)∈A×C(a,b)∈(A×B)∪(A×C)故A×(B∪C)(A×B)∪(A∪C)且(A×B)∪(A∪C)A×(B∪C)则A×(B∪C)＝(A×B)∪(A∪C)。⑸(B∩C)×A＝(B×A)∩(C×A)7证：对任意的有序对(b,a)，(b,a)∈(B∩C)×Ab∈(B∩C)a∈A(b∈Bb∈C)a∈A(b∈Ba∈A)(b∈Ca∈A)(b,a)∈B×A(b,a)∈C×A(b,a)∈(B×A)∩(C×A)故(B∩C)×A(B×A)∩(C×A)且(B×A)∩(C×A)(B∩C)×A则(B∩C)×A＝(B×A)∩(C×A)。⑹A×(B－C)＝(A×B)－(A×C)证：对任意的有序对(a,b)，(a,b)∈A×(B－C)a∈Ab∈(B－C)a∈A(b∈BbC)(a∈Ab∈B)(a∈AbC)(a,b)∈A×B(a,b)A×C(a,b)∈(A×B)－(A×C)故A×(B∪C)(A×B)∪(A∪C)且(A×B)∪(A∪C)A×(B∪C)则A×(B∪C)＝(A×B)∪(A∪C)。需要说明的是：对于(a,b)∈A×B(a,b)A×C(a∈Ab∈B)(a∈AbC本来，由(a,b)A×C只能得到(aAbC)。但是(a,b)∈A×B，故a∈A，这样，必须bC。⑺如果AB，则2A2B证：对任意的C，C∈2ACA由于AB，故CB，则C∈2B，从而2A2B。⑻2BA＝2A∩2B证：对任意的C，C∈2BACA∩BCACBC∈2AC∈2BC∈2A∩2B则2BA2A∩2B且2A∩2B2BA，故2BA＝2A∩2B。⑼│A∪B│≤│A│＋│B│证：由容斥原理，│A∪B│＝│A│＋│B│－│A∩B│8①当A∩B≠Φ时，│A∪B│＜│A│＋│B│②当A∩B＝Φ时，│A∪B│＝│A│＋│B│由①②知│A∪B│≤│A│＋│B│。(10)(B－C)×A＝(B×A)－(C×A)证：对任意的有序对(b,a)，(b,a)∈(B－C)×Ab∈(B－C)a∈A(b∈BbC)a∈A(b∈Ba∈A)(bCa∈A)(b,a)∈B×A(b,a)C×A(b,a)∈(B×A)－(C×A)故(B－C)×A(B×A)－(C×A)且(B×A)－(C×A)(B－C)×A则(B－C)×A＝(B×A)－(C×A)。需要说明的是：对于(b,a)∈B×A(b,a)C×A(b∈Ba∈A)(bCa∈A)本来，由(b,a)C×A只能得到(aAbC)。但是(b,a)∈B×A，故a∈A，这样，必须bC。(11)如果AB，则BA证：对任意的x，x∈BxB由于AB，故xA，即x∈A。因此，BA。(12)B＝AA∪B＝U且A∩B＝Φ证：①由B＝A以及A的定义知，A∪B＝A∪A＝U，A∩B＝A∩A＝Φ。②由A∩B＝Φ知，对任意的x∈B，xA，即x∈B，x∈A，故BA。又由A∪B＝U知，对任意的x∈A，xA，则x∈B，故AB。这样，B＝A。综合①②得，B＝AA∪B＝U且A∩B＝Φ。(13)BA＝A∪B证：对任意的x，x∈BAx(A∩B)9xAxBx∈Ax∈Bx∈(A∪B)则BAA∪B且A∪BBA故BA＝A∪B。(14)BA＝A∩B证：对任意的