《離散數(shù)學(xué)知識(shí)匯總.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)知識(shí)匯總.doc（14頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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