形式語(yǔ)言與自動(dòng)機(jī)-緒論

1、12022-4-9College of Computer Science & Technology, BUPTFormal Languages and Automata 課程名稱(chēng)課程名稱(chēng) 形式語(yǔ)言與自動(dòng)機(jī)形式語(yǔ)言與自動(dòng)機(jī) 教師姓名教師姓名 楊娟楊娟（計(jì)算機(jī)學(xué)院（計(jì)算機(jī)學(xué)院 軟件工程中心）軟件工程中心） 電話電話 6228 3778 信箱信箱 助教助教 徐晨陽(yáng)徐晨陽(yáng) 彭爽彭爽 22022-4-9College of Computer Science & Technology, BUPT緒論緒論n 課程信息課程信息n 為什么學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)為什么學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)n 形式語(yǔ)言

2、與自動(dòng)機(jī)概述及應(yīng)用形式語(yǔ)言與自動(dòng)機(jī)概述及應(yīng)用n 課程內(nèi)容及要求課程內(nèi)容及要求32022-4-9College of Computer Science & Technology, BUPT 專(zhuān)業(yè)基礎(chǔ)課專(zhuān)業(yè)基礎(chǔ)課 - 上世紀(jì)上世紀(jì) 60 60 年代末、年代末、7070年代初，年代初，研究的高峰研究的高峰- 之后，向應(yīng)用領(lǐng)域滲透，之后，向應(yīng)用領(lǐng)域滲透，研究生課程研究生課程- 逐漸普及，逐漸普及，本科階段的專(zhuān)業(yè)基礎(chǔ)課本科階段的專(zhuān)業(yè)基礎(chǔ)課 專(zhuān)業(yè)工作者必須的理論素養(yǎng)專(zhuān)業(yè)工作者必須的理論素養(yǎng) - 計(jì)算模型計(jì)算模型 計(jì)算機(jī)（不）能夠做什么計(jì)算機(jī)（不）能夠做什么 - 問(wèn)題分類(lèi)問(wèn)題分類(lèi) 計(jì)算的復(fù)雜性，算法

3、分析計(jì)算的復(fù)雜性，算法分析 - 形式系統(tǒng)形式系統(tǒng) 建模工具（狀態(tài)機(jī)建模工具（狀態(tài)機(jī) ）- 抽象描述抽象描述 形式文法、形式表達(dá)式形式文法、形式表達(dá)式 課課 程程 性性 質(zhì)質(zhì)42022-4-9College of Computer Science & Technology, BUPT相 關(guān) 課 程先修課程先修課程 - 離散數(shù)學(xué)離散數(shù)學(xué)（數(shù)理邏輯，集合論）（數(shù)理邏輯，集合論）- 計(jì)算機(jī)導(dǎo)論與程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)導(dǎo)論與程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu) 后續(xù)課程后續(xù)課程 - 編譯原理編譯原理 其它相關(guān)課程其它相關(guān)課程 模式識(shí)別、算法分析模式識(shí)別、算法分析 52022-4-9College of Comp

4、uter Science & Technology, BUPTn教材教材：形式語(yǔ)言與自動(dòng)機(jī)形式語(yǔ)言與自動(dòng)機(jī) 王柏王柏 楊娟楊娟 編著編著 北京郵電大學(xué)出版社北京郵電大學(xué)出版社 2003.162022-4-9College of Computer Science & Technology, BUPT 經(jīng) 典 參 考 書(shū) 書(shū)名書(shū)名 Introduction to Automata Theory, Languages, and Computation （Second Edition） 作者作者 John E. Hopcroft （Cornell） Rajeev Motwani （St

5、anford） Jefferey D. Ullman （Stanford） 出版社出版社 Addison Wesley （2001） 清華大學(xué)出版社清華大學(xué)出版社 （影印版）（影印版） First Edition 中譯本中譯本自動(dòng)機(jī)理論、語(yǔ)言和自動(dòng)機(jī)理論、語(yǔ)言和計(jì)算導(dǎo)引計(jì)算導(dǎo)引 徐美瑞徐美瑞 等譯等譯 科學(xué)出版社，科學(xué)出版社，1990 John.E.Hopcroft,the Turing Awardwinner in 1986.72022-4-9College of Computer Science & Technology, BUPT 其它參 考 書(shū) 自動(dòng)機(jī)理論及其應(yīng)用自動(dòng)機(jī)理論及其

