湖南大學(xué)離散數(shù)學(xué)教案-命題邏輯.ppt

《湖南大學(xué)離散數(shù)學(xué)教案-命題邏輯.ppt》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《湖南大學(xué)離散數(shù)學(xué)教案-命題邏輯.ppt（84頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

第一章 命題邏輯,楊圣洪 yangshenghong8@ 13007432216,引言 邏輯學(xué)是推理的基礎(chǔ)，在社會(huì)學(xué)、自然科學(xué)尤其計(jì)算機(jī)學(xué)科中得到普遍應(yīng)用。 數(shù)理邏輯是邏輯學(xué)的一個(gè)分支，也是數(shù)學(xué)的分支，它用數(shù)學(xué)方法研究推理規(guī)律，它采用符號(hào)的方法來(lái)描述和處理思維形式、思維過(guò)程和思維規(guī)律，它在程序設(shè)計(jì)、數(shù)字電路設(shè)計(jì)、計(jì)算機(jī)原理、人工智能等計(jì)算機(jī)課程得到了廣泛應(yīng)用。 命題邏輯是數(shù)理邏輯的基礎(chǔ)部分， 但究竟什么是命題？ 如何表示命題？ 如何構(gòu)造出復(fù)雜的命題？ 在本章將討論這些問(wèn)題。,1.1 命題及聯(lián)結(jié)詞 對(duì)錯(cuò)確定的陳述語(yǔ)句稱(chēng)為命題。如： (1)湖南大學(xué)是一本學(xué)校。 (2)命題邏輯是計(jì)算機(jī)科學(xué)的基礎(chǔ)課程。 (3)命題及聯(lián)結(jié)詞是命題邏輯的最基礎(chǔ)的內(nèi)容。 (4)4是素?cái)?shù)。 (5)湖南大學(xué)坐落于湘江以東。 (6)2011年湖南長(zhǎng)沙輕軌通車(chē)。 其中(1)、(2)、(3) 與事實(shí)相符，是對(duì)的、正確的，稱(chēng)為真命題，或者稱(chēng)命題的值為“真”，簡(jiǎn)記為T(mén)或數(shù)字1。 而(4)、(5)明顯與事實(shí)不相符，是錯(cuò)的、不正確，稱(chēng)為假命題，或稱(chēng)命題的值為“假”，簡(jiǎn)記為F或數(shù)字0。 陳述句(6)的正確性，到2011年12月時(shí)能確定的，若屆時(shí)開(kāi)通了則它是對(duì)的、為真命題，否為假命題。,1.1 命題及聯(lián)結(jié)詞 對(duì)錯(cuò)確定的陳述語(yǔ)句稱(chēng)為命題。如： (7) x與y之和為100，其中x為整數(shù)，y為整數(shù) (8)1加1等于10 (7)的對(duì)錯(cuò)不確定的。當(dāng)x為50、y為50時(shí)是對(duì)的，當(dāng)x為51、y為52時(shí)是錯(cuò)的。 (8)的對(duì)錯(cuò)是不確定的，為二進(jìn)制時(shí)正確，當(dāng)為八進(jìn)制、十進(jìn)制時(shí)是錯(cuò)的，因此這兩個(gè)陳述句不是命題。 (9)岳麓山的紅葉真美呀！ (10)動(dòng)作快點(diǎn)！ (11)你是離散數(shù)學(xué)老師嗎？ 這三個(gè)語(yǔ)句不是陳述語(yǔ)句，因此不是命題。,1.1 命題及聯(lián)結(jié)詞 對(duì)錯(cuò)確定的陳述語(yǔ)句稱(chēng)為命題。如： (12)我在說(shuō)假話(huà)。 (13)我只給自己不能理發(fā)的人理發(fā)。 (14)派出所說(shuō):必須先房子再能上戶(hù)口 單位后勤說(shuō):必須先有戶(hù)口才能分房 你能上到戶(hù)口與要到房子嗎? 這是一個(gè)悖論，其真值不能確定，故不是命題。。,1.1 命題及聯(lián)結(jié)詞 對(duì)錯(cuò)確定的陳述語(yǔ)句稱(chēng)為命題。如： (13)我既要學(xué)程序設(shè)計(jì)，又要學(xué)離散數(shù)學(xué)。 (14)我們?cè)绮驮诠⑹程没蛲饷嬖琰c(diǎn)攤上吃。 (15)我不是數(shù)學(xué)院的學(xué)生 這三個(gè)陳述句都與事實(shí)相符，是對(duì)的，是真命題，其值為真(T/1)。 其中(13)與(14)可分解為另外二句話(huà)的組合， 而(15)是對(duì)“我是數(shù)學(xué)院學(xué)生”的否定，這些語(yǔ)句稱(chēng)為“復(fù)合命題”，不能再分解的語(yǔ)句稱(chēng)為“簡(jiǎn)單命題”或“原子命題”，為了便于推理與書(shū)寫(xiě)，常用小寫(xiě)字母表示簡(jiǎn)單命題或原子命題。,1.1 命題及聯(lián)結(jié)詞 簡(jiǎn)單命題組合成復(fù)雜命題時(shí)所使用的輔助詞稱(chēng)為“聯(lián)結(jié)詞”。 命題邏輯中的聯(lián)結(jié)詞歸納為以下5種。 合取?：C語(yǔ)言中 && and 并且 析取?：C語(yǔ)言中 || or 或 否定?：C語(yǔ)言中 ! not 非,不是,否定 條件式?：C語(yǔ)言中 if () 如果…那么 如p則q 雙條件式?： 如p則q且如q則p,當(dāng)且僅當(dāng),1.1 命題及聯(lián)結(jié)詞 定義1.1合?。?當(dāng)p、q都對(duì)，即取值為真(T或1)時(shí)，“p合取q”的值為真.,1.1 命題及聯(lián)結(jié)詞 定義1.1合?。?當(dāng)p、q都對(duì)，即取值為真(T或1)時(shí)，“p合取q”的值為真，其他情況為假。,邏輯運(yùn)算符“合取”，與漢語(yǔ)中“并且、而且、同時(shí)”含義相當(dāng),1.1 命題及聯(lián)結(jié)詞 定義1.2析?。?當(dāng)p、q都不對(duì)，即取值為假(F或0)時(shí)，“p析取q”的值為假，其他情況為真。,邏輯運(yùn)算符“析取”，與漢語(yǔ)中“或”含義相當(dāng)，但有細(xì)微的區(qū)別,1.1 命題及聯(lián)結(jié)詞 邏輯運(yùn)算符“析取” 與漢語(yǔ)的“或”幾乎一致但有區(qū)別： (16)“講離散數(shù)學(xué)的老師是楊老師或劉老師”，可以表示為“講離散數(shù)學(xué)的老師是楊老師”?“講離散數(shù)學(xué)的老師是劉老師”，這兩個(gè)原子命題有可能都是對(duì)的，這種“或”稱(chēng)為“可同時(shí)為真的或”，或簡(jiǎn)稱(chēng)為“可兼或”。 (17)“離散數(shù)學(xué)的教室是102或302”，不可以表示為“離散數(shù)學(xué)的教室是102”?“離散數(shù)學(xué)的教室是302”，因?yàn)檫@兩個(gè)原子命題不可能都對(duì)，只能這二種情況之一，這種“或”稱(chēng)為“不可同時(shí)為真的或”，或簡(jiǎn)稱(chēng)為“不可兼或”、“排斥或”. 這種“或”表示不能簡(jiǎn)單表示為“析取”，需要聯(lián)合使用下面將要介紹的“否定”與“析取”符號(hào)，才能準(zhǔn)確表達(dá)。,1.1 命題及聯(lián)結(jié)詞 定義1.3否定:當(dāng)p是1 ，p的否定?p即為0。,邏輯運(yùn)算符“否定”，與漢語(yǔ)中“否定”含義相當(dāng). “我不是數(shù)學(xué)院的學(xué)生”可表示為“?我是數(shù)學(xué)院的學(xué)生” “離散數(shù)學(xué)的教室是102或302”,表示 離散數(shù)學(xué)的教室是102不是302“ 或 “離散數(shù)學(xué)的教室是302不是102“ p:離散數(shù)學(xué)的教室是102 q:離散數(shù)學(xué)的教室是302 上面的語(yǔ)句表示: (p??q)?(?p?q),1.1 命題及聯(lián)結(jié)詞 定義1.4條件:當(dāng)p是1 ,q是0時(shí),p?q為0,即1?0為0,其他情況為1。,邏輯運(yùn)算符“如果…那么”，它是用單個(gè)運(yùn)算符表示一個(gè)復(fù)合語(yǔ)句。 如老媽說(shuō)：“如果期終考了年級(jí)前10名，那么獎(jiǎng)勵(lì)1000元”。 p:期終考了年級(jí)前10名 q:獎(jiǎng)勵(lì)1000元 則上面的語(yǔ)句表示為p?q。 當(dāng)p為1即“期終考了年級(jí)前10”， 且q為0即“沒(méi)有獎(jiǎng)勵(lì)1000元” 這時(shí)老媽的話(huà)是假話(huà)空話(huà)， 故p?q為0,1.1 命題及聯(lián)結(jié)詞 定義1.4條件式(蘊(yùn)含式):當(dāng)p是1 ,q是0時(shí),p?q為0,即1?0為0,其他情況為1。 p為前件,q為后件,(1)當(dāng)p為1即“我期終考了年級(jí)前10” q為0即“我老媽沒(méi)有獎(jiǎng)勵(lì)1000元” 這時(shí)老媽的話(huà)為假，即p?q為0 (2)當(dāng)p為1即“我期終考了年級(jí)前10” q為1即“我老媽獎(jiǎng)勵(lì)1000元” 這時(shí)媽媽的話(huà)就對(duì)了，即p?q為1 (3)至于p為0即“我期終考了年級(jí)不是前10”時(shí),無(wú)論q為1或?yàn)?，即無(wú)論“我老媽獎(jiǎng)勵(lì)1000元“或不獎(jiǎng)勵(lì)，都不能說(shuō)老媽的話(huà)是假的，故可善意的認(rèn)為p?q為1均為1,1.1 命題及聯(lián)結(jié)詞 定義1.5雙條件:當(dāng)p與q值相同0時(shí),p?q為1,不同為0。 稱(chēng)p與q的等價(jià)式,“我明年賺了10萬(wàn)當(dāng)且僅當(dāng)我買(mǎi)彩票中了大獎(jiǎng)”， 可以表示為“我明年賺了10萬(wàn)?我買(mǎi)彩票中了大獎(jiǎng)”,1.2公式及其賦值 對(duì)錯(cuò)明確的陳述語(yǔ)句稱(chēng)為命題，其真值確定，又稱(chēng)為命題常元或命題常項(xiàng)，相當(dāng)于初等數(shù)學(xué)中的“常數(shù)”。 數(shù)學(xué)的運(yùn)算符號(hào)為“加+、減-、乘x、除?、冪?”， 命題邏輯的符號(hào)“合取?、析取?、否定?、條件?、雙條件?” 數(shù)學(xué)中用變量x表示某些數(shù)，如x2+x+10是代數(shù)式， 命題邏輯用變量表示任意一個(gè)命題，如p,q,r,這時(shí)由符號(hào)與變量所構(gòu)成命題表達(dá)式，簡(jiǎn)稱(chēng)為“命題公式”。 代數(shù)式的書(shū)寫(xiě)有規(guī)律，命題公式也有規(guī)律與約束，稱(chēng)滿(mǎn)足這些規(guī)則的公式為“合式公式”，也稱(chēng)為“命題公式”，簡(jiǎn)稱(chēng)為“公式”。,1.2公式及其賦值 定義1.2.1 合式公式的生成規(guī)則 (1)單個(gè)命題變?cè)⒚}常元為合式公式(原子公式)。 (2)若A是合式公式，則?A、(A)也是合式公式。 (3)若A、B是合式公式，則A?B、A?B、A?B、A?B是合式公式。 (4)有限次使用(2)~(3)形成的字符串均為合式公式。 如：(p?1)?q是合式公式。 因?yàn)閜、1是合公式，則(p?1)是合式公式，而r是合式公式，故(p?1)?q是合式公式。 (p?1)r?不是合式公式。 因?yàn)閜、1是合公式，則(p?1)是合式公式，而r是合式公式，但(p?1) r?不是合法公式。,1.2公式及其賦值 對(duì)于代數(shù)式x2+y+10，當(dāng)x與y的值不確定時(shí)，該代數(shù)式的值是不確定的。 對(duì)于公式 (p?1)?q，由于p與q值不確定時(shí)，公式(p?1)?q的值不確定，因而不是命題。 只有當(dāng)p與q的值確定后，公式(p?1)?q的值才能確定，我們可能像表1.2到表1.5一樣，給出公式在各種情況下的取值，即得到這個(gè)公式的真值表。,p與q每一種取值稱(chēng)為p、q的一種解釋,1.2公式及其賦值 公式(?p?q)、p?q的真值表如下表。,真值表的構(gòu)造方法： (1)命題變?cè)娜≈祻娜?開(kāi)始，依次加1，直到全1，當(dāng)有n個(gè)變?cè)獣r(shí)，則共有2n種不同的取值情況。 (2)分步驟計(jì)算公式的值 (3)見(jiàn)黑板上寫(xiě),成真賦值:如p?q為(0,0),(0,1),(1,1) 成假賦值:如p?q為(1,0),1.2公式及其賦值 公式(p?q)?(q?p)、p?q的真值表。,無(wú)論p/q取何值，這兩個(gè)公式的值總相等。,1.2公式及其賦值 公式 ?(p?q)、? p? ? q的真值表。,無(wú)論p/q取何值，這兩個(gè)公式的值總相等。,1.2公式及其賦值 公式p?q、? p?q的真值表。,無(wú)論p/q取何值，這兩個(gè)公式的值總相等。,1,1.2公式及其賦值 公式p?q、?q??p的真值表。,無(wú)論p/q取何值，這兩個(gè)公式的值總相等，若前者稱(chēng)為原命題，后者為逆否命題,1,1.2公式及其賦值 公式p?(q?r)、(p?q)?(p?r)的真值表。,無(wú)論p/q取何值，這兩個(gè)公式的值，與前面各例不同，此表是將運(yùn)算結(jié)果寫(xiě)在聯(lián)結(jié)詞的下方！,1.3 等值式 一、復(fù)習(xí) 由前節(jié)可知： p?q與?p?q、 ?q??p p?q與(p?q)?(q?p) 、(p?q)?(?p??q) ?(p?q)與?p ? ?q p?(q?r)、(p?q)?(p?r) 的真值表完全一樣，稱(chēng)為等值。 定義1.3.1 設(shè)A、B是兩個(gè)合法的命題公式，無(wú)論其中的命題變?cè)『沃?，這兩個(gè)公式的總相等，稱(chēng)為兩個(gè)公式等值，記為A?B,由定義及前節(jié)習(xí)題有： (1)p?q??p?q??q??p 條件式的等值式 (2)p?q?(p?q)?(q?p)?(p?q)?(?p??q) 雙條件 (3)p???p 雙重否定律 (4)p?p?p?p?p 冪等律 (5)p?q? q?p，p?q? q?p 交換律 (6) p?(q?r) ?(p?q) ? r 結(jié)合律 p?(q?r) ? (p?q) ? r (7) p?(q?r) ?(p?q)?(p?r) 分配律 p?(q?r) ? (p?q)?(p?r) (8) p?(p?r) ?p 吸收律(多吃少) p?(p?r) ?p (9) ?(p?q) ??p??q 德摩律 ?(p?q) ??p??q 將以上等值式中的變?cè)獡Q成合式公式仍等值！,如：p?q ? ?p?q 則有 A?B ? ?A?B 盡管A/B可能很復(fù)雜，但是公式值也只有0、1二種可能，公式A/B的組合只有0/0,0/1,1/0,1/1四種，如下表所示,顯然有 A?B ? ?A?B,置換規(guī)則：當(dāng)將公式A中的子公式B換成C得到公式D后，若B?C，那么A?D。 因?yàn)锳、D除了“A中B所在之處、D中C所在之處”外，其他地方均相同，而不同之處的B與C等值，所以公式A、公式D的真值表應(yīng)該完全他相同，故A?D。 當(dāng)將一個(gè)公式的局部進(jìn)行等值替換后， 仍與原公式等值，這也是數(shù)學(xué)中最常見(jiàn)的方法，不斷對(duì)局部進(jìn)行等值替換的操作，稱(chēng)為“等值演算”。 利用該規(guī)則及前述的等值式，可進(jìn)行等值演算，從而推導(dǎo)出新的公式。,求證 (p?q)?r?(p?r) ? (q?r) (p?q)?r ??(p?q)?r 條件式的等值式 ?(?p??q) ?r 利用德摩律 ?r? (?p??q) 交換律 ?(r??p)?( r??q) 分配律 ?(?p ? r)?( ?q?r) 交換律 ?(p?r) ? (q?r) 條件式等值式,等值演算的基本套路 (1)轉(zhuǎn)換? ： A?B??A?B (2)恰當(dāng)轉(zhuǎn)換? ：A?B?(?A?B) ?(A??B) ?(A?B)?(?A??B) 確保公式只保留? ? ?聯(lián)結(jié)詞 (3)否定到底 ： ??A, ?(A?B), ?(A?B) (4)恰當(dāng)使用分配律、吸收律。,利用等值演算，判斷公式的類(lèi)型 ((p?q)?p)?q ((p?q)?p)?q ?((?p?q)?p)?q (條件式的等值式) ??((?p?q)?p)?q (條件式的等值式) ? (? (?p?q)??p)?q (德摩律) ? ((p??q)??p)?q (德摩律) ? (p??q)?(?p?q) (結(jié)合律) ? (p??q)? ? (p??q) (逆用德摩律) ?A??A (A= (p??q)) ?1 稱(chēng)為永真式或重言式， 即利用等值演算，可以判斷公式的類(lèi)型。,利用等值演算判斷公式類(lèi)型：?(p?(p?q))?r 解： ?(p?(p?q))?r ??(?p?(p?q))?r (條件式的等值式) ??((?p?p)?q) ?r (結(jié)合律) ??(1?q) ?r (析取的性質(zhì)即析取定義真值表) ??1?r (析取的性質(zhì)即析取定義真值表) ?0?r (否定的定義) ?0 (析取的性質(zhì)即析取定義真值表) 永假式或矛盾式。 問(wèn)題：盡管有套路可行，但是隨意性還是比較大，能否有某種方式肯定能成功呢？,1.4 析取范式與合取范式 文字：命題變項(xiàng)(變?cè)?及其否定稱(chēng)為文字. 如:p,q,r, ?p, ?q, ?r 簡(jiǎn)單析取式:僅由有限個(gè)文字構(gòu)成的析取式. 如:p?q, ?p?q,p??q, ?p? ?q,p?q?r 簡(jiǎn)單合取式:僅由有限個(gè)文字構(gòu)成的合取式. 如:p?q, ?p?q,p??q, ?p??q,p?q?r 定理：簡(jiǎn)單析取式與簡(jiǎn)單合取式 (1)一個(gè)簡(jiǎn)單析取式Ai是重言式? 含有某個(gè)命題變?cè)捌浞穸ㄊ?，如Ai=p??p?… (2)一個(gè)簡(jiǎn)單合取式Ai是矛盾式? 含有某個(gè)命題變?cè)捌浞穸ㄊ剑鏏i=p??p?…,1.4 析取范式與合取范式 析取范式：由有限個(gè)簡(jiǎn)單合取式的析取構(gòu)成的命題公式稱(chēng)為析取范式。 總體是析取式?，每對(duì)括號(hào)內(nèi)是合取式 A=(p?q)?(?p?r) 合取范式：由有限個(gè)簡(jiǎn)單析取式的合取構(gòu)成的命題公式稱(chēng)為合取范式。 總體是合取式?，每對(duì)括號(hào)內(nèi)是析取式 A=(p?q)?(?p?r),1.4 析取范式與合取范式 總體是析取式?，每對(duì)括號(hào)內(nèi)是合取式 A=(p?q)?(?p?r) 析取范式 總體是合取式?，每對(duì)括號(hào)內(nèi)是析取式 A=(p?q)?(?p?r) 合取范式 定理：析取范式與合取范式 (1)一個(gè)析取范式A是矛盾式? 每個(gè)簡(jiǎn)單合取式是矛盾式。 A=(p?q)?(?p?r) (2)一個(gè)合取范式A是重言式? 每個(gè)簡(jiǎn)單析取式是重言式。 A=(p?q)?(?p?r),1.4 析取范式與合取范式 (1)轉(zhuǎn)換? ： A?B??A?B (2)恰當(dāng)轉(zhuǎn)換? ：A?B?(?A?B) ?(A??B) ?(A?B)?(?A??B) (3)否定到底 ： ??A, ?(A?B), ?(A?B) (4)適當(dāng)使用分配律： A?(B?C), A?(B?C). 經(jīng)過(guò)第1步、第2步轉(zhuǎn)換后，公式中只有?、?、?三種運(yùn)算符。 經(jīng)過(guò)第3步后，?從括號(hào)外深入到變?cè)那懊?，與變?cè)Y(jié)合成文文字，文字之間只有?、?。,1.4 析取范式與合取范式 (1)轉(zhuǎn)換? ： A?B??A?B (2)恰當(dāng)轉(zhuǎn)換? ：A?B?(?A?B) ?(A??B) ?(A?B)?(?A??B) (3)否定到底 ： ??A, ?(A?B), ?(A?B) (4)適當(dāng)使用分配律： A?(B?C), A?(B?C). 如果外層運(yùn)算符全部是?，而內(nèi)層子公式全部是簡(jiǎn)單析取式，則已經(jīng)是合取范式。 如果內(nèi)層某子公式形如A?(B?C)，不是簡(jiǎn)單析取式，則轉(zhuǎn)換為(A?B)?(A?C)。,1.4 析取范式與合取范式 (1)轉(zhuǎn)換? ： A?B??A?B (2)恰當(dāng)轉(zhuǎn)換? ：A?B?(?A?B) ?(A??B) ?(A?B)?(?A??B) (3)否定到底 ： ??A, ?(A?B), ?(A?B) (4)適當(dāng)使用分配律： A?(B?C), A?(B?C). 如果外層運(yùn)算符全部是?，而內(nèi)層子公式全部是簡(jiǎn)單合取式，則已經(jīng)是析取范式。 如果內(nèi)層某子公式形如A?(B?C)，不是簡(jiǎn)單合取式，則轉(zhuǎn)換為(A?B)?(A?C)。因此有： (1)不是永假的命題公式，存在析取范式。 (2)不是永真的命題公式，存在合取范式。,1.4 析取范式與合取范式 (1)轉(zhuǎn)換? ： A?B??A?B (2)恰當(dāng)轉(zhuǎn)換? ：A?B?(?A?B) ?(A??B) ?(A?B)?(?A??B) (3)否定到底 ： ??A, ?(A?B), ?(A?B) (4)適當(dāng)使用分配律： A?(B?C), A?(B?C). 如析取式范式：(p?q) ?r ?(?p?q) ?r ?((?p?q)?r)?(?(?p?q)??r) ?(?p ?r)?(q?r)?(p??q??r),1.4 析取范式與合取范式 求(p?q) ?r的析取范式、合取范式 解：(1)求析取范式。即外層是?，內(nèi)層是?，所以?轉(zhuǎn)換模式為A?B? (A?B)?(?A??B) (p?q) ?r ?((p?q) ?r)?( ? (p?q) ?? r) (整體為析取) ?((?p?q) ?r)?( ? (?p?q) ?? r) (A?B??A?B) ?((?p?q) ?r)?( (p??q) ?? r) (德摩律) ?((?p ?r )?(q?r))?( (p??q) ?? r) (分配律) ?(?p ?r )?(q?r)?( p??q ?? r) (結(jié)合律),1.4 析取范式與合取范式 解：(1)求合取范式。所以?轉(zhuǎn)換模式為A?B?(?A?B)?(A??B) (p?q) ?r ?(? (p?q)?r)?( (p?q)?? r) (整體為合取) ?(? (?p?q)?r)?( (?p?q)?? r) (條件等價(jià)式) ?((p??q)?r)?( (?p?q)?? r) (德摩律) ?((p?r) ?(?q?r))?( (?p?q)?? r) (分配律) ?(p?r) ?(?q?r)?( ?p?q?? r) (結(jié)合律),1.4 析取范式與合取范式 小項(xiàng)：在含有n個(gè)變?cè)暮?jiǎn)單合取式中,每個(gè)命題變?cè)蚱浞穸▋H出現(xiàn)一次,且各變?cè)雌渥帜疙樞虺霈F(xiàn),則該簡(jiǎn)單合取式為(極)小項(xiàng)。 如：p?q?r, p??q?r, p?q??r, ?p?q?r (?p ?r), (q?r) 非小項(xiàng) 大項(xiàng)：在含有n個(gè)變?cè)暮?jiǎn)單析取式中,每個(gè)命題變?cè)蚱浞穸▋H出現(xiàn)一次,且各變?cè)雌渥帜疙樞虺霈F(xiàn),則該簡(jiǎn)單析取式為(極)大項(xiàng)。 如：p?q?r, p??q?r, p?q??r, ?p?q?r (p?r), (?q?r) 非大項(xiàng),1.4 析取范式與合取范式 主析取范式：一個(gè)析取范式中，如果所有簡(jiǎn)單合取式均為(極)小項(xiàng)，則稱(chēng)為主析取范式。 (p?q) ?r ?(?p ?r)?(q?r)?(p??q??r) 不是 (?p?q?r)?(?p??q?r)? (p?q?r)?(p??q??r) 是主析取范式,1.4 析取范式與合取范式 主合取范式：一個(gè)合取范式中，如果所有簡(jiǎn)單析取式均為(極)大項(xiàng)，則稱(chēng)為主合取范式。 (p?q)?r ?(p?r)?(?q?r)?(?p?q??r) 不是 ?(p?q?r)? (p??q?r) ?(?p??q?r) ?(?p?q??r) 是主合取范式,1.4 析取范式與合取范式—獲取方法 通過(guò)轉(zhuǎn)換聯(lián)結(jié)詞??、“?到底”及適當(dāng)使用分配律，可以得到合取范式與析取范式，這時(shí)可能還缺少某個(gè)變?cè)?因?yàn)閜??p?1，1?r?1，可在缺少變?cè)男№?xiàng)中加入形如“p??p”的公式。 如小項(xiàng)(?p?r)缺少變?cè)猶，加入q??q，即 ?p?r ??p?1?r ??p?(q??q)?r ?(?p?q?r)?(?p??q?r)。,1.4 析取范式與合取范式—獲取方法 通過(guò)轉(zhuǎn)換聯(lián)結(jié)詞??、“?到底”及適當(dāng)使用分配律，可以得到合取范式與析取范式，這時(shí)可能還缺少某個(gè)變?cè)?因?yàn)閜??p?1，1?r?1，可在缺少變?cè)男№?xiàng)中加入形如“p??p”的公式。 (p?q) ?r ?(?p?r)?(q?r)?(p??q??r) ?(?p?(q??q)? r)?((p??p)?q?r)?(p??q??r) ?(?p?q?r )?(?p??q?r)? (p?q?r )?(?p?q?r) ?(p??q??r) ?(?p?q?r )?(?p??q?r)? (p?q?r )? (p??q??r),1.4 析取范式與合取范式—獲取方法 通過(guò)轉(zhuǎn)換聯(lián)結(jié)詞??、“?到底”及適當(dāng)使用分配律，可以得到合取范式與析取范式，這時(shí)可能還缺少某個(gè)變?cè)?因?yàn)閜??p?0，0?p?p，可在缺少變?cè)拇箜?xiàng)中加入形如“p??p”的公式 。 如 p?r ?p?0?r ?p?(q??q)?r ?(p?q?r)?(p??q?r),1.4 析取范式與合取范式—獲取方法 通過(guò)轉(zhuǎn)換聯(lián)結(jié)詞??、“?到底”及適當(dāng)使用分配律，可以得到合取范式與析取范式，這時(shí)可能還缺少某個(gè)變?cè)?因?yàn)閜??p?0，0?p?p，可在缺少變?cè)拇箜?xiàng)中加入形如“p??p”的公式 。 (p?q) ?r ?(p?r)?(?q?r)?(?p?q??r) ?(p?(q??q)?r)?((p??p)??q?r)?(?p?q??r) ?(p?q?r)?(p??q?r)?(p??q?r)?(?p??q?r)? (?p?q??r) ?(p?q?r) ?(p??q?r)?(?p??q?r) ? (?p?q??r),1.4 析取范式與合取范式 當(dāng)一個(gè)公式比較復(fù)雜時(shí)，得到其析取范式、合取范式的演算量比較大，再將簡(jiǎn)單析取式轉(zhuǎn)換為大項(xiàng)，或簡(jiǎn)單合取式轉(zhuǎn)換為小項(xiàng)，又需要進(jìn)一步演算，能否直接基于原公式，不進(jìn)行等值演算直接得到，或者能按某種統(tǒng)一的方式得到其主析取范式、主合取范式呢？ 通過(guò)真值表可以實(shí)現(xiàn)！為此先研究小項(xiàng)與大項(xiàng)的性質(zhì)。,1.4 析取范式與合取范式 通過(guò)真值表可以實(shí)現(xiàn)！為此先研究小項(xiàng)與大項(xiàng)的性質(zhì)，下表是各小項(xiàng)的真值表。,1. 3個(gè)變?cè)男№?xiàng)共有8個(gè)，它們各不相同。 2.從每一行來(lái)看，命題變?cè)拿總€(gè)指派中，只有一個(gè)小項(xiàng)的值為1。 3.從每一列來(lái)看，每個(gè)小項(xiàng)僅在一個(gè)指派中值為1，其余7種指派中均為0。 4.小項(xiàng)值為1(如?p??q??r=1)時(shí)，?p,?q,?r均為1，即(p,q,r)=(0,0,0)，取該值為小項(xiàng)編號(hào)，如最后一行。,(5)根據(jù)小項(xiàng)的編號(hào)，可寫(xiě)出小項(xiàng)的具體形式。 如小項(xiàng)m101，其編號(hào)為101，表示(p,q,r)=(1,0,1)時(shí)該小項(xiàng)的值為1，而小項(xiàng)是文字的合取，故小項(xiàng)的各個(gè)文字必須為1,則文字只能是p、?q、r,故該小項(xiàng)為p??q?r。 規(guī)則：1對(duì)應(yīng)變?cè)旧?如p)，0對(duì)應(yīng)其否定(如?p) 。 如m00為?p??q、m01為?p?q、m10為p??q、m11為p?q。 很重要！,(1)三個(gè)變?cè)拇箜?xiàng)共有8個(gè)。 (2) 每一行:每個(gè)指派中，只有一個(gè)大項(xiàng)的值為0。 (3)每一列:每個(gè)大項(xiàng)僅在一個(gè)指派下值為0。 (4)大項(xiàng)值為0(如?p??q??r=0) 時(shí)，?p、?q、?r均為0，則(p,q,r)=(1,1,1)，將其記為大項(xiàng)編號(hào),如表最后行。,(5)根據(jù)大項(xiàng)的編號(hào)，可寫(xiě)出大項(xiàng)的具體形式。 如大項(xiàng)M101,其編號(hào)為101，表示(p,q,r)=(1,0,1)時(shí)該大項(xiàng)的值為0，而大項(xiàng)是文字的析取，故各個(gè)文字必須為0，文字只能是?p、q、?r，故該大項(xiàng)為?p?q??r。 規(guī)則：1對(duì)應(yīng)變?cè)姆穸?如?p)，0對(duì)應(yīng)變?cè)?如p) 如M00為p?q,M01為p??q,M10為?p?q, M11為?p??q。,1.4 析取范式與合取范式—獲取方法 1、先轉(zhuǎn)換析取式或合取式，再合取1或析取0。 2、先建立真值表， 取出所有成真賦值對(duì)應(yīng)的小項(xiàng)，析取所有小項(xiàng)得主析取范式。小項(xiàng)與成真賦值對(duì)應(yīng)。 取出所有成假賦值對(duì)應(yīng)的大項(xiàng)，合取所有大項(xiàng)得主合取范式。大項(xiàng)與成假賦值對(duì)應(yīng)。 如用真值表求主范式: (p?q)?r, p?q, p?q, ?(p?q)?q,p?(p?q),(p?q) ?r的主析取范式、主合取范式,主析取范式 ?公式值為1的指派對(duì)應(yīng)小項(xiàng)的析取 m001? m011? m100? m111 1變?cè)?0變?cè)穸? 使小項(xiàng)=1 (?p??q?r)? (?p?q?r)?(p??q??r)?( p?q?r),(p?q) ?r的主析取范式、主合取范式,主合取式范式 ?公式值為0的指派對(duì)應(yīng)大項(xiàng)的合取 ? M000? M010? M101? M110 1變?cè)穸?變?cè)?使大項(xiàng)=0 (p?q?r)?( p??q?r)?( ?p?q??r)?( ?p??q?r),(p?q)?r、與其主析取范式、主合取范式的真值完全一樣，說(shuō)明三者互相等值，一般情況下有如下定理 ： (1)不是永假的命題公式，有等值的主析取范式。 (2)不是永真的命題公式，有等值的主合取范式。 由于永假?zèng)]有取值為1的解釋?zhuān)薀o(wú)相應(yīng)小項(xiàng)，故沒(méi)有主析取范式。永真無(wú)取值為0的解釋,故沒(méi)有主合取范式.,設(shè)計(jì)一個(gè)電子評(píng)分系統(tǒng)，3位專(zhuān)家打分，如果有2位以上專(zhuān)家打分為“通過(guò)”，則總成績(jī)?yōu)椤巴ㄟ^(guò)” 。,對(duì)應(yīng)的主析取范式?值為1的指派對(duì)應(yīng)的小項(xiàng)的析取 ?m011?m101?m110?m111 ?(?x1?x2?x3)? (x1??x2?x3)?(x1?x2??x3)?(x1?x2?x3) ?((?x1?x2?x3)?(x1??x2?x3))?((x1?x2??x3)? (x1?x2?x3)) ?( ((?x1?x2)? (x1??x2))?x3)?(((x1?x2?(?x3?x3))) ?(((?x1?x2)? (x1??x2))?x3)?( x1?x2) ?((?x1??x2)?(x1?x2)?x3)?( x1?x2) 與非或門(mén)表示,某公司要從曹、喬、宋、黎、鄒5人中，選擇一些人承包一項(xiàng)工程，考慮到人與人組合優(yōu)化的問(wèn)題，需滿(mǎn)足如下約束條件： (1)如果曹去，那么喬也去； (2)黎、鄒兩人中必有一人去； (3)喬、宋兩人中去且僅去一人； (4)宋、黎兩人同去或同時(shí)不去； (5)若鄒去，則曹、喬也同去； 解：用小寫(xiě)字母表示： c:曹去， q：?jiǎn)倘?s：宋去 l：黎去 z：鄒去時(shí)，以上5句話(huà)可表示為如下的公式： (c?q)、(l?z)、((q??s)?(?q?s))、(s?l)、(z?(q?c))， 5句話(huà)同時(shí)成立即每句話(huà)的值均為1，也即其合取式(c?q)?(l?z)?((q??s)?(?q?s))?(s?l)?(z?(q?c))為1,(c?q)?(l?z)?((q??s)?(?q?s))?(s?l)?(z?(q?c)) ? (?c?q)?(l?z)?((q??s)?(?q?s))?((s?l)?(?s??l))?(?z?(q?c)) ?(?c?q)?(l?z)?(?z?(q?c))?((q??s?s?l)?(q??s??s??l)?(?q?s?s?l)?(?q?s??s??l)) ?(?c?q)?(l?z)?(?z?(q?c))?((q??s??l)?(?q?s?l)) ?(?c?q)?(l?z)?((?z?q??s??l)?(?z??q?s?l)?(q?c??s??l)) ?(?c?q)?((?z??q?s?l)?(z?q?c??s??l)) ?(?c??z??q?s?l)?(z?q?c??s??l) 因(c?q)?(l?z)?((q??s)?(?q?s))?(s?l)?(z?(q?c))為1，故1?(?c??z??q?s?l)?(z?q?c??s??l)， 故1?(?c??z??q?s?l)或1?(z?q?c??s??l) 故 方案一是：曹不去、鄒不去、喬不去，宋與黎去。 方案二是：曹去、喬去、鄒去，宋與黎均不去,在某班班委的選舉中，該班的甲、乙、丙學(xué)生預(yù)言： 甲說(shuō)：王娟為班長(zhǎng)、劉強(qiáng)為生活委員； 乙說(shuō)：金鑫為班長(zhǎng)、王娟為生活委員； 丙說(shuō)：劉強(qiáng)為班長(zhǎng)、王娟為學(xué)習(xí)委員； 結(jié)果公布后，發(fā)現(xiàn)甲、乙、丙三人都恰好對(duì)了一半，請(qǐng)問(wèn)王娟、劉強(qiáng)、金鑫各任何職？ 解：p1,q1,r1:表示王娟，劉強(qiáng)，金鑫是班長(zhǎng)； p2,q2,r2:分別表示王娟，劉強(qiáng)，金鑫是學(xué)習(xí)委員； p3,q3,r3:分別表示王娟，劉強(qiáng)，金鑫是生活委員； “每個(gè)人說(shuō)法對(duì)一半”將是一個(gè)非常復(fù)雜的公式(p1??q3?r1??p3?q1??p2)?( p1??q3?r1??p3??q1?p2)?( p1??q3??r1?p3?q1??p2)?( p1??q3??r1?p3??q1?p2)?( ?p1?q3?r1??p3?q1??p2)?( ?p1?q3?r1??p3??q1?p2)?( ?p1?q3??r1?p3?q1??p2)?( ?p1?q3??r1?p3??q1?p2)，要構(gòu)造這9個(gè)變?cè)恼嬷当恚瑢⑿枰?9=512行，工作量實(shí)在太大了， ！,參考“真值表”，設(shè)計(jì)如下的判斷表,,1.6 推理理論 從已知條件、假設(shè)、前提或公理出發(fā)，根據(jù)推理規(guī)則推出結(jié)論、定理的過(guò)程，稱(chēng)為推理 。 定義1 設(shè)A與C是兩個(gè)命題公式，若A?C為永真式(重言式)，則稱(chēng)C是A的有效結(jié)論，或稱(chēng)A可以邏輯推出C，記為A?C. 由“?”的定義可知，當(dāng)A為假時(shí)，A?C肯定為真，故只要考慮A為真時(shí)C是否為真即可，故有: 定義2 設(shè)A與C是兩個(gè)命題公式，若當(dāng)A為真時(shí)C也為真，則稱(chēng)C是A的有效結(jié)論，或稱(chēng)A可以邏輯推出C，記為A?C。 一般情況下，利用定義2去證明要簡(jiǎn)單些，我們?cè)谄渌麑W(xué)科中遇到的證明都是基于定義2的。 判斷A?C為永真可用等值演算、真值表等方法,例題 求證：A?(A?B)?B (A?(A?B)) ?B ??(A?(A?B))?B (?的等值式) ?? (A?(?A?B))?B (?的等值式) ? ? ((A??A)?(A?B))?B (分配律) ?? (0?(A?B))?B (合取的性質(zhì)) ?? (A?B)?B (析取的性質(zhì)) ?(?A??B)?B (德摩律) ??A?(?B?B) (結(jié)合律) ??A?1 (析取的性質(zhì)) ? 1 (析取的性質(zhì)) 所以(A?(A?B)) ?B是重言式，真值表也證永真 所以A?(A?B)?B。這是有名的“假言推理(modus ponens)”，或“分離原則”,假如我今年進(jìn)入年級(jí)前10名老爸給我買(mǎi)iphone 4; 期末考試后我為年級(jí)第8名，所以老爸應(yīng)該給我買(mǎi)iphone4。這是假言推理。 A?(A?B)?B 從形式上看，結(jié)論B是A?B的后件，推導(dǎo)的結(jié)果是將后件分離出來(lái)，故也稱(chēng)為分離原則。 利用假言推理規(guī)則或分離規(guī)則，結(jié)合析取、合取、否定的定義，只要不歉麻煩，幾乎可推出所有的結(jié)論。 為了提高推理效率，還需要學(xué)習(xí)、掌握某些推理規(guī)則。,例題 求證 A?A?B 采用定義1來(lái)證明，即證明A?A?B為永真式。 A?A?B ??A?(A?B) (?的等值式) ?(?A?A)?B (結(jié)合律) ?1?B (析取的性質(zhì)) ?1 (析取的性質(zhì)) 所以A?A?B,例題 求證 A?B?A A?B?A ??(A?B)?A (?的等值式) ?(?A??B)?A (德摩律) ??A??B?A (結(jié)合律) ?1??B (析取的性質(zhì)) ?1 (析取的性質(zhì)) 類(lèi)似 A?B?B 根據(jù)?的定義可知A?B為真時(shí)，A與B均為真，因此由推理定義2可知 A?B?A， A?B? B 。 同樣由?的定義可知A為真時(shí) A?B為真，故由推理定義2可知A?A?B。 然這3個(gè)推理式不必記憶！推理定義2效率較高,例題 求證 (A?B)?(B?C)?(A?C) 根據(jù)定義1，要證明下式為永真式。 (A?B)?(B?C) ? (A?C) ??((A?B)?(B?C)) ?(A?C) (?的等值式) ??((?A?B)?( ?B?C)) ?(?A?C) (?的等值式) ?((A??B) ? (B??C)) ?(?A?C) (德摩律) ?((A? B)?(A? ?C )?(?B ? B) ?(?B??C)) ?(?A?C) (分配律) ?((A? B)?(A? ?C )?1?(?B??C)) ?(?A?C) (析取的性質(zhì)) ?((A? B)?(A? ?C )?(?B??C)) ?(?A?C) (析取的性質(zhì)) ?(A? B??A?C)?(A? ?C??A?C )?(?B??C??A?C) (分配律) ?(1? B?C)?(1? ?C?C )?(?B??A?1) (析取的性質(zhì)) ?1?1?1 (析取的性質(zhì)) ?1 (析取的性質(zhì)) 判斷公式的類(lèi)型，除等值演算外，還有真值表與范式等方法。,例題 求證 (A?B)?(B?C)?(A?C),由上表可知， (A?B)?(B?C) ? (A?C) 為重言式， 由定義1可知(A?B)?(B?C)? (A?C)。 這是有名的傳遞律，要記住呀！,例題 求證 (A?B)?(C?D)?(A?C)?B?D 利用定義1證明了假言推理規(guī)則(A?B)?A?B,傳遞規(guī)則(A?B)?(B?C)?(A?C)。 有了這2條規(guī)則后,可用定義2來(lái)證明推理式了。 由于這2條規(guī)則的結(jié)論中沒(méi)有析取式，只有條件式，因此將題中結(jié)論?轉(zhuǎn)換為? B?D,題設(shè)中?轉(zhuǎn)換為? (1)(A?B)?(C?D)?(A?C)為真 前提條件(定義2的套路) (2) (A?B)為真 (1)及合取的性質(zhì) (3) (C?D)為真 (1)及合取的性質(zhì) (4) (A?C)為真 (1)及合取的性質(zhì) (5)(?B??A)為真 (2)及(A?B)? (?B??A) (6) (?A?C)為真 (4)及(A?C) ?(?A?C) (7) (?B?C)為真 (5)、(6)及推理傳遞律 (8) (?B?D)為真 (7)、(3)及推理傳遞律 (9) B?D為真 (8)及(?B?D) ?B?D,例題 求證 (A?B)?(C?D)?(?B??D)?A??C 可用傳遞律來(lái)證明，還有更高效的方法 由定義1只要證((A?B)?(C?D)?(?B??D))?(A??C)為重言式，而 ((A?B)?(C?D)?(?B??D))?(A??C) ??((A?B)?(C?D)?(?B??D))? (?A??C) ?(? ((A?B)?(C?D)?(?B??D))??A)??C) ??((A?B)?(C?D)?(?B??D))?A)??C) ?((A?B)?(C?D)?(?B??D))?A)??C 故只需證 ((A?B)?(C?D)?(?B??D))?A)??C為重言式 即只需證明(A?B)?(C?D)?(?B??D))?A??C A從結(jié)論中挪到前提中，這種技巧稱(chēng)為附加條件(CP)法，適合于結(jié)論為條件式的情形。,例題 求證 (A?B)?(C?D)?(?B??D)?A??C (1)(A?B)?(C?D)?(?B??D)?A為真 CP規(guī)則及前提 (2)A?B為真 (1)及合取的性質(zhì) (3)A為真 (1)及合取的性質(zhì) (4)B為真 (2)(3)及假言推理式(A?B)?A?B (5)?B??D為真 (1)及合取的性質(zhì) (6)B??D為真 (5)及?B??D?B??D (7)?D為真 (4)(6)及假言推理式(B??D)?B??D (8)C?D為真 (1)及合取的性質(zhì) (9)?D??C為真 (8)及原命題?逆否命題 (10)?C為真 (7)(9)假言推理式(?D??C)??D??C 提示：熟練后可不寫(xiě)(1)式，直接引用(2)(3)(5)(8)！,例題 求證 (A?B)?(C?D)?(?B??D)?A??C (1)A?B為真 前提條件 (2)A為真 附加前提 (3)B為真 (1)(2)及假言推理式(A?B)?A?B (4)?B??D為真 前提條件 (5)B??D為真 (4)及?B??D?B??D (6)?D為真 (3)(5)及假言推理式(B??D)?B??D (7)C?D為真 前提條件 (8)?D??C為真 (7)及原命題?逆否命題 (9)?C為真 (6)(8)假言推理式(?D??C)??D??C,求證 (W?R)?V, V?(C?S),S?U,?C,?U??W 提示：此處用逗號(hào)簡(jiǎn)寫(xiě)前述各例中的合取式，從而鼓勵(lì)大家直接引用前提。 利用假言推理、傳遞律及前面所學(xué)的等值式，可以推出結(jié)論。在黑板上演示一番 考慮到本題的結(jié)論是?W，可采用反證法。 根據(jù)定義2可知“當(dāng)前提為真時(shí)結(jié)論也為真”， 反證法是“前提為真時(shí)，假設(shè)結(jié)論不為真即結(jié)論的否定為真”。 即基于前提、結(jié)論否定進(jìn)行推理。 如果推出了一個(gè)矛盾的結(jié)論出來(lái)，則說(shuō)明“假設(shè)結(jié)論不為真”是錯(cuò)誤的，即表示結(jié)論只能為真了,求證 (W?R)?V, V?(C?S),S?U,?C,?U??W (1)??W為真 假設(shè)結(jié)論?W為0即? ? W為1(真) (2)W為真 (1)與否定的性質(zhì) (3)(W?R)為真 (2)與析取的性質(zhì) (4)(W?R)?V為真 前提條件 (5)V為真 (4)(3)假言推理((W?R)?V)?(W?R)? V (6)V?(C?S)為真 前提條件 (7) (C?S)為真 (5)(6)假言推理(V?(C?S))?V?(C?S) (8) ?C?S為真 (7)與條件式的等值式C?S??C?S (9)?C為真 前提條件 (10)S為真 (8)(9)與假言推理(?C?S)?( ?C)?S (11) S?U為真 前提條件 (12)U為真 (10)(11)假言推理(S?U)?S?U (13) ?U為真 前提條件 顯然(12)與(13)矛盾，故假設(shè)有誤！,應(yīng)用題 天氣情況要么天晴，要么天下雨；如果天晴我去爬山，如果我去爬山那么我回來(lái)后不做飯， 結(jié)論是：如果我已做飯那么肯定天下雨了。 解：用M表示天晴， R表示天下雨， C表示爬山， F表示做飯，則問(wèn)題可表示為 M?R，M?C，C??F?F?R (M??R)?(?M?R) ，M?C，C??F?F?R,應(yīng)用題M?R，M?C，C??F?F?R (1)F為真 附件前提 (2)C??F為真 前提條件 (3)??F??C為真 (2)的等值式 (4) F??C為真 (3)的等值式 (5) ?C為真 (1)(4)的假言推理 (6) M?C為真 前提條件 (7)?C??M為真 (6)的等值式 (8) ?M為真 (5)(7)的假言推理 (9) M?R為真 前提條件 (10) ?M?R為真 (9)的等值式 (11) R為真 (8)(10)的假言推理,應(yīng)用題M?R，M?C，C??F?F?R (1)F為真 附件前提 (2)C??F為真 前提條件 (3)??F??C為真 (2)的等值式 (4) F??C為真 (3)的等值式 (5) ?C為真 (1)(4)的假言推理 (6) M?C為真 前提條件 (7)?C??M為真 (6)的等值式 (8) ?M為真 (5)(7)的假言推理 (9) (M??R)?(?M?R)為真 前提條件 (10) ? (M??R) ? (?M?R)為真 (9)的等值式 (11) ? M?R ? (?M?R)為真 (10)的等值式 (12) ? M?R為真 (8)與析取的定義 (13) (?M?R)為真 (11)(12)的假言推理 (14) R為真 (13)與合取的定義,定義2證明推理式的規(guī)律 (1)利用“條件等值式”，盡可能將前提、中間結(jié)論及最終結(jié)論中的“析取式”轉(zhuǎn)換為“條件式”，以便可引用假言推理、傳遞律。 (2)如果結(jié)論為條件式，則將條件式的前件做為附加前提。CP原則 (3)如果結(jié)論的否定在前提中多次出現(xiàn)，可采 用反證法。 (4)每一步的推理理由可簡(jiǎn)化，如“前提條件”簡(jiǎn)寫(xiě)為“P”，“假言推理”可簡(jiǎn)寫(xiě)“M”，等值式只寫(xiě)“等值”或簡(jiǎn)寫(xiě)“E”。 (5)這種從前提出發(fā)，應(yīng)用已證明的推理式，不斷推出中間結(jié)論，最后推出結(jié)論的方式，稱(chēng)為自然推理，這是最常見(jiàn)的方式。,1.7消解規(guī)則 證明(A?C)?(B??C)?A?B (1) (A?C)為真 前提條件 (2) ?A? C為真 與(1)等值 (3) B??C為真 前提條件 (4) ?C? B為真 與(3)等值 (5)C?B為真 與(4)等值 (6) ?A?B為真 (2)(5)傳遞律 (7) A?B為真 與(6)等值 因此當(dāng)(A?C)?(B??C)為真時(shí)，A?B為真。 由于(A?C?(B??C)中互補(bǔ)的公式C、?C同時(shí)消失了，稱(chēng)“A?B”為 “(A?C)，(B??C)”的消解式。 因此在采用定義2進(jìn)行推理時(shí)，只要(A?C)、(B??C)同時(shí)為真，則可直接寫(xiě)出A?B為真，從而節(jié)省大量的中間環(huán)節(jié)，提高了證明效率。,1.7消解規(guī)則 例題 (A?B)?(C?D)?(?B??D)?A??C 利用條件式的等值式，則此題等價(jià)于證明 (?A?B)?(?C?D)?(?B??D)??A??C (1) (?A?B)為真 前提條件 (2) (?B??D)為真 前提條件 (3) ?A??D為真 當(dāng)(1)(2)為真消解式?A??D為真 (4) ?C?D為真 前提條件 (5) ?A??C為真 當(dāng)(3)(4)為真消解式?A??C為真 采用假言推理原則時(shí)，盡可能將析取轉(zhuǎn)換為條件式。 采用消解法時(shí)，盡可能將條件式轉(zhuǎn)換為析取。 消解法是一種高效的方法。 消解法可完成1.6節(jié)中所有推理式,1.7消解規(guī)則 采用定傳遞律證明了(A?C)?(B??C)?A?B 因A?B? ?A?B,故可用假言推理及CP原則證明 (1) ?A為真 附加前提 (2) (A?C)為真 前提條件 (3) ?A? C為真 與(1)等值 (4) C為真 (1)(3)假言推理 (5) B ? ?C 為真 前提條件 (6)C?B為真 與(4)等值 (7) B為真 (4)(6)假言推理 用假言推理證明了消解規(guī)則，反過(guò)來(lái) 用消解規(guī)則可證明假言推理,1.7消解規(guī)則 用假言推理證明了消解規(guī)則證明了 (A?C)?(B??C)?A?B 反過(guò)來(lái)，用消解規(guī)則可證明假言推理 A?(A?B)?B A?B為真 前提條件 ?A ?B為真 與(1)等值 A為真 前提條件 B為真 (2)(3)消解得到 “假言推理”與“消解規(guī)則”可以互相推出，因此一方推出的結(jié)論另一方也可以推出 因此習(xí)題三可由消解規(guī)則推導(dǎo)出來(lái)呀,