教材及主要参考书目 1.蒋宗礼,姜守旭.形式语言与自动机理论.北京: 清华大学出版社,2003年 2. John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman. Introduction to Automata Theory, Addison-Wesley Publishing Company, 200 ition) Languages, and Computation (2nd edi 3. John E Hopcroft, Jeffrey d ulman. Introduction Automata Theory, Languages, and Computation Addison-Wesley Publishing Company, 1979 2021/2/20
2021/2/20 6 教材及主要参考书目 1.蒋宗礼，姜守旭. 形式语言与自动机理论. 北京： 清华大学出版社，2003年 2. John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman. Introduction to Automata Theory, Languages, and Computation (2 nd Edition). Addison-Wesley Publishing Company, 2001 3. John E Hopcroft, Jeffrey D Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Publishing Company, 1979
第1章绪论 1.1集合的基础知识 111集合及其表示 集合:一定范围内的、确定的、并且彼此可以区 分的对象汇集在一起形成的整体叫做集合(set), 简称为集(et) 元素:集合的成员为该集合的元素( element) 集合描述形式 基数。 集合的分类。 2021/2/20
2021/2/20 7 第1章 绪论 • 1.1 集合的基础知识 • 1.1.1 集合及其表示 – 集合：一定范围内的、确定的、并且彼此可以区 分的对象汇集在一起形成的整体叫做集合(set)， 简称为集(set)。 – 元素：集合的成员为该集合的元素(element)。 – 集合描述形式。 – 基数。 – 集合的分类
1.12集合之间的关系 子集 如果集合A中的每个元素都是集合B的元素, 则称集合A是集合B的子集( subset),集合B是 集合A的包集( container)记作AcB。也可记 作BA。AcB读作集合A包含在集合B中; BA读作集合B包含集合A。 如果AcB,且彐x∈B,但xA,则称A是B的 真子集( proper subset),记作AcB 2021/2/20 8
2021/2/20 8 1.1.2 集合之间的关系 • 子集 • 如果集合A中的每个元素都是集合B的元素， 则称集合A是集合B的子集(subset)，集合B是 集合A的包集(container)。记作AB。也可记 作BA。AB读作集合A包含在集合B中； BA读作集合B包含集合A。 • 如果AB，且x∈B，但xA，则称A是B的 真子集(proper subset)，记作AB
1.12集合之间的关系 集合相等 如果集合A,B含有的元素完全相同,则称集 合A与集合B相等( equivalence),记作A=B 对任意集合A、B、C: (1)A= Biface且BcA。 (2)如果AcB,则A≤B (3)如果AcB,则AB (4)如果A是有穷集,且AcB,则B>|A| 2021/2/20 9
2021/2/20 9 1.1.2 集合之间的关系 •集合相等 –如果集合A，B含有的元素完全相同，则称集 合A与集合B相等(equivalence)，记作A=B。 •对任意集合A、B、C： ⑴ A=B iff AB且BA。 ⑵ 如果AB，则|A|≤|B|。 ⑶ 如果AB，则|A|≤|B|。 ⑷ 如果A是有穷集，且AB，则|B|>|A|
1.12集合之间的关系 (5)如果AcB,则对vx∈A,有x∈B (6)如果AcB,则对x∈A,有x∈B并且 彐x∈B,但xgA。 (7)如果AcB且BcC,则AcC (8)如果AcB且BcC,或者AcB且BCC,或者 AcB且BcC,则AcC。 (9)如果A=B,则A=Bl 2021/2/20 10
2021/2/20 10 1.1.2 集合之间的关系 ⑸ 如果AB，则对x∈A，有x∈B。 ⑹ 如 果 AB ， 则 对 x∈A， 有 x∈B 并 且 x∈B，但xA。 ⑺ 如果AB且BC，则AC。 ⑻ 如果AB且BC，或者AB且BC，或者 AB且BC，则AC。 ⑼ 如果A=B，则|A|=|B|