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

1、會(huì)計(jì)學(xué)1離散數(shù)學(xué)考前復(fù)習(xí)離散數(shù)學(xué)考前復(fù)習(xí)(fx)第一頁(yè)，共292頁(yè)。第1頁(yè)/共292頁(yè)第二頁(yè)，共292頁(yè)。第一部分(b fen) 數(shù)理邏輯數(shù)理邏輯(shl-lu j)是用數(shù)學(xué)方法研究推理中前提和結(jié)論之間的形式關(guān)系的學(xué)科。推理是由一個(gè)或幾個(gè)判斷(pndun)推出一個(gè)新判斷(pndun)的思維形式。數(shù)學(xué)方法是指建立一套表意符號(hào)體系，對(duì)具體事物進(jìn)行抽象的形式研究的方法。第2頁(yè)/共292頁(yè)第三頁(yè)，共292頁(yè)。第3頁(yè)/共292頁(yè)第四頁(yè)，共292頁(yè)。第4頁(yè)/共292頁(yè)第五頁(yè)，共292頁(yè)。1. 命題(mng t)：能判斷真假的陳述句。包含(bohn)兩層意思：（1）必須(bx)是陳述句。 （2）能夠確定（分

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

3、：真用T或1表示(biosh)，假用F或0表示(biosh)。3.命題和真值的符號(hào)化1.1 命題和命題聯(lián)結(jié)詞第7頁(yè)/共292頁(yè)第八頁(yè)，共292頁(yè)?；鹦巧嫌猩７e大。海洋的面積比陸地的面例：:962:rqp）我正在說(shuō)謊。）啊，我的天哪?。┪覀円W(xué)習(xí)。）你喜歡數(shù)學(xué)嗎？。三角形的內(nèi)角和等于8765801:s）火星上有生命。）面積大。）海洋的面積比陸地的例：396221）我正在說(shuō)謊。）啊，我的天哪?。┪覀円W(xué)習(xí)。）你喜歡數(shù)學(xué)嗎？。）三角形的內(nèi)角和等于87658014第8頁(yè)/共292頁(yè)第九頁(yè)，共292頁(yè)。例：2是有理數(shù)是不對(duì)的；2是偶素?cái)?shù)(s sh)；2或4是素?cái)?shù)(s sh)；如果2是素?cái)?shù)(s

4、 sh)，則3也是素?cái)?shù)(s sh)；2是素?cái)?shù)(s sh)當(dāng)且僅當(dāng)3也是素?cái)?shù)(s sh)。p：2是有理數(shù)，q：2是偶數(shù)(u sh)，r：2是素?cái)?shù)，s：3是素?cái)?shù)，t：4是素?cái)?shù)。第9頁(yè)/共292頁(yè)第十頁(yè)，共292頁(yè)。4、命題(mng t)聯(lián)結(jié)詞”。讀作“非的否命題，記作稱作復(fù)合命題，沒(méi)有”等否定詞組成的和“非”、“不”、“用命題否定詞pppp,).1不是質(zhì)數(shù)。：是質(zhì)數(shù)。如：的邏輯抽象。、“不”和“沒(méi)有”等是自然語(yǔ)言中的“非”44:ppp pTFFT1.1 命題(mng t)和命題(mng t)聯(lián)結(jié)詞第10頁(yè)/共292頁(yè)第十一頁(yè)，共292頁(yè)。”。合取”或“與讀作“組成的復(fù)合命題，記作和、是命題，由、合

5、取詞qpqpqpqpqp,).2一面”等的邏輯抽象。、“一面但是”而且”、“雖然”、“不但又“既”、是自然語(yǔ)言中的“并且pqp qFFFFTFTFFTTT：王化的品德很好。：王化的成績(jī)很好。qp王化不但成績(jī)(chngj)好而且品德好。pq：1.1 命題(mng t)和命題(mng t)聯(lián)結(jié)詞第11頁(yè)/共292頁(yè)第十二頁(yè)，共292頁(yè)。”。或讀作“組成的復(fù)合命題記作和、命題析取詞qpqpqp,).3的邏輯抽象。、“或者”中的可兼或是自然語(yǔ)言中的“或”pqp qFFFFTTTFTTTT：燈泡壞了。：開關(guān)壞了。qp1.1 命題(mng t)和命題(mng t)聯(lián)結(jié)詞開關(guān)(kigun)壞了或燈泡壞了。p

6、q：第12頁(yè)/共292頁(yè)第十三頁(yè)，共292頁(yè)。注意：當(dāng)排斥或兩邊的情況(qngkung)實(shí)際根本不可能同時(shí)發(fā)生的時(shí)候，排斥或也可抽象為。但為了方便起見(jiàn)一般不這樣抽象。第13頁(yè)/共292頁(yè)第十四頁(yè)，共292頁(yè)。稱作后件（結(jié)論）。，”。稱為前件（前提）條件或“”則讀作“如果組成的復(fù)合命題記作和、由命題蘊(yùn)涵詞qqpqppqp,q).4的邏輯抽象?！?，則”，“若，則是自然語(yǔ)言中的“如果pqp qFFTFTTTFFTTT有位父親(f qn)對(duì)兒子說(shuō)：“如果我去書店，就一定給你買電腦報(bào)“。問(wèn)：在什么情況下，父親(f qn)算失信呢？1.1 命題(mng t)和命題(mng t)聯(lián)結(jié)詞第14頁(yè)/共292頁(yè)第

7、十五頁(yè)，共292頁(yè)。注意：“只要p，就q，因?yàn)閜，所以q”，“p僅當(dāng)q”，只有q，才p“，”除非q才p“，”除非q，否則非p“都可抽象為pq。p，q可以(ky)沒(méi)有任何內(nèi)在聯(lián)系。例：1.如果336，那么雪是白的。2.除非(chfi)我能工作完成了，我才去看電影。3.只要天下雨，我就回家。4.我回家僅當(dāng)天下雨。pq的邏輯關(guān)系為q是p的必要條件(b yo tio jin)或p是q的充分條件。第15頁(yè)/共292頁(yè)第十六頁(yè)，共292頁(yè)。的邏輯抽象。條件”，“當(dāng)且僅當(dāng)”是自然語(yǔ)言中的“充要”。當(dāng)且僅當(dāng)讀作“組成的復(fù)合命題記作和、由命題等價(jià)詞qp,).5qpqppqp qFFTFTFTFFTTT1.1 命

