形式化方法导论

第1章 绪论

1.1 形式化方法的发展历程

1.2 形式化方法的基本内容

1.2.1 系统建模

1.2.2 形式规约

1.2.3 形式验证

1.3 本章小结

习题1

第2章 程序正确性证明

2.1 前后断言法

2.1.1 基本概念

2.1.2 证明方法

2.1.3 应用举例

2.2 公理化方法

2.2.1 基本概念

2.2.2 证明方法

2.2.3 应用举例

2.3 最弱前置条件方法

2.3.1 基本概念

2.3.2 证明方法

2.3.3 应用举例

2.4 本章小结

习题2

上篇 系统建模

第3章 迁移系统

3.1 基本概念

3.1.1 形式定义

3.1.2 迁移图

3.1.3 计算

3.2 应用举例

3.2.1 时序电路

3.2.2 数据依赖系统

3.2.3 并发和交错

3.3 本章小结

习题3

第4章 自动机

4.1 有穷自动机

4.1.1 有穷状态系统

4.1.2 形式定义

4.1.3 判定算法

4.2 Buchi自动机

4.2.1 ω—有穷自动机简介

4.2.2 Buchi自动机

4.2.3 应用举例

4.3 本章小结

习题4

第5章 Petri网

5.1 库所／变迁Petri网

5.1.1 基本概念

5.1.2 基本性质

5.1.3 分析方法

5.1.4 应用举例

5.2 谓词／变迁Petri网

5.2.1 基本概念

5.2.2 应用举例

5.3 着色Petri网

5.3.1 基本概念

5.3.2 应用举例

5.4 本章小结

习题5

中篇 形式规约

第6章 时序逻辑

6.1 线性时序逻辑

6.1.1 LTL语法

6.1.2 LTL语义

6.1.3 应用举例

6.2 分支时序逻辑

6.2.1 CTL语法

6.2.2 CTL语义

6.2.3 应用举例

6.3 区间时序逻辑简介

6.4 本章小结

习题6

第7章 并发系统属性

7.1 基本概念

7.2 安全性

7.2.1 形式定义

7.2.2 形式描述

7.2.3 应用举例

7.3 活性

7.3.1 形式定义

7.3.2 形式描述

7.3.3 应用举例

7.4 本章小结

习题7

下篇 形式验证

第8章 演绎证明

8.1 演绎证明方法

8.1.1 PLTL逻辑系统

8.1.2 Manna—Pnueli演绎规则方法

8.1.3 验证图方法

8.1.4 应用举例

8.2 验证工具STeP

8.2.1 STeP简介

8.2.2 STeP使用

8.3 STeP应用举例

8.3.1 建模

8.3.2 验证

8.4 本章小结

习题8

第9章 模型检测

9.1 基本概念

9.2 模型检测算法

9.2.1 CTL模型检测算法

9.2.2 LTL模型检测算法

9.3 模型检测工具及应用

9.3.1 验证工具SPIN

9.3.2 应用举例

9.4 本章小结

习题9

第10章 符号模型检测

10.1 二叉决策图

10.1.1 基本概念

10.1.2 约简方法

10.1.3 Apply操作及应用

10.2 CTL符号模型检测

10.2.1 基本方法

10.2.2 验证工具SMV

10.2.3 应用举例

10.3 LTL符号模型检测简介

10.4 本章小结

习题10

第11章 概率模型检测

11.1 概率模型

11.1.1 离散时间马尔可夫链

11.1.2 马尔可夫决策过程

11.1.3 连续时间马尔可夫链

11.2 概率时序逻辑

11.2.1 概率计算树逻辑

11.2.2 连续随机逻辑

11.3 概率模型检测工具及应用

11.3.1 验证工具PRISM

11.3.2 应用举例

11.4 本章小结

习题l1

第12章 实时与混成系统验证

12.1 时间自动机

12.1.1 语法

12.1.2 语义

12.2 实时逻辑

12.2.1 时间计算树逻辑

12.2.2 度量区间时序逻辑

12.3 实时系统模型检测

12.3.1 基本方法

12.3.2 验证工具UPPAAL

12.3.3 应用举例

12.4 混成系统验证简介

12.4.1 混成自动机

12.4.2 微分动态逻辑

12.4.3 混成系统模型检测

12.5 本章小结

习题12

参考文献

形式化方法是指有严格数学基础的软件和系统开发方法，支持软件与系统的规约、设计、验证与演化等活动。随着软件可信需求的不断增长，形式化方法的重要性和关注度日益提高。全书共12章，第1章概述形式化方法，第2章介绍形式化方法发展早期的经典内容，其余部分共分3篇：上篇（第3～5章）为系统建模篇，着重介绍迁移系统、有穷自动机、Petri网等基本计算模型；中篇（第6和第7章）为形式规约篇，着重讨论时序逻辑及其在并发系统属性描述的应用；下篇（第8～12章）为形式验证篇，除介绍演绎证明方法外，着重介绍验证并发、实时及混成系统的各种模型检测方法及相关验证工具。全书提供了大量应用实例，每章后均附有习题。本书适合作为高等院校计算机、软件工程、网络工程、信息安全、自动化等专业高年级本科生、研究生的教材，同时可供相关领域的研究人员和技术开发人员参考。

《"十二五"江苏省高等学校重点教材·21世纪高等学校计算机专业实用规划教材:形式化方法导论》适合作为高等院校计算机、软件工程、网络工程、信息安全、自动化等专业高年级本科生、研究生的教材，同时可供相关领域的研究人员和技术开发人员参考。