簡(jiǎn)析邏輯推演程序設(shè)計(jì)在現(xiàn)實(shí)生活中的應(yīng)用

1、簡(jiǎn)析邏輯推演-程序設(shè)計(jì)在現(xiàn)實(shí)生活中的應(yīng)用論文關(guān)鍵詞:邏輯推演程序設(shè)計(jì)數(shù)據(jù)構(gòu)造論文摘要:“邏輯推演是指利用信息，通過(guò)分析和判斷，得出未知信息的過(guò)程。計(jì)算機(jī)解決邏輯推演問(wèn)題要依靠邏輯表達(dá)式。本文結(jié)合邏輯推演，剖析了程序設(shè)計(jì)在現(xiàn)實(shí)生活中的應(yīng)用。一、經(jīng)典邏輯推演問(wèn)題的引入問(wèn)題1：從前，一個(gè)農(nóng)夫帶一只狼，一只羊和一顆白菜過(guò)河(注意該狼已被農(nóng)夫征服，但還是會(huì)吃羊)。他要將所有東西平安的帶到河的對(duì)岸。不幸的是河邊只有一條小船，只能裝下農(nóng)夫和他的一樣?xùn)|西，并且農(nóng)夫必須每次都隨船過(guò)河，因?yàn)橹挥兴軗未?。在無(wú)人看管的情況下狼要吃羊，羊要吃白菜，因此，農(nóng)夫不能在河的某邊岸上單獨(dú)留下狼和羊，也不能單獨(dú)留下羊和白菜。問(wèn)

2、農(nóng)夫如何才能使三樣?xùn)|西平安過(guò)河。農(nóng)夫過(guò)河問(wèn)題2：公安人員審問(wèn)四名嫌疑犯。四人中僅有一名是竊賊還知道這四個(gè)人中每人要么是老實(shí)的，要么總是說(shuō)謊的。在答復(fù)公安人員的問(wèn)題時(shí)：甲說(shuō)：“乙沒(méi)有偷，是丁偷的。乙說(shuō)：“我沒(méi)有偷，是丙偷的。丙說(shuō)：“甲沒(méi)有偷，是乙偷的。丁說(shuō)：“我沒(méi)有偷。請(qǐng)根據(jù)這四人的答話判別誰(shuí)是盜竊者。竊賊說(shuō)謊要解決上面兩個(gè)問(wèn)題需通過(guò)合理假設(shè)與邏輯推演將問(wèn)題簡(jiǎn)化，通過(guò)正確的表達(dá)邏輯關(guān)系來(lái)駕馭程序設(shè)計(jì)。二、邏輯推演在程序設(shè)計(jì)中的運(yùn)用1、委派任務(wù)問(wèn)題某任務(wù)需要在A，B，D，E這五人中物色人員去完成，但派人受限于以下條件：(1)假設(shè)A去，那么B跟去；(2)D，E兩人中必有人去；(3)B，兩人中必有人去

3、，但只去一人；(4)，D兩人要么都去，要么都不去；(5)假設(shè)E去，那么A，B都去。問(wèn)這五個(gè)條件如何表示?分析：求一個(gè)邏輯判斷類問(wèn)題的關(guān)鍵是寫出正確的邏輯表達(dá)式。語(yǔ)言中提供了豐富的算術(shù)和邏輯操作符，可以借助它們將問(wèn)題化繁為簡(jiǎn)。將題設(shè)條件用程序語(yǔ)言描繪清楚后計(jì)算機(jī)就可以依此窮舉。第一種方法用0和1表示執(zhí)行任務(wù)的狀態(tài)：1(去)，0(不去)，那么A=或A+B=：2D-4-E1B+=l+D：=0或+D=2E=0或A+B+E=3各表達(dá)式之間是“與的關(guān)系。窮舉每個(gè)人去或不去的各種可能，代入表達(dá)式中進(jìn)展推理運(yùn)算，使上述各表達(dá)式值均為真的情況就是正確結(jié)果。第二種方法用位操作。令A(yù)，B，D，E都為邏輯型值true

4、或false。那么：條件1可以表示為：AB，它等價(jià)于!AttB。條件2可以表示為：DIIE。條件3可以表示為：(B!)B)，推演為!B：。條件4可以表示為：(!IID)(lID!)，更簡(jiǎn)單的形式是=D。條件5可以表示為：!EiI(AB)。假如將每個(gè)人的去與不去看成是5位整數(shù)的其中1位，其中A對(duì)應(yīng)最高位，E對(duì)應(yīng)最低位，那么所有可能的調(diào)派方案為從全部不派的00000到全部派去的11111之間變化。顯然，共有32種方案。全部遍歷的循環(huán)為：fr(inti_0；i32；i+)。其中每個(gè)i對(duì)應(yīng)一個(gè)二進(jìn)制數(shù)，為一種調(diào)派方案。在某一種調(diào)派方案i中：A為最高位(i16)4或者i4(將低位都擠掉)B為次高位(i8

5、)3為中間位(i4)2D為次低位(i2)lE為最低位(i1)根據(jù)求解形式，把這五個(gè)條件表示成否認(rèn)的形式：否認(rèn)條件1為(!AIIB)=AB，否認(rèn)條件2為!(DJIE)，否認(rèn)條件3為B=，否認(rèn)條件4為!=D，否認(rèn)條件5為E!fAB)。在將AE的式子代入條件表達(dá)式，即可編程求解。2、竊賊說(shuō)謊問(wèn)題來(lái)看文章開(kāi)場(chǎng)時(shí)提到的問(wèn)題2：用A，B，D分別代表四人，變量的值為1代表該人是竊賊。：四人中僅有一名竊賊，且這四個(gè)人中的每個(gè)人要么說(shuō)真話，要么說(shuō)假話，而由于甲乙丙三人都說(shuō)了兩句話：沒(méi)偷，偷了，故不管該人是否說(shuō)謊，他提到的兩人之中必有人是小偷。故在列條件表達(dá)式時(shí)，可以不關(guān)心誰(shuí)說(shuō)謊，誰(shuí)說(shuō)實(shí)話。這樣，可以列出以下條件