8、題(mng t)和命題(mng t)聯(lián)結(jié)詞p q的邏輯關(guān)系為p與q互為充要條件例：1.3是有理數(shù)當(dāng)且僅當(dāng)加拿大位于亞洲。2.兩圓的面積相等(xingdng)，則他們的半徑相等(xingdng)，反之亦然。第16頁(yè)/共292頁(yè)第十七頁(yè)，共292頁(yè)。6.q異或聯(lián)結(jié)詞指的是排斥或，當(dāng)且僅當(dāng)p、q的真值相異時(shí)，p為真。pqp qFFFFTTTFTTTF)()()2(qp1qpqpqppq等價(jià)于等價(jià)于）（有如下性質(zhì)：由定義知1.1 命題(mng t)和命題(mng t)聯(lián)結(jié)詞例：今天(jntin)第一節(jié)課上離散數(shù)學(xué)或數(shù)據(jù)結(jié)構(gòu)。第17頁(yè)/共292頁(yè)第十八頁(yè)，共292頁(yè)。左往右的次序運(yùn)算。）同級(jí)的聯(lián)結(jié)詞，按

9、從（省略不必要的括號(hào)。）按優(yōu)先級(jí)書寫，可以（。，）由強(qiáng)到弱依次是：（聯(lián)結(jié)詞的優(yōu)先次序：32,1例：p：北京(bi jn)比天津人口多 q：224 r：烏鴉是黑色的pqpqrrqqp)2(1 ）（求以下命題的真值第18頁(yè)/共292頁(yè)第十九頁(yè)，共292頁(yè)。5、語(yǔ)句(yj)形式化）選擇命題聯(lián)結(jié)詞。（命題）；）確定原子命題（簡(jiǎn)單（形式化的步驟：211.1 命題(mng t)和命題(mng t)聯(lián)結(jié)詞例：2是有理數(shù)是不對(duì)的；2是偶素?cái)?shù)(s sh)；2或4是素?cái)?shù)(s sh)；如果2是素?cái)?shù)(s sh)，則3也是素?cái)?shù)(s sh)；2是素?cái)?shù)(s sh)當(dāng)且僅當(dāng)3也是素?cái)?shù)(s sh)。p：2是有理數(shù)，q：2是偶數(shù)

10、，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。第19頁(yè)/共292頁(yè)第二十頁(yè)，共292頁(yè)。跳墻。中的聯(lián)結(jié)詞，如：狗急）要善于識(shí)別自然語(yǔ)言（，如：我和他是同學(xué)。）給定句子是否是命題（注意：21去郊游，否則就不去。如果明天天氣好，我們表。選小陳或小周一人為代踐經(jīng)驗(yàn)。他雖有理論知識(shí)但無(wú)實(shí)。么你一定會(huì)成為近視眼如果你走路時(shí)看書，那自討沒(méi)趣。，那么你們倆都不會(huì)去如果你和他不都是傻子例. 5. 4. 3. 2. 11.1 命題(mng t)和命題(mng t)聯(lián)結(jié)詞第20頁(yè)/共292頁(yè)第二十一頁(yè)，共292頁(yè)。命題(mng t)常元：表示具體確定內(nèi)容的命題(m

11、ng t)。命題(mng t)變?cè)罕硎静淮_定具體內(nèi)容的命題(mng t)。題公式。）得到的符號(hào)串都是命）、（）有限次的使用（也是命題公式；是命題公式，則、）若（公式；公式，稱其為原子命題）單個(gè)命題變?cè)敲}（命題公式的遞歸定義：定義213,qp,q21.1qpqpqpqppp1.2 命題(mng t)公式及其賦值第21頁(yè)/共292頁(yè)第二十二頁(yè)，共292頁(yè)。rpprqppqpqrrqqp)5()4()3()2(1 ）例（同時(shí)(tngsh)約定：（1）最外層的括號(hào)可以省去。 （2）不影響運(yùn)算次序的括號(hào)也可以省去。第22頁(yè)/共292頁(yè)第二十三頁(yè)，共292頁(yè)。層公式，是，則公式或或或或?qū)庸剑?，?/p>

12、別是，）若公式（層公式；是，則層公式且是）若公式（層公式；其為為單個(gè)命題變?cè)?，則稱）公式（命題公式的層次：定義),max(1nACBACBACBACBACBAjiCB31nABAnB20A1. 2jin pqpqrrqp)2(1 ）例（第23頁(yè)/共292頁(yè)第二十四頁(yè)，共292頁(yè)。rqp )(是有理數(shù)：是偶數(shù)，：是素?cái)?shù)，：232rqp是無(wú)理數(shù)：是偶數(shù)，：是素?cái)?shù)，：232rqp稱為成假賦值。的成真賦值，否則，則稱其為的真值為若指定的一組值使的一組賦值或解釋。對(duì)一組確定的取值，稱為給的命題公式，為含有命題變?cè)O(shè)定義A1Ap,p,.32121AppppAnn第24頁(yè)/共292頁(yè)第二十五頁(yè)，共292頁(yè)。

13、的真值表。稱為情況列成表，在其全部賦值下的真值將公式定義AA. 41n1)1223FnFnnnn真值表的構(gòu)造步驟：（ ）若公式 共有（個(gè)變?cè)?，則真值表第一行寫出個(gè)變?cè)紽寫在第列。（ ）寫出 個(gè)變?cè)乃锌赡苋≈担ǚN）,按從低到高的順序?qū)懗龉降母鲗哟?。?）在不同賦值下求出各層次的真值及 的真值。第25頁(yè)/共292頁(yè)第二十六頁(yè)，共292頁(yè)。為可滿足式。的值為真，則稱）若至少有一組賦值使為永假式；為假，則稱在所有賦值下的取值均）若為永真式；為真，則稱在所有賦值下的取值均若，公式定義AA3AA2AA) 1. 5A1.2 命題(mng t)公式及其賦值pqpqrrqp)2(1 ）例（第26頁(yè)/

14、共292頁(yè)第二十七頁(yè)，共292頁(yè)。也是重言式。為重言式，則和若定理BABABA,. 11.2 命題(mng t)公式及其賦值第27頁(yè)/共292頁(yè)第二十八頁(yè)，共292頁(yè)。1.,ABABA BAB定義 設(shè) 和 是兩個(gè)命題公式，若為重言式，則稱公式是等值的公式，記作。1.p)();.qqpppp 例 證明（.qpq注意：和的區(qū)別是公式間的關(guān)系符號(hào)，如：p是命題聯(lián)結(jié)詞1.3 命題(mng t)公式的等值式第28頁(yè)/共292頁(yè)第二十九頁(yè)，共292頁(yè)。 , ABAB ABBAABCABC ABCABCABCABACABCABAC交換律：結(jié)合律：分配律：)(),(),()pqpqpqrpqrpqr 例： （