6、應(yīng)用 何成武何成武 科學(xué)出版社科學(xué)出版社19901990形式語(yǔ)言及其句法分析形式語(yǔ)言及其句法分析 美美A.V. A.V. 阿霍阿霍 等等 科學(xué)出版社科學(xué)出版社1987 1987 形式語(yǔ)言形式語(yǔ)言 王兵山，吳兵王兵山，吳兵 編編 國(guó)防工業(yè)大學(xué)出版社，國(guó)防工業(yè)大學(xué)出版社，19881988 形式語(yǔ)言與自動(dòng)機(jī)理論形式語(yǔ)言與自動(dòng)機(jī)理論 蔣宗禮，姜守旭蔣宗禮，姜守旭. . 清華大學(xué)出版社，清華大學(xué)出版社，20032003形式語(yǔ)言與自動(dòng)機(jī)形式語(yǔ)言與自動(dòng)機(jī) 陳有祺陳有祺 編著編著 機(jī)械工業(yè)出版社，機(jī)械工業(yè)出版社，20082008 82022-4-9College of Computer Science &am

7、p; Technology, BUPT為什么學(xué)習(xí)形式語(yǔ)言與自動(dòng)機(jī)n形式語(yǔ)言與自動(dòng)機(jī)是計(jì)算機(jī)科學(xué)的基礎(chǔ)理論形式語(yǔ)言與自動(dòng)機(jī)是計(jì)算機(jī)科學(xué)的基礎(chǔ)理論之一，是計(jì)算機(jī)學(xué)科的專(zhuān)業(yè)基礎(chǔ)課。之一，是計(jì)算機(jī)學(xué)科的專(zhuān)業(yè)基礎(chǔ)課。n在人工智能、電信領(lǐng)域等有廣泛的應(yīng)用。在人工智能、電信領(lǐng)域等有廣泛的應(yīng)用。n通過(guò)一些定理的證明和應(yīng)用，對(duì)大家進(jìn)行思通過(guò)一些定理的證明和應(yīng)用，對(duì)大家進(jìn)行思維訓(xùn)練，從而為今后學(xué)習(xí)通信軟件，協(xié)議工維訓(xùn)練，從而為今后學(xué)習(xí)通信軟件，協(xié)議工程，編譯技術(shù)，人工智能等內(nèi)容提供理論基程，編譯技術(shù)，人工智能等內(nèi)容提供理論基礎(chǔ)。礎(chǔ)。92022-4-9College of Computer Science &

8、; Technology, BUPTn對(duì)客觀世界的科學(xué)研究：目的在于把抽象數(shù)對(duì)客觀世界的科學(xué)研究：目的在于把抽象數(shù)學(xué)的形式化體系發(fā)展成為與現(xiàn)實(shí)生活相似的學(xué)的形式化體系發(fā)展成為與現(xiàn)實(shí)生活相似的理論模型，從而提供一種通用結(jié)構(gòu)來(lái)描述、理論模型，從而提供一種通用結(jié)構(gòu)來(lái)描述、理解和解決問(wèn)題。理解和解決問(wèn)題。n計(jì)算機(jī)科學(xué)：是關(guān)于計(jì)算知識(shí)的有系統(tǒng)的整計(jì)算機(jī)科學(xué)：是關(guān)于計(jì)算知識(shí)的有系統(tǒng)的整體。體。102022-4-9College of Computer Science & Technology, BUPTn計(jì)算機(jī)科學(xué)的兩個(gè)主要部分：n構(gòu)成計(jì)算基礎(chǔ)的一些基本概念和模型；n設(shè)計(jì)計(jì)算系統(tǒng)(軟件和硬件)的工

