離散數(shù)學知識匯總.doc

《離散數(shù)學知識匯總.doc》由會員分享，可在線閱讀，更多相關《離散數(shù)學知識匯總.doc（14頁珍藏版）》請在裝配圖網(wǎng)上搜索。

離散數(shù)學筆記 第一章 命題邏輯 合取 析取 定義 1. 1.3 否定：當某個命題為真時，其否定為假，當某個命題為假時，其否定為真 定義 1. 1.4 條件聯(lián)結詞，表示“如果… …那么……”形式的語句 定義 1. 1.5 雙條件聯(lián)結詞，表示“當且僅當”形式的語句 定義 1.2.1 合式公式 (1)單個命題變元、命題常元為合式公式，稱為原子公式。 (2)若某個字符串 A 是合式公式，則A、(A)也是合式公式。 (3)若 A、B 是合式公式，則 A B、AB、A B、AB 是合式公式。 (4)有限次使用(2)~(3)形成的字符串均為合式公式。 1.3等值式 1.4析取范式與合取范式 將一個普通公式轉換為范式的基本步驟 1.6推理 定義 1.6.1 設 A 與 C 是兩個命題公式， 若 A → C 為永真式、 重言式，則稱 C 是 A 的有 效結論，或稱 A 可以邏輯推出 C，記為 A => C。（用等值演算或真值表） 第二章 謂詞邏輯 2.1、基本概念 ?：全稱量詞 ?：存在量詞 一般情況下， 如果個體變元的取值范圍不做任何限制即為全總個體域時， 帶 “全稱量詞”的謂詞公式形如"?x(H(x)→B(x))，即量詞的后面為條件式，帶“存在量詞”的謂詞公式形如?x(H(x)∨WL(x))，即量詞的后面為合取式 例題 R(x)表示對象 x 是兔子，T(x)表示對象 x 是烏龜， H(x,y)表示 x 比 y 跑得快，L(x,y)表示x 與 y 一樣快，則兔子比烏龜跑得快表示為： ?x?y(R(x)∧T(y)→H(x,y)) 有的兔子比所有的烏龜跑得快表示為：?x?y(R(x)∧T(y)→H(x,y)) 2.2、謂詞公式及其解釋 定義 2.2.1、 非邏輯符號： 個體常元(如 a,b,c)、 函數(shù)常元(如表示的 f(x,y))、 謂詞常元(如表示人類的 H(x))。 定義 2.2.2、邏輯符號：個體變元、量詞(??)、聯(lián)結詞(﹁∨∧→?)、逗號、括號。 定義 2.2.3、項的定義：個體常元、變元及其函數(shù)式的表達式稱為項(item)。 定義 2.2.4、原子公式：設 R()是 n 元謂詞，是項，則 R(t)是原子公式。原子公式中的個體變元，可以換成個體變元的表達式(項)，但不能出現(xiàn)任何聯(lián)結詞與量詞，只能為單個的謂詞公式。 定義 2.2.5 合式公式：(1)原子公式是合式公式；(2)若 A 是合式公式，則(﹁A)也是合式公式；(3)若 A,B 合式，則 A∨B, A∧B, A→B , A?B 合式(4)若 A 合式，則?xA、?xA 合式(5)有限次使用(2)~(4)得到的式子是合式。 定義 2.2.6 量詞轄域：?xA 和?xA 中的量詞?x/?x 的作用范圍，A 就是作用范圍。 定義 2.2.7 約束變元：在?x 和?x 的轄域 A 中出現(xiàn)的個體變元 x，稱為約束變元，這是與量詞相關的變元，約束變元的所有出現(xiàn)都稱為約束出現(xiàn)。 定義 2.2.8 自由變元：謂詞公式中與任何量詞都無關的量詞，稱為自由變元，它的每次出現(xiàn)稱為自由出現(xiàn)。一個公式的個體變元不是約束變元，就是自由變元。 注意：為了避免約束變元和自由變元同名出現(xiàn)，一般要對“約束變元”改名，而不對自由變元改名。 定義 2.2.9 閉公式是指不含自由變元的謂詞公式 從本例(已省)可知， 不同的公式在同一個解釋下， 其真值可能存在， 也可能不存在， 但是對于沒有自由變元的公式(閉公式)，不論做何種解釋，其真值肯定存在 謂詞公式的類型：重言式(永真式)、矛盾式(永假式)、可滿足公式三種類型 定義 2.2.10 在任何解釋下，公式的真值總存在并為真，則為重言式或永真式。 定義 2.2.11 在任何解釋下，公式的真值總存在并為假，則為矛盾式或永假式。 定義 2.2.12 存在個體域并存在一個解釋使得公式的真值存在并為真，則為可滿足式。 定義 2.2.13 代換實例 設 是命題公式 中的命題變元， 是 n 個謂 詞公式，用代替公式 中的后得到公式 A，則稱 A 為 的代換實例。 如 A(x)∨﹁A(x)，?xA(x) ∨﹁? xA(x)可看成 p ∨﹁ p 的代換實例，A(x) ∧﹁A(x)，?xA(x) ∧﹁ ?x A(x)可看成 p ∧﹁ p 的代換實例。 定理 2.2.1 命題邏輯的永真公式之代換實例是謂詞邏輯的永真公式， 命題邏輯的永假公式之代換實例是謂詞邏輯的永假式。（代換前后是同類型的公式） 2.3、謂詞公式的等值演算 定義 2.3.1 設 A、B 是兩個合法的謂詞公式，如果在任何解釋下，這兩個公式的真值都相等，則稱 A 與 B 等值，記為 A ó B。 當 AóB 時，根據(jù)定義可知，在任何解釋下，公式 A 與公式 B 的真值都相同，故 A?B 為永真式，故得到如下的定義。 定義 2.3.2 設 A、B 是兩個合法謂詞公式，如果在任何解釋下， A? B 為永真式， 則 A與 B 等值，記為 A ó B。 一、利用代換實例可證明的等值式(p?﹁﹁p 永真，代換實例? xF(x) ?﹁﹁? xF(x)永真) 二、個體域有限時，帶全稱量詞、存在量詞公式的等值式 如：若D={ }，則? xA(x) ó A()∧A()∧…∧A() 三、量詞的德摩律 1、﹁?xA(x) ó ?x﹁A(x) 2、﹁?xA(x) ó ?x﹁A(x) 四、量詞分配律 1、?x(A(x)∧B(x)) ó ?xA(x)∧?xB(x) 2、?x(A(x)∨B(x)) ó ?xA(x)∨?xB(x) 記憶方法：?與∧，一個尖角朝下、一個尖角朝上，相反可才分配。2 式可看成 1 式的對偶式 五、量詞作用域的收縮與擴張律 A(x)含自由出現(xiàn)的個體變元 x，B 不含有自由出現(xiàn)的 x，則有： 1、?/?(A(x)∨B) ó ?/?A(x)∨B 2、?/?(A(x)∧B) ó ?/?A(x)∧B 對于條件式 A(x) ?B， 利用 “基本等值一” 將其轉換為析取式， 再使用德摩律進行演算 六、置換規(guī)則 若 B 是公式 A 的子公式，且B ó C，將 B 在 A 中的每次出現(xiàn)，都換成 C 得到的公式記為 D，則 A óD 七、約束變元改名規(guī)則 將公式 A 中某量詞的指導變元及轄域中約束變元每次約束出現(xiàn)，全部換成公式中未出現(xiàn)的字母，所得到的公式記為 B，則 A ó B 例 證明步驟： 2.4、謂詞公式的范式 從定理證明過程，可得到獲取前束范式的步驟： (1)剔除不起作用的量詞； (2)如果約束變元與自由變元同名，則約束變元改名； (3)如果后面的約束變元與前面的約束變元同名，則后的約束變元改名； (4)利用代換實例，將→、?轉換﹁∨∧表示； (5)利用德摩律，將否定﹁深入到原子公式或命題的前面； (6)利用量詞轄域的擴張與收縮規(guī)律或利用量詞的分配律，將量詞移到最左邊 2.5、謂詞推理 定義 2.5.1 若在各種解釋下 只能為真即為永真，則稱為前提可推出結論 B。 定義 2.5.2 在所有使 為真的解釋下，B 為真，則稱為前提 可推出結論 B。 謂詞邏輯的推理方法分為以下幾類： 一、 謂詞邏輯的等值演算原則、 規(guī)律： 代換實例、 量詞的德摩律、 量詞的分配律、 量詞 轄域的擴張與收縮、約束變元改名。 二、 命題邏輯的推理規(guī)則的代換實例， 如假言推理規(guī)則、 傳遞律、 合取與析取的性質(zhì)律、 CP 規(guī)則、反證法等。 三、謂詞邏輯的推理公理 第三章 集合與關系 3.1、基本概念 在離散數(shù)學稱 “不產(chǎn)生歧義的對象的匯集一塊” 便構成集合。常用大寫字母表示集合， 如 R 表示實數(shù)， N 表示自然數(shù)， Z 表示整數(shù)， Q 表示有理數(shù)，C 表示復數(shù)。描述一個集合一般有 “枚舉法” 與 “描述法” ， “枚舉法”。元素與集合之間有“屬于”或“不屬于”二種關系。 定義 3.1.1 設 A，B 是兩個集合，如果 A 中的任何元素都是 B 中的元素，則稱 A 是 B 的子集，也稱 B 包含于 A，記為 BA，也稱 A 包含 B，記為 AB。 3.2集合運算性質(zhì) 定義 3.2.1 設 A、B 為集合，A 與 B 的并集 AB、A 與 B 的的交集 AB、A-B 的定 義：AB={x|xAxB}，AB={x|xAxB}，A-B={x|xAxB} 定 義 3.2.2 設 A、 B 為 集 合 ， A 與 B 的 對 稱 差 ， 記 為 AB={x|(xAxB)( x AxB)}= AB - AB。 定義 3.2.3 設 A、B 是兩個集合，若 AB、BA 則 A=B，即兩個集合相等。 冪等律 AA=A、AA=A 結合律 ABC= A(BC)= (AB)C ABC= A(BC)= (AB)C 交換律 AB=BA、AB=BA 分配律 A(BC)=(AB)(AC) A(BC)=(AB)(AC) 同一/零律 A? = A、A?= ? 排中/矛盾律 AA=E、AA= ? 吸收律(大吃小) A(BA)=A、 A(BA)=A 德摩律 (AB)= A B 、 (AB)= AB 雙重否定 A=A 3.3、有窮集的計數(shù) 定理 3.3.1 二個集合的包含排斥原理 | | = || + || - || 3.4、序偶 定義 3.4.2 令與是二個序偶，如果 x=u、y=v，那么=即二個序偶相等。 定義 3.4.3 如果是序偶，且<,z>也是一個序偶，則稱為三元組。 3.5、直積或笛卡爾積 定義 3.5.1 令 A、B 是兩個集合， 稱序偶的集合{|xA, yB}為A與B的直積或笛卡爾積，記為 AB。 如：A={1,2,3}，B={a,b,c}則AB={1,2,3}{a,b,c}={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>} 直積的性質(zhì) 1、A(BC)= A B A C 2、A (BC)= A B A C 3、(B C) A = B A C A 4、(B C) A = B A C A 5、ABóA C B C ó C A C B 6、AB,CDóA C B D 定義 3.5.2 令 是 n 個集合，稱n元組的集合{<>| }，為的直積或笛卡爾積，記為。 3.6、關系 定義 3.6.1 稱直積中部分感興趣的序偶所組成的集合為“關系” ，記為 R。 如在直積{1,2,3,4,5,6,7,8}{1,2,3,4,5,6,7,8}中， 只對第 1 個元素是第 2 個元素的因數(shù)的序偶感興趣，即只對R={<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>, <1,7>,<1,8>, <2,2>,<2,4>, <2,6>, <2,8>, <3,3>,<3,6>,<4,4>,<4,8>,<5,5>, <6,6>,<7,7>,<8,8>}，RAA（A={1,2,3,4,5,6,7,8}） 定義 3.6.2 如果序偶或元組屬于某個關系 R，則稱序偶或元組具有關系 R。 關系圖，關系矩陣 3.7、關系的復合 定義 3.7.1 若關系 FAA，關系 GAA，稱集合{|t 使得F，G} 為 F 與 G 的復合，記為 FG。 例題 3.7.1 令 A={1,2,3}，F(xiàn)={<1,1>,<1,2>} G={<2,2>,<1,3>,<1,1>}則 解： FG={ <1,3>,<1,1>,<1,2>} ，GF={<1,2>,<1,1>}， 因此關系的復合不滿足交換律。 采用復合的定義去計算，只適合于人工計算，為了編程實現(xiàn)，故采用矩陣表示關系。 說明：的第 i 行與的第 j 列相乘時，乘法是合取，加法是析取，如 MF 的 1 行與 MG 的第 3 列相乘是：(11)(10)(00)，結果為 1。 定義 3.7.2 若關系 FAA，稱集合{|F }為 F 的逆，記為 例題 3.7.2 令 A={1,2,3}，F(xiàn)={<1,2>,<1,3>,<2,1>}，則={ <2,1>,<3,1>,<1,2>}。 3.8、關系的分類 定義 3.8.1 若都有R，則R是自反關系。(自己到自己的關系全屬于R) 定義 3.8.2 若都有R,則 R 是反自反的。(自己到自己的關系全不屬于R) 定義 3.8.4 如果所有形如的序偶都在關系 R 中， R 也只有這種形式的序偶， 則稱 R為恒等關系，記為。 對于恒等關系而言，其關系矩陣是單位矩陣，即其主對角線全是 1，其他位置全是 0，對關系圖是每個點都有自旋，僅只有自旋，沒有其他邊。 定義 3.8.5 令關系RAA，如果當R 時R，則稱 R 為對稱關系。 定義 3.8.6 令關系RAA，如果當R 且xy時R， 則稱 R 為反對稱關系。 定義 3.8.8 令關系RAA，若當R,R時有R，則稱R為可傳遞關系。 從RR 的關系矩陣可知，其非0元素在R的關系矩陣都出現(xiàn)，即，凡滿足這個不等式的關系，肯定為可傳遞關系。 所以不可傳遞。 從RR的關系矩陣可知，其非0元素出現(xiàn)在(1,1)，(1,3)，(2,2)，(2,4)，在 R 的關系矩 陣都沒出現(xiàn)，不滿足，不可傳遞關系。 3.9、關系的閉包 將關系矩陣的主角線上全部變成 1， 即得到其自反閉包的關系矩陣， 從而可得到其自反閉包。 3.10、等價關系與集合的劃分 定義 3.10.1 設R AA，如果 R 是自反、對稱、可傳遞的關系則稱為等價關系。 定義 3.10.2 設R AA，如果 R 是等價關系， BA， B 中任意二個元素之間都有關系R，則 B 是一個等價類。 定義 3.10.3 設R AA，R是等價關系，是基于 R 得到的等價類，則稱集合{}為 A 關于 R 的商集，記為 A/R。 定義 3.10.3 若是 A 的子集，若時，并且，則稱是A的一個劃分。 定理 3.10.1 設R AA，R 是等價關系，是利用 R 得到的 k 個不同的等價類，則 為集合 A 的劃分。 定理 3.10.2 設是A 的劃分， R=， 則 R 是等價關系。 3.11、偏序關系 定義 3.1 1.1 設R AA，如果 R 是自反、反對稱、可傳遞的關系則稱為偏序關系。 如：R 是實數(shù)中小于等于關系，則R是偏序關系。 定義 3.1 1.2 設R AA，R 偏序關系，x 與 y 是 A 中的元素，若序偶與至少有一個在 R 中，則稱 x 與 y 可比。 定義 3.1 1.3 設R AA，R 偏序關系，若 A 中任意二個元素都可比，則稱 A 為全序關系或線序關系。 定義 3.1 1.4 設R AA，R 偏序關系，將關系圖繪制成所有箭頭都朝上，然后去掉所有箭頭、去掉自旋邊、去掉復合邊，得到關系圖的簡化形式，稱為哈斯圖。 定義 3.1 1.5 在哈斯圖中，如果某個元素 y 在元素 x 的直接上方，則稱 y 蓋住了 x。記COVA={} 定義 3.1 1.6 設R AA，R 偏序關系，將偏序關系與集合 A 一塊稱為偏序集，記為，表示是 A 上的偏序關系。以后說偏序關系時，可簡單地說偏序集。 定義 3.1 1.7 在偏序集中，BA，yB，若都有R，則稱 y 是最大元。即最大元與 B 中每個元素都可比，并且都比其大。 定義 3.1 1.8 在偏序集中，BA，yB，若都有R，則稱 y 是最小元。即最小元與 B 中每個元素都可比，并且都比其小。 一個子集中沒有最大元或最小元時，可能存在極大元或極小元。 定義 3.1 1.9 在偏序集中，BA，yB，若不存在 xB 使得R，則稱 y是極大元， 即B中不存在比y“大”的元素。 即極大元與 B 中有些元素是否可比不做要求。 定義 3.1 1.10 在偏序集中，BA，yB，若不存在xB 都有R，則稱 y是極小元，不存在比 y 小的元素。即極小元與 B中元素是否可比不做要求。 定義 3.1 1.1 1 在偏序集中，BA，yB，若任意xB都有R，則稱y是B 的上界。與 B 中每個元素都可比，并且都 B 中的元素大。 3.12、其它關系 定義3.6.1 給定集合A上的關系ρ，若ρ是自反的、對稱的，則稱ρ是A上的相容關系。 定義3.6.3 給定非空集合A，設有集合S={}，其中且，i=1,2,…,m,且，則稱集合S稱作A的覆蓋。 定理3.6.1 給定集合A的覆蓋，，由它確定的關系：是相容關系。 定義3.7.1 設R為定義在集合A上的一個關系，若R是自反的，對稱的，傳遞的，則R稱為等價關系。(顯然等價關系一定是相容關系)。 定義3.7.2 設給定非空集合A，若有集合S={}，其中且(i=1,2,…,m)，且有，同時有，則稱S為A的一個劃分。(所有子集的并為A，且子集的交為空，則這些子集組成的集合為A的一個劃分，覆蓋中，子集的交集可不為空) 等價類 商集 偏序關系(自反性，反對稱性，傳遞性)，哈斯圖，可比的，元素y蓋住元素x，全序關系，極大元，極小元，最大元，最小元 擬序關系(反自反的，傳遞的) 第四章 代數(shù)系統(tǒng) 定義 4.3.1 設°是集合 S 上的二元運算，若都有 x°y=y°x，則稱°在 S 上是可交換的，或者說運算°在 S 上滿足交換律。 定義 4.3.2 設°是集合 S 上的二元運算，若都有(x°y)°z=x°(y°z)，則稱°在 S上是可結合的,或者說運算°在 S 上滿足結合律。 定義 4.3.3 設°是集合 S 上的二元運算，若都有 x°x=x， 則稱°在 S 上是冪等的,或說運算°在 S 上滿足冪等律。 定義 4.3.4 設°與*是集合 S 上的二種運算，若都有 x*(y°z)=(x*y)°(x*z)與(y°z)*x=(y*x)°(z*x)，則稱*對°是可分配的。 定義 4.3.5 設°與*是集合 S 上的二種可交換的二元運算，若都有 x*(x°y)=x 與x°(x*y)=x 則稱*與°是滿足吸收律，內(nèi)外二種運算不一樣，運算符內(nèi)外各出現(xiàn)一次，以多吃少。 廣群： 半群： 群： 子群： xiv