離散數(shù)學筆記

第一章 命題邏輯

合取

析取

定義 1. 1.3 否定：當某個命題為真時，其否定為假，當某個命題為假時，其否定為真

定義 1. 1.4 條件聯(lián)結(jié)詞，表示“如果… …那么……”形式的語句

定義 1. 1.5 雙條件聯(lián)結(jié)詞，表示“當且僅當”形式的語句

定義 1.2.1 合式公式

(1)單個命題變元、命題常元為合式公式，稱為原子公式。

(2)若某個字符串 A 是合式公式，則

A、(A)也是合式公式。

(3)若 A、B 是合式公式，則 A

B、A

B、A

B、A

B 是合式公式。

(4)有限次使用(2)~(3)形成的字符串均為合式公式。

1.3等值式

1.4析取范式與合取范式

將一個普通公式轉(zhuǎn)換為范式的基本步驟

1.6推理

定義 1.6.1 設 A 與 C 是兩個命題公式， 若 A → C 為永真式、 重言式，則稱 C 是 A 的有

效結(jié)論，或稱 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)結(jié)詞(﹁∨∧→?)、逗號、括號。

定義 2.2.3、項的定義：個體常元、變元及其函數(shù)式的表達式稱為項(item)。

定義 2.2.4、原子公式：設 R(

)是 n 元謂詞，

是項，則 R(t)是原子公式。原子公式中的個體變元，可以換成個體變元的表達式(項)，但不能出現(xiàn)任何聯(lián)結(jié)詞與量詞，只能為單個的謂詞公式。

定義 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，稱為約束變元，這是與量詞相關(guān)的變元，約束變元的所有出現(xiàn)都稱為約束出現(xiàn)。

定義 2.2.8 自由變元：謂詞公式中與任何量詞都無關(guān)的量詞，稱為自由變元，它的每次出現(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， 利用 “基本等值一” 將其轉(zhuǎn)換為析取式， 再使用德摩律進行演算

六、置換規(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)利用代換實例，將→、?轉(zhuǎn)換﹁∨∧表示；

(5)利用德摩律，將否定﹁深入到原子公式或命題的前面；

(6)利用量詞轄域的擴張與收縮規(guī)律或利用量詞的分配律，將量詞移到最左邊

2.5、謂詞推理

定義 2.5.1 若在各種解釋下

只能為真即為永真，則稱為前提

可推出結(jié)論 B。

定義 2.5.2 在所有使

為真的解釋下，B 為真，則稱為前提

可推出結(jié)論 B。

謂詞邏輯的推理方法分為以下幾類：

一、 謂詞邏輯的等值演算原則、 規(guī)律： 代換實例、 量詞的德摩律、 量詞的分配律、 量詞

轄域的擴張與收縮、約束變元改名。

二、 命題邏輯的推理規(guī)則的代換實例， 如假言推理規(guī)則、 傳遞律、 合取與析取的性質(zhì)律、

CP 規(guī)則、反證法等。

三、謂詞邏輯的推理公理

第三章 集合與關(guān)系

3.1、基本概念

在離散數(shù)學稱 “不產(chǎn)生歧義的對象的匯集一塊” 便構(gòu)成集合。常用大寫字母表示集合， 如 R 表示實數(shù)， N 表示自然數(shù)， Z 表示整數(shù)， Q 表示有理數(shù)，C 表示復數(shù)。描述一個集合一般有 “枚舉法” 與 “描述法” ， “枚舉法”。元素與集合之間有“屬于

”或“不屬于

”二種關(guān)系。

定義 3.1.1 設 A，B 是兩個集合，如果 A 中的任何元素都是 B 中的元素，則稱 A 是 B

的子集，也稱 B 包含于 A，記為 B

A，也稱 A 包含 B，記為 A

B。

3.2集合運算性質(zhì)

定義 3.2.1 設 A、B 為集合，A 與 B 的并集 A

B、A 與 B 的的交集 A

B、A-B 的定

義：A

B={x|x

A

x

B}，A

B={x|x

A

x

B}，A-B={x|x

A

x

B}

定 義 3.2.2 設 A、 B 為 集 合 ， A 與 B 的 對 稱 差 ， 記 為 A

B={x|(x

A

x

B)

( x

A

x

B)}= A

B - A

B。

定義 3.2.3 設 A、B 是兩個集合，若 A

B、B

A 則 A=B，即兩個集合相等。

冪等律 A

A=A、A

A=A

結(jié)合律 A

B

C= A

(B

C)= (A

B)

C

A

B

C= A

(B

C)= (A

B)

C

交換律 A

B=B

A、A

B=B

A

分配律 A

(B

C)=(A

B)

(A

C)

A

(B

C)=(A

B)

(A

C)

同一/零律 A

? = A、A

?= ?

排中/矛盾律 A

A=E、A

A= ?

吸收律(大吃小) A

(B

A)=A、 A

(B

A)=A

德摩律

(A

B)=

A

B 、

(A

B)=

A

B

雙重否定

A=A

3.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>|x

A, y

B}為A與B的直積或笛卡爾積，記為 A

