1、2020/9/21,.,1,第4講 集合恒等式,內(nèi)容提要 1. 集合恒等式與對(duì)偶原理 2. 集合恒等式的證明 3. 集合列的極限 4. 集合論悖論與集合論公理,2020/9/21,.,2,集合恒等式(關(guān)于與),等冪律(idempotent laws) AA=A AA=A 交換律(commutative laws) AB=BA AB=BA,2020/9/21,.,3,集合恒等式(關(guān)于與、續(xù)),結(jié)合律(associative laws) (AB)C=A(BC) (AB)C=A(BC) 分配律(distributive laws) A(BC)=(AB)(AC) A(BC)=(AB)(AC),2020

2、/9/21,.,4,集合恒等式(關(guān)于與 、續(xù)),吸收律(absorption laws) A(AB)=A A(AB)=A,2020/9/21,.,5,集合恒等式(關(guān)于),雙重否定律(double complement law) A=A 德摩根律(DeMorgans laws) (AB)=AB (AB)=AB,2020/9/21,.,6,集合恒等式(關(guān)于與E),零律(dominance laws) AE=E A= 同一律(identity laws) A=A AE=A,2020/9/21,.,7,集合恒等式(關(guān)于,E),排中律(excluded middle) AA = E 矛盾律(contra

3、diction) AA = 全補(bǔ)律 = E E = ,2020/9/21,.,8,集合恒等式(關(guān)于-),補(bǔ)交轉(zhuǎn)換律(difference as intersection) A-B=AB,2020/9/21,.,9,集合恒等式(推廣到集族),分配律 德摩根律,2020/9/21,.,10,對(duì)偶(dual)原理,對(duì)偶式(dual): 一個(gè)集合關(guān)系式, 如果只含有, , E,=, , 那么, 同時(shí)把與互換, 把與E互換, 把與互換, 得到的式子稱為原式的對(duì)偶式. 對(duì)偶原理: 對(duì)偶式同真假. 或者說, 集合恒等式的對(duì)偶式還是恒等式.,2020/9/21,.,11,對(duì)偶原理(舉例),分配律 A (B C

4、) = (A B ) (A C ) A (B C) = (A B ) (A C ) 排中律 A A=E 矛盾律 A A= ,2020/9/21,.,12,對(duì)偶原理(舉例、續(xù)),零律 A E =E A = 同一律 A =A A E=A,2020/9/21,.,13,對(duì)偶原理(舉例、續(xù)),A B A A B A A E A,2020/9/21,.,14,集合恒等式證明(方法),邏輯演算法: 利用邏輯等值式和推理規(guī)則 集合演算法: 利用集合恒等式和已知結(jié)論,2020/9/21,.,15,邏輯演算法(格式),題目: A=B. 證明: x, xA (?) xB A=B. #,題目: AB. 證明: x,

5、 xA (?) xB AB. #,2020/9/21,.,16,分配律(證明),A(BC)=(AB)(AC) 證明: x, xA(BC) xA x(BC) (定義) xA (xB xC) (定義) (xAxB)(xAxC) (命題邏輯分配律) (xAB)(xAC) (定義) x(AB)(AC) (定義) A(BC)=(AB)(AC),2020/9/21,.,17,零律(證明),A = 證明: x, xA xA x (定義) xA 0 (定義) 0 (命題邏輯零律) A = ,2020/9/21,.,18,排中律(證明),AA = E 證明: x, xAA xA xA (定義) xA xA (定

6、義) xA xA (定義) 1 (命題邏輯排中律) AA = E,2020/9/21,.,19,集合演算法(格式),題目: A=B. 證明: A =(?) =B A=B. #,題目: AB. 證明: A (?) B AB. #,2020/9/21,.,20,吸收律(證明),A(AB)=A 證明: A(AB) = (AE)(AB) (同一律) = A(EB) (分配律) = AE (零律) = A (同一律) A(AB)=A,A,B,2020/9/21,.,21,吸收律(證明、續(xù)),A(AB) = A 證明: A(AB) = (AA)(AB) (分配律) = A(AB) (等冪律) = A (吸