9、程技術(shù)（設(shè)計(jì)理論的應(yīng)用）n本課程著重介紹第一部分（涉及到一些第二部分的應(yīng)用），通過(guò)形式化技術(shù)對(duì)大家進(jìn)行思維訓(xùn)練，為今后的學(xué)習(xí)打好理論基礎(chǔ)。n4 4種基本的專(zhuān)業(yè)能力種基本的專(zhuān)業(yè)能力n計(jì)算思維能力計(jì)算思維能力n算法的設(shè)計(jì)與分析能力算法的設(shè)計(jì)與分析能力n程序設(shè)計(jì)和實(shí)現(xiàn)能力程序設(shè)計(jì)和實(shí)現(xiàn)能力n計(jì)算機(jī)軟硬件系統(tǒng)的認(rèn)知、分析、設(shè)計(jì)與應(yīng)用能力計(jì)算機(jī)軟硬件系統(tǒng)的認(rèn)知、分析、設(shè)計(jì)與應(yīng)用能力n計(jì)算思維能力計(jì)算思維能力n邏輯思維能力和抽象思維能力邏輯思維能力和抽象思維能力n構(gòu)造模型對(duì)問(wèn)題進(jìn)行形式化描述構(gòu)造模型對(duì)問(wèn)題進(jìn)行形式化描述n理解和處理形式模型理解和處理形式模型112022-4-9122022-4-9Colle

10、ge of Computer Science & Technology, BUPT2022-4-913n能力能力n培養(yǎng)學(xué)生的形式化描述和抽象思維能力。培養(yǎng)學(xué)生的形式化描述和抽象思維能力。n使學(xué)生了解和初步掌握使學(xué)生了解和初步掌握“問(wèn)題、形式化描述、自問(wèn)題、形式化描述、自動(dòng)化（計(jì)算機(jī)化）動(dòng)化（計(jì)算機(jī)化）”這一最典型的計(jì)算機(jī)問(wèn)題求這一最典型的計(jì)算機(jī)問(wèn)題求解思路。解思路。 形式語(yǔ)言與自動(dòng)機(jī)概述及應(yīng)用n本門(mén)課程將圍繞著什么是形式語(yǔ)言、什么是自動(dòng)機(jī)、以及形式語(yǔ)言和自動(dòng)機(jī)的相互關(guān)系進(jìn)行闡述。n核心內(nèi)容核心內(nèi)容n有限狀態(tài)自動(dòng)機(jī)，正規(guī)語(yǔ)言，正規(guī)表達(dá)式有限狀態(tài)自動(dòng)機(jī)，正規(guī)語(yǔ)言，正規(guī)表達(dá)式n上下文無(wú)關(guān)文法

11、，上下文無(wú)關(guān)語(yǔ)言，下推自動(dòng)機(jī)上下文無(wú)關(guān)文法，上下文無(wú)關(guān)語(yǔ)言，下推自動(dòng)機(jī)n 圖靈機(jī)，計(jì)算問(wèn)題分類(lèi)圖靈機(jī)，計(jì)算問(wèn)題分類(lèi)142022-4-9College of Computer Science & Technology, BUPT152022-4-9College of Computer Science & Technology, BUPT1形式語(yǔ)言n什么是形式語(yǔ)言什么是形式語(yǔ)言n形式語(yǔ)言: 形式化描述的字母表上的字符串的集形式化描述的字母表上的字符串的集合。合。n字母表：字符的有限集合。ne.g.：26個(gè)英文字母構(gòu)成的字母表。n字符串：字母表中的字符構(gòu)成的有限序列。ne.g. h

12、ello, afjhkfyu 162022-4-9College of Computer Science & Technology, BUPT為什么用形式語(yǔ)言為什么用形式語(yǔ)言n自然語(yǔ)言自然語(yǔ)言：人們平時(shí)說(shuō)話時(shí)所使用的一種語(yǔ)：人們平時(shí)說(shuō)話時(shí)所使用的一種語(yǔ)言，不同的國(guó)家和民族有著不同的語(yǔ)言。言，不同的國(guó)家和民族有著不同的語(yǔ)言。n形式語(yǔ)言形式語(yǔ)言n通過(guò)人們公認(rèn)的符號(hào)，表達(dá)方式所描述的通過(guò)人們公認(rèn)的符號(hào)，表達(dá)方式所描述的一種語(yǔ)言，是一種通用語(yǔ)言，沒(méi)有國(guó)籍之一種語(yǔ)言，是一種通用語(yǔ)言，沒(méi)有國(guó)籍之分。分。n形式語(yǔ)言是某個(gè)字母表上的字符串的集合，形式語(yǔ)言是某個(gè)字母表上的字符串的集合，有一定的描述范圍。