B。

如：A={1,2,3}，B={a,b,c}則A

B={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

(B

C)= A

B

A

C

2、A

(B

C)= A

B

A

C

3、(B

C)

A = B

A

C

A

4、(B

C)

A = B

A

C

A

5、A

BóA

C

B

C ó C

A

C

B

6、A

B,C

DóA

C

B

D

定義 3.5.2 令

是 n 個集合，稱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}中， 只對第 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>}，R

A

A（A={1,2,3,4,5,6,7,8}）

定義 3.6.2 如果序偶或元組屬于某個關(guān)系 R，則稱序偶或元組具有關(guān)系 R。

關(guān)系圖，關(guān)系矩陣

3.7、關(guān)系的復合

定義 3.7.1 若關(guān)系 F

A

A，關(guān)系 G

A

A，稱集合{<x,y>|

t 使得<x, t>

F，<t,y>

G}

為 F 與 G 的復合，記為 F

G。

例題 3.7.1 令 A={1,2,3}，F(xiàn)={<1,1>,<1,2>} G={<2,2>,<1,3>,<1,1>}則

解： F

G={ <1,3>,<1,1>,<1,2>} ，G

F={<1,2>,<1,1>}， 因此關(guān)系的復合不滿足交換律。

采用復合的定義去計算，只適合于人工計算，為了編程實現(xiàn)，故采用矩陣表示關(guān)系。

說明：

的第 i 行與

的第 j 列相乘時，乘法是合取

，加法是析取

，如 MF 的 1 行與 MG

的第 3 列相乘是：(1

1)

(1

0)

(0

0)，結(jié)果為 1。

定義 3.7.2 若關(guān)系 F

A

