简析逻辑推演

1、    简析逻辑推演-程序设计在现实生活中的应用            作者：田 甜 柳保燕 黄利利时间：2010-2-8 16:49:00                     论文关键词:逻辑推演程序设计 数据结构论文摘要:“逻辑推演

2、”是指利用已知信息，通过分析和判断，得出未知信息的过程。计算机解决逻辑推演问题要依靠逻辑表达式。本文结合逻辑推演，剖析了程序设计在现实生活中的应用。一、 经典逻辑推演问题的引入 问题 1：从前，一个农夫带一只狼，一只羊和一颗白菜过河(注意该狼已被农夫驯服，但还是会吃羊 )。他要将所有东西安全的带到河的对岸。不幸的是河边只有一条小船 ，只能装下农夫和他的一样东西，并且农夫必须每次都随船过河，因为只有他能撑船。在无人看管的情况下狼要吃羊，羊要吃白菜，因此，农夫不能在河的某边岸上单独留下狼和羊，也不能单独留下羊和白菜。问农夫如何才能使三样东西平安过河。 农夫过河问题 2：公安人员审问四名嫌疑犯。已知

3、四人中仅有一名是窃贼还知道这四个人中每人要么是诚实的，要么总是说谎的。在回答公安人员的问题时： 甲说：“乙没有偷，是丁偷的。” 乙说：“我没有偷，是丙偷的。” 丙说：“甲没有偷，是乙偷的。” 丁说：“我没有偷。” 请根据这四人的答话判别谁是盗窃者。 窃贼说谎要解决上面两个问题需通过合理假设与逻辑推演将问题简化，通过正确的表达逻辑关系来驾驭程序设计。 二、逻辑推演在程序设计中的运用 1、委派任务问题 某任务需要在 A，B，c，D，E这五人中物色人员去完成，但派人受限于下列条件： (1)若 A去，则 B跟去；(2)D，E两人中必有人去；(3)B，C两人中必有人去，但只去一人；(4)c，D两人要么都

4、去，要么都不去；(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

5、，B，C，D，E都为逻辑型值 true或false。则 ： 条件 1可以表示为：AB，它等价于!AttB。 条件 2可 以表示为 ：DIIE。 条件 3可以表示为：(B!c) B&c)，推演为!B：c。 条件 4可以表示为：(!CIID)&(clID!)，更简单的形式是 c=D。 条件 5可以表示为：!EII(A&&B)。    如果将每个人的去与不去看成是 5位整数的其中 1位 ，其中 A对应最高位，E对应最低位 ，那么所有可能的调派方案为从全部不派的00000到全部派去的 11111之间变化。显然，共有 32种方案。全

6、部遍历的循环为：for(inti_0；i<32；i+)。其中每个 i对应一个二进制数，为一种调派方案。在某一种调派方案 i中： A为最高位(i&16)>>4或者 i>>4(将低位都挤掉 ) B为次高位 (i8)>>3 C为中间位(i4)>>2 D为次低位(i2)>>l E为最低位(i&1) 根据求解模式，把这五个条件表示成否定的形式：否定条件 1为(!AIIB)=A&B，否定条件 2为 !(DJIE)，否定条件3为 B=C，否定条件4为 c!=D，否定条件 5为 E&!fAB)。在将 AE的式子代

7、入条件表达式，即可编程求解。 2、窃贼说谎问题 来看文章开始时提到的问题 2：用 A，B，c，D分别代表四人 ，变量的值为 1代表该人是窃贼。已知：四人中仅有一名窃贼，且这四个人中的每个人要么说真话，要么说假话，而由于甲乙丙三人都说了两句话：××没偷，××偷了”，故不论该人是否说谎，他提到的两人之中必有人是小偷。故在列条件表达式时，可以不关心谁说谎 ，谁说实话。这样 ，可以列出下列条件表达式： 甲说 ：“乙没有偷，是丁偷的。”B+D=I 乙说：“我没有偷，是丙偷的。”B+C=I 丙说：“甲没有偷，是乙偷的。”A+B=I 丁说：“我没有偷。” 

8、A+B+C+D=I 其中丁只说了一句话，无法判定真假，表达式反映了四个人中仅有一名是窃贼的条件。有了条件表达式，运用程序设计中的穷举法就可以轻松求解。 3、农夫过河问题(逻辑推演方法与 BFS、DFS相结合的实例) 用一个四位二进制数来分别表示白菜、羊、狼、和农夫的过河状态0表示在原始岸边，即尚未过河 ；1表示在目的岸边，已经过河。将过河对象定义为枚举 enum类型，bitset<4>类型定义为 bitvee(这里用到了c+标准函数库 STL)。枚举类型定义过河者时，是按照白菜、羊、狼、和农夫的次序分别定义的。这种次序中前三者的顺序可以随意，但农夫farmer必须在最后，目的是便于

9、在试探随农夫过河的对象时逐序进行所有的东西都不能带过河时，最后才选择让农夫单独过河。 enum W ader cabbage,默认为 1 goat， 默认为2 wolf,  默认为 3 farmer， 默认为 4 J； typedef bitset<4> bitvec；    过河的对象必须与农夫在河的同一侧，设计函数 withFarmer来判断。如果当前 state下，过河对象与农夫的状态参数一致，则返回真，表示二者在河的同一侧。 此外，不论农夫每次过河带的东西如何，首先都应该判断这样过河是否安全，即在无人看管的情况下，狼和羊，羊

10、和白菜都没有在河的同侧，函数 is_sMe完成判断。当农夫与羊不在河的同侧时，羊与白菜、或羊与狼在同侧都是不安全的，返回false；其他情况则是安全的，返回true。 bool issafe(const bitvecstate) ，羊吃白菜 if(statecabbage】=stategoat)(statefarmer!=stategoat) return false； ，狼吃羊 if(stategoat】=stateoLq)(statefarmer!=statewolq) retum false； 其它状态为安全状态 为了防止发生状态的往复，即农夫将一个东西带过去又带回来的情况发生，也为了记

11、录过河的状态过程，对所有可能的状态进行标定。四位二进制数的所有可能状态为 16，都初始化为一1，表示过河过程中尚未出现过；随着过河过程的不断进行，它被改变为其前一状态二进制数对应的整数值。 于是，农夫过河问题经过二进制化以后，化为从初始状态 0000出发，经过系列安全状态后，如果最后状态到达，即path15有前驱状态，则表示过河成功。问题求解后得到一系-进制数 ，将这一系列二进制数表示的过河状态转换为实际的过河方案即可。 三、总结 程序设计是将人的思维转化为机器语言的过程，程序抽象程度越高，与人的思维方式就越类似。逻辑推演是建立在思维之上的，是有依据的推演，将逻辑推演的思想融人程序，在一定程度上可以实现程序的智能化。随着程序