Toward Software Verification with Theorem Provers

よくわかる定理証明：
Isabelle/HOLを用いた定理証明入門
南出靖彦
筑波大学システム情報工学研究科
1
定理証明系（証明支援系）
対象を論理的に形式化し、その性質を証明・検証

システム


Coq, PVS, Isabelle, HOL, ACL2
応用例




数学の証明：ラムダ計算
ハードウェアの検証
プログラミング言語：Javaの型システムの健全性
暗号プロトコルの安全性
2
Isabelle/HOL
高階論理の基づく定理証明系[Paulson , Nipkow]
 高階論理 (Higher-Order Logic)



関数プログラミング



論理演算子（Æ, !, 8, 9,…)
ラムダ計算
データ型
再帰関数
対話的証明環境

（部分的な）自動証明のサポート
3
構成要素

Isabelle : メタ論理（generic theorem prover)



Isabelle/HOL: 高階論理
Isar : 記述言語


オブジェクト論理（HOL)の推論規則を表現
人が書く証明に近い記述が可能
Proof General : ユーザインタフェース

(X)Emacs 上のインタフェース
4
概要





高階論理HOLとIsarによる証明
メタ論理と対話的証明
Isabelle/HOLによる関数プログラミング
応用例：算術式の評価とその性質の証明
Isabelle/HOLの使い方
5
HOLの論理
型付ラムダ計算に基づく論理
型
 ::= bool | nat |  )  | …
項
t ::= x | c | x.t
論理式
P ::= t | : P | P Æ P | P Ç P
| P ! P | 8 x.P | 9 x.P
ただし、t はbool型を持つ項
6
推論規則
導入規則
除去規則

Æ の除去規則は、通常の自然演繹とは異なる形をしている
実際に証明に使いやすいこの形の規則がIsabelle/HOLでは除去規則と呼ばれる
7
例：証明
自然言語による証明
A Æ B を仮定して B Æ A を証明する。 (!の導入)
A Æ B より B と A が成り立つ。
(Æの除去)
よって B Æ A が成り立つ。
(Æの導入)
8
証明図に対応する
Isabelleの証明
lemma "A Æ B ! B Æ A“
proof (rule impI)
assume "A Æ B“
show "B Æ A"
proof (rule conjE)
show "A Æ B"
by assumption
next
assume "A" "B"
show "B Æ A"
proof (rule conjI)
show "B" by assumption
show "A" by assumption
qed
この記述言語を Isar と言う
qed
qed
• 構造を持った証明を記述できる
9
簡素化した証明
仮定による証明の部分など簡素化
⇒ 人が書く証明に近いスタイルの証明
lemma "A Æ B ! B Æ A“
proof (rule impI)
assume "A Æ B“
thus "B Æ A"
proof (rule conjE)
assume "A" "B"
show "B Æ A"
by (rule conjI)
qed
qed
10
概要





高階論理HOLとIsarによる証明記述
メタ論理と対話的証明
Isabelle/HOLによる関数プログラミング
応用例：算術式の評価とその性質の証明
Isabelle/HOLの使い方
11
メタ論理：Isabelle

メタレベルの論理結合子

P )Q
P を仮定して Q を証明可能

P1 ) P2 ) …. ) Pn ) Q
P1 , P2 , …, Pn を仮定して Q を証明可能
[| P1 ; P2 ; …. ; Pn |] ) Q と書く

Æx. P x (メタレベルの8)
任意の x について P xが証明可能
12
スキーマテック変数

自由に代入できる変数 : ?A, ?B, ….
ÆA B. A Æ B
?A Æ ?B
13
推論規則
推論規則は、メタレベルの論理式で表現
impI : (?P ) ?Q) ) (?P ! ?Q)
conjI: [| ?P ; ?Q |] ) ?P Æ ?Q
conjE [| ?P Æ ?Q; [| ?P; ?Q |] ) ?R |] ) ?R
14
対話的証明（１）

証明する命題を入力



theory, lemma コマンド
入力された命題が示すべきゴールになる
proof コマンドでゴールを証明する方法を指定
⇒ 次に示すべきゴールが提示される
下の形のサブゴールが0個以上
[| P1 ; P2 ; …. ; Pn |] ) Q
15
対話的証明（２）

各サブゴールに対して




P1 , P2 , …., Pnをassume コマンドで仮定
Q をshowコマンドで証明
各サブゴールの証明は next コマンドで区切る
すべてのサーブゴールを証明したら qed
16
証明規則の適用

proof (rule 規則の名前）

規則の結論部分がゴールとマッチする場合に適用



マッチングには、高階単一化が用いられる
規則の仮定部分が次の証明すべきゴール（0個以上）
例

ゴール
A Æ (B Æ C)
規則 conjI: [| ?P ; ?Q |] ) ?P Æ ?Q