6、表達(dá)式：甲說(shuō)：“乙沒(méi)有偷，是丁偷的。B+D=I乙說(shuō)：“我沒(méi)有偷，是丙偷的。B+=I丙說(shuō)：“甲沒(méi)有偷，是乙偷的。A+B=I丁說(shuō)：“我沒(méi)有偷。A+B+D=I其中丁只說(shuō)了一句話，無(wú)法斷定真假，表達(dá)式反映了四個(gè)人中僅有一名是竊賊的條件。有了條件表達(dá)式，運(yùn)用程序設(shè)計(jì)中的窮舉法就可以輕松求解。3、農(nóng)夫過(guò)河問(wèn)題(邏輯推演方法與BFS、DFS相結(jié)合的實(shí)例)用一個(gè)四位二進(jìn)制數(shù)來(lái)分別表示白菜、羊、狼、和農(nóng)夫的過(guò)河狀態(tài)0表示在原始岸邊，即尚未過(guò)河；1表示在目的岸邊，已經(jīng)過(guò)河。將過(guò)河對(duì)象定義為枚舉enu類型，bitset4類型定義為bitvee(這里用到了+標(biāo)準(zhǔn)函數(shù)庫(kù)STL)。枚舉類型定義過(guò)河者時(shí)，是按照白菜、羊、狼

7、、和農(nóng)夫的次序分別定義的。這種次序中前三者的順序可以隨意，但農(nóng)夫farer必須在最后，目的是便于在試探隨農(nóng)夫過(guò)河的對(duì)象時(shí)逐序進(jìn)展所有的東西都不能帶過(guò)河時(shí)，最后才選擇讓農(nóng)夫單獨(dú)過(guò)河。enuaderabbage,默認(rèn)為1gat，默認(rèn)為2lf,默認(rèn)為3farer，默認(rèn)為4J；typedefbitset4bitve；過(guò)河的對(duì)象必須與農(nóng)夫在河的同一側(cè)，設(shè)計(jì)函數(shù)ithFarer來(lái)判斷。假如當(dāng)前state下，過(guò)河對(duì)象與農(nóng)夫的狀態(tài)參數(shù)一致，那么返回真，表示二者在河的同一側(cè)。此外，不管農(nóng)夫每次過(guò)河帶的東西如何，首先都應(yīng)該判斷這樣過(guò)河是否平安，即在無(wú)人看管的情況下，狼和羊，羊和白菜都沒(méi)有在河的同側(cè)，函數(shù)is_se

8、完成判斷。當(dāng)農(nóng)夫與羊不在河的同側(cè)時(shí)，羊與白菜、或羊與狼在同側(cè)都是不平安的，返回false；其他情況那么是平安的，返回true。blissafe(nstbitvestate)，羊吃白菜if(stateabbage】=stategat)(statefarer!=stategat)returnfalse；，狼吃羊if(stategat】=stateLq)(statefarer!=statelq)retufalse；其它狀態(tài)為平安狀態(tài)為了防止發(fā)生狀態(tài)的往復(fù)，即農(nóng)夫?qū)⒁粋€(gè)東西帶過(guò)去又帶回來(lái)的情況發(fā)生，也為了記錄過(guò)河的狀態(tài)過(guò)程，對(duì)所有可能的狀態(tài)進(jìn)展標(biāo)定。四位二進(jìn)制數(shù)的所有可能狀態(tài)為16，都初始化為一1，表示過(guò)河過(guò)程中尚未出現(xiàn)過(guò)；隨著過(guò)河過(guò)程的不斷進(jìn)展，它被改變?yōu)槠淝耙粻顟B(tài)二進(jìn)制數(shù)對(duì)應(yīng)的整數(shù)值。于是，農(nóng)夫過(guò)河問(wèn)題經(jīng)過(guò)二進(jìn)制化以后，化為從初始狀態(tài)0000出發(fā)，經(jīng)過(guò)系列平安狀態(tài)后，假如最后狀態(tài)到達(dá)，即path15有前驅(qū)狀態(tài)，那么表示過(guò)河成功。問(wèn)題求解后得到一系-進(jìn)制數(shù)，將這一系列二進(jìn)制數(shù)表示的過(guò)河狀態(tài)轉(zhuǎn)換為實(shí)際的過(guò)河方案即可。三、總結(jié)程序設(shè)計(jì)是將人的思維轉(zhuǎn)化為機(jī)器語(yǔ)言的過(guò)程，程序抽象程度越高，與人的思維方式就越類似。邏輯推演是建立在思維之上的，是有根據(jù)的推演，將邏輯推演的思想融人程序，在一定程度上可以實(shí)現(xiàn)程序的智能化。隨著程序設(shè)計(jì)語(yǔ)言的開(kāi)展，邏輯推演的應(yīng)用一