1、離散數學數學與信息科學學院v第一部分 數理邏輯v第二部分 集合論v第三部分 圖論v第四部分 抽象代數離散數學第一部分 數理邏輯數理邏輯是用數學方法研究推理中前提和結論之間的形式關系的學科。推理是由一個或幾個判斷推出一個新判斷的思維形式。數學方法是指建立一套表意符號體系，對具體事物進行抽象的形式研究的方法。v第一章 命題邏輯v第二章 一階謂詞邏輯第一部分 數理邏輯v1.1 命題和命題聯結詞v1.2 命題公式及其賦值v1.3 等值演算與聯結詞完備集v1.4 析取范式與合取范式v1.5 推理的形式結構v1.6 自然推理系統P第一章 命題邏輯1. 命題：能判斷真假的陳述句。包含兩層意思：（1）必須是陳

2、述句。 （2）能夠確定（分辨）其真值。不等式等式自然語言中的陳述句萬根。如：張校長的頭發有一。是否知道真假是不同的注意：能否分辨真假與 1.1 命題和命題聯結詞）我正在說謊。）啊，我的天哪?。┪覀円W習。）你喜歡數學嗎？。）三角形的內角和等于87658014）火星上有生命。）面積大。）海洋的面積比陸地的例：3962211.1 命題和命題聯結詞2. 命題的真值：判斷結果表示?；蛞话阌妹},:iiqprqp注意：此處不糾纏具體命題的真假問題，只是將其作為數學概念來處理。假命題假真命題真真值：真用T或1表示，假用F或0表示。3.命題和真值的符號化1.1 命題和命題聯結詞1.1 命題和命題聯結詞火

3、星上有生命。積大。海洋的面積比陸地的面例：:962:rqp）我正在說謊。）啊，我的天哪?。┪覀円W習。）你喜歡數學嗎？。三角形的內角和等于8765801:s）火星上有生命。）面積大。）海洋的面積比陸地的例：396221）我正在說謊。）啊，我的天哪！）我們要努力學習。）你喜歡數學嗎？。）三角形的內角和等于87658014原子命題：不能被分解為更簡單的陳述句復合命題：原子命題通過聯結詞聯結而成例：2是有理數是不對的；2是偶素數；2或4是素數；如果2是素數，則3也是素數；2是素數當且僅當3也是素數。p：2是有理數，q：2是偶數，r：2是素數，s：3是素數，t：4是素數。1.1 命題和命題聯結詞4

4、、命題聯結詞”。讀作“非的否命題，記作稱作復合命題，沒有”等否定詞組成的和“非”、“不”、“用命題否定詞pppp,).1不是質數。：是質數。如：的邏輯抽象。、“不”和“沒有”等是自然語言中的“非”44:ppp pTFFT1.1 命題和命題聯結詞”。合取”或“與讀作“組成的復合命題，記作和、是命題，由、合取詞qpqpqpqpqp,).2一面”等的邏輯抽象。、“一面但是”而且”、“雖然”、“不但又“既”、是自然語言中的“并且pqp qFFFFTFTFFTTT：王化的品德很好。：王化的成績很好。qp王化不但成績好而且品德好。pq：1.1 命題和命題聯結詞”?；蜃x作“組成的復合命題記作和、命題析取詞q

5、pqpqp,).3的邏輯抽象。、“或者”中的可兼或是自然語言中的“或”pqp qFFFFTTTFTTTT：燈泡壞了。：開關壞了。qp1.1 命題和命題聯結詞開關壞了或燈泡壞了。pq：例：1.張曉婧愛唱歌或愛聽音樂。 2.張曉婧是內蒙人或是陜西人。 3.張曉婧只能挑選202或203房間。1.1 命題和命題聯結詞注意：當排斥或兩邊的情況實際根本不可能同時發生的時候，排斥或也可抽象為。但為了方便起見一般不這樣抽象。稱作后件（結論）。，”。稱為前件（前提）條件或“”則讀作“如果組成的復合命題記作和、由命題蘊涵詞qqpqppqp,q).4的邏輯抽象?！保瑒t”，“若，則是自然語言中的“如果pqp qFFT

6、FTTTFFTTT有位父親對兒子說：“如果我去書店，就一定給你買電腦報“。問：在什么情況下，父親算失信呢？1.1 命題和命題聯結詞注意：“只要p，就q，因為p，所以q”，“p僅當q”，只有q，才p“，”除非q才p“，”除非q，否則非p“都可抽象為pq。p，q可以沒有任何內在聯系。例：1.如果336，那么雪是白的。2.除非我能工作完成了，我才去看電影。3.只要天下雨，我就回家。4.我回家僅當天下雨。pq的邏輯關系為q是p的必要條件或p是q的充分條件。1.1 命題和命題聯結詞的邏輯抽象。條件”，“當且僅當”是自然語言中的“充要”。當且僅當讀作“組成的復合命題記作和、由命題等價詞qp,).5qpqp

