程序原本(十一):计算系统——逻辑(正确逻辑:顺序、分支,与循环)

阅读数:24 2019 年 9 月 28 日 17:51

程序原本(十一):计算系统——逻辑(正确逻辑:顺序、分支,与循环)

现在我们都知道原因:在“三加二乘以五”中应该先计算“二乘以五”。对于 3+2×5 这个题目来说,单纯地做:

复制代码
3+2=5
5×5=25

这样的计算是不行的,因为上面的解题中出现了“先”计算什么,与“后”计算什么的问题。

由此可见:无论是 3+2 还是 5×5 等,都是数值的计算;这些计算要正确地表述一个解题过程,还需要一个正确的逻辑描述,例如“先后”——即是指,我们要按某种顺序逻辑来应用“算”的规则。然而这样“正确的逻辑描述”有哪些呢?

这倒不需要我们再逐一列举,或像我一样回顾数学知识的点滴来源。Dijkstra(戴克斯特拉)1对这个问题有过非常严谨的数学论证,他指出:(我们)有三种思维方法用来理解一个程序,即枚举法、数学归纳法和抽象。除顺序逻辑之外,他指出枚举法、数学归纳法分别可以用程序中的分支逻辑循环逻辑来表达2 3 4。例如,枚举法的基本思维是,对于一个条件集,

1 艾兹赫尔•戴克斯特拉(Edsger Wybe Dijkstra),荷兰计算机科学家,结构程序设计之父。1972 年图灵奖获得者。本书对 Dijkstra 的观点的引用,均出自《结构程序设计》的第一篇,即“结构程序札记”。于此,后文中不再复述。

2 Dijkstra 是用数学方法来证明分支与循环(和递归)逻辑的正确性,我们同样可以把这个证明过程看成一个映射关系,即上述逻辑可以视为思维方法在计算系统中的映射。

3 Dijkstra 提到了抽象,但没有对抽象在逻辑证明中的作用给出类似的数学证明——尽管他事实上在后面(不太明显地)给出了一个抽象逻辑证明的实例。

4 Dijkstra 并没有用同样的方法来证明顺序逻辑,而顺序逻辑正是图灵机的本质设定。因此,在 Dijkstra 的论证中,他强调“只讨论关于‘顺序机器’的程序”。

  • 如果条件 n 不成立,则条件 n+1 可能成立;若条件 n+1 仍不成立,则条件 n+1+1 可能成立……
  • 如此非此即彼,则当所有条件不成立时,条件集中没有可成立的条件;否则,
  • 条件之一成立,则该集中有成立条件。

对于上述思维过程,就可以用分支逻辑(分支以及多重分支语句)来表达。

评论

发布