離散數學之集合論【上】 - 台部落

離散數學之集合論【上】 一、集合基本概念集合(set)：做爲整體識別的、確定的、互相區別的一些對象的總體。

〉 整體識別：不再分割〉 確定：屬於或者 ... 請輸入正確的登錄賬號或密碼 註冊 忘記密碼 首頁 計算數學與數學理論 正文 離散數學之集合論【上】 原創 smilejiasmile 2020-06-2010:27 離散數學之集合論【上】 一、集合基本概念 集合(set)：做爲整體識別的、確定的、互相區別的一些對象的總體。

〉整體識別：不再分割 〉確定：屬於或者不屬於整體 〉互相區別：各異的對象 〉集合的例子 北京大學的全體學生：組成對象是學生全體自然數0，1，2，……：組成對象的是各個自然數。

方程x2+x+1=0的根：如果討論複數，則組成對象是兩個複數如果討論實數，則是一個沒有任何組成對象的集合   成員： 〉組成集合的對象稱爲成員(member)或者元素(element) 元素可以是任何具體或者抽象的事物，元素也可以是集合 〉集合的記號“{,}”。

A={1,2,3}，S={1,{2,3},10}，N={} 〉元素和集合的隸屬關係 當對象a是集合A的成員時，稱a屬於A，記做“a∈A” 當對象a不是集合A的成員時，稱a不屬於A，記做“¬(a∈A)”或者“a∉A 規定集合的方式：列舉法、描述法、歸納法： 〉列舉法：將所有元素列舉  A={1,2,3}   B={a1,a2,…,an} 〉描述法：將集合中元素的特徵用謂詞公式描述    A={x|P(x)}或者A={x:P(x)}，表示x∈A當且僅當P(x) 〉歸納法：後面會專門說明，並且我們已經用歸納法定義了數理邏輯中命題公式、個體項等   例如： 〉{0,1}={x|x=0∨x=1} 〉N={0,1,2,3,…}={x|x是自然數} 〉I+={1,2,3,…}={x|x是正整數} 〉Nn={0,1,2,…,n-1}={x|x∈N∧0≤x＜n}，即前n個自然數集合的集合  ={{0},{0,1},{0,1,2},…}={x|x=Nn∧n∈I+} ={Nn|n∈I+}   空集 沒有任何元素的特定集合稱爲空集，記做ø，ø={}={x|x≠x} 〉有限集(finitesets)    空集和只含有限多個元素的集合稱作有限集。

否則，稱作無限集(infinitesets) 〉基數(cardinality) 有限集合中成員的個數稱作集合的基數（無限集合的基數定義更爲複雜）集合A的基數記做|A|   集合論的三大基本原理 〉外延公理、概括公理、正規公理：規定了集合概念的意義外延公理(extensionalityaxiom)： 兩個集合A和B相等當且僅當它們具有相同的元素。

〉A=B↔∀x(x∈A↔x∈B) 〉{0,1}={1,0}={x|x=0∨x=1} 〉說明集合元素的無序性，以及集合表示形式的不唯一性。

概括公理(comprehensionaxiom) 〉對於任意個體域U，任一謂詞公式P都確定一個以該域中的對象爲元素的集合S。

〉S={x|x∈U∧P(x)} 〉規定了集合成員的確定性 〉對空集來說：P(x)爲永假式 正規公理(regularityaxiom) 〉不存在集合A1,A2,A3,…使得： …∈A3∈A2∈A1 〉直觀來說就是集合的有限可分，個體域的元素是“基本粒子” 〉正規公理確立了元素和集合的不同層次性，集合不能是自己的成員。

〉排除了A={A}這樣的“病態”集合。

而羅素構造悖論便是這種具有自指意向的集合。

