離散數(shù)學(xué)考前復(fù)習(xí)ppt

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

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

3、星上有生命。積大。海洋的面積比陸地的面例：:962:rqp）我正在說(shuō)謊。）啊，我的天哪?。┪覀円W(xué)習(xí)。）你喜歡數(shù)學(xué)嗎？。三角形的內(nèi)角和等于8765801:s）火星上有生命。）面積大。）海洋的面積比陸地的例：396221）我正在說(shuō)謊。）啊，我的天哪?。┪覀円W(xué)習(xí)。）你喜歡數(shù)學(xué)嗎？。）三角形的內(nèi)角和等于87658014原子命題：不能被分解為更簡(jiǎn)單的陳述句復(fù)合命題：原子命題通過(guò)聯(lián)結(jié)詞聯(lián)結(jié)而成例：2是有理數(shù)是不對(duì)的；2是偶素?cái)?shù)；2或4是素?cái)?shù)；如果2是素?cái)?shù)，則3也是素?cái)?shù)；2是素?cái)?shù)當(dāng)且僅當(dāng)3也是素?cái)?shù)。p：2是有理數(shù)，q：2是偶數(shù)，r：2是素?cái)?shù)，s：3是素?cái)?shù)，t：4是素?cái)?shù)。1.1 命題和命題聯(lián)結(jié)詞4

4、、命題聯(lián)結(jié)詞”。讀作“非的否命題，記作稱(chēng)作復(fù)合命題，沒(méi)有”等否定詞組成的和“非”、“不”、“用命題否定詞pppp,).1不是質(zhì)數(shù)。：是質(zhì)數(shù)。如：的邏輯抽象。、“不”和“沒(méi)有”等是自然語(yǔ)言中的“非”44:ppp pTFFT1.1 命題和命題聯(lián)結(jié)詞”。合取”或“與讀作“組成的復(fù)合命題，記作和、是命題，由、合取詞qpqpqpqpqp,).2一面”等的邏輯抽象。、“一面但是”而且”、“雖然”、“不但又“既”、是自然語(yǔ)言中的“并且pqp qFFFFTFTFFTTT：王化的品德很好。：王化的成績(jī)很好。qp王化不但成績(jī)好而且品德好。pq：1.1 命題和命題聯(lián)結(jié)詞”。或讀作“組成的復(fù)合命題記作和、命題析取詞q

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

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

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

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

9、。么你一定會(huì)成為近視眼如果你走路時(shí)看書(shū)，那自討沒(méi)趣。，那么你們倆都不會(huì)去如果你和他不都是傻子例. 5. 4. 3. 2. 11.1 命題和命題聯(lián)結(jié)詞命題常元：表示具體確定內(nèi)容的命題。命題變?cè)罕硎静淮_定具體內(nèi)容的命題。題公式。）得到的符號(hào)串都是命）、（）有限次的使用（也是命題公式；是命題公式，則、）若（公式；公式，稱(chēng)其為原子命題）單個(gè)命題變?cè)敲}（命題公式的遞歸定義：定義213,qp,q21.1qpqpqpqppp1.2 命題公式及其賦值rpprqppqpqrrqqp)5()4()3()2(1 ）例（1.2 命題公式及其賦值同時(shí)約定：（1）最外層的括號(hào)可以省去。 （2）不影響運(yùn)算次序的括號(hào)也

10、可以省去。層公式，是，則公式或或或或?qū)庸剑?，分別是，）若公式（層公式；是，則層公式且是）若公式（層公式；其為為單個(gè)命題變?cè)?，則稱(chēng)）公式（命題公式的層次：定義),max(1nACBACBACBACBACBAjiCB31nABAnB20A1. 2jin 1.2 命題公式及其賦值pqpqrrqp)2(1 ）例（1.2 命題公式及其賦值rqp )(是有理數(shù)：是偶數(shù)，：是素?cái)?shù)，：232rqp是無(wú)理數(shù)：是偶數(shù)，：是素?cái)?shù)，：232rqp稱(chēng)為成假賦值。的成真賦值，否則，則稱(chēng)其為的真值為若指定的一組值使的一組賦值或解釋。對(duì)一組確定的取值，稱(chēng)為給的命題公式，為含有命題變?cè)O(shè)定義A1Ap,p,.32121App

