第一篇:集合與推理方法

1:我們?yōu)槭裁匆獙W(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)

任何一門科學(xué)都有其自身的理論基礎(chǔ),計(jì)算機(jī)科學(xué)也是這樣.大家現(xiàn)在看看計(jì)算機(jī)的技術(shù)變化的很快,現(xiàn)在我們很流行的框架和工具很有可能幾年內(nèi)就會(huì)變成過(guò)時(shí)的東西.但是計(jì)算機(jī)科學(xué)的整體的思維不會(huì)變,在學(xué)習(xí)中,我們更要應(yīng)該看思考能力的培養(yǎng),如何清楚的表達(dá)自己的能力,如何清晰地解決問(wèn)題的能力以及自己還欠缺的能力.這方面的東西在我看來(lái),是具有持久的價(jià)值的,學(xué)習(xí)理論能夠拓展人們的思維,并能使人們?cè)谶@方面得到訓(xùn)練.

說(shuō)回形式語(yǔ)言與自動(dòng)機(jī),大家在大學(xué)學(xué)習(xí)中可能離形式語(yǔ)言與自動(dòng)機(jī)的一門課應(yīng)該是<編譯原理>,<編譯原理>中是會(huì)講到形式語(yǔ)言和自動(dòng)機(jī)的部分東西,另外有的學(xué)?？赡芫陀袑ｉT的這一門課,比如北航和哈工大等等.說(shuō)到底,形式語(yǔ)言與自動(dòng)機(jī)其實(shí)是一門將數(shù)學(xué)系統(tǒng)應(yīng)用于計(jì)算的一種模型.所以我想用這一系列文章來(lái)重點(diǎn)介紹形式語(yǔ)言以及與之相對(duì)應(yīng)的自動(dòng)機(jī)體系.

形式語(yǔ)言給出了語(yǔ)言的語(yǔ)法規(guī)則和分類的形式化方法,而自動(dòng)機(jī)則描述了能夠識(shí)別的語(yǔ)言的自動(dòng)裝置.這樣的形式化的描述以及自動(dòng)機(jī)的工作原理將會(huì)是這一系列文章的核心.這一些核心在編譯理論,人工智能,現(xiàn)代安全學(xué)和通信中都有著極強(qiáng)的應(yīng)用,是每個(gè)對(duì)于計(jì)算機(jī)科學(xué)感興趣的人都應(yīng)該熟悉的內(nèi)容.

這一系列文章我現(xiàn)在想先簡(jiǎn)單的分為三大部分:

第一部分是基礎(chǔ)的預(yù)備知識(shí)的學(xué)習(xí)

第二部分是講述四類文法所產(chǎn)生的語(yǔ)言以及這些語(yǔ)言的識(shí)別裝置

第三部分是講述這四類文法的理論在實(shí)際生產(chǎn)中的應(yīng)用

但是上述的理論可能會(huì)比較枯燥,所以我也想大家有興趣可以配合蔣宗禮老師的<形式語(yǔ)言與自動(dòng)機(jī)理論>,加上上邊的習(xí)題,效果會(huì)更好,更加的容易理解和接受.

2:什么是形式語(yǔ)言與自動(dòng)機(jī)?

形式語(yǔ)言和自動(dòng)機(jī)的理論是計(jì)算機(jī)科學(xué)的理論基礎(chǔ)。這些理論來(lái)源于 :

(1) Chomsky對(duì)自然語(yǔ)言的研究; (2) 巴科斯和諾爾使用巴科斯-諾爾范式(BNF)對(duì) ALGOL 60 語(yǔ)言的語(yǔ)法規(guī)則進(jìn)行描述; (3) Kleene在研究神經(jīng)細(xì)胞時(shí)建立的自動(dòng)機(jī)模型。 形式語(yǔ)言理論的研究對(duì)象與以前所有語(yǔ)言的研究對(duì)象不同 , 不止是自然語(yǔ)言 , 而是人類的

一切語(yǔ)言 : 既有自然語(yǔ)言 , 也有人工語(yǔ)言 , 包括高級(jí)程序設(shè)計(jì)語(yǔ)言。 形式語(yǔ)言和自動(dòng)機(jī)的理論已經(jīng)成為計(jì)算機(jī)科學(xué) 的理論 基礎(chǔ) , 其 應(yīng)用范 圍已 被擴(kuò)展 到生 物