A，稱集合{<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、關(guān)系的分類

定義 3.8.1 若

都有<x,x>

R，則R是自反關(guān)系。(自己到自己的關(guān)系全屬于R)

定義 3.8.2 若

都有<x,x>

R,則 R 是反自反的。(自己到自己的關(guān)系全不屬于R)

定義 3.8.4 如果所有形如<x,x>的序偶都在關(guān)系 R 中， R 也只有這種形式的序偶， 則稱 R為恒等關(guān)系，記為

。

對于恒等關(guān)系而言，其關(guān)系矩陣是單位矩陣，即其主對角線全是 1，其他位置全是 0，對關(guān)系圖是每個點都有自旋，僅只有自旋，沒有其他邊。

定義 3.8.5 令關(guān)系R

A

A，如果當<x,y>

R 時<y,x>

R，則稱 R 為對稱關(guān)系。

定義 3.8.6 令關(guān)系R

A

A，如果當<x,y>

R 且x

y時<y,x>

R， 則稱 R 為反對稱關(guān)系。

定義 3.8.8 令關(guān)系R

A

A，若當<x,y>

R,<y,z>

R時有<x,z>

R，則稱R為可傳遞關(guān)系。

從R

R 的關(guān)系矩陣可知，其非0元素在R的關(guān)系矩陣都出現(xiàn)，即

，凡滿足這個不等式的關(guān)系，肯定為可傳遞關(guān)系。

所以不可傳遞。

從R

R的關(guān)系矩陣可知，其非0元素出現(xiàn)在(1,1)，(1,3)，(2,2)，(2,4)，在 R 的關(guān)系矩

陣都沒出現(xiàn)，不滿足

，不可傳遞關(guān)系。

3.9、關(guān)系的閉包

將關(guān)系矩陣的主角線上全部變成 1， 即得到其自反閉包的關(guān)系矩陣， 從而可得到其自反閉包。

3.10、等價關(guān)系與集合的劃分

定義 3.10.1 設R

A

A，如果 R 是自反、對稱、可傳遞的關(guān)系則稱為等價關(guān)系。

定義 3.10.2 設R

A

A，如果 R 是等價關(guān)系， B

A， B 中任意二個元素之間都有關(guān)系R，則 B 是一個等價類。

定義 3.10.3 設R

A

A，R是等價關(guān)系，

是基于 R 得到的等價類，則稱集合{

}為 A 關(guān)于 R 的商集，記為 A/R。

定義 3.10.3 若

是 A 的子集，若

時

，并且

，則稱

是A的一個劃分。

定理 3.10.1 設R

A

A，R 是等價關(guān)系，

是利用 R 得到的 k 個不同的等價類，則

為集合 A 的劃分。

定理 3.10.2 設

是A 的劃分， R=

， 則 R 是等價關(guān)系。

3.11、偏序關(guān)系

定義 3.1 1.1 設R

A

A，如果 R 是自反、反對稱、可傳遞的關(guān)系則稱為偏序關(guān)系。

如：R 是實數(shù)中小于等于關(guān)系，則R是偏序關(guān)系。

定義 3.1 1.2 設R

A

A，R 偏序關(guān)系，x 與 y 是 A 中的元素，若序偶<x,y>與<y,x>至少有一個在 R 中，則稱 x 與 y 可比。

定義 3.1 1.3 設R

A

A，R 偏序關(guān)系，若 A 中任意二個元素都可比，則稱 A 為全序關(guān)系或線序關(guān)系。

定義 3.1 1.4 設R

A

A，R 偏序關(guān)系，將關(guān)系圖繪制成所有箭頭都朝上，然后去掉所有箭頭、去掉自旋邊、去掉復合邊，得到關(guān)系圖的簡化形式，稱為哈斯圖。

定義 3.1 1.5 在哈斯圖中，如果某個元素 y 在元素 x 的直接上方，則稱 y 蓋住了 x。記COVA={<x,y>}

定義 3.1 1.6 設R

A

A，R 偏序關(guān)系，將偏序關(guān)系與集合 A 一塊稱為偏序集，記為<A,R>，表示是 A 上的偏序關(guān)系。以后說偏序關(guān)系時，可簡單地說偏序集<A,R>。

定義 3.1 1.7 在偏序集<A,R>中，B

A，y

B，若

都有<x,y>

R，則稱 y 是最大元。即最大元與 B 中每個元素都可比，并且都比其大。

定義 3.1 1.8 在偏序集<A,R>中，B

A，y

B，若

都有<y,x>

R，則稱 y 是最小元。即最小元與 B 中每個元素都可比，并且都比其小。

一個子集中沒有最大元或最小元時，可能存在極大元或極小元。

定義 3.1 1.9 在偏序集<A,R>中，B

A，y

B，若不存在 x

B 使得<y,x>

R，則稱 y是極大元， 即B中不存在比y“大”的元素。 即極大元與 B 中有些元素是否可比不做要求。

定義 3.1 1.10 在偏序集<A,R>中，B

A，y

B，若不存在x

B 都有<x,y>

R，則稱 y是極小元，不存在比 y 小的元素。即極小元與 B中元素是否可比不做要求。

定義 3.1 1.1 1 在偏序集<A,R>中，B

A，y

B，若任意x

B都有<x,y>

R，則稱y是B 的上界。與 B 中每個元素都可比，并且都 B 中的元素大。

3.12、其它關(guān)系

定義3.6.1 給定集合A上的關(guān)系ρ，若ρ是自反的、對稱的，則稱ρ是A上的相容關(guān)系。

定義3.6.3 給定非空集合A，設有集合S={

}，其中

且

，i=1,2,…,m,且

，則稱集合S稱作A的覆蓋。

定理3.6.1 給定集合A的覆蓋，

，由它確定的關(guān)系：

是相容關(guān)系。

定義3.7.1 設R為定義在集合A上的一個關(guān)系，若R是自反的，對稱的，傳遞的，則R稱為等價關(guān)系。(顯然等價關(guān)系一定是相容關(guān)系)。

定義3.7.2 設給定非空集合A，若有集合S={

}，其中

且

(i=1,2,…,m)，且有

，同時有

，則稱S為A的一個劃分。(所有子集的并為A，且子集的交為空，則這些子集組成的集合為A的一個劃分，覆蓋中，子集的交集可不為空)

等價類

商集

偏序關(guān)系(自反性，反對稱性，傳遞性)

，哈斯圖，可比的，元素y蓋住元素x，全序關(guān)系，極大元，極小元，最大元，最小元

擬序關(guān)系(反自反的，傳遞的)

第四章 代數(shù)系統(tǒng)

定義 4.3.1 設°是集合 S 上的二元運算，若

都有 x°y=y°x，則稱°在 S 上是可交換的，或者說運算°在 S 上滿足交換律。

定義 4.3.2 設°是集合 S 上的二元運算，若

都有(x°y)°z=x°(y°z)，則稱°在 S上是可結(jié)合的,或者說運算°在 S 上滿足結(jié)合律。

定義 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)一次，以多吃少。

廣群：

半群：

群：

子群：