第二篇:邏輯與圖論

1:什么是命題? 說(shuō)起什么是命題,命題是一個(gè)能夠判斷真假的語(yǔ)句,一般可以用一個(gè)大寫的字母表示為一個(gè)命題.舉個(gè)例子:

A:3是奇數(shù)

B:銅是金屬

C:1+4=2

結(jié)果很顯然易見,命題A和命題B的真值均是真命題,命題C的真值是假命題

2:什么是連接詞?

連接詞是用于把單個(gè)命題構(gòu)成復(fù)合命題,連接詞包括”非”,”與”,”或”,”蘊(yùn)含”,通常用符號(hào)“┐”表示“非”, 符號(hào)“ ∧”表示“ 與”、符 號(hào)“ ∨ ”表 示“ 或 ”和 符 號(hào)“ → ”表 示“ 蘊(yùn) 含 ”。

下邊有一張真值表,可以看看給出的這些連接詞的定義:

把上邊的圖字符用語(yǔ)言來(lái)概括下:

1:當(dāng)命題P和Q的真值時(shí),當(dāng)且僅當(dāng)復(fù)合命題P∧Q的真值是真,其他的情況P∧Q的真值均為假

2:當(dāng)命題P和Q的真值均為假時(shí),當(dāng)且僅當(dāng)復(fù)合命題P∨Q的真值為假,其他情況P∨Q均為真

3:當(dāng)命題P為真且命題Q為假時(shí),當(dāng)且僅當(dāng)復(fù)合命題P→Q的 真值為假。其他情況P→Q均為真。

4:至于連接詞“非”可對(duì)命題進(jìn)行否定,當(dāng)命題P為真,則有┐P為假。

3:命題的演算規(guī)律

根據(jù)上邊的幾條規(guī)定,對(duì)他的命題演算進(jìn)行證明下:

(1) ┐┐P =P

(2)P∨P P

P∧P P

(3)P∨Q Q∨P

P∧Q Q∧P

(4)P∨(Q∧R) (P∨Q)∧(P∨R)

P∧(Q∨R) (P∧Q)∨(P∧R) (5)P∨(P∧Q)P

P∧(P∨Q)P

(6)┐(P∨Q) ┐P∧┐Q

┐(P∧Q) ┐P∨┐Q

(7)P∨F P

P∧T P

(8)P∨T T

P∧F F

二:圖

這一部分將介紹下圖論的一些基本概念,先說(shuō)說(shuō)什么是圖,圖的定義如下:

1:什么是圖?

一個(gè)圖是由一個(gè)三元組(V,E,ψ)組成的,其中V是非空的節(jié)點(diǎn)集合,E是邊的集合,ψ是從邊集合E到節(jié)點(diǎn)無(wú)序偶或有序偶集合上的函數(shù)。

下面以一個(gè)例子說(shuō)明:

大家發(fā)現(xiàn)圖中的邊總是與兩個(gè)節(jié)點(diǎn)相關(guān)聯(lián),所以一個(gè)圖一般表示為二元組,即G = (V,E),若邊ek與節(jié)點(diǎn)無(wú)序偶〈vi,vj>相關(guān)聯(lián),則稱該邊為無(wú)向邊。若邊ek與節(jié)點(diǎn)有序偶〈vi,vj>相關(guān)聯(lián),則稱該邊為有向邊,其中vi為 邊ek的起始節(jié)點(diǎn),vj為終止節(jié)點(diǎn)。

并且如果一個(gè)圖中的每條邊都是沒有方向的,這個(gè)圖就可以稱為無(wú)向圖,就跟例1一樣,如果一個(gè)圖中每條邊都是有向邊,稱該圖為有向圖,如下圖所示:

在第二個(gè)圖中其實(shí)就可以用G = (V, E)來(lái)表示:

V= {a,b,c,d}

E= {〈a,b〉,〈a,d〉,〈b,d〉,〈b,c〉,〈c,c〉}

在圖中,如果兩個(gè)節(jié)點(diǎn)是由一條有向邊或者一條無(wú)向邊關(guān)聯(lián),則稱這兩個(gè)節(jié)點(diǎn)是鄰接點(diǎn).關(guān)聯(lián)于同一節(jié)點(diǎn)的兩條邊統(tǒng)稱為鄰接邊.關(guān)聯(lián)與同一個(gè)節(jié)點(diǎn)的一條邊稱為自閉路,比如上圖中的(c,c)就是一條自閉路.

另外在研究圖的性質(zhì)和圖的局部結(jié)構(gòu)中,子圖的概念是很重要的,下邊我想要說(shuō)說(shuō)子圖的定義:

