《形式语言与自动机理论-蒋宗礼-第一章参考答案》由会员分享，可在线阅读，更多相关《形式语言与自动机理论-蒋宗礼-第一章参考答案（26页珍藏版）》请在金锄头文库上搜索。
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、2,4,1,3,4,2,3,4,1,2,3,4 所有的非负奇数。解：1,3,5,7, 0100的所有正整数。解：1,2,3,100(10) 110之间的和为10的整数集合的集合。解：设所求的集合为A，集合A中的元素为Ai（i=1,2,3,），Ai也是集合，Ai中的元素在110之间，并且和为10。根据集合元素的彼此可区分性，可以计算出Ai中元素的最多个数，方法是：把1开始的正整数逐个相加，直到等于10（即10=1+2+3+4），这样，Ai中最多有4个元素。原因是：从最小的1开始，每次加入新的元素都只依次增加1，这样相加的和最小，要加到10，元素个数就最多。求出最大的Ai4后，再求出元素个数为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,41.2 请用命题法给出下列集合 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,11.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）
4、 所有基数不大于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，41.5解答： 1、3、8、10、11、12、16正确1.6证明下列各题目 （02282081 刘秋雯）1）A=B，iff A是B的子集且B是A的子集证明：充分条件： A=B则由集合相等的定义知对于任何xA，有xBA为B的子集同理，B为A的子集必要条件：A为B的子集 对于任何xA，都有xB又B为A的子集，对于任何xB有，xA由集合相等的定义知，A=B2）如
5、果A为B的子集，则|A|=|B|证明：A为B的子集，则对于任何xA有xB,存在一个集合C 使B=AC 且AC为空集则|B|=|A|+|C|C|=0|A|=|B|3）如果A为B的真子集，则|A|=|B|证明：（1）当A为有穷集合时，因为A为B的真子集，且则对于任何xA有xB,且存在B的x，此x不A存在一个非空集合C ， 使B=AC 且AC为空集则|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为
6、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的子集 则对于任何xA，则x都B，且，又对于任何yB，则yC，对于任何xA，xCA为C的子集8）如果A为B的真子集，B为C的真子集，则A为C的真子集 证明： A为B的真子集，B为C的真子集 则对于任何xA，则x都B，且，存在xB但次x不A，又对于任何yB，则yC，存在yC但此y不B，对于任何xA，xC，存在xC.x不AA为C的真子集9
7、）如果A为B的子集，B为C的真子集，则A为C的真子集 证明： 因为A为B的子集，B为C的真子集 则对于任何xA， x都B，且x都C又对于任何yB，则yC，存在yC但此y不B，则y不A对于任何xA，xC，存在xC.x不AA为C的真子集10）如果A为B的真子集，B为C的子集，则A为C的真子集 证明： A为B的真子集，B为C的子集 则对于任何xA，则x都B，且存在xB但次x不A，又对于任何yB，则yC对于任何xA，xC，存在xC.x不AA为C的真子集11）如果A=B，则|A|=|B|证明： A=B，则A与B所含元素相同|A|=|B|12）如果A为B的子集，B为C的真子集，或如果A为B的真子集，B为C
8、的子集，则A为C的真子集证明：证明见9，101.7 A = 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). = 1,3,5 = B(2).= 1,3,5=1,2,3,4,5,6 = A(3).= 1,3,5=0,1,3,5,7,8,9 = (4).A-B-C= 2,4,6 2,4,6=(5).A B C =A = (6).= 1,3,50,7,8,90,7,8,9= 0,1,3,5,7,8,9 = (7).=(8).= = = =1，2，3，4，5，618 对论域U上的集合A、B、C，证明以下结论成立。 （0228204
9、7 吴贤珺） ABBA证：对任意的x，xAB xAxB xBxA xBA故ABBA 且 BAAB则 ABBA。 (AB)CA(BC)证：对任意的x，x(AB)C x(AB)xC (xAxB)xC xAxBxCxA(xBxC)xAx(BC )xA(BC) 故(AB)C A(BC) 且 A(BC) (AB)C 则 (AB)CA(BC)。 ABA iff BA证： 由BAB及 ABA知 BA。 由BA 知xB, xA 则对任意的x，xABxAxBxA 故 ABA，又AAB，所以 ABA。综合得到 ABA iff BA。 A(BC)(AB)(AC)证：对任意的有序对(a, b)，(a, b)A(BC)
10、 aAb(BC) aA(bBbC) (aAbB)( aAbC)(a, b)AB(a, b)AC(a, b)(AB)(AC) 故A(BC) (AB)(AC) 且 (AB)(AC) A(BC) 则 A(BC)(AB)(AC)。 (BC)A(BA)(CA)证：对任意的有序对(b, a)，(b, a)(BC)A b(BC)aA (bBbC)aA (bBaA)(bCaA)(b, a)BA(b, a)CA(b, a)(BA)(CA) 故(BC)A (BA)(CA) 且 (BA)(CA) (BC)A 则 (BC)A(BA)(CA)。 A(BC)(AB)(AC)证：对任意的有序对(a, b)，(a, b)A(
11、BC) aAb(BC) aA(bBbC) (aAbB)( aAbC)(a, b)AB(a, b)AC(a, b)(AB)(AC) 故A(BC) (AB)(AC) 且 (AB)(AC) A(BC) 则 A(BC)(AB)(AC)。 需要说明的是：对于 (a, b)AB(a, b)AC (aAbB)( aAbC 本来，由(a, b)AC 只能得到 (aAbC)。但是(a, b)AB，故aA，这样，必须bC。 如果 AB，则2A2B 证：对任意的C，C2A CA 由于AB，故CB，则C2B，从而2A2B。 22A2B证：对任意的C，C2 CAB CACB C2AC2B C2A2B则 2 2A2B 且 2A2B 2，故22A2B。 ABAB证：由容斥原理，ABABAB 当AB时，ABAB 当AB时，ABAB 由知ABAB。(10) (BC)A(BA)(CA)证：对任意的有序对(b, a)，(b, a)(BC)A