7、pqp qFFTFTFTFFTTT1.1 命題和命題聯結詞p q的邏輯關系為p與q互為充要條件例：1.3是有理數當且僅當加拿大位于亞洲。2.兩圓的面積相等，則他們的半徑相等，反之亦然。6.q異或聯結詞指的是排斥或，當且僅當p、q的真值相異時，p為真。pqp qFFFFTTTFTTTF)()()2(qp1qpqpqppq等價于等價于）（有如下性質：由定義知1.1 命題和命題聯結詞例：今天第一節課上離散數學或數據結構。左往右的次序運算。）同級的聯結詞，按從（省略不必要的括號。）按優先級書寫，可以（。，）由強到弱依次是：（聯結詞的優先次序：32,1例：p：北京比天津人口多 q：224 r：烏鴉是黑色

8、的pqpqrrqqp)2(1）（求以下命題的真值1.1 命題和命題聯結詞5、語句形式化）選擇命題聯結詞。（命題）；）確定原子命題（簡單（形式化的步驟：211.1 命題和命題聯結詞例：2是有理數是不對的；2是偶素數；2或4是素數；如果2是素數，則3也是素數；2是素數當且僅當3也是素數。p：2是有理數，q：2是偶數，r：2是素數，s：3是素數，t：4是素數。p不對；q且r；r或t；如果r，則s；r當且僅當s。跳墻。中的聯結詞，如：狗急）要善于識別自然語言（，如：我和他是同學。）給定句子是否是命題（注意：21去郊游，否則就不去。如果明天天氣好，我們表。選小陳或小周一人為代踐經驗。他雖有理論知識但無實

9、。么你一定會成為近視眼如果你走路時看書，那自討沒趣。，那么你們倆都不會去如果你和他不都是傻子例. 5. 4. 3. 2. 11.1 命題和命題聯結詞命題常元：表示具體確定內容的命題。命題變元：表示不確定具體內容的命題。題公式。）得到的符號串都是命）、（）有限次的使用（也是命題公式；是命題公式，則、）若（公式；公式，稱其為原子命題）單個命題變元是命題（命題公式的遞歸定義：定義213,qp,q21.1qpqpqpqppp1.2 命題公式及其賦值rpprqppqpqrrqqp)5()4()3()2(1 ）例（1.2 命題公式及其賦值同時約定：（1）最外層的括號可以省去。 （2）不影響運算次序的括號也

10、可以省去。層公式，是，則公式或或或或層公式，且，分別是，）若公式（層公式；是，則層公式且是）若公式（層公式；其為為單個命題變元，則稱）公式（命題公式的層次：定義),max(1nACBACBACBACBACBAjiCB31nABAnB20A1. 2jin 1.2 命題公式及其賦值pqpqrrqp)2(1 ）例（1.2 命題公式及其賦值rqp )(是有理數：是偶數，：是素數，：232rqp是無理數：是偶數，：是素數，：232rqp稱為成假賦值。的成真賦值，否則，則稱其為的真值為若指定的一組值使的一組賦值或解釋。對一組確定的取值，稱為給的命題公式，為含有命題變元設定義A1Ap,p,.32121App

11、ppAnn的真值表。稱為情況列成表，在其全部賦值下的真值將公式定義AA. 41.2 命題公式及其賦值1n1)1223FnFnnnn真值表的構造步驟：（ ）若公式共有（個變元，則真值表第一行寫出個變元，公式F寫在第列。（ ）寫出 個變元的所有可能取值（種）,按從低到高的順序寫出公式的各層次。（ ）在不同賦值下求出各層次的真值及 的真值。為可滿足式。的值為真，則稱）若至少有一組賦值使為永假式；為假，則稱在所有賦值下的取值均）若為永真式；為真，則稱在所有賦值下的取值均若，公式定義AA3AA2AA) 1. 5A1.2 命題公式及其賦值pqpqrrqp)2(1 ）例（也是重言式。為重言式，則和若定理BA

12、BABA,. 11.2 命題公式及其賦值1.,ABABA BAB定義 設 和 是兩個命題公式，若為重言式，則稱公式是等值的公式，記作。1.p)();.qqpppp 例 證明（.qpq注意： 和的區別是公式間的關系符號，如：p是命題聯結詞1.3 命題公式的等值式 , ABAB ABBAABCABC ABCABCABCABACABCABAC交換律：結合律：分配律：)(),(),()pqpqpqrpqrpqr 例： （與基本等值式（基本等值式（A，B，C為任意命題公式）為任意命題公式）1.3 命題公式的等值式0,110A,1, ,1.11,00(),AA AAAAAAAAAA AAA AAAAAAA

13、A AAAAABA AABAABABABAB 同一律：互補律：，重補律：等冪律：零一律：A吸收律：德摩根律：1.3 命題公式的等值式, BABABBABABBAABABBAABABABABAB 蘊含等值式：A假言易位：等價等值式：A等價否定等值式：歸謬論：(AB) (AB)A因A，B，C可以代入任意的命題公式，故以上等值式稱為等值式模式。由已知的等值式推演出另外一些等值式的過程為等值演算。1.3 命題公式的等值式( )( )( ) ABA(B)(A)AABBA 置換規則：設是含公式 的命題公式，是用公式 置換了中所有的 后得到的命題公式。若，則等值演算的應用： 1.驗證等值式 2.判定公式的類

14、型 3.解決工作生活中的判斷問題 2.qpqqp 例 等值等價式p1.3 命題公式的等值式()()()pqprpqr(), (),()pqpqppqr ppqpq甲、已、丙3人根據口音對王教授是哪人進行了判斷： 甲說：王教授不是蘇州人，是上海人 已說：王教授不是上海人，是蘇州人 丙說：王教授既不是上海人，也不是杭州人結果3人中有一人全對，一人對一半，一人全錯。問王教授是哪人？聯結詞的完備集.0,10,1n.nF定義稱 ：為 元真值函數0,10 1nn中的元素為由 ， 組成的長為 的符號串n個命題變元可以形成22n個不同的真值函數對于每個真值函數，都可以找到許多與之等值的命題公式，而每個命題公式