11、ppAnn的真值表。稱(chēng)為情況列成表，在其全部賦值下的真值將公式定義AA. 41.2 命題公式及其賦值1n1)1223FnFnnnn真值表的構(gòu)造步驟：（ ）若公式共有（個(gè)變?cè)?，則真值表第一行寫(xiě)出個(gè)變?cè)紽寫(xiě)在第列。（ ）寫(xiě)出 個(gè)變?cè)乃锌赡苋≈担ǚN）,按從低到高的順序?qū)懗龉降母鲗哟?。?）在不同賦值下求出各層次的真值及 的真值。為可滿(mǎn)足式。的值為真，則稱(chēng)）若至少有一組賦值使為永假式；為假，則稱(chēng)在所有賦值下的取值均）若為永真式；為真，則稱(chēng)在所有賦值下的取值均若，公式定義AA3AA2AA) 1. 5A1.2 命題公式及其賦值pqpqrrqp)2(1 ）例（也是重言式。為重言式，則和若定理BA

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

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

14、型 3.解決工作生活中的判斷問(wèn)題 2.qpqqp 例 等值等價(jià)式p1.3 命題公式的等值式()()()pqprpqr(), (),()pqpqppqr ppqpq甲、已、丙3人根據(jù)口音對(duì)王教授是哪人進(jìn)行了判斷： 甲說(shuō)：王教授不是蘇州人，是上海人 已說(shuō)：王教授不是上海人，是蘇州人 丙說(shuō)：王教授既不是上海人，也不是杭州人結(jié)果3人中有一人全對(duì)，一人對(duì)一半，一人全錯(cuò)。問(wèn)王教授是哪人？聯(lián)結(jié)詞的完備集.0,10,1n.nF定義稱(chēng) ：為 元真值函數(shù)0,10 1nn中的元素為由 ， 組成的長(zhǎng)為 的符號(hào)串n個(gè)命題變?cè)梢孕纬?2n個(gè)不同的真值函數(shù)對(duì)于每個(gè)真值函數(shù)，都可以找到許多與之等值的命題公式，而每個(gè)命題公式

15、對(duì)應(yīng)唯一的與之等值的真值函數(shù)。定義.設(shè)S是一個(gè)聯(lián)結(jié)詞集合，如果任何n（n1）元真值 函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示，則 稱(chēng)S是聯(lián)結(jié)詞完備集。. , , Th S 是聯(lián)結(jié)詞完備集.345S , , , , , ,SSS 12推論：以下聯(lián)結(jié)詞集都是完備集 , , ,S.,p qpq定義 設(shè)為兩個(gè)命題，復(fù)合命題“ 與（或） 的否定式”稱(chēng)作p,q的與（或）非式，記作pq(pq). , Th 也是聯(lián)結(jié)詞完備集.聯(lián)結(jié)詞的完備集1.4 析取范式與合取范式定義：命題變?cè)捌浞穸ńy(tǒng)稱(chēng)為文字。 僅由有限個(gè)文字構(gòu)成的析取式稱(chēng)為簡(jiǎn)單（質(zhì)）析取式。 僅由有限個(gè)文字構(gòu)成的合取式稱(chēng)為簡(jiǎn)單（質(zhì)）合取式。,pp p

