程序原本(十二):计算系统——逻辑(我们要记住:Dijkstra 说他只讨论了“顺序机器”上的正确的逻辑)

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

程序原本(十二):计算系统——逻辑(我们要记住:Dijkstra说他只讨论了“顺序机器”上的正确的逻辑)

我们已经触及到计算系统的构成,以及在这样的计算系统上正确计算的诸多要素。一些看起来很明显的要素包括:数、数据(标识、值)和正确的逻辑描述,另一些不太明显的要素包括:算、思维方法和确定性。

Dijkstra 接下来用顺序逻辑统一了分支与循环逻辑,使之成为“顺序机器”上的最基本的正确的逻辑描述。他说明,我们可以从形式上将上述三种逻辑表示为图 1 所示的图形。

图 1 三种逻辑表示

程序原本(十二):计算系统——逻辑(我们要记住:Dijkstra说他只讨论了“顺序机器”上的正确的逻辑)

很自然地可以发现:分支逻辑与循环逻辑其实都只有一个入口和一个出口,因此它们也自然可以作为顺序逻辑中的 S1Sn,而不会破坏顺序逻辑的基本规则。更进一步,既然分支逻辑与循环逻辑是可被证明为正确的,并可以作为“顺序机器”本质所设定的顺序逻辑的一部分,那么由这些逻辑构成的“程序”也就必然是正确的。

这里的所谓正确,包括三个意思:一是程序能正确地描述人的思维;二是程序可以由机器正确地执行;三是机器执行的结果正确地符合人的思维的预期。不过这所有的“正确”仍然依赖两项前提:一是计算系统是一个“顺序机器”,二是在每一个用于顺序计算的阶段(S1…Sn)中的数据,是确定的。

最后这一点——数据的确定性,正是顺序逻辑的必然结果:对于一个确定的逻辑而言,一个确定的输入,必有一个确定的输出。所谓输入与输出,若是数据,则在“第 1 章 数,以及对数据的性质的思考”中所述数据的内聚与外延的性质保障了这一结果;若是逻辑,则如上的形式化证明便保障了这一结果。

评论

发布