子集合 〉集合A稱作集合B的子集合，如果A的每一個元素都是B的元素 〉∀x(x∈A→x∈B) 〉A是B的子集，記做A⊆B 〉集合的兩個基本關係：隸屬和包含 例如： 〉{a,b}⊆ {a,b,c,d} 〉{a,b,c} ⊆ {a,b,c} 〉a⊆{a,b,c}不成立，只有a∈{a,b,c} 〉{a,b}⊆{{a,b},{c,d}}：false 〉{a,b}∈{{a,b},{c,d}}：true 〉有時候隸屬和包含關係會同時成立，如{1}和{1,{1}}之間的關係。

子集合的性質 〉定理1：對於任意集合A和B，A=B當且僅當A⊆B且B⊆A 〉特別的，對於任意集合A，有A⊆A 〉定理2：設A,B,C爲任意集合，若 〉(A⊆B)∧(B⊆C)，則有A⊆C 〉利用邏輯蘊涵式I6：(A→B)∧(B→C)╞A→C來證明 〉定理3：對於任意集合A，A⊆U 〉因爲x∈U是恆真的，所以 ∀x(x∈A→x∈U)也是恆真的 〉定理4：對於任何集合A，ø⊆A 〉因爲x∈ø是恆假的，所以∀x(x∈ø→x∈A)是恆真的 〉定理5：空集是唯一的 〉假設有兩個空集ø1和ø2， 〉根據定理4，有ø1⊆ø2，而且ø2⊆ø1，再根據定理1，ø1=ø2 〉定理6：設A爲一有限集合，|A|=n，那麼A的子集個數爲 〉A的子集有：ø：=1個，只有包含A中1個元素的子集：個，只有包含A中2個元素的子集：個……    包含A中所有元素的子集：A本身，=1個 〉總和：++…+= 個 〉例：{1,2}的子集：ø,{1},{2},{1,2} 真子集(propersubset) 〉如果A⊆B且A≠B，記做：A⊂B 〉空集ø是所有非空集合的真子集 〉判斷題： ø⊆ø，正確，空集是任何集合的子集。

ø∈ø，不對，空集中沒有任何元素。

ø⊆ {ø}，正確 ø∈{ø}，正確 如果A∈B且B∈C，那麼A∈C，不對。

比如 ø∈{ø}，{ø}∈{{ø}}，但 ø不屬於 {{ø}}。

二、集合運算 〉集合運算指以集合作爲運算對象，結果還是集合的運算 〉並運算：∪(union)  定義：A∪B={x|x∈A∨x∈B} ，使用隸屬符號和謂詞聯結詞定義。

