離散數(shù)學(xué)---集合代數(shù)

1、第二部分 集合論引言第6章 集合代數(shù)第7章 二元關(guān)系第8章 函數(shù)2022/7/211集合論集合論：研究集合的數(shù)學(xué)理論起源George Cantor (1845-1918，德國(guó)) 重要性它是數(shù)學(xué)的一個(gè)基本分支，在數(shù)學(xué)中占據(jù)著一個(gè)極其獨(dú)特的地位，其基本概念已滲透到數(shù)學(xué)的所有領(lǐng)域。集合論廣泛地應(yīng)用于計(jì)算機(jī)科學(xué)領(lǐng)域如：形式語(yǔ)言、自動(dòng)機(jī)理論、人工智能、數(shù)據(jù)庫(kù)等。如果把現(xiàn)代數(shù)學(xué)比作一座無(wú)比輝煌的大廈，那么可以說(shuō)集合論正是構(gòu)成這座大廈的基石。2022/7/212第6章 集合代數(shù)6.1 集合的基本概念6.2 集合的基本運(yùn)算及恒等式6.3 集合中元素的計(jì)數(shù)本章小結(jié)2022/7/2136.1 集合的基本概念集合集

2、合是數(shù)學(xué)中的一個(gè)基本概念，一般地，由一些可區(qū)分的對(duì)象組成的一個(gè)整體，稱為集合。通常用大寫(xiě)字母A、B、表示集合。集合的元素集合中的對(duì)象稱為集合的元素。通常用小寫(xiě)字母a、b、c、表示集合的元素。注：集合由它的元素所決定。2022/7/2146.1 集合的基本概念集合表示方法列舉法A1，2，3，4N0，1，2，3，謂詞表示法: 用謂詞描述出集合元素的屬性（特征）形如： Sx|P(x)如：Bx|xRx210 樹(shù)形圖表示法如：A a, b,c , d, d 2022/7/2156.1 集合的基本概念集合的元素的性質(zhì):確定性設(shè)a為任意元素，S為任意集合，則aS或a S，二者必居其一，且只居其一。集合中的元

3、素是互異的;集合中的元素?zé)o次序和大小之分;抽象性2022/7/2166.1 集合的基本概念練習(xí):求使得下列集合等式成立時(shí)，a, b, c, d應(yīng)該滿足的條件：(1) a , b a, b, c(2) a, b, a a,b(3) a, , b, c 答： (1) ac或cb (2) 任意a, b(3) ac,且b2022/7/2176.1 集合的基本概念集合的基數(shù)集合A中的不同元素個(gè)數(shù)稱為集合A的基數(shù)，記做|A|。集合的分類(lèi)：有限集合無(wú)限集合空集注意： 和的區(qū)別全集E2022/7/2186.1 集合的基本概念集合間的關(guān)系的定義設(shè)A、B是任意兩個(gè)集合A B x(x A x B) AB A B B