15、與基本等值式（基本等值式（A，B，C為任意為任意(rny)命題公式）命題公式）1.3 命題(mng t)公式的等值式第29頁(yè)/共292頁(yè)第三十頁(yè)，共292頁(yè)。0,110A,1, ,1.11,00(),AA AAAAAAAAAA AAA AAAAAAAA AAAAABA AABAABABABAB 同一律：互補(bǔ)律：，重補(bǔ)律：等冪律：零一律：A吸收律：德摩根律：1.3 命題(mng t)公式的等值式第30頁(yè)/共292頁(yè)第三十一頁(yè)，共292頁(yè)。, BABABBABABBAABABBAABABABABAB 蘊(yùn)含等值式：A假言易位：等價(jià)等值式：A等價(jià)否定等值式：歸謬論：(AB) (AB)A因A，B，C可以

16、代入任意(rny)的命題公式，故以上等值式稱為等值式模式。由已知的等值式推演出另外一些等值式的過(guò)程(guchng)為等值演算。1.3 命題(mng t)公式的等值式第31頁(yè)/共292頁(yè)第三十二頁(yè)，共292頁(yè)。( )( )( ) ABA(B)(A)AABBA 置換規(guī)則：設(shè)是含公式 的命題公式，是用公式 置換了中所有的 后得到的命題公式。若，則等值演算的應(yīng)用： 1.驗(yàn)證等值式 2.判定公式(gngsh)的類型 3.解決工作生活中的判斷問(wèn)題 2.qpqqp 例 等值等價(jià)式p1.3 命題(mng t)公式的等值式()()()pqprpqr(),(),()pqpqppqr ppqpq甲、已、丙3人根據(jù)口

17、音對(duì)王教授是哪人進(jìn)行了判斷： 甲說(shuō)：王教授不是(b shi)蘇州人，是上海人 已說(shuō)：王教授不是(b shi)上海人，是蘇州人 丙說(shuō)：王教授既不是(b shi)上海人，也不是(b shi)杭州人結(jié)果3人中有一人全對(duì)，一人對(duì)一半，一人全錯(cuò)。問(wèn)王教授是哪人？第32頁(yè)/共292頁(yè)第三十三頁(yè)，共292頁(yè)。聯(lián)結(jié)詞的完備(wnbi)集.0,10,1n.nF定義稱 ：為 元真值函數(shù)0,10 1nn中的元素為由 ， 組成的長(zhǎng)為 的符號(hào)串n個(gè)命題變?cè)梢孕纬?2n個(gè)不同(b tn)的真值函數(shù)對(duì)于每個(gè)真值函數(shù)，都可以找到許多與之等值的命題公式，而每個(gè)命題公式對(duì)應(yīng)(duyng)唯一的與之等值的真值函數(shù)。定義.設(shè)S是一

18、個(gè)聯(lián)結(jié)詞集合，如果任何n（n1）元真值 函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示，則 稱S是聯(lián)結(jié)詞完備集。第33頁(yè)/共292頁(yè)第三十四頁(yè)，共292頁(yè)。. , , Th S 是聯(lián)結(jié)詞完備集.345S , , , , , ,SSS 12推論：以下聯(lián)結(jié)詞集都是完備集 , , ,S.,p qpq定義 設(shè)為兩個(gè)命題，復(fù)合命題“ 與（或） 的否定式”稱作p,q的與（或）非式，記作pq(pq). , Th 也是聯(lián)結(jié)詞完備集.聯(lián)結(jié)詞的完備(wnbi)集第34頁(yè)/共292頁(yè)第三十五頁(yè)，共292頁(yè)。1.4 析取范式與合取范式定義：命題變?cè)捌浞穸ńy(tǒng)稱為(chn wi)文字。 僅由有限個(gè)文字構(gòu)成的析取式稱為(ch

19、n wi)簡(jiǎn)單（質(zhì)）析取式。 僅由有限個(gè)文字構(gòu)成的合取式稱為(chn wi)簡(jiǎn)單（質(zhì)）合取式。,pp pq pq例：注意(zh y)：?jiǎn)蝹€(gè)文字既是簡(jiǎn)單析取式又是簡(jiǎn)單合取式。討論：設(shè)A為含n個(gè)文字(wnz)的簡(jiǎn)單析取式 若A中同時(shí)含pi和pi，則？若A為永真式，則？第35頁(yè)/共292頁(yè)第三十六頁(yè)，共292頁(yè)。若A為永真式，則A中必同時(shí)(tngsh)含有pi和pi，反之亦然。同理有，若A為簡(jiǎn)單合取式，A為永假式的充要條件是A中同時(shí)(tngsh)含有pi和pi。定理1. 一個(gè)簡(jiǎn)單析取式是重言式當(dāng)且僅當(dāng)它同時(shí)含有(hn yu)某 個(gè)命題變?cè)捌渌姆穸ā?一個(gè)簡(jiǎn)單合取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)含有(hn

20、 yu)某 個(gè)命題變?cè)捌渌姆穸ā?.4 析取范式與合取范式第36頁(yè)/共292頁(yè)第三十七頁(yè)，共292頁(yè)。定義：由有限(yuxin)個(gè)簡(jiǎn)單合取式構(gòu)成的析取式稱為析取范式。 由有限(yuxin)個(gè)簡(jiǎn)單析取式構(gòu)成的合取式稱為合取范式。 析取范式與合取范式稱為范式。,()()pp pq pqpqpq 例：注意(zh y)：?jiǎn)蝹€(gè)文字、簡(jiǎn)單析取式、簡(jiǎn)單合取式都既是析取范 式又是合取范式。1.4 析取范式與合取范式定理(dngl)2. 一個(gè)析取范式是矛盾式當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單合 取式為矛盾式。 一個(gè)合取范式是重言式當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單析 取式為重言式。第37頁(yè)/共292頁(yè)第三十八頁(yè)，共292頁(yè)。定理(dn

21、gl)3.任一命題公式都存在與之等值的析取范式和合取范式。范式的求法：消去公式中的蘊(yùn)涵、等價(jià)和異或聯(lián)結(jié)詞 使用雙重否定(fudng)律和德摩根律，將公式中出現(xiàn) 的否定(fudng) 詞移到命題變?cè)啊?利用分配律、結(jié)合律將公式化為合（析）取 范式。,()rpqrp例：(pq)范式(fn sh)形式不唯一。1.4 析取范式與合取范式第38頁(yè)/共292頁(yè)第三十九頁(yè)，共292頁(yè)。定義：在含有(hn yu)n個(gè)命題變?cè)暮?jiǎn)單合（析）取式中，若每個(gè) 命題變?cè)?它的否定式不同時(shí)出現(xiàn)，而二者之一必 出現(xiàn)且僅出現(xiàn)一次，且第 i個(gè)命題變?cè)蛩姆穸ㄊ?出現(xiàn)在從左算起的第i位上（字典序），稱這樣的簡(jiǎn) 單合（析

