離散第6章 第二部分 集合論

1、第二部分 集合論第六章 集合代數(shù)第一節(jié) 集合的基本概念 d A , a A 圖1說明隸屬關(guān)系可以看作是處在不同層次上的集合之間的關(guān)系。規(guī)定：對任何集合A都有AA。第二節(jié) 集合的運(yùn)算舉例設(shè) Aa，b，c，Ba，Cb，d 則有 ABa，b，c，ABa， ABb，c， BA ，BC說明如果兩個(gè)集合的交集為 ，則稱這兩個(gè)集合是不相交的。例如B和C是不相交的。 兩個(gè)集合的并和交運(yùn)算可以推廣成n個(gè)集合的并和交：A1A2Anx|xA1xA2xAnA1A2Anx|xA1xA2xAn可簡記為： A1A2An A1A2An 并和交運(yùn)算還可以推廣到無窮多個(gè)集合的情況： A1A2 A1A2定義6.8 設(shè)A，B為集合，

2、A與B的對稱差集AB定義為： AB(AB)(BA) 例如Aa，b，c，Bb，d，則 ABa，c，d。 對稱差運(yùn)算的另一種定義是 AB(AB)(AB) 可以證明這兩種定義是等價(jià)的。 在給定全集E以后，AE，A的絕對補(bǔ)集A定義如下：定義6.9 AEAx|xExA 因?yàn)镋是全集，xE是真命題，所以A可以定義為 Ax|xA 例如Ea，b，c，d，Aa，b，c，則Ad。 以上集合之間的關(guān)系和運(yùn)算可以用文氏圖(Venn Diagram)給予形象的描述。文氏圖的構(gòu)造方法如下： 文氏圖的構(gòu)造方法如下：畫一個(gè)大矩形表示全集E(有時(shí)為簡單起見可將全集省略)。在矩形內(nèi)畫一些圓(或任何其它的適當(dāng)?shù)拈]曲線)，用圓的內(nèi)部

3、表示集合。不同的圓代表不同的集合。如果沒有關(guān)于集合不交的說明，任何兩個(gè)圓彼此相交。圖中陰影的區(qū)域表示新組成的集合?？梢杂脤?shí)心點(diǎn)代表集合中的元素。 文氏圖的實(shí)例有窮集的計(jì)數(shù)問題使用文氏圖可以很方便地解決有窮集的計(jì)數(shù)問題。首先根據(jù)已知條件把對應(yīng)的文氏圖畫出來。一般地說，每一條性質(zhì)決定一個(gè)集合。有多少條性質(zhì)，就有多少個(gè)集合。如果沒有特殊說明，任何兩個(gè)集合都畫成相交的然后將已知集合的元素?cái)?shù)填入表示該集合的區(qū)域內(nèi)。通常從n個(gè)集合的交集填起，根據(jù)計(jì)算的結(jié)果將數(shù)字逐步填入所有的空白區(qū)域。如果交集的數(shù)字是未知的，可以設(shè)為x。根據(jù)題目中的條件，列出一次方程或方程組，就可以求得所需要的結(jié)果。 例6.2 對24名會(huì)

4、外語的科技人員進(jìn)行掌握外語情況的調(diào)查。其統(tǒng)計(jì)結(jié)果如下：會(huì)英、日、德和法語的人分別為13，5，10和9人，其中同時(shí)會(huì)英語和日語的有2人，會(huì)英、德和法語中任兩種語言的都是4人。已知會(huì)日語的人既不懂法語也不懂德語，分別求只會(huì)一種語言(英、德、法、日)的人數(shù)和會(huì)三種語言的人數(shù)。 解：令A(yù)，B，C，D分別表示會(huì)英、法、德、日語的人的集合。根據(jù)題意畫出文氏圖。設(shè)同時(shí)會(huì)三種語言的有x人，只會(huì)英、法或德語一種語言的分別為y1，y2和y3人。將x和y1，y2，y3填入圖中相應(yīng)的區(qū)域，然后依次填入其它區(qū)域的人數(shù)。 例6.24-x4-x4-xxy2y1y325-2英 13法 9德 10日 5y1+2(4-x)+x+

5、213y2+2(4-x)+x9y3+2(4-x)+x10y1+y2+y3+3(4-x)+x24-533第三節(jié) 集合恒等式下面的恒等式給出了集合運(yùn)算的主要算律，其中A，B，C代表任意集合。冪等律 AAA (6.1) AAA (6.2)結(jié)合律 (AB)CA(BC) (6.3) (AB)CA(BC) (6.4)交換律 ABBA (6.5) ABBA (6.6)分配律 A(BC)(AB)(AC) (6.7) A(BC)(AB)(AC) (6.8)同一律 AA (6.9) AEA (6.10) 零律 AEE (6.11) A (6.12)排中律 AAE (6.13)矛盾律 AA (6.14)吸收律 A(

6、AB)A (6.15) A(AB)A (6.16)德摩根律 A(BC)(AB)(AC)(6.17) A(BC)(AB)(AC)(6.18)(BC)BC (6.19) (BC)BC (6.20)E (6.21)E (6.22)雙重否定律 (A)A (6.23)集合運(yùn)算性質(zhì)的一些重要結(jié)果ABA，ABB(6.24)AAB，BAB(6.25)ABA(6.26)ABAB (6.27)ABB AB ABA AB (6.28) ABBA (6.29)(AB)CA(BC) (6.30)AA (6.31)AA (6.32)ABAC BC (6.33)集合恒等式的證明方法邏輯演算法利用邏輯等值式和推理規(guī)則集合演算

7、法利用集合恒等式和已知結(jié)論邏輯演算法的格式題目：AB證明： x， xA xB所以 AB或證 PQ QP 題目：AB證明： x， xA xB所以 AB集合演算法的格式題目：AB證明： A B所以 AB題目：AB證明：A B所以 AB例6.6 證明式6.17，即 A(BC)(AB)( AC) 證明: 對任意的x，有xA(BC)xA xBCxA (xBxC) xA (xBxC) xA (xB xC) (xAxB) (xAxC) xAB xAC x(AB)(AC)所以 A(BC)(AB)( AC)例6.7 證明式6.10，即 AEA證明 對任意的x，有xAExA xExA (因?yàn)閤E是恒真命題)所以 AEA例6.8 假設(shè)已知等式6.16.14，試證等式6.15，即 A(AB)A。證明 A(AB) (AE)(AB) (由等式6.10)A(EB) (由等式6.8)A(BE) (由等式6.5)AE (由等式6.11)A (由等式6.10)例6.9 證明等式6.27，即 ABAB證明 對于任意的x，有xAB xA