|
|
|
這本實用的教科書適用於形式化方法的入門課程或高級課程。本書以B形式化方法的一個擴展Event-B作為工具，展示了一種完成系統建模和設計的數學方法。
簡-埃蒙德·阿布瑞爾（Jean-Raymond Abrial）是國際著名電腦科學家，曾任蘇黎世聯邦理工學院客座教授，他基於精化的思想提出了一種系統化的方法，教讀者如何逐步構造出所期望的模型，並通過嚴格的證明完成對所構造模型做系統化的推理。
本書將介紹如何根據實際需要去構造各種程式，以及如何更為普遍地構造各種離散系統的模型。
本書提供了大量的示例，這些示例源自電腦系統開發的各個領域，包括順序程式、併發程式和電子線路等。
本書還包含了大量具有不同難度的練習和開發專案。書中的每個例子都用Rodin平臺工具集證明過。
本書適合作為高等院校電腦、軟體工程、網路工程、資訊安全等專業高年級本科生、研究生的教材，也可供相關領域的研究人員和技術人員參考。
簡-埃蒙德·阿布瑞爾（Jean-Raymond Abrial）法國電腦科學家，國際知名的形式化方法和軟體工程專家，歐洲科學院院士。20世紀80年代，他先後開發了著名的Z語言和B方法。2000年以後，他開發了Event-B方法，並領導一個國際團隊，在歐盟專案支持下，為Event-B開發了公開免費的Rodin平臺。這些語言和方法被國際形式化方法領域廣泛接受和使用，並被開發工作者應用于軟體和其他系統的實際開發工作。阿布瑞爾教授長期致力於推動和參與形式化方法的工業應用，指導了B方法在軌道交通領域的最早開發工作，在相關領域做出了卓越的貢獻。阿布瑞爾教授與國內一些高校和研究單位有長期而密切的合作關係，並於2016年獲得了中華人民共和國國務院頒發的“中華人民共和國國際科學技術合作獎”。
第1章 引言 1
1．1 動機 1
1．2 各章概覽 2
1．3 如何用這本書 6
1．4 形式化方法 8
1．5 一個小迂回：藍圖 9
1．6 需求文檔 10
1．6．1 生命週期 10
1．6．2 需求文檔的困難 10
1．6．3 一種有用的比較 11
1．7 本書中使用的“形式化方法”的定義 12
1．7．1 複雜系統 12
1．7．2 離散系統 13
1．7．3 測試推理與模型（藍圖）推理 13
1．8 有關離散模型的非形式化概覽 14
1．8．1 狀態和遷移 14
1．8．2 操作性解釋 14
1．8．3 形式化推理 15
1．8．4 管理閉模型的複雜性 15
1．8．5 精化 15
1．8．6 分解 16
1．8．7 泛型開發 16
1．9 參考資料 17
第2章 控制橋上的汽車 18
2．1 引言 18
2．2 需求文檔 18
2．3 精化策略 20
2．4 初始模型：限制汽車的數量 20
2．4．1 引言 20
2．4．2 狀態的形式化 21
2．4．3 事件的形式化 22
2．4．4 前-後謂詞 23
2．4．5 證明不變式的保持性質 23
2．4．6 相繼式 25
2．4．7 應用不變式保持性的規則 25
2．4．8 證明義務的證明 26
2．4．9 推理規則 27
2．4．10 元變數 29
2．4．11 證明 29
2．4．12 更多推理規則 30
2．4．13 改造兩個事件：引進衛 31
2．4．14 改造的不變式保持規則 31
2．4．15 重新證明不變式的保持性 32
2．4．16 初始化 33
2．4．17 初始化事件init的不變式建立規則 33
2．4．18 應用不變式建立規則 34
2．4．19 證明初始化的證明義務：更多推理規則 34
2．4．20 無鎖死 35
2．4．21 無鎖死規則 35
2．4．22 應用無鎖死證明義務規則 35
2．4．23 更多推理規則 36
2．4．24 證明無鎖死的證明義務 37
2．4．25 對初始模型的總結 38
2．5 第 一次精化：引入單行橋 38
2．5．1 引言 38
2．5．2 狀態的精化 39
2．5．3 精化抽象事件 40
2．5．4 重溫前-後謂詞 40
2．5．5 精化的非形式化證明 41
2．5．6 證明抽象事件的正確精化 42
2．5．7 應用精化規則 43
2．5．8 精化初始化事件init 45
2．5．9 初始化事件init精化正確性的證明義務規則 46
2．5．10 應用初始化精化的證明義務規則 46
2．5．11 引入新事件 46
2．5．12 空動作skip 47
2．5．13 證明兩個新事件的正確性 47
2．5．14 證明新事件的收斂性 49
2．5．15 應用非收斂證明義務規則 50
2．5．16 相對無鎖死 51
2．5．17 應用相對無鎖死證明義務規則 51
2．5．18 更多推理規則 52
2．5．19 第 一個精化的總結 54
2．6 第二次精化：引入交通燈 55
2．6．1 精化狀態 55
2．6．2 精化抽象事件 56
2．6．3 引進新事件 56
2．6．4 疊加：調整精化規則 57
2．6．5 證明事件的正確性 58
2．6．6 更多邏輯推理規則 58
2．6．7 試探性的證明和解 58
2．6．8 新事件的收斂性 64
2．6．9 相對無鎖死 67
2．6．10 第二個精化的總結 68
2．7 第三次精化：引入車輛感測器 70
2．7．1 引言 70
2．7．2 精化狀態 72
2．7．3 精化控制器裡的抽象事件 75
2．7．4 在環境裡增加新事件 77
2．7．5 新事件的收斂性 78
2．7．6 無鎖死 78
第3章 衝壓機控制器 79
3．1 非形式描述 79
3．1．1 基本設備 79
3．1．2 基本命令和按鈕 80
3．1．3 基本用戶動作 80
3．1．4 用戶工作期 80
3．1．5 危險：控制器的必要性 80
3．1．6 安全門 81
3．2 設計模式 81
3．2．1 動作和反應 82
3．2．2 第 一種情況：一個簡單的動作反應模式，無反作用 83
3．2．3 第二種情況：一個簡單的動作模式，一次重複動作和反應 86
3．3 衝壓機的需求 90
3．4 精化策略 91
3．5 初始模型：連接控制器和電動機 92
3．5．1 引言 92
3．5．2 建模 92
3．5．3 事件的總結 94
3．6 第 一次精化：把電動機按鈕連接到控制器 94
3．6．1 引言 94
3．6．2 建模 95
3．6．3 加入“假”事件 99
3．6．4 事件的總結 100
3．7 第二次精化：連接控制器到離合器 100
3．8 另一個設計模式：兩個強反應的弱同步 101
3．8．1 引言 101
3．8．2 建模 103
3．9 第三次精化：約束離合器和電動機 108
3．10 第四次精化：連接控制器到安全門 110
3．10．1 拷貝 110
3．10．2 事件的總結 110
3．11 第五次精化：約束離合器和安全門 110
3．12 另一設計模式：兩個強反應的強同步 111
3．12．1 引言 111
3．12．2 建模 112
3．13 第六次精化：離合器和安全門之間的更多約束 117
3．14 第七次精化：把控制器連接到離合器按鈕 118
3．14．1 拷貝 118
3．14．2 事件的總結 118
第4章 簡單檔案傳輸通訊協定 120
4．1 需求 120
4．2 精化策略 120
4．3 協定的初始模型 121
4．3．1 狀態 122
4．3．2 一些數學標記法 122
4．3．3 事件 125
4．3．4 證明 125
4．4 協議的第 一次精化 127
4．4．1 非形式化的說明 127
4．4．2 狀態 128
4．4．3 更多數學符號 128
4．4．4 事件 130
4．4．5 精化證明 131
4．4．6 事件receive的收斂性證明 134
4．4．7 相對無鎖死證明 135
4．5 協議的第二次精化 135
4．5．1 狀態和事件 135
4．5．2 證明 137
4．6 協議的第三次精化 137
4．6．1 狀態 137
4．6．2 事件 138
4．6．3 全稱量化謂詞的推理規則 138
4．7 對開發的回顧 139
4．7．1 動機和預期事件的引入 139
4．7．2 初始模型 140
4．7．3 第 一次精化 140
4．7．4 第二次精化 141
4．7．5 第三次精化 141
4．8 參考資料 142
第5章 Event-B建模語言和證明義務規則 143
5．1 Event-B標記法 143
5．1．1 引言：機器和上下文 143
5．1．2 機器和上下文的關係 143
5．1．3 上下文的結構 144
5．1．4 上下文的例子 145
5．1．5 機器的結構 145
5．1．6 機器的例子 146
5．1．7 事件 147
5．1．8 動作 147
5．1．9 事件的例子 149
5．2 證明義務規則 150
5．2．1 引言 150
5．2．2 不變式保持證明義務規則：INV 151
5．2．3 可行性證明義務規則：FIS 153
5．2．4 衛加強證明義務規則：GRD 153
5．2．5 衛歸併證明義務規則：MRG 154
5．2．6 類比證明義務規則：SIM 155
5．2．7 數值變動式證明義務規則：NAT 158
5．2．8 有窮集變動式證明義務規則：FIN 158
5．2．9 變動量證明義務規則：VAR 159
5．2．10 非確定性見證證明義務規則：WFIS 161
5．2．11 定理證明義務規則：THM 162
5．2．12 良好定義證明義務規則：WD 162
第6章 有界重傳協議 163
6．1 有界重傳協議的非形式說明 163
6．1．1 正常行為 163
6．1．2 不可靠的通信 163
6．1．3 協議流產 164
6．1．4 交替位 164
6．1．5 協定的最後情況 164
6．1．6 BRP的偽代碼描述 165
6．1．7 有關偽代碼的說明 167
6．2 需求文檔 167
6．3 精化策略 168
6．4 初始模型 169
6．4．1 狀態 169
6．4．2 事件 169
6．5 第 一次和第二次精化 170
6．5．1 狀態 170
6．5．2 第 一次精化的事件 170
6．5．3 第二次精化的事件 171
6．6 第三次精化 171
6．6．1 狀態 172
6．6．2 事件 172
6．6．3 事件之間的同步 173
6．7 第四次精化 173
6．7．1 狀態 173
6．7．2 事件 174
6．7．3 事件的同步 175
6．8 第五次精化 176
6．8．1 狀態 176
6．8．2 事件 177
6．8．3 事件的同步 180
6．9 第六次精化 181
6．10 參考資料 181
第7章 一個併發程式的開發1 182
7．1 分散式和併發程式的比較 182
7．1．1 分散式程式 182
7．1．2 併發程式 182
7．2 提出的實例 183
7．2．1 非形式的說明 183
7．2．2 非併發的場景展示 185
7．2．3 定義原子性 186
7．3 交錯 187
7．3．1 問題 187
7．3．2 計算不同交錯的數目 188
7．3．3 結果 189
7．4 併發程式的規範描述 190
7．4．1 寫和讀的軌跡 190
7．4．2 軌跡之間的關係 190
7．4．3 不變式的總結 193
7．4．4 事件 193
7．5 精化策略 194
7．5．1 最終精化的梗概 194
7．5．2 精化的目標 196
7．6 第 一次精化 196
7．6．1 讀者狀態 196
7．6．2 讀事件 197
7．6．3 寫者狀態 198
7．6．4 寫事件 198
7．7 第二次精化 200
7．7．1 狀態 200
7．7．2 事件和新增的不變式 200
7．8 第三次精化 203
7．8．1 狀態 203
7．8．2 事件 203
7．9 第四次精化 204
7．9．1 狀態 204
7．9．2 事件 205
7．10 參考資料 206
第8章 電路的開發 207
8．1 引言 207
8．1．1 同步電路 207
8．1．2 電路與其環境的耦合 208
8．1．3 耦合的動態觀點 208
8．1．4 耦合的靜態觀點 209
8．1．5 協調性條件 209
8．1．6 一個警告 210
8．1．7 電路的最終構造 210
8．1．8 一個非常小的示例 213
8．2 第 一個例子 214
8．2．1 非形式的規範描述 214
8．2．2 初始模型 215
8．2．3 精化電路以減少其非確定性 218
8．2．4 通過改變資料空間來精化電路 220
8．2．5 構造最後的電路 222
8．3 第二個例子：仲裁器 225
8．3．1 非形式的規範描述 225
8．3．2 初始模型 226
8．3．3 第 一次精化：讓電路生成二進位輸出 229
8．3．4 第二次精化 231
8．3．5 第三次精化：消除電路的非確定性 233
8．3．6 第四次精化：構造最後的電路 234
8．4 第三個例子：一種特殊的道路交通燈 234
8．4．1 非形式的規範描述 235
8．4．2 關注點分離的方法 235
8．4．3 優先權電路：初始模型 236
8．4．4 最後的Priority電路 238
8．5 Light電路 240
8．5．1 一個抽象：Upper電路 241
8．5．2 精化：加入Lower電路 242
8．6 參考資料 245
第9章 數學語言 246
9．1 相繼式演算 246
9．1．1 定義 246
9．1．2 一個數學語言的相繼式 248
9．1．3 初始理論 248
9．2 命題語言 249
9．2．1 語法 249
9．2．2 初始理論的擴充 250
9．2．3 派生規則 250
9．2．4 方法論 252
9．2．5 命題語言的擴充 252
9．3 謂詞語言 253
9．3．1 語法 253
9．3．2 謂詞和運算式 254
9．3．3 全稱量詞的推理規則 254
9．4 相等謂詞 256
9．5 集合論語言 257
9．5．1 語法 258
9．5．2 集合論公理 258
9．5．3 基本集合運算子 259
9．5．4 基本集合運算子的推廣 260
9．5．5 二元關係運算子 261
9．5．6 函數運算子 264
9．5．7 各種箭頭的總結 265
9．5．8 lambda抽象和函式呼叫 265
9．6 布林和算術語言 266
9．6．1 語法 266
9．6．2 皮阿諾公理和遞迴定義 267
9．6．3 算術語言的擴充 267
9．7 高級資料結構 269
9．7．1 反自反的傳遞閉包 269
9．7．2 強連通圖 270
9．7．3 無窮表 271
9．7．4 有窮表 274
9．7．5 環 276
9．7．6 無窮樹 277
9．7．7 有窮深度樹 280
9．7．8 自由樹 281
9．7．9 良定義條件和有向無環圖 283
第10章 環狀網路上選領導 284
10．1 需求文檔 284
10．2 初始模型 286
10．3 討論 286
10．3．1 第 一個嘗試 286
10．3．2 第二個嘗試 287
10．3．3 第三個嘗試 287
10．3．4 解的非形式化展示 287
10．4 第 一次精化 288
10．4．1 狀態：環的形式化 288
10．4．2 狀態：變數 289
10．4．3 事件 289
10．5 證明 289
10．5．1 事件elect的證明 290
10．5．2 事件accept的證明 291
10．5．3 事件reject的證明 293
10．5．4 新事件不發散的證明 293
10．5．5 無鎖死的證明 293
10．6 參考資料 294
第11章 樹形網路上的同步 295
11．1 引言 295
11．2 初始模型 296
11．2．1 狀態 296
11．2．2 事件 297
11．2．3 證明 297
11．3 第 一次精化 298
11．3．1 狀態 298
11．3．2 事件 300
11．3．3 證明 300
11．4 第二次精化 301
11．5 第三次精化 303
11．5．1 事件ascending的精化 303
11．5．2 事件descending的精化 304
11．5．3 證明定理thm3_4 306
11．5．4 證明不變式inv3_3的保持性 306
11．6 第四次精化 308
11．7 參考資料 310
第12章 移動代理的路由演算法 311
12．1 問題的非形式化描述 311
12．1．1 抽象的非形式化描述 311
12．1．2 第 一個非形式化的精化 312
12．1．3 第二個非形式化的精化 312
12．1．4 第三個非形式化的精化：解 314
12．2 初始模型 315
12．2．1 狀態 315
12．2．2 事件 316
12．2．3 證明 317
12．3 第 一次精化 318
12．3．1 狀態 318
12．3．2 事件 319
12．3．3 證明 320
12．4 第二次精化 320
12．4．1 狀態 320
12．4．2 事件 322
12．4．3 證明 323
12．5 第三次精化：數據精化 324
12．5．1 狀態 324
12．5．2 事件 324
12．5．3 證明 325
12．6 第四次精化 325
12．7 參考資料 325
第13章 在連通圖網路上選領導 326
13．1 初始模型 326
13．1．1 狀態 326
13．1．2 事件 327
13．2 第 一次精化 327
13．2．1 定義自由樹 327
13．2．2 擴充狀態 327
13．2．3 事件的第 一次精化 328
13．2．4 第 一次精化的證明 329
13．3 第二次精化 329
13．3．1 第二次精化的狀態 329
13．3．2 事件 329
13．3．3 證明 330
13．4 第三次精化：競爭問題 330
13．4．1 引言 330
13．4．2 處理競爭的狀態 331
13．4．3 處理競爭的事件 332
13．5 第四次精化：簡化 332
13．6 第五次精化：引入基數 333
第14章 證明義務的數學模型 335
14．1 引言 335
14．2 不變式保持性的證明義務規則 335
14．3 觀察離散遷移系統的演化：跡 337
14．3．1 第 一個例子 338
14．3．2 跡 338
14．3．3 跡的特徵 339
14．3．4 演化圖 339
14．3．5 數學表示 339
14．4 用跡表示簡單精化 340
14．4．1 第二個例子 340
14．4．2 比較這兩個例子 341
14．4．3 簡單精化：非形式化的方法 342
14．4．4 簡單精化：形式化定義 342
14．4．5 考慮個別的事件 343
14．4．6 外部變數和內部變數 344
14．4．7 外部集合 345
14．5 廣義精化的集合論表示 345
14．5．1 引言 346
14．5．2 精化的形式化定義 347
14．5．3 精化的充分條件：前向模擬 347
14．5．4 精化的另一充分條件：反向模擬 352
14．5．5 跡的精化 352
14．6 打破抽象和具體事件之間的一對一關聯性 353
14．6．1 分裂抽象事件 353
14．6．2 合併幾個抽象事件 353
14．6．3 引進新事件 354
第15章 順序程式的開發 357
15．1 開發順序程式的一種系統化方法 357
15．1．1 順序程式的組成部分 357
15．1．2 把順序程式分解為獨立的事件 358
15．1．3 方法梗概 359
15．1．4 順序程式的規範：前條件和後條件 359
15．2 一個非常簡單的例子 360
15．2．1 規範 360
15．2．2 精化 361
15．2．3 推廣 362
15．3 合併規則 362
15．4 例：排序陣列裡的二分檢索 363
15．4．1 初始模型 363
15．4．2 第 一次精化 364
15．4．3 第二次精化 365
15．4．4 合併 366
15．5 例：自然數陣列中的最小值 366
15．5．1 初始模型 366
15．5．2 第 一次精化 367
15．6 例：陣列劃分 367
15．6．1 初始模型 367
15．6．2 第 一次精化 368
15．6．3 合併 370
15．7 例：簡單排序 370
15．7．1 初始模型 370
15．7．2 第 一次精化 371
15．7．3 第二次精化 371
15．7．4 合併 373
15．8 例：陣列反轉 373
15．8．1 初始模型 373
15．8．2 第 一次精化 374
15．9 例：連結表反轉 375
15．9．1 初始模型 375
15．9．2 第 一次精化 376
15．9．3 第二次精化 377
15．9．4 第三次精化 378
15．9．5 合併 378
15．10 例：計算平方根的簡單數值程式 378
15．10．1 初始模型 379
15．10．2 第 一次精化 379
15．10．3 第二次精化 379
15．11 例：內射數值函數的逆 380
15．11．1 初始模型 380
15．11．2 第 一次精化 381
15．11．3 第二次精化 382
15．11．4 產生實體 383
15．11．5 第 一次產生實體 383
15．11．6 第二次產生實體 384
第16章 位置存取控制器 385
16．1 需求文檔 385
16．2 討論 387
16．2．1 控制的共用 387
16．2．2 閉模型的構造 387
16．2．3 設備的行為 388
16．2．4 處理安全問題 388
16．2．5 同步問題 388
16．2．6 邊界的功能 388
16．3 系統的初始模型 389
16．4 第 一次精化 390
16．4．1 狀態和事件 390
16．4．2 無鎖死 391
16．4．3 第 一個解 392
16．4．4 第二個解 393
16．4．5 無鎖死的修正 393
16．5 第二次精化 394
16．5．1 狀態和事件 394
16．5．2 同步 396
16．5．3 證明 396
16．5．4 讀卡器持續阻塞的危險 396
16．5．5 避免持續阻塞的提議 396
16．5．6 最後的決定 397
16．6 第三次精化 397
16．6．1 引進讀卡器 397
16．6．2 與通信網路有關的假設 398
16．6．3 變數和不變式 398
16．6．4 事件 399
16．6．5 同步 400
16．6．6 證明 400
16．7 第四次精化 400
16．7．1 與物理門有關的決策 400
16．7．2 變數和不變式：綠色鏈 401
16．7．3 變數和不變式：紅色鏈 401
16．7．4 事件 402
16．7．5 同步 404
第17章 列車系統 406
17．1 非形式的引言 406
17．1．1 非形式描述的方法論約定 407
17．1．2 行車調度員控制下的軌道網路 407
17．1．3 網路的特殊元件：道岔和交叉點 407
17．1．4 阻塞的概念 409
17．1．5 通路的概念 409
17．1．6 信號的概念 411
17．1．7 通路和阻塞保持 412
17．1．8 安全性條件 414
17．1．9 運行條件 415
17．1．10 列車的假設 415
17．1．11 事故 416
17．1．12 實例 417
17．2 精化策略 420
17．3 初始模型 420
17．3．1 狀態 420
17．3．2 事件 425
17．4 第 一次精化 427
17．4．1 狀態 427
17．4．2 事件 429
17．5 第二次精化 431
17．5．1 狀態 432
17．5．2 事件 432
17．6 第三次精化 433
17．6．1 狀態 433
17．6．2 事件 433
17．7 第四次精化 434
17．8 總結 436
17．9 參考資料 437
第18章 一些問題 438
18．1 練習 438
18．1．1 銀行 438
18．1．2 生日記錄冊 438
18．1．3 有一行為0的數值矩陣 439
18．1．4 有序矩陣檢索 439
18．1．5 名人問題 439
18．1．6 在兩個有交集的有窮數值集合裡找公共元素 440
18．1．7 簡單的存取控制系統 441
18．1．8 簡單的圖書館 441
18．1．9 簡單的電路 441
18．1．10 鬧鐘 442
18．1．11 連續信號的分析 442
18．2 項目 443
18．2．1 旅館的電子鑰匙系統 443
18．2．2 Earley分析器 444
18．2．3 Schorr-Wait演算法 446
18．2．4 線性表封裝 447
18．2．5 佇列的併發訪問 447
18．2．6 幾乎線性的排序 448
18．2．7 終止性檢查 449
18．2．8 分散式互斥 449
18．2．9 電梯 452
18．2．10 業務交易協定 453
18．3 數學的開發 454
18．3．1 良構集合和關係 454
18．3．2 不動點 456
18．3．3 遞迴 457
18．3．4 傳遞閉包 457
18．3．5 篩檢程式和超篩檢程式 458
18．3．6 拓撲 458
18．3．7 Cantor-Bernstein定理 460
18．3．8 Zermelo定理 460
18．4 參考資料 462