15、對應唯一的與之等值的真值函數。定義.設S是一個聯結詞集合，如果任何n（n1）元真值 函數都可以由僅含S中的聯結詞構成的公式表示，則 稱S是聯結詞完備集。. , , Th S 是聯結詞完備集.345S , , , , , ,SSS 12推論：以下聯結詞集都是完備集 , , ,S.,p qpq定義 設為兩個命題，復合命題“ 與（或） 的否定式”稱作p,q的與（或）非式，記作pq(pq). , Th 也是聯結詞完備集.聯結詞的完備集1.4 析取范式與合取范式定義：命題變元及其否定統稱為文字。 僅由有限個文字構成的析取式稱為簡單（質）析取式。 僅由有限個文字構成的合取式稱為簡單（質）合取式。,pp p

16、q pq例：注意：單個文字既是簡單析取式又是簡單合取式。討論：設A為含n個文字的簡單析取式 若A中同時含pi和pi，則？若A為永真式，則？若A為永真式，則A中必同時含有pi和pi，反之亦然。同理有，若A為簡單合取式，A為永假式的充要條件是A中同時含有pi和pi。定理1. 一個簡單析取式是重言式當且僅當它同時含有某 個命題變元及其他的否定。 一個簡單合取式是矛盾式當且僅當它同時含有某 個命題變元及其他的否定。1.4 析取范式與合取范式定義：由有限個簡單合取式構成的析取式稱為析取范式。 由有限個簡單析取式構成的合取式稱為合取范式。 析取范式與合取范式稱為范式。,()()pp pq pqpqpq 例

17、：注意：單個文字、簡單析取式、簡單合取式都既是析取范 式又是合取范式。1.4 析取范式與合取范式定理2. 一個析取范式是矛盾式當且僅當它的每個簡單合 取式為矛盾式。 一個合取范式是重言式當且僅當它的每個簡單析 取式為重言式。定理3.任一命題公式都存在與之等值的析取范式和合取范式。范式的求法：消去公式中的蘊涵、等價和異或聯結詞 使用雙重否定律和德摩根律，將公式中出現 的否定 詞移到命題變元之前。 利用分配律、結合律將公式化為合（析）取 范式。,()rpqrp例：(pq)范式形式不唯一。1.4 析取范式與合取范式定義：在含有n個命題變元的簡單合（析）取式中，若每個 命題變元和 它的否定式不同時出現

18、，而二者之一必 出現且僅出現一次，且第 i個命題變元或它的否定是 出現在從左算起的第i位上（字典序），稱這樣的簡 單合（析）取式為極小（大）項。,()pqpq pq pqpq 例：性質：n個變元可以形成2n個極?。ù螅╉?； 每個極小（大）項有且僅有一個成真（假）賦值； 每組賦值下僅有一個極?。ù螅╉棡檎妫伲?； 所有極小（大）項的析（合）取為真（假）；1.4 析取范式與合取范式將極小項的成真賦值對應的二進制數轉化為十進制數為i，將對應的極小項記為mi。將極大項的成假賦值對應的二進制數轉化為十進制數為i，將對應的極大項記為Mi。定義：設由n個命題變元構成的析（合）取范式中所有的簡 單合（析）取式

19、都是極?。ù螅╉?，則稱該析取范 式為主析（合）取范式。1.4 析取范式與合取范式定理.任何命題公式都存在與之等值的主析取范式和主合取范 式，并且是唯一的。1.4 析取范式與合取范式公式法：求析取范式 用同一律補進未出現的命題變元 消去永假或重復出現的變元和極小項 將極小項按下標從小到大排列真值表法：列出公式及各極小項的真值表，將每組賦值下 公式及極小項真值都為真的極小項進行析取。主析取范式的求法：1.公式法2.真值表法1.4 析取范式與合取范式應用：1.求公式的成真、成假賦值 成真賦值為析取范式中所含極小項的編碼的二進制數 成假賦值為合取范式中所含極大項的編碼的二進制數12i, m;iiiiM

20、p pMMmin定理.設m 與是,p 形成的極小項、極大項，則，由主析取范式可以直接求主合取范式： 1求出主析取范式中未包含的極小項 2求出與1中求出的極小項下標相同的極大項 3做2中極大項之合取1.4 析取范式與合取范式3.判斷兩公式是否等值 若A，B共含有n個命題變元，按n個命題變元求出A與B的主析取范式A、B，若AB，則AB.2.判斷公式的類型 設A含有n個命題變元A為重言式當且僅當A的主析取范式含全部2n個極小項； A為矛盾式當且僅當A的主析取范式不含任何極小項，此 時記為0；A為可滿足式當且僅當A的主析取范式中至少含一個極小項。例：要在A，B，C中挑選2名出國進修，選派時滿足下列條件