22、）取式為極?。ù螅╉?xiàng)。,()pqpq pq pqpq 例：性質(zhì)(xngzh)：n個(gè)變?cè)梢孕纬?n個(gè)極?。ù螅╉?xiàng)； 每個(gè)極?。ù螅╉?xiàng)有且僅有一個(gè)成真（假）賦值； 每組賦值下僅有一個(gè)極?。ù螅╉?xiàng)為真（假）； 所有極?。ù螅╉?xiàng)的析（合）取為真（假）；1.4 析取范式與合取范式第39頁(yè)/共292頁(yè)第四十頁(yè)，共292頁(yè)。將極小(j xio)項(xiàng)的成真賦值對(duì)應(yīng)的二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)為i，將對(duì)應(yīng)的極小(j xio)項(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è)命題(mng t)變?cè)獦?gòu)成的析（合）取范式中所有的簡(jiǎn) 單合（析）取式都是極?。ù螅╉?xiàng)，則稱該

23、析取范 式為主析（合）取范式。1.4 析取范式與合取范式定理.任何命題公式(gngsh)都存在與之等值的主析取范式和主合取范 式，并且是唯一的。第40頁(yè)/共292頁(yè)第四十一頁(yè)，共292頁(yè)。1.4 析取范式與合取范式公式法：求析取范式 用同一律補(bǔ)進(jìn)未出現(xiàn)(chxin)的命題變?cè)?消去永假或重復(fù)出現(xiàn)(chxin)的變?cè)蜆O小項(xiàng) 將極小項(xiàng)按下標(biāo)從小到大排列真值表法：列出公式(gngsh)及各極小項(xiàng)的真值表，將每組賦值下 公式(gngsh)及極小項(xiàng)真值都為真的極小項(xiàng)進(jìn)行析取。主析取范式的求法：1.公式(gngsh)法2.真值表法第41頁(yè)/共292頁(yè)第四十二頁(yè)，共292頁(yè)。1.4 析取范式與合取范式應(yīng)用

24、：1.求公式的成真、成假賦值 成真賦值為析取范式中所含極小(j xio)項(xiàng)的編碼的二進(jìn)制數(shù) 成假賦值為合取范式中所含極大項(xiàng)的編碼的二進(jìn)制數(shù)12i, m;iiiiMp pMMmin定理.設(shè)m 與是,p 形成的極小項(xiàng)、極大項(xiàng)，則，由主析取范式可以直接求主合取范式： 1求出主析取范式中未包含的極小(j xio)項(xiàng) 2求出與1中求出的極小(j xio)項(xiàng)下標(biāo)相同的極大項(xiàng) 3做2中極大項(xiàng)之合取第42頁(yè)/共292頁(yè)第四十三頁(yè)，共292頁(yè)。1.4 析取范式與合取范式3.判斷兩公式(gngsh)是否等值 若A，B共含有n個(gè)命題變?cè)?，按n個(gè)命題變?cè)蟪鯝與B的主析取范式A、B，若AB，則AB.2.判斷(pndu

25、n)公式的類型 設(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為可滿足式當(dāng)且僅當(dāng)A的主析取范式中至少含一個(gè)極小項(xiàng)。第43頁(yè)/共292頁(yè)第四十四頁(yè)，共292頁(yè)。例：要在A，B，C中挑選2名出國(guó)進(jìn)修，選派時(shí)滿足下列條件： 若A去，則C同去 若B去，則C不能去 若C不去，則A或B可以去問(wèn)有幾種(j zhn)選派方案，分別是什么？4.解決實(shí)際(shj)問(wèn)題1.4 析取范式與合取范式第44頁(yè)/共292頁(yè)第四十五頁(yè)，共292頁(yè)。222222, ,A AA BA AA BAAAAAABA AABA AAB1k1k1k

26、1k1k1k定義.設(shè),都是公式，若，的任意 一組賦值，或者為假，或者和 同為真，則稱由前提，推出 的推理 是有效的或正確的，稱，為前提集合為 有效結(jié)論.1.5推理(tul)的形式結(jié)構(gòu)注意：推理正確實(shí)際是排除(pich)前提真結(jié)論假的情況推理是否正確與前提的排列順序無(wú)關(guān)推理正確并不能保證B一定為真第45頁(yè)/共292頁(yè)第四十六頁(yè)，共292頁(yè)。12)kAAAB若推理正確，則記作(1212.,BBkkAAAAAA定 理 公 式推的 推 理 正 確 當(dāng) 且 僅 當(dāng) （）為 永 真 式 。1.5推理(tul)的形式結(jié)構(gòu)212,B kA AABAAA1k由，推 ，記作（）推理的形式(xngsh)結(jié)構(gòu)第46頁(yè)

27、/共292頁(yè)第四十七頁(yè)，共292頁(yè)。1212,kkAAABAAAB用（）作為推理的形式結(jié)構(gòu)，證明時(shí)要先寫成前提：,結(jié)論：12)kAAAB論證推理是否正確，就是判斷(是否為永真式真值表法方法有等值演算法主范式法1.5推理(tul)的形式結(jié)構(gòu)第47頁(yè)/共292頁(yè)第四十八頁(yè)，共292頁(yè)。例：若下午(xiw)溫度超過(guò)30度，則王曉燕必去游泳。若她去游 泳，她就不會(huì)去看電影。所以若王曉燕沒(méi)去看電影， 下午(xiw)溫度必超過(guò)了30度。p：溫度(wnd)超過(guò)30度q：王曉燕去游泳r：王曉燕去看電影,pq qrrp 前提：結(jié)論：1.5推理的形式(xngsh)結(jié)構(gòu)第48頁(yè)/共292頁(yè)第四十九頁(yè)，共292頁(yè)。,

28、()() AABABAABABABBAABBAABBCACABBCACABCDACBDABABAABABCDBDAC 附加律：化簡(jiǎn)律：假言推理：拒取式：析取三段論：假言三段論：等價(jià)三段論：構(gòu)造性二難：破壞性二難：1.5推理(tul)的形式結(jié)構(gòu)第49頁(yè)/共292頁(yè)第五十頁(yè)，共292頁(yè)。注意：以上都是蘊(yùn)含式模式若某推理的形式結(jié)構(gòu)與某定律一致，則推理正確(zhngqu)成立的等值式可產(chǎn)生兩條定律推理定律可產(chǎn)生相應(yīng)的推理規(guī)則1.5推理的形式(xngsh)結(jié)構(gòu)第50頁(yè)/共292頁(yè)第五十一頁(yè)，共292頁(yè)。1.6自然推理(tul)系統(tǒng)P定義.一個(gè)(y )形式系統(tǒng)I由以下4部分組成： 非空的字母表，記作A(I

29、) A(I)中符號(hào)構(gòu)成的合式公式集，記作E(I) E(I)中特殊的公式組成的公理集，記作Ax(I) 推理規(guī)則集，記作R(I)自 然 推 理 系 統(tǒng)形 式 系 統(tǒng)公 理 推 理 系 統(tǒng)任給的前提，應(yīng)用規(guī)則得到結(jié)論(jiln)（可能真）任給的公理，應(yīng)用規(guī)則得到結(jié)論（永真）第51頁(yè)/共292頁(yè)第五十二頁(yè)，共292頁(yè)。P, , , ,2.1.63.1(P)iiip q rp q r 定義.自然推理系統(tǒng)或1.字母表， ， ，（）和，合式公式定義中所定義的所有命題公式推理規(guī)則（）前提引入規(guī)則：證明的任何步驟上都可以引入前提1.6自然推理(tul)系統(tǒng)P第52頁(yè)/共292頁(yè)第五十三頁(yè)，共292頁(yè)。(2)結(jié)論

30、引入(T)規(guī)則：證明的任何步驟上所得的結(jié)論都可作為 后繼證明的前提（3）置換規(guī)則：在證明的任何步驟上，命題公式中的子公式都 可以用與之等值的公式置換ABABABAB(4)假言推理規(guī)則：若序列中已出現(xiàn)和 ，則可將 引入序列中(5)附加規(guī)則;（6）化簡(jiǎn)規(guī)則;（7）拒取式（8）假言三段論規(guī)則;（9）析取三段論規(guī)則（10)構(gòu)造性二難規(guī)則;（11）破壞性二難規(guī)則（12）合取引入規(guī)則：若序列中出現(xiàn)了和 ，則可將引入序列中1.6自然(zrn)推理系統(tǒng)P第53頁(yè)/共292頁(yè)第五十四頁(yè)，共292頁(yè)。,()pq qr pssrpq例：前提： 結(jié)論：例：若小王是理科生，則他的數(shù)學(xué)成績(jī)一定很好。如果(rgu) 小王不