13、有一定的描述范圍。172022-4-9College of Computer Science & Technology, BUPTn例例1： 漢語(yǔ)：漢語(yǔ)： 用數(shù)用數(shù)字、符號(hào)等形式化的東西來(lái)描述語(yǔ)言字、符號(hào)等形式化的東西來(lái)描述語(yǔ)言n我吃飯我吃飯 語(yǔ)法正確語(yǔ)法正確n我飯吃我飯吃 語(yǔ)法錯(cuò)誤語(yǔ)法錯(cuò)誤n飯吃我飯吃我 語(yǔ)法正確，語(yǔ)義錯(cuò)誤語(yǔ)法正確，語(yǔ)義錯(cuò)誤182022-4-9College of Computer Science & Technology, BUPTn例2：T為PASCAL語(yǔ)言所用的全部符號(hào)的集合。n正確的PASCAL程序就是T上的語(yǔ)言。n例3：在字母表T=a上，L = a

14、2n+1 | n =0 n表示任意一對(duì)aa (包括0對(duì)) 后跟一個(gè)a的字符串。（即含有奇數(shù)個(gè)a的字符串。）192022-4-9College of Computer Science & Technology, BUPTn形式語(yǔ)言的最初起因： 語(yǔ)言學(xué)家（Chomsky）想用一套形式化方法來(lái)描述語(yǔ)言。n形式語(yǔ)言在自然語(yǔ)言研究中起步，在計(jì)算機(jī)科學(xué)中得到廣泛應(yīng)用。n最初的應(yīng)用：編譯 讓計(jì)算機(jī)按照語(yǔ)法規(guī)則將高級(jí)語(yǔ)言方便地翻譯成機(jī)器語(yǔ)言。202022-4-9College of Computer Science & Technology, BUPTn現(xiàn)在： 已廣泛應(yīng)用在人工智能、圖象處理、

15、通信協(xié)議、通信軟件等多個(gè)領(lǐng)域n在計(jì)算機(jī)理論科學(xué)方面： 是可計(jì)算理論（算法在有限步驟內(nèi)求得解、算法復(fù)雜性、停機(jī)問(wèn)題、）、定理自動(dòng)證明、程序轉(zhuǎn)換（程序自動(dòng)生成）、模式識(shí)別等的基礎(chǔ)。212022-4-9College of Computer Science & Technology, BUPTn比爾.蓋茨：人類(lèi)計(jì)算的未來(lái)是讓計(jì)算機(jī)能夠看、聽(tīng)、學(xué)，能用自然語(yǔ)言與人類(lèi)交流 n形式化非常重要n例1：微軟對(duì)聯(lián)軟件網(wǎng)址：網(wǎng)址：http:/ of Computer Science & Technology, BUPT圖靈測(cè)試圖靈測(cè)試 (1)n問(wèn)：請(qǐng)給我寫(xiě)出有關(guān)“第四號(hào)橋”主題的十四行詩(shī)。n答：不

16、要問(wèn)我這道題，我從來(lái)不會(huì)寫(xiě)詩(shī)。n問(wèn)：34957加70764等于多少？n答：（停30秒后）105721n問(wèn)：你會(huì)下國(guó)際象棋嗎？n答：是的。n問(wèn)：我在我的K1處有棋子K；你僅在K6處有棋子K，在R1處有棋子R?，F(xiàn)在輪到你走，你應(yīng)該下那步棋？n答：（停15秒鐘后）棋子R走到R8處，將軍！232022-4-9College of Computer Science & Technology, BUPT圖靈測(cè)試圖靈測(cè)試 (2)n問(wèn)：你會(huì)下國(guó)際象棋嗎？n答：是的。n問(wèn)：你會(huì)下國(guó)際象棋嗎？n答：是的。n問(wèn)：請(qǐng)?jiān)俅位卮?，你?huì)下國(guó)際象棋嗎？n答：是的。242022-4-9College of Comput

