您當前所在位置:首頁 > PPT課件 > 學校ppt > 數學課件PPT → 離散數學-集合證明PPT

離散數學-集合證明PPT

PPT預覽

離散數學-集合證明PPT

PPT內容

這是離散數學-集合證明PPT下載,主要介紹了集合恒等式;內容提要;對偶原理(舉例);對偶原理(舉例、續);邏輯演算法(格式);分配律(證明);零律(證明);集合演算法(格式);吸收律(證明、續);集合恒等式證明(舉例);補交轉換律;德●摩根律的相對形式;對稱差的性質;集族的性質;集合列的極限;總結作業,歡迎點擊下載哦。

第4講  集合恒等式
內容提要
1.  集合恒等式與對偶原理
2.  集合恒等式的證明
3.  集合列的極限
4.  集合論悖論與集合論公理
集合恒等式(關于與)
等冪律(idempotent laws)
AA=A
AA=A
交換律(commutative laws)
AB=BA
AB=BA
集合恒等式(關于與、續)
結合律(associative laws)
(AB)C=A(BC)
(AB)C=A(BC)
分配律(distributive laws)
A(BC)=(AB)(AC)
A(BC)=(AB)(AC)
集合恒等式(關于與 、續)
吸收律(absorption laws)
A(AB)=A
A(AB)=A
集合恒等式(關于~)
雙重否定律(double complement law)
~~A=A
德●摩根律(DeMorgan’s laws)
~(AB)=~A~B
~(AB)=~A~B
集合恒等式(關于與E)
零律(dominance laws)
AE=E
A=
同一律(identity laws)
A=A
AE=A
集合恒等式(關于,E)
排中律(excluded middle)
A~A = E
矛盾律(contradiction)
A~A = 
全補律
~ = E
~E = 
集合恒等式(關于-)
補交轉換律(difference as intersection)
A-B=A~B
集合恒等式(推廣到集族)
分配律
德●摩根律
對偶(dual)原理
對偶式(dual):  一個集合關系式, 如果只含有, ,~,, E,=, , 那么, 同時把與互換, 把與E互換, 把與互換, 得到的式子稱為原式的對偶式.
對偶原理:  對偶式同真假.  或者說, 集合恒等式的對偶式還是恒等式.
對偶原理(舉例)
分配律
A  (B  C) = (A  B )  (A  C )
A  (B  C) = (A  B )  (A  C )
排中律
A  ~A=E
矛盾律
A  ~A= 
對偶原理(舉例、續)
零律
A  E =E
A   = 
同一律
A   =A
A  E=A
對偶原理(舉例、續)
A  B  A
A  B  A
  A
E   A
集合恒等式證明(方法)
邏輯演算法:
利用邏輯等值式和推理規則
集合演算法:
利用集合恒等式和已知結論
邏輯演算法(格式)
題目: A=B.
證明:   x,
xA
 …     (????)
 xB
 A=B.      #
題目: AB.
證明:   x,
xA
 …     (????)
 xB
 AB.     #
分配律(證明)
A(BC)=(AB)(AC)
證明:    x,   xA(BC)
 xA  x(BC)               (定義)
 xA  (xB  xC)         (定義)
 (xAxB)(xAxC) (命題邏輯分配律)
 (xAB)(xAC)         (定義)
 x(AB)(AC)             (定義)
 A(BC)=(AB)(AC)
零律(證明)
A = 
證明:    x,   xA
 xA  x               (定義)
 xA  0                    (定義)
 0                   (命題邏輯零律)
 A = 
排中律(證明)
A~A = E
證明:    x,   xA~A
 xA  x~A             (定義)
 xA  xA               (~定義)
 xA  xA             (定義)
 1                (命題邏輯排中律)
 A~A = E
集合演算法(格式)
題目: A=B.
證明:  A
=…(????)
=B
 A=B.    #
題目: AB.
證明:   A
 …(????)
 B
 AB.      #
吸收律(證明)
A(AB)=A
證明:    A(AB)
= (AE)(AB)   (同一律)
= A(EB)           (分配律)
= AE                      (零律)
= A                        (同一律)
  A(AB)=A
吸收律(證明、續)
A(AB) = A
證明:      A(AB)
= (AA)(AB)    (分配律)
= A(AB)           (等冪律)
= A              (吸收律第一式)
 A(AB) = A
集合演算法(格式,續)
題目: A=B.
證明:  () …
 AB
() …
 A  B
 A = B.    #
說明: 分=成與
題目: AB.
證明:   AB (或AB)
=…(????)
= A (或B)
 AB.   #
說明: 化成=
AB=AAB
AB=BAB
集合恒等式證明(舉例)
基本集合恒等式
對稱差()的性質
集族({A}S)的性質
冪集(P( ))的性質
補交轉換律
A-B = A~B
證明: x,
xA-B
 xA  xB
 xA  x~B
 x A~B