21、： 若A去，則C同去 若B去，則C不能去 若C不去，則A或B可以去問有幾種選派方案，分別是什么？4.解決實際問題1.4 析取范式與合取范式222222, ,A AA BA AA BAAAAAABA AABA AAB1k1k1k1k1k1k定義.設,都是公式，若，的任意 一組賦值，或者為假，或者和 同為真，則稱由前提，推出 的推理 是有效的或正確的，稱，為前提集合為 有效結論.1.5推理的形式結構注意：推理正確實際是排除前提真結論假的情況推理是否正確與前提的排列順序無關推理正確并不能保證B一定為真12)kAAAB若推理正確，則記作(1212.,BBkkAAAAAA定 理 公 式推的 推 理 正

22、確 當 且 僅 當 （）為 永 真 式 。1.5推理的形式結構212,B kA AABAAA1k由，推 ，記作（）推理的形式結構1212,kkAAABAAAB用（）作為推理的形式結構，證明時要先寫成前提：,結論：12)kAAAB論證推理是否正確，就是判斷(是否為永真式真值表法方法有等值演算法主范式法1.5推理的形式結構例：若下午溫度超過30度，則王曉燕必去游泳。若她去游 泳，她就不會去看電影。所以若王曉燕沒去看電影， 下午溫度必超過了30度。p：溫度超過30度q：王曉燕去游泳r：王曉燕去看電影,pq qrrp 前提：結論：1.5推理的形式結構,()() AABABAABABABBAABBAAB

23、BCACABBCACABCDACBDABABAABABCDBDAC 附加律：化簡律：假言推理：拒取式：析取三段論：假言三段論：等價三段論：構造性二難：破壞性二難：1.5推理的形式結構注意：以上都是蘊含式模式若某推理的形式結構與某定律一致，則推理正確成立的等值式可產生兩條定律推理定律可產生相應的推理規則1.5推理的形式結構1.6自然推理系統P定義.一個形式系統I由以下4部分組成： 非空的字母表，記作A(I) A(I)中符號構成的合式公式集，記作E(I) E(I)中特殊的公式組成的公理集，記作Ax(I) 推理規則集，記作R(I)自 然 推 理 系 統形 式 系 統公 理 推 理 系 統任給的前提，

24、應用規則得到結論（可能真）任給的公理，應用規則得到結論（永真）P, , , ,2.1.63.1(P)iiip q rp q r 定義.自然推理系統或1.字母表， ， ，（）和，合式公式定義中所定義的所有命題公式推理規則（）前提引入規則：證明的任何步驟上都可以引入前提1.6自然推理系統P(2)結論引入(T)規則：證明的任何步驟上所得的結論都可作為 后繼證明的前提（3）置換規則：在證明的任何步驟上，命題公式中的子公式都 可以用與之等值的公式置換ABABABAB(4)假言推理規則：若序列中已出現和 ，則可將 引入序列中(5)附加規則;（6）化簡規則;（7）拒取式（8）假言三段論規則;（9）析取三段論

25、規則（10)構造性二難規則;（11）破壞性二難規則（12）合取引入規則：若序列中出現了和 ，則可將引入序列中1.6自然推理系統P,()pq qr pssrpq例：前提： 結論：例：若小王是理科生，則他的數學成績一定很好。如果 小王不是理科生，他一定是文科生。小王的數學成績 不好。所以小王是文科生。p：小王是理科生q：小王是文科生r：小王的數學成績很好,prpqrq前提：結論：1.6自然推理系統P12121.()()()kkAAAABAAAAB附加前提證明法若推理形式為，則可轉換為例：如果小張和小王去看電影，則小李也去看電影。小趙 不去看電影或小張去看電影。小王去看電影。所以， 當小趙去看電影時

26、，小李也去。p：小張去看電影q：小王去看電影r：小李去看電影s：小趙去看電影(),pqrsp qsr 前提：結論：1.6自然推理系統P1212()()()kkAAABAAAB 2.歸謬法將結論的否定作為前提引入，能推出矛盾來，則推理正確例：如果馬會飛或羊不吃草，則母雞就會是飛鳥。如果母 雞是飛鳥，那么烤熟的鴨子還會跑?？臼斓镍喿硬粫?跑。所以羊吃草。p：馬會飛q：羊吃草r：母雞是飛鳥s：烤熟的鴨子會跑(),pqr rssq 前提：結論：1.6自然推理系統P所有的人總是要死的。蘇格拉底是人。所以蘇格拉底是要死的。p:q:r:, p qr前提：結論：()pqr推理形式：第二章 謂詞邏輯第二章 謂詞

27、邏輯v2.1一階邏輯命題符號化v2.2一階邏輯公式及解釋v2.3一階邏輯等值式與置換規則v2.4一階邏輯前束范式v2.5一階邏輯的推理理論2.1一階邏輯命題符號化個體常項個體變項, , ,iiia b ca b c用表示, ,iiix y zxyz用表示1.個體詞所研究對象中可以獨立存在的具體的或抽象的客體（事物）表示具體的或特定的客體表示抽象或泛指的客體個體變項的取值范圍稱為個體域，用D表示宇宙間一切事物組成的稱為全總個體域1,2,3,N R有窮，無窮，謂詞常項：具體性質或關系的詞謂詞變項：抽象或泛指的性質或關系的詞2.謂詞用來刻劃個體詞性質及個體詞之間相互關系的詞,iiiF G HF GH

28、用,表示2是有理數x是無理數小王與小李同歲x與y具有關系L是有理數是無理數與同歲與具有關系LF：G：H：L：2.1一階邏輯命題符號化3.量詞：個體詞之間的數量關系（1）全稱量詞 “一切的”，“所有的”，“每一個”，“任意的”，“凡”，“都” 記作(2) 存在量詞 “存在”，“有一個”，“有的”，“至少有一個”記作4.符號化 確定個體域確定個體詞、量詞和謂詞確定聯結詞2.1一階邏輯命題符號化例：所有的人都是要死的。 有的人用左手寫字。注意：全稱量詞的特性謂詞必須作為蘊涵式的前件引入存在量詞的特性謂詞必須作為合取式的合取項引入同一命題，不同的個體域符號化的形式可能不同未指明個體域即為全總個體域2.

29、1一階邏輯命題符號化例：在美國留學的學生未必都是亞洲人。 有的兔子比所有的烏龜跑的快。 對任意的整數x，都存在整數y使得xy10。注意：多個量詞出現時，順序一般不能隨便換有些命題符號化形式不唯一2.1一階邏輯命題符號化2.2一階邏輯公式及解釋.F(1), , ,(2), , , , ,(7) ( ),iiiiiiiiiiiia b ca b cx y zx y zf g hf g hF G HF G H 定義一階語言 的字母表個體常項：，個體變項：，(3)函數符號：，(4)謂詞符號：，(5)量詞符號： ，(6)聯結詞: , , ,和121212( ,)n, , ,n( , ,)(3)(1)(2

30、)nnnx xxt ttt tt定義.一階語言的項的定義(1)個體常項和個體變項是項；(2)若,是任意的 元函數, 是一階語言的任意 個項，則,是項；所有的項都是有限次使用得到的。121212.( ,)n, , ,n( , ,)nnnR x xxt ttR t tt定義設，是一階語言的任意 元謂詞, 是一階語言的任意 個項，則稱，是 一階語言的原子公式。2.2一階邏輯公式及解釋.(1)(2)()(3),(4),(5)AAA BAB AB AB ABAxAxA定義一階語言的合式公式的定義原子公式是合式公式；若 是合式公式，則也是合式公式；若是合式公式，則也是合式公式；若 是合式公式，則也是合式公