工程、自動(dòng)控制系統(tǒng)、圖像處理與模式識(shí)別等許多領(lǐng)域。

3:學(xué)習(xí)之前所需要的知識(shí)

在學(xué)習(xí)形式語(yǔ)言之前,我們首先要明確下所需的集合,圖論,邏輯證明這樣的知識(shí),這些知識(shí)難度不會(huì)超過(guò)高等數(shù)學(xué)的難度,如果你已經(jīng)會(huì)了,就直接跳過(guò)去吧,如果不會(huì)就可以繼續(xù)看下去.

1:集合

當(dāng)我們?nèi)パ芯恳活悓?duì)象的時(shí)候,我們可以將具有同一類對(duì)象的整體看作是一個(gè)集合,組成一個(gè)集合的對(duì)象稱為該集合的元素

如果設(shè)A是一個(gè)集合,a是集合A的一個(gè)元素,就可以表示為a∈A,如果a不是集合A的元素,就可以表示a∈|A,也就是a不屬于A

以后我為了省事,比如a屬于A,b屬于A,c屬于A的,都寫成a,b,c∈A.

有限個(gè)元素x1,x2,.......,xn組成的集合,稱為有限集合.無(wú)限個(gè)元素組成的集合,稱為無(wú)限集合.比如,整數(shù)構(gòu)成的集合是一個(gè)無(wú)限集合.

不含元素的集合,稱為空集,符號(hào)是:?

2:集合之間的關(guān)系

(1) 設(shè)兩個(gè)集合A、B包含的元素完全相同,則稱集合A和B

相等,表示為A=B。

例如,集合A={a,b,c},集合B={b,a,c},則有A=B。 這里強(qiáng)調(diào), 一個(gè)集合中元素排列的順序是無(wú)關(guān)緊要的。 有限集合A中不同元素的個(gè)數(shù)稱為集合的基數(shù), 表示為 #A或A。

例如,B={a,b,c,4,8},其基數(shù)#B=5。

(2)設(shè)兩個(gè)集合A、B,當(dāng)A的元素都是B的元素,則稱A包

含于B,或稱A是B的子集,表示為A∈B。當(dāng)A∈B且A≠B, 稱A是B的真子集,表示為A B。

如果所研究的集合皆為某個(gè)集合的子集時(shí) , 稱該集合為全集 , 記為E

(3) 根據(jù)(1)和(2) ,對(duì)于任意兩個(gè)集合A、B,A=B的充要條 件是A∈B且B∈A。

3:冪集

設(shè)A是集合,A的所有子集組成的集合稱為A的冪集,表示 為2A或ρ(A)。

例 如 ,A= {a,b,c} ,

則 有ρ(A) = { ?,{a},{b},{c},{a,b},{b,c}, {a,c},{a,b,c}}

當(dāng)A是 有 限 集 , #A=n, 則 ρ(A) 的 元 素 數(shù) 為C0n+C1n+…+Cn=2n

但是有一個(gè)例外,空集?是任何集合的一個(gè)子集

4:集合的運(yùn)算

( 1 ) 設(shè) 兩 個(gè) 集 合A、B, 由A和B的 所 有 共 同 元 素 構(gòu) 成 的 集 合,稱為A和B的交集,表示為A∩B。

(2) 設(shè)兩個(gè)集合A、B, 所有屬于A或?qū)儆?i>B的元素組成的集 合,稱為A和B的并集,表示為A∪B。

(3) 設(shè)兩個(gè)集合A、B, 所有屬于A而不屬于B的一切元素組 成的集合,稱為B對(duì)A的補(bǔ)集,表示為A-B。

(4) 設(shè)兩個(gè)集合A、B,所有序偶(a,b)組成的集合,稱為A、B的笛卡爾乘積,表示為A×B。

A×B={(a,b)|a∈A且b∈B}

比如:A = {a,b,c},B={0,1},則A*B = {(a,0),(a,1),(b,0), (b,1), (c,0) ,(c,1) }

但是要注意一點(diǎn),序偶的元素排序是有順序的,不能夠隨意的顛倒,(a,b)和(b,a)是不同的兩個(gè)序偶,所以說(shuō)如果兩個(gè)序偶相等, 應(yīng)該是對(duì)應(yīng)元素相同, 例如,(a,b)=(c,d),應(yīng)有a=c和b=d。

