论文关键词:逻辑推演程序设计 数据结构

　　论文摘要:“逻辑推演”是指利用已知信息，通过分析和判断，得出未知信息的过程。计算机解决逻辑推演问题要依靠逻辑表达式。本文结合逻辑推演，剖析了程序设计在现实生活中的应用。[

　　一、 经典逻辑推演问题的引入

　　问题 1：从前，一个农夫带一只狼，一只羊和一颗白菜过河(注意该狼已被农夫驯服，但还是会吃羊 )。他要将所有东西安全的带到河的对岸。不幸的是河边只有一条小船 ，只能装下农夫和他的一样东西，并且农夫必须每次都随船过河，因为只有他能撑船。在无人看管的情况下狼要吃羊，羊要吃白菜，因此，农夫不能在河的某边岸上单独留下狼和羊，也不能单独留下羊和白菜。问农夫如何才能使三样东西平安过河。 ——农夫过河

　　问题 2：公安人员审问四名嫌疑犯。已知四人中仅有一名是窃贼还知道这四个人中每人要么是诚实的，要么总是说谎的。在回答公安人员的问题时：

　　甲说：“乙没有偷，是丁偷的。”

　　乙说：“我没有偷，是丙偷的。”

　　丙说：“甲没有偷，是乙偷的。”

　　丁说：“我没有偷。”

　　请根据这四人的答话判别谁是盗窃者。 ——窃贼说谎要解决上面两个问题需通过合理假设与逻辑推演将问题简化，通过正确的表达逻辑关系来驾驭程序设计。

　　二、逻辑推演在程序设计中的运用

　　1、委派任务问题

　　某任务需要在 A，B，c，D，E这五人中物色人员去完成，但派人受限于下列条件：

　　(1)若 A去，则 B跟去；(2)D，E两人中必有人去；(3)B，C两人中必有人去，但只去一人；(4)c，D两人要么都去，要么都不去；(5)若 E去，则 A，B都去。问这五个条件如何表示?

　　分析：求一个逻辑判断类问题的关键是写出正确的逻辑表达式。C语言中提供了丰富的算术和逻辑操作符，可以借助它们将问题化繁为简。将题设条件用程序语言描述清楚后计算机就可以依此穷举。

　　第一种方法

　　用 0和 1表示执行任务的状态 ：1(去)，0(不去)，则

　　A==O或 A+B=：2  ’

　　D-4-E>1

　　B+C==l

　　c+D：=0或 c+D==2

　　E==0或 A+B+E=3

　　各表达式之间是“与”的关系。穷举每个人去或不去的各种可能，代入表达式中进行推理运算 ，使上述各表达式值均为真的情况就是正确结果。

　　第二种方法

　　用位操作。令 A，B，C，D，E都为逻辑型值 true或false。则 ：

　　条件 1可以表示为：A—B，它等价于!AttB。

　　条件 2可 以表示为 ：DIIE。

　　条件 3可以表示为：(B＆＆!c) B&＆c)，推演为!B：c。

　　条件 4可以表示为：(!CIID)&＆(clID!)，更简单的形式是 c==D。

　　条件 5可以表示为：!EII(A&&B)。