大学离散数学

《大学离散数学》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学1.课程性质计算机数学基础课程2.教学内容集合（1）集合论自然数集二元关系（2）组合论：离散函数，计数与生成（3）图论：图，树（4）数理逻辑：命题逻辑，谓词逻辑（5）群论：群、环、域（不讲）3.预修课程（1）高等数学（2）线性代数（3）概率论4.下列课程的基础课（1）数据结构（2）数据库第一章集合§１集合[定义]集合：把一些确定的，彼此不同的对象作为一个整体考虑，这个整体称为集合。[定义]元素：集合里所含的个体称为集合的元素。注：大写英文字母表示集合小写英文字母（或加数字）表示集合的元素集合的表示法：１

2、.穷举法，例如：Ｓ＝｛２，４，６，８，１０｝将集合中的所有的元素罗列出来。２.描述法：把集合内元素的性质、特点概括描述出来，如上例：Ｓ＝｛ｘ｜ｘ是偶数且０＜ｘ≤１０｝元素与集合的关系：１.∈：ａ∈Ｓ，表示ａ是集合Ｓ中的元素读作ａ属于Ｓ２.：ａＳ，表示ａ不是Ｓ的元素读作ａ不属于Ｓ[定义]空集：集合中没有元素，称此集合为空集。注：１.是空集，｛Φ｝不是空集，此集合有一个元素2.｛Φ，｛Φ｝｝是有二个元素的集合3.同一集合里不能有相同的元素，元素之间没有先后次序（扩充集合除外）[定义]子集：集合Ｐ的元素均

3、属于集合Ｑ，称Ｐ为Ｑ的子集，记为ＰＱ。注：Ｐ包含在Ｑ中，不属于Ｑ的元素也不会属于Ｐ。[定义]集合相等：Ｐ与Ｑ包含相同的元素，记为Ｐ=Ｑ。即ＰＱ，又ＱＰ，得出Ｐ＝Ｑ。[定义]真子集：若Ｐ是Ｑ的子集，且Ｑ中至少有一个元素不属于Ｐ，称Ｐ是Ｑ的真子集，记为ＰＱ。注：1.ＰＱ意为：对a∈Ｐ，则a∈Ｑb∈Ｑ,但bＰ2.ΦＰ，即空集Φ是任何集合的子集Ｐ非空时，Φ是Ｐ的真子集，ΦＰ。3.任何集合Ｐ是自身Ｐ的子集，但不是真子集。[定义]平凡子集：Ｐ的平凡子集只有二个：Φ和Ｐ。[定义]基数：集合内元素的个数称为此集