A-B = A~B.    #
德●摩根律的相對形式
A-(BC)=(A-B)(A-C)
A-(BC)=(A-B)(A-C)
證明: A-(BC)
= A~(BC)              (補交轉換律)
= A(~B~C)            (德●摩根律)
= (AA)(~B~C)     (等冪律)
= (A~B)(A~C)     (交換律,結合律)
= (A-B)(B-A)            (補交轉換律). #
對稱差的性質
交換律: AB=BA
結合律: A(BC)=(AB)C
分配律: A(BC)=(AB)(AC)
A=A,  AE=~A
AA=,  A~A=E
對稱差的性質(證明2)
結合律:  A(BC)=(AB)C
證明思路:   分解成
“基本單位”, 例如:
1.   A~B~C
2.   A  B~C
3.   A  B  C
4. ~A~B~C
對稱差的性質(證明2、續1)
結合律:  A(BC)=(AB)C
證明:   首先,
AB = (A-B)(B-A)           (定義)
= (A~B)(B~A)    (補交轉換律)
= (A~B)(~AB)    (交換律)  (*)
對稱差的性質(證明2、續2)
其次,    A(BC)
= (A~(BC))(~A(BC))         (*)
= (A~((B~C)(~BC)))
(~A((B~C)(~BC)))         (*)
= (A(~(B~C)~(~BC)))
(~A((B~C)(~BC)))   (德•摩根律)
對稱差的性質(證明2、續3)
= (A(~(B~C)~(~BC)))
(~A((B~C)(~BC)))
= (A(~BC)(B~C)))
(~A((B~C)(~BC)))   (德•摩根律)
= (ABC)(A~B~C)
(~AB~C)(~A~BC) (分配律…)
對稱差的性質(證明2、續4)
同理,  (AB)C
= (AB)~C)(~(AB)C)         (*)
= (((A~B)(~AB))~C)
(~((A~B)(~AB))C)         (*)
= (((A~B)(~AB))~C)
((~(A~B)~(~AB))C)   (德•摩根律)
對稱差的性質(證明2、續5)
= (((A~B)(~AB))~C)
((~(A~B)~(~AB))C)
= (((A~B)(~AB))~C)
((~AB)(A~B))C) (德•摩根律)
= (A~B~C)(~AB~C)
(~A~BC)(ABC) (分配律…)
  A(BC)=(AB)C.         #
對稱差的性質(討論)
有些作者用△表示對稱差: AB=A△B
消去律:  AB=AC  B=C (習題一,23)
A=BC  B=AC C=AB
對稱差與補: ~(AB) = ~AB = A~B
AB = ~A~B
問題:  ABC=~A~B~C ?
對稱差的性質(討論、續)
如何把對稱差推廣到n個集合:
A1A2A3…An = ?
x,   xA1A2A3…An
 x恰好屬于A1,A2,A3,…,An中的奇數個
特征函數表達:   A1A2…An(x)
= A1(x)+A2(x)+…+An(x) (mod 2)
= A1(x)A2(x)…An(x)
((mod 2),,都表示模2加法,即相加除以2取余數)
特征函數與集合運算:
AB(x) = A(x)B(x)
~A(x)   = 1-A(x)
A-B(x)  = A~B(x)=A(x)(1-B(x))
AB(x) = (A-B)B(x)
= A(x)+B(x)-A(x)B(x)
AB(x) = A(x)+B(x)  (mod 2)
= A(x)B(x)
對稱差的性質(討論、續)
問題:  ABC =  ~A~B~C ?
答案: ABC = ~(~A~B~C)
= ~(AB~C) = A~B~C
ABCD = ~A~B~C~D
= A~BC~D = ~(~A~BC~D)
=…
A = ~(~A)
對稱差的性質(證明3)
分配律: A(BC)=(AB)(AC)
證明
A(BC)
= A((B~C)(~BC))
= (AB~C) (A~BC)
對稱差分配律(證明3、續)
(續)   (AB)(AC)
= ((AB)~(AC))(~(AB)(AC))
=((AB)(~A~C))((~A~B)(AC))
=(AB~C)(A~BC)
 A(BC)=(AB)(AC).     #
對稱差分配律(討論)
A(BC)=(AB)(AC)  
A(BC)=(AB)(AC)  ?
A(BC)=(AB)(AC)  ?
A(BC)=(AB)(AC)  ?
集族的性質
設A,B為集族, 則
1.               AB  ∪A ∪B
2.               AB      A ∪B
3. A  AB  ∩B  ∩A
4.                AB  ∩B     A
5. A              ∩A  ∪A
集族的性質(證明1)
AB  ∪A ∪B
證明: x,
x∪A
 A(AA  xA)        (∪A定義)
  A(AB  xA)       (AB)
 x∪B                            (∪B定義)
 ∪A ∪B.      #
集族的性質(證明2)
AB  A ∪B
證明: x,
xA
       AB  xA          (AB, 合取)
 A(AB  xA)       (EG)
 x∪B
 A ∪B.         #
集族的性質(證明3)
A  AB  ∩B  ∩A
說明: 若約定∩=E, 則A的條件可去掉.
證明: x,
x∩B   y( yB  xy )
 y( yA  xy )       (AB)
 x∩A
 ∩B ∩A .                #