7、收律第一式) A(AB) = A,A,B,2020/9/21,.,22,集合演算法(格式,續(xù)),題目: A=B. 證明: () AB () A B A = B. # 說明: 分=成與,題目: AB. 證明: AB (或AB) =(?) = A (或B) AB. # 說明: 化成= AB=AAB AB=BAB,2020/9/21,.,23,集合恒等式證明(舉例),基本集合恒等式 對(duì)稱差()的性質(zhì) 集族(AS)的性質(zhì) 冪集(P( )的性質(zhì),2020/9/21,.,24,補(bǔ)交轉(zhuǎn)換律,A-B = AB 證明: x, xA-B xA xB xA xB x AB A-B = AB. #,2020/9/21

8、,.,25,德摩根律的相對(duì)形式,A-(BC)=(A-B)(A-C) A-(BC)=(A-B)(A-C) 證明: A-(BC) = A(BC) (補(bǔ)交轉(zhuǎn)換律) = A(BC) (德摩根律) = (AA)(BC) (等冪律) = (AB)(AC) (交換律,結(jié)合律) = (A-B)(B-A) (補(bǔ)交轉(zhuǎn)換律). #,2020/9/21,.,26,對(duì)稱差的性質(zhì),交換律: AB=BA 結(jié)合律: A(BC)=(AB)C 分配律: A(BC)=(AB)(AC) A=A, AE=A AA=, AA=E,2020/9/21,.,27,對(duì)稱差的性質(zhì)(證明2),結(jié)合律: A(BC)=(AB)C 證明思路： 分解成

9、“基本單位”, 例如: 1. ABC 2. A BC 3. A B C 4. ABC,A,B,C,ABC,1,2,3,4,2020/9/21,.,28,對(duì)稱差的性質(zhì)(證明2、續(xù)1),結(jié)合律: A(BC)=(AB)C 證明: 首先, AB = (A-B)(B-A) (定義) = (AB)(BA) (補(bǔ)交轉(zhuǎn)換律) = (AB)(AB) (交換律) (*),AB,A,B,2020/9/21,.,29,對(duì)稱差的性質(zhì)(證明2、續(xù)2),其次, A(BC) = (A(BC)(A(BC) (*) = (A(BC)(BC) (A(BC)(BC) (*) = (A(BC)(BC) (A(BC)(BC) (德摩根律

10、),2020/9/21,.,30,對(duì)稱差的性質(zhì)(證明2、續(xù)3),= (A(BC)(BC) (A(BC)(BC) = (A(BC)(BC) (A(BC)(BC) (德摩根律) = (ABC)(ABC) (ABC)(ABC) (分配律),2020/9/21,.,31,對(duì)稱差的性質(zhì)(證明2、續(xù)4),同理, (AB)C = (AB)C)(AB)C) (*) = (AB)(AB)C) (AB)(AB)C) (*) = (AB)(AB)C) (AB)(AB)C) (德摩根律),2020/9/21,.,32,對(duì)稱差的性質(zhì)(證明2、續(xù)5),= (AB)(AB)C) (AB)(AB)C) = (AB)(AB)C

11、) (AB)(AB)C) (德摩根律) = (ABC)(ABC) (ABC)(ABC) (分配律) A(BC)=(AB)C. #,2020/9/21,.,33,對(duì)稱差的性質(zhì)(討論),有些作者用表示對(duì)稱差: AB=AB 消去律: AB=AC B=C (習(xí)題一,23) A=BC B=AC C=AB 對(duì)稱差與補(bǔ): (AB) = AB = AB AB = AB 問題: ABC=ABC ?,2020/9/21,.,34,對(duì)稱差的性質(zhì)(討論、續(xù)),如何把對(duì)稱差推廣到n個(gè)集合: A1A2A3An = ? x, xA1A2A3An x恰好屬于A1,A2,A3,An中的奇數(shù)個(gè) 特征函數(shù)表達(dá): A1A2An(x)