4、A x(x A x B)AB x(x A x B ） x(x B x A ）2022/7/2196.1 集合的基本概念顯然：(1) A (2) A A (3) 若A B BC ，那么A C 推論：空集是唯一的。2022/7/21106.1 集合的基本概念冪集：設(shè)A為一個(gè)集合，A的冪集(A)是A的所有子集的集合，即：(A)B|B A例：若A ，則(A)=；若A a，則(A)=,a；若A a,b，則(A)=,a,b,a,b；若A a,b,c，則(A)=,a,b,c,a,b,a,c,b,c,a,b,c;2022/7/21116.1 集合的基本概念定理：若|A|n, 則|(A)|2n；證明（方法1）對(duì)

5、每個(gè)i(0in)，A的恰有i個(gè)元素的子集的個(gè)數(shù)即是從A的n個(gè)元素中選取i個(gè)元素的組合數(shù).2022/7/21126.1 集合的基本概念證明（方法2）： 設(shè)Aa1,a2,，an，則：一方面：對(duì)于A的任何子集S可以表示為一個(gè)n位二進(jìn)制數(shù)b1b2bn，其中2022/7/21136.1 集合的基本概念另一方面：對(duì)于任意一個(gè)n位二進(jìn)制數(shù)b1b2bn，也可以唯一地對(duì)應(yīng)一個(gè)A的子集S因此，n個(gè)元素的集合的子集個(gè)數(shù)與n位二進(jìn)制的個(gè)數(shù)相同，即|(A)|2n成立。2022/7/21146.2 集合的運(yùn)算及恒等式1.交集的定義ABx|xAxB性質(zhì)AA AAAEAAB BA（AB ） C A（B C）BA可以看出202

6、2/7/21156.2 集合的運(yùn)算及恒等式例：證明 (AB) C A(B C)2022/7/21166.2 集合的基本運(yùn)算及恒等式證：對(duì)任意的元素xx(AB ) C x(AB) xC (x A xB) xC x A (xB xC ) xA x(BC ) xA(B C)由x的任意性，知 (AB ) C A(B C)成立。2022/7/21176.2 集合的基本運(yùn)算及恒等式集合的交運(yùn)算的推廣A1A2Anx|xA1xA2xAn記做：也可推廣到無(wú)窮多個(gè)集合：2022/7/21186.2 集合的基本運(yùn)算及恒等式集合廣義交定義 6.11設(shè)：A=A1,A2,An2022/7/21196.2 集合的基本運(yùn)算及

7、恒等式2.并集的定義ABx|xAxB性質(zhì)AA AAAAEEAB BA(AB) C A(B C)A(B C) (A B ) (A C)A(B C) (A B ) (A C)A(A B) AA(A B) ABA可以看出2022/7/21206.2 集合的基本運(yùn)算及恒等式證明：A (B C) (A B) (A C)證明：對(duì)于任意的x，若由x的任意性知:A (B C) (A B ) (AC)成立2022/7/21216.2 集合的基本運(yùn)算及恒等式集合的并運(yùn)算的推廣A1A2Anx|xA1xA2xAn記做：也可推廣到無(wú)窮多個(gè)集合：2022/7/21226.2 集合的基本運(yùn)算及恒等式集合廣義并定義 6.10

8、設(shè)：A=A1,A2,An2022/7/21236.2 集合的基本運(yùn)算及恒等式3.集合的相對(duì)補(bǔ)（差集）ABx|xAx B性質(zhì)A A A AA BAAB2022/7/21246.2 集合的基本運(yùn)算及恒等式例1：設(shè) A1，2，4 ，5, B3，4，6計(jì)算： AB BA AA AA2022/7/21256.2 集合的基本運(yùn)算及恒等式例2：設(shè)集合A 1 , 2 , 1,2 , , 試計(jì)算： A 1, 2 ; A; A ; 1 ,2 A; A; A答： (1) 1 , 2, (2) A; (3) 1 , 2, 1,2 ； (4) ; (5) ; (6) 2022/7/21266.2 集合的基本運(yùn)算及恒等式

9、思考：下列等式可能成立嗎？若可能，刻畫(huà)等式出現(xiàn)的全部條件。ABAABBABBAAB 答：AB ； AB ；AB；A B2022/7/21276.2 集合的基本運(yùn)算及恒等式4.集合的絕對(duì)補(bǔ)的定義： x|xEx A x|x AA2022/7/21286.2 集合的基本運(yùn)算及恒等式5.對(duì)稱差的定義：AB（AB）（BA）BAAB2022/7/21296.2 集合的基本運(yùn)算及恒等式例設(shè)A1，2，5，B2，4，計(jì)算AB。解：AB 1，5 BA 4 AB1,4,52022/7/21306.2 集合的基本運(yùn)算及恒等式集合的恒等式（集合的算律）（P92）集合運(yùn)算性質(zhì)的重要結(jié)果（P94）證明方法（1）證明P Q方

10、法1： 對(duì)任意的x，x P x Q方法2： 找到一個(gè)集合T，滿足：P T，T Q 則 P Q2022/7/21316.2 集合的基本運(yùn)算及恒等式集合的證明方法2.證明PQ方法1： 對(duì)任意的x，x P x Q方法2：反證法方法3：集合恒等式代入法2022/7/21326.3 有窮集的計(jì)數(shù)1. 設(shè)A，B為任意兩個(gè)有窮集合，則|AB|A | |B|AB| BA2022/7/21336.3 有窮集的計(jì)數(shù)例1：有100名程序員，其中47名熟悉C#語(yǔ)言，35名熟悉JAVA語(yǔ)言，23名熟悉兩種語(yǔ)言。問(wèn)：有多少人對(duì)這兩種語(yǔ)言都不熟悉？解：設(shè)A、B分別表示熟悉C#和JAVA語(yǔ)言的程序員的集合，則法1：根據(jù)容斥原

11、理求解法2：使用文氏圖求解2022/7/21346.3 有窮集的計(jì)數(shù)例2：設(shè)|A|=3，|P(B)|=64， |P(AB)|=256，求|B|，|AB|，|AB|， |AB|。例3：求在1到1000 000之間（含1和1000 000在內(nèi)）有多少個(gè)整數(shù)既不是完全平方數(shù)，也不是完全立方數(shù)?2022/7/21356.3 有窮集的計(jì)數(shù)2.對(duì)于三個(gè)集合，容易看出：|AB C| |A|B| |C| (|AB| |AC| |BC|） |AB C|CBA2022/7/21366.3 有窮集的計(jì)數(shù)例6.5（P89）習(xí)題六2021 （P99）22 （P99）2022/7/21376.3 有窮集的計(jì)數(shù)一般地，對(duì)于

12、n個(gè)有限集合A1,An,有如下結(jié)論：容斥原理所謂容斥(inclusion-exclusion)是指我們計(jì)算某類(lèi)事物的數(shù)目時(shí), 要排斥那些不應(yīng)包含在這個(gè)計(jì)數(shù)中的數(shù)目; 但同時(shí)要包容那些被錯(cuò)誤排斥了的數(shù)目, 以此補(bǔ)償。2022/7/21386.3 有窮集的計(jì)數(shù)例6.4 （P88）設(shè)：E為全集，A、B、C、D分別表示會(huì)英、法、德、日的人的集合，由題設(shè)知：|E|=24|A|=13, |B|=9，|C|=10, |D|=5|AD|=2, |BD|=|CD|=0|AB|= |AC|= |BC|= 4設(shè)同時(shí)會(huì)英、法、德三種語(yǔ)言的有x人，只會(huì)英、法、德語(yǔ)的中一門(mén)語(yǔ)言的分別有y1、 y2、 y3人，于是可以根據(jù)題意畫(huà)出文氏圖2022/7/21396.3 有窮集的計(jì)數(shù)列方程求解解得：x1，y14，y22，y33。 2022/7/21406.3 集合中元素的計(jì)數(shù)例：求1到250之間能被2，3，5和7中任何一個(gè)整除的整數(shù)個(gè)數(shù)。解：設(shè)A1表示1到250之間能被2整除的整數(shù)集合，A2表示1到250之間能被3整除的整數(shù)集合