16、q pq例：注意：?jiǎn)蝹€(gè)文字既是簡(jiǎn)單析取式又是簡(jiǎn)單合取式。討論：設(shè)A為含n個(gè)文字的簡(jiǎn)單析取式 若A中同時(shí)含pi和pi，則？若A為永真式，則？若A為永真式，則A中必同時(shí)含有pi和pi，反之亦然。同理有，若A為簡(jiǎn)單合取式，A為永假式的充要條件是A中同時(shí)含有pi和pi。定理1. 一個(gè)簡(jiǎn)單析取式是重言式當(dāng)且僅當(dāng)它同時(shí)含有某 個(gè)命題變?cè)捌渌姆穸ā?一個(gè)簡(jiǎn)單合取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)含有某 個(gè)命題變?cè)捌渌姆穸ā?.4 析取范式與合取范式定義：由有限個(gè)簡(jiǎn)單合取式構(gòu)成的析取式稱(chēng)為析取范式。 由有限個(gè)簡(jiǎn)單析取式構(gòu)成的合取式稱(chēng)為合取范式。 析取范式與合取范式稱(chēng)為范式。,()()pp pq pqpqpq 例

17、：注意：?jiǎn)蝹€(gè)文字、簡(jiǎn)單析取式、簡(jiǎn)單合取式都既是析取范 式又是合取范式。1.4 析取范式與合取范式定理2. 一個(gè)析取范式是矛盾式當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單合 取式為矛盾式。 一個(gè)合取范式是重言式當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單析 取式為重言式。定理3.任一命題公式都存在與之等值的析取范式和合取范式。范式的求法：消去公式中的蘊(yùn)涵、等價(jià)和異或聯(lián)結(jié)詞 使用雙重否定律和德摩根律，將公式中出現(xiàn) 的否定 詞移到命題變?cè)啊?利用分配律、結(jié)合律將公式化為合（析）取 范式。,()rpqrp例：(pq)范式形式不唯一。1.4 析取范式與合取范式定義：在含有n個(gè)命題變?cè)暮?jiǎn)單合（析）取式中，若每個(gè) 命題變?cè)?它的否定式不同時(shí)出現(xiàn)

18、，而二者之一必 出現(xiàn)且僅出現(xiàn)一次，且第 i個(gè)命題變?cè)蛩姆穸ㄊ?出現(xiàn)在從左算起的第i位上（字典序），稱(chēng)這樣的簡(jiǎn) 單合（析）取式為極小（大）項(xiàng)。,()pqpq pq pqpq 例：性質(zhì)：n個(gè)變?cè)梢孕纬?n個(gè)極?。ù螅╉?xiàng)； 每個(gè)極?。ù螅╉?xiàng)有且僅有一個(gè)成真（假）賦值； 每組賦值下僅有一個(gè)極?。ù螅╉?xiàng)為真（假）； 所有極小（大）項(xiàng)的析（合）取為真（假）；1.4 析取范式與合取范式將極小項(xiàng)的成真賦值對(duì)應(yīng)的二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)為i，將對(duì)應(yīng)的極小項(xiàng)記為mi。將極大項(xiàng)的成假賦值對(duì)應(yīng)的二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)為i，將對(duì)應(yīng)的極大項(xiàng)記為Mi。定義：設(shè)由n個(gè)命題變?cè)獦?gòu)成的析（合）取范式中所有的簡(jiǎn) 單合（析）取式

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

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

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

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

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

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

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

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

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

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

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

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