31、是理科生，他一定是文科生。小王的數(shù)學(xué)成績(jī) 不好。所以小王是文科生。p：小王(xio wn)是理科生q：小王(xio wn)是文科生r：小王(xio wn)的數(shù)學(xué)成績(jī)很好,prpqrq前提：結(jié)論：1.6自然推理(tul)系統(tǒng)P第54頁(yè)/共292頁(yè)第五十五頁(yè)，共292頁(yè)。12121.()()()kkAAAABAAAAB附加前提證明法若推理形式為，則可轉(zhuǎn)換為例：如果小張和小王(xio wn)去看電影，則小李也去看電影。小趙 不去看電影或小張去看電影。小王(xio wn)去看電影。所以， 當(dāng)小趙去看電影時(shí)，小李也去。p：小張去看電影(dinyng)q：小王去看電影(dinyng)r：小李去看電影(di

32、nyng)s：小趙去看電影(dinyng)(),pqrsp qsr 前提：結(jié)論：1.6自然推理(tul)系統(tǒng)P第55頁(yè)/共292頁(yè)第五十六頁(yè)，共292頁(yè)。1212()()()kkAAABAAAB 2.歸謬法將結(jié)論的否定(fudng)作為前提引入，能推出矛盾來(lái)，則推理正確例：如果馬會(huì)飛或羊不吃草，則母雞就會(huì)是飛鳥(fi nio)。如果母 雞是飛鳥(fi nio)，那么烤熟的鴨子還會(huì)跑?？臼斓镍喿硬粫?huì) 跑。所以羊吃草。p：馬會(huì)飛q：羊吃草r：母雞是飛鳥(fi nio)s：烤熟的鴨子會(huì)跑(),pqr rssq 前提：結(jié)論：1.6自然推理系統(tǒng)P第56頁(yè)/共292頁(yè)第五十七頁(yè)，共292頁(yè)。所有(suyu

33、)的人總是要死的。蘇格拉底是人。所以蘇格拉底是要死的。p:q:r:, p qr前提：結(jié)論：()pqr推理形式：第57頁(yè)/共292頁(yè)第五十八頁(yè)，共292頁(yè)。第58頁(yè)/共292頁(yè)第五十九頁(yè)，共292頁(yè)。個(gè)體常項(xiàng)個(gè)體變項(xiàng), , ,iiia b ca b c用表示, ,iiix y zxyz用表示1.個(gè)體(gt)詞所研究對(duì)象中可以獨(dú)立(dl)存在的具體的或抽象的客體（事物）表示具體的或特定的客體表示抽象或泛指的客體個(gè)體變項(xiàng)的取值范圍稱為個(gè)體域，用D表示宇宙間一切事物組成的稱為全總個(gè)體域1,2,3,N R有窮，無(wú)窮，第59頁(yè)/共292頁(yè)第六十頁(yè)，共292頁(yè)。謂詞常項(xiàng)：具體性質(zhì)或關(guān)系的詞謂詞變項(xiàng)：抽象或泛

34、指的性質(zhì)或關(guān)系的詞2.謂詞(wi c)用來(lái)刻劃個(gè)體詞性質(zhì)(xngzh)及個(gè)體詞之間相互關(guān)系的詞,iiiF G HF GH用,表示2是有理數(shù)x是無(wú)理數(shù)小王與小李同歲(tn su)x與y具有關(guān)系L是有理數(shù)是無(wú)理數(shù)與同歲與具有關(guān)系LF：G：H：L：第60頁(yè)/共292頁(yè)第六十一頁(yè)，共292頁(yè)。3.量詞：個(gè)體詞之間的數(shù)量(shling)關(guān)系（1）全稱量詞(lingc) “一切的”，“所有的”，“每一個(gè)”，“任意的”，“凡”，“都” 記作(2) 存在量詞 “存在”，“有一個(gè)”，“有的”，“至少有一個(gè)”記作4.符號(hào)化 確定個(gè)體(gt)域確定個(gè)體(gt)詞、量詞和謂詞確定聯(lián)結(jié)詞第61頁(yè)/共292頁(yè)第六十二頁(yè)，