對(duì)任意集合A、B、C有如下運(yùn)算律:

(1)A∪A=A,A∩A=A; (2)A∪B=B∪A,A∩B=B∩A;

(3) (A∪B)∪C=A∪(B∪C), (A∩B)∩C=A∩(B∩C);

(4)A∪(B∩C)=(A∪B)∩(A∪C),A∩(B∪C)= (A∩B)∪(A∩C); (5)A∪(A∩B)=A,A∩(A∪B)=A; (6)A∪A=E,A∩A= ? (7)A∪B=A∩B,A∩B=A∪B; (8)E∪A=E,E∩A=A;

(9)A∪? =A,A∩? =?

5:關(guān)系

說(shuō)到關(guān)系,我們平時(shí)用的大于,小于,等于,包括等都是屬于關(guān)系,下面我引用蔣老師的書中的描述來(lái)說(shuō)一下關(guān)系的形式定義:

定義1.1.1 設(shè)A是一個(gè)集合,A×A的一個(gè)子集R,稱為是 集合A上的一個(gè)二元關(guān)系,簡(jiǎn)稱關(guān)系。

對(duì)于a∈A,b∈A,如果(a,b)∈R,稱a和b存在關(guān)系R,表示 為aRb;如果(a,b)∈|R,稱a和b不存在關(guān)系R,表示為a/Rb。

例如 , 自然數(shù)集合N中的大于關(guān)系 , 可表示為 > ={(a,b)|a,b∈N且a>b}

當(dāng)有兩個(gè)集合A、B,則從A到B的關(guān)系是A×B的一個(gè)子集。

定義1.1.2 設(shè)集合A,R是A上的關(guān)系:

對(duì)每個(gè)a∈A,如果有aRa,稱R是自反的; 對(duì) 于a,b∈A, 如 果 有a R b, 又 有b R a, 稱R是 對(duì) 稱 的 ; 對(duì) 于a,b∈A, 如 果 有a R b和b R a, 則 必 有a=b, 稱R是 反對(duì)稱的 ; 對(duì)于a,b,c∈A,如果有aRb和bRc,則有aRc,稱R是傳遞的;對(duì)每個(gè)a∈A,如果a/Ra,稱R是反自反的。

例如 , 數(shù)之間的相等關(guān)系 , 具有自反性、對(duì)稱性和傳遞性 , 小于 關(guān)系和大于關(guān)系沒(méi)有自反性 , 但有傳遞性。

定義1.1.3 設(shè)R是非空集合A上的一個(gè)關(guān)系,如果R有自 反性、對(duì)稱性和傳遞性 , 則稱R是一個(gè)等價(jià)關(guān)系。

由等價(jià)關(guān)系R可以把A分為若干子集, 每個(gè)子集稱為一個(gè)等 價(jià)類 , 同一等價(jià)類中的元素互相是等價(jià)的.

定義1 .1 .4 設(shè)R是集合A上的一個(gè)關(guān)系,如果R有自反性、 反對(duì)稱性和傳遞性,則稱R是偏序關(guān)系(或部分序關(guān)系)。

這個(gè)值得說(shuō)一下,現(xiàn)在套用書中的例子

設(shè)集合C={2,3,6,8},R是集合C上的整除關(guān)系,即R= {(x,y) |x,y∈C且x整除y}

可以得到:

R= {(2,2), (3,3), (6,6), (8,8), (2,6), (2,8), (3,6)}

結(jié)合上面的偏序關(guān)系,我們可以描寫出關(guān)于偏序的圖,叫做哈斯圖,有興趣的可以百度了解下,并不是很重要的東西.

定 義 1 . 1 . 5 設(shè)R是 集 合A上 的 關(guān) 系 , 如 果 另 有 關(guān) 系R′滿 足:

(1)R′是傳遞的(自反的,對(duì)稱的) ; (2)R′R; (3) 對(duì)任何傳遞的(自反的、對(duì)稱的)關(guān)系R′′,當(dāng)有R′′R,就

有R′′R′,則稱關(guān)系R′是R的傳遞(自反、對(duì)稱)閉包。R的自反閉包表示為r(R),R的對(duì)稱閉包表示為s(R),R的

傳遞閉包表示為t(R)。如果給定一個(gè)集合A上的關(guān)系R, 可用以下方法找出傳遞閉

包t(R),自反閉包r(R)和對(duì)稱閉包s(R):

