離散數學思維導圖

大綱：

預備知識1.集合論set表示方法大寫字母表示枚舉法(顯示法)敘述法(隱式法)歸納法遞歸指定集合法文氏圖解法幾個特殊集合空集(絕對唯一）全集(相對唯一）無限集等勢一一對應兩個有限集合等勢當且僅當它們的元素個數相同；可數集合可以和其可數的真子集等勢.可數集合基數(阿列夫0)∈阿列夫1(開區間(0,1)的基數)不可數集合既不是有限集也不是可數集的集合重要定義集合A的元素個數: |A|(基數)集族(Power Set)集合作為元素構成冪集所有不同子集構成⊕：對稱差運算補集相對補集A-B(差集)德摩根律重要題型數理邏輯命題邏輯聯結詞┐否定∧合取∨析取異或“P異或Q”稱為P與Q的不可兼或→蘊涵P稱為蘊涵式的前件，Q稱為蘊涵式的后件若P，則QP僅當Q只要P， 就Q只有Q，才P除非Q，才P除非Q，否則非PP是Q的充分條件P→Q為假當且僅當P為真且Q為假?等價P當且僅當Q優先級：否定→合取→析取→蘊涵→等價命題公式分類永真公式(重言式)滿足式(一定)永假公式(矛盾式)G在解釋Ｉ下是真的:Ｉ滿足G； G在解釋Ｉ下是假的:Ｉ弄假于G.公式G、H等價 ? 公式G?H是永真公式G = H 不是命題公式， G?H是命題公式范式定義命題變元或命題變元的否定稱為文字有限個文字的析取稱為析取式(也稱為子句）有限個文字的合取稱為合取式(也稱為短語）P與┐P稱為互補對包括單個有限個短語的析取式稱為析取范式有限個子句的合取式稱為合取范式主析取范式每一個短語都是極小項必須且只能包含使得公式真值為真的那些解釋對應的極小項主合取范式每一個子句都是極大項必須且只能包含使得公式真值為假的那些解釋對應的極大項求解方法等價式和蘊涵式(Ｇ→Ｈ) = (┐Ｇ∨Ｈ)(Ｇ?Ｈ) = (Ｇ→Ｈ)∧(Ｈ→Ｇ) = (┐Ｇ∨Ｈ)∧(┐Ｈ∨Ｇ)德?摩根定律┐(┐Ｇ) =Ｇ；┐(Ｇ∨Ｈ) =┐Ｇ∧┐Ｈ；┐(Ｇ∧Ｈ) =┐Ｇ∨┐Ｈ。分配定律Ｇ∨(Ｈ∧Ｓ) = (Ｇ∨Ｈ)∧(Ｇ∨Ｓ)Ｇ∧(Ｈ∨Ｓ) = (Ｇ∧Ｈ)∨(Ｇ∧Ｓ)包括單個總結若單個的子句（短語）無 最外層括號，則是合取范式（析取范式）；析取范式、合取范式僅含聯結詞集{┐，∧，∨}；“┐”聯結詞僅出現在命題變元前.推理推論概念反映客觀對象或現象的共同本質屬性的思維形式任何概念都是內涵和外延的統一體。內涵概念的質外延概念的量若H是G1∧G2∧…∧Gn的邏輯結果則efficacious(有效的)Г={G1,G2,…,Gn}H是G的邏輯結果(或稱G蘊涵H當且僅當G→Ｈ為永真公式G為前提PremiseH為結論conclusion判斷方法真值表技術對所有G1,G2,…,Gn都具有真值T的行(表示前提為真的行),如果在每一個這樣的行中，H也具有真值T對所有H具有真值為F的行(表示結論為假的行),如果在每一個這樣的行中，G1,G2,…,Gn中至少有一個公式的真值為F(前提也為假)推理定律演繹法規則P（稱為前提引用規則）規則T（邏輯結果引用規則）規則CP（附加前提規則）反證法謂詞邏輯解決“命題的結構和成分”有關的推理問題基本概念Universal Quantifier全稱量詞Existential Quantifier存在量詞Individual個體詞不能隨意變更順序取值范圍：Individual Field 個體域(或論域)全總個體域(Universal Individual Field)P(x)x：個體詞P：謂詞P(x):命題函數Predicate謂詞0元命題一元某一個個體的某種特性n元n個個體之間的關系項與原子公式項(Term)（1）任意的常量符號或任意的變量符號是項；（2）若f(x1, x2, …, xn)是n 元函數符號，t1,t2,…,tn是項，則f(t1, t2, …, tn)是項；（3）僅由有限次使用(1)，(2)產生的符號串才是項。原子公式(Atomic Formulae)若P(x1,x2,…,xn)是n 元謂詞，t1，t2，…，tn是項，則稱P(t1,t2,…,tn)為原子謂詞公式(Atomic Propositional Formulae)存在：合取 任意：蘊含x : Function Variable作用變量F(x) : Scope轄域自由主題樹定義無向樹連通而不含回路的無向圖簡稱樹(Tree)，常用T表示樹。葉樹中度數為1的結點分支點度數大于1的結點內部結點森林每個連通分支都是樹的無向圖生成樹給定圖G = <V, E>，若G的某個生成子圖是樹樹枝生成樹TG中的邊弦G中不在TG中的邊補TG的所有弦的集合稱為生成樹權T的每個樹枝所賦權值之和最小生成樹G中具有最小權的生成樹有向樹一個有向圖，若略去所有有向邊的方向所得到的無向圖是一棵樹有序樹如果在根樹中規定了每一層上結點的次序k元樹若每個分支點至多有k個兒子k元完全樹若每個分支點都恰有k個兒子k元有序完全樹k元完全樹T是有序的子樹任一結點v及其所有后代導出的子圖T’稱為T的以v為根決策樹有一棵根樹，如果其每個分支點都會提出一個問題，從根開始，每回答一個問題，走相應的邊，最后到達一個葉結點，即獲得一個決策!算法Kruskal算法Prim算法哈夫曼算法定理樹邊數最多的無回路圖邊數最少的連通圖無向圖G = (n, m)中，若m＜n-1，則G是不連通的若m＞n-1，則G必含回路圖論握手定理推論：圖中度數為奇數的結點個數為偶數。同構必要條件（1）結點數目相同； （2）邊數相同； （3）度數相同的結點數相同。邊數最大值連通性連通圖強連通圖G中任何一對結點之間都是相互可達的它的可達性矩陣P的所有元素均為1；單向連通圖若G中任何一對結點之間至少有一個結點到另一個結點是可達的它的可達性矩陣P及其轉置矩陣PT經過布爾并運算后所得的矩陣P’= P∨PT中除主對角元外其余元素均為1(弱)連通圖略去G中所有有向邊的方向得無向圖G’，如果無向圖G’是連通圖它的鄰接矩陣A及其轉置矩陣AT經布爾并運算所得的矩陣A’= A∨AT作為鄰接矩陣而求得的可達性矩陣P’中所有元素均為1。若有向圖G是強連通圖，則它必是單向連通圖；若有向圖G是單向連通圖，則它必是（弱）連通圖。分支應用Floyd算法Dijkstra算法鄰接矩陣與可達性矩陣可達性矩陣二元關系關系的基本概念 有序偶對(序偶)兩個元素x,y按照一定的次序組成的二元組<x,y>其中稱x為<x,y>的第一元素，y為<x,y>的第二元素成對出現、具有一定的順序笛卡爾積(Descartes Product)集合：A×B＝{<x,y>|(x∈A)∧(y∈B)}為集合A與B的笛卡爾積對有限集A,B，有|A×B|=|B×A|=|A|×|B|A×(B∪C)=(A×B)∪(A×C)關系(Relation)稱A×B的任何子集 R 為從A到B的二元關系A＝B，則稱R為A上的二元關系A稱為R的前域，B稱為R的后域當R=Φ時，稱R為空關系(empty relation)；當R=A×B時，則稱R為全關系(Total Relation)xRy<x,y>∈Rx對y有關系R當集合A,B都是有限集時，A×B共有2^(|A|?|B|)個不同的子集，即從A到B的不同關系共有2^(|A|?|B|)個。關系的表示與運算集合表示法（枚舉法和敘述法）關系圖法關系矩陣關系矩陣是0-1矩陣，稱為布爾矩陣R∪S={<x,y>|(xRy)∨(xSy)} (即<x,y>∈R∨<x,y>∈S)復合運算(RoS)oT = Ro(SoT)IAoR = RoIB = R逆運算R-1＝{<b,a>|<a,b>∈R}(RoS)-1 = S-1oR-1冪運算設R是集合A上的關系，則R的n次冪，記為Rn，定義如下：R0＝IA＝{<a,a>|a∈A}；R1＝R；Rn+1＝RnoR＝RoRn關系的性質與閉包 假定其前域和后域相同特殊關系等價關系設R是定義在非空集合A上的關系，如果R是自反的、對稱的、傳遞的，則稱R為A上的等價關系。事實上，對任意正整數n，整數集合Z的任意非空子集A上的關系，R={<x,y>|(x,y∈A)∧(n|(x-y))}，都是等價關系。 同余式上述R稱為Z上以n為模的同余關系(Congruence Relation)，記xRy為x＝y(mod n)等價類商集次序關系擬序關系偏序關系哈斯圖用小圓圈或點表示A中的元素，省掉關系圖中所有的環；（因自反性)對任意x,y∈A，若x＜y，則將x畫在y的下方，可省掉關系圖中所有邊的箭頭；（因反對稱性）對任意x,y∈A，若x＜y，且不存在z∈A，使得x＜z, z＜y，則x與y之間用一條線相連，否則無線相連。（因傳遞性）設<A,≤>是偏序集，B是A的任何一個子集。若存在元素a∈A，使得對任意x∈B，都有x≤a，則稱a為B的上界；對任意x∈B，都有a≤x，則稱a為B的下界；若元素a′∈A是B的上界，元素a∈A是B的任何一個上界，若均有a′≤a，則稱a′為B的最小上界或上確界。記a′= SupB；若元素a'∈A是B的下界，元素a∈A是B的任何一個下界，若均有a≤a′，則稱a′為B的最大下界或下確界。記a′= InfB。全序關系全序關系是偏序關系，反之則不然。良序關系

總結

以上是生活随笔為你收集整理的离散数学思维导图 - 集合论，命题逻辑，谓词逻辑，二元关系，特殊关系，图论，树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。