霍尔逻辑(英语:HoareLogic),又称弗洛伊德霍尔逻辑(FloydHoarelogic),是英国计算机科学家东尼霍尔开发的形式系统,这个系统的用途是为了使用严格的数理逻辑推理来替计算机程序的正确性提供一组逻辑规则。
起源
这个想法起源于罗伯特弗洛伊德于较早的研究,他为流程图提供了类似的系统。东尼霍尔于1969年首次发表〔,随后为其他研究者所精制。
Hoare逻辑(也叫做FloydHoare逻辑)是英国计算机科学家C。A。R。Hoare开发的形式系统,随后为Hoare和其他研究者所精制。它发表于Hoare1969年的论文计算机程序的公理基础中。这个系统的用途是为了使用严格的数理逻辑推理计算机程序的正确性提供一组逻辑规则。
Hoare认可RobertFloyd的早期贡献,他为流程图提供了类似的系统。
霍尔三元组
霍尔逻辑的中心特征是霍尔三元组(Hoaretriple)。这种三元组描述一段代码的执行如何改变计算的状态。Hoare三元组有如下形式
这里的P和Q是断言而C是命令。P叫做前条件而Q叫做后条件。断言是谓词逻辑的公式。这个三元组在直觉上读做:只要P在C执行前的状态下成立,则在执行之后Q也成立。注意如果C不终止,也就没有之后了,所以Q在根本上可以是任何语句。实际上,你可以选择Q为假来表达C不终止。事实上,这种情形叫做部分正确(partialcorrectness)。如果C终止并且在终止时Q是真,则表达式被称作全部正确性(totalcorrectness)。终止必须被单独证明。
霍尔逻辑为简单的命令式编程语言的所有构造提供了公理和推理规则。除了给Hoare论文中的简单语言的规则,其他语言构造的规则也已经被Hoare和很多其他研究者开发完成。包括并发、过程、goto语句,和指针。
...
(全文)