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

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

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

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

4、的情況就是正確結(jié)果。第二種方法用位操作。令A(yù)， B， C， D，E 都為邏輯型值true 或false 。則條件1 可以表示為：A B,它等價于！AttB 。條件2 可 以表示為：DIIE 。條件3 可以表示為：B&c) ，推演為 ！B：c。條件4 可以表示為：&，更簡單的形式是c=D。條件5 可以表示為：！EII 。如果將每個人的去與不去看成是 5 位整數(shù)的其中 1 位 ，其中 A 對應(yīng)最高位， E 對應(yīng)最低位 ，那么所有可 能的調(diào)派方案為從全部不派的 00000 到全部派去的 11111 之間變化。顯然，共有 32 種方案。全部遍歷的循環(huán)為： for 。 其中每個 i 對應(yīng)一個二進(jìn)制數(shù)，為

5、一種調(diào)派方案。在某一 種調(diào)派方案 i 中：A為最高位4或者 i4B 為次高位 3C為中間位2D為次低位1E為最低位根據(jù)求解模式，把這五個條件表示成否定的形式：否定 條件 1為=A8& B,否定條件 2為！，否定條件3為 B=C, 否定條件4為 c!=D ,否定條件 5為 E& !fA & B）。在 將 A E 的式子代入條件表達(dá)式，即可編程求解。2、竊賊說謊問題來看文章開始時提到的問題2：用 A， B， c， D 分別代表四人 ，變量的值為 1 代表該人是竊賊。已知：四人 中僅有一名竊賊，且這四個人中的每個人要么說真話，要么 說假話，而由于甲乙丙三人都說了兩句話：XX沒偷，xx 偷了”，故不論該人是否說謊，他提到的兩人之中必有人是 小偷。故在列