12、 = A1(x)+A2(x)+An(x) (mod 2) = A1(x)A2(x)An(x) (mod 2),都表示模2加法,即相加除以2取余數(shù)),2020/9/21,.,35,特征函數(shù)與集合運(yùn)算:,AB(x) = A(x)B(x) A(x) = 1-A(x) A-B(x) = AB(x)=A(x)(1-B(x) AB(x) = (A-B)B(x) = A(x)+B(x)-A(x)B(x) AB(x) = A(x)+B(x) (mod 2) = A(x)B(x),A,B,2020/9/21,.,36,對(duì)稱差的性質(zhì)(討論、續(xù)),問題: ABC = ABC ? 答案: ABC = (ABC) =

13、(ABC) = ABC ABCD = ABCD = ABCD = (ABCD) = A = (A),2020/9/21,.,37,對(duì)稱差的性質(zhì)(證明3),分配律: A(BC)=(AB)(AC) 證明 A(BC) = A(BC)(BC) = (ABC) (ABC),A,B,C,A(BC),2020/9/21,.,38,對(duì)稱差分配律(證明3、續(xù)),(續(xù)) (AB)(AC) = (AB)(AC)(AB)(AC) =(AB)(AC)(AB)(AC) =(ABC)(ABC) A(BC)=(AB)(AC). #,2020/9/21,.,39,對(duì)稱差分配律(討論),A(BC)=(AB)(AC) A(BC)=

14、(AB)(AC) ? A(BC)=(AB)(AC) ? A(BC)=(AB)(AC) ?,2020/9/21,.,40,集族的性質(zhì),設(shè)A,B為集族, 則 1. AB A B 2. AB A B 3. A AB B A 4. AB B A 5. A A A,2020/9/21,.,41,集族的性質(zhì)(證明1),AB A B 證明: x, xA A(AA xA) (A定義) A(AB xA) (AB) xB (B定義) A B. #,2020/9/21,.,42,集族的性質(zhì)(證明2),AB A B 證明: x, xA AB xA (AB, 合取) A(AB xA) (EG) xB A B. #,20

15、20/9/21,.,43,集族的性質(zhì)(證明3),A AB B A 說明: 若約定=E, 則A的條件可去掉. 證明: x, xB y( yB xy ) y( yA xy ) (AB) xA B A . #,2020/9/21,.,44,集族的性質(zhì)(證明4),AB B A 證明: x, xB y( yB xy ) AB x A (UI) xA (AB) B A . #,2020/9/21,.,45,集族的性質(zhì)(證明5),A A A 說明: A的條件不可去掉! 證明: A y(yA), 設(shè) AA. x, xA y( yA xy ) AA xA xA (AA) AA xA y( yA xy) x A

16、A A . #,2020/9/21,.,46,冪集的性質(zhì),AB P(A)P(B) P(A)P(B) P(AB) P(A)P(B) = P(AB) P(A-B) (P(A)-P(B),2020/9/21,.,47,冪集的性質(zhì)(證明1),AB P(A)P(B) 證明: () x, xP(A) xA xB (AB) xP(B) P(A)P(B),2020/9/21,.,48,冪集的性質(zhì)(證明1、續(xù)),AB P(A)P(B) 證明(續(xù)): () x, xA xP(A) xP(B) (P(A)P(B) xB AB. #,2020/9/21,.,49,冪集的性質(zhì)(證明2),P(A)P(B) P(AB) 證

17、明: x, xP(A)P(B) xP(A)xP(B) xAxB xAB xP(AB) P(A)P(B) P(AB),2020/9/21,.,50,冪集的性質(zhì)(證明2、續(xù)),P(A)P(B) P(AB) 討論: 給出反例, 說明等號(hào)不成立: A=1, B=2, AB=1,2, P(A)=,1, P(B)=,2, P(AB)= ,1,2,1,2 P(A)P(B) ,1,2 此時(shí), P(A)P(B) P(AB). #,2020/9/21,.,51,冪集的性質(zhì)(證明3),P(A)P(B) = P(AB) 證明: x, xP(A)P(B) xP(A) xP(B) xA xB x AB xP(AB) P(

18、A)P(B) = P(AB). #,2020/9/21,.,52,冪集的性質(zhì)(證明4),P(A-B) (P(A)-P(B) 證明: x, 分兩種情況, (1) x=, 這時(shí) xP(A-B) 并且 x(P(A)-P(B) (2) x, 這時(shí) xP(A-B) x A-B xAxB xP(A)xP(B) xP(A)-P(B) P(A-B) (P(A)-P(B). #,A,B,2020/9/21,.,53,集合運(yùn)算的優(yōu)先級(jí),分三級(jí): 第一級(jí)最高, 依次降低 第一級(jí): 補(bǔ), 冪P() 第二級(jí): 廣義并, 廣義交 第三級(jí): 并, 交, 相對(duì)補(bǔ)-, 對(duì)稱差 同一級(jí): 用括號(hào)表示先后順序,2020/9/21,.,54,集合列的極限,2020/9/21,.,5