31、式；只有有限次地應用(1)(4)構成的符號串才是合式公式。合式公式也稱謂詞公式，簡稱公式2.2一階邏輯公式及解釋.,xAxAxxAxAxA定義在公式中，稱 為指導變元，A為相應量詞的轄域。在的轄域中， 的所有出現稱為約束出現， 中不是約束出現的變元均稱為自由出現。( ( , )( , ) ( ( )( )( )( , , )x F x yG x zx F xG yy H xL x y z 例：.AAA定義設 是任意的公式，若 中不含自由出現的個體變項，則稱 為封閉的公式，簡稱閉式。2.2一階邏輯公式及解釋( ( )( ) ( ( )( )( , )( ( , ), ( , )x F xG xx

32、 y F xF yG x yH f x y g x y 例：12.I(1)(2) ,(3)| ,1(4)| ,1.IIinIinIiDDa aaDfi nDFi n定義一階語言的解釋 由以下部分組成非空個體域；中一些特殊元素的集合,；上特定函數集合；上特定謂詞集合2.2一階邏輯公式及解釋I(1)(2)(3)(4).IinniinniiDaffFF對 的說明：公式中的個體變項均取值于；若含個體變項就解釋為 ；若含函數就解釋為 ；若含謂詞就解釋為2.2一階邏輯公式及解釋I(1) D=N=0,1,2, (2) 0(3) ( , ), ( , )(4) ( , )af x yxy g x yxyF x

33、 yxy例：解釋 ：為(1)( ,),( ,)(2)( ,), )(3)( ,), )( ,)Ff x yg x yxF g x axxF g x axF x y定理.閉式在任何解釋下都變成命題。2.2一階邏輯公式及解釋.AAAAAAA定義設 為公式 若 在任何解釋下均為真，則稱 為永真式(邏輯有效式). 若 在任何解釋下均為假，則稱 為永假式(矛盾式). 若至少有一個解釋使 為真，則稱 為可滿足式。0121200., n(1),nniiAp ppA AAAinApAA 定義設是含命題變項， 的命題公式，是個謂詞公式，用處處代替 中的所得公式 為 的代換實例。2.2一階邏輯公式及解釋( )(

34、,)( )( )( )( )( )( )( )( )xF xx yG x yxF xxF xyG yyG yx F xG xx F xG x 例：定理.重言式的代換實例都是永真式，矛盾式的代換 實例都是矛盾式。( )( )( )( )( )xF xxF xx F xG xyG y 2.2一階邏輯公式及解釋2.3一階邏輯等值式與置換規則A BABABAB定義.設 , 是一階邏輯中任意兩個公式，若是永真式， 則 與 等值，記作1212121.D=,( )()()()( )()()()nnnaaaxA xA aA aA axA xA aA aA a消去量詞等值式 ,第一組第一組 命題邏輯中等值式模式

35、的代換實例都是一階邏 輯的等值式模式第二組第二組 一階邏輯中特殊的等值式 , , ,( )( ),( ,)Da b cxF xyG yxyF x y 2.( )( )( )( )xA xx A xxA xx A x 量詞否定等值式3.(1)( ( )( ) ( ( )( ) ( ( )( ) ( )( )x A xBxA xBx A xBxA xBx A xBxA xBx BA xBxA x 量詞轄域收縮與擴張等值式(2)( )( ) ( )( ) ( )( ) ( )( )x A xBxA xBx A xBxA xBx A xBxA xBx BA xBxA x 2.3一階邏輯等值式與置換規則

36、( ( )( )( )( )( ( )( )x A xB xxA xxB xx A xB xxA xxB x 4.量詞分配等值式( )( )x A xB xxA xxB xx A xB xxA xxB x 5.量詞分配蘊涵式（ ） （ ）（ ）（ ）（ ） （ ）（ ）（ ）D=N，F(x)：x是奇數 G(x)：x是偶數2.3一階邏輯等值式與置換規則( )( ),( )( )AABBAAABAB 置換規則 設是含公式 的公式，是用 取代 (中的所有的 之后的公式。若則。AAAA換名規則 設A為一公式，將 中某量詞轄域中某約束變項的所有出現及相應的指導變元，改成該量詞轄域中未曾出現過的某個體變項

37、的符號，公式中其余部分不變，設所得公式為,則2.3一階邏輯等值式與置換規則AAAAA代替規則 設 為一公式，將 中某自由出現的個體變項的所有出現用A中未曾出現過的某個體變項的符號代替，公式中其余部分不變，設所得公式為,則( , )( , ) ( ,)( , )xF x y zyG x y zx F x yyG x y z 例：( ( )( )( ( )( ) ( ( )( )( , )( ( )( )( , )x F xG xx F xG xx y F xG yL x yx y F xG yL x y 證明：2.3一階邏輯等值式與置換規則2.4一階邏輯前束范式為了方便使用謂詞公式進行定理證明和

38、邏輯推理，需要把謂詞公式變換為便于使用的規范形式，就是范式。 112233kki112233kk.AAQ x Q x Q xQ x BQBAQ x Q x Q xQ x B定義設 為一個一階邏輯公式，若 具有 形式，其中每個為量詞 或 ， 為不含量詞的 謂詞公式，則稱 為前束范式，稱為公式的首標， 為公式的尾部。)()()(),()2();,()()() 1 (1yQxRxQyxPzyxzxRyQxPzyx：例定理1：任一謂詞公式都可以化成為與之等值的前束范式。1(B23求前束范式的步驟：、消去可能出現的多余量詞 在 中無相應變項的量詞）；、利用換名或代入規則使所有約束變元的符號均不相同，并且

39、自由變元與約束變元的符號也不相同；、利用量詞轄域的擴張和收縮律，將所有量詞以在公式中出現的順序移到公式的最前面，擴大量詞的轄域至整個公式。2.4一階邏輯前束范式( )( )( , )( , )( , )( )( , , )xF xxG xxF x yyG x yxF x yyG yxH x y z 例：2.4一階邏輯前束范式2.5一階邏輯的推理理論1212,BBkkA AAAAA從,推出結論 的推理形式在一階邏輯中，稱永真的蘊涵式為推理定律。若一個推理的形式結構正是某條推理定律，則該推理顯然是正確的。第一組第一組 命題邏輯推理定律的代換實例第二組第二組 由基本等值式生成的推理定律第三組第三組

40、以下重要定律( )( )( ( )( )( ( )( )( )( )( ( )( )( )( )( ( )( )( )( )xA xxB xx A xB xx A xB xxA xxB xx A xB xxA xxB xx A xB xxA xxB x 第四組第四組 消去量詞和引入量詞的推理規則1、全稱量詞消去規則（UI）2.5一階邏輯的推理理論)()(yAxxAUI規則成立的條件： （1）取代x的y應為任意不在A(x)中約束出現的個體變項； （2）用y取代A(x)中自由出現的x時，必須將所有的自由出現x都取代； （3）自由變元y也可替換為個體域中任意的個體常元c，c為任意不在A(x)中出現過

41、的個體常項。)()(cAxxA2.5一階邏輯的推理理論),( : :1yxyLxyxL(x,y)RD：例含義：如果個體域的所有個體都具有性質A，則個體域中的任一個個體都具有性質A。 2、存在量詞消去規則（EI）)()(cAxxA含義：如果個體域存在有性質A的個體，則個體域中必有某一個個體具有性質A。 2.5一階邏輯的推理理論ES規則成立的條件： （1）c是個體域中使A為真的特定的個體常項； （2）c不曾在A(x)或前面的推導公式中出現過； （3）A（x）中除x外還有其他自由變元時，不能用此規則1xxA ND2）：（：例),( : :3yxyLxyxL(x,y)RD：例2.5一階邏輯的推理理論）

42、（）（是偶數）：（是奇數）：（：例xxQxxPxxQ xxP ND43、全稱量詞引入規則（UG）( )( )A yxA x UG規則成立的條件： （1）y在A（y）中自由出現，且y取任何值時A均為真；（2）x不在A（y）中約束出現。 含義：如果個體域的任意個體都具有性質A，則個體域中的所有個體都具有性質A。 ),(A(x) : :5yxyLyxL(x,y)RD：例2.5一階邏輯的推理理論4、存在量詞引入規則（EG）( )( )A cxA x EG規則成立的條件： （1）c是個體域中某個確定的個體；（2）代替c的x不在A（c）中出現過。 含義：如果個體域有某一個個體c具有性質A，則個體域中必存在

43、具有性質A的個體。 ), 8(A(8) : :6yyLyxL(x,y)RD：例2.5一階邏輯的推理理論定義.一階邏輯自然推理系統F的定義 1.字母表：同一階語言的字母表 2.合式公式：同一階語言合式公式的定義 3.推理規則 a.前提引入規則 b.結論引入規則 c.置換規則 d.假言推理規則 e.附加規則 f.化簡規則 g.拒取式規則 h.假言三段論規則 i.析取三段論規則 j.構造性二難規則 k.合取引入規則 l. UI，EI，UG，EG2.5一階邏輯的推理理論例7：證明邏輯三段論 所有的人總是要死的。 蘇格拉底是人。所以蘇格拉底是要死的。( ( )( ( )( )( )( ( )( )x F

44、 xG yH xxF xx F xH x例8：已知前提，證明結論：2.5一階邏輯的推理理論2.5一階邏輯的推理理論例10：如果一個人怕困難就不會獲得成功。每一個人或者獲得成功或者是失敗的。有些人未曾失敗過，所以有些人不怕困難。（個體域是人的集合）判斷這個推理是否正確。 例9：根據前提集合：同事之間總是有工作矛盾的，張平和李明沒有工作矛盾，能得出什么結論？第二部分 集合論v第三章 集合代數v第四章 二元關系v第五章 函數第三章 集合代數v3.1 集合的基本概念v3.2 集合的運算v3.3 集合恒等式一、集合的概念集合（set)的含義：一個集合是作為整體識別的、確定的、互相區別的一些事物的聚集（全

45、體或總體等)。構成一個集合的每個事物，成為這個集合中的元素或成員。集合一般用A、B、C表示，集合中的元素用a、b、c表示。但這不是絕對的，因為一個集合可以作為另一個集合的元素。如果x是集合s的一個元素,記作 ; y不是集合s的元素，記作 sxsy3.1集合的基本概念例1： 1.偶素數集合。2.二進制的基數集合。3.英文字母的集合。4.全體實數的集合。5.自然數集合。6.整數集合。7.有理數集合。8.素數集合。3.1集合的基本概念3.1集合的基本概念集合的表示方法: 1.列舉法（枚舉法、外延法）把集合的所有元素（元素較少時）寫在一個花括號內;列出足夠多的元素（元素很多或無窮時）以反映集合中元素的

46、特征。如例1中的1、2、3、5可分別表示為：20，1a，b，cz，A，B，CZ1，2，33.1集合的基本概念2.描述法（概括法）將集合中的元素的性質用一個謂詞公式來描述，S=X|P(X),意義為:集合S由且僅由滿足為此公式P(X)的對象組成，即 ，當且僅當p(a)為真。如例1中的4、6、7可表示為：sa|Rxx|Qxx3.文氏圖用圖形圖像直觀的描述集合之間的相互關系和有關運算。|Ixx3.1集合的基本概念幾個常見集合的表示符號：N：自然數集合，N=0，1，2，3；I：整數集合；P：素數或質數集合；Q：有理數集合；R：實數集合；C：復數集合；3.1集合的基本概念集合的特性:A.互異性：一個集合的

47、個元素是可以區分開的，即每一 元素只出現一次。B.無序性：集合中元素排列順序無關緊要，即集合表示 形式的不唯一性。例2：a，b，c=b，c，a=c，a，b=a，c，b=b，a，c=c，b，a3.1集合的基本概念C.確定性：任一事物是否屬于某一集合，回答是確定的。例3：“好書”的全體，這不構成集合。注意：一個集合是已知的，指的是對任一元素，利用某種方法可以判斷它是否是這個集合的元素，而不是把集合的每一個元素都給出來。3.1集合的基本概念集合的元素可以是任何具體或抽象的事物，包括別的集合，但不能是本集合自身。例4：在一個住著一些人家的偏僻孤島上，島上只有一個理發師a，a給且只給島上所有不能自己理發

48、的人理發。問誰給a理發？定義1.設A和B是兩個集合，若A中的每一個元素都是B的元素，則稱A是B的子集，也稱B包含A,記作)(ABBA3.1集合的基本概念定義2.設A和B是任意兩個集合，若A包含B且B包含A，則稱A與B相等，記作A=B.即，ABBABA|BxAxxBA二、集合的關系3.1集合的基本概念定義3.若A是B的子集且 ，則稱A為B的真子集，或稱B真包含A，記作，B稱為A的超集。是集合間的包含關系。、；是元素與集合間的關系的區別：和、注意BA BA BABABA. 2 . 15中國人臺灣人臺灣人都是中國人。：例CRQN集合的相等關系的性質：。，則且傳遞性：若）（；，則對稱性：若）（；自反性

49、：CACBBAABBAAA.3.2).1 (設A,B,C為3個集合，集合的包含關系的性質:。，則且傳遞性：若）（；，則且反對稱性：若）（；自反性：CACBBABAABBAAA.3.2).1 (3.1集合的基本概念, 01x|xA62Rx：例定義4.不包含任何元素的集合稱為空集，記作或推論：空集是唯一的。集。：空集是一切集合的子定理1 .7.6 .5.4 ).3().2( .17）（）（；）（）（；）（：判斷下列命題的真假例3.1集合的基本概念三、特殊集合定義4：在一定范圍內，如果所有集合均為某一集合的子集，則稱該集合為全集，記作E。 。，；例：210 1 0定義5.集合中元素的個數稱為基數或勢

50、，用|A|表示?；鶖凳怯邢迶档募戏Q為有限集，否則稱為無限集。全集是相對的，不同的問題有不同的全集，即使是同一個問題也可以取不同的全集 。3.1集合的基本概念3.1集合的基本概念含n個元素的集合簡稱n元集，其含有k(kn)個元素的子集稱為它的k元子集。定義6.由集合S的所有子集組成的集合，稱為集合S的冪 集，記作P（S）。表示為：.|)(SAASP有限集S ，|P（S）|=2|S|例：Aa，b，c，d，c3.2 集合的運算一、集合的基本運算BxAx|xBA BA BABA1.且。的交集，記作與稱為，的公共元素組成的集合和，由和設有集合定義 BA| . B. 2BxAxxBABABAABA或的并

51、集，記作與稱為，的所有元素組成的集合和，由和設有集合定義.iiiiAA與分別記為，算推廣到任意多個集合將集合的交運算和并運| . . 3BxAxxBABAABBABA且的相對補集，記作對稱為，的一切元素組成的集合但不屬于，由屬于、設有集合定義3.2 集合的運算|.BxxBxExxBEBBBEB且的絕對補集，記作的相對補集，稱為對全集)()( )()( | .BA . 4BABAABBAAxBxBxAxxBABAABBABA且，或且的對稱差，記作與的集合，稱為元素組成的但不屬于，或屬于但不屬于，由屬于、設有集合定義CABACABACBACBCBA)( ,),(,63851321求，、，、，：例定

52、義5.設A 為集合， A 的元素的元素構成的集合稱為A的廣義并，記作A 。3.2 集合的運算A x|z (zA xz)若A A1,A2,，An，則A A1A2 An 定義6.設A 為非空集合， A 的所有元素的公共元素構成的集合稱為A的廣義交，記作A 。A x|z (zA xz)若A A1,A2,，An，則A A1 A2 An 例：Aa，b，c，a，b，e B=a C=a，c，d集合運算的優先級：高級：廣義并、廣義交、絕對補、求冪集；同級按從右向左的順 序進行低級：并、交、相對補和對稱差；同級按從左向右的順序進行3.2 集合的運算3.2 集合的運算 文氏圖可以用來描述集合間的關系及其運算.在文

53、氏圖中,全集用矩形表示,子集用圓形表示,陰影部分表示運算結果的集合.二、文氏圖ABBABABAAB BAB ABA 3.2 集合的運算A A3.3 集合恒等式一、集合運算定律以下列出集合性質中最主要的幾條基本定律，對于全集E的任意子集A，B，C，有：A;BBAA,BB AABBA , ) 1 (交換律;) , )2(CBACB A C,BAC(BACBACBA結合律 C);(AB)(AC)(B A, CABACBA,CABACBACABACBA ,)3(分配律A;A A,-A A,A ,A )4(EA同一律;AA , 5EAA）互補律（；）重補律（AA 6; ,7AAAAAA）等冪律（; ,

54、, ,)8(AAAAAEEA零一律; ,)9(ABAAABAA吸收律）；（德摩根律CABACBACABACBABABABABA()()( ),()()(,)( ,)10().()( )()( )()(,11BABAABBABABABABABA）功能完備律（3.3 集合恒等式1、基本定義法根據集合相等的充要條件等式兩邊互為子集或由定義進行等價推理。2、公式法利用已證明過的恒等式去證明另外的恒等式。若表達式中出現形為A-B的差集時，用功能完備律先將運算“-”轉化為運算“ ”和“”。二、集合恒等式證明3.3 集合恒等式).()()(:1CABACBA證明分配律例)()()()()()()()()(:

55、CABAxCAxBAxCxAxBxAxCxBxAxCBxAxCBAx證明3.3 集合恒等式).()()(:2CABACBA證明德摩根律例)()()()()()()()()()()(:CABAxCAxBAxCxAxBxAxCxBxAxCxBxAxCBxAxCBxAxCBxAxCBAx證明3.3 集合恒等式)()()(:3CABACBA證明例CBACBACBA)()(:證明CBACBACBAABACABACABACABA)()()()()()()()()(3.3 集合恒等式小 結集合的概念集合的特性集合的表示方法:列舉法、描述法、文氏圖集合的運算：并、交、補、差、求冪集合間的關系：包含、相等集合恒

56、等式的證明：定義法、公式法、成員表法第四章二元關系v4.1 有序對與笛卡兒積v4.2 二元關系v4.3 關系的運算v4.4 關系的性質v4.5 關系的閉包v4.6 劃分和等價關系v4.7 偏序關系定義1.由兩個具有固定次序的個體a，b組成的序列,稱為序偶,記作.其中a,b稱為序偶的分量.定義2.設和是兩個序偶,若a=c且b=d,則稱這兩個序偶相等,記作=.區別:集合a,b=b,a= (a=b)4.1 有序對與笛卡兒積例3:設A=a,b,c,B=1,0,則;1 ,0 ,1 ,0 ,1 ,0 ,ccbbaaBA., 1, 1, 1, 0, 0, 0cbacbaAB)(. 2BABAABBA或或除非

57、，即笛卡兒積不滿足交換律性質4.1 有序對與笛卡兒積定義3.設集合A，B，以A的元素作為第一元素，B的元算作為第二元素的有序對構成的集合稱為A與B的笛卡兒積，記作AB，符號化為AB =|xAyB性質1. A=， A=例4:設A=a,b,B=0,1,C=u,v則 vubbaaCBA,1 ,0 ,1 ,0 ,)(vbubvbubvauavaua,1 ,1 ,0 ,0 ,1 ,1 ,0 ,0 , vuvubaCBA, 1, 1, 0, 0,)(vbvaubuavbvaubua, 1, 1, 1, 1, 0, 0, 0, 0,)()(. 3CBACBACBA或或除非，即笛卡兒積不滿足結合律性質4.1

58、有序對與笛卡兒積則為任意集合設滿足分配律笛卡兒積對并、交運算性質,. 4CBA).()()();()()()()()();()()(ACABACBCABACBAACABACBCABACBA4.1 有序對與笛卡兒積)()()(:CABACBA證明)()(,)()()()(,CABAyxCAyxBAyxCyAxByAxCyByAxCByAxCBAyx4.1 有序對與笛卡兒積性質5.若AC BD，則A B CD。4.1 有序對與笛卡兒積其逆命題不成立。A=B=，成立；A ，B ，成立；A= 且 B ，不成立； A 且B= ，不成立。DBCADbCaDCbaBbAaBAba,:證明DCBADCbaDB

59、CADbCaBbAaBAba,),(,定義4.由n個具有給定次序的個體a1，a2，an組成的序列，稱為有序n元組，記作，其中ai稱為第i個分量。=當且僅當ai=bi（i=1，2，3，n）。有序n元組仍然是序偶，即=，an。4.1 有序對與笛卡兒積定義5. 設A1，A2，An是任意的n個集合，所有有序n元組組成的集合，稱為集合A1，A2，An的笛卡兒積，并用 表示。其中 （i=1，2，n）nAAAA321iiAa, 2 , 1,|2121niAaaaaAAAiinn，4.1 有序對與笛卡兒積。也是有限集合，且，則，對任意有限集合定理|,. 1321321321321nnnnAAAAAAAAAAA

60、AAAAA次冪集的稱為時，當，nAAAAAAAAnnn212121|21niAaaaaAAAAinn，4.2 二元關系定義1.若一個集合滿足以下條件之一：（1）集合非空，且它的元素都是有序對（2）集合是空集則稱該集合為一個二元關系。一、關系的定義.,.,bRaRbaRbaaRbRbaRbaBAR記作沒有關系與則稱若記作有關系與則稱若設.,2121的一個二元關系到的任意一個子集稱特別地AAAA 2121RAARAA上的關系，即到是設.,:,8 , 6 , 4 , 2,5 , 3 , 1:1baRbaRBABA當且僅當的二元關系到定義設例8 , 5,6 , 5,8 , 3,6 , 3,4 , 3,