17、er Science & Technology, BUPT圖靈測(cè)試圖靈測(cè)試 (3)n問(wèn)：你會(huì)下國(guó)際象棋嗎？n答：是的。n問(wèn)：你會(huì)下國(guó)際象棋嗎？n答：是的，我不是已經(jīng)說(shuō)過(guò)了嗎？n問(wèn)：請(qǐng)?jiān)俅位卮?，你?huì)下國(guó)際象棋嗎？n答：你煩不煩，干嘛老提同樣的問(wèn)題。25College of Computer Science & Technology, BUPT在線圖靈測(cè)試網(wǎng)址在線圖靈測(cè)試網(wǎng)址nElbothttp:/ of Computer Science & Technology, BUPT 2. 自動(dòng)機(jī)自動(dòng)機(jī)n什么是自動(dòng)機(jī)？具有離散輸入輸出的數(shù)學(xué)模型。n大量通信軟件的基本工作機(jī)制都是有限

18、狀態(tài)自動(dòng)機(jī)。自動(dòng)機(jī)理論在通信領(lǐng)域中的應(yīng)用極為廣泛。272022-4-9College of Computer Science & Technology, BUPTn自動(dòng)機(jī)接受一定的輸入，執(zhí)行一定的動(dòng)作，產(chǎn)生一定的結(jié)果。使用狀態(tài)遷移描述整個(gè)工作過(guò)程。n狀態(tài)狀態(tài)：一個(gè)標(biāo)識(shí)，能區(qū)分自動(dòng)機(jī)在不同時(shí)刻的狀況。有限狀態(tài)系統(tǒng)具有任意有限數(shù)目的內(nèi)部“狀態(tài)”n自動(dòng)機(jī)的本質(zhì)自動(dòng)機(jī)的本質(zhì)：根據(jù)狀態(tài)、輸入和規(guī)則決定下一個(gè)狀態(tài)狀態(tài)狀態(tài) 輸入（激勵(lì)）輸入（激勵(lì)） 規(guī)則規(guī)則 狀態(tài)遷移狀態(tài)遷移282022-4-9College of Computer Science & Technology, BUPT為什么

19、叫自動(dòng)機(jī)？為什么叫自動(dòng)機(jī)？n可能的狀態(tài)、運(yùn)行的規(guī)則都是事先確定的。一旦開(kāi)始運(yùn)行，就按照事先確定的規(guī)則工作，因此叫“自動(dòng)機(jī)”。n有限自動(dòng)機(jī)可以認(rèn)為是由一個(gè)帶有讀頭的有限控制器和一條寫(xiě)有字符的輸入帶組成。292022-4-9College of Computer Science & Technology, BUPTn例1：打電話 (自動(dòng)機(jī)在通信領(lǐng)域的應(yīng)用)。 在一次呼叫中，從建立連接到通話完畢，要經(jīng)歷摘機(jī)，撥號(hào)，應(yīng)答，進(jìn)行通話等過(guò)程，可以分別用五個(gè)狀態(tài)來(lái)表示。q0q0q1q1q2q2q3q3q4q4摘機(jī)摘機(jī)收到撥號(hào)音收到撥號(hào)音撥號(hào)撥號(hào)收應(yīng)答信號(hào)收應(yīng)答信號(hào)掛機(jī)掛機(jī)收齊號(hào)碼收齊號(hào)碼q0:q0:

20、空閑狀態(tài)空閑狀態(tài)q1:q1:等待撥號(hào)狀態(tài)等待撥號(hào)狀態(tài)q2:q2:可以撥號(hào)狀態(tài)可以撥號(hào)狀態(tài)q3:q3:等待應(yīng)答狀態(tài)等待應(yīng)答狀態(tài)q4:q4:通話狀態(tài)通話狀態(tài)302022-4-9College of Computer Science & Technology, BUPTn例2：串口通信 兩臺(tái)微機(jī)通過(guò)串口通信, 需在兩臺(tái)機(jī)器間建立好連接后，才可以傳遞數(shù)據(jù)，可以使用有限狀態(tài)自動(dòng)機(jī)，描述串口通信的狀態(tài)。傳輸數(shù)據(jù)收到應(yīng)答斷開(kāi)連接連接請(qǐng)求q0q1q2312022-4-9College of Computer Science & Technology, BUPTn根據(jù)結(jié)構(gòu)不同，自動(dòng)機(jī)又可分為有限

