1、離散數學教學的理性思考離散數學教學的理性思考計算機學院2計算機學院2主要內容主要內容 基本問題基本問題 數理邏輯數理邏輯 數理邏輯是基礎數理邏輯是基礎 離散數學是基礎離散數學是基礎計算機學院3計算機學院3基本問題基本問題 離散數學離散數學 數理邏輯數理邏輯 集合論集合論 圖論圖論 代數系統代數系統 常識常識 問：學習離散數學有什么有？問：學習離散數學有什么有？ 答：離散數學是計算機專業基礎答：離散數學是計算機專業基礎 基本問題基本問題 “離散數學是計算機專業基礎離散數學是計算機專業基礎”是什么意思？是什么意思？ “離散數學如何是計算機專業基礎離散數學如何是計算機專業基礎”是什么意思？是什么意思

2、？計算機學院4計算機學院4離散數學與計算機專業課程關系問題離散數學與計算機專業課程關系問題核心課程核心課程先修課程先修課程計算機導論計算機導論程序設計基礎程序設計基礎計算機導論計算機導論離散結構離散結構數學分析或高等數學數學分析或高等數學算法與數據結構算法與數據結構高級語言程序設計、離散結構高級語言程序設計、離散結構計算機組成基礎計算機組成基礎計算機導論、數字邏輯計算機導論、數字邏輯計算機體系結構計算機體系結構計算機組成基礎計算機組成基礎操作系統操作系統算法與數據結構算法與數據結構數據庫系統原理數據庫系統原理算法與數據結構、離散數學算法與數據結構、離散數學編譯原理編譯原理程序設計、離散結構、算

3、法與數據結構程序設計、離散結構、算法與數據結構軟件工程軟件工程程序設計、算法與數據結構程序設計、算法與數據結構計算機圖形學計算機圖形學程序設計、離散數學程序設計、離散數學計算機網絡計算機網絡計算機導論、計算機組成、操作系統、計算機導論、計算機組成、操作系統、算法與數據結構算法與數據結構人工智能人工智能高級語言程序設計、離散結構高級語言程序設計、離散結構數字邏輯數字邏輯計算機導論計算機導論高等學校計算機科學與技術專業發展戰略報告暨專業規范高等學校計算機科學與技術專業發展戰略報告暨專業規范為什么離散數學的為什么離散數學的前導課程是數學？前導課程是數學？為什么數字邏輯課為什么數字邏輯課程前導課程是計

4、算程前導課程是計算機導論？機導論？如何體現離散數學如何體現離散數學課程的基礎性？課程的基礎性？計算機學院5計算機學院5計算機專業的基礎問題計算機專業的基礎問題 邏輯是所有數學推理及其所有自邏輯是所有數學推理及其所有自動推理的基礎。動推理的基礎。 對于計算機的設計、系統規范說對于計算機的設計、系統規范說明、人工智能、計算機程序設計明、人工智能、計算機程序設計、程序設計語言以及計算機科學、程序設計語言以及計算機科學的其它許多領域，邏輯都有實際的其它許多領域，邏輯都有實際的應用。的應用。 Kenneth H. RosenKenneth H. Rosen計算機學院6計算機學院6ACM Computer

5、 Science Curricula 2013ACM Computer Science Curricula 2013DS.DS.離散結構（離散結構（3737個核心一級學時，個核心一級學時，4 4個核心二級學時）個核心二級學時）核心一級學時核心一級學時核心二級學時核心二級學時比例比例DS/DS/集合、關系與函數集合、關系與函數4 49%9%DS/DS/基礎邏輯基礎邏輯9 922%22%DS/DS/證明方法證明方法10101 127%27%DS/DS/計數基礎計數基礎5 512%12%DS/DS/樹和圖樹和圖3 31 110%10%DS/DS/離散概率離散概率6 62 220%20%計算機學院7計

6、算機學院7集合、基本邏輯和證明方法的知識點集合、基本邏輯和證明方法的知識點 集合集合 維恩圖維恩圖 并集、交集、補集并集、交集、補集 笛卡爾積、冪集、笛卡爾積、冪集、有限集合的基數有限集合的基數 關系關系 自反性、對稱性、自反性、對稱性、傳遞性傳遞性 等價關系、偏序關等價關系、偏序關系系 函數函數 滿射、單射、雙射滿射、單射、雙射 反函數反函數 函數的復合函數的復合命題邏輯（參考：命題命題邏輯（參考：命題邏輯同時出現在智能系邏輯同時出現在智能系統統/ /知識推理）知識推理）邏輯聯結詞邏輯聯結詞真值表真值表范式（合取范式、析取范式（合取范式、析取范式）范式）合式公式的有效性合式公式的有效性命題推

7、理定律（肯定前命題推理定律（肯定前件式和否定后件式的概件式和否定后件式的概念）念）謂詞邏輯謂詞邏輯全稱量詞與存在量詞全稱量詞與存在量詞命題邏輯和謂詞邏輯的命題邏輯和謂詞邏輯的局限局限蘊含、等價、逆命題蘊含、等價、逆命題、否命題、逆否命題、否命題、逆否命題、否定和矛盾等概念、否定和矛盾等概念數學證明架構數學證明架構直接證明直接證明反例證偽反例證偽反證法反證法數學歸納法數學歸納法結構歸納法結構歸納法弱歸納法與強歸納法弱歸納法與強歸納法（即，第一類數學歸（即，第一類數學歸納法和第二類數學歸納法和第二類數學歸納法）納法）數學上的遞歸定義數學上的遞歸定義計算機學院8計算機學院8主要內容主要內容 基本問題

