第四章推理技術(shù)

4.1一階謂詞邏輯推理4.2歸結(jié)演繹推理推理技術(shù)概述推理是人類求解問題的主要思維方法，即按照某種策略從已有事實(shí)和知識(shí)推出結(jié)論的過程。按思維方式可分演繹推理、歸納推理、類比推理等。邏輯推理：按邏輯規(guī)則進(jìn)行的推理。分為：

經(jīng)典邏輯推理

:主要指命題邏輯和一階謂詞邏輯推理，也稱精確推理或確定性推理；

非經(jīng)典邏輯推理：主要指除經(jīng)典邏輯之外，按多值邏輯、模糊邏輯、概率邏輯等的推理，也稱為非精確推理或非確定性推理。邏輯推理舉例

經(jīng)典推理：蘇格拉底之死

如何判別謊言？

ABC三人都喜歡說謊話，偶爾也說真話。某天，A指責(zé)B說謊話，B指責(zé)C說謊話，C說AB兩人都在說謊話。問誰在說謊？

有幾條瘋狗？

村里有50戶人家，每家都養(yǎng)了一條狗。現(xiàn)發(fā)現(xiàn)村子里面出現(xiàn)了n只瘋狗，村里規(guī)定，誰要是發(fā)現(xiàn)了自己的狗是瘋狗，就要將自己的狗槍斃。但問題是，村子里面的人只能看出別人家的狗是不是瘋狗，而不能看出自己的狗是不是瘋的，如果看出別人家的狗是瘋狗，也不能告訴別人。于是大家開始觀察，第一天晚上，沒有槍聲，第二天晚上，沒有槍聲，第三天晚上，槍聲響起（具體幾槍不清楚），問村子里有幾只瘋狗？只有晚上才能看出病狗，并且一天晚上只能看一次。愛因斯坦的世界難題（1）愛因斯坦在20世紀(jì)初出一個(gè)謎語。他說世界上有98％的人答不出來。1、在一條街上，有5座房子，噴了5種顏色；2、每個(gè)房里住著不同國(guó)籍的人；3、每個(gè)人喝不同的飲料，抽不同品牌的香煙，養(yǎng)不同的寵物。

問題是：誰養(yǎng)魚？

愛因斯坦的世界難題（2）條件是：1、英國(guó)人住紅色房子； 2、瑞典人養(yǎng)狗；3、丹麥人喝茶； 4、綠色房子在白色房子左面；5、綠色房子主人喝咖啡；6、抽PallMall香煙的人養(yǎng)鳥；7、黃色房子主人抽Dunhill香煙；8、住在中間房子的人喝牛奶；9、挪威人住第一間房； 10、抽Blends香煙的人住在養(yǎng)貓的人隔壁11、養(yǎng)馬的人住抽Dunhill香煙的人隔壁；12、抽BlueMaster的人喝??；13、德國(guó)人抽Prince香煙； 14、挪威人住藍(lán)色房子隔壁；15、抽Blends香煙的人有一個(gè)喝水的鄰居。邏輯學(xué)與計(jì)算機(jī)科學(xué)邏輯學(xué)：研究思維規(guī)律的科學(xué)計(jì)算機(jī)科學(xué)：模擬人腦行為和功能（思維）的科學(xué)思維：大腦、邏輯、語言、計(jì)算機(jī)邏輯是知識(shí)表示和推理的重要形式和工具8邏輯的歷史Aristotle——邏輯學(xué)Leibnitz——數(shù)理邏輯：邏輯+數(shù)學(xué)GottlobFrege(1848-1925)——一階謂詞演算系統(tǒng)邏輯是探索、闡述和確立有效推理原則的學(xué)科，最早由古希臘學(xué)者亞里士多德創(chuàng)建的。用數(shù)學(xué)的方法研究關(guān)于推理、證明等問題的學(xué)科就叫做數(shù)理邏輯。也叫做符號(hào)邏輯。20世紀(jì)30年代，數(shù)理邏輯廣泛發(fā)展，成為數(shù)學(xué)和計(jì)算機(jī)科學(xué)基礎(chǔ)。邏輯系統(tǒng)一個(gè)邏輯系統(tǒng)是定義語言和它的含義的方法。邏輯系統(tǒng)中的一個(gè)邏輯理論是該邏輯的語言的一個(gè)語句集合，它包括：邏輯符號(hào)集合：在所有該邏輯的邏輯理論中均出現(xiàn)的符號(hào)；非邏輯符號(hào)集合：不同的邏輯理論中出現(xiàn)的不同的符號(hào)；語句規(guī)則：定義什么樣的符號(hào)串是有意義的；證明：什么樣的符號(hào)串是一個(gè)合理的證明；語義規(guī)則：定義符號(hào)串的語義。邏輯程序語言邏輯符號(hào)保留字或者符號(hào)非邏輯符號(hào)用戶自定義的符號(hào)(變量名，函數(shù)名等)語句規(guī)則構(gòu)造一個(gè)程序的語句規(guī)則語義規(guī)則定義程序做什么的語句規(guī)則推理規(guī)則、公理和證明沒有邏輯與程序語言的對(duì)比1.3命題邏輯命題：可以確定其真假的陳述句。Bolle提出了布爾代數(shù)。語言:原子Q、否定?、吸取V、合取、蘊(yùn)含、等價(jià)<->公式：AV?B，(AB,A)=>?

公司招聘工作人員，有M,N,Q三人應(yīng)聘，經(jīng)面試后，公司表示如下想法：（1）三人中至少錄取一人;（2）如果錄取M,則一定錄取N；（3）如果錄取N,則一定錄取Q。結(jié)果如何？1.4謂詞邏輯(一階邏輯)謂詞邏輯是一種形式語言，具有嚴(yán)密的理論體系，也是一種常用的知識(shí)表示方法。語言:

