第二篇:邏輯與圖論
1:什么是命題? 說起什么是命題,命題是一個能夠判斷真假的語句,一般可以用一個大寫的字母表示為一個命題.舉個例子:
A:3是奇數(shù)
B:銅是金屬
C:1+4=2
結(jié)果很顯然易見,命題A和命題B的真值均是真命題,命題C的真值是假命題
2:什么是連接詞?
連接詞是用于把單個命題構(gòu)成復(fù)合命題,連接詞包括”非”,”與”,”或”,”蘊含”,通常用符號“┐”表示“非”, 符號“ ∧”表示“ 與”、符 號“ ∨ ”表 示“ 或 ”和 符 號“ → ”表 示“ 蘊 含 ”。
下邊有一張真值表,可以看看給出的這些連接詞的定義:
把上邊的圖字符用語言來概括下:
1:當命題P和Q的真值時,當且僅當復(fù)合命題P∧Q的真值是真,其他的情況P∧Q的真值均為假
2:當命題P和Q的真值均為假時,當且僅當復(fù)合命題P∨Q的真值為假,其他情況P∨Q均為真
3:當命題P為真且命題Q為假時,當且僅當復(fù)合命題P→Q的 真值為假。其他情況P→Q均為真。
4:至于連接詞“非”可對命題進行否定,當命題P為真,則有┐P為假。
3:命題的演算規(guī)律
根據(jù)上邊的幾條規(guī)定,對他的命題演算進行證明下:
(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
二:圖
這一部分將介紹下圖論的一些基本概念,先說說什么是圖,圖的定義如下:
1:什么是圖?
一個圖是由一個三元組(V,E,ψ)組成的,其中V是非空的節(jié)點集合,E是邊的集合,ψ是從邊集合E到節(jié)點無序偶或有序偶集合上的函數(shù)。
下面以一個例子說明:
大家發(fā)現(xiàn)圖中的邊總是與兩個節(jié)點相關(guān)聯(lián),所以一個圖一般表示為二元組,即G = (V,E),若邊ek與節(jié)點無序偶〈vi,vj>相關(guān)聯(lián),則稱該邊為無向邊。若邊ek與節(jié)點有序偶〈vi,vj>相關(guān)聯(lián),則稱該邊為有向邊,其中vi為 邊ek的起始節(jié)點,vj為終止節(jié)點。
并且如果一個圖中的每條邊都是沒有方向的,這個圖就可以稱為無向圖,就跟例1一樣,如果一個圖中每條邊都是有向邊,稱該圖為有向圖,如下圖所示:
在第二個圖中其實就可以用G = (V, E)來表示:
V= {a,b,c,d}
E= {〈a,b〉,〈a,d〉,〈b,d〉,〈b,c〉,〈c,c〉}
在圖中,如果兩個節(jié)點是由一條有向邊或者一條無向邊關(guān)聯(lián),則稱這兩個節(jié)點是鄰接點.關(guān)聯(lián)于同一節(jié)點的兩條邊統(tǒng)稱為鄰接邊.關(guān)聯(lián)與同一個節(jié)點的一條邊稱為自閉路,比如上圖中的(c,c)就是一條自閉路.
另外在研究圖的性質(zhì)和圖的局部結(jié)構(gòu)中,子圖的概念是很重要的,下邊我想要說說子圖的定義:
設(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的生成子圖。
下邊的這一個例子,(b)和(c)均為(a)的子圖,又(b)是(a)的生成子圖。
2:圖的重構(gòu)
通常, 一個圖的幾何圖形可有若干個不同的畫法, 就是說, 一 個圖的幾何圖并不是惟 一的 , 但它們描述的圖卻是相同的。如果有兩個圖 , 它們的節(jié)點數(shù)和邊數(shù)相同 , 而且節(jié)點和邊的關(guān)聯(lián)關(guān)系也一樣 , 那么這兩個圖應(yīng)是相同的 , 或稱同構(gòu)圖。
定義如下:
圖G1 =(V1,E1)和圖G2 =(V2,E2),若存在雙射函數(shù)f:V1→V2,且e=〈vi,vj〉是G1的一條邊,當且僅當e′=〈f(vi),f(vj)〉是G2 的一條邊,則稱G1 和G2 同構(gòu),記為G1 DG2。
舉個例子:
下面的兩個圖是同構(gòu)圖,用\來表示對應(yīng)
節(jié)點的對應(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é)點是邊ei+ 1 的起始節(jié)點 , 則稱這樣的邊
序列是圖G的路徑。當路徑中所有的邊都互不相同時 , 稱為簡單路徑 ; 當路徑中所
有節(jié)點都互不相同時 , 稱為基本路徑
比如在下圖中:
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〉)
是一條簡單回路 ;P6 = (〈v1 ,v2〉,〈v2 ,v3〉,〈v3 ,v4〉,〈v4 ,v5〉,〈v5 ,v1〉) 是 一條 基
本回路。
路徑長度:
在一條路徑中, 所含邊的條數(shù)稱為該路徑的長度。
在一個有向圖中, 如果存在從節(jié) 點vi到節(jié)點vj的路徑,則稱從vi到vj是可達的。將vi可達的所有節(jié)點構(gòu)成 的集合稱為是vi的可達節(jié)點集。
在一個有向圖中, 如果每對不同 的節(jié)點vi和vj之間都是相互可達的, 則稱該圖是強連圖。
3:圖的矩陣表示:
定義:
設(shè)G= (V,E) 是 有 向 圖 ,V= {v1 ,v2,…,vn},定義一個n×n的矩陣A,A的元素是aij, 并且有
稱矩陣A是圖G的鄰接矩陣。
4 .節(jié)點度數(shù)
在有向圖中 , 射入一個節(jié)點的邊數(shù)稱為該節(jié)點的入度 , 由一個節(jié)點射出的邊數(shù)稱為該節(jié)點的出度。 節(jié)點的入度和出度之和 , 稱為該節(jié)點的度數(shù)。在無向圖中 , 一個節(jié)點關(guān)聯(lián)的邊數(shù)就稱為該節(jié)點的度數(shù)。
5:樹
樹是一種無回路的有向圖,無回路的有向圖, 是指一個有向圖中不存在回路。其中, 入度為 0 的節(jié)點 稱為根節(jié)點,出度為 0 的節(jié)點稱為葉子。因此, 圖中節(jié)點a和節(jié) 點f是根節(jié)點 , 而節(jié) 點b、d和g便 是 葉 子 。
定義如下:
如果有向圖T中,只存在一個節(jié)點v的入度為0,其他所有節(jié)點入度均為 1, 從節(jié)點v出發(fā)可到達T中的每個節(jié) 點,則稱T是一棵有向樹或稱根樹.T中入度為0的節(jié)點v是樹的根,T中出度為0的節(jié)點是樹 的葉子,其他入度為 1 的節(jié)點稱為樹的枝節(jié)點(或稱內(nèi)節(jié)點)。
例如下圖中的所示的樹均為根樹。一個孤立節(jié)點也是一棵有向樹。
因為有向樹中沒有任何回路, 所以樹中所有路徑都是基本路 徑。從根節(jié)點到樹中某一節(jié)點的路徑長度, 稱為該節(jié)點的層數(shù)。
在上圖(a)所示的樹中,根節(jié)點1 的層數(shù)為0,節(jié)點2,5,6 的層 數(shù)為 1, 節(jié)點 3,4, 7 的層數(shù)為 3。同時將樹中最長的路徑長度稱為樹的高度。
同時為了方便 , 可以借用家族術(shù)語來表達樹中節(jié)點之間的關(guān)系 , 把 從節(jié)點v出發(fā)可達的每個節(jié)點 , 都稱是v的子孫 , 其中只經(jīng)一條邊可達的節(jié)點,稱是v的直接子孫(或稱兒子)。
從有向樹的結(jié)構(gòu)可以看出,樹的每一個節(jié)點也都是給定樹的 子樹的根。如果刪除樹的根和與它關(guān)聯(lián)的邊 , 便得到一些子樹 , 這 些子樹的根 , 就是第一層上的各節(jié)點
在有向樹中,如果每個節(jié)點的出度小于或等于m, 稱該樹是m元樹; 如果每個節(jié)點的出度都等于m或 0, 稱該樹是完全m元樹
當m= 2,m元樹和完全m元樹分別稱為二元樹和完全二元 樹。對于二元樹的每個枝節(jié)點或根節(jié)點 , 至多有兩棵子樹 , 分別為 左子樹和右子樹
舉個例子:
用二元樹表示一個算術(shù)表達式((a-c)/(b1+b2))+b3 *b4
對計算機來說 , 處理二元樹是比較方便的 , 所以常把有序樹轉(zhuǎn) 化為二元樹。用二元樹表示有序樹的方法是 :
(1) 除保留最左邊的枝節(jié)點外, 刪去所有從每個節(jié)點長出的 分枝 , 在一層中的節(jié)點之間用從左到右的有向邊連接。
(2) 對任何給定的節(jié)點, 它的左兒子和右兒子按以下方法選 定:直接處于給定節(jié)點之下的節(jié)點, 作為左兒子, 對于同一水平線 上與給定節(jié)點有鄰接的節(jié)點 , 作為右兒子 , 依此類推。
好,上述內(nèi)容已經(jīng)包含了大部分形式語言和自動機所需的基礎(chǔ)知識,接下來我們將會正式開始形式語言和自動機的學(xué)習(xí)
