1、計算學科中的數學方法計算學科中的數學方法鄒復好鄒復好:fuhao_計算機科學中的問題求解初探計算機科學中的問題求解初探計算學科中的數學方法計算學科中的數學方法 實際上，凡能被計算機處置的問題均可以轉換為一實際上，凡能被計算機處置的問題均可以轉換為一個數學問題；凡能以離散數學為代表的構造性數學方法個數學問題；凡能以離散數學為代表的構造性數學方法描畫的問題，當該問題所涉及的論域為有窮，或者為無描畫的問題，當該問題所涉及的論域為有窮，或者為無窮但存在有窮表示時，這個問題也一定能用計算機來處窮但存在有窮表示時，這個問題也一定能用計算機來處置。置。引 言 數學有延續數學和離散數學之

2、分，離散數學源于算術，延續數學源于數學有延續數學和離散數學之分，離散數學源于算術，延續數學源于幾何。幾何。 自牛頓開創微積分后，延續數學就以微積分為根底。自牛頓開創微積分后，延續數學就以微積分為根底。 計算學科與物理等學科不同，它的根本問題是計算學科與物理等學科不同，它的根本問題是“能行性問題。能行性問題。“能能行性這個根本問題決議了計算機本身的構造和它處置的對象都是離散行性這個根本問題決議了計算機本身的構造和它處置的對象都是離散型的，而延續型的問題只需經過型的，而延續型的問題只需經過“離散化的處置后才干被計算機處置。離散化的處置后才干被計算機處置。因此，在計算學科中，采用的數學方法，主要是離

3、散數學的方法。因此，在計算學科中，采用的數學方法，主要是離散數學的方法。引 言 在對待數學的問題上，計算機科學家與數學家的偏重點在對待數學的問題上，計算機科學家與數學家的偏重點不一樣：不一樣： 數學家關懷的是數學家關懷的是“是什么是什么What is it的問題，重點的問題，重點放在數學本身的性質上；放在數學本身的性質上； 計算機科學家那么不同，他們不僅要知道計算機科學家那么不同，他們不僅要知道“是什么的問是什么的問題，更要處理題，更要處理“怎樣做怎樣做How to do it的問題。的問題。在計算領域，人們發明了基于離散數學的在計算領域，人們發明了基于離散數學的“詳細數學的詳細數學的大量概念

4、和方法如學科中的各種方式化方法。大量概念和方法如學科中的各種方式化方法。一、數學的根本特征及數學方法的作用一、數學的根本特征及數學方法的作用高度籠統高度籠統邏輯嚴密邏輯嚴密普遍適用普遍適用l 為科學技術研討提供簡約準確的方式化言語為科學技術研討提供簡約準確的方式化言語l 為科學技術研討提供數量分析和計算的方法為科學技術研討提供數量分析和計算的方法l 為科學技術研討提供邏輯推理的工具為科學技術研討提供邏輯推理的工具二、計算學科中常用的數學概念和術語二、計算學科中常用的數學概念和術語 集合集合 函數和關系函數和關系謂詞和布爾邏輯謂詞和布爾邏輯字母表、字符串和言語字母表、字符串和言語定義、定理和證明

5、定義、定理和證明 論域：一定場所語境中思索和議論所涉論域：一定場所語境中思索和議論所涉及的對象的范圍。即某一范圍內被論及對象及的對象的范圍。即某一范圍內被論及對象的全部所構成的集合。的全部所構成的集合。1 1集合的概念集合的概念集合是數學的根本概念，它是構造性數學集合是數學的根本概念，它是構造性數學方法的根底。方法的根底。 集合就是一組無反復的對象的全體。集集合就是一組無反復的對象的全體。集合中的對象稱為集合的元素。合中的對象稱為集合的元素。 如：計算機專業學生全部必修課程可以如：計算機專業學生全部必修課程可以組成一個集合，其中的每門課程就是這一集組成一個集合，其中的每門課程就是這一集合中的元

6、素。合中的元素。一集合一集合集合集合 2 2集合的描畫方法集合的描畫方法通常用大寫字母表示集合，用小寫字母表示元素，描畫通常用大寫字母表示集合，用小寫字母表示元素，描畫集合的方式主要有以下集合的方式主要有以下3 3種：種：1 1枚舉法：列出一切元素的表示方法。枚舉法：列出一切元素的表示方法。如如1 1至至5 5的整數集合可表示為：的整數集合可表示為：A=A=1 1，2 2，3 3，4 4，5 5 ；2 2外延表示法：當集合中所列元素的普通方式很明顯時，外延表示法：當集合中所列元素的普通方式很明顯時，可只列出部分元素，其他那么用省略號表示。可只列出部分元素，其他那么用省略號表示。如斐波那契數列可