8、基本問題 數理邏輯數理邏輯 數理邏輯是基礎數理邏輯是基礎 離散數學是基礎離散數學是基礎計算機學院9計算機學院9最簡單的論域最簡單的論域邏輯域邏輯域 邏輯對象：邏輯對象：0,10,1 邏輯運算：邏輯運算： , , , , , , , , , , 邏輯關系：邏輯關系： =, , 真值表真值表 一組邏輯自變量與一個邏輯因變量的對應表一組邏輯自變量與一個邏輯因變量的對應表 真值表定義邏輯運算和關系真值表定義邏輯運算和關系0110pp100110111110111001010000qpqpqpqpqp計算機學院10計算機學院10命題邏輯公式與語言命題邏輯公式與語言 定義：定義： (1).(1).常量常量

9、0 0和和1 1是邏輯公式；是邏輯公式； (2).(2).命題變量是邏輯公式；命題變量是邏輯公式； (3).(3).若若Q,RQ,R是邏輯公式，則是邏輯公式，則( ( Q)Q)、(Q(Q R) R) 、(Q(Q R) R) 、(Q(QR) R) 、(Q(QR) R) 、(Q(Q R)R)是邏輯是邏輯公式；公式； (4).(4).只有有限次應用只有有限次應用(1)(1)(3)(3)構成的公式是邏構成的公式是邏輯公式。輯公式。計算機學院11計算機學院11真值表驗證運算性質真值表驗證運算性質 結合律結合律 (PQ)R=P(QR)(PQ)R=P(QR) (PQ)R=P(QR)(PQ)R=P(QR) (

10、P(PQ)Q)R=PR=P(Q(QR) R) 分配律分配律 P(QR)=(PQ)(PR) P(QR)=(PQ)(PR) P(QR)=(PQ)(PR)P(QR)=(PQ)(PR) P(QP(QR)=(PQ)R)=(PQ)(PR) (PR) 交換律交換律 QR=RQQR=RQ QR=RQQR=RQ Q QR=RR=RQ Q 德德 摩根律摩根律 (QR)=(QR)= QQ R R (QR)=(QR)= QQ R R 計算機學院12計算機學院12邏輯表達式一般方法邏輯表達式一般方法 若若x xi,j i,j =1=1，則，則x xi,j i,j=x=xk k，若，若x xi,j i,j =0=0，則，

11、則x xi,j i,j= = x xi,j i,j 若若y yk k=1=1，k=0,nk=0,n，則，則y yk k=x=xm-1,km-1,k x x0,k0,k y= yy= y0 0 y yn n 功能可以用真值表表達功能可以用真值表表達 所有邏輯運算都可以所有邏輯運算都可以表達為表達為 , , , , , ,的運算。的運算。x0 xkxm-1y000000k1001012m-11111計算機學院13計算機學院13邏輯哲學邏輯哲學 世界是由事實構成的世界是由事實構成的 邏輯哲學論邏輯哲學論 事實是事物的性質，以及事物之事實是事物的性質，以及事物之間的關系間的關系 我們關于外間世界的知識

12、我們關于外間世界的知識- -哲學哲學上科學方法應用的一個領域上科學方法應用的一個領域維特根斯坦維特根斯坦羅素羅素 根據維特根斯坦和羅素的哲學思想，事實是表達事物的性質根據維特根斯坦和羅素的哲學思想，事實是表達事物的性質或表達一些事物之間的關系。或表達一些事物之間的關系。 世界由事實構成，而命題與事實對應，事實使一個命題為真世界由事實構成，而命題與事實對應，事實使一個命題為真或為假。最簡單的事實稱為原子事實，與原子事實對應的是或為假。最簡單的事實稱為原子事實，與原子事實對應的是原子命題。原子命題。 原子命題的真或假取決于它與相應的原子事實是否符合。原子命題的真或假取決于它與相應的原子事實是否符合