21、自動(dòng)機(jī)，下推自動(dòng)機(jī)，圖靈機(jī)等。n下推自動(dòng)機(jī)可以看作是由一條輸入帶，一個(gè)有限控制器和一個(gè)下推棧組成。n基本圖靈機(jī)由一個(gè)具有讀寫(xiě)頭的有限控制器和一條無(wú)限帶組成。n使用自動(dòng)機(jī)，可以形式化的描述現(xiàn)實(shí)世界中的一些問(wèn)題。322022-4-9College of Computer Science & Technology, BUPT3形式語(yǔ)言與自動(dòng)機(jī)的關(guān)系形式語(yǔ)言與自動(dòng)機(jī)的關(guān)系n形式語(yǔ)言和自動(dòng)機(jī)是密切相關(guān)的。形式語(yǔ)言 字符串自動(dòng)機(jī) 字符串的識(shí)別系統(tǒng)n根據(jù)復(fù)雜程度可將形式語(yǔ)言分類(lèi)，根據(jù)自動(dòng)機(jī)的接受能力、處理能力的不同也將自動(dòng)機(jī)分類(lèi)。二者之間具有較好的對(duì)應(yīng)關(guān)系。332022-4-9College of

22、Computer Science & Technology, BUPT342022-4-9College of Computer Science & Technology, BUPT語(yǔ)言與有限自動(dòng)機(jī)（Finite Automata） 設(shè)設(shè) = 0, 1 ， L = w w 中至少有一個(gè)中至少有一個(gè)0 ， 如如 0011, 10, 110111 L, 而而11, , 1111 L。下圖是一個(gè)可接受該語(yǔ)言的有限狀態(tài)自動(dòng)機(jī)下圖是一個(gè)可接受該語(yǔ)言的有限狀態(tài)自動(dòng)機(jī) 12Start0, 101352022-4-9College of Computer Science & Techn

23、ology, BUPT小結(jié)n文法是定義語(yǔ)言的一個(gè)數(shù)學(xué)模型，而自動(dòng)機(jī)可看作是語(yǔ)言的識(shí)別系統(tǒng)。n通過(guò)對(duì)一些定理的證明，說(shuō)明對(duì)于一個(gè)文法產(chǎn)生的語(yǔ)言，可以構(gòu)造相應(yīng)自動(dòng)機(jī)接受該語(yǔ)言：一個(gè)自動(dòng)機(jī)接受的語(yǔ)言，可以構(gòu)造對(duì)應(yīng)的文法產(chǎn)生該語(yǔ)言。一定類(lèi)型的自動(dòng)機(jī)和某種類(lèi)型的文法具有等價(jià)性。 362022-4-9College of Computer Science & Technology, BUPT課程內(nèi)容及要求n課程內(nèi)容： 書(shū)上二、三、四、五章。n要求：通過(guò)本課學(xué)習(xí)，要求同學(xué)們掌握形式化描述方法，建立起形式語(yǔ)言與自動(dòng)機(jī)的概念，并能在實(shí)際中加以應(yīng)用。n通過(guò)對(duì)定理的證明，對(duì)同學(xué)們進(jìn)行思維訓(xùn)練，并掌握一定的證

24、明方法。372022-4-9College of Computer Science & Technology, BUPT證 明 技 術(shù)* 基本證明方法基本證明方法 歸納證明技術(shù)歸納證明技術(shù)* 引自清華大學(xué)計(jì)算機(jī)系軟件技術(shù)研究所王生原老師課件引自清華大學(xué)計(jì)算機(jī)系軟件技術(shù)研究所王生原老師課件382022-4-9College of Computer Science & Technology, BUPT演 繹 證 明 概念概念 一個(gè)一個(gè) 證明證明（proof）是命題的序列，是命題的序列，其中的每一個(gè)命題或者是已知的命題，或者是其中的每一個(gè)命題或者是已知的命題，或者是由前面出現(xiàn)過(guò)的命題