35、共292頁(yè)。例：所有的人都是要死的。 有的人用左手(zushu)寫字。注意：全稱量詞的特性謂詞必須作為蘊(yùn)涵式的前件引入存在(cnzi)量詞的特性謂詞必須作為合取式的合取項(xiàng)引入同一命題，不同的個(gè)體域符號(hào)化的形式可能不同未指明個(gè)體域即為全總個(gè)體域第62頁(yè)/共292頁(yè)第六十三頁(yè)，共292頁(yè)。例：在美國(guó)留學(xué)的學(xué)生未必都是亞洲人。 有的兔子(t zi)比所有的烏龜跑的快。 對(duì)任意的整數(shù)x，都存在整數(shù)y使得xy10。注意：多個(gè)量詞出現(xiàn)時(shí)，順序一般不能隨便換有些(yuxi)命題符號(hào)化形式不唯一第63頁(yè)/共292頁(yè)第六十四頁(yè)，共292頁(yè)。.F(1), , ,(2), , , , ,(7) ( ),iiiiii

36、iiiiiia 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é)詞: , , ,和第64頁(yè)/共292頁(yè)第六十五頁(yè)，共292頁(yè)。121212( ,)n, , ,n( , ,)(3)(1)(2)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定義

37、設(shè)，是一階語(yǔ)言的任意 元謂詞, 是一階語(yǔ)言的任意 個(gè)項(xiàng)，則稱，是 一階語(yǔ)言的原子公式。第65頁(yè)/共292頁(yè)第六十六頁(yè)，共292頁(yè)。.(1)(2)()(3),(4),(5)AAA BAB AB AB ABAxAxA定義一階語(yǔ)言的合式公式的定義原子公式是合式公式；若 是合式公式，則也是合式公式；若是合式公式，則也是合式公式；若 是合式公式，則也是合式公式；只有有限次地應(yīng)用(1)(4)構(gòu)成的符號(hào)串才是合式公式。合式公式也稱謂(chngwi)詞公式，簡(jiǎn)稱公式第66頁(yè)/共292頁(yè)第六十七頁(yè)，共292頁(yè)。.,xAxAxxAxAxA定義在公式中，稱 為指導(dǎo)變?cè)?，A為相應(yīng)量詞的轄域。在的轄域中， 的所有出現(xiàn)稱

38、為約束出現(xiàn)， 中不是約束出現(xiàn)的變?cè)Q為自由出現(xiàn)。( ( , )( , ) ( ( )( )( )( , , )x F x yG x zx F xG yy H xL x y z 例：.AAA定義設(shè) 是任意的公式，若 中不含自由出現(xiàn)的個(gè)體變項(xiàng)，則稱 為封閉的公式，簡(jiǎn)稱閉式。第67頁(yè)/共292頁(yè)第六十八頁(yè)，共292頁(yè)。( ( )( ) ( ( )( )( , )( ( , ), ( , )x F xG xx 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ǔ)言的解釋 由以下部分

39、組成非空個(gè)體域；中一些特殊元素的集合, ；上特定函數(shù)集合；上特定謂詞集合第68頁(yè)/共292頁(yè)第六十九頁(yè)，共292頁(yè)。I(1)(2)(3)(4).IinniinniiDaffFF對(duì) 的說(shuō)明：公式中的個(gè)體變項(xiàng)均取值于；若含個(gè)體變項(xiàng)就解釋為 ；若含函數(shù)就解釋為 ；若含謂詞就解釋為第69頁(yè)/共292頁(yè)第七十頁(yè)，共292頁(yè)。I(1) D=N=0,1,2, (2) 0(3) ( , ), ( , )(4) ( , )af x yxy g x yxyF x yxy例：解釋 ：為(1)( ,),( ,)(2)( , ), )(3)( , ), )( ,)Ff x yg x yxF g x axxF g x a

40、xF x y定理(dngl).閉式在任何解釋下都變成命題。第70頁(yè)/共292頁(yè)第七十一頁(yè)，共292頁(yè)。.AAAAAAA定義設(shè) 為公式 若 在任何解釋下均為真，則稱 為永真式(邏輯有效式). 若 在任何解釋下均為假，則稱 為永假式(矛盾式). 若至少有一個(gè)解釋使 為真，則稱 為可滿足式。0121200., n(1),nniiAp ppA AAAinApAA 定義設(shè)是含命題變項(xiàng)， 的命題公式，是個(gè)謂詞公式，用處處代替 中的所得公式 為 的代換實(shí)例。2.2一階邏輯公式(gngsh)及解釋第71頁(yè)/共292頁(yè)第七十二頁(yè)，共292頁(yè)。( )( ,)( )( )( )( )( )( )( )( )xF x

41、x yG x yxF xxF xyG yyG yx F xG xx F xG x 例：定理.重言式的代換(di hun)實(shí)例都是永真式，矛盾式的代換(di hun) 實(shí)例都是矛盾式。( )( )( )( )( )xF xxF xx F xG xyG y 第72頁(yè)/共292頁(yè)第七十三頁(yè)，共292頁(yè)。A BABABAB定義.設(shè) , 是一階邏輯中任意兩個(gè)公式，若是永真式， 則 與 等值，記作1212121.D=,( )()()()( )()()()nnnaaaxA xA aA aA axA xA aA aA a消去量詞等值式 ,第一組第一組 命題邏輯中等值式模式的代換命題邏輯中等值式模式的代換(di

42、 hun)實(shí)例都是一階邏實(shí)例都是一階邏 輯的等值式模式輯的等值式模式第二組第二組 一階邏輯一階邏輯(lu j)中特殊的等值式中特殊的等值式 , , ,( )( ),( ,)Da b cxF xyG yxyF x y 第73頁(yè)/共292頁(yè)第七十四頁(yè)，共292頁(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 x

43、BxA xBx A xBxA xBx A xBxA xBx BA xBxA x 第74頁(yè)/共292頁(yè)第七十五頁(yè)，共292頁(yè)。( ( )( )( )( )( ( )( )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ù)(j sh) G(x)：x是偶數(shù)第75頁(yè)/共292頁(yè)第七十六頁(yè)，共292頁(yè)。( )( ),( )( )AABBAAABAB 置換規(guī)則 設(shè)是含公式 的公式，是用 取代 (中的所

44、有的 之后的公式。若則。AAAA換名規(guī)則 設(shè)A為一公式，將 中某量詞轄域中某約束變項(xiàng)的所有出現(xiàn)及相應(yīng)的指導(dǎo)變?cè)某稍摿吭~轄域中未曾出現(xiàn)過(guò)的某個(gè)體變項(xiàng)的符號(hào)，公式中其余部分不變，設(shè)所得公式為,則第76頁(yè)/共292頁(yè)第七十七頁(yè)，共292頁(yè)。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

45、 xG xx y F xG yL x yx y F xG yL x y 證明：第77頁(yè)/共292頁(yè)第七十八頁(yè)，共292頁(yè)。為了方便使用謂詞公式(gngsh)進(jìn)行定理證明和邏輯推理，需要把謂詞公式(gngsh)變換為便于使用的規(guī)范形式，就是范式。 112233kki112233kk.AAQ x Q x Q xQ x BQBAQ x Q x Q xQ x B定義 設(shè) 為一個(gè)一階邏輯公式，若 具有 形式，其中每個(gè)為量詞 或 ， 為不含量詞的 謂詞公式，則稱 為前束范式，稱為公式的首標(biāo)， 為公式的尾部。)()()(),()2();,()()() 1 (1yQxRxQyxPzyxzxRyQxPzyx：例

46、第78頁(yè)/共292頁(yè)第七十九頁(yè)，共292頁(yè)。定理1：任一謂詞公式都可以(ky)化成為與之等值的前束范式。1(B23求前束范式的步驟：、消去可能出現(xiàn)的多余量詞 在 中無(wú)相應(yīng)變項(xiàng)的量詞）；、利用換名或代入規(guī)則使所有約束變?cè)姆?hào)均不相同，并且自由變?cè)c約束變?cè)姆?hào)也不相同；、利用量詞轄域的擴(kuò)張和收縮律，將所有量詞以在公式中出現(xiàn)的順序移到公式的最前面，擴(kuò)大量詞的轄域至整個(gè)公式。2.4一階邏輯(lu j)前束范式第79頁(yè)/共292頁(yè)第八十頁(yè)，共292頁(yè)。( )( )( , )( , )( , )( )( , , )xF xxG xxF x yyG x yxF x yyG yxH x y z 例：2.