〉{1,2}∪{1,3,4}={1,2,3,4} 〉交運算：∩(intersection) 定義：A∩B={x|x∈A∧x∈B} 〉{1,2}∩{2,3}={2} 〉差運算－(difference) 〉定義：A－B={x|x∈A∧x∉B} 〉{1,2,3}－{2,3,4}={1} 〉補運算 ~(complement) 〉定義：A~=U－A={x|x∉A} 〉{0,1,2,3,4}~={5,6,7,…}（U=N） 交和並運算性質 〉A∪A=A；A∩A=A 〉交換律：A∪B=B∪A；A∩B=B∩A 〉結合律：A∪(B∪C)=(A∪B)∪C；A∩(B∩C)=(A∩B)∩C 〉A∪ø=A；A∪U=U；A∩ø=ø；A∩U=A 〉分配律：A∪(B∩C)=(A∪B)∩(A∪C)，A∩(B∪C)=(A∩B)∪(A∩C) 〉A∩(A∪B)=A，A∪(A∩B)=A差和補運算性質 〉A-A=ø，A-ø=A，A-U=ø 〉A-(B∪C)=(A-B)∩(A-C) 〉A-(B∩C)=(A-B)∪(A-C) 〉利用德摩根律得證 〉A~~=A，U~=ø，ø~=U 〉A∪A~=U，A∩A~=ø 〉(A∪B)~=A~∩B~，(A∩B)~=A~∪B~ 〉A-B=A∩B~集合運算和子集關係 〉A⊆A∪B 〉A∩B⊆A 〉A－B⊆A 〉A⊆B╞╡A-B=ø╞╡A∪B=B╞╡A∩B=A 〉如果A⊆B，則有B~⊆A~ 對於任意集合A,B，如果有A∪B=U且A∩B=ø，那麼A=B~ 冪集(powerset)運算 〉對任意集合A，ρ(A)稱作A的冪集，定義爲：ρ(A)={x|x⊆A} 〉A的所有子集作爲元素構成的集合(族) 〉因爲ø⊆A，A⊆A；所以必有ø∈ρ(A)，A∈ρ(A) 〉例：ρ({1,2})={ø,{1},{2},{1,2}} 〉冪集的基數：|ρ(A)|= 冪集的性質 〉設A,B爲任意集合： 〉A⊆B當且僅當ρ(A)⊆ρ(B) 集合族及運算 集合族(collections): 如果集合C中的每個元素都是集合，稱C爲集合族 〉集合族的標誌集(indexset) 如果集合族C可以表示爲某種下標的形式C={|d∈D} 那麼這些下標組成的集合稱作集合族C的標誌集 〉標誌集可以是自然數、某些連續符號集合族和標誌集例子 〉C={{0},{0,1},{0,1,2},…}是集合族，但是沒有標誌集 〉如果定義Nn={0,1,2,…,n-1}，那麼C就可以表示爲{Nn|n∈}，這樣C的標誌集就是 〉集合族C={}={|d∈{a,b,c}}，標誌集就是{a,b,c} 〉A的冪集ρ(A)是一個集合族 集合族的運算 〉廣義並：集合族中所有集合的並集∪C={x|∃S(S∈C∧x∈S)} 〉廣義交：集合族中所有集合的交集  ∩C={x|∀S(S∈C→x∈S)} 〉如果C恰含兩個集合A,B，則∪C=A∪B，∩C=A∩B 〉有標誌集的表示方法：C={|d∈D}，∪C=，∩C= 集合族運算例子 〉C={{0},{0,1},{0,1,2},…}，∪C=N，∩C={0} 〉C={{1},{1,2},{1,3,5}}，∪C={1,2,3,5}，∩C={1}集合族運算性質 〉任意集合A和集合族C，有 〉A∩(∪C)=∪{A∩S:S∈C} 〉A∪(∩C)=∩{A∪S:S∈C} 〉A－(∩C)=∪{A－S:S∈C} 〉A－(∪C)=∩{A－S:S∈C} 〉(∪C)~=∩{S~:S∈C} 〉(∩C)~=∪{S~:S∈C} 〉A－(∪C)=∩{A－S:S∈C} 〉對任意集合A，∪ρ(A)=A 三、歸納定義 〉集合定義的另兩種方式：列舉法、描述法 〉歸納定義 (inductivedefinition)基礎條款：規定某些元素爲待定義集合成員，集合其它元素可以從基本元素出發逐步確定歸納條款：規定由已確定的集合元素去進一步確定其它元素的規則終極條款：規定待定義集合只含有基礎條款和歸納條款所確定的成員 〉基礎條款和歸納條款稱作“完備性條款”，必須保證毫無遺漏產生集合中所有成員 〉終極條款又稱“純粹性條款”，保證集合中僅包含滿足完備性條款的那些對象 歸納定義例子：“聖誕節” 〉基礎條款：耶穌基督降生的那天是聖誕節 〉歸納條款：如果某天是聖誕節，則這一天後的第365天，也是聖誕節（不考慮閏年） 〉終極條款：除了上面兩條所包括的日子，其它日子都不是聖誕節 歸納定義例子：偶數集合 〉個體域U爲自然數集，定義偶數集E 〉基礎條款：0∈E 〉歸納條款：若x∈E，則x+2∈E 〉終極條款：除了有限次使用上述條款確定的元素以外，E中沒有別的元素 歸納定義例子：程序 〉基礎條款：v:=e是程序（其中v是變量，e是算術表達式） 〉歸納條款： 若p1,p2是程序，則p1;p2也是程序； 若p1,p2是程序，則ifcthenp1elsep2endif也是程序（其中c是條件表達式）； 若p是程序，則whilecdopendwhile也是程序； 〉終極條款（略） 注意：上述基礎條款是賦值操作，歸納條款中分別對應了程序的順序結構、選擇結構、和循環結構。

