1、離散數學 集合第1頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講2集合恒等式(關于與)等冪律(idempotent laws)AA=AAA=A交換律(commutative laws)AB=BAAB=BA第2頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講3集合恒等式(關于與、續)結合律(associative laws)(AB)C=A(BC) (AB)C=A(BC) 分配律(distributive laws)A(BC)=(AB)(AC)A(BC)=(AB)(AC)第3頁，共62頁，2022年，5月20

2、日，11點8分，星期五2022/9/25集合論與圖論第4講4集合恒等式(關于與 、續)吸收律(absorption laws)A(AB)=AA(AB)=A第4頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講5集合恒等式(關于)雙重否定律(double complement law)A=A德摩根律(DeMorgans laws)(AB)=AB(AB)=AB第5頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講6集合恒等式(關于與E)零律(dominance laws)AE=EA=同一律(identity law

3、s)A=AAE=A第6頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講7集合恒等式(關于,E)排中律(excluded middle)AA = E矛盾律(contradiction)AA = 全補律 = EE = 第7頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講8集合恒等式(關于-)補交轉換律(difference as intersection)A-B=AB第8頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講9集合恒等式(推廣到集族)分配律德摩根律第9頁，共

4、62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講10對偶(dual)原理對偶式(dual): 一個集合關系式, 如果只含有, , E,=, , 那么, 同時把與互換, 把與E互換, 把與互換, 得到的式子稱為原式的對偶式. 對偶原理: 對偶式同真假. 或者說, 集合恒等式的對偶式還是恒等式.第10頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講11對偶原理(舉例)分配律A (B C) = (A B ) (A C )A (B C) = (A B ) (A C )排中律A A=E矛盾律A A= 第11頁，共62頁，2

5、022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講12對偶原理(舉例、續)零律A E =EA = 同一律A =AA E=A第12頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講13對偶原理(舉例、續) A B AA B A AE A第13頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講14集合恒等式證明(方法)邏輯演算法: 利用邏輯等值式和推理規則集合演算法: 利用集合恒等式和已知結論第14頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講

6、15邏輯演算法(格式)題目: A=B. 證明: x, xA (?) xB A=B. #題目: AB. 證明: x, xA (?) xB AB. #第15頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講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)第16頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論

7、與圖論第4講17零律(證明)A = 證明: x, xA xA x (定義) xA 0 (定義) 0 (命題邏輯零律) A = 第17頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講18排中律(證明)AA = E證明: x, xAA xA xA (定義) xA xA (定義) xA xA (定義) 1 (命題邏輯排中律) AA = E第18頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講19集合演算法(格式)題目: A=B. 證明: A =(?) =B A=B. #題目: AB. 證明: A (?) B AB

8、. #第19頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講20吸收律(證明)A(AB)=A證明: A(AB) = (AE)(AB) (同一律) = A(EB) (分配律) = AE (零律) = A (同一律) A(AB)=AAB第20頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講21吸收律(證明、續)A(AB) = A證明: A(AB) = (AA)(AB) (分配律) = A(AB) (等冪律) = A (吸收律第一式) A(AB) = AAB第21頁，共62頁，2022年，5月20日，11點8分，

9、星期五2022/9/25集合論與圖論第4講22集合演算法(格式,續)題目: A=B. 證明: () AB () A B A = B. #說明: 分=成與題目: AB. 證明: AB (或AB) =(?) = A (或B) AB. #說明: 化成=AB=AABAB=BAB 第22頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講23集合恒等式證明(舉例)基本集合恒等式對稱差()的性質集族(AS)的性質冪集(P( )的性質第23頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講24補交轉換律A-B = AB證明:

10、x, xA-B xA xB xA xB xABA-B = AB. #第24頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講25德摩根律的相對形式A-(BC)=(A-B)(A-C)A-(BC)=(A-B)(A-C)證明: A-(BC) = A(BC) (補交轉換律) = A(BC) (德摩根律) = (AA)(BC) (等冪律) = (AB)(AC) (交換律,結合律)= (A-B)(A-C) (補交轉換律). #第25頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講26對稱差的性質交換律: AB=BA結合律

11、: A(BC)=(AB)C分配律: A(BC)=(AB)(AC)A=A, AE=AAA=, AA=E第26頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講27對稱差的性質(證明2)結合律: A(BC)=(AB)C證明思路： 分解成 “基本單位”, 例如: 1. ABC 2. A BC 3. A B C 4. ABCABCABC1234第27頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講28對稱差的性質(證明2、續1)結合律: A(BC)=(AB)C證明: 首先, AB = (A-B)(B-A) (定義)