31、式；只有有限次地應(yīng)用(1)(4)構(gòu)成的符號(hào)串才是合式公式。合式公式也稱(chēng)謂詞公式，簡(jiǎn)稱(chēng)公式2.2一階邏輯公式及解釋.,xAxAxxAxAxA定義在公式中，稱(chēng) 為指導(dǎo)變?cè)?，A為相應(yīng)量詞的轄域。在的轄域中， 的所有出現(xiàn)稱(chēng)為約束出現(xiàn)， 中不是約束出現(xiàn)的變?cè)Q(chēng)為自由出現(xiàn)。( ( , )( , ) ( ( )( )( )( , , )x F x yG x zx F xG yy H xL x y z 例：.AAA定義設(shè) 是任意的公式，若 中不含自由出現(xiàn)的個(gè)體變項(xiàng)，則稱(chēng) 為封閉的公式，簡(jiǎn)稱(chēng)閉式。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定義一階語(yǔ)言的解釋 由以下部分組成非空個(gè)體域；中一些特殊元素的集合,；上特定函數(shù)集合；上特定謂詞集合2.2一階邏輯公式及解釋I(1)(2)(3)(4).IinniinniiDaffFF對(duì) 的說(shuō)明：公式中的個(gè)體變項(xiàng)均取值于；若含個(gè)體變項(xiàng)就解釋為 ；若含函數(shù)就解釋為 ；若含謂詞就解釋為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定義設(shè) 為公式 若 在任何解釋下均為真，則稱(chēng) 為永真式(邏輯有效式). 若 在任何解釋下均為假，則稱(chēng) 為永假式(矛盾式). 若至少有一個(gè)解釋使 為真，則稱(chēng) 為可滿(mǎn)足式。0121200., n(1),nniiAp ppA AAAinApAA 定義設(shè)是含命題變項(xiàng)， 的命題公式，是個(gè)謂詞公式，用處處代替 中的所得公式 為 的代換實(shí)例。2.2一階邏輯公式及解釋( )(

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

35、的代換實(shí)例都是一階邏 輯的等值式模式第二組第二組 一階邏輯中特殊的等值式 , , ,( )( ),( ,)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 量詞轄域收縮與擴(kuò)張等值式(2)( )( ) ( )( ) ( )( ) ( )( )x A xBxA xBx A xBxA xBx A xBxA xBx BA xBxA x 2.3一階邏輯等值式與置換規(guī)則

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.量詞分配蘊(yùn)涵式（ ） （ ）（ ）（ ）（ ） （ ）（ ）（ ）D=N，F(xiàn)(x)：x是奇數(shù) G(x)：x是偶數(shù)2.3一階邏輯等值式與置換規(guī)則( )( ),( )( )AABBAAABAB 置換規(guī)則 設(shè)是含公式 的公式，是用 取代 (中的所有的 之后的公式。若則。AAAA換名規(guī)則 設(shè)A為一公式，將 中某量詞轄域中某約束變項(xiàng)的所有出現(xiàn)及相應(yīng)的指導(dǎo)變?cè)?，改成該量詞轄域中未曾出現(xiàn)過(guò)的某個(gè)體變項(xiàng)

37、的符號(hào)，公式中其余部分不變，設(shè)所得公式為,則2.3一階邏輯等值式與置換規(guī)則AAAAA代替規(guī)則 設(shè) 為一公式，將 中某自由出現(xiàn)的個(gè)體變項(xiàng)的所有出現(xiàn)用A中未曾出現(xiàn)過(guò)的某個(gè)體變項(xiàng)的符號(hào)代替，公式中其余部分不變，設(shè)所得公式為,則( , )( , ) ( ,)( , )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一階邏輯等值式與置換規(guī)則2.4一階邏輯前束范式為了方便使用謂詞公式進(jìn)行定理證明和

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

39、自由變?cè)c約束變?cè)姆?hào)也不相同；、利用量詞轄域的擴(kuò)張和收縮律，將所有量詞以在公式中出現(xiàn)的順序移到公式的最前面，擴(kuò)大量詞的轄域至整個(gè)公式。2.4一階邏輯前束范式( )( )( , )( , )( , )( )( , , )xF xxG xxF x yyG x yxF x yyG yxH x y z 例：2.4一階邏輯前束范式2.5一階邏輯的推理理論1212,BBkkA AAAAA從,推出結(jié)論 的推理形式在一階邏輯中，稱(chēng)永真的蘊(yùn)涵式為推理定律。若一個(gè)推理的形式結(jié)構(gòu)正是某條推理定律，則該推理顯然是正確的。第一組第一組 命題邏輯推理定律的代換實(shí)例第二組第二組 由基本等值式生成的推理定律第三組第三組

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

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

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

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

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

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

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

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

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

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

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

