程序验证(六):纳尔逊-欧朋算法(Nelson-Oppen Procedure) 动机 截至目前,我们学习了一些一阶理论,每一个都是关于某一种数据类型 然而,现实中的公式并不是由单一的理论组成,如: ∀ i . 0 ≤ i ≤ n → a [ i ] ≤ a [ i + 1 ] \forall i.0\le i\le n\to a[i]\le a[i+1] ∀i.0≤i≤n→a[i]≤a[i
程序验证(五):一阶理论的过程 主要讨论 T E T_E TE的量词自由片段以及 T A T_A TA 等价理论的判定 等价及未解释函数理论(Theory of Equality and Uninterpreted Functions) 除=外的谓词实际上使我们的讨论不必要地复杂化,去除这些累赘谓词的方法如下: 对每个谓词 p p p,引入一个新的(fresh)函数符号 f p f_
程序验证(十):演绎验证(上) 基础路径(Basic Approach) 给定一个程序 c c c,由以下specification注解: { P } c { Q } \{P\}c\{Q\} {P}c{Q} 为了证明这个三元组,我们构造一个验证条件(verification condition, VC)的集合 每个VC都是某个理论的一阶公式如果所有的VC都是永真的,那么 { P } c {
程序验证(九):程序正确性规范 什么是程序的正确性?应当在指定的前提下,进行预定的行为,达到指定的结果。 部分正确性(Partial Correctness) 部分正确性指的是一个程序的停止行为 我们将部分正确性用霍尔三元组(Hoare triples)表达: { P } c { Q } \{P\}c\{Q\} {P}c{Q} 这里: c c c是一个程序 P P P和 Q Q Q是一
程序验证(八):形式语义 语义描述方法 如下: 操作语义:用抽象机描述程序执行引起的状态改变,关心状态改变是怎样产生的,与语言的实现关系紧密。指称语义:使程序执行的效果对应数学对象,只关心程序执行的效果,不关心其是怎样产生的。公理语义:将程序的语义性质表示为命题,采用数理逻辑的方法研究。 引入玩具语言Imp 语法范畴 如下: 数字集 N u m Num Num,用 n n n表示数字