47、4一階邏輯(lu j)前束范式第80頁(yè)/共292頁(yè)第八十一頁(yè)，共292頁(yè)。1212,BBkkA AAAAA從,推出結(jié)論 的推理形式在一階邏輯中，稱永真的蘊(yùn)涵式為推理定律。若一個(gè)推理的形式結(jié)構(gòu)正是某條推理定律，則該推理顯然(xinrn)是正確的。第一組第一組 命題命題(mng t)邏輯推理定律的代換實(shí)例邏輯推理定律的代換實(shí)例第二組第二組 由基本等值式生成的推理定律第三組第三組 以下重要定律第81頁(yè)/共292頁(yè)第八十二頁(yè)，共292頁(yè)。( )( )( ( )( )( ( )( )( )( )( ( )( )( )( )( ( )( )( )( )xA xxB xx A xB xx A xB xxA

48、xxB xx A xB xxA xxB xx A xB xxA xxB x 第四組第四組 消去量詞消去量詞(lingc)和引入量詞和引入量詞(lingc)的推理規(guī)則的推理規(guī)則1、全稱(qun chn)量詞消去規(guī)則（UI）2.5一階邏輯的推理(tul)理論第82頁(yè)/共292頁(yè)第八十三頁(yè)，共292頁(yè)。)()(yAxxAUI規(guī)則成立(chngl)的條件： （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ò)的個(gè)體常項(xiàng)。)()(cAxxA2.5

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

50、，不能用此規(guī)則1xxA ND2）：（：例),( : :3yxyLxyxL(x,y)RD：例2.5一階邏輯(lu j)的推理理論）（）（是偶數(shù)）：（是奇數(shù)）：（：例xxQxxPxxQ xxP ND4第85頁(yè)/共292頁(yè)第八十六頁(yè)，共292頁(yè)。3、全稱(qun chn)量詞引入規(guī)則（UG）( )( )A yxA x UG規(guī)則成立的條件： （1）y在A（y）中自由出現(xiàn)，且y取任何(rnh)值時(shí)A均為真；（2）x不在A（y）中約束出現(xiàn)。 含義：如果個(gè)體域的任意(rny)個(gè)體都具有性質(zhì)A，則個(gè)體域中的所有個(gè)體都具有性質(zhì)A。 ),(A(x) : :5yxyLyxL(x,y)RD：例2.5一階邏輯的推理理論

51、第86頁(yè)/共292頁(yè)第八十七頁(yè)，共292頁(yè)。4、存在量詞(lingc)引入規(guī)則（EG）( )( )A cxA x EG規(guī)則成立的條件： （1）c是個(gè)體(gt)域中某個(gè)確定的個(gè)體(gt)；（2）代替c的x不在A（c）中出現(xiàn)過(guò)。 含義(hny)：如果個(gè)體域有某一個(gè)個(gè)體c具有性質(zhì)A，則個(gè)體域中必存在具有性質(zhì)A的個(gè)體。 ), 8(A(8) : :6yyLyxL(x,y)RD：例2.5一階邏輯的推理理論第87頁(yè)/共292頁(yè)第八十八頁(yè)，共292頁(yè)。定義.一階邏輯自然推理(tul)系統(tǒng)F的定義 1.字母表：同一階語(yǔ)言的字母表 2.合式公式：同一階語(yǔ)言合式公式的定義 3.推理(tul)規(guī)則 a.前提引入規(guī)則

52、b.結(jié)論引入規(guī)則 c.置換規(guī)則 d.假言推理(tul)規(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一階邏輯(lu j)的推理理論第88頁(yè)/共292頁(yè)第八十九頁(yè)，共292頁(yè)。例7：證明邏輯三段論 所有的人總是(zn sh)要死的。 蘇格拉底是人。所以蘇格拉底是要死的。( ( )( ( )( )( )( ( )( )x F xG yH xxF xx F xH x例8：已知前提，證明結(jié)論：2.5一階邏輯(lu j)的推理理論第89頁(yè)/共292頁(yè)第九十頁(yè)，共292頁(yè)。2.5一階邏輯的推

53、理(tul)理論例10：如果一個(gè)人怕困難就不會(huì)獲得成功。每一個(gè)人或者獲得成功或者是失敗的。有些人未曾失敗過(guò)，所以(suy)有些人不怕困難。（個(gè)體域是人的集合）判斷這個(gè)推理是否正確。 例9：根據(jù)前提(qint)集合：同事之間總是有工作矛盾的，張平和李明沒(méi)有工作矛盾，能得出什么結(jié)論？第90頁(yè)/共292頁(yè)第九十一頁(yè)，共292頁(yè)。第91頁(yè)/共292頁(yè)第九十二頁(yè)，共292頁(yè)。第92頁(yè)/共292頁(yè)第九十三頁(yè)，共292頁(yè)。sxsy第93頁(yè)/共292頁(yè)第九十四頁(yè)，共292頁(yè)。例1： 1.偶素?cái)?shù)集合。2.二進(jìn)制的基數(shù)集合。3.英文字母的集合。4.全體(qunt)實(shí)數(shù)的集合。5.自然數(shù)集合。6.整數(shù)集合。7.有理

54、數(shù)集合。8.素?cái)?shù)集合。3.1集合(jh)的基本概念第94頁(yè)/共292頁(yè)第九十五頁(yè)，共292頁(yè)。3.1集合(jh)的基本概念集合的表示方法: 1.列舉法（枚舉法、外延法）把集合的所有元素（元素較少時(shí)(shosh)）寫在一個(gè)花括號(hào)內(nèi);列出足夠多的元素（元素很多或無(wú)窮時(shí)）以反映集合中元素的特征。如例1中的1、2、3、5可分別表示為：20，1a，b，cz，A，B，CZ1，2，3第95頁(yè)/共292頁(yè)第九十六頁(yè)，共292頁(yè)。3.1集合(jh)的基本概念2.描述法（概括法）將集合中的元素的性質(zhì)用一個(gè)謂詞公式來(lái)描述，S=X|P(X),意義為:集合S由且僅由滿足為此(wi c)公式P(X)的對(duì)象組成，即 ，當(dāng)且

55、僅當(dāng)p(a)為真。如例1中的4、6、7可表示為：sa|Rxx|Qxx3.文氏圖用圖形圖像直觀的描述集合之間的相互(xingh)關(guān)系和有關(guān)運(yùn)算。|Ixx第96頁(yè)/共292頁(yè)第九十七頁(yè)，共292頁(yè)。3.1集合(jh)的基本概念幾個(gè)常見(jiàn)(chn jin)集合的表示符號(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ù)集合；第97頁(yè)/共292頁(yè)第九十八頁(yè)，共292頁(yè)。3.1集合(jh)的基本概念集合的特性:A.互異性：一個(gè)集合的個(gè)元素(yun s)是可以區(qū)分開的，即每一 元素(yun s)只出現(xiàn)一次。B.無(wú)序性：集合中元素(yun s)排列順

56、序無(wú)關(guān)緊要，即集合表示 形式的不唯一性。例2：a，b，c=b，c，a=c，a，b=a，c，b=b，a，c=c，b，a第98頁(yè)/共292頁(yè)第九十九頁(yè)，共292頁(yè)。3.1集合(jh)的基本概念C.確定性：任一事物是否屬于某一集合(jh)，回答是確定的。例3：“好書(ho sh)”的全體，這不構(gòu)成集合。注意：一個(gè)集合是已知的，指的是對(duì)任一元素，利用某種方法可以判斷它是否是這個(gè)集合的元素，而不是把集合的每一個(gè)元素都給出來(lái)。第99頁(yè)/共292頁(yè)第一百頁(yè)，共292頁(yè)。3.1集合(jh)的基本概念集合的元素可以是任何具體或抽象的事物，包括(boku)別的集合，但不能是本集合自身。例4：在一個(gè)住著一些人家的偏

57、僻孤島( do)上，島上只有一個(gè)理發(fā)師a，a給且只給島上所有不能自己理發(fā)的人理發(fā)。問(wèn)誰(shuí)給a理發(fā)？第100頁(yè)/共292頁(yè)第一百零一頁(yè)，共292頁(yè)。定義1.設(shè)A和B是兩個(gè)集合(jh)，若A中的每一個(gè)元素都是B的元素，則稱A是B的子集，也稱B包含A,記作)(ABBA3.1集合(jh)的基本概念定義2.設(shè)A和B是任意兩個(gè)集合(jh)，若A包含B且B包含A，則稱A與B相等，記作A=B.即，ABBABA|BxAxxBA二、集合的關(guān)系第101頁(yè)/共292頁(yè)第一百零二頁(yè)，共292頁(yè)。3.1集合(jh)的基本概念定義(dngy)3.若A是B的子集且 ，則稱A為B的真子集，或稱B真包含A，記作，B稱為A的超集。是

58、集合間的包含關(guān)系。、；是元素與集合間的關(guān)系的區(qū)別：和、注意BA BA BABABA. 2 . 15中國(guó)人臺(tái)灣人臺(tái)灣人都是中國(guó)人。：例CRQN第102頁(yè)/共292頁(yè)第一百零三頁(yè)，共292頁(yè)。集合(jh)的相等關(guān)系的性質(zhì)：。，則且傳遞性：若）（；，則對(duì)稱性：若）（；自反性：CACBBAABBAAA.3.2).1 (設(shè)A,B,C為3個(gè)集合，集合的包含關(guān)系(gun x)的性質(zhì):。，則且傳遞性：若）（；，則且反對(duì)稱性：若）（；自反性：CACBBABAABBAAA.3.2).1 (3.1集合(jh)的基本概念第103頁(yè)/共292頁(yè)第一百零四頁(yè)，共292頁(yè)。, 01x|xA62Rx：例定義4.不包含(boh

59、n)任何元素的集合稱為空集，記作或推論：空集是唯一的。集。：空集是一切集合的子定理1 .7.6 .5.4 ).3().2( .17）（）（；）（）（；）（：判斷下列命題的真假例3.1集合(jh)的基本概念三、特殊(tsh)集合第104頁(yè)/共292頁(yè)第一百零五頁(yè)，共292頁(yè)。定義(dngy)4：在一定范圍內(nèi)，如果所有集合均為某一集合的子集，則稱該集合為全集，記作E。 。，；例：210 1 0定義(dngy)5.集合中元素的個(gè)數(shù)稱為基數(shù)或勢(shì)，用|A|表示。基數(shù)是有限數(shù)的集合稱為有限集，否則稱為無(wú)限集。全集(qunj)是相對(duì)的，不同的問(wèn)題有不同的全集(qunj)，即使是同一個(gè)問(wèn)題也可以取不同的全集(

60、qunj) 。3.1集合的基本概念第105頁(yè)/共292頁(yè)第一百零六頁(yè)，共292頁(yè)。含n個(gè)元素(yun s)的集合簡(jiǎn)稱n元集，其含有k(kn)個(gè)元素(yun s)的子集稱為它的k元子集。定義6.由集合S的所有子集組成的集合，稱為(chn wi)集合S的冪 集，記作P（S）。表示為：.|)(SAASP有限集S ，|P（S）|=2|S|例：Aa，b，c，d，c第106頁(yè)/共292頁(yè)第一百零七頁(yè)，共292頁(yè)。一、集合(jh)的基本運(yùn)算BxAx|xBA BA BABA1.且。的交集，記作與稱為，的公共元素組成的集合和，由和設(shè)有集合定義 BA| . B. 2BxAxxBABABAABA或的并集，記作與稱為