51、集，記作與稱(chēng)為，的所有元素組成的集合和，由和設(shè)有集合定義.iiiiAA與分別記為，算推廣到任意多個(gè)集合將集合的交運(yùn)算和并運(yùn)| . . 3BxAxxBABAABBABA且的相對(duì)補(bǔ)集，記作對(duì)稱(chēng)為，的一切元素組成的集合但不屬于，由屬于、設(shè)有集合定義3.2 集合的運(yùn)算|.BxxBxExxBEBBBEB且的絕對(duì)補(bǔ)集，記作的相對(duì)補(bǔ)集，稱(chēng)為對(duì)全集)()( )()( | .BA . 4BABAABBAAxBxBxAxxBABAABBABA且，或且的對(duì)稱(chēng)差，記作與的集合，稱(chēng)為元素組成的但不屬于，或?qū)儆诘粚儆冢蓪儆?、設(shè)有集合定義CABACABACBACBCBA)( ,),(,63851321求，、，、，：例定

52、義5.設(shè)A 為集合， A 的元素的元素構(gòu)成的集合稱(chēng)為A的廣義并，記作A 。3.2 集合的運(yùn)算A x|z (zA xz)若A A1,A2,，An，則A A1A2 An 定義6.設(shè)A 為非空集合， A 的所有元素的公共元素構(gòu)成的集合稱(chēng)為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集合運(yùn)算的優(yōu)先級(jí)：高級(jí)：廣義并、廣義交、絕對(duì)補(bǔ)、求冪集；同級(jí)按從右向左的順 序進(jìn)行低級(jí)：并、交、相對(duì)補(bǔ)和對(duì)稱(chēng)差；同級(jí)按從左向右的順序進(jìn)行3.2 集合的運(yùn)算3.2 集合的運(yùn)算 文氏圖可以用來(lái)描述集合間的關(guān)系及其運(yùn)算.在文

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

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

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

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

57、，即笛卡兒積不滿(mǎn)足交換律性質(zhì)4.1 有序?qū)εc笛卡兒積定義3.設(shè)集合A，B，以A的元素作為第一元素，B的元算作為第二元素的有序?qū)?gòu)成的集合稱(chēng)為A與B的笛卡兒積，記作AB，符號(hào)化為AB =|xAyB性質(zhì)1. A=， A=例4:設(shè)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或或除非，即笛卡兒積不滿(mǎn)足結(jié)合律性質(zhì)4.1

58、有序?qū)εc笛卡兒積則為任意集合設(shè)滿(mǎn)足分配律笛卡兒積對(duì)并、交運(yùn)算性質(zhì),. 4CBA).()()();()()()()()();()()(ACABACBCABACBAACABACBCABACBA4.1 有序?qū)εc笛卡兒積)()()(:CABACBA證明)()(,)()()()(,CABAyxCAyxBAyxCyAxByAxCyByAxCByAxCBAyx4.1 有序?qū)εc笛卡兒積性質(zhì)5.若AC BD，則A B CD。4.1 有序?qū)εc笛卡兒積其逆命題不成立。A=B=，成立；A ，B ，成立；A= 且 B ，不成立； A 且B= ，不成立。DBCADbCaDCbaBbAaBAba,:證明DCBADCbaDB

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

60、AAAAA次冪集的稱(chēng)為時(shí)，當(dāng)，nAAAAAAAAnnn212121|21niAaaaaAAAAinn，4.2 二元關(guān)系定義1.若一個(gè)集合滿(mǎn)足以下條件之一：（1）集合非空，且它的元素都是有序?qū)Γ?）集合是空集則稱(chēng)該集合為一個(gè)二元關(guān)系。一、關(guān)系的定義.,.,bRaRbaRbaaRbRbaRbaBAR記作沒(méi)有關(guān)系與則稱(chēng)若記作有關(guān)系與則稱(chēng)若設(shè).,2121的一個(gè)二元關(guān)系到的任意一個(gè)子集稱(chēng)特別地AAAA 2121RAARAA上的關(guān)系，即到是設(shè).,:,8 , 6 , 4 , 2,5 , 3 , 1:1baRbaRBABA當(dāng)且僅當(dāng)?shù)亩P(guān)系到定義設(shè)例8 , 5,6 , 5,8 , 3,6 , 3,4 , 3,