設(shè)圖G=(V,E)和圖G1=(V1,E1),如果V1 ∈V且E1∈E,則稱G1 是G的子圖;如果V1 =V且E1=E,則稱G1 是G的真子圖;如果V1=V且E1∈E,則稱G1 是G的生成子圖。

下邊的這一個(gè)例子,(b)和(c)均為(a)的子圖,又(b)是(a)的生成子圖。

2:圖的重構(gòu)

通常, 一個(gè)圖的幾何圖形可有若干個(gè)不同的畫法, 就是說(shuō), 一 個(gè)圖的幾何圖并不是惟 一的 , 但它們描述的圖卻是相同的。如果有兩個(gè)圖 , 它們的節(jié)點(diǎn)數(shù)和邊數(shù)相同 , 而且節(jié)點(diǎn)和邊的關(guān)聯(lián)關(guān)系也一樣 , 那么這兩個(gè)圖應(yīng)是相同的 , 或稱同構(gòu)圖。

定義如下:

圖G1 =(V1,E1)和圖G2 =(V2,E2),若存在雙射函數(shù)f:V1→V2,且e=〈vi,vj〉是G1的一條邊,當(dāng)且僅當(dāng)e′=〈f(vi),f(vj)〉是G2 的一條邊,則稱G1 和G2 同構(gòu),記為G1 DG2。

舉個(gè)例子:

下面的兩個(gè)圖是同構(gòu)圖,用\來(lái)表示對(duì)應(yīng)

節(jié)點(diǎn)的對(duì)應(yīng):

v1 \a

v2 \b

v3 \c

v4 \d

〈v2,v1〉\〈b,a〉

〈v4 ,v1〉\ 〈d,a〉

〈v3 ,v4〉\ 〈c,d〉

〈v3 ,v2〉\ 〈c,b〉

2:路徑和回路

路徑的定義:

有向圖G=(V,E)的有限條邊的序列e1,e2,…,en, 其中任意邊ei的終止節(jié)點(diǎn)是邊ei+ 1 的起始節(jié)點(diǎn) , 則稱這樣的邊

序列是圖G的路徑。當(dāng)路徑中所有的邊都互不相同時(shí) , 稱為簡(jiǎn)單路徑 ; 當(dāng)路徑中所

有節(jié)點(diǎn)都互不相同時(shí) , 稱為基本路徑

比如在下圖中:

P4 = (〈v1 ,v2〉,〈v2 ,v4〉,〈v4 ,v2〉,〈v2 ,v3〉,〈v3 ,v4〉,〈v4 ,v2〉,

〈v2 ,v5〉,〈v5 ,v1〉)是一條回路;P5 = (〈v1 ,v2〉,〈v2 ,v3〉,〈v3 ,v4〉,〈v4 ,v2〉,〈v2 ,v5〉,〈v5 ,v1〉)

是一條簡(jiǎn)單回路 ;P6 = (〈v1 ,v2〉,〈v2 ,v3〉,〈v3 ,v4〉,〈v4 ,v5〉,〈v5 ,v1〉) 是 一條 基

本回路。

路徑長(zhǎng)度:

在一條路徑中, 所含邊的條數(shù)稱為該路徑的長(zhǎng)度。

在一個(gè)有向圖中, 如果存在從節(jié) 點(diǎn)vi到節(jié)點(diǎn)vj的路徑,則稱從vi到vj是可達(dá)的。將vi可達(dá)的所有節(jié)點(diǎn)構(gòu)成 的集合稱為是vi的可達(dá)節(jié)點(diǎn)集。

在一個(gè)有向圖中, 如果每對(duì)不同 的節(jié)點(diǎn)vi和vj之間都是相互可達(dá)的, 則稱該圖是強(qiáng)連圖。

3:圖的矩陣表示:

定義:

設(shè)G= (V,E) 是 有 向 圖 ,V= {v1 ,v2,…,vn},定義一個(gè)n×n的矩陣A,A的元素是aij, 并且有

稱矩陣A是圖G的鄰接矩陣。

4 .節(jié)點(diǎn)度數(shù)

在有向圖中 , 射入一個(gè)節(jié)點(diǎn)的邊數(shù)稱為該節(jié)點(diǎn)的入度 , 由一個(gè)節(jié)點(diǎn)射出的邊數(shù)稱為該節(jié)點(diǎn)的出度。 節(jié)點(diǎn)的入度和出度之和 , 稱為該節(jié)點(diǎn)的度數(shù)。在無(wú)向圖中 , 一個(gè)節(jié)點(diǎn)關(guān)聯(lián)的邊數(shù)就稱為該節(jié)點(diǎn)的度數(shù)。