集族的性質(證明4)
AB  ∩B  A
證明: x,
x∩B   y( yB  xy )
 AB  x A          (UI)
 xA            (AB)
 ∩B A .                #
集族的性質(證明5)
A  ∩A  ∪A
說明:  A的條件不可去掉!
證明:  A  y(yA), 設 AA.
x,   x∩A   y( yA  xy )
 AA  xA  xA          (AA)
 AA  xA   y( yA  xy)
  x ∪A
 ∩A  ∪A .                #
冪集的性質
AB  P(A)P(B)
P(A)P(B)  P(AB)
P(A)P(B) = P(AB)
P(A-B)  (P(A)-P(B)){}
冪集的性質(證明1)
AB  P(A)P(B)
證明:  ()   x,
xP(A)
 xA
 xB        (AB)
 xP(B)
   P(A)P(B)
冪集的性質(證明1、續)
AB  P(A)P(B)
證明(續): ()  x,
xA
 {x}P(A)
 {x}P(B)       (P(A)P(B))
 xB
   AB.      #
冪集的性質(證明2)
P(A)P(B)  P(AB)
證明:    x,
xP(A)P(B)
 xP(A)xP(B)
 xAxB
  xAB
 xP(AB)
 P(A)P(B)  P(AB)
冪集的性質(證明2、續)
P(A)P(B)  P(AB)
討論:  給出反例, 說明等號不成立:
A={1},  B={2},  AB={1,2},
P(A)={,{1}},  P(B)={,{2}},
P(AB)= {,{1},{2},{1,2}}
P(A)P(B)  {,{1},{2}}
此時, P(A)P(B)  P(AB).  #
冪集的性質(證明3)
P(A)P(B) = P(AB)
證明:    x,
xP(A)P(B)
 xP(A)  xP(B)
 xA  xB
 x AB
 xP(AB)
 P(A)P(B) = P(AB).    #
冪集的性質(證明4)
P(A-B)  (P(A)-P(B)){}
證明: x,  分兩種情況,  (1) x=,  這時
xP(A-B) 并且 x(P(A)-P(B)){}
(2) x,  這時
xP(A-B)  x A-B  xAxB
 xP(A)xP(B)  xP(A)-P(B)
 P(A-B)  (P(A)-P(B)){}.      #
集合運算的優先級
分三級:  第一級最高, 依次降低
第一級:  補~, 冪P()
第二級:  廣義并∪, 廣義交∩
第三級:  并, 交, 相對補-, 對稱差
同一級:  用括號表示先后順序
集合列的極限
集合列的極限
Infinite often( i.o.):
Almost everywhere(a.e.)
集合列的極限
上極限:
下極限:
集合列的極限
性質:
集合論悖論
羅素悖論(Russell’s paradox):
S = { x | xx }
SS  ?
SS  SS
SS  SS
集合論公理
外延公理: 所含元素相同的兩個集合是相等的
空集存在公理: 空集合存在
無序對公理: 對任意的a,b,  {a,b}存在
并集公理: 對任意的A, ∪A存在
冪集公理: 對任意的A, P(A)存在
聯集公理:
集合論公理(續)
子集公理:  { xA | P(x) }存在
正則公理: 若S,則
x(xSy(ySxy))
無窮公理: 無窮集存在
替換公理: { f(a) | aA }存在
( f是定義域為A的函數)
集合論公理(續)
選擇公理(Zorn引理, 良序原理): A是元素互不相交的集合,則可以從A的每個元素中恰好選擇一個元素, 構成一個集合
總結
集合恒等式
集合恒等式的證明
集合論悖論
作業(#2)
p27, 習題一, 11, 13, 14, 20
今天1班交作業(#1)
 

相關PPT

《章末復習課》集合與常用邏輯用語PPT:這是《章末復習課》集合與常用邏輯用語PPT下載,主要介紹了提醒探究,集合的并、交、補運算,規律方法,跟蹤訓練,集合關系和運算中的參數問題,歡迎點擊下載哦。
《充分條件與必要條件》集合與常用邏輯用語PPT課件:這是《充分條件與必要條件》集合與常用邏輯用語PPT課件下載,主要介紹了學習目標,自主學習,問題導學,新知初探,1.充分條件與必要條件,自我檢測,講練互動,充分、必要、充要條件的判斷,跟蹤訓練,達標反饋,歡迎點擊下載哦。
《集合的基本運算》集合與常用邏輯用語PPT課件(第2課時補集):這是《集合的基本運算》集合與常用邏輯用語PPT課件(第2課時補集)下載,主要介紹了學習目標,核心素養,自主預習探新知1.全集,2.補集,初試身手,合作探究提素養,規律方法,求集合的補集的方法,當堂達標固雙基,歡迎點擊下載哦。
《離散數學-集合證明PPT》是由用戶T_back撩撥于2018-01-31上傳,屬于數學課件PPT。

標簽:

相關PPT

縮略圖

  • 離散數學-集合證明PPT
丁香五月啪啪中文字幕