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

離散數(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 一樣快，則兔子比烏龜跑得快表示為： xy(R(x)T(y)H(x,y)有的兔子比所有的烏龜跑得快表示為：xy(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 合式，則 AB, AB, AB , AB 合式(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 的真值都相同，故 AB 為永真式，故得到如下的定義。定義 2.3.2 設 A、B 是兩個合法謂詞公式，如果在任何解釋下， A B 為永真式， 則 A與 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)的個體變元 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ī)則、 傳遞律、 合取與析取的性質律、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集合運算性質定義 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)( xAxB)= AB - AB。定義 3.2.3 設 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)同一/零律 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、序偶定義 3.4.2 令<x,y>與<u,v>是二個序偶，如果 x=u、y=v，那么<x,y>=<u,v>即二個序偶相等。定義 3.4.3 如果<x,y>是序偶，且<<x,y>,z>也是一個序偶，則稱<x,y,z>為三元組。3.5、直積或笛卡爾積定義 3.5.1 令 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 C ó C A C B6、AB,CDóA C B D定義 3.5.2 令 是 n 個集合，稱n元組的集合<>|，為的直積或笛卡爾積，記為。3.6、關系定義 3.6.1 稱直積中部分感興趣的序偶所組成的集合為“關系” ，記為 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,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，稱集合<x,y>|t 使得<x, t>F，<t,y>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，稱集合<y,x>|<x,y>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 若都有<x,x>R，則R是自反關系。(自己到自己的關系全屬于R)定義 3.8.2 若都有<x,x>R,則 R 是反自反的。(自己到自己的關系全不屬于R)定義 3.8.4 如果所有形如<x,x>的序偶都在關系 R 中， R 也只有這種形式的序偶， 則稱 R為恒等關系，記為。對于恒等關系而言，其關系矩陣是單位矩陣，即其主對角線全是 1，其他位置全是 0，對關系圖是每個點都有自旋，僅只有自旋，沒有其他邊。定義 3.8.5 令關系RAA，如果當<x,y>R 時<y,x>R，則稱 R 為對稱關系。定義 3.8.6 令關系RAA，如果當<x,y>R 且xy時<y,x>R， 則稱 R 為反對稱關系。定義 3.8.8 令關系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、關系的閉包將關系矩陣的主角線上全部變成 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 中的元素，若序偶<x,y>與<y,x>至少有一個在 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=<x,y>定義 3.1 1.6 設R AA，R 偏序關系，將偏序關系與集合 A 一塊稱為偏序集，記為<A,R>，表示是 A 上的偏序關系。以后說偏序關系時，可簡單地說偏序集<A,R>。定義 3.1 1.7 在偏序集<A,R>中，BA，yB，若都有<x,y>R，則稱 y 是最大元。即最大元與 B 中每個元素都可比，并且都比其大。定義 3.1 1.8 在偏序集<A,R>中，BA，yB，若都有<y,x>R，則稱 y 是最小元。即最小元與 B 中每個元素都可比，并且都比其小。一個子集中沒有最大元或最小元時，可能存在極大元或極小元。定義 3.1 1.9 在偏序集<A,R>中，BA，yB，若不存在 xB 使得<y,x>R，則稱 y是極大元， 即B中不存在比y“大”的元素。 即極大元與 B 中有些元素是否可比不做要求。定義 3.1 1.10 在偏序集<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 中的元素大。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