离散数学左孝凌3.ppt

第三章集合与关系〔SetsandRelations);;;3-1集合的概念和表示方法;3-1.1有关集合的概念;3-1.2集合的表示方法;3-1.2集合的表示方法;两种表示法可以互相转化;3-1.3数的集合;3-1.4集合之间的关系;〔1〕子集;证明A?B??x(x?A?x?B)成立

[证明]：根据定义

A?B?(?x)(x?A?x?B)

那么A?B??(?x)(x?A?x?B)

?(?x)?(?(x?A)?(x?B))

?(?x)((x?A)??(x?B))

?(?x)(x?A?x?B)

子集(举例)

设A={a,b,c},B={a,b,c,d},C={a,b},那么

A?B,C?A,C?B;定理3-1.1集合A和集合B相等的充分必要条件是这两个集合互为子集。

A=B?A?B?B?A

A=B?(?x)(x?Ax?B)

[证明]

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?Ax?B)(等价式);包含(?)的性质：;〔2〕真子集;A?B的含义：;?真包含(?)的性质;3．假设A?B,且B?C,那么A?C〔传递性〕

证明:A?B?A?B?A?B?A?B(化简),

同理B?C?B?C,所以A?C.

假设A=C,那么B?C?B?A,又A?B,故A=B,此与A?B矛盾,所以A?C.

所以,A?C.#;〔3〕空集;?[推论]空集是唯一的.〔可作为讨论〕

证明:设?1与?2都是空集,那么

?1??2??2??1??1=?2.#;〔4〕全集;〔5〕幂集;[定理]如果有限集合A有n个元素，那么幂集P(A)有2n个元素。

证明:利用二项式展开定理。;作业(3-1)：;3-2集合的运算;例2:设An={x?R|0?x?1/n},n=1,2,…,那么

A1?A2???An??=;不相交(disjoint);集合交运算的性质;3-2.2集合的并;例2:设An={x?R|0?x?1/n},n=1,2,…,那么

A1?A2???An??=;集合并运算的性质;3-2.3集合的补／相对补;集合补运算的性质;3-2.4集合的对称差;对称差(?)的性质;相对补、对称差(举例);3-2.5集合运算的性质〔集合恒等式〕;(4)分配律(distributivelaws)

A?(B?C)=(A?B)?(A?C)

A?(B?C)=(A?B)?(A?C)

(5)对合律(doublecomplementlaw)

~~A=A

(6)零律(dominancelaws)

A?E=E

A??=?;(7)同一律(identitylaws)

A??=A

A?E=A

(8)排中律(excludedmiddle)

A?~A=E

(9)矛盾律(contradiction)

A?~A=?

(10)全补律

~?=E

~E=?;(11)吸收律(absorptionlaws)

A?(A?B)=A

A?(A?B)=A

(12)德.摩根律(DeMorgan’slaws)

~(A?B)=~A?~B

~(A?B)=~A?~B

(13)补交转换律(differenceasintersection)

A-B=A?~B;3-2.6集合恒等式证明(方法);〔1〕逻辑演算法(格式);例1：分配律(定理3-2.1);例2：零律(证明);例3.?排中律(证明);(2)集合演算法〔格式〕;例1：吸收律(定理3-2.2);例2：吸收律(定理3-2.2);(2)集合演算法〔格式〕续;3-2.7集合恒等式证明(举例);②德?摩根律的相对形式

A-(B?C)=(A-B)?(A-C)

A-(B?C)=(A-B)?(A-C)

证明:A-(B?C)

=A?~(B?C)(补交转换律)

=A?(~B?~C)(德?摩根律)

=(A?A)?(~B?~C)(幂等律)

=(A?~B)?(A?~C)(交换律,结合律)

=(A-B)?(A-C)(补交转换律).#;;3-4??序偶与笛卡尔积;?3-4.2三元组(orderedtriple);3-4.3?笛卡尔积及其性质;例1:A={?,a},B={1,