[WIP]TODO多めのまま公開します。別に書いてた下書きが消えたので。定理証明のコンテストシステムを作って、今日の夕方に第1回のコンテストを開催していた。2019年8月18日これです。定理証明コンテストとは,定理証明支援系を用いて与えられた定理に対して証明を与えるコンテストです。現在コンテストサイトに実装されている支援系はCoqです。Coqで解く問題の見た目はこんなかんじです。*)Qed.これはn×(m+1)とn+(n×m)が任意の自然数n,mについて等しいことを示せというものです。HEREの部分にCoqの言葉で証明を与えます。この問題を通そう環境準備Coqのインストールをしたのち,Coqをインタラクティブに使うツールを用意します。ツールにはEmacs+ProofGeneralが最も標準的です。WindowsではCoqIDEを使う方法もあります。現在バグだらけで使い物になりません。その方法をおすすめすることはできません。Emacs+Spacemacs+ProofGeneral導入記事は後で書くことにします。TODOここでは他の選択肢として,macでvscode+vscoqを用いる方法を説明します。最新のvscodeでは正常に動作しません。2年前ぐらいのvscodeをダウンロードして利用しましょう。2018vscodeでvscoq拡張をインストールします。して*.vファイルを開くと,次の証明画面が出ます。TODO定義というわけでこの命題を示しましょう。m.定理の証明にはまず定義を観察することが大事です。ドキュメントに定義があります。Coq上でも定義を見ることができます。nat.natという集合は,次の2つのコンストラクタから生み出されるものである。コンストラクタ"O"は無引数でnatである。コンストラクタ"S"はnatを引数に取ることでnatである。O)なんかがnatで有ることがわかります。これが我々の良く知る自然数であるところの0や2に対応しています。O)のエイリアスです。nat_scope.と再帰的に定義されています。matchは関数型言語ではおなじみのパターンマッチです。その先の項を返します。O)と読むことに注意してください。演算子のほうが関数適用っぽいものより優先度が弱いです。O)))))という感じです。Coqは便利で,具体的な例の計算ならやってくれます。実際に証明を行っています。coqでは定理の証明を次の形で書きます。証明tacticの列Qed.Proof.のあとに続くのは証明のtacticというものです。証明の状態を変化させます。証明するべきものである「ゴール」の列です。ゴールとは次の形で表されます。「仮定の列から結論を導く」ことを要求するものがゴールです。命題が結論となったゴールが1つだけ状態から始まります。証明を完遂したことになります。この状態を表しています。reflexivity.Qed.例交えてやる。初めに示した命題の証明を行いたいと思います。この程度の命題であれば自動で解いてくれる強いtaciticがあります。自動証明tacticはゴールに対してtacticを適用するかを定義することで作られています。ringというtacticを用いれば自動で行ってくれます。omegaといったtacticがあります。証明してくれる命題の範囲がそれほど広くないです。その証明を自分でもできるときに限って使うのが良いです。僕が示せなかった証明を振り返る長くなってきたので後編へ移ります。Coqの勉強法はこれが一番有名らしいです。2019年8月21日また京大の五十嵐先生の講義テキストも便利です。証明コンテストTopProverは出れば出るだけ得するレートの付き方をするらしいです。参加して証明力を高めましょう。京都はクソ湿度が高くて気力が出ないです。(1)はてなブログをはじめよう!wass80さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。