《简析逻辑推演》由会员分享，可在线阅读，更多相关《简析逻辑推演（5页珍藏版）》请在金锄头文库上搜索。
1、简析逻辑推演 - 程序设计在现实生活中 的应用 (1) 论文关键词 : 逻辑推演程序设计 数据结构论文摘要 : “逻辑推演”是指利用已知信息，通过分析 和判断，得出未知信息的过程。计算机解决逻辑推演问题要 依靠逻辑表达式。本文结合逻辑推演，剖析了程序设计在现 实生活中的应用。 一、 经典逻辑推演问题的引入问题 1：从前，一个农夫带一只狼，一只羊和一颗白 菜过河。他要将所有东西安全的带到河的对岸。不幸的是河 边只有一条小船 ，只能装下农夫和他的一样东西，并且农 夫必须每次都随船过河，因为只有他能撑船。在无人看管的 情况下狼要吃羊，羊要吃白菜，因此，农夫不能在河的某边 岸上单独留下狼和羊，也不能单
2、独留下羊和白菜。问农夫如 何才能使三样东西平安过河。 农夫过河问题 2：公安人员审问四名嫌疑犯。已知四人中仅有 一名是窃贼还知道这四个人中每人要么是诚实的，要么总是 说谎的。在回答公安人员的问题时：甲说：“乙没有偷，是丁偷的。 ”乙说：“我没有偷，是丙偷的。 ”丙说：“甲没有偷，是乙偷的。 ”丁说：“我没有偷。 ”要解决上面两个问题需通过合理假设与逻辑推演将问题简 化，通过正确的表达逻辑关系来驾驭程序设计。二、逻辑推演在程序设计中的运用1、委派任务问题某任务需要在A，B，c， D，E 这五人中物色人员去完成，但派人受限于下列条件：若 A去，则 B跟去；D, E两人中必有人去；B, C两人中必有
3、人去，但只去一人；c, D两人要么都去，要么都不去；若 E 去,则 A, B 都去。问这五个条件如何表示 ?分析：求一个逻辑判断类问题的关键是写出正确的逻辑 表达式。 C 语言中提供了丰富的算术和逻辑操作符,可以借 助它们将问题化繁为简。将题设条件用程序语言描述清楚后 计算机就可以依此穷举。第一种方法用 0 和 1 表示执行任务的状态： 1, 0 ,则A=0或 A+B三 2D-4-E1B+C=lc+D：=0 或 c+D=2E=0 或 A+B+E=3各表达式之间是“与”的关系。穷举每个人去或不去的，使上述各表达式各种可能，代入表达式中进行推理运算值均为真的情况就是正确结果。第二种方法用位操作。令
4、A， B， C， D，E 都为逻辑型值true 或false 。则条件1 可以表示为：A B,它等价于！AttB 。条件2 可 以表示为：DIIE 。条件3 可以表示为：B&c) ，推演为 ！B ：c。条件4 可以表示为：&，更简单的形式是c=D。条件5 可以表示为：！EII 。如果将每个人的去与不去看成是 5 位整数的其中 1 位 ，其中 A 对应最高位， E 对应最低位 ，那么所有可 能的调派方案为从全部不派的 00000 到全部派去的 11111 之间变化。显然，共有 32 种方案。全部遍历的循环为： for 。 其中每个 i 对应一个二进制数，为一种调派方案。在某一 种调派方案 i 中
5、：A为最高位4或者 i4B 为次高位 3C为中间位2D为次低位1E为最低位根据求解模式，把这五个条件表示成否定的形式：否定 条件 1为=A8& B,否定条件 2为！，否定条件3为 B=C, 否定条件4为 c!=D ,否定条件 5为 E& !fA & B）。在 将 A E 的式子代入条件表达式，即可编程求解。2、窃贼说谎问题来看文章开始时提到的问题2：用 A， B， c， D 分别代表四人 ，变量的值为 1 代表该人是窃贼。已知：四人 中仅有一名窃贼，且这四个人中的每个人要么说真话，要么 说假话，而由于甲乙丙三人都说了两句话：XX没偷，xx 偷了”，故不论该人是否说谎，他提到的两人之中必有人是 小偷。故在列条件表达式时，可以不关心谁说谎，谁说实话。这样 ，可以列出下列条件表达式： （作者：未知本文来源于爬虫自动抓取，如有侵犯权益请联 系 service 立即删除）
