简析逻辑推演程序设计在现实生活中的应用

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

2、农夫如何才能使三样东西平安过河。农夫过河问题2：公安人员审问四名嫌疑犯。四人中仅有一名是窃贼还知道这四个人中每人要么是老实的，要么总是说谎的。在答复公安人员的问题时：甲说：“乙没有偷，是丁偷的。乙说：“我没有偷，是丙偷的。丙说：“甲没有偷，是乙偷的。丁说：“我没有偷。请根据这四人的答话判别谁是盗窃者。窃贼说谎要解决上面两个问题需通过合理假设与逻辑推演将问题简化，通过正确的表达逻辑关系来驾驭程序设计。二、逻辑推演在程序设计中的运用1、委派任务问题某任务需要在A，B，D，E这五人中物色人员去完成，但派人受限于以下条件：(1)假设A去，那么B跟去；(2)D，E两人中必有人去；(3)B，两人中必有人去

3、，但只去一人；(4)，D两人要么都去，要么都不去；(5)假设E去，那么A，B都去。问这五个条件如何表示?分析：求一个逻辑判断类问题的关键是写出正确的逻辑表达式。语言中提供了丰富的算术和逻辑操作符，可以借助它们将问题化繁为简。将题设条件用程序语言描绘清楚后计算机就可以依此穷举。第一种方法用0和1表示执行任务的状态：1(去)，0(不去)，那么A=或A+B=：2D-4-E1B+=l+D：=0或+D=2E=0或A+B+E=3各表达式之间是“与的关系。穷举每个人去或不去的各种可能，代入表达式中进展推理运算，使上述各表达式值均为真的情况就是正确结果。第二种方法用位操作。令A，B，D，E都为逻辑型值true

4、或false。那么：条件1可以表示为：AB，它等价于!AttB。条件2可以表示为：DIIE。条件3可以表示为：(B!)B)，推演为!B：。条件4可以表示为：(!IID)(lID!)，更简单的形式是=D。条件5可以表示为：!EiI(AB)。假如将每个人的去与不去看成是5位整数的其中1位，其中A对应最高位，E对应最低位，那么所有可能的调派方案为从全部不派的00000到全部派去的11111之间变化。显然，共有32种方案。全部遍历的循环为：fr(inti_0；i32；i+)。其中每个i对应一个二进制数，为一种调派方案。在某一种调派方案i中：A为最高位(i16)4或者i4(将低位都挤掉)B为次高位(i8

5、)3为中间位(i4)2D为次低位(i2)lE为最低位(i1)根据求解形式，把这五个条件表示成否认的形式：否认条件1为(!AIIB)=AB，否认条件2为!(DJIE)，否认条件3为B=，否认条件4为!=D，否认条件5为E!fAB)。在将AE的式子代入条件表达式，即可编程求解。2、窃贼说谎问题来看文章开场时提到的问题2：用A，B，D分别代表四人，变量的值为1代表该人是窃贼。：四人中仅有一名窃贼，且这四个人中的每个人要么说真话，要么说假话，而由于甲乙丙三人都说了两句话：没偷，偷了，故不管该人是否说谎，他提到的两人之中必有人是小偷。故在列条件表达式时，可以不关心谁说谎，谁说实话。这样，可以列出以下条件

6、表达式：甲说：“乙没有偷，是丁偷的。B+D=I乙说：“我没有偷，是丙偷的。B+=I丙说：“甲没有偷，是乙偷的。A+B=I丁说：“我没有偷。A+B+D=I其中丁只说了一句话，无法断定真假，表达式反映了四个人中仅有一名是窃贼的条件。有了条件表达式，运用程序设计中的穷举法就可以轻松求解。3、农夫过河问题(逻辑推演方法与BFS、DFS相结合的实例)用一个四位二进制数来分别表示白菜、羊、狼、和农夫的过河状态0表示在原始岸边，即尚未过河；1表示在目的岸边，已经过河。将过河对象定义为枚举enu类型，bitset4类型定义为bitvee(这里用到了+标准函数库STL)。枚举类型定义过河者时，是按照白菜、羊、狼

7、、和农夫的次序分别定义的。这种次序中前三者的顺序可以随意，但农夫farer必须在最后，目的是便于在试探随农夫过河的对象时逐序进展所有的东西都不能带过河时，最后才选择让农夫单独过河。enuaderabbage,默认为1gat，默认为2lf,默认为3farer，默认为4J；typedefbitset4bitve；过河的对象必须与农夫在河的同一侧，设计函数ithFarer来判断。假如当前state下，过河对象与农夫的状态参数一致，那么返回真，表示二者在河的同一侧。此外，不管农夫每次过河带的东西如何，首先都应该判断这样过河是否平安，即在无人看管的情况下，狼和羊，羊和白菜都没有在河的同侧，函数is_se

8、完成判断。当农夫与羊不在河的同侧时，羊与白菜、或羊与狼在同侧都是不平安的，返回false；其他情况那么是平安的，返回true。blissafe(nstbitvestate)，羊吃白菜if(stateabbage】=stategat)(statefarer!=stategat)returnfalse；，狼吃羊if(stategat】=stateLq)(statefarer!=statelq)retufalse；其它状态为平安状态为了防止发生状态的往复，即农夫将一个东西带过去又带回来的情况发生，也为了记录过河的状态过程，对所有可能的状态进展标定。四位二进制数的所有可能状态为16，都初始化为一1，表示过河过程中尚未出现过；随着过河过程的不断进展，它被改变为其前一状态二进制数对应的整数值。于是，农夫过河问题经过二进制化以后，化为从初始状态0000出发，经过系列平安状态后，假如最后状态到达，即path15有前驱状态，那么表示过河成功。问题求解后得到一系-进制数，将这一系列二进制数表示的过河状态转换为实际的过河方案即可。三、总结程序设计是将人的思维转化为机器语言的过程，程序抽象程度越高，与人的思维方式就越类似。逻辑推演是建立在思维之上的，是有根据的推演，将逻辑推演的思想融人程序，在一定程度上可以实现程序的智能化。随着程序设计语言的开展，逻辑推演的应用一