7、表示為：如斐波那契數列可表示為： 0 0，1 1，1 1，2 2，3 3，5 5，8 8，1313，2121，3434， ；3 3謂詞表示法：用謂詞來概括集合中元素的屬性。謂詞表示法：用謂詞來概括集合中元素的屬性。如斐波那契數列可表示為：如斐波那契數列可表示為：Fn|Fn+2=Fn+1+FnFn|Fn+2=Fn+1+Fn，F0=0F0=0，F1=1F1=1，n0n0。集合集合 3集合的運算集合的運算 集合的根本運算有并、差、交、補和乘積等運算。集合的根本運算有并、差、交、補和乘積等運算。1集合的并集合的并 設設A、B為兩個恣意集合，一切屬于為兩個恣意集合，一切屬于A或屬于或屬于B的元素構成的集

8、合的元素構成的集合C，稱為，稱為A和和B的并集。可表示為：的并集。可表示為：CABxxAxB，稱為并，稱為并運算。運算。 例例1 假設假設A=a，b，c，d，B=b，d，e，求集合，求集合A和和B的并。的并。 解：解：ABa，b，c，d，e2集合的差集合的差 設設A、B為兩個恣意集合，一切屬于為兩個恣意集合，一切屬于A而不屬于而不屬于B的一切元素構成的集合的一切元素構成的集合S，稱為稱為A和和B的差集。可表示為：的差集。可表示為：S=AB=xxAxB，稱為差，稱為差運算。運算。 例例2 假設假設A=a，b，c，d，B=b，d，e，求集合，求集合A和和B的差。的差。 解：解：AB=a，c集合集合

9、3集合的交集合的交 設設A、B為兩個恣意集合，由和的一切一樣元素構成的集合為兩個恣意集合，由和的一切一樣元素構成的集合C，稱，稱為為A和和B的交集。可表示為：的交集。可表示為：CABxxAxB，稱，稱為交運算。為交運算。例例3 假設假設A=x | x 5，B=x | x 5x | x 1x5 x 14集合的補集合的補 設設I為選集，為選集，A為為I的恣意一子集，的恣意一子集，IA那么為那么為A的補集，記為的補集，記為 。可。可表示為表示為 =IA=xxI，xA求補集的運算稱為補運算。求補集的運算稱為補運算。 例例4 假設假設I=x5x5，A=x0 x1，求，求 。 解：解： =IA=x5x01

10、x5AAAA集合集合5集合的乘積集合的乘積集合集合A1，A2，An的乘積普通用法國數學家笛卡爾的乘積普通用法國數學家笛卡爾Rene Descartes的名字命名，即笛卡爾積。該乘積表示如下：的名字命名，即笛卡爾積。該乘積表示如下：A1A2An=a1，a2，anaiAi，i1，2，nA1A2An的結果是一個有序的結果是一個有序n元組的集合。元組的集合。 例例5 假設假設A=1，2，3，B=a，b，求，求AB。 解：解：AB=1，a，1，b，2，a，2，b，3，a，3，b二函數和關系二函數和關系1函數函數函數又稱映射，是指把輸入轉變成輸出的運算，該運算函數又稱映射，是指把輸入轉變成輸出的運算，該運

11、算也可了解為從某一也可了解為從某一“定義域的對象到某一定義域的對象到某一“值域的對象的值域的對象的映射。映射。 設設f為一個函數，當輸入值為為一個函數，當輸入值為a 時輸出值為時輸出值為b，那么記作：，那么記作：f(a)=b。2關系關系關系是一個謂詞，其定義域為關系是一個謂詞，其定義域為k元組的集合。通常的關系元組的集合。通常的關系為二元關系，其定義域為有序對的集合，通常有序對的第一為二元關系，其定義域為有序對的集合，通常有序對的第一個元素和第二個元素有關系。如學生選課。個元素和第二個元素有關系。如學生選課。函數和關系函數和關系n定義：定義：A1A2 An中的任一子集稱為中的任一子集稱為A1,

