[离散数学]集合论初步.ppt

《[离散数学]集合论初步.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二篇集合论主要包括如下内容：集合论初步二元关系函数第三章集合论初步本章主要介绍如下内容：基本概念及集合的表示方法集合间的关系特殊集合集合的运算＊包含排斥原理3-1基本概念1.集合与元素集合是个最基本的概念。集合：是由确定的对象(客体)构成的集体。用大写的英文字母表示。这里所谓“确定”是指：论域内任何客体，要么属于这个集合，要么不属于这个集合，是唯一确定的。元素：集合中的对象，称之为元素。∈：表示元素与集合的属于关系。例如，N表示自然数集合，2∈N，而1.5不属于N写成(1.5∈N),或写成1.5N。2.有限集合与无限集合这

2、里对有限集合与无限集合只给出朴素的定义，以后再给出严格的形式定义。有限集合：元素是有限个的集合。如果A是有限集合，用

3、A

4、表示A中元素个数。例如，A={1,2,3},则

5、A

6、=3。无限集合：元素是无限个的集合。对无限集合的所谓‘大小’的讨论，以后再进行。3.集合的表示方法列举法：将集合中的元素一一列出，写在大括号内。例如，N={1,2,3,4,……}A={a,b,c,d}描述法：用句子(或谓词公式)描述元素的属性。例如，B={x

7、x是偶数}C={x

8、x是实数且2≤x≤5}一般地，A={x

9、P(x)},其中P(x)是谓词公式，如果

10、论域内客体a使得P(a)为真，则a∈A，否则aA。4.说明⑴集合中的元素间次序是无关紧要的，但是必须是可以区分的，即是不同的。例如A={a,b,c,a}，B={c,b,a,}，则A与B是一样的。⑵对集合中的元素无任何限制，例如令A={人，石头，1，Ｂ},B={Φ,{Φ}}⑶本书中常用的几个集合符号的约定：自然数集合N={1,2,3,……}整数集合I，实数集合R，有理数集合Q⑷集合中的元素也可以是集合，下面的集合的含义不同：如a：张书记{a}:党支部(只有一个书记){{a}}：分党委(只有一个支部){{{a}}}：党委(只有一个

11、分党委){{{{a}}}}：市党委(只有一个党委)3-2集合间的关系一.被包含关系(子集)1.定义：A、B是集合，如果A中元素都是B中元素，则称B包含A，A包含于B，也称A是B的子集。记作AB。文氏图表示如右下图。例如，N是自然数集合，R是实数集合，则NR谓词定义：ABx(x∈Ax∈B)AB2.性质：⑴有自反性，对任何集合A有AA。⑵有传递性，对任何集合A、B、C，有AB且BC，则AC。⑶有反对称性，对任何集合A、B，有AB且BA，则A=B。二.相等关系1.定义：A、B是集合，如果它们的元素完全相同，则

12、称A与B相等。记作A=B。定理：A=B，当且仅当AB且BA。证明：充分性，已知AB且BA，假设A≠B，则至少有一个元素a,使得a∈A而aB；或者a∈B而aA。如果a∈A而aB，则与AB矛盾。如果a∈B而aA，则与BA矛盾。所以A=B。必要性显然成立，因为如果A=B，则必有AB且BA。谓词定义：A=BABBAx(x∈Ax∈B)x(x∈Bx∈A)x((x∈Ax∈B)(x∈Bx∈A))x(x∈Ax∈B)2.性质⑴有自反性，对任何集合A，有A=A。⑵有传递性，对任何集合A、B、

13、C，如果有A=B且B=C，则A=C。⑶有对称性，对任何集合A、B，如果有A=B，则B=A。三.真被包含关系(真子集)1.定义：A、B是集合，如果AB且A≠B，则称B真包含A，A真包含于B，也称A是B的真子集。记作AB。谓词定义：ABABA≠Bx(x∈Ax∈B)x(x∈Ax∈B)x(x∈Ax∈B)(x(x∈Ax∈B)x(x∈Bx∈A))(x(x∈Ax∈B)x(x∈Ax∈B))(x(x∈Ax∈B)x(x∈Bx∈A))x(x∈Ax∈B)x(x∈B

14、xA)2.性质有传递性，对任何集合A、B、C，如果有AB且BC，则AC。练习题：设A={a,{a},{a,b},{{a,b},c}}判断下面命题的真值。⑴{a}∈A⑵({a}A)⑶c∈A⑷{a}{{a,b},c}⑸{{a}}A⑹{a,b}∈{{a,b},c}⑺{{a,b}}A⑻{a,b}{{a,b},c}⑼{c}{{a,b},c}⑽({c}A)(a∈Φ)3-3特殊集合一.全集E定义：包含所讨论的所有集合的集合，称之为全集，记作E。实际上，就是论域。它的文氏图如右图。由于讨论的问题不同，全集也不同。所以全

15、集不唯一。例如，若讨论数，可以把实数集看成全集。若讨论人，可以把人类看成全集。E由于论域内任何客体x都属于E，所以x∈E为永真式。所以需要用永真式定义E。E={x

16、P(x)∨P(x)}性质：对于任何集合A，都有AE。二.空集Φ定义：没有元素的集合，称之为空集