?，，，，(，)；常元，變?cè)?，函詞，謂詞；公式City（北京）City（上海）Age（張三，23）(x)(y)(z)(F(x,y)F(y,z)GF(x,z)）謂詞楚邏輯巾中的脊形式開演繹急推理將自友然語附言中拒的陳昌述語悉句利用圓謂詞仿公式絕表示利用附邏輯舅等價(jià)浙式將謂膚詞公逃式進(jìn)勢(shì)行變究換利用號(hào)邏輯洞蘊(yùn)含瞎式推出饞結(jié)論符號(hào)飯化過濁程公式報(bào)變形推理半過程表4.脹1常用刊邏輯或等價(jià)土式表4.嗽2常用洲邏輯迅蘊(yùn)含醬式設(shè)有劫前提廳：(1晶)凡是湊大學(xué)揭生都裳學(xué)過漠計(jì)算行機(jī)；(2壟)小王但是大輩學(xué)生命。試問川：小摔王學(xué)裂過計(jì)鞭算機(jī)努嗎？解令S(元x)：x是大泰學(xué)生;M(毀x)：x學(xué)過賣計(jì)算道機(jī);a：小融王。則上正面的滅兩個(gè)莫命題允可用從謂詞冤公式階表示閱為(1映)允x諒(S肚(x悲)→莖M(處x)統(tǒng))(2懲)候S(醋a)例下面腸我們垮進(jìn)行換形式真推理妹：(1雖)巾x(應(yīng)S(銅x)晃→M薦(x銅))［前搭提］(2匆)S撿(a吸)→枕M(侍a)［(1勵(lì)),乏US］(3以)S投(a僅)［前率提］(4軋)M綱(a賀)［(2葛),南(3瞎),I3］得結(jié)咸果：M(州a)，即圈“小辦王學(xué)棉過計(jì)睛算機(jī)饒”。這種樂推理播過程昏完全蒼是一敘種符襪號(hào)變?cè)畵Q過玻程，勾很類癢似于綁人們棵用自頁然語洲言推安理的容思維龜過程畢，因閉而稱厘為自然陷演繹波推理在語閱法上臉，如衣果存去在一裹個(gè)從們假設(shè)到的證純明，則記跌為?，稱由可推濟(jì)導(dǎo)出偶的，暮或可證棋明的。鍵如果零在沒觀有任濱何假智設(shè)下是可春推導(dǎo)耀出的多，則應(yīng)記為?，稱為可顆證明壺的。稱一匹個(gè)假薪設(shè)是不協(xié)逝調(diào)的，如耐果存殃在一刺個(gè)語婦句使得和的否心定均蔥可由推導(dǎo)盯得出楚。稱一嚇個(gè)邏返輯系素統(tǒng)是一致補(bǔ)的，或相容恒的(co郵ns沿is悼te剃nt隱)，如果模不存健在邏內(nèi)輯系蕩統(tǒng)的層公式A，使看得?A與??A同時(shí)光成立。證宰明(語法)語言孔的解釋是在綠某個(gè)生論域(d江om峰ai掠n)中定怪義非搶邏輯符號(hào)表。語拒句的表語義廚是在削解釋禍下定們義出勢(shì)語言L的真糟假值瘡。懼如果I是L的一捎個(gè)解款釋，利且在I中為晴真，厭則記礙為I?，稱屢作I滿足，或蘿者I是的一雜個(gè)模型。類似碼地，貪給定取一個(gè)吵語句和一延個(gè)語哀句，如孔果對(duì)每個(gè)舟解釋I，有I?蘊(yùn)含I?，換口言之牛，如按果I是的一購(gòu)個(gè)模怕型則I也是的一荒個(gè)模接型，玻則記攀為?，我們稱為的一獄個(gè)邏輯童結(jié)果。解放釋(語義)可靠協(xié)性(r叉el謠ia臥bl謹(jǐn)e)語法->語義一個(gè)床邏輯寬是可率靠的梨，如露果它隨的證啟明保慈持真豆假值吹，即在體任何偶解釋I下，壁如果I是的模葛型，菜且可由推導(dǎo)出，故則I也是的一鼠個(gè)模粉型。慈即，紅一個(gè)膚邏輯收是可黑靠的傭，如果告對(duì)任溪何語灣句集貓合和語恩句，?蘊(yùn)涵??？煽魁斝院兔⑼陚浼~奉性完備窯性(c眉o(jì)m筑pl喚et饅e)語義->語法一個(gè)劫邏輯蠟是完逝備的侮，如綠果任圓何永旗真語顯句是慘可證括的。即，獎(jiǎng)對(duì)任慘何語隨句集播合和語褲句，?蘊(yùn)涵?。如果見一個(gè)貢邏輯針是完艦備的俊，則培該邏駛輯的全證明的系統(tǒng)擾已強(qiáng)睜到可以朱推出拔任何胳永真今式。G?de澡l完備除性定去理：一階器邏輯晚是完隙備的可判蠢定的一個(gè)薯邏輯驚稱為衣是可判謊定的(d蜓ec鋤id墳ab綠le暢)，如槍果存留在一個(gè)徹算法砍對(duì)邏械輯中割的任嫁一公旱式A，可漸確定?A是否限成立。貪否則治，稱袋為是不可揪判定裕的(u貪nd雷ec纏id拐ab醬le替)。如果輛上述肉算法蛙雖不今一定愉存在餃，卻追有一刻個(gè)過棉程，責(zé)可對(duì)奏該系糠統(tǒng)的啄定理滋做出橋肯定察的判礙斷，尿但對(duì)集非定紙理的仙公式骨過程唱未必夕終止梳，因遮而未駕必能畝作出暈判斷語。這秩時(shí)稱效邏輯熱是半可千判定轎的?？膳衅范ㄐ砸浑A捆邏輯魂是不磚可判仁定的景，但畏它是何半可鄉(xiāng)豐判定功的?，F(xiàn)代鑒邏輯四學(xué)與距計(jì)算課機(jī)科似學(xué)、狠計(jì)算宣語言寄學(xué)和聽人工燭智能跑的關(guān)血系表邏遙輯艙自然略語禾程序失人肆工虎邏輯脈指旦令與傻直萌數(shù)據(jù)耕庫五復(fù)雜車性鈴智能片體敵未崖來寇展馬望言處劑理適控制翅智商能脾編程初陳怕式語告言瓣理畝論芳理論皺理終論時(shí)序伐邏輯典√錄√壓√貢√菊√包√隆√藍(lán)√耀廣顯泛應(yīng)已用模態(tài)梯邏輯腸√桐√出√虹√尾√杠√傳√首√笑非怎?；蠲S算法瘋證明針√浪√失√長(zhǎng)√聽√遵√繩√捐√非單貨調(diào)推蠻理眉√猛√勇√羞√屯√午√喂√宣意士義重裕大概率煩和模烈糊腐√天√魂√褲√摩√簽√宵√紹目姥前主淺流直覺校主義攝邏輯男√秩√造√華√煎√難√迷√瘋√私主窯要替敞代者高階梢邏輯秀，λ-演算塵√利√還√框√督√企√梳更具徒中心畫作用經(jīng)典乏邏輯擇片斷蝦√兼√民√診√扶√堆√船前透景誘觀人資源城和子投結(jié)構(gòu)半邏輯燭√診√蒸√險(xiǎn)√纖維纏化和驚組合乎邏輯疤√令√并√桂√毀√泛√皂可濫自我騎指稱謬誤藥理論設(shè)在塑適當(dāng)級(jí)語境邏輯摟動(dòng)力比學(xué)嚇√器√肝動(dòng)態(tài)需邏輯這觀論辯途理論圾游戲燥√禮前景摧光明對(duì)象狹層次/元層輪次雙√貧√庭總魂起中療心作策用機(jī)制:溯因揚(yáng)缺詠省湊相干嫌√留√古邏輯殿的一相部分與神料經(jīng)網(wǎng)型絡(luò)的活聯(lián)系輸極軋重要脅，剛皮開始時(shí)間-行動(dòng)-修正摔模型盾√乏√李一妥類新堡模型加標(biāo)換演繹溪系統(tǒng)擔(dān)√騾√滑√呀√濁√腫邏輯幟學(xué)的普統(tǒng)一哨框架4.映2歸結(jié)織演繹捐推理歸結(jié)旁演繹禽推理瞎是基壇于一屯種稱鋸為歸站結(jié)原熟理(亦稱消解蘇原理pr養(yǎng)in栗ci葵pl跑e撤of討r繁es恥ol碑ut伐io悲n)的推母理規(guī)堵則的熊推理記方法談。歸結(jié)滾原理嶼是由度魯濱堅(jiān)遜(J藍(lán).A牙.R湯ob甲in材so飛n)于19稱65年首讓先提肯出。因它是摧謂詞添邏輯伙的一淚個(gè)相器當(dāng)有夕效的沉機(jī)械留化推紹理方注法。歸結(jié)霉原理捆的出鋤現(xiàn)，險(xiǎn)被認(rèn)妹為是計(jì)自動(dòng)咳推理稈，特波別是愁定理枯機(jī)器頓證明沿領(lǐng)域揭的重喘大突磁破。給從理清論上制解決吃了定個(gè)理證仰明問屢題。有關(guān)紫歸結(jié)彩演繹姓推理蔬的定欲義文字子句空子宣句子句麥集Sk申ol偶em函數(shù)Sk喬ol評(píng)em常量互補(bǔ)涉文字歸結(jié)，又此稱消解(r冊(cè)es路ol綢ut鋸io狐n)定義1原子川謂詞鋸公式員及其禽否定框稱為文字，若干薪個(gè)文因字的額一個(gè)味析取鼓式稱禽為一移個(gè)子句不含經(jīng)任何股文字桂的子籮句稱講為空子蒜句（零真值奪為假屢），記克為NI奇L。例如怕下面師的析沿取式她都是呢子句P∨蜓Q∨乛RP(引x,負(fù)y)嫌∨乛Q(震x)定義2對(duì)一起個(gè)謂臺(tái)詞公店式G，通宏過以扛下步異驟所評(píng)得的痰子句魚集合S，稱悉為G的子句妄集。(1翠)消去緣瑞蘊(yùn)含孤詞→炒和等砍值詞暫←→狹?？缮晔褂昧w邏輯矛等價(jià)鋸式:①A聞→B乛A∨社B②A心←雜→B蘭(乛A∨英B)艇∧(乛B∨塔A)(2甚)縮小蒼否定侍詞的鴉作用介范圍戰(zhàn)，直汽到其妨僅作追用于擺原子啄公式后。可爪使用喉邏輯櫻等價(jià)鈔式:①乛(乛A)芳A②乛(A賣∧B德)乛A∨乛B將一雄個(gè)謂籌詞公角式轉(zhuǎn)黎換為臥子句傍集③乛(A勵(lì)∨B襯)乛A∧乛B④乛xP栽(x銷)巧x乛P(蚊x)⑤乛xP激(x金)京x乛P(乒x)(3協(xié))適當(dāng)倡改名益，使訴量詞黑間不淹含同莊名自脖由變位元和屆約束粘變?cè)x。(4靠)消去眾存在塊量詞政。消去易存在槳量詞霧時(shí)，竄同時(shí)遲還要榮進(jìn)行暴變?cè)鎿Q能。變柱元替訓(xùn)換分棵兩種嫩情況絮：①若潑該存復(fù)在量亭詞在址某些燈全稱綠量詞絞的轄淋域內(nèi)大，則閑用這鴿些全碑稱量調(diào)詞指蓄導(dǎo)變臂元的奏一個(gè)口函數(shù)手代替蒜該存罰在量強(qiáng)詞轄診域中包的相搶應(yīng)約濃束變豆元，窮這樣柴的函督數(shù)稱囑為Sk墓ol炊em函數(shù)塑；②若該白存在涉量詞莖不在辦任何住全稱倍量詞油的轄倆域內(nèi)緩，則遞用一歲個(gè)常撞量符奔號(hào)代釣替該擔(dān)存在艇量詞朗轄域于中的枝相應(yīng)茄約束鳴變?cè)?，這原樣的蘿常量嫂符號(hào)常稱為Sk涼ol技em常量。x床y蜂P(勻x,配y)根據(jù)附步驟4轉(zhuǎn)換仰為x棚P(急x,辛g(侵x)姻)這里y=削g(棍x)為Sk虧ol被em函數(shù)。xP井(x碎)根據(jù)拼步驟4轉(zhuǎn)換脂為P(材a)句,這里a為Sk賤ol淺em常量Sk臭ol旺em函數(shù)勝舉例(5子)消去察所有燥全稱濤量詞監(jiān)。(6洋)化公靈式為冤合取腸范式災(zāi)。可使?jié)灿眠壚演嫷却矁r(jià)式:①A暈∨(館B∧例C)鑒(A裝∨B悼)∧隸(A族∨C穗)②(嘉A∧注B)鎖∨C籮(炭A∨泊C)泛∧(此B∨跌C)(7流)適當(dāng)狹改名苦，使妄子句男間無魄同名援變?cè)谩?8腦)消去居合取些詞∧尸，以嶼子句嗽為元故素組礦成一預(yù)個(gè)集宴合S。(AB)(CD)1.消去(AB)(CD)轉(zhuǎn)換轉(zhuǎn)子句亡集舉紋例(AB)(CD)1.消去(AB)(CD)2.縮減作用衡范圍(AB)(CD)轉(zhuǎn)換豆子句吵集舉父例(AB)(CD)1.消去(AB)(CD)2.縮減作用愿范圍(AB)(CD)3.化公訴式為攜合取錫范式(A(CD)漫)(B(CD)緞)(AC)(AD)(BC)(BD)轉(zhuǎn)換禿子句云集舉鞠例(AB)(CD)1.消去(AB)(CD)2.縮減作用舊范圍(AB)(CD)3.化公遇式為廉合取游范式(A(CD)艷)(B(CD)刮)(AC)(AD)(BC)(BD)子句時(shí)集:{AC,AD沈,爺BC節(jié),閣BD}謂詞興公式氏轉(zhuǎn)換欣子句憤集舉滔例定義3：若P是原煤子謂珍詞公的式，芳則P與乛P為互補(bǔ)男文字定義4：設(shè)C1與C2是子更句集透中的賽任意唐兩個(gè)際基子眠句，下如果C1中的濟(jì)文字L1與C2中的燥文字L2互補(bǔ)討，那喚么C1和C2中分陡別消忌去L1和L2，并堂將兩凱個(gè)子亭句余陳下的創(chuàng)部分認(rèn)析取音，構(gòu)幣成一廉個(gè)新繡子句C12，則繞稱此步過程肝為歸結(jié)逆，又桂稱消行解（re姜so蟲lu排ti錦on）。稱C12為基然子句C1和C2的歸結(jié)北式。稱C1和C2為C12的親本仔子句。例3.示9設(shè)C1=乛P∨紀(jì)Q∨惕R,尤C2=乛Q∨親S,于是C1,C2的歸但結(jié)式聽為乛P∨草R∨辰S歸結(jié)油（消厭解）沸定義子句碎集的哭特點(diǎn)由謂擠詞公賴式轉(zhuǎn)挎化為呈子句蛋集的伯過程樓中可挪以看類出，倆在子旅句集擦中子床句之蹄間是馳合取鋸關(guān)系猶。其中讓只要奪有一敞個(gè)子倉句不逮可滿偷足(真值深為假兵），怨則子止句集腔就不薯可滿銳足。若一冤個(gè)子填句集產(chǎn)中包蕩含空析子句般，則瞞這個(gè)龜子句帳集一霞定是途不可肥滿足渾的。由歸次結(jié)原瓶理可瘋知：如果掀兩個(gè)爪互否陶的單域元子蠅句進(jìn)齊行歸朝結(jié)，惱則歸游結(jié)式煉為空唯子句即:L?L繡=須□同時(shí)弱，L?L大=赴F(假）因此牲□F因此調(diào)，可即以通造過推盼導(dǎo)空挖子句顆來做質(zhì)間接屬證明銷。一旦里推出秧了空鉗子句螺，就者說明丟子句惱集S是不腔可滿遇足的歸結(jié)闊反演毯證明仰步驟第一事步：因化子五句集（1）將歪定理談證明林的前用提謂污詞公轟式轉(zhuǎn)恥換為責(zé)子句芳集F(2驅(qū))將要紡求證宗明的省目標(biāo)淺表示稀成謂者詞公勒式G(目標(biāo)鉗公式案）（3）將丈目標(biāo)駛公式忠的否定遇式乛G轉(zhuǎn)化酸成子咱句的濕形式杏，并餡加入照到子胃句集F,得到動(dòng)子句辮集S。第二什步：燦歸結(jié)堂反演應(yīng)用御歸結(jié)胸原理賭對(duì)子首句集S中的竹子句研進(jìn)行驗(yàn)歸結(jié)床，并通把每逼次歸灑結(jié)的變歸結(jié)柱式都憲并入象到S中。棋如此笨反復(fù)栗進(jìn)行境，若濕歸結(jié)客得到醉一個(gè)衛(wèi)空子爆句NI券L，則躺停止倘歸結(jié)命，此鎮(zhèn)時(shí)證習(xí)明了G為真晌。歸結(jié)欣原理去證明換定理李思路用歸子結(jié)原當(dāng)理證焦明定愁理有倒些類鄙似于舒“反看證法卵”的誘思想訊。反證手法：首先岸假定蠅要證敢明的轉(zhuǎn)結(jié)論肢不成傍立然后島通過漿推導(dǎo)淋出與尖已知?dú)l件票存在棍矛盾反證浸出結(jié)正論成機(jī)立。歸結(jié)服法：首先在對(duì)結(jié)畝論求沾反，然后藍(lán)將已替知條取件和糞結(jié)論竿的否嗚定合諸在一帆起用子丸句怖集表鍬達(dá)。如果鴉該子權(quán)句集稠存在思矛盾嗎，則閣證明返了結(jié)步論的正確銅性。2．命各題邏嚼輯的昆歸結(jié)命題綁邏輯，簡(jiǎn)倘單的俊說，金就是弓不含勢(shì)有變猾量的駝邏輯盜。歸結(jié)紛式：對(duì)暗任意懼兩個(gè)啊子句C1和C2，若C1中有糧一個(gè)痛文字L1，而C2中有貌一個(gè)糠與L1成互雙補(bǔ)的污文字L2，則趴分別秋從C1、C2中刪隆去L1和L2，并手將其施剩余扔部分脆組成典新的墻析取儉式C1治2，則鐮稱這坊個(gè)新已子句總為歸哈結(jié)式下或預(yù)息解式霸。命題抱邏輯妥的歸法結(jié)過莖程命題帽邏輯堅(jiān)中，疊若給軟定公高理集F和命滿題P，則米歸結(jié)全證明疤過程歷可歸貸納如戴下：財(cái)①假把F轉(zhuǎn)化云成子床句集謀表示膜，得談子句始集S0；利②把聽命題P的否牌定式~P也轉(zhuǎn)云化成棉子句倆集表術(shù)示，溫并將區(qū)其加旱到S0中，購(gòu)得S＝S0∪{晨S~蹲p}；剪③對(duì)貞子句捆集S反復(fù)漸應(yīng)用嘴歸結(jié)呢推理歪規(guī)則特，直陰至導(dǎo)將出含躬有空熱子句拘的擴(kuò)省大子猛句集徹為止神。即伸出現(xiàn)愉歸結(jié)臘式為體空子請(qǐng)句的化情況地時(shí)，搏表明狐已找衛(wèi)到了循矛盾冠，證貢明過咽程結(jié)降束。例字證撈明子寺句集{P漸∨乛Q,乛P,彈Q}是不寄可滿圣足的企。證(1機(jī))P兄∨乛Q(2著)乛P(3掃)Q(4覽)乛Q由(1壟),蠶(2慢)(5虧)□由(3役),深(4齡)基于什命題墳邏輯日的歸舊結(jié)舉伐例P∨乛Q乛P乛QQ□例曲用歸扛結(jié)原線理證泊明R是P,殼(P藍(lán)∧Q箱)→散R,國(guó)(殖S∨捐U)屑→Q燒,六U的邏吉輯結(jié)繳果。證明絕步驟第一朝步將堤問題蠅轉(zhuǎn)換添為子設(shè)句集蜜。我們望先把員諸前奧提條葉件化味為子顛句形陷式，采再把抵結(jié)論R的非羽乛R也化鳳為子毛句，濫由所該有子液句得棕到子躬句集S將P,臺(tái)(運(yùn)P∧欣Q)花→R漫,荷(S氧∨U汪)→早Q,破U化為遍子句眉集形束式：(P滅∧Q華)→隸R乛(P匹∧Q佩)夠∨R(乛P羊∨乛Q)龜∨壺R乛P留∨乛Q∨童R(S倉∨U果)→壯Q(1片)乛(S夕∨腹U)譯∨徒Q(2品)絕(乛S飄∧乛U)繡∨捧Q(3畜)昏(乛S∨擇Q)知∧羨(乛U∨臨Q)子句辰集：{P嶺,乛P或∨乛Q∨帆R,乛S∨細(xì)Q棋,乛U∨使Q,蟻U較,乛R}第二計(jì)步：別然后中對(duì)該洲子句束集S進(jìn)行約歸結(jié)例。如果礦從子案句集S最后邪歸結(jié)松出空剖子句轎，則腹子句能集S不可縫滿足團(tuán)，從污而間蜜接證左明R是真辯。P乛P∨乛Q∨美R乛S∨飽Q乛U∨究QU乛R乛P諸∨乛Q條(渠2)和（6）乛Q莊(渣1)和（7）乛U繞(摧4)和(8抵)□通(5小)和(9刪)子句介集圖3―稼1例3.遼12歸結(jié)遍演繹味樹在一愛階謂候詞邏陪輯中嘉應(yīng)用逃消解句原理輸，不饑像命主題邏喇輯中拿那樣細(xì)簡(jiǎn)單生，因小為謂鞭詞邏榨輯中宮謂詞艘具有不常量配、變待量和筐函數(shù)汁等變圣元的拳存在捧，這憐就使便尋找滑含互柜否文紡字的勁子句易對(duì)的叢操作潔變得直復(fù)雜徐。例滋如：C1=P訴(x澡)∨烤Q(途x)C2=乛P(教a)想∨R佩(y硬)直接礙比較站，似搏乎兩廚者中庭不含儲(chǔ)互否貨文字怪，但棗如果何我們鵲用a替換C1中的x，則材得到C1′=礎(chǔ)P(叮a)泥∨Q刊(a砍)C2′=乛P(慮a)斃∨R斃(y層)于是外根據(jù)錦命題堅(jiān)邏輯短中的釀消解些原理紡，得C1′和C2′的消針解式鋒：C3′=征Q(逢a)古∨R銜(y蒜)氣謂詞蔥邏輯繭的歸搭結(jié)合一鄉(xiāng)豐（Un藏if平y(tǒng)）在謂寬詞邏敏輯的相歸結(jié)藝過程盞中，貧尋找愚項(xiàng)之增間合歷適的制變量輕置換煉使表殘達(dá)式菊一致約是一脆個(gè)很宿重要摘的過喚程，叉這個(gè)輔過程瞎稱為合一。定義6一個(gè)擠替換(S賀ub大st若it飽ut將io寇n)是形達(dá)如mg煉u=｛t1/x1,t2/x2,…,tn/xn｝的遇有限秘集合準(zhǔn)，其中t1,t2,…,tn是項(xiàng)世，稱衫為替換陷的分翁子；x1,x2,…,xn是互濾不相女同的恒個(gè)體武變?cè)S，稱批為替換殲的分嫂母；替換(S敬ub罵st儀it賓ut涌io稼n)C1=P削(x擠)∨下Q(勾x)C2=乛P(填a)植∨R芬(y炎)做替柱換：膝mg凍u=夾{a輪/x伶}C1′=黃P(袖a)多∨Q鄰(a噴)C2′=乛P(銹a)蜜∨R亭(y企)于是捷根據(jù)活命題斯邏輯盼中的銷消解膠原理劈燕，得C1′和C2′的消鍛解式蓋：C3′=旦Q(應(yīng)a)咸∨R掌(y到)例3.含21求證G是A1和A2的邏筒輯結(jié)嘉果。A1:投x屢(P承(x聰)→霉(Q徹(x您)∧問R(偏x)屠))A2:姓x豈(P丹(x挽)∧逗S(礙x)成)G:貍x續(xù)(S遵(x袖)∧睬R(胃x)美)證沫我們徐用反隙證法姑，即兆證明A1美∧A迫2∧乛G不可扣滿足輛。首瀉先求漢得子扶句集S：(1討)乛P(謝x)脆∨Q梨(x顧)(2斜)乛P(再y)爐∨R閘(y希)(3逝)P贊(a薪)(4負(fù))S傅(a拜)(5蛛)乛S(役z)幟∨乛R(鹿z)亭(乛G)婚然后引應(yīng)用適消解公原理昌，得(6尺)R逮(a仇)［(2權(quán)),拋(3稍),慣mg五u=｛a/膏y｝］(7紙)乛R(虹a)［(4荷),規(guī)(5曠),出mg祖u=｛a/憶z｝］(8狹)□［(6膽),蟻(7最)］所以S是不滲可滿扎足的突，從而而G是A1和A2的邏鳳輯結(jié)索果。(A1)(A2)S例音設(shè)已脅知：(1濃)能閱卻讀者貿(mào)是識(shí)郊字的丘；(2竟)海豚松不識(shí)銹字；(3厚)有些另海豚辱是很樓聰明姻的。試證貢明：判有些謀聰明咸并不步能閱匠讀。證標(biāo)首先洗，定攔義如遺下謂叮詞：R(呆x)：x能閱組讀。L(霉x)：x識(shí)字唇。I(大x)：x是聰影明的皮。D(君x)：x是海術(shù)豚。然后池把上裂述各汪語句恭翻譯工為謂紀(jì)詞公梢式：(1環(huán))顯x(令R(看x)尺→L摩(x樸))婆(2宮)憤x(度D(邪x)代→乛L(似x)楊)已知腸條件(3彼)己x(木D(考x)恩∧I勾(x瓦))(4危)會(huì)x(抓I(貧x)?！膩^R(累x)展)需證央結(jié)論杰求題臉設(shè)與競(jìng)結(jié)論猴否定府的子兇句集包，得(1惑)乛R(蒼x)嫩∨L紹(x談)(2蝕)乛D(廢y)平∨乛L(談y)(3虎)D戰(zhàn)(a寸)(4噴)I紀(jì)(a筍)(5帆)乛I(寨z)慣∨R途(z植)歸結(jié)適得(6里)生R(幅a)匠(5東)，(4難)，{a慶/z糖}(7激)合L代(a暖)臭(6溉)，(1昨)，{a法/x全}(8阻)乛D(辣a)質(zhì)(7襪),蔑(夢(mèng)2)色,職{a熊/y慮}(9夕)□弱(8竊),精(3啞)這個(gè)撈歸結(jié)扔過程量的演布繹樹禽如圖3―絹2所示附。圖3-緊2例3.友22歸結(jié)支演繹曬樹練習(xí)1證明捏子句謎集{P陸∨乛Q,乛P,蝕Q}是不慶可滿橡足的爸。練習(xí)2某公洪司招淡聘工葵作人餓員，厚有A,捕B,松C三人寧應(yīng)聘危，經(jīng)右面試弱后，犬公司搜表示綢如下懂想法涌：（1）三爽人中怨至少寨錄取龍一人（2）如滴果錄反取A而不普錄取B,則一旱定錄踩取C（3）如叛果錄翁取B,則一忘定錄倚取C試用繡歸結(jié)俊原理后求證御：公盤司一裹定錄睛取C第一歸步：看將問滅題用器謂詞魚公式菜表示前提射：（1）三槍人中雞至少飼錄取俱一人：A∨源B擾∨蒸C（2）如彎果錄同取A而不補(bǔ)錄取B,則一栽定錄最取C：(A疏∧乛B)租→C（3）如陷果錄瓜取B,則一聞定錄黎取C：B→陪C結(jié)論唇：公剃司一控定錄悅?cè)勾C第二能步：選將謂弊詞公恐式轉(zhuǎn)陵化為兔子句沿集，項(xiàng)并將位結(jié)論支的否仙定化陽為子畜句，與也加貧入子恒句集（1）A∨節(jié)B能∨雜C（2）(A加∧乛B)含→C乛(A到∧乛B)兆∨孝C乛A每∨B扇∨C(3漠)眨B→乒C乛B巴∨C(4標(biāo))乛C子句顯集：{A∨榜B鈔∨析C，乛A析∨B澡∨C，乛B禾∨C，乛C}第三課步適證明輸子句誘集是弓不可窄滿足好的（1）A∨疼B再∨邪C（2）乛A件∨B盼∨C(3廣)乛B遵∨C(4謠)乛C(5烤)餃B木∨堤C由（1）（2）(6映)燈C由(5角)響(3止)(7菌)謙□由（4）（6）課堂帖練習(xí)問題1：設(shè)脈已知哥公理豎集為P…鉗……寸……燈……（1）慶（P∧賞Q）→R…恭…（2）范（S∨眠T）→Q…刺…（3）T…凳……帖……號(hào)……（4）撞求證R。由（1）有誦子句蛙集{P紋}；壁由（2）有錘：恩（P∧鉆Q）→R＝>～(P妥∧Q復(fù))∨貨R＝>旁(～P∨～Q∨歡R)得子興句集因：{～P∨～Q∨導(dǎo)R}由（3）有仰：(S灶∨T蒜)→寇Q＝>～(S火∨T疏)∨摘Q＝>魄(～S∧～T)母∨Q＝>腹(～S∨蔬Q)坐∧(～T∨炊Q)得子病句集鹽：{～S∨翅Q,～T∨點(diǎn)Q}由（4）有穗子句綠集：(T去)。醒由結(jié)許論的辛否定章得子境句集袋：{～R}將以煤上子牲句集污并在葬一起廈有總脾的子搭句集肚：{P，~P父∨~牛Q∨殼R，~S贏∨Q，~T指∨Q，T，~R看}命題舉邏輯竄的歸灘結(jié)演價(jià)繹樹一個(gè)拌經(jīng)典努的歸后結(jié)問躬題例“快窩樂學(xué)范生”嬌問題假設(shè)迅：任負(fù)何通岡過計(jì)公算機(jī)仇考試在并獲飛獎(jiǎng)的營(yíng)人都焰是快厭樂的妻，任蠢何肯雄學(xué)習(xí)鳥或幸哈運(yùn)的朗人都血可以俊通過父所有砍考試港，張世不肯雁學(xué)習(xí)霧但他深是幸腫運(yùn)的悄，任理何幸昏運(yùn)的懸人都虛能獲支獎(jiǎng)。求證新：張?zhí)凼强鞂O樂的妻。解：先定鈔義謂茄詞：Pa愁ss賓(x批,毀y)維x可以亞通過y考試Wi誘n(頓x,萄p水ri臂ze福)周x能獲果得獎(jiǎng)快勵(lì)St規(guī)ud屯y(貢x)浩x肯學(xué)成習(xí)Ha寧pp蓋y(辰x)枝x是快沸樂的Lu歐ck拾y(售x)溝x是幸惰運(yùn)的再將哪問題崗用謂安詞表谷示如揪下：“任戀何通艷過計(jì)猴算機(jī)餐考試阻并獎(jiǎng)穗的人并都是木快樂榴的”(?x)年(P聞as位s(美x,災(zāi)c夠om榴pu納te呆r)嶺∧W需in柳(x鍛,赴pr撞iz月e)→Ha淹pp質(zhì)y(城x)蜓)“任何塔肯學(xué)娃習(xí)或店幸運(yùn)窩的人鈔都可棵以通賞過所飄有考突試”(?x)壺(?y)劍(嘩St述ud肥y(擴(kuò)x)顫∨L益uc膝ky燭(x帖)→劇Pa革ss關(guān)(x響,拳y)論)“張不瞇肯學(xué)鍛習(xí)但莊他是尚幸運(yùn)趕的”﹁S品tu酷dy擇(z甚ha統(tǒng)ng好)∧尾Lu糖ck釋y(攝zh最an絹g)“任何牌幸運(yùn)包的人稻都能美獲獎(jiǎng)倘”(?x)創(chuàng)(賓Lu圈ck作y(稀x)它→W隊(duì)in少(x咽,點(diǎn)pr現(xiàn)iz墳e)享)結(jié)論濤“張執(zhí)是快限樂的陜”的桃否定﹁H侍ap叢py涂(z談ha漂ng賄)將上索述謂杜詞公趕式轉(zhuǎn)擋化為父子句高集如遺下：(1遣)符﹁P鈔as文s(踩x,考c比om椅pu獻(xiàn)te兄r)蘆∨﹁醬Wi慰n(鑄x,巖p交ri捷ze丟)∨Ha腥pp迅y(注x)(2粘)辮﹁S香tu返dy聾(y醉)∨協(xié)Pa鋸ss附(y繞,考z)(3聚)謀﹁L快uc何ky間(u邀)∨晉Pa并ss妖(u續(xù),縱v)(4堅(jiān))犁﹁S攏tu弄dy也(z挎ha謠ng婆)(5頑)果L育uc畏ky難(z渾ha公ng懷)(6殺)煙﹁L鎖uc雕ky慈(w斷)∨講Wi抗n(雅w,草p另ri擠ze刪)(7簡(jiǎn))旱﹁縱Ha電pp取y(好zh度an予g)咐(結(jié)論壤的否脖定)﹁E益xc呆it點(diǎn)in艙g(胞Li息mi循ng膛)﹁H學(xué)ap諸py憤(z蕩)∨Ex潛ci態(tài)ti熱ng悲(z僚)﹁H寺ap寺py叢(L蝴im繳in饒g)Ha乒pp氧y(湖x)皆)∨換﹁S詠ma貓rt麗(x景)∨Ha候pp泰y(甚x)Po沿or丟(L黎im動(dòng)in勻g)簽∨﹁S程ma建rt走(L溜im樸in罰g)﹁R啟ea阿d(挑y)恨∨Sm肉ar仙t(今y配)Po巡壽or因(L孟im克in庭g)母∨﹁Re療ad椅(L起im妨in灘g)﹁P停oo碗r(皺Li顛mi言ng芹)﹁R完ea生d(售Li家mi鏟ng生)Re順ad擔(dān)(L限im但in章g)NI膽L{L效im洋in沒g/戰(zhàn)z}{L砍im醫(yī)in毫g/俗x}{L珠im忠in致g/衫y}歸結(jié)憂演繹速推理鹿的歸脂結(jié)策辟略廣度臺(tái)優(yōu)先是一庭種窮座盡子季句比掘較的哥復(fù)雜密搜索畫方法解。設(shè)涌初始繩子句筒集為S0，廣爬度優(yōu)攀先策吉略的策歸結(jié)謠過程每可描鴨述如眾下：(1美)從S0出發(fā)老，對(duì)S0中的鉤全部方子句鬼作所充有可累能的判歸結(jié)意，得陰到第必一層酬歸結(jié)然式，坊把這依些歸琴結(jié)式困的集炭合記棉為S1;(2夕)用S0中的迎子句洽與S1中的忙子句見進(jìn)行捧所有畏可能鏈的歸抓結(jié)，熊得到存第二佳層歸猶結(jié)式斜，把役這些速歸結(jié)肚式的符集合說記為S2;(3某)用S0和S1中的企子句匯與S2中的熔子句梯進(jìn)行漠所有皇可能憐的歸喚結(jié)，條得到解第三反層歸鵲結(jié)式額，把竿這些烘歸結(jié)假式的駐集合堂記為S3;如此鞋繼續(xù)區(qū)，知是道得囑出空扁子句辮或不距能再難繼續(xù)艱歸結(jié)士為止奏。例設(shè)有歸如下肚子句轉(zhuǎn)集：S=宰{﹁互I(蠶x)組∨R找(x轉(zhuǎn)),滿I(迫a)裳,椒﹁R兩(y懇)∨剪L(乳y)善,覺﹁L浴(a呆)楊}用寬乒度優(yōu)咱先策饒略證戒明S為不撈可滿舟足。寬度餐優(yōu)先懼策略拌的歸趟結(jié)樹己如下毫：歸結(jié)查演繹峽推理飽的歸狂結(jié)策元略1.廣度芳優(yōu)先統(tǒng)策略裂（2/吩3）﹁I叮(x宏)∨毫R(杰x)I(童a)﹁R言(y吃)∨學(xué)L(旺y)﹁L節(jié)(a潔)R(罷a)﹁I滴(x血)敞∨L報(bào)(x寺)﹁R薦(a肺)L(告a)L(磚a)﹁I葉(a吹)﹁I糧(a為)NI點(diǎn)LSS1S2歸結(jié)植演繹濫推理門的歸煮結(jié)策閣略1.廣度榜優(yōu)先誕策略山（3/借3）從這型個(gè)例峰子可抹以看鼓出，穴寬度碧優(yōu)先役策略葡歸結(jié)怒出了飽許多理無用異的子聚句，眉既浪漁費(fèi)事呆間，吩又浪哲費(fèi)空耀間。噸但是缺，這意種策異略由狐一個(gè)眠有趣偷的特艇性，妥就是敢當(dāng)問荷題有珍解時(shí)見保證能找癢到最酷短歸勇結(jié)路秋徑。因此放，它是一驚種完壁備的歸替結(jié)策有略。歌寬度舉優(yōu)先裳對(duì)大仰問題董的歸挪結(jié)容滿易產(chǎn)絕生組模合爆番炸，琴但對(duì)行小問塌題卻再仍是產(chǎn)一種在比較親好的扣歸結(jié)晶策略能。歸結(jié)惕演繹醋推理仙的歸齡結(jié)策架略2.支持童集策祥略（1/華3）支持餅集策籮略是懷沃斯(W匪os查)等人簡(jiǎn)在19哀65年提搬出的更一種盯歸結(jié)史策略翻。它要宮求每闊一次洲參加忽歸結(jié)謠的兩課個(gè)親賀本子侮句中微，至舅少應(yīng)疲該有詢一個(gè)版是由介目標(biāo)尚公式焦的否叛定所飽得到偶的子魔句或帆它們煮的后驚裔?？梢孕g(shù)證明牢支持尚集策倡略是完備曾的，即轎當(dāng)子幻玉句集濤為不票可滿憐足時(shí)居，則盈由支響持集殊策略游一定今能夠如歸結(jié)例出一缸個(gè)空鞠子句掘。也遭可以樸把支吉持集亦策略帖看成羞是在測(cè)寬度歐優(yōu)先粉策略蒼中引站入了幟某種菠限制購(gòu)條件核，這獸種限賊制條獻(xiàn)件代處表一千種啟唐發(fā)信涂息，麥因而轉(zhuǎn)有較音高的投效率例設(shè)有痛如下零子句蠅集：S=辟{﹁僅I(縣x)俗∨R圈(x案),滔I(巡壽a)取,﹁崇R選(y想)∨牢L(茂y)殘,烈﹁L粉(a遇)各}其中灑，﹁I竹(x貼)∨裝R(們x)為目急標(biāo)公依式的鑼否定山。用凍支持核集策鄙略證慌明S為不導(dǎo)可滿欣足。歸結(jié)捷演繹今推理鵝的歸提結(jié)策籍略2.支持勢(shì)集策杏略（2/蓄3）﹁I昂(x撒)∨聽R(倍x)I(榆a)﹁道R(執(zhí)y)筐∨L什(y恰)﹁L撒(a版)R(普a)﹁I約(x承)∨扯L(圈x)L(寧a)L(衡a)﹁I司(a沉)NI直L歸結(jié)雅演繹拌推理慚的歸眼結(jié)策陷略2.支持搏集策災(zāi)略（3/披3）從上恒述歸胡結(jié)過菊程可破以看章出，緣瑞各級(jí)斧歸結(jié)噸式數(shù)促目要屋比寬悄度優(yōu)評(píng)先策包略生穩(wěn)成的校少，缺但在陡第二毒級(jí)還灑沒有少空子敞句。暫就是糧說這春種策庫略限寒制了懷子句奮集元估素的奶劇增仔，但會(huì)增活加空五子句圈所在哥的深秀度。此燃外，答支持披集策韻略具有喇逆向類推理衰的含底義，由廚于進(jìn)屆行歸籃結(jié)的將親本就子句陣中至機(jī)少有嘉一個(gè)戶與目旨標(biāo)子以句有絞關(guān)，列因此葬推理談過程零可以劑看作臘是沿島目標(biāo)渣、子述目標(biāo)券的方宿向前夸進(jìn)的。歸結(jié)娛演繹勁推理蛛的歸勞結(jié)策萌略3.刪除煮策略松（2/玩2）重言手式刪恒除法如果放一個(gè)忘子句河中包含詳有互雅補(bǔ)的援文字帆對(duì)，則佳稱該榆子句礎(chǔ)為重言判式。例襯如P(墨x)猶∨﹁變P(浴x)查,弟P紫(x濃)∨穿Q(姓x)哄∨﹁炕P(概x)都是策重言傾式，乳不管P(趟x)的真嶄值為親真還摸是為機(jī)假，P(舍x)滅∨﹁嘴P(稼x)和P(永x)罩∨Q跡(x紙)∨腸﹁P蓮(x培)都均敵為真格。重言注式是活真值手為真壟的子胸句。本對(duì)一賭個(gè)子店句集系來說角，不低管是濤增加易還是雪刪除笛一個(gè)浮真值喜為真便的子膊句，班都不乖會(huì)影評(píng)響該湯子句胡集的嘆不可穿滿足特性。政因此少，可滾從子鞋句集南中刪呈去重科言式滔。歸結(jié)察演繹蜘推理特的歸抬結(jié)策劣略4.單文溉字子編句策覽略（1/仿2）如果違一個(gè)創(chuàng)子句只包侮含一胸個(gè)文倍字，則困稱此修子句搜為單興文字燙子句窩。單觸文字暫子句霉策略敬是對(duì)舞支持伙集策破略的烏進(jìn)一永步改蹦進(jìn)，城它要祖求每算次參示加歸槳結(jié)的扎兩個(gè)槳親本炭子句乳中至繞少有皇一個(gè)鍛子句寺是單泥文字老子句煤。例設(shè)有嘉如下暮子句潔集：S=筋{﹁向I(語x)牌∨R搞(x逢),光I(單a)協(xié),治﹁R網(wǎng)(y錯(cuò))∨訴L(繪y)鳳,的﹁L鼠(a盞)即}用單擋文字晶子句癢策略爛證明S為不落可滿塞足。采用資單文枕字子沙句策命略，宿歸結(jié)慚式包腸含的銳文字絕數(shù)將霸少于拋其親急本子蟲句中框的文港字?jǐn)?shù)凈，這暈將有遞利于帽向空蚊子句剛的方構(gòu)向發(fā)縱展，饑因此臉會(huì)有較阻高的歷歸結(jié)江效率浩。但詠這種扎策略剃是不派完備唐的，即擴(kuò)當(dāng)子前句集匠為不尾可滿森足時(shí)敬，用衰這種撐策略瓦不一渣定能信歸結(jié)慨出空煌子句賠。歸結(jié)船演繹液推理窯的歸上結(jié)策寶略4.單文聞字子節(jié)句策羞略（2/森2）﹁I繩(x宿)∨可R(餓x)I(右a)﹁R銷(y姜)∨慚L(牙y)﹁L約(a甚)R(敗a)﹁R(懲a)NI算L歸結(jié)怕演繹稼推理磚的歸誰結(jié)策折略5.線形恐輸入夠策略曬（1/繁2）這種熱策略買要求浩每次他參加鐘歸結(jié)蔑的兩尚個(gè)親族本子倚句中裂，至少帝應(yīng)該示有一析個(gè)是緣瑞初始注子句釘集中火的子劍句。所絨謂初約始子紙句集參是指伸開始食歸結(jié)終時(shí)所緩使用眼的子朝句集劍。例設(shè)有倍如下流子句晝集：S=呼{﹁詳I(泡x)存∨R固(x注