自然數定義 〉數學中“數”是最基本的原始概念，在集合論創立之後，採用集合來定義自然數， 〉使得數學建立在更爲簡單的概念“集合”基礎之上 〉在算術公理化系統中，皮亞諾(Peano)的5大公理刻畫了自然數概念 P1：至少有一個對象是自然數，記做0； P2：如果n是自然數，那麼n必定恰有一個直接後繼，記做n' P3：0不是任何自然數的直接後繼 P4：如果自然數m,n的直接後繼m',n'相同，那麼m=n P5：沒有不滿足上述條件的對象是自然數 利用集合定義自然數 利用集合定義自然數要考慮的幾個問題 〉找一個最簡單的集合作爲0 〉ø 〉找一種集合運算定義“直接後繼” 〉∪?∩？－？ 〉這種集合運算（直接後繼對應的集合運算）不可能得到0對應的那個集合 〉ø 〉可以通過集合關係反應自然數的順序性質（表示序關係） 〉⊆、 自然數集N的歸納定義 〉基礎條款：ø∈N 〉歸納條款：如果x∈N，則x'=x∪{x}∈N 〉終極條款（略） 〉自然數集的列舉定義： {ø,{ø},{ø,{ø}},{ø,{ø},{ø,{ø}}},…}，即實際上有：1={0},2={0,1},3={0,1,2} 〉0∈1∈2∈3…同時也有0∈3 〉還有0⊆1⊆2⊆3…， 1⊆2，4⊆10，10⊆10體現了順序關係，而且子集關係具有傳遞性 如果我們用x'={x}∈N作直接後繼會如何？ 〉{ø,{ø},{{ø}},{{{ø}}},….} 〉0∈1∈2∈3 〉但是沒有1∈3 〉子集關係⊆在自然數之間也不成立 遞歸定義自然數的運算：＋、× 〉加法的定義：x＋0＝x， x＋y'＝(x＋y)' 〉如： 3+2 =(3+1)' =((3+0)')'  =(3')'=4'=5 遞歸定義自然數的運算：＋、× 〉乘法的定義： x×0＝0， x×y'＝(x×y)＋x 〉例子 〉如：3×2＝(3×1)+3=((3×0)+3)+3 =(0+3)+3=(0+2)'+3=((0+1)')'＋3 =(((0+0)')')'+3=((0')')'+3=3+3 =…… =6 歸納原理 〉設集合A是歸納定義的集合 〉要證明A中所有元素具有性質P，即：∀x(x∈A→P(x))，可以進行如下的證明： 〉（歸納基礎）針對歸納定義的基礎條款，證明基礎條款中的所有元素均使P()真 〉（歸納推理）證明歸納條款是“保持性質P的” 〉即在假設歸納條款中已確定元素x使P(x)真的前提下，證明用歸納條款中的操作g所生成的g(x)依然有性質P，即P(g(x))爲真 例如利用歸納原理證明：命題公式中左括號的數量等於右括號的數量 〉命題公式，是由歸納定義所定義的集合 〉設L[A],R[A]分別表示公式A的左括號數量和右括號的數量 〉（歸納基礎）：對於命題變元(或常元)p，L[p]=R[p]=0 〉（歸納推理）：設L[A]=R[A],L[B]=R[B]，那麼： 〉L[(¬A)]=L[A]+1=R[A]+1=R[(¬A)] 〉L[(A→B)]=L[A]+L[B]+1=R[A]+R[B]+1=R[(A→B)] 〉所以對於一切命題公式，左括號數量等於右括號數量 數學歸納法 〉既然自然數集合也是歸納定義的，對於自然數的一些性質，也可以通過歸納原理來證明，即我們通常用的“數學歸納法” 〉第一數學歸納法 〉歸納基礎：證明P(0)爲真 〉歸納過程：對於任意k≥0假設P(k) 爲真時，推出P(k+1)也爲真 〉結論：所有自然數n都使P(n)爲真 數學歸納法例子                數學歸納法的變種 〉起始於任意自然數  的數學歸納法。

證明所有大於等於的自然數都具有性質P 〉起始於多個自然數的數學歸納法歸納基礎：證明P(0),P(1)真歸納過程：對於任意k≥0假設P(k)爲真時， 推出P(k+2)也爲真結論：所有自然數具有性質P 〉允許有參變量的數學歸納法 對於二元謂詞P(m,n)，證明對於一切自然數m,n都爲真，可以視情況只對一個變量進行歸納，另一個變量作爲參數 數學歸納法例子 〉證明：3分幣和5分幣可以組成8分以上任何幣值 〉證明：8=3+5;9=3+3+3;10=5+5 〉假設k可以用3分和5分幣組成， 〉需要證明k+3 時命題真， 〉這是顯然的，只要再加一個3分幣即可 數學歸納法的正確性證明 〉假設我們已經完成下面的推理： 〉歸納基礎：P(0)真； 〉歸納推理：∀k(P(k)→P(k+1)) 〉但是還並非所有自然數都有性質P 〉將這些不滿足性質P的自然數構成一個非空自然數子集，這樣，子集中必定有一個最小的自然數，設爲m 〉顯然m>0，記做n+1，這樣n一定具有性質P，即 P(n)爲真 〉∃n(P(n)∧¬P(n+1))╞╡¬∀k(¬P(k)∨P(k+1))╞╡¬∀k(P(k)→P(k+1)) 〉假設推理結果與已經完成的歸納推理矛盾，所以假設錯誤 〉即數學歸納法成立，所有自然數都有性質P 計算數學與數學理論 集合論 離散數學 發表評論 登录 所有評論 還沒有人評論，想成為第一個評論的人麼?請在上方評論欄輸入並且點擊發布. 相關文章 【離散數學】證明:超人不存在 題目 假如超人能夠並願意防止邪惡，則他將這樣做。

假如超人不能防止邪惡，則他將是無能的;假如超人不願意防止邪惡，則他將是惡意的。

超人沒有防止邪惡。

若超人存在，則他是無能的或惡意的。

證明:超人不存在。

？求上述命題的符號化，並證明。

證 有问题先搜报错~ 2020-07-0418:28:18 實數系統的構造與發展歷程 實數系統的構造與發展歷程 一、第一次數學危機與畢達哥拉斯學派 1、2、3、……，自然數就好像是大自然的母語，它獨立於人的思維而存在，甚至很多動物都會簡單的計數。

考古學有足夠的證據表明，遠遠早於人類文明之前，人們就開始有意識地計數了。

到了古 smilejiasmile 2020-07-0221:58:58 帶路徑壓縮的並查集C/C++模板 拿下面一道入門並查集的題作爲例子 重點在於father數組、getFather函數、union函數 這篇博文的目的是記錄下並查集的模板！   題目背景 若某個家族人員過於龐大，要判斷兩個是否是親戚，確實還很不容易，現在給出某個親戚關係圖， NGU_Jq 2020-07-0810:21:35 matlab實現基於DFS的Ford_Fulkerson最大流最小割算法 function[F,maxf,V,S]=Ford_Fulkerson(C,src,sink) n=size(C,1); F=zeros(n); maxf=0; V=[]; S=[]; whi cjliux 2020-07-0807:47:49 離散數學——自動生成真值表、主合取範式 主要完成真值表的自動生成： 1. 自動生成真值表 2. 生成主合取範式 給出兩個版本，先給一個簡單的，怕大家看完都不想往下看了，簡單版本的，只需要100多行代碼！！！！（好像也不少），但是比第二個版本增加了生成主合取範式的功能，主 Mr.Slin 2020-07-0709:57:29 數據離散程度的指標——標準差 標準差（StandardDeviation） 標準差，在概率統計中最常使用作爲統計分佈程度（statisticaldispersion）上的測量。

反應組內個體間的離散程度。

標準差的計算（Calculationofstand Atom_QQ2022313691 2020-07-0504:34:22 離散數學第一章 爲了感興趣而學。

1.1 主要內容（集合論和圖論）         1.2命題邏輯     定義原子命題，而後原子命題的各種結合，可以滿足某些定理。

就像定義數字以及其運算規則一樣，比如乘法交換律等等啥，不過這裏數字 LeetCoder 2020-07-0401:38:51 離散數學------代數系統部分 代數系統簡介一、二元運算及其性質①、定義②、二元與一元運算的表示③、二元運算的性質④、特異元素：單位元、零元，逆元二、代數系統①、定義②、代數系統的成分與表示③、同類型與同種代數系統三、幾個典型的代數系統①、半羣、獨異點與羣②、 code_Zbw 2020-07-0323:32:05 離散題目18（傳遞閉包） 離散題目18 TimeLimit:1000MSMemoryLimit:65536KB SubmitStatistic ProblemDescription 給出一個集合A和A上的關係R，求關係R的傳遞閉包。

F_Last_Game 2020-07-0307:22:32 離散數學|∅與{∅}出現在離散數學冪集合中 關於這個標題概念的理解上，其實大家都是很清楚的。

只是有的時候吧，很多東西雜糅在一起，我比較容易犯傻，腦子一時短路就忽略了要義 首先必須明確，∅與{∅}是肯定有區別的，至少在離散數學這門課程的學習中； 這樣來理解這兩者的區 zhouie 2020-07-0204:30:47 圖的連通性——通路和迴路 圖的連通性——通路和迴路Abstract1.通路和迴路1.2通路和迴路的概念和定義1.3迴路通路舉例1.4迴路記號簡化2.通路數量2.1通路數量的計算2.2通路計算數學歸納法證明2.3通路數量計算案例2.3.1無 Taosolo 2020-07-0203:00:49 圖論——無向圖的連通性 圖論——無向圖的連通性Abstract1.無向圖連通性定義1.1無向圖可達關係的性質2.點集和割集2.1點割集2.1.1例2.2邊割集3.連通度3.1點連通度和邊連通度例3.2特殊圖的連通度 Abstract 聲 Taosolo 2020-07-0203:00:49 圖論——可達性和最短路徑 可達性和最短路徑Abstract1.可達性的定義1.1可達性判定，只需要求出鄰接矩陣的n-1次冪1.2迴路判定，只需要計算到鄰接矩陣的n次冪2.可達性判定定理2.1可達關係的判定2.1.1例2.1可達性矩陣2.2可 Taosolo 2020-07-0203:00:49 離散數學證明公式整理 先把公式按照自己的方式背下來  然後多練幾題    什麼是前束範式》？？？         ao_mike 2020-07-0111:04:42 離散數學筆記一 第一章命題邏輯的基本概念 1.1命題與聯結詞 （1）命題：第一，命題必須是陳述句，第二，命題必須有唯一真值，即，要麼是真，要麼爲假。

真值爲真的成爲真命題，真值爲假的爲假命題。

（2）簡單（原子）命題：不能分解成更簡單命題的命題成爲原子命 软件猫 2020-07-0104:10:51 S smilejiasmile 24小時熱門文章 最新文章 實數系統的構造與發展歷程 離散結構：圖論與樹 離散結構：圖論進階 基於信息流的安全格模型 圖論問題建模討論彙總 最新評論文章 centos7mysql8安裝和卸載 深切緬懷 2021年年終總結和2022年展望 Java認證考試OCAJP經驗總結 Appbundle打包簽名、安裝調試 5G/NR/LTE學習筆記:事件測量 Python基礎--opencv入門3 presto整體流程及重要概念 WinEdt10.2破解教程【適用於WinEdt10版本及以上】 金盾加密視頻解密金盾2016201820192021加密視頻提取