タグ

Coqに関するkabisukeのブックマーク (3)

  • Coq Tips

    以下、Parameters A B C P Q R : Prop. を仮定。 目次 前件 (仮定) が……の場合 仮定が False の場合・仮定に矛盾がある場合 仮定が否定の場合 (~A の形) 仮定が含意の場合 (A -> B の形) 仮定が連言の場合 (A /\ B の形) 仮定が選言の場合 (A \/ B の形) 仮定が全称量化子 (forall) の場合 仮定が存在量化子 (exists) の場合 後件 (ゴール) が……の場合 ゴールが True の場合 ゴールが False・否定の場合 ゴールが含意の場合 (A -> B の形) ゴールが連言の場合 (A /\ B の形) ゴールが選言の場合 (A \/ B の形) ゴールが全称量化子 (forall) の場合 ゴールが存在量化子 (exists) の場合 ゴールが恒真命題 (トートロジー)

    kabisuke
    kabisuke 2009/12/30
  • Coqによる証明駆動開発で Merge Sort プログラムをつくってみた - にわとり小屋でのプログラミング

    OCaml合宿で帰りの車の中でid:zyxwv さんにMergeSortの正しさをどうやって証明するか聞かれてとっさに証明できなかったので、合宿から帰ったあとに一生懸命証明してみた。 プログラムと証明の全体はこちら: yoshihiro503 / mergesort / source / — Bitbucket。 思ったより簡単ではなく、いろいろなテクニックが必要で非常に勉強になった。Coq初心者の人はMergeSortの問題をとりあえずの目標にして証明を頑張ると非常に効率がいいのではないかと思う。 私は、だいたい以下の流れでプログラムした。 Sortedという命題を作り、リストがソート済みであるという状態を定義する mergesort関数があるとして、満たすべき性質(i)を定理として記述する mergesort関数を定義する mergesort関数に必要な補助関数 merge関数を定義し

    Coqによる証明駆動開発で Merge Sort プログラムをつくってみた - にわとり小屋でのプログラミング
  • はじめての Coq - zyxwvの日記

    Coq などの定理証明系に興味を持っている人は少なくないと思うのですが、やっぱり最初の一歩を踏み出すのは大変。web 上の Coq チュートリアルは、Coq 処理系の機能を説明しているだけで、数学の素養がない人(普通の情報系の学生)が実際に関数の性質を証明するためにどうしたらいいかが書いてあるわけじゃないし。 だって「(a -> b -> c) -> (a -> b) -> a -> c" を証明してみましょう」とか言われても全然やる気にならないじゃん。そんなことを証明するために Coq を使いたいわけじゃない! そんなわけで、ocaml-nagoya の合宿の機会を利用して id:yoshihiro503 さんと id:suer さんに、Coq をプログラミング言語として使う場合の基を教えてもらってきました。特に id:yoshihiro503 さんは少なくとも僕から見ると Coq M

    はじめての Coq - zyxwvの日記
  • 1