(1)r(R)=R∪IA,其中IA ={(x,x)|x∈A};

(2)s(R)=R∪R-1;

(3)t(R)=R∪R2∪…∪Rn,其#A=n。

舉個(gè)例子:

設(shè)集合A={a,b,c},A上的關(guān)系R={(a,b),(b,b), (b,c)},則R的傳遞閉包為

t(R) = {(a,b) , (b,b) , (b,c) , (a,c)} , 而R的自反傳遞閉包表示為

tr(R) = {(a,a), (a,b) ,(b,b), (b,c), (a,c) ,(c,c)}。 今后用R+ 表示R的傳遞閉包,用R* 表示R的自反傳遞閉包。

定義1.1.6 映射是關(guān)系的一個(gè)特殊類型 , 也稱函數(shù)。設(shè)集合A和B,f是從A到B的一個(gè)關(guān)系,如果

對(duì)每一個(gè)a∈A,有惟一的b∈B,使得(a,b)∈f,稱關(guān)系f是函 數(shù),記為f:A→B。

如果存在(a,b)∈f,則a是f的自變量,b是f作用下的像點(diǎn),因此(a,b)∈f亦可寫成f(a) =b。

由 定 義 1 .1 .6 可 知 , 函 數(shù) 有 如 下 特 點(diǎn) :

(1) 函數(shù)f的定義域是A, 不能是A的某個(gè)真子集。

(2) 一個(gè)a∈A只能對(duì)應(yīng)于惟一的一個(gè)b,或者說(shuō)f(a)是單值的。

f的值域是B的子集,記為Rf。

函數(shù)的幾種特殊類型是 :

(1) 對(duì)于f:A→B。如果f的值域Rf =B,即B的每一個(gè)元素

都是A中一個(gè)或多個(gè)元素的像點(diǎn),則稱f是滿射的。 例如,集合A={a,b,c,d},B={x,y,z},如果f:A→B為:

f(a)=x,f(b)=x,f(c)=y,f(d)=z則f是滿射的。

(2) 對(duì)于f:A→B。如果A中沒(méi)有兩個(gè)元素有相同的象點(diǎn), 則稱f是入射的,即對(duì)于任意a1,a2∈A:

如果a1 ≠a2,則有f(a1)≠f(a2),或者如果f(a1)=f(a2), 則有a1 =a2。

例如,集合A={a,b},B={x,y,z},如果f:A→B為:f(a) =x,f(b)=y,則稱f是入射的。

(3) 對(duì)于f:A→B。如果f既是滿射的,又是入射的,則稱f是雙射的 , 或稱是一一對(duì)應(yīng)的。

例如,集合A={a,b,c},B={1,2,3},

如果f:A→B為f(a) = 3,f(b) = 1,f(c) = 2

則稱f是雙射的,或者說(shuō)是一一對(duì)應(yīng)的。

定義1.1.7 設(shè)非空集合A,∏={π1,π2,…,πn},其中πi n

A,πi≠? (i=1,2,…,n),如果有∪πi=A且πi∩πj=? (i≠j),i=1

則稱∏是A的劃分。其中πi是一個(gè)劃分塊。

例如,集合S={a,b,c,d},考慮下列集合:

A={{a,b},{c,d}}

B= {{a},{b},{c},{d}}C= {{a},{b,c,d}}

D= {{a,b,c,d}}E={{a,b},{b,c,d}}F= {{a,b},{c}}

則A、B、C和D都是S的劃分,E和F則不是S的劃分。

定義1.1.8 設(shè)有集合A、B,如果存在雙射函數(shù)f:A→B,則 說(shuō)A和B有相同的基數(shù),或者說(shuō)A和B等勢(shì),記為A~B。

一個(gè)無(wú)限集 , 存在著它與其自身的一個(gè)真子集有 相 同的基數(shù)。這里Ne 和自然數(shù)集合都是無(wú)限集。

通常 , 考慮一個(gè)無(wú)限集的基數(shù)時(shí) , 總是看它與自然數(shù)集合能否 建立一一對(duì)應(yīng)。能與自然數(shù)集合建立一一對(duì)應(yīng)的無(wú)限集稱為可數(shù)集 ; 不能與自然數(shù)集合建立一一對(duì)應(yīng)的無(wú)限集稱為不可數(shù)集。

