Share
Embed
Transcript
16 slides
-
sou7といいます 学部2年 Zli 次期副代表 GDSC(Google Developer Student Community) Aizu Lead
プログラミング言語触ったりしてます Twitter : @sou7___ Github : @soukouki . やぁ > 2 -
実際に見てみよう この命題を関数に落とすと (p -> q) -> p -> q という型を持つ関数(変数)を定義す
ることになります。 modusPonens :: (p -> q) -> p -> q modusPonens hpq hp = hpq hp (P → Q) → P → Q 6 -
もうちょっと違う例で見てみましょう。 に対応する型は、 ((A -> B), (B -> C)) -> (A
-> C) です。 syllogism :: ((a -> b), (b -> c)) -> (a -> c) syllogism (hab, hbc) ha = hbc (hab ha) (A → B) ∧ (B → C) → (A → C) 7 -
ド・モルガンの法則の一部は、こんなふうに書けます。 import Data.Void and_l :: (p, q) -> p and_l
(hp, _) = hp and_r :: (p, q) -> q and_r (_, hq) = hq deMorgan :: (Either (p -> Void) (q -> Void)) -> ((p, q) -> Void) deMorgan (Left hnp) = hnp . and_l deMorgan (Right hnq) = hnq . and_r ¬P ∨ ¬Q → ¬(P ∧ Q) 8 -
じゃぁCoqだとどんなふうに証明するの? これまではHaskellでの証明を見てきましたが、証明の割にとてもややこしいコードに なってしまいます。 そこでCoqは、タクティックと呼ばれる構文を使うことで、証明を簡単に書けるよう にしました。 Theorem ModusPonens (P Q: Prop):
(P -> Q) -> P -> Q. Proof. move=> Hpq Hp. (* Proof.からQed.までの3行がタクティック *) apply Hpq. apply Hp. Qed. (このコードはSSReflectのタクティックを使っているため、実際にはSSReflectをイン ポートする必要があります。) 9 -
(* (2.3)' *) Theorem subsets_cap: forall A B C, C
\subset A -> C \subset B -> C \subset A \cap B. Proof. move=> A B C HC_subset_A HC_subset_B x. split. - by apply HC_subset_A. - by apply HC_subset_B. Qed. (* (2.4)' *) Theorem cap_diag: forall A, A \cap A = A. Proof. move=> A. apply eq_subset' => x; rewrite -cap_and. - by case. - by split => //. Qed. 11 -
1. 定理の証明の検証 数学の証明の中には、いくつか「証明の正しさを保証できない」ものが存在します。 ABC予想 なんか他にもあるやろ そのような証明に対して、形式的な言語を使い機械的に検証することで、証明が本当 に正しいことを検証します。定理証明支援系で行われた形式証明として、以下のもの があります。 四色定理 奇数位数定理
この定理の証明のために作られたライブラリ(MathComp)が今も広く使われてい ます。 ケプラー予想 Coqと同じ定理証明支援系である、Isabelle/HOLを使って証明されています。 13 -
2. 安全なソフトウェアの開発 プログラムがバグなく動くことを保証したいときに、どんな手段があるでしょうか。 1. ソースコードとにらめっこする 2. 型をつける => 例えばクイックソートなんかでは、型は合っていてもバグがあるかも・・・ (その条件式、本当に合ってる?)
3. テストを書く => 全パターンはチェックできない! 4. 形式的に証明をする => ソースコードが仕様を満たしていることを保証できます!! 14 -
まとめ おすすめの本・サイト 「Coq/SSReflect/MathCompによる定理証明」 https://www.morikita.co.jp/books/mid/006241 「ソフトウェアの基礎」 日本語版 https://www.chiguri.info/sfja/lf/toc.html 上の本を読み進めながらサイトの演習問題を解く流れが安定すると思います! 参考文献 「計算と論理」配布資料
「カリー・ハワード同型対応」 https://www.fos.kuis.kyoto-u.ac.jp/~igarashi/class/cal21w/ch.pdf 15