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

1、-作者xxxx-日期xxxx離散數(shù)學知識匯總【精品文檔】離散數(shù)學筆記第一章 命題邏輯合取析取 否定：當某個命題為真時，其否定為假，當某個命題為假時，其否定為真 條件聯(lián)結詞，表示“如果 那么”形式的語句 雙條件聯(lián)結詞，表示“當且僅當”形式的語句 合式公式(1)單個命題變元、命題常元為合式公式，稱為原子公式。(2)若某個字符串 A 是合式公式，則A、(A)也是合式公式。(3)若 A、B 是合式公式，則 A B、AB、A B、AB 是合式公式。(4)有限次使用(2)(3)形成的字符串均為合式公式。值式取范式與合取范式將一個普通公式轉換為范式的基本步驟定義 1.6.1 設 A 與 C 是兩個命題公式，

2、 若 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 一樣快，則兔子比烏龜跑得快表示為： xy(R(x

3、)T(y)H(x,y)有的兔子比所有的烏龜跑得快表示為：xy(R(x)T(y)H(x,y)、謂詞公式及其解釋、 非邏輯符號： 個體常元(如 a,b,c)、 函數(shù)常元(如表示的 f(x,y)、 謂詞常元(如表示人類的 H(x)。、邏輯符號：個體變元、量詞()、聯(lián)結詞()、逗號、括號。、項的定義：個體常元、變元及其函數(shù)式的表達式稱為項(item)。、原子公式：設 R()是 n 元謂詞，是項，則 R(t)是原子公式。原子公式中的個體變元，可以換成個體變元的表達式(項)，但不能出現(xiàn)任何聯(lián)結詞與量詞，只能為單個的謂詞公式。 合式公式：(1)原子公式是合式公式；(2)若 A 是合式公式，則(A)也是合式公

4、式；(3)若 A,B 合式，則 AB, AB, AB , AB 合式(4)若 A 合式，則xA、xA 合式(5)有限次使用(2)(4)得到的式子是合式。 量詞轄域：xA 和xA 中的量詞x/x 的作用范圍，A 就是作用范圍。 約束變元：在x 和x 的轄域 A 中出現(xiàn)的個體變元 x，稱為約束變元，這是與量詞相關的變元，約束變元的所有出現(xiàn)都稱為約束出現(xiàn)。 自由變元：謂詞公式中與任何量詞都無關的量詞，稱為自由變元，它的每次出現(xiàn)稱為自由出現(xiàn)。一個公式的個體變元不是約束變元，就是自由變元。注意：為了避免約束變元和自由變元同名出現(xiàn)，一般要對“約束變元”改名，而不對自由變元改名。 閉公式是指不含自由變元的謂

5、詞公式從本例(已省)可知， 不同的公式在同一個解釋下， 其真值可能存在， 也可能不存在， 但是對于沒有自由變元的公式(閉公式)，不論做何種解釋，其真值肯定存在謂詞公式的類型：重言式(永真式)、矛盾式(永假式)、可滿足公式三種類型 在任何解釋下，公式的真值總存在并為真，則為重言式或永真式。定義1 在任何解釋下，公式的真值總存在并為假，則為矛盾式或永假式。 存在個體域并存在一個解釋使得公式的真值存在并為真，則為可滿足式。定義 2.2.13 代換實例 設 是命題公式 中的命題變元， 是 n 個謂詞公式，用代替公式 中的后得到公式 A，則稱 A 為 的代換實例。如 A(x)A(x)，xA(x) xA(

6、x)可看成 p p 的代換實例，A(x) A(x)，xA(x) x A(x)可看成 p p 的代換實例。 命題邏輯的永真公式之代換實例是謂詞邏輯的永真公式， 命題邏輯的永假公式之代換實例是謂詞邏輯的永假式。（代換前后是同類型的公式）2.3、謂詞公式的等值演算 設 A、B 是兩個合法的謂詞公式，如果在任何解釋下，這兩個公式的真值都相等，則稱 A 與 B 等值，記為 A ó B。當 AóB 時，根據(jù)定義可知，在任何解釋下，公式 A 與公式 B 的真值都相同，故 AB 為永真式，故得到如下的定義。 設 A、B 是兩個合法謂詞公式，如果在任何解釋下， A B 為永真式， 則 A與

7、B 等值，記為 A ó B。一、利用代換實例可證明的等值式(pp 永真，代換實例 xF(x) xF(x)永真)二、個體域有限時，帶全稱量詞、存在量詞公式的等值式如：若D= ，則 xA(x) ó A()A()A()三、量詞的德摩律1、xA(x) ó xA(x) 2、xA(x) ó xA(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)的個

8、體變元 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、謂詞公式的范式從定理證明過程，可得到獲取前束

9、范式的步驟：(1)剔除不起作用的量詞；(2)如果約束變元與自由變元同名，則約束變元改名；(3)如果后面的約束變元與前面的約束變元同名，則后的約束變元改名；(4)利用代換實例，將、轉換表示；(5)利用德摩律，將否定深入到原子公式或命題的前面；(6)利用量詞轄域的擴張與收縮規(guī)律或利用量詞的分配律，將量詞移到最左邊2.5、謂詞推理定義 2.5.1 若在各種解釋下 只能為真即為永真，則稱為前提可推出結論 B。定義 2.5.2 在所有使 為真的解釋下，B 為真，則稱為前提 可推出結論 B。謂詞邏輯的推理方法分為以下幾類：一、 謂詞邏輯的等值演算原則、 規(guī)律： 代換實例、 量詞的德摩律、 量詞的分配律、

10、量詞轄域的擴張與收縮、約束變元改名。二、 命題邏輯的推理規(guī)則的代換實例， 如假言推理規(guī)則、 傳遞律、 合取與析取的性質律、CP 規(guī)則、反證法等。三、謂詞邏輯的推理公理第三章 集合與關系3.1、基本概念在離散數(shù)學稱 “不產(chǎn)生歧義的對象的匯集一塊” 便構成集合。常用大寫字母表示集合， 如 R 表示實數(shù)， N 表示自然數(shù)， Z 表示整數(shù)， Q 表示有理數(shù)，C 表示復數(shù)。描述一個集合一般有 “枚舉法” 與 “描述法” ， “枚舉法”。元素與集合之間有“屬于”或“不屬于”二種關系。 設 A，B 是兩個集合，如果 A 中的任何元素都是 B 中的元素，則稱 A 是 B的子集，也稱 B 包含于 A，記為 BA

11、，也稱 A 包含 B，記為 AB。集合運算性質 設 A、B 為集合，A 與 B 的并集 AB、A 與 B 的的交集 AB、A-B 的定義：AB=x|xAxB，AB=x|xAxB，A-B=x|xAxB 設 A、 B 為 集 合 ， A 與 B 的 對 稱 差 ， 記 為 AB=x|(xAxB)( xAxB)= AB - AB。 設 A、B 是兩個集合，若 AB、BA 則 A=B，即兩個集合相等。冪等律 AA=A、AA=A結合律 ABC= A(BC)= (AB)CABC= A(BC)= (AB)C交換律 AB=BA、AB=BA分配律 A(BC)=(AB)(AC)A(BC)=(AB)(AC)同一/零

12、律 AØ = A、AØ= Ø排中/矛盾律 AA=E、AA= Ø吸收律(大吃小) A(BA)=A、 A(BA)=A德摩律 (AB)= A B 、 (AB)= AB雙重否定 A=A3.3、有窮集的計數(shù)定理 3.3.1 二個集合的包含排斥原理 | | = | + | - |3.4、序偶 令<x,y>與<u,v>是二個序偶，如果 x=u、y=v，那么<x,y>=<u,v>即二個序偶相等。 如果<x,y>是序偶，且<<x,y>,z>也是一個序偶，則稱<x,y,z>為三元

13、組。3.5、直積或笛卡爾積 令 A、B 是兩個集合， 稱序偶的集合<x,y>|xA, yB為A與B的直積或笛卡爾積，記為 AB。如：A=1,2,3，B=a,b,c則AB=1,2,3a,b,c=<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>直積的性質1、A(BC)= A B A C2、A (BC)= A B A C3、(B C) A = B A C A4、(B C) A = B A C A5、ABóA C B

14、 C ó C A C B6、AB,CDóA C B D 令 是 n 個集合，稱n元組的集合<>|，為的直積或笛卡爾積，記為。3.6、關系 稱直積中部分感興趣的序偶所組成的集合為“關系” ，記為 R。如在直積1,2,3,4,5,6,7,81,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,

15、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） 如果序偶或元組屬于某個關系 R，則稱序偶或元組具有關系 R。關系圖，關系矩陣 3.7、關系的復合 若關系 FAA，關系 GAA，稱集合<x,y>|t 使得<x, t>F，<t,y>G為 F 與 G 的復合，記為 FG。 令 A=1,2,3，F(xiàn)=<1,1&

16、gt;,<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。 若關系 FAA，稱集合<y,x>|<x,y>F 為 F 的逆，記為 令

17、 A=1,2,3，F(xiàn)=<1,2>,<1,3>,<2,1>，則= <2,1>,<3,1>,<1,2>。3.8、關系的分類 若都有<x,x>R，則R是自反關系。(自己到自己的關系全屬于R) 若都有<x,x>R,則 R 是反自反的。(自己到自己的關系全不屬于R) 如果所有形如<x,x>的序偶都在關系 R 中， R 也只有這種形式的序偶， 則稱 R為恒等關系，記為。對于恒等關系而言，其關系矩陣是單位矩陣，即其主對角線全是 1，其他位置全是 0，對關系圖是每個點都有自旋，僅只有自旋，沒有其他邊。

18、令關系RAA，如果當<x,y>R 時<y,x>R，則稱 R 為對稱關系。 令關系RAA，如果當<x,y>R 且xy時<y,x>R， 則稱 R 為反對稱關系。 令關系RAA，若當<x,y>R,<y,z>R時有<x,z>R，則稱R為可傳遞關系。從RR 的關系矩陣可知，其非0元素在R的關系矩陣都出現(xiàn)，即，凡滿足這個不等式的關系，肯定為可傳遞關系。所以不可傳遞。從RR的關系矩陣可知，其非0元素出現(xiàn)在(1,1)，(1,3)，(2,2)，(2,4)，在 R 的關系矩陣都沒出現(xiàn)，不滿足，不可傳遞關系。3.9、關系的閉包將關系

19、矩陣的主角線上全部變成 1， 即得到其自反閉包的關系矩陣， 從而可得到其自反閉包。3.10、等價關系與集合的劃分 設R AA，如果 R 是自反、對稱、可傳遞的關系則稱為等價關系。 設R AA，如果 R 是等價關系， BA， B 中任意二個元素之間都有關系R，則 B 是一個等價類。 設R AA，R是等價關系，是基于 R 得到的等價類，則稱集合為 A 關于 R 的商集，記為 A/R。 若是 A 的子集，若時，并且，則稱是A的一個劃分。 設R AA，R 是等價關系，是利用 R 得到的 k 個不同的等價類，則 為集合 A 的劃分。 設是A 的劃分， R=， 則 R 是等價關系。3.11、偏序關系 設R

20、 AA，如果 R 是自反、反對稱、可傳遞的關系則稱為偏序關系。如：R 是實數(shù)中小于等于關系，則R是偏序關系。 設R AA，R 偏序關系，x 與 y 是 A 中的元素，若序偶<x,y>與<y,x>至少有一個在 R 中，則稱 x 與 y 可比。 設R AA，R 偏序關系，若 A 中任意二個元素都可比，則稱 A 為全序關系或線序關系。 設R AA，R 偏序關系，將關系圖繪制成所有箭頭都朝上，然后去掉所有箭頭、去掉自旋邊、去掉復合邊，得到關系圖的簡化形式，稱為哈斯圖。 在哈斯圖中，如果某個元素 y 在元素 x 的直接上方，則稱 y 蓋住了 x。記COVA=<x,y>

21、 設R AA，R 偏序關系，將偏序關系與集合 A 一塊稱為偏序集，記為<A,R>，表示是 A 上的偏序關系。以后說偏序關系時，可簡單地說偏序集<A,R>。 在偏序集<A,R>中，BA，yB，若都有<x,y>R，則稱 y 是最大元。即最大元與 B 中每個元素都可比，并且都比其大。 在偏序集<A,R>中，BA，yB，若都有<y,x>R，則稱 y 是最小元。即最小元與 B 中每個元素都可比，并且都比其小。一個子集中沒有最大元或最小元時，可能存在極大元或極小元。 在偏序集<A,R>中，BA，yB，若不存在 xB 使得&

22、lt;y,x>R，則稱 y是極大元， 即B中不存在比y“大”的元素。 即極大元與 B 中有些元素是否可比不做要求。 在偏序集<A,R>中，BA，yB，若不存在xB 都有<x,y>R，則稱 y是極小元，不存在比 y 小的元素。即極小元與 B中元素是否可比不做要求。定義 3.1 1.1 1 在偏序集<A,R>中，BA，yB，若任意xB都有<x,y>R，則稱y是B 的上界。與 B 中每個元素都可比，并且都 B 中的元素大。2、其它關系定義 給定集合A上的關系，若是自反的、對稱的，則稱是A上的相容關系。定義 給定非空集合A，設有集合S=，其中且，i=1,2,m,且，則稱集合S稱作A的覆蓋。定理3.6.1 給定集合A的覆蓋，由它確定的關系：是相容關系。定義3.7.1