5:樹

樹是一種無(wú)回路的有向圖,無(wú)回路的有向圖, 是指一個(gè)有向圖中不存在回路。其中, 入度為 0 的節(jié)點(diǎn) 稱為根節(jié)點(diǎn),出度為 0 的節(jié)點(diǎn)稱為葉子。因此, 圖中節(jié)點(diǎn)a和節(jié) 點(diǎn)f是根節(jié)點(diǎn) , 而節(jié) 點(diǎn)b、d和g便 是 葉 子 。

定義如下:

如果有向圖T中,只存在一個(gè)節(jié)點(diǎn)v的入度為0,其他所有節(jié)點(diǎn)入度均為 1, 從節(jié)點(diǎn)v出發(fā)可到達(dá)T中的每個(gè)節(jié) 點(diǎn),則稱T是一棵有向樹或稱根樹.T中入度為0的節(jié)點(diǎn)v是樹的根,T中出度為0的節(jié)點(diǎn)是樹 的葉子,其他入度為 1 的節(jié)點(diǎn)稱為樹的枝節(jié)點(diǎn)(或稱內(nèi)節(jié)點(diǎn))。

例如下圖中的所示的樹均為根樹。一個(gè)孤立節(jié)點(diǎn)也是一棵有向樹。

因?yàn)橛邢驑渲袥]有任何回路, 所以樹中所有路徑都是基本路 徑。從根節(jié)點(diǎn)到樹中某一節(jié)點(diǎn)的路徑長(zhǎng)度, 稱為該節(jié)點(diǎn)的層數(shù)。

在上圖(a)所示的樹中,根節(jié)點(diǎn)1 的層數(shù)為0,節(jié)點(diǎn)2,5,6 的層 數(shù)為 1, 節(jié)點(diǎn) 3,4, 7 的層數(shù)為 3。同時(shí)將樹中最長(zhǎng)的路徑長(zhǎng)度稱為樹的高度。

同時(shí)為了方便 , 可以借用家族術(shù)語(yǔ)來(lái)表達(dá)樹中節(jié)點(diǎn)之間的關(guān)系 , 把 從節(jié)點(diǎn)v出發(fā)可達(dá)的每個(gè)節(jié)點(diǎn) , 都稱是v的子孫 , 其中只經(jīng)一條邊可達(dá)的節(jié)點(diǎn),稱是v的直接子孫(或稱兒子)。

從有向樹的結(jié)構(gòu)可以看出,樹的每一個(gè)節(jié)點(diǎn)也都是給定樹的 子樹的根。如果刪除樹的根和與它關(guān)聯(lián)的邊 , 便得到一些子樹 , 這 些子樹的根 , 就是第一層上的各節(jié)點(diǎn)

在有向樹中,如果每個(gè)節(jié)點(diǎn)的出度小于或等于m, 稱該樹是m元樹; 如果每個(gè)節(jié)點(diǎn)的出度都等于m或 0, 稱該樹是完全m元樹

當(dāng)m= 2,m元樹和完全m元樹分別稱為二元樹和完全二元 樹。對(duì)于二元樹的每個(gè)枝節(jié)點(diǎn)或根節(jié)點(diǎn) , 至多有兩棵子樹 , 分別為 左子樹和右子樹

舉個(gè)例子:

用二元樹表示一個(gè)算術(shù)表達(dá)式((a-c)/(b1+b2))+b3 *b4

對(duì)計(jì)算機(jī)來(lái)說(shuō) , 處理二元樹是比較方便的 , 所以常把有序樹轉(zhuǎn) 化為二元樹。用二元樹表示有序樹的方法是 :

(1) 除保留最左邊的枝節(jié)點(diǎn)外, 刪去所有從每個(gè)節(jié)點(diǎn)長(zhǎng)出的 分枝 , 在一層中的節(jié)點(diǎn)之間用從左到右的有向邊連接。

(2) 對(duì)任何給定的節(jié)點(diǎn), 它的左兒子和右兒子按以下方法選 定:直接處于給定節(jié)點(diǎn)之下的節(jié)點(diǎn), 作為左兒子, 對(duì)于同一水平線 上與給定節(jié)點(diǎn)有鄰接的節(jié)點(diǎn) , 作為右兒子 , 依此類推。

好,上述內(nèi)容已經(jīng)包含了大部分形式語(yǔ)言和自動(dòng)機(jī)所需的基礎(chǔ)知識(shí),接下來(lái)我們將會(huì)正式開始形式語(yǔ)言和自動(dòng)機(jī)的學(xué)習(xí)