13、。計算機學院14計算機學院14謂詞謂詞 定義：研究對象統稱為客體。定義：研究對象統稱為客體。 定義：事物的性質詞和事物的關系詞統稱為謂詞。定義：事物的性質詞和事物的關系詞統稱為謂詞。謂詞可以表示為謂詞可以表示為Q(xQ(x1 1,.,x,.,xn n) )，其中，其中，Q Q是謂詞，是謂詞，x x1 1,.,x,.,xn n是客體是客體Q(x)Q(x)是一元謂詞，是一元謂詞，Q(x,y)Q(x,y)二元謂詞，二元謂詞，Q(xQ(x1 1,.,x,.,xn n) )是是n n元謂詞。元謂詞。謂詞對于任意客體都有真值。謂詞對于任意客體都有真值。 謂詞形式謂詞形式 如果謂詞形式是如果謂詞形式是Q(x

14、)Q(x)表示客體表示客體x x有有Q Q性質；性質； 如果謂詞形式是如果謂詞形式是Q(xQ(x1 1,.,x,.,xn n) )表示客體表示客體x x1 1,.,x,.,xn n之間有之間有Q Q關系。關系。 量詞量詞 表示所有客體具有某性質或關系的詞稱為全稱量詞，記為表示所有客體具有某性質或關系的詞稱為全稱量詞，記為 x(Q(x)x(Q(x)R(x)R(x) 表示至少有一個客體具有某性質或關系的詞稱為存在量詞，記表示至少有一個客體具有某性質或關系的詞稱為存在量詞，記為為 x(Q(x)x(Q(x) R(x)R(x)計算機學院15計算機學院15合式公式與一階謂詞語言合式公式與一階謂詞語言 定義

15、：合式公式是按如下規則構成的有窮長符號串。定義：合式公式是按如下規則構成的有窮長符號串。 (1).(1).若是若是x x1 1, ,x ,xn n是變元，是變元，Q Qi in n是是n n元謂詞，則元謂詞，則Q Qi in n(x (x1 1, ,x ,xn n) )是是合式公式。合式公式。 (2).(2).若若Q Q是合式公式，則是合式公式，則( ( Q)Q)是合式公式；是合式公式； (3).(3).若若Q Q和和R R是合式公式，則是合式公式，則(Q(Q R)R)、(Q(Q R)R)、(Q(QR) R) 、(Q(QR)R)及及(Q(Q R)R)是合式公式；是合式公式； (4).(4).若

16、若Q Q是合式公式，是合式公式，x x是變元，則是變元，則( ( xQ)xQ)及及( ( xQ)xQ)是合式是合式公式。公式。 (5).(5).只有有限次應用只有有限次應用(1)(1)(4)(4)構成的公式是合式公式。構成的公式是合式公式。計算機學院16計算機學院16思想理論與邏輯語言思想理論與邏輯語言 弗雷格思想理論弗雷格思想理論 思想是陳述句的含義思想是陳述句的含義 思想有真假思想有真假 思想有結構思想有結構 思想通過語言來表達和傳遞思想通過語言來表達和傳遞 存在判定思想同一性的標準存在判定思想同一性的標準 思想影響人的意志思想影響人的意志 自然語言符合邏輯語言自然語言符合邏輯語言 在保持

17、思想的情況下，自然語言在保持思想的情況下，自然語言變換為邏輯語言變換為邏輯語言Gottlob Frege 1848-1925計算機學院17計算機學院17自然（科學）語言命題符合邏輯語言自然（科學）語言命題符合邏輯語言 定義：具有確定真或假含義的陳述句稱為定義：具有確定真或假含義的陳述句稱為原子命題原子命題，或，或簡單簡單命題命題。 在自然語言中，在自然語言中，并且并且、或或、并非并非、如果如果. .，則，則. .。、當且當且僅當僅當等詞也稱為聯接詞。等詞也稱為聯接詞。 復合語句復合語句是一些陳述句用是一些陳述句用并且并且、或或、并非并非、如果如果. .，則，則. .。、當且僅當當且僅當等聯接為

18、一條語句。等聯接為一條語句。 量化語句量化語句是用是用所有所有、存在存在等量詞約束陳述句或復合語句。等量詞約束陳述句或復合語句。 定義：原子命題用定義：原子命題用并且并且、或或、并非并非、如果如果. .，則，則. .。、當當且僅當且僅當等聯接詞聯接的語句稱為等聯接詞聯接的語句稱為復合命題復合命題。 定義：用定義：用所有所有和和存在存在量詞約束的原子命題或復合命題稱為量詞約束的原子命題或復合命題稱為量化命題量化命題。 定義：原子命題、復合命題和量化命題統稱為定義：原子命題、復合命題和量化命題統稱為命題命題。計算機學院18計算機學院18符號化機械過程符號化機械過程 自然語言的命題符號化方法是機械式

19、過程，無需理解具自然語言的命題符號化方法是機械式過程，無需理解具體概念的含義，僅僅將相同的客體、函數、性質或關系體概念的含義，僅僅將相同的客體、函數、性質或關系分別用相同符號表示。分別用相同符號表示。 復合語句由簡單語句、聯接詞及量詞構成。復合語句由簡單語句、聯接詞及量詞構成。 首先，識別出簡單語句，而后，簡單語句符號化。首先，識別出簡單語句，而后，簡單語句符號化。 復合語句由符號化的簡單命題形式和聯接詞及量詞構成。復合語句由符號化的簡單命題形式和聯接詞及量詞構成。 復合語句就可以根據聯接詞及量詞的含義，形成符號化的復合語句就可以根據聯接詞及量詞的含義，形成符號化的命題。命題。計算機學院19計

20、算機學院19符號化機械過程（續）符號化機械過程（續） 自然知識可以表示為命題，所有的自然律也可以表達為自然知識可以表示為命題，所有的自然律也可以表達為命題。命題。 自然語言的命題符號化方法：自然語言的命題符號化方法： (1).(1).在復合語句中識別出陳述句，并用下劃線標出在復合語句中識別出陳述句，并用下劃線標出 (2).(2).陳述語句符號化陳述語句符號化相同相同（不同）（不同）的客體用相同的客體用相同( (不同不同) )符號表示符號表示相同相同（不同）（不同）函數用相同函數用相同（不同）（不同）符號表示符號表示相同相同（不同）（不同）性質或關系用相同性質或關系用相同（不同）（不同）符號表示

21、符號表示 (3).(3).聯接詞及量詞符號化聯接詞及量詞符號化并且并且表示為表示為 ，或或表示為表示為 ，并非并非表示為表示為 ，如果如果. .，則，則. .。表示為表示為，當且僅當當且僅當表示為表示為所有所有表示為表示為 ，存在存在表示為表示為 ，形成符號化的命題。，形成符號化的命題。計算機學院20計算機學院20數學分析概念數學分析概念 在研究過程中，首先用定義的方式給出概念，而后研究在研究過程中，首先用定義的方式給出概念，而后研究概念的性質以及概念之間的關系，形成定理。概念的性質以及概念之間的關系，形成定理。 概念的定義是復合語句，也能夠用機械方式符號化。概念的定義是復合語句，也能夠用機械

22、方式符號化。 自然語言表達序列極限、函數極限、連續、一致連續、自然語言表達序列極限、函數極限、連續、一致連續、導數等概念，人們可能有二義性理解，即人們對這些概導數等概念，人們可能有二義性理解，即人們對這些概念含義會有不同的理解。念含義會有不同的理解。 如果這些概念符號化，那么，人們對這些概念的理解就如果這些概念符號化，那么，人們對這些概念的理解就會相同。會相同。計算機學院21計算機學院21定義（極限）是命題定義（極限）是命題 定義：設定義：設xxn n 是序列，對于任意是序列，對于任意 00，存在，存在N0N0，對于任，對于任何何n n，當，當nNnN時，都有時，都有|x|xn n-b|-b|

23、00，存在，存在N N，N0N0，對于任何，對于任何n n，當，當nNnN時，都有時，都有|x|xn n-b|-b|00，存在，存在N N，N0N0，對于所有，對于所有n n，當，當nNnN時時，都有，都有|x|xn n-b|-b|00N(N0N(N0n(nNn(nN|x|xn n-b|-b|0(0N N1 1(N(N1 100n(nNn(nN1 1|x|xn n-a|), -a|0(0N N2 2(N(N2 200n(nNn(nN2 2|x|xn n-b|) a=b-b|0(0N(N0N(N0n(nNn(nN|x|xn n-a|) -a|0M(M0n(n0n(n0|x|xn n |M) |M

24、)計算機學院23計算機學院23歐幾里德幾何學歐幾里德幾何學 歐幾里德歐幾里德（325 BC -265 BC ），），古希臘數學家；古希臘數學家； 幾何原本幾何原本是一個實質公理系統是一個實質公理系統把點、線、面、角等分為原始定義概念（把點、線、面、角等分為原始定義概念（2323）和可定）和可定義概念；義概念；命題分為公理（命題分為公理（5 5）、公設（）、公設（5 5）；）；由公理公設出發加以證明的定理（由公理公設出發加以證明的定理（467467） 從簡單到復雜，證明相當嚴格。從而建立了歐幾里從簡單到復雜，證明相當嚴格。從而建立了歐幾里得幾何學的第一個公理化數學體系。得幾何學的第一個公理化數學

25、體系。 公設公設1. 1.由任意一點到另外任意一點可以畫直線。由任意一點到另外任意一點可以畫直線。2. 2.一條有限直線可以繼續延長。一條有限直線可以繼續延長。3. 3.以任意點為心及任意的距離可以畫圓。以任意點為心及任意的距離可以畫圓。4. 4.凡直角都彼此相等。凡直角都彼此相等。5 5( (平行公設平行公設) )若一直線與兩直線相交，且若若一直線與兩直線相交，且若同側所交兩內角之和小于兩直角，則兩直線同側所交兩內角之和小于兩直角，則兩直線無限延長后必相交于該側的一點。無限延長后必相交于該側的一點。 公理公理1 1等于同量的量彼此相等。等于同量的量彼此相等。2 2等最加等量，其和仍相等。等最

26、加等量，其和仍相等。3 3，等量減等量，其差仍相等。，等量減等量，其差仍相等。4 4彼此能重合的物體是全等的。彼此能重合的物體是全等的。5 5整體大于部分。整體大于部分。計算機學院24計算機學院24希爾伯特證明論希爾伯特證明論 通過形式化第一次使證明本身成為通過形式化第一次使證明本身成為數學研究對象。數學研究對象。 給出初始符號集合給出初始符號集合 構造合式公式規則構造合式公式規則 Q Q的證明，的證明，構造出構造出1m1m個合式個合式公式序列，其中，第公式序列，其中，第m m個合式公式個合式公式是是Q Q，并且，并且1m1m合式公式合式公式 或者是前提或者是前提 或者是公理或者是公理 或者是

27、推導規則或者是推導規則 形式證明正確性的驗證。形式證明正確性的驗證。David Hilbert 1826-1943計算機學院25計算機學院25邏輯證明有何不同？邏輯證明有何不同？ 領域知識是提出概念，形成定理，對定理進行證明。領域知識是提出概念，形成定理，對定理進行證明。 通過思想概念的涵義以及關系，形成一個個推理步驟，最通過思想概念的涵義以及關系，形成一個個推理步驟，最后完成證明。領域知識不同，證明方法也不同。后完成證明。領域知識不同，證明方法也不同。 在邏輯公理系統中，已知語言、公理、在邏輯公理系統中，已知語言、公理、推理規則推理規則 是前提集是前提集, Q, Q是結論是結論 是是語句集合

28、，語句集合，Q Q是語句是語句 在邏輯公理系統中，各個領域知識都抽象為形式語言。在邏輯公理系統中，各個領域知識都抽象為形式語言。從形式語言表示的公理和前提集開始，一步步推理到結從形式語言表示的公理和前提集開始，一步步推理到結論。論。 因為推理過程沒有領域概念及其涵義，僅有抽象的符號，因為推理過程沒有領域概念及其涵義，僅有抽象的符號，按照推理規則一步一步進行推理，所以，推理具有統一方按照推理規則一步一步進行推理，所以，推理具有統一方法。法。計算機學院26計算機學院26邏輯公理系統邏輯公理系統 公理系統公理系統 從一些從一些公理公理出發，根據出發，根據演繹法演繹法，推導出一系列，推導出一系列定理定

29、理，形成的演繹體系叫作，形成的演繹體系叫作公理系統公理系統。 公理系統的組成：公理系統的組成： 語言集語言集 公理集公理集公理是用于表達推理由之出發的初始肯定命題；公理是用于表達推理由之出發的初始肯定命題； 推理規則集推理規則集推理規則是由公理及已證定理得出新定理的規則；推理規則是由公理及已證定理得出新定理的規則； 定理集定理集表達了肯定的所有命題。表達了肯定的所有命題。計算機學院27計算機學院27謂詞邏輯公理系統謂詞邏輯公理系統 (1)(1)謂詞邏輯語言：謂詞邏輯語言：L=L=,P,F,C ( (2 2). ).公理集合：公理集合： 1).1).公理模式公理模式A A 1 1：Q Q (R

30、(RQ)Q) 2).2).公理模式公理模式A A 2 2：(P(P (Q (QR) R) (P (PQ) Q) (P (PR)R) 3).3).公理模式公理模式A A 3 3：( ( Q QR) R) (R (RQ) Q) 4).4).公理模式公理模式A A 4 4： xQ(x)xQ(x)Q(x)Q(x)x/t x/t 其中，項其中，項t t對于對于Q Q中的中的x x是可代入的。是可代入的。 5).5).公理模式公理模式A A 5 5： x x( (Q QR(x)R(x) ) ( (Q QxR(x)xR(x) ) 其中其中x x不是不是Q Q中自由變元中自由變元。 ( (3 3). ).推理

31、規則推理規則 1).1).分離規則（簡稱分離規則（簡稱MPMP規則）：從規則）：從Q Q和和Q QR R推出推出R R。 2).2).全稱全稱概括（簡稱概括（簡稱UGUG規則）：從規則）：從Q(x)Q(x)推出推出( ( xQ)xQ)。計算機學院28計算機學院28演繹與證明演繹與證明 Q Q的的證明，就是要構造一個合式公式的變換序列，其證明，就是要構造一個合式公式的變換序列，其中每一步產生的合式公式中每一步產生的合式公式，并且，并且 或者是公理模式或者是公理模式 或者是前提模式或者是前提模式 或者是由分離規或者是由分離規 或者是或者是全稱全稱概括概括（謂詞邏輯）（謂詞邏輯）計算機學院29計算機

32、學院29 xQ(x)yQ(y) (y不在不在Q中出現中出現) 證明：證明： 證據：證據： A A1 1= = xQ(x) xQ(x) Q(y) Q(y) A4 4 A A2 2= = y y( ( xQ(x) xQ(x) Q(y) UG Q(y) UG A A3 3= = y y( ( xQ(x) xQ(x) Q(y)Q(y)( ( xQ(x) xQ(x) y Q(y) y Q(y) A5 5 A A4 4= = xQ(x) xQ(x) y Q(y) Ay Q(y) A3 3=A=A2 2 A A4 4 證畢證畢計算機學院30計算機學院30定理定理( (傳遞律傳遞律) )：P PQ,QQ,QR

33、PRPR R 證明：證明： 證據：證據：A A1 1=(Q=(QR) R) (P(P (Q (QR) R) A1 1A A2 2=Q=QR R A A2 2 A A3 3=P=P (Q (QR) R) A A1 1= =A A2 2 A A3 3 A A4 4=(P=(P (Q (QR) R) (P(PQ) Q) (P(PR) R) A2 2A A5 5=(P=(PQ) Q) (P(PR) R) A A4 4= =A A3 3 A A5 5 A A6 6=(P=(PQ) Q) A A6 6 A A7 7=(P=(PR) R) A A5 5= =A A6 6A A7 7 證畢證畢計算機學院31計

34、算機學院31定律與規則定律與規則 思維直覺思維直覺、思維定律與定理。思維定律與定理。 充分理由律（三段論）：充分理由律（三段論）：Q, QQ, QR RR R 傳遞律：傳遞律：P PQ,QQ,QRPRPR R 反證律：如果反證律：如果 , , Q R, Q R, , , QQ R,R,則則 Q Q 歸謬律：如果歸謬律：如果 , Q R, , Q R, , Q , Q R R，則，則 Q Q 排中律：排中律：(Q(QQ Q) ) 矛盾律：矛盾律： (Q(QQ)Q) 引入規則：引入規則： P(c) P(c) xP(x) xP(x) 選擇規則：選擇規則： xP(x)xP(x)P(c) P(c) 計算

35、機學院32計算機學院32命題邏輯定理命題邏輯定理 (P (P(Q(QR) R) (Q(Q(P(PR)R)(Q(QR)R)(P(PQ)Q)(P(PR)R)(P(P Q) Q)(Q(QR)R)(P(PR)R)(P(P Q) Q)(P(PR)R)(P(P(Q (Q R)R)QQQ QQ QQ Q Q QQ QQ Q(Q(QR)R) R)R) Q Q (Q(QR)R)R R Q Q Q Q Q Q Q Q Q Q Q Q(Q(QR) R) (R (RQ)Q)(Q(Q R) R) (Q (Q R) R) ( (Q QR)R)(Q(QR)R) (Q(QR)R)( (Q QR)R)(Q(QR)R)( ( R

36、 RQ)Q)( Q QR)R)( ( R RQ)Q)(Q(QR )R )(R(RQ)Q) Q Q(Q(Q R) R)( ( Q QQ)Q)(R(RQ)Q)( ( Q QQ)Q)Q Q ( Q QR RR)R)Q Q( ( Q QR) R) ( ( Q QR) R) Q)Q)(Q(QR) R) (Q(QR)R)Q)Q) 計算機學院33計算機學院33一階謂詞邏輯定理一階謂詞邏輯定理 xR(x) xR(x) y R(y)y R(y) xR(x) xR(x) y R(y)y R(y) Q(c) Q(c) xQ(x)xQ(x) Q(c) Q(c) xQ(x)xQ(x) xR(x) xR(x) xR(x)

37、 xR(x) x x y R(x,y) y R(x,y) y y xR(x,y) xR(x,y) x x y R(x,y) y R(x,y) y y xR(x,y) xR(x,y) x x yR(x,y) yR(x,y) y y x R(x,y)x R(x,y) x x yR(x,y) yR(x,y) xR(x,x)xR(x,x) xR(x,x) xR(x,x) x x yR(x,y) yR(x,y) x(P(x)x(P(x)Q(x) Q(x) ( ( xP(x) xP(x) x Q(x)x Q(x) x(P(x) x(P(x) Q(x) Q(x) ( ( xP(x) xP(x) x Q(x)

38、x Q(x) x(P(x)x(P(x) Q(x)Q(x)( ( xP(x)xP(x)xQ(x) xQ(x) xP(x) xP(x) xQ(x)xQ(x)x(P(x) x(P(x) Q(x) Q(x) x(P(x)x(P(x) Q(x) Q(x) ( ( xP(x) xP(x) xQ(x)xQ(x) x(P(x)x(P(x) Q(x) Q(x) ( ( xP(x) xP(x) xQ(x) xQ(x) xP(x) xP(x) x x P(x) P(x) xP(x) xP(x) x x P(x) P(x) x x P(x) P(x) xP(x) xP(x) x x P(x) P(x) xP(x)xP

39、(x)計算機學院34計算機學院34論域、解釋、賦值與模型論域、解釋、賦值與模型 在指定論域上，對于一階邏輯語言在指定論域上，對于一階邏輯語言L L 解釋解釋將常元指稱為論域中某客體；將常元指稱為論域中某客體；將謂詞指稱為論域上的關系；將謂詞指稱為論域上的關系；將函詞指稱為論域上的函數。將函詞指稱為論域上的函數。 賦值賦值將客體變元指稱為論域中的客體。將客體變元指稱為論域中的客體。 一階邏輯語言的解釋，是確定該種語言里的符號表達式同某一階邏輯語言的解釋，是確定該種語言里的符號表達式同某個論域之間的聯系。個論域之間的聯系。 論域和解釋構成了結構。論域和解釋構成了結構。 結構和賦值構成了模型。結構和

40、賦值構成了模型。 一階邏輯語言的語義就是在模型上的邏輯真值。一階邏輯語言的語義就是在模型上的邏輯真值。計算機學院35計算機學院35合式公式、合式公式集合與模型合式公式、合式公式集合與模型 研究合式公式或合式公式集合研究合式公式或合式公式集合 Q Q = Q= Q1 1,.,Q,.,Qn n 在一個模型上具有的性質；在一個模型上具有的性質； 在所有模型上具有的性質在所有模型上具有的性質真值性真值性永真性永真性相等性相等性推論性推論性存在模型存在模型可滿足性可滿足性模型模型永真永真模型等值模型等值模型推論模型推論所有模型所有模型有效性有效性邏輯邏輯永真永真邏輯等邏輯等值值邏輯推論邏輯推論計算機學院

41、36計算機學院36等式關系和推論關系等式關系和推論關系 定義：給定一階語言定義：給定一階語言L L及它的兩個公式及它的兩個公式Q,RQ,R，如果存在模型，如果存在模型M=D, M=，使得，使得(Q) = (R), (Q) = (R), 則稱則稱Q Q與與R R是在是在模型模型MM等值等值，記，記為為Q QMMR R。 定義：給定一個語言定義：給定一個語言L , L , 是一個公式集合是一個公式集合, Q , Q 是一個公式。是一個公式。 若存在模型若存在模型M=M=，使得當，使得當( ( )=1)=1時時，有有(Q)=1(Q)=1，則稱，則稱Q Q 是是 關于模型邏輯推論關于模型邏輯推論，記為

42、，記為 MMQ Q。 定義：如果對于定義：如果對于任意模型任意模型M=D, M=，都有，都有 (Q) = (Q) = (R), (R), 則稱則稱Q Q與與R R是是邏輯等價邏輯等價，記為，記為Q QR R。 定義：給定一個語言定義：給定一個語言L , L , 是一個公式集合是一個公式集合, Q , Q 是一個公式。是一個公式。 若對于若對于任意模型任意模型M=M=，使得當，使得當( ( )=1)=1時有時有(Q)=1(Q)=1，則稱，則稱Q Q 是是 邏輯推論邏輯推論，或稱，或稱 語義推出語義推出Q Q，記為，記為 QQ。計算機學院37計算機學院37前束范式前束范式 定義：設定義：設 k k

43、為為 , , 量詞，量詞，x x1 1xxn n為不同變元，為不同變元，Q Q為開公式為開公式，形式為，形式為 1 1x x1 1n n x xn nQ Q的公式稱為前束范式，的公式稱為前束范式， 稱稱 1 1x x1 1n n x xn n為前束詞，稱為前束詞，稱Q Q為母式。為母式。 定理：設定理：設 k k為為 , , 量詞，量詞，x x1 1xxn n為不同變元，對于任意合為不同變元，對于任意合式公式式公式Q Q，存在前束范式，存在前束范式 1 1x x1 1n n x xn nR R， 使得使得Q Q 1 1x x1 1n n x xn nR R。 定義：若定義：若 1 1x x1

44、1n n x xn nQ Q的是前束范式，并且的是前束范式，并且Q Q是合取范式是合取范式，則稱，則稱 1 1x x1 1n n x xn nQ Q是前束合取范式。是前束合取范式。計算機學院38計算機學院38前束范式步驟前束范式步驟(1).(1).依次用等值公式依次用等值公式Q Q R R (Q (QR)R)Q QR R (Q (QR)R) (R(RQ)Q)Q QR R Q Q R R進行等值變換，產生的公式僅有聯結詞進行等值變換，產生的公式僅有聯結詞 、 、 以及量詞以及量詞 、 。(2). (2). 用等值公式用等值公式Q QQ Q進行變換化簡公式。進行變換化簡公式。(3).(3).根據以

45、上等值公式，以及如下量詞變換等值公式根據以上等值公式，以及如下量詞變換等值公式Q(x) Q(x) x x Q(x)Q(x)Q(x) Q(x) x x Q(x)Q(x)(4).(4).用德用德 摩根律摩根律 (Q(Q R) R) Q QR R， (Q(Q R) R) Q QR R進行化簡。進行化簡。重復應用重復應用(2)(2)、(3)(3)、(4)(4)步驟，逐次將所有聯結詞步驟，逐次將所有聯結詞 置于原子謂詞。置于原子謂詞。計算機學院39計算機學院39前束范式步驟（續）前束范式步驟（續）(5).(5).用換名等值公式用換名等值公式 xQ(x)xQ(x)yQ(y)yQ(y)和和 xQ(x)xQ(

46、x)yQ(y)yQ(y)將所有不同量詞轄將所有不同量詞轄域的變元換名為互不同的變元。域的變元換名為互不同的變元。(6). (6). 若若x x不在不在Q Q中出現，則中出現，則Q QxR(x) xR(x) x(Qx(Q R(x)R(x)Q QxR(x) xR(x) x(Qx(Q R(x)R(x)Q QxR(x) xR(x) x(Qx(Q R(x)R(x)Q QxR(x) xR(x) x(Qx(Q R(x)R(x) 1 1x x1 1Q(xQ(x1 1) ) 2 2 R(x R(x2 2) ) 1 1x x1 1 2 2 x x2 2(Q(x(Q(x1 1) ) R(xR(x2 2) ) 1 1

47、x x1 1Q(xQ(x1 1) ) 2 2 R(x R(x2 2) ) 1 1x x1 1 2 2 x x2 2(Q(x(Q(x1 1) ) R(xR(x2 2) )重復應用重復應用(6)(6)步驟，逐次將量詞前置，使得公式變換為前束范式。步驟，逐次將量詞前置，使得公式變換為前束范式。(7).(7).用等值變換交換量詞次序用等值變換交換量詞次序 x x y Q(x,y) y Q(x,y) y y xQ(x,y)xQ(x,y) x x y Q(x,y) y Q(x,y) y y xQ(x,y)xQ(x,y)計算機學院40計算機學院40等式演算一般方法等式演算一般方法 命題公式命題公式:Q:Q的

48、范式是的范式是Q Q ，R R的范式是的范式是R R ， 因為因為 Q QQ Q ， Q Q R R ，R R R R 。 所以所以Q QR R 謂詞公式謂詞公式:Q:Q的前束合取范式是的前束合取范式是Q Q ，R R的前束合取范式是的前束合取范式是R R ， 因為因為 Q QQ Q ， Q Q R R ，R R R R 。 所以所以Q QR R計算機學院41計算機學院41主要內容主要內容 基本問題基本問題 數理邏輯數理邏輯 數理邏輯是基礎數理邏輯是基礎 離散數學是基礎離散數學是基礎計算機學院42計算機學院42結構主義結構主義 在在結構主義結構主義中，皮亞杰給出中，皮亞杰給出結構特征結構特征

49、結構由對象集合結構由對象集合S S以及關系集合以及關系集合R R、運算集合、運算集合F F和常元集合和常元集合C C組成，組成， 整體性、轉換、自身調整性整體性、轉換、自身調整性 結構主義是知識表征的重要方法結構主義是知識表征的重要方法計算機學院43計算機學院43從結構主義觀點看從結構主義觀點看 集合論集合論 性質定義概念性質定義概念 外延與內涵外延與內涵 圖論圖論 結構集合定義概念結構集合定義概念 代數系統代數系統 操作定義概念操作定義概念 定義運算定義運算 保持封閉性保持封閉性 定義關系定義關系 洞察性質，形成定理洞察性質，形成定理 邏輯表達概念、運算和關系邏輯表達概念、運算和關系 一般方

50、法證明等式一般方法證明等式 演繹形式證明演繹形式證明計算機學院44計算機學院44命題的邏輯構造命題的邏輯構造 基本概念與導出概念基本概念與導出概念 命題：命題： 概念定義是命題。概念定義是命題。 運算定義是命題。運算定義是命題。 關系定義是命題。關系定義是命題。 定理是命題。定理是命題。 邏輯命題能由自然語言描述機械式的變換為邏輯描述。邏輯命題能由自然語言描述機械式的變換為邏輯描述。 聯接詞聯接詞 , , , , , , , 量詞量詞 , , 謂詞、函詞和常元謂詞、函詞和常元 邏輯命題是形式的。邏輯命題是形式的。計算機學院45計算機學院45集合基本概念、概括性公理集合基本概念、概括性公理 集合

51、是一些能夠明確區分的對象構成的整體。集合是一些能夠明確區分的對象構成的整體。 集合一般用大寫英文字母表示，構成集合的對象稱為元素集合一般用大寫英文字母表示，構成集合的對象稱為元素，一般用小寫英文字母表示。，一般用小寫英文字母表示。 元素與集合有元素與集合有“屬于屬于”基本關系基本關系， 關系關系 如果對象如果對象 a a 在集合在集合 A A 中，則稱中，則稱 a a 是是A A 的元素，或者的元素，或者a a 屬于屬于A A，記為，記為 a a A A，否則記為，否則記為a a A A。 概括性公理概括性公理 謂詞謂詞(x)是給定的一個性質，則是給定的一個性質，則(x)確定唯一一個集合。確定

52、唯一一個集合。 設設A = x |(x)，滿足性質，滿足性質(x)的對象都在的對象都在A A中，不滿足中，不滿足該性質的對象都不在該性質的對象都不在A A中。即中。即 x (x) x A) 計算機學院46計算機學院46關系關系 定義定義 設設X X，Y Y是集合，若是集合，若R R X X Y Y ，則稱，則稱 R R 為從為從X X到到Y Y的關系，簡稱為關系的關系，簡稱為關系R R。R= |xR= |x X X y y Y Y 若若R R 是從是從X X到到Y Y的關系，就是集合的關系，就是集合X X中元素與集合中元素與集合Y Y中元中元素之間的對應素之間的對應。計算機學院47計算機學院4

53、7函數函數 定義：設定義：設 f f 是從集合是從集合 X X 到到 Y Y 的關系的關系 若對每個若對每個 x x X X 存在唯一存在唯一 y y Y Y 使得使得 f f，則稱，則稱 f f 為從為從 X X 到到 Y Y 的函數的函數( (映射映射) )，記為，記為 f : X f : X Y Y。 從從 X X 到到 Y Y 的函數指的是的函數指的是單值全函數單值全函數，滿足，滿足f f X X Y Y dom( f ) = Xdom( f ) = X ran( f ) ran( f ) Y Y f f f fy = zy = z計算機學院48計算機學院48滿射、單射和雙射滿射、單射

54、和雙射 定義：設函數定義：設函數f : X f : X Y Y， (1).(1).若對于每個若對于每個 y y Y Y ，都存在，都存在 x x X X使得使得 f (x) = yf (x) = y，則稱，則稱 f f 為滿射，即為滿射，即 y (yy (y Y Y x (xx (x X X f (x) = y) f (x) = y) (2).(2).若對于任意若對于任意 x x X, yX, y Y Y，只要，只要 f (x) = f (y)f (x) = f (y)，就有，就有 x = y x = y ，或只要，或只要 x x y y，就有，就有 f (x) f (x) f (y) f (

55、y) ，則稱，則稱 f f 為單射，即為單射，即 x x y(xy(x X X y y X X f (x) = f (y) f (x) = f (y) x = y) x = y) (3).(3).若函數若函數f f既是單射又是滿射，則稱既是單射又是滿射，則稱 f f為雙射，也稱為一為雙射，也稱為一一對應。一對應。計算機學院49計算機學院49單調性函數單調性函數 定義：設定義：設X X，Y Y為集合，為集合，是全序關系，是全序關系，f: f: X XY Y， (1).(1).如果對于任意如果對于任意x x1 1 x x2 2，則，則f(xf(x1 1) ) f(xf(x2 2) )，則稱，則稱f

56、 f是單調遞增的是單調遞增的 x x1 1 x x2 2(x (x1 1 x x2 2 f(x f(x1 1) ) f(xf(x2 2) ) (2).(2).如果對于任意如果對于任意x x1 1 x x2 2，則，則f(xf(x1 1) ) f(xf(x2 2) )，則稱，則稱f f是嚴格單調遞增是嚴格單調遞增的的 x x1 1 x x2 2(x (x1 1 x x2 2 f(x f(x1 1) ) f(xf(x2 2) ) (3).(3).如果對于任意如果對于任意x x1 1 x x2 2，則，則f(xf(x1 1) ) f(xf(x2 2) )，則稱，則稱f f是單調遞減的是單調遞減的 x

57、 x1 1 x x2 2(x (x1 1 x x2 2 f(x f(x1 1) ) f(xf(x2 2) ) (4).(4).如果對于任意如果對于任意x x1 1 x f(xf(x2 2) )，則稱，則稱f f是嚴格單調遞減是嚴格單調遞減的的 x x1 1 x x2 2(x (x1 1 x f(xf(x2 2) )計算機學院50計算機學院50集合運算集合運算 定義：設定義：設A,BA,B為二集合，稱由為二集合，稱由A A和和B B的所有元素組成的集合為的所有元素組成的集合為A A與與B B的并集，記作的并集，記作A A B B，稱，稱 為并運算符。為并運算符。A A B = x | x B =

58、 x | x A A x x BB A A B = x | xB = x | x A A x x B B 交運算交運算 A-B = x | xA-B = x | x A A x x B B 差運算差運算 A+B = x | xA+B = x | x A A x x B B 對稱差運算對稱差運算 A = x | xA = x | x A A 補運算補運算 集合運算也是由集合及集合運算也是由集合及“ ”這兩個基本概念的導出概念。這兩個基本概念的導出概念。計算機學院51計算機學院51關系運算關系運算 定義：設關系定義：設關系R R和和S S是從是從X X到到Y Y的兩個關系，則的兩個關系，則R R

59、S, R S, R S, R S, R S, R + S, S, R + S, R R為為 R R S=| S=| R R S S R R S=| S=| R R S S R R S=| S=| R R S S R + S=|R + S=| R R S S R=| R=| RR 復合運算、指數運算及逆運算復合運算、指數運算及逆運算 R R S = | S = | y(y( R R SS R Rn+1 n+1 = R= Rn n R R（ R R0 0 = I= IX X ） R R 1 1 = | = | RR計算機學院52計算機學院52集合相等關系集合相等關系 定義定義( (外延性公理）：外

60、延性公理）： 如果集合如果集合A A 和和B B 含有相同的元素，含有相同的元素，則稱則稱A A 和和B B相等，記為相等，記為A = BA = B。 A = B A = B x (xx (x A A x x B)B)x (xx (x A A x x B)B)x (xx (x B B x x A)A) 其中其中表示當且僅當關系。在數理邏輯證明中，用表示當且僅當關系。在數理邏輯證明中，用“符符號號”代替集合符號代替集合符號“”。 集合的集合的“= =”是集合之間的一種關系，即相等關系；是集合之間的一種關系，即相等關系； 這個等關系也可以是表示相等謂詞。這個等關系也可以是表示相等謂詞。 謂詞謂詞“