12、= (AB)(BA) (補交轉換律) = (AB)(AB) (交換律) (*)ABAB第28頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講29對稱差的性質(證明2、續2) 其次, A(BC) = (A(BC)(A(BC) (*) = (A(BC)(BC) (A(BC)(BC) (*) = (A(BC)(BC) (A(BC)(BC) (德摩根律)第29頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講30對稱差的性質(證明2、續3) = (A(BC)(BC) (A(BC)(BC) = (A(BC)(BC) (

13、A(BC)(BC) (德摩根律) = (ABC)(ABC) (ABC)(ABC) (分配律)第30頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講31對稱差的性質(證明2、續4) 同理, (AB)C = (AB)C)(AB)C) (*) = (AB)(AB)C) (AB)(AB)C) (*) = (AB)(AB)C) (AB)(AB)C) (德摩根律)第31頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講32對稱差的性質(證明2、續5) = (AB)(AB)C) (AB)(AB)C) = (AB)(AB)C

14、) (AB)(AB)C) (德摩根律) = (ABC)(ABC) (ABC)(ABC) (分配律) A(BC)=(AB)C. #第32頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講33對稱差的性質(作業）有些作者用表示對稱差: AB=AB 消去律: AB=AC B=C A=BC B=AC C=AB對稱差與補: (AB) = AB = AB AB = AB問題: ABC=ABC ?第33頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講34對稱差的性質(作業續)如何把對稱差推廣到n個集合: A1A2A3An

15、= ? x, xA1A2A3An x恰好屬于A1,A2,A3,An中的奇數個特征函數表達: A1A2An(x) = A1(x)+A2(x)+An(x) (mod 2) = A1(x)A2(x)An(x) (mod 2),都表示模2加法,即相加除以2取余數)第34頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講35特征函數與集合運算: 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)

16、 (mod 2) = A(x)B(x)AB第35頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講36對稱差的性質(討論、續)問題: ABC = ABC ? 答案: ABC = (ABC) = (ABC) = ABC ABCD = ABCD = ABCD = (ABCD) =A = (A)第36頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講37對稱差的性質(證明3)分配律: A(BC)=(AB)(AC)證明 A(BC) = A(BC)(BC) = (ABC) (ABC)ABCA(BC)第37頁，共62頁，2

17、022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講38對稱差分配律(證明3、續)(續) (AB)(AC) = (AB)(AC)(AB)(AC) =(AB)(AC)(AB)(AC) =(ABC)(ABC) A(BC)=(AB)(AC). #第38頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講39對稱差分配律(討論)A(BC)=(AB)(AC) A(BC)=(AB)(AC) ?A(BC)=(AB)(AC) ?A(BC)=(AB)(AC) ?第39頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與

18、圖論第4講40集族的性質設A,B為集族, 則1. AB A B2. AB A B 3. A AB B A4. AB B A5. A A A第40頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講41集族的性質(證明1)AB A B證明: x, xA A(AA xA) (A定義) A(AB xA) (AB) xB (B定義) A B. #第41頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講42集族的性質(證明2)AB A B 證明: x, xA AB xA (AB, 合取) A(AB xA) (EG) xB

19、A B. #第42頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講43集族的性質(證明3)A AB B A說明: 若約定=E, 則A的條件可去掉.證明: x, xB y( yB xy ) y( yA xy ) (AB) xA B A . #第43頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講44集族的性質(證明4)AB B A證明: x, xB y( yB xy ) AB x A (UI) xA (AB) B A . #第44頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論

20、與圖論第4講45集族的性質(證明5)A A A說明: A的條件不可去掉!證明: A y(yA), 設 AA. x, xA y( yA xy ) AA xA xA (AA) AA xA y( yA xy) x A A A . #第45頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講46冪集的性質AB P(A)P(B)P(A)P(B) P(AB)P(A)P(B) = P(AB)P(A-B) (P(A)-P(B)第46頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講47冪集的性質(證明1)AB P(A)P(B)證

21、明: () x, xP(A) xA xB (AB) xP(B) P(A)P(B)第47頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講48冪集的性質(證明1、續)AB P(A)P(B)證明(續): () x, xA xP(A) xP(B) (P(A)P(B) xB AB. #第48頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講49冪集的性質(證明2)P(A)P(B) P(AB)證明: x, xP(A)P(B) xP(A)xP(B) xAxB xAB xP(AB) P(A)P(B) P(AB)第49頁，共6

22、2頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講50冪集的性質(證明2、續)P(A)P(B) P(AB)討論: 給出反例, 說明等號不成立: 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 此時, P(A)P(B) P(AB). #第50頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講51冪集的性質(證明3)P(A)P(B) = P(AB)證明: x, xP(A)P(B) xP(A) xP(B) xA xB x AB xP(AB)

23、P(A)P(B) = P(AB). #第51頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講52冪集的性質(證明4)P(A-B) (P(A)-P(B)證明: x, 分兩種情況, (1) x=, 這時 xP(A-B) 并且 x(P(A)-P(B) (2) x, 這時 xP(A-B) x A-B xAxB xP(A)xP(B) xP(A)-P(B) P(A-B) (P(A)-P(B). #AB第52頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講53集合運算的優先級分三級: 第一級最高, 依次降低第一級: 補, 冪P()第二級: 廣義并, 廣義交第三級: 并, 交, 相對補-, 對稱差同一級: 用括號表示先后順序第53頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講54集合列的極限A1A2A3A4A5E第54頁，共62頁，2022年，5月20日，11點8分，星期五2022/9/25集合論與圖論第4講55集合列的極限Infinite often( i.o.):無窮多次Almost everywhere(a.e.):幾乎處處第5