例如:整數(shù)集合是可數(shù)集; 集合{1, 3, 5, 7, …}是可數(shù)集; 實(shí)數(shù) 集合R是不可數(shù)集;集合{x|x∈R,0<x<1}是不可數(shù)集,其中R是實(shí)數(shù)。

6:證明和證明方法

形式語(yǔ)言和有限自動(dòng)機(jī),有很強(qiáng)的理論性, 許多的論斷是以定理的形式給出的,而定理的 正確性是需要進(jìn)行證明的。

形式語(yǔ)言和有限自動(dòng)機(jī)理論中定理的證明大多使用反證法和歸納法進(jìn)行。

(1):反證法

反證法也稱為歸謬法。利用反證法證明一個(gè)命題時(shí) , 一般的步驟為 :

假設(shè)該命題不成立; 進(jìn)行一系列的推理; 如果在推理的過(guò)程中,出現(xiàn)了下列情況之一:

1 與已知條件矛盾;

2 與公理矛盾;

3 與已證過(guò)的定理矛盾;

4 與臨時(shí)的假定矛盾;

5 自相矛盾。 由于上述矛盾的出現(xiàn),可以斷言“假設(shè)該命題不成立”的假定是不正確的; 肯定原來(lái)的命題是正確的。

(2)歸納法

歸納法就是從特殊到一般的推理方法。分為完全歸納法和不完全歸納法兩種形式。

完全歸納法是根據(jù)一切情況的分析而作出的 推理。由 于必 須考慮 所有 的情況 , 所 以得 出 的結(jié)論是完全可靠的。

不完全歸納法是根據(jù)一部分情況作出的推理 , 因此 , 不能作為嚴(yán)格的證明方法。 在形式語(yǔ)言與有限自動(dòng)機(jī)理論中 , 大量使用數(shù)學(xué)歸納法證明某個(gè)命題。數(shù) 學(xué) 歸 納 法 可 以 使 用“ 有 限 ”步 驟 來(lái) 解 決“ 無(wú) 限 ”的 問(wèn) 題 。數(shù)學(xué)歸納法的原理為 :

假定對(duì)于一切非負(fù)整數(shù)n, 有一個(gè)命題M(n) , 假設(shè)證明了 :

(1)M(0) 為真; (2) 設(shè)對(duì)于任意的k≥0,M(k) 為真,如果能夠推出M(k+ 1) 為真,則對(duì)一切n≥0,

M(n) 為真。因此,在使用數(shù)學(xué)歸納法證明某個(gè)關(guān)于非負(fù)整數(shù)n的命題P(n) 時(shí),只需要證明(1)、(2)

兩點(diǎn)即可。第(1)步稱為歸納基礎(chǔ), 第(2)步稱為歸納步驟。第(2)步中“設(shè)對(duì)于任意的k≥ 0,M(k) 為 真 ”, 稱 為 歸 納 假 設(shè) 。

在實(shí)際應(yīng)用中,某些命題P(n)并非對(duì)n≥0都成立,而是對(duì)n≥N(N為大于0的某個(gè)自 然數(shù))成立, 此時(shí),也一樣可以使用該歸納法。具體步驟如下。

假定對(duì)于一切非負(fù)整數(shù)n, 有一個(gè)命題M(n), 假設(shè)證明了:

(1)M(N) 為真; (2)設(shè)對(duì)于任意的k≥N,M(k)為真,如果能夠推出M(k+1)為真,則對(duì)一切n≥N,

M(n) 為真。

比如說(shuō)用歸納法證明下遞歸:

歸納法證明遞歸定義集合性質(zhì)的步驟如下。(1) 基礎(chǔ):證明該集合中的最基本元素具有性質(zhì)P; 而且使得該集合非空; (2) 歸納: 證明如果該集合的元素x1 ,x2 ,x3 , …,具有性質(zhì)P, 則使用某種運(yùn)算、函數(shù)或組

合方法對(duì)這些元素進(jìn)行處理后所得的元素也具有性質(zhì)P;

(3) 由歸納法原理,集合中的所有元素也具有性質(zhì)P。

這上述的大概是集合的能夠概括的所有知識(shí)點(diǎn)了,只需要了解即可,在下一篇文章中,將會(huì)描述一下邏輯和圖論的問(wèn)題,然后基礎(chǔ)知識(shí)將很快學(xué)完,開(kāi)始真正有意思的部分