●第 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 &nb變量 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 &nbs關繫運算符 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