12、 A2, , An的一的一個個n元關系。元關系。n 二元關系：二元關系： A1A2 的一個子集，或稱有序對。的一個子集，或稱有序對。n 例例6，選課關系：，選課關系：R=(張張, 文文)，(張張, 哲哲)， (李李, 數數)，(李李, 藝藝)，(王王, 史史)，( 王王, 文文)函數和關系函數和關系n二元關系中的特例：集合二元關系中的特例：集合A上的關系：上的關系：AAnA到到A本身的關系，記為本身的關系，記為A2。n 例例7 A=0, 1, 2, 3，那么，那么n =(0, 0), (0 3), (2 0), (2, 1), (2, 3), (3, 2)是是A上的一個關上的一個關系；系；n

13、AA有有16個元素。個元素。n 例例8 實數集實數集R，1=(x, y)|(x, y) R2, xy, 1是是R上的上的“小小于關系，記為于關系，記為x1y。函數和關系函數和關系給定給定R=1, 2, 3, 4，寫出關系，寫出關系1(xy)和和3(x=y)的元組的元組 。R R=(1,1), (1,2), (1,3), (1,4), (2,1), (2,2), (2,3), (2,4), (3,1), (3,2), (3,3), (3,4) (4,1), (4,2), (4,3), (4,4)1(xy)= (2,1), (3,1), (3,2), (4,1), (4,2), (4,3)3(x=

14、y)= (1,1), (2,2), (3,3), (4,4)n 集合集合A上的關系性質上的關系性質n 設設是集合是集合A上的關系。上的關系。n 假設對于一切的假設對于一切的 a A。有。有aa，那么稱，那么稱是是自反的。自反的。n 對于一切的對于一切的 a, b A，假設每當有，假設每當有ab就有就有ba， n 那么稱那么稱 是對稱的。是對稱的。n 對于一切的對于一切的a, b, c A，假設每當有，假設每當有ab和和bc就有就有n ac，那么稱，那么稱是可傳送的。是可傳送的。函數和關系函數和關系n 等價關系：集合等價關系：集合A上的關系上的關系 ，假設它是自反、，假設它是自反、對稱且可傳送的

15、，那么稱對稱且可傳送的，那么稱為為A上的等價關系。上的等價關系。n 如：集合元素中的相等關系，直線之間的平行關如：集合元素中的相等關系，直線之間的平行關n 系，三角形的類似關系，位于同一條街的居系，三角形的類似關系，位于同一條街的居 民之間的關系等。民之間的關系等。函數和關系函數和關系n 等價類等價類n 設設是是A上的等價關系，假設上的等價關系，假設ab成立，那么成立，那么a等價等價n 于于b在在下。下。n 定義：設定義：設是是A上的等價關系，那么上的等價關系，那么A中等價于中等價于a 的的全全n 體元素的集合稱為體元素的集合稱為a所生成的等價類。所生成的等價類。n 記為記為a=b|bA, a

16、bn 例例9，“同余關系是等價關系同余關系是等價關系n 例例10，“并發關系是非等價關系并發關系是非等價關系n 例例11，“小于關系小于關系不具備自反性和對稱性；不具備自反性和對稱性；“等等于關系于關系具備自反性、對稱性、可傳送。具備自反性、對稱性、可傳送。函數和關系函數和關系p 個體：可以獨立存在的物體。個體：可以獨立存在的物體。p 謂詞：用來描寫個體的性質或關系的詞謂詞：用來描寫個體的性質或關系的詞p 描寫一個個體性質的詞為一元謂詞，描寫幾描寫一個個體性質的詞為一元謂詞，描寫幾個個體之間關系的詞稱為個個體之間關系的詞稱為n元謂詞。元謂詞。1. 謂詞：充任謂語闡明主語謂詞：充任謂語闡明主語“

17、怎樣樣，怎樣樣，“是什么是什么和能同副詞結合的動詞、描畫詞辭海。和能同副詞結合的動詞、描畫詞辭海。 Predicate，謂詞、斷言，謂詞、斷言三謂詞與布爾邏輯三謂詞與布爾邏輯命題邏輯命題邏輯2. 命題邏輯命題邏輯命題：一個能分辨真假的陳說句稱作一個命題。命題：一個能分辨真假的陳說句稱作一個命題。例如例如 地球上海洋面積比陸地大。地球上海洋面積比陸地大。 他喜歡周杰倫的歌嗎？他喜歡周杰倫的歌嗎？ 22 5。 今天天氣太不好啦。今天天氣太不好啦。 2x30。 三角之和小于三角之和小于180度。度。 非命題非命題( (值：真值：真值：假值：假非命題非命題是陳說句，但不能分辨真假，非命題是陳說句，但不

18、能分辨真假，非命題值：假值：假命題邏輯命題邏輯結合詞：結合詞： 合取合取 析取析取 取反取反 蘊含蘊含 等值等值異或異或例，例， 今天下雨。今天下雨。 值為假值為假原子命題經過結合詞組成復合命題。原子命題經過結合詞組成復合命題。命題邏輯命題邏輯關于析取和異或：關于析取和異或： 析取表示析取表示“可兼或可兼或例，例，P P：劉翔是：劉翔是110110米欄冠軍米欄冠軍 Q Q：劉翔是：劉翔是200200米欄冠軍米欄冠軍 P Q P Q 為復合命題，表示為復合命題，表示“劉翔或者是劉翔或者是110110米欄冠軍，米欄冠軍，或者是或者是200200米欄冠軍米欄冠軍例，今天晚上我在家看電視或去劇場看戲。

19、例，今天晚上我在家看電視或去劇場看戲。 P Q P Q？ 不能兼或不能兼或同時成立也為真。同時成立也為真。命題邏輯命題邏輯關于析取和異或：關于析取和異或： 異或：異或：P P和和Q Q相反時，相反時， P Q P Q為真為真可用可用、 來表達來表達普通不將普通不將列為根本結合詞列為根本結合詞命題邏輯命題邏輯關于蘊含：關于蘊含： 蘊含：表示蘊含：表示“假設假設，那么，那么P QP Q，假設，假設P P，那么，那么Q Q。當且僅當當且僅當P P為真，為真，Q Q為假，為假，P QP Q為假。為假。真值表真值表Q Q為真為真命題邏輯命題邏輯例，例， P P：月亮出來了。：月亮出來了。 Q Q：3 3

20、3 39 9。 P Q P Q成立成立 只需后件為真，不論前件是真是假，蘊含均成立。只需后件為真，不論前件是真是假，蘊含均成立。命題邏輯命題邏輯真值表真值表Q Q為假為假例，例，P P：教師教學生，：教師教學生， Q Q：地球今天爆炸：地球今天爆炸 PQ PQ：為假。：為假。例，例，P P：雪是黑的，：雪是黑的， Q Q：太陽從西邊出來：太陽從西邊出來 PQ PQ：假設雪是黑的，太陽就會從西邊出來：假設雪是黑的，太陽就會從西邊出來命題邏輯命題邏輯關于等值：關于等值： 當前件后件取同一值時，等值為真。當前件后件取同一值時，等值為真。真值表真值表 命題：一個能分辯真假的陳說句稱作一個命題命題：一個

21、能分辯真假的陳說句稱作一個命題 量詞：全稱量詞量詞：全稱量詞 ：一切的：一切的 存在量詞存在量詞 ：存在：存在3. 謂詞邏輯：將命題分解為主詞、謂詞和量詞，謂詞邏輯：將命題分解為主詞、謂詞和量詞，研討研討 其方式構造，導出有關的邏輯其方式構造，導出有關的邏輯方式和規方式和規 律的邏輯實際辭海。律的邏輯實際辭海。謂詞邏輯謂詞邏輯謂詞邏輯謂詞邏輯謂詞邏輯與命題邏輯謂詞邏輯與命題邏輯 在命題邏輯中，是把簡單命題作為根本單元或作為在命題邏輯中，是把簡單命題作為根本單元或作為原子命題來對待的，不再對簡單命題的內部構造進展分原子命題來對待的，不再對簡單命題的內部構造進展分析。析。 謂詞邏輯引入謂詞和量詞對

22、簡單命題做了進一步分謂詞邏輯引入謂詞和量詞對簡單命題做了進一步分析。析。 商定以小寫字母表示命題、函數，而以大寫字母來商定以小寫字母表示命題、函數，而以大寫字母來表示謂詞。表示謂詞。 本課程限于一階謂詞邏輯或稱狹義謂詞邏輯。本課程限于一階謂詞邏輯或稱狹義謂詞邏輯。謂詞邏輯謂詞邏輯例例 張三是學生李四是學生張三是學生李四是學生1 1 在命題邏輯里，這是兩個不同的命題，只能分別以兩在命題邏輯里，這是兩個不同的命題，只能分別以兩個不同的符號表示。個不同的符號表示。2 2然而它們都有主詞和謂詞。主詞然而它們都有主詞和謂詞。主詞“張三、張三、“李四不同。李四不同。謂詞謂詞“是學生是一樣的。假設以大寫符號

23、是學生是一樣的。假設以大寫符號P P表示表示“是學生，是學生，便可把這兩個命題分別寫成便可把這兩個命題分別寫成P(P(張三張三) ) 和和P(P(李四李四) )3 3普通地，可引入變量普通地，可引入變量x x來表示主詞，于是符號來表示主詞，于是符號P(x)P(x)就表就表示示“x x是學生通常把是學生通常把P(x)P(x)稱作謂詞稱作謂詞個體與謂詞個體與謂詞1 1個體個體 ：個體是指研討對象中不依賴于人的客觀而獨立存：個體是指研討對象中不依賴于人的客觀而獨立存在的詳細的或籠統的客觀實體在的詳細的或籠統的客觀實體 個體常項或個體常元個體常項或個體常元 ； 個體變項或個體變元個體變項或個體變元 ；

24、 個體域或論域個體域或論域 。2 2謂詞：用來描寫個體詞的性質或個體詞之間關系的詞。普謂詞：用來描寫個體詞的性質或個體詞之間關系的詞。普通來說，通來說，“x x是是A A類型的命題可以用類型的命題可以用A Ax x表達。對于表達。對于“x x大于大于y y這種兩個個體之間關系的命題，可表達為這種兩個個體之間關系的命題，可表達為B Bx x，y y，這，這里里B B表示表示“大于大于謂詞。謂詞。 把把A Ax x稱為一元謂詞，稱為一元謂詞，B Bx x，y y稱為二元謂詞，稱為二元謂詞，M Ma a，b b，c c稱為三元謂詞，依次類推，通常把二元以上謂詞稱作多元稱為三元謂詞，依次類推，通常把二

25、元以上謂詞稱作多元謂詞。謂詞。 謂詞邏輯謂詞邏輯符號化符號化 D(x): D謂詞，謂詞，x個體個體 例：例：D張三：張三是要死的張三：張三是要死的D謂詞：要死謂詞：要死的的 Dx：人是要死的：人是要死的x是人是人 量詞量詞1 1全稱量詞全稱量詞例：例：“凡事物都是運動的。這命題中的凡事物都是運動的。這命題中的“凡凡 是表示是表示個體變元數量的詞，個體變元數量的詞，“凡的等義詞有凡的等義詞有“一切的、一切的、“切的、切的、“任任個、個、“每一個，它是全稱量詞。每一個，它是全稱量詞。符號符號:(:(x)x)讀作一切的讀作一切的x x或任一或任一x x，一切，一切x x，而，而就稱就稱為全稱量詞，它

26、所約束的個體是為全稱量詞，它所約束的個體是x x。定義：命題定義：命題( (x)P(x)x)P(x)當且僅當對論域中的一切當且僅當對論域中的一切x x來說，來說，P(x)P(x)均為真時方為真。均為真時方為真。 ( (x)P(x)x)P(x)也寫為也寫為( (x)(P(x)x)(P(x) 留意留意( (x)(P(x)x)(P(x)Q(x)Q(x) ( (x)P(x)x)P(x)Q(x)Q(x) 量詞的運算優先級高于邏輯結合詞量詞的運算優先級高于邏輯結合詞性質性質:(:(x)Q(x)x)Q(x)F F，當且僅當對一切的，當且僅當對一切的x xD D都有都有Q(x)Q(x)F F。量詞量詞2 2存

27、在量詞存在量詞例：例：“有的事物是動物。這命題中有的事物是動物。這命題中“有的就是表示有的就是表示個體變元數量的詞，個體變元數量的詞，“有的的等義詞有有的的等義詞有“存在一個存在一個、“有一個、有一個、“有些它是存在量詞。有些它是存在量詞。符號符號:(:(x)x)讀作至少有一個讀作至少有一個x x或存在或存在個個x x或有某些或有某些x x而而就是對個體詞起約束作用的存在量詞，所就是對個體詞起約束作用的存在量詞，所約束的變元是約束的變元是x x。定義：命題定義：命題( (x)Q(x)x)Q(x)當且僅當在論域中至少有一個當且僅當在論域中至少有一個x0 x0，Q(x0)Q(x0)為真時方為真。為

28、真時方為真。( (x)Q(x)x)Q(x)也寫為也寫為( (x)(Q(x)x)(Q(x)留意留意( (x)(P(x)x)(P(x)Q(x)Q(x) ( (x)P(x)x)P(x)Q(x)Q(x)性質性質: (: (x)P(x)x)P(x)F F成立，當且僅當有一個成立，當且僅當有一個x0 x0 D D ，使使P(x0P(x0D)D)F F謂詞邏輯謂詞邏輯量詞：量詞： 一切的；一切的； 存在存在 x(D(x)x(D(x)：凡人必死：凡人必死 x(G(x)x(G(x)：某些人活到：某些人活到100100歲歲例，例，M(x)M(x)：x x是人，是人，D(x)D(x)：x x是要死的是要死的 x(M

29、(x)D(x)x(M(x)D(x)：例，例，P(x)P(x)：x x是蘋果，是蘋果，S(x)S(x)：x x是紅色的是紅色的 x(P(x)S(x)x(P(x)S(x)： x(P(x)S(x)x(P(x)S(x)：T TT TT TT TF F謂詞邏輯謂詞邏輯例，例，A(x)A(x)：x x是球，是球，B(x)B(x)：x x是圓的是圓的 x(A(x) B(x)x(A(x) B(x)：F F例，例，D(x)D(x)：x x是狗，是狗，P(x)P(x)：x x會叫，會叫，Q(x)Q(x)：x x咬人咬人 x(D(x) P(x) x(D(x) P(x) Q(x)Q(x)存在一條會叫不咬人的狗，即會叫

30、的狗不一定咬人存在一條會叫不咬人的狗，即會叫的狗不一定咬人 x(x(Q(x) P(x) Q(x)Q(x) P(x) Q(x)謂詞邏輯謂詞邏輯例，例， 將以下命題符號化，并指出真值情況。將以下命題符號化，并指出真值情況。1沒有人登上過月球。沒有人登上過月球。2一切人的頭發未必都是黑色的。一切人的頭發未必都是黑色的。解：個體域為全總個體域，令解：個體域為全總個體域，令Mx：x是人。是人。1令令Fx：x登上過月球。命題登上過月球。命題1符號化為：符號化為： xMxFx設設a是是1969年登上月球完成阿波羅方案的一名美國人，那么年登上月球完成阿波羅方案的一名美國人，那么MaFa為真，故命題為真，故命題

31、1為假。為假。2令令Hx：x的頭發是黑色的。命題的頭發是黑色的。命題2可符號化為：可符號化為： xMxHx我們知道有的人頭發是褐色的，所以我們知道有的人頭發是褐色的，所以xMxHx為假，故命題為假，故命題2為真。為真。 謂詞邏輯謂詞邏輯例，將以下命題符號化。例，將以下命題符號化。1 1貓比老鼠跑得快。貓比老鼠跑得快。2 2有的貓比一切老鼠跑得快。有的貓比一切老鼠跑得快。3 3并不是一切的貓比老鼠跑得快。并不是一切的貓比老鼠跑得快。4 4不存在跑得同樣快的兩只貓。不存在跑得同樣快的兩只貓。解：設個體域為全總個體域。令解：設個體域為全總個體域。令C Cx x：x x是貓；是貓；M My y：y y

32、是是老鼠；老鼠；Q Qx x，y y：x x比比y y跑得快；跑得快；L Lx x，y y：x x和和y y跑得同樣跑得同樣快。快。這這4 4個命題分別符號化為：個命題分別符號化為：1 1x x y yC Cx xMMy yQ Qx x，y y；2 2x xC Cx xy yM My yQ Qx x，y y；3 3x x y yC Cx xMMy yQ Qx x，y y；4 4x x y yC Cx xCCy yLLx x，y y。4. 字母表、字符串和言語字母表、字符串和言語1字母表2字符串3言語：給定字母表上的字符串的集合集合運算、閉包運算言語、文法與自動機言語由文法產生自動機是識別言語的數學模型5. 定義、定理和證明定義、定理和證明 1定義：定義是蘊含在公理系統之中的概念和命題。2定理：定理是被證明為真的數學命題。3證明：證明是為使人們確信一個命題為真，而作的一種邏輯論證。三、證明方法三、證明方法直