25、使用邏輯公理和規(guī)則得出由前面出現(xiàn)過(guò)的命題使用邏輯公理和規(guī)則得出. 已知的命題集合稱(chēng)為已知的命題集合稱(chēng)為假設(shè)假設(shè)（hypothesis）或或前前提提（premise），），最后一個(gè)命題稱(chēng)為該前提的最后一個(gè)命題稱(chēng)為該前提的結(jié)論結(jié)論（conclusion）. 392022-4-9College of Computer Science & Technology, BUPT“If Then”命題命題 證明方法證明方法 把把 If 部分作為已知的命題，把部分作為已知的命題，把 Then 部分作部分作為結(jié)論為結(jié)論. 舉例舉例 如果如果x+y=1，那么那么x2-y2=x-y. 證明證明:1 x2-y2

26、 = (x+y)(x-y) / 數(shù)學(xué)數(shù)學(xué)公理公理2 (x+y) = 1 / 已知已知x2-y2 = x-y / 由由1、2 和算術(shù)性質(zhì)推出和算術(shù)性質(zhì)推出402022-4-9College of Computer Science & Technology, BUPT“If - And - Only - If ”命題命題 欲證欲證 A if and only if B， 可分別證明如下兩個(gè)命題：可分別證明如下兩個(gè)命題： 1 if A then B， 2 if B then A. 412022-4-9College of Computer Science & Technology,

27、BUPT有關(guān)集合的命題有關(guān)集合的命題 設(shè)設(shè) R, S 為集合為集合. 欲證欲證 R S， 可證明如下命題：可證明如下命題： if x R then x S 欲證欲證 R = S， 可分別證明如下兩個(gè)命題：可分別證明如下兩個(gè)命題： 1 if x R then x S 2 if x S then x R422022-4-9College of Computer Science & Technology, BUPT原命題的逆否命題原命題的逆否命題 有時(shí)，證明原命題的逆否有時(shí)，證明原命題的逆否(contrapositive) 命題更加方便命題更加方便. 欲證欲證 if A then B ， 可

28、證明如下命題：可證明如下命題： if not B then not A432022-4-9College of Computer Science & Technology, BUPT反證法反證法 反證（反證（proof by contradiction） 欲證欲證 if H then C ，可以把可以把 H 和和 not C 都作為已知的命題，把任何一個(gè)矛盾都作為已知的命題，把任何一個(gè)矛盾( contradiction )命題作為新的結(jié)論命題作為新的結(jié)論.442022-4-9College of Computer Science & Technology, BUPT舉例證明或否

29、證舉例證明或否證 舉例證明存在量化的命題舉例證明存在量化的命題 如命題：存在整數(shù)如命題：存在整數(shù) a，滿足滿足 a2 = 2a. 證明證明: 取取 a = 2. ，滿足滿足 a2 = 2a. 舉反例否定全稱(chēng)量化的命題舉反例否定全稱(chēng)量化的命題 如命題：所有整數(shù)如命題：所有整數(shù) a，都滿足都滿足 a2=2a. 否證否證: 取取 a = 1. ，不滿足不滿足 a2 = 2a. 452022-4-9College of Computer Science & Technology, BUPT 集合的歸納定義集合的歸納定義 由由 3 部分構(gòu)成：部分構(gòu)成： 1 基礎(chǔ)基礎(chǔ)（basis） / / 直接定

30、義集合中的元素（至少直接定義集合中的元素（至少1個(gè)）個(gè)） 2 歸納歸納（induction）/ / 從已知元素生成新元素的規(guī)則從已知元素生成新元素的規(guī)則 3 極小性限制極小性限制 / / 申明集合中的元素只能由申明集合中的元素只能由 1、2 生成生成 結(jié)構(gòu)歸納法結(jié)構(gòu)歸納法 對(duì)于歸納定義的集合對(duì)于歸納定義的集合 S，欲證對(duì)于任意欲證對(duì)于任意x S，滿足性質(zhì)滿足性質(zhì)P(x). 1 基礎(chǔ)基礎(chǔ)（basis） / / 若有直接定義若有直接定義 a S，則證明則證明 P(a) 2 歸納歸納（induction） / / 若歸納定義中有規(guī)則若歸納定義中有規(guī)則 if a1, a2, , an S then f (a1, a2, , an ) S ，則證明則證明 if P( a1 ), P( a2 ), , P( an ) then P( f (a1, a2, , an )