4、合的基数。也称基度、势，记｜Ａ｜为集合Ａ的基数，或记为CardＡ。注：有限集：元素个数是有限个的集合。无限集：元素个数是无限个的集合。[定义]幂集：集合Ａ的所有子集组成的集合称为Ａ的幂集，记为Ｐ（Ａ）。注：1.Φ只有一个子集Φ，Ｐ（Φ）＝｛Φ｝ＣａｒｄＰ(Φ）＝20＝１2.设Ａ＝｛ａ｝，有二个子集Φ和｛ａ｝，Ｐ（Ａ）＝｛Φ，｛ａ｝｝

5、Ｐ(Ａ)

6、＝21＝２3.若Ａ＝｛ａ1，ａ2，…，ａn｝,

7、Ａ

8、=ｎ，则

9、Ｐ(Ａ)

10、＝2n即A的不同子集个数为：集合内元素是无序的，但用计算机进行操作时，只能对规定了次序的有限集进

11、行操作。例：Ｓ3＝｛ａ1，ａ2，ａ3｝Ｐ（Ｓ3）＝｛Ｂi｜i∈Ｊ｝其中：Ｊ＝｛i｜０００≤i≤１１１｝i是二进制数故有：Ｂ0＝Ｂ000＝Ｂ1＝Ｂ001＝｛ａ3｝Ｂ2＝Ｂ010＝｛ａ2｝Ｂ3＝Ｂ011＝｛ａ2，ａ3｝Ｂ4＝Ｂ100＝｛ａ1｝Ｂ5＝Ｂ101＝｛ａ1，ａ3｝Ｂ6＝Ｂ110＝｛ａ1，ａ2｝Ｂ7＝Ｂ111＝｛ａ1，ａ2，ａ3｝§２集合的运算及文氏图常常需要研究集合之间的关系，或用一些集合来构造另一些集合,这就需要讨论集合的运算。[定义]全集：包含当前讨论的所有元素的集合称为全集，记为Ｕ。[定义]并

12、集：把所有Ｐ与Ｑ的元素并在一起组成新的集合，称为Ｐ与Ｑ的并集，记为Ｐ∪Ｑ。Ｐ∪Ｑ＝｛ｘ｜ｘ∈Ｐorｘ∈Ｑ｝注：1.Ａ∪Ｂ＝Ｂ∪Ａ，ＡＡ∪Ｂ，ＢＡ∪Ｂ2.ＡＣ且ＢＣ，则Ａ∪ＢＣ3.｜Ａ∪Ｂ｜≤｜Ａ｜＋｜Ｂ｜。由于Ａ与Ｂ的公共元素在Ａ∪Ｂ中只出现一次，故当Ａ与Ｂ无公共元素且是有限集合时等式成立。4.当且仅当ＡＢ时Ａ∪Ｂ＝Ｂ。即要证：若ＡＢ，则有Ａ∪Ｂ＝Ｂ且若Ａ∪Ｂ＝Ｂ，则有ＡＢ而要证：若ＡＢ，则有Ａ∪Ｂ＝Ｂ，则需证：（1）Ａ∪ＢＢ（2）ＢＡ∪Ｂ又如何证明：Ａ∪ＢＢ？思路为：根据定义，对

13、a∈Ａ∪Ｂ，证明a∈Ｂ证明：若ＡＢ，则有Ａ∪Ｂ＝Ｂ（1）对ｘ∈Ａ∪Ｂ，则ｘ∈Ａ或ｘ∈Ｂ若ｘ∈Ａ，由ＡＢ，得出ｘ∈Ｂ故Ａ∪ＢＢ（2）显然ＢＡ∪Ｂ由集合相等定义得出Ａ∪Ｂ＝Ｂ。证毕。证明：若Ａ∪Ｂ＝Ｂ，则有ＡＢ用反证法，若ＡＢ则ｘ∈Ａ，而ｘＢ故ｘ∈Ａ∪Ｂ，而ｘＢ与Ａ∪Ｂ＝Ｂ（Ａ∪ＢＢ）矛盾。[定义]交集：所有既在Ｐ中又在Ｑ中的元素组成一个新的集合，称为Ｐ与Ｑ的交集，记为Ｐ∩Ｑ。即Ｐ∩Ｑ＝｛ｘ｜ｘ∈Ｐandｘ∈Ｑ｝注：（1）Ａ∩Ｂ＝Ｂ∩Ａ（交换律）（2）Ａ∩ＢＡ，Ａ∩ＢＢ（3）当且仅当ＣＡ

14、且ＣＢ时有ＣＡ∩Ｂ（4）｜Ｐ∩Ｑ｜≤｜Ｐ｜，｜Ｐ∩Ｑ｜≤｜Ｑ｜当Ｐ＝Ｑ时等号成立。（5）当且仅当ＡＢ时Ａ∩Ｂ＝Ａ[定义]差集：所有在Ｐ中而不在Ｑ中的元素组成一个新的集合，称为Ｐ减Ｑ的差集，记为Ｐ－Ｑ。Ｐ－Ｑ＝｛ｘ｜ｘ∈ＰandｘＱ｝注：（1）Ｐ－Ｑ只是在Ｐ中减去了Ｐ与Ｑ有公共元素即Ｐ－Ｑ＝Ｐ－（Ｐ∩Ｑ）（2）若Ｐ∩Ｑ＝Φ则Ｐ－Ｑ＝Ｐ（3）ＱＰ有