对程序进行推理逻辑计算机科学导论第二讲.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 程 序 验 证 实 例 n ? 0 // 前条件 void mult(int m, int n) { x = 0 ; y = 0 ; while (y n) do { x = x + m ; y = y + 1 ; } } x == m ? n // 后条件 由程序员提供 由程序员提供 * 程 序 验 证 实 例 n ? 0 void mult(int m, int n) { x = 0 ; y = 0 ; while (y n) do { (x == m?y) ? (y ? n) // 循环不变式 x = x + m ; y = y + 1 ; } } x == m ? n 也由程序员提供 * 程 序 验 证 实 例 n ? 0 void mult(int m, int n) { x = 0 ; y = 0 ; while (y n) do { (x == m?y) ? (y ? n) // 循环不变式 x = x + m ; y = y + 1 ; } } x == m ? n 函数前后条件、循环不变式 都称为断言 它们看上去像编程语言的布 尔表达式 * 程 序 验 证 实 例 n ? 0 void mult(int m, int n) { x = 0 ; y = 0 ; while (y n) do { (x == m?y) ? (y ? n) x = x + m ; y = y + 1 ; } ((x == m?y) ? (y ? n)) ? ?(y n) // 循环结束程序点的断言 } x == m ? n I ? ?E * 程 序 验 证 实 例 n ? 0 void mult(int m, int n) { x = 0 ; y = 0 ; while (y n) do { (x == m?y) ? (y ? n) x = x + m ; y = y + 1 ; } ((x == m?y) ? (y ? n)) ? ?(y n) ? (x == m?n) } x == m ? n I ? ?E ? Q（Q是函数后条件） 第1个验证条件 * 程 序 验 证 实 例 n ? 0 void mult(int m, int n) { x = 0 ; y = 0 ; while (y n) do { (x == m?y) ? (y ? n) x = x + m ; (x == m?(y+1)) ? ((y+1) ? n) y = y + 1 ; } (x == m?y) ? (y ? n) ((x == m?y) ? (y ? n)) ? ?(y n) ? (x == m?n) } x == m ? n 通过最弱前条件演算得到 * 程 序 验 证 实 例 n ? 0 void mult(int m, int n) { x = 0 ; y = 0 ; while (y n) do { (x == m?y) ? (y ? n) (x+m == m?(y+1)) ? ((y+1) ? n) x = x + m ; (x == m?(y+1)) ? ((y+1) ? n) y = y + 1 ; } (x == m?y) ? (y ? n) ((x == m?y) ? (y ? n)) ? ?(y n) ? (x == m?n) } x == m ? n * 程 序 验 证 实 例 n ? 0 void mult(int m, int n) { x = 0 ; y = 0 ; I ? E ? VC(S, I)（S是循环体） ((x ==m?y) ? (y ? n)) ? (y n) ? (x+m ==m?(y+1)) ? ((y+1) ?