生成されるゴール



A
BÆC
17
例：規則の適用
証明
lemma "A Æ B ! B Æ A“
proof (rule impI)
assume "A Æ B“
show "B Æ A"
proof (rule conjE)
...
ゴール
A Æ B ) B Æ A
?P Æ ?Q
[|?P; ?Q |] ) B Æ A
この後、何らかのPとQに関して以下のゴールを示せばよい
P Æ Q
[|P; Q |] ) B Æ A
18
除去規則を用いた証明（１）
除去規則をruleで適用すると無駄がある

仮定や証明済みの事実ですぐに証明できるゴー
ルが生成される
lemma "A Æ B ! B Æ A“
proof (rule impI)
assume "A Æ B“
show "B Æ A"
proof (rule conjE)
show "A Æ B"
by assumption
19
除去規則を用いた証明（２）
除去規則を適用する仮定を明示
lemma "A Æ B ! B Æ A“
proof (rule impI)
assume AB: “A Æ B“
from AB
show "B Æ A"
proof (rule conjE)
仮定に名前を付ける
除去規則に用いる仮定
ゴール A Æ B は証明する必要がない
20
除去規則適用の仕組み
A Æ B を仮定して B Æ A を証明
• 除去規則を用いて仮定に含まる結合子を除去（分解）
仮定
AÆB
conjE: [| ?P Æ ?Q ; [| ?P; ?Q |] ) ?R |] ) ?R
ゴール
[| [| A; B |] ) ?R |] ) ?R
BÆA
この規則を適用
次のゴール [| A; B |] ) B Æ A
21
述語論理の証明： 8の証明

8 の導入規則
allI : (Æx. ?P x) ) (8x.?P x)
⇒ ゴールにメタ論理の全称記号 Æ が現れる

ゴール Æx.P x ) Q x の証明
fix a
assume “P a”
show “Q a”
….
xを変数aで表し固定
22
例： 8の証明
“8x. P x ) 8x. P (f x)”の証明
lemma assumes P: “8x. P x”
shows “8x. P (f x)”
proof (rule allI)
fix a
xをaで固定
from P
show “P (f a)”
by (rule allE)
残りのゴールは仮定で証明
qed
23
概要





高階論理HOLとIsarによる証明記述
メタ論理と対話的証明
Isabelle/HOLによる関数プログラミング
応用例：式の評価とその性質の証明
Isabelle/HOLの使い方について
24
Isabelle/HOLによる関数プログラミング
MLに近い関数プログラミングが可能
 多相型を持つ型システム
 言語機能




定数の定義
データ型
原始帰納関数
全域帰納関数
 停止性の証明が必要
必ず停止する関数のみを扱える
25
自然数に関するセオリー
自然数のセオリー
 型：nat
 定数： 0:nat, Suc : nat => nat
 基本的な関数（+,-, £）、関係（<, <=)

単純化（書き換え）規則が与えられている
単純化による証明例
lemma "(0 + Suc 0) * Suc (Suc 0) = Suc (Suc 0)"
by simp
26
原始帰納関数
下の形の定義で与えられる関数（2引数の場合）
例：加算の定義
consts
plus :: “nat => nat => nat”
primrec
"plus 0 y = y"
"plus (Suc x) y = Suc (plus x y)"
定数の型を定義
原始帰納関数の定義
27
データ型の定義
datatype 'a list = Nil ("[]")
| Cons 'a "'a list"

Consを表す右結合の中置記法として # を導入


(infixr "#" 65)
65は結合の強さ
データ型が定義されると帰納法の推論規則が導入され
る

例: list.induct
[| ?P []; Æ a list. ?P list ) ?P (a#list) |] ) ?P ?list
28
原始帰納関数の定義
consts
@ :: “‘a list => ’a list => ‘a list“
(infixr 65)
primrec
"[] @ ys = ys"
"(x#xs) @ ys = x # (xs @ ys)"

定義の等式が左辺から右辺への書き換え規則として導入さ
れる
29
帰納法による証明
補題を単純化に用いる
lemma [simp]: "xs @ [] = xs"
proof (induct xs)
xsに関する帰納法
show "[] @ [] = []"
by simp
next
fix x xs
assume "xs @ [] = xs"
show "(x # xs) @ [] = x # xs"
by (simp!)
仮定を用いた単純化
qed
30
帰納法による証明: 自動証明
lemma [simp]: "xs @ [] = xs"
by (induct xs, auto)
下の証明法を順番に適用することで証明できる


induct xs: xs に関する帰納法
auto : 単純化、推論規則を用いた自動証明
31
補題を用いた証明: rev (rev xs) = xs
consts rev :: "'a list => 'a list"
primrec
"rev [] = []"
“rev (x#xs) = rev xs @ (x#[])"
補題に名前を付ける
lemma app_assoc: "(xs @ ys) @ zs = xs @ (ys @ zs)"
by (induct xs,auto)
lemma rev_app: "rev (xs @ ys) = rev ys @ rev xs"
by (induct xs,auto simp add: app_assoc)
theorem "rev (rev xs) = xs"
by (induct xs,auto simp add: rev_app)
書き換え規則に追加
32
全域帰納関数

必ず停止する帰納関数を定義できる

再帰呼び出しのときに、引数がある意味で必ず小さく
なることを示すことが必要
consts
fib :: "nat => nat"
less_than :: ('a £ 'a) set
recdef fib “less_than"
整礎な関係を指定
"fib 0 = 0"
"fib (Suc 0) = 1"
"fib (Suc (Suc n)) = fib n + fib (Suc n)"
33
概要





高階論理HOLとIsarによる証明記述
メタ論理と対話的証明
Isabelle/HOLによる関数プログラミング
応用例：算術式の評価とその性質の証明
Isabelle/HOLの使い方
34
応用例 : 式
変数を含む算術式の形式化
例： (x + 10) - y
types var = nat
datatype exp =
|
|
|
型に別名を付ける
NatExp nat
VarExp var
PlusExp exp exp
MinusExp exp exp
注意: 変数を自然数で表している
35
応用例 : 評価関数
consts
eval :: “exp => (var => nat) => nat“
primrec
"eval (NatExp i) env = i"
"eval (VarExp x) env = env x"
"eval (PlusExp e1 e2) env = eval e1 env + eval e2 env"
"eval (MinusExp e1 e2) env = eval e1 env - eval e2 env"
36
応用例 : 自由変数
consts
fv :: "exp => var set“
t set ：要素が t 型の集合
primrec
"fv (NatExp i) = {}"
"fv (VarExp x) = {x}"
[ fv e2“
e1 [ fv e2"
"fv (PlusExp e1 e2) = fv e1
"fv (MinusExp e1 e2) = fv
37
応用例 : 証明例
lemma
“(8x. (x2fv exp ! env1 x = env2 x))
! eval exp env1 = eval exp env2“
by (induct exp, auto)

env1 と env2 が expの自由変数に関して同じ値を持つ
ならば、どちらで評価しても値は等しい
38
概要





高階論理HOLとIsarによる証明記述
メタ論理と対話的証明
Isabelle/HOLによる関数プログラミング
応用例：算術式の評価とその性質の証明
Isabelle/HOLに使い方
39
動作環境：Isabelle

Standard MLが動作するUNIX (Linux)

バイナリパッケージ




Linux/x86
Solaris/Sparc
Darwin/PPC (MacOS X)
非公式バージョン

MS-Windows

かなり機能に制限あり
40
スクリプトの全体構造 : theoryファイル
定義や証明のまとまり（theory）を “名前.thy”に書く
ファイル： Demo.thy
使用するtheory
theory Demo = T1+T2+…+Tn:
型、関数の定義、補題・定理の証明
end
使用するtheoryの部分は、通常はMain
Main : 自然数、リスト、集合、関係など定義されて
いるtheory
41
Proof Generalの使い方の基本
(X)Emacs上のユーザインタフェース


1ステップ進む : Ctl - x Ctl - n
1ステップ戻る : Ctl - x Ctl - u
42
記号の記法
二種類の記号の記法がある
ASCII
X-symbols
A ==> B
(メタレベルの含意）
A --> B
(HOL の含意）
A&B
A)B
\<Longrightarrow>
A!B
\<Longrightarrow>
AÆB
! x. A
8 x.A
43
X-symbolsによる記号の入力

Emacsのパッケージ X-symboｌs を用いて数学
記号の入力が可能


Emacsのメニュから選択
記号の名前を用いて入力


\<Longrightarrow>, <\and> …
略記を用いた入力

例： “-->” を入力すると ! が表示される
44
参考資料

Isabelle/HOLホームページ
http://www.cl.cam.ac.uk/Research/HVG/Isabelle/


開発者などが書いたチュートリアルのスライドなどもある
Isabelle/HOL : A Proof Assistant for HigherOrder Logic, Tobias Nipkow , Lawrence C.
Paulson and Markus Wenzel, LNCS 2283

異なるスタイルで証明が書かれている
45
参考資料

Introduction to HOL: A Theorem Proving
Environment for Higher Order Logic, M.J.C.
Gordon, T.F. Melham, 1993

定理証明系HOLの本だが、論理としてのHOLの説明
の部分は、非常に参考になる
46

Download Report