【文章內容簡介】 理論知識出發(fā)，去認識個別的、特殊的現(xiàn)象的一種邏輯推理方法。 演繹的基本形式是三段論。 ?歸納 是根據(jù)個別的、特殊的現(xiàn)象，得到普遍性知識的邏輯推理方法。 歸納法 歸納法是從 特殊到一般 的邏輯推理方法。 分為 完全歸納法 和 不完全歸納法 兩種形式。 完全歸納法是根據(jù) 一切情況的分析而作出的推理 。 由于必須考慮所有的情況 ，得出的結論是 完全可靠 的 。 歸納法（續(xù)） 不完全歸納法是根據(jù) 一部分情況作出的推理 。 不能作為嚴格的證明方法 。 在自動機理論中 ， 普遍使用 數(shù)學歸納法 證明某個命題 。 數(shù)學歸納法 可以使用 “ 有限步驟 ” 解決 “ 無限 ” 問題 。 數(shù)學歸納法 對于一切非負整數(shù) n的 命題 M(n) (1) M(0)為真 ； (2) 假設對于任意的 k ? 0， M(k)為真，能夠證明 M(k + 1)為真 (3)則 對一切 n ? 0， M(n)為真。 第 (1)步稱為 歸納基礎 第 (2) 步稱為 歸納步驟 第 (2)步中“設對于任意的 k ? 0，M(k)為真”，稱為歸納假設 數(shù)學歸納法的簡化 對于 0，證明結論成立； 假設結論對于 n成立，證明結論對于 n＋１成立。 集合遞歸定義與歸納證明 遞歸定義 (1) 基礎 (2) 歸納 (3) 極小性限定 (有限性 ) 遞歸定義集合 步驟 (1)基礎： 首先定義該集合中最基本的元素 x1, x2, x3, … xm (2)歸納： 對于該集合中的元素 x1, x2, x3, … xn 使用某種 組合方法 對這些元素進行處理后所得的新元素在該集合中 (3)有限性： 只有滿足 (1)和 (2)的元素才在集合中 遞歸定義集合的優(yōu)點 除集合的基本元素 (直接定義 )外 集合中的元素的產(chǎn)生遵從相同的規(guī)律 。 例 16 Fibonacci數(shù) Fibonacci數(shù)組成的集合為： {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …} (1)基礎： 0和 1是最基本的兩個元素； (2)歸納： 若 m是第 i個元素 ,n是第 i+1個元素 則第 i + 2個元素為 n + m。 (3)只有滿足 (1)和 (2)的數(shù) ， 才是集合的元素 例 括號匹配的串構成的集合的定義 {( ),( )( ),( ( ) ), … } （ 1） 基礎： ( )是最基本的串 （ 2） 歸納： 若 S是括號匹配的串 ,則 (S)是括號匹配的串 若 S是括號匹配的串 ,則 SS是括號匹配的串 練習 給出下列計算的遞歸定義 字符串的 倒序 圖與樹 無向圖 有向圖 樹 圖 現(xiàn)實世界中 ， 許多問題可以抽象成 圖 來表示 。 直觀地 ， 圖是由一些 點 和連接兩點的 邊 組成的 。 定義 110無向圖 設 V是一個非空的有窮集合 E ? V ? V 稱 G = (V, E)為一個無向圖 。 其中 ， V稱為頂點集 E稱為無向邊集 無向圖中的邊都 沒有方向 (vi, vj)和 (vj, vi)表示的是同一條邊 無向圖頂點的度 : 該頂點 相關聯(lián) 的邊的條數(shù) 記為 deg(v)， 其中： v ? V 練習 ? 設 G = (V， E)為一個無向圖，則 ||2)de g ( EvVv???數(shù)學歸納法 證明： (1)基礎。 當圖 |E|=0時，圖中各結點的度均為 0，因此 0||2)d e g ( ????EvVv(2)歸納。 假設 |E|=n時結論成立 |E|=n+1時，圖添加一條邊 令為 (vi,vj)。 則 deg(vi)， deg(vj) 都 增加 1 而其它結點的度保持不變 因此在新圖中仍有 ||2)de g ( EvVv???(3)由歸納法原理 結論對任意無向圖成立。 例 V = {v1, v2, v3, v4, v5} E = {(v1, v2), (v1, v3), (v1, v4), (v2, v3), (v2, v5), (v3, v4), (v3, v5), (v4, v5)} deg(v1) = deg(v2) =deg(v4) = deg(v5) = 3 deg(v3) = 4 v1 v2 v3 v4 v5 有向圖 (vi, vj)表示的是從 前導 vi出發(fā) ， 到達 后繼 vj的一條邊 。 (vi, vj)和 (vj, vi)表示的是不同邊 有向圖頂點的度： 入 度與 出 度 例 G2 V = {v1, v2, v3, v4, v5} E = {(v1, v2), (v1, v3), (v2, v3), (v3, v4), (v3, v5), (v4, v1),(v4, v5), (v5, v2),(v5, v4)} ideg(v1)= 1,odeg (v1)= 2 ideg(v2) =2, odeg(v2) =1 v1 v2 v3 v4 v5 定義 112 有向路 設 G = (V， E)為一個有向圖 如果對于 0 ? i ? k – 1， 均有 (vi, vi+1) ? E 稱 v0， v1， … ， vk是一條 (有向 )路 有向回路 當 v0 = vk時 稱 為 一條 (有向 )回路 。 思考 ?從 v1到 v4有多少條路 ？ v1 v2 v3 v4 v5 定義 113 樹 設 G = (V, E)為一個有向圖 。 當 G滿足如下條件時 ， 稱 G為一棵 (有向 )樹 ： 1) ?v ? V， v沒有前導 ， 且 v到樹中的其他頂點都有一條有向路 ， 該頂點稱為樹 G的根； 2)每個非根頂點有且僅有一個前導； 3) 每個頂點的后繼按其拓撲關系從左到右排序 。 語言 任意字符的集合是一個 字母表 。 如 26個英文字母表； 10個阿拉伯數(shù)字字母表； 24個希臘字母表；二進制字母表 字母表有 非空性 、 有窮性 、 單一性 一般使用 ∑表示字母表 。 字符串 字母表中的字母按照某種順序排列成的字符的序列 語言 ?字符串的 集合 語言研究的三個方面 1） 如何給出一個 語言的表示 。 對于有窮語言 ， 使用列舉法； 對于無窮語言 ， 需要考慮語言的有窮描述 。 語言研究的三個方面（續(xù)） 2） 對于一個給定的無窮語言是否存在 有窮描述 （ 有窮表示 ） 。 注意：并不是所有的無窮語言都存在 有窮表示 。 語言研究的