Bukti Teorema dalam Coq

Latar Belakang

Saya belajar bantuan, Coq, sendiri. Sejauh ini, saya telah selesai membaca Yves Bertot's Coq in a Hurry . Sekarang, tujuan saya adalah untuk membuktikan beberapa hasil dasar mengenai bilangan asli, yang berpuncak dengan algoritma pembagian. Namun, saya telah menemui beberapa kemunduran dalam perjalanan menuju tujuan itu. Secara khusus, dua hasil berikut telah membuktikan (pun intended) lebih sulit untuk dibuktikan dalam Coq daripada yang saya bayangkan sebelumnya. Bahkan, setelah banyak upaya saya sia-sia, saya terpaksa membuktikannya dengan tangan (seperti yang ditunjukkan di bawah). Ini jelas tidak membantu saya menjadi lebih mahir dalam menangani Coq; itulah sebabnya saya beralih ke forum ini. Harapan saya adalah seseorang di situs ini dapat dan maumembantu saya menerjemahkan bukti saya di bawah ini menjadi bukti yang diterima Coq. Semua bantuan dengan tulus dihargai!

Teorema A

Untuk semua Bukti: $x,y \in N$

x < S (y) \subset x < y \lor I (N, x, y)

$\begin{equation} x < S(y) \subset x < y \lor \text{I}(N,x,y) \end{equation}$

Misalkan . Karenanya ada dengan $x < S(y)$ $z \in N$ Maka oleh (Peano 1b dan 3)

\begin{matrix} (*) & I (N, x + S (z), S (y)) \end{matrix}

$\begin{equation} \text{I}(N,x+S(z),S(y)) \tag{*}\end{equation}$

I (N, x + z, y)

$\begin{equation} \text{I}(N,x+z,y) \end{equation}$

Tentukan predikat

Q (u) := (I (N, x + u, y) \subset x < y \lor I (N, x, y)

$\begin{equation} Q(u):=(\text{I}(N,x+u,y) \subset x<y \lor \text{I}(N,x,y) \end{equation}$

Cukup untuk menunjukkan . Kami membuktikan ini dengan induksi pada . Untuk melihat , bukan ethat jika berlaku maka benar oleh Peano 1a. Jadi, . Sekarang, kami membuktikan $Q(z)$ $z$ $Q(0)$ $\text{I}(N,x+0,y)$ $\text{I}(N,x,y)$ $x<y \lor \text{I}(n,x,y)$ : Misalkan . Dari definisi ini kita memiliki dan dengan demikian juga dalam hal ini. Akhirnya, aksioma kelima Peano memberi dan dengan kita mendapatkan $Q(S(v))$ $\text{I}(N,x+S(v),y)$ $x<y$ $x<y \lor \text{I}(N,x,y)$ $Q(z)$ $(*)$ . $x < y \lor \text{I}(N,x,y)$

\begin{matrix} (◻) \end{matrix}

$\begin{equation} \tag{$\square$} \end{equation}$

Teorema B

Untuk semua Bukti: $x,y \in N$

x < y \lor I (N, x, y) \lor y < x

$\begin{equation} x <y \lor \text{I}(N,x,y) \lor y<x \end{equation}$

Jika maka menurut definisi, dan jika maka juga menurut definisi. Jika dan maka dengan transitivitas dan refleksivitas, kita memiliki , yang merupakan kontradiksi. Akibatnya, tidak lebih dari satu pernyataan yang benar. $x<y$ $\neg \text{I}(N,x,y)$ $x>y$ $\neg \text{I}(N,x,y)$ $x>y$ $y>x$ $\text{I}(N,x,y)$

Kami terus tetap dan melantik pada . Ketika kita miliki $y$ $x$ $\text{I}(N,0,y)$ untuk semua , yang membuktikan kasus dasar. Selanjutnya, anggap teorema berlaku untuk ; sekarang kita ingin membuktikan teorema untuk . Dari trikotomi untuk , ada tiga kasus: $0 < y \lor \text{I}(N,0,y)$ $y$ $x$ $S(x)$ $x$ , dan . Jika , maka jelas . Jika , maka (sebagai untuk semua ). Akhirnya, misalkan Kemudian, dengan teorema A kita memiliki $x<y,\text{I}(N,x,y)$ $x>y$ $x>y$ $S(x) >y$ $\text{I}(N,x,y)$ $S(x) >y$ $S(x) >x$ $x\in \mathbb{N}$ $x <y$ atau , dan dalam kedua kasus kita selesai. $S(x) < y$ $\text{I}(N,S(x),y)$

\begin{matrix} (◻) \end{matrix}

$\begin{equation} \tag{$\square$} \end{equation}$

Teorema yang ingin saya buktikan, dapat diungkapkan sebagai berikut dalam Coq.

Lemma less_lem (xy: N): less x (succ y) -> atau (less xy) (IN xy).

Teorema Ntrichotomy: (forall xy: N, atau (less xy) (atau (IN xy) (less yx))).

Hasil yang bermanfaat

Di sini, saya telah mengumpulkan beberapa hasil yang telah saya tetapkan, dan terbukti sampai titik ini. Inilah yang saya sebut di atas. * Ini adalah kode yang saya tulis sejauh ini, perhatikan bahwa sebagian besar terdiri dari definisi. *

(* Sigma types *)


Inductive Sigma (A:Set)(B:A -> Set) :Set :=
  Spair: forall a:A, forall b : B a,Sigma A B.

Definition E (A:Set)(B:A -> Set)
  (C: Sigma A B -> Set)
  (c: Sigma A B)
  (d: (forall x:A, forall y:B x, 
      C (Spair A B x y))): C c :=

match c as c0 return (C c0) with
| Spair a b => d a b
end. 


(* Binary sum type *)

Inductive sum' (A B:Set):Set := 
inl': A -> sum' A B | inr': B -> sum' A B.

Print sum'_rect.

Definition D (A B : Set)(C: sum' A B -> Set)
(c: sum' A B)
(d: (forall x:A, C (inl' A B x)))
(e: (forall y:B, C (inr' A B y))): C c :=

match c as c0 return C c0 with
| inl' x => d x
| inr' y => e y
end.

(* Three useful finite sets *)

Inductive N_0: Set :=.

Definition R_0
  (C:N_0 -> Set)
  (c: N_0): C c :=
match c as c0 return (C c0) with
end.

Inductive N_1: Set := zero_1:N_1.

Definition R_1 
  (C:N_1 -> Set)
  (c: N_1)
  (d_zero: C zero_1): C c :=
match c as c0 return (C c0) with
  | zero_1 => d_zero
end.

Inductive N_2: Set := zero_2:N_2 | one_2:N_2.

Definition R_2 
  (C:N_2 -> Set)
  (c: N_2)
  (d_zero: C zero_2)
  (d_one: C one_2): C c :=
match c as c0 return (C c0) with
  | zero_2 => d_zero
  | one_2  => d_one
end.


(* Natural numbers *)

Inductive N:Set :=
zero: N | succ : N -> N.

Print N. 

Print N_rect.

Definition R 
  (C:N -> Set)
  (d: C zero)
  (e: (forall x:N, C x -> C (succ x))):
  (forall n:N, C n) :=
fix F (n: N): C n :=
  match n as n0 return (C n0) with
  | zero => d
  | succ n0 => e n0 (F n0)
  end.

(* Boolean to truth-value converter *)

Definition Tr (c:N_2) : Set :=
match c as c0 with
  | zero_2 => N_0
  | one_2 => N_1
end.

(* Identity type *)

Inductive I (A: Set)(x: A) : A -> Set :=
r :  I A x x.

Print I_rect.

Theorem J 
  (A:Set)
  (C: (forall x y:A, 
              forall z: I A x y, Set))
  (d: (forall x:A, C x x (r A x)))
  (a:A)(b:A)(c:I A a b): C a b c.
induction c.
apply d.
Defined.

(* functions are extensional wrt
  identity types *)

Theorem I_I_extensionality (A B: Set)(f: A -> B):
(forall x y:A, I A x y -> I B (f x) (f y)).
Proof.
intros x y P.
induction P.
apply r.
Defined.


(* addition *)

Definition add (m n:N) : N 
 := R (fun z=> N) m (fun x y => succ y) n.

(* multiplication *)

Definition mul (m n:N) : N 
 := R (fun z=> N) zero (fun x y => add y m) n.


(* Axioms of Peano verified *)

Theorem P1a: (forall x: N, I N (add x zero) x).
intro x.
(* force use of definitional equality
  by applying reflexivity *)
apply r.
Defined.


Theorem P1b: (forall x y: N, 
I N (add x (succ y)) (succ (add x y))).
intros.
apply r.
Defined.


Theorem P2a: (forall x: N, I N (mul x zero) zero).
intros.
apply r.
Defined.


Theorem P2b: (forall x y: N, 
I N (mul x (succ y)) (add (mul x y) x)).
intros.
apply r.
Defined.

Definition pd (n: N): N :=
R (fun _=> N) zero (fun x y=> x) n.

(* alternatively
Definition pd (x: N): N :=
match x as x0 with
  | zero => zero
  | succ n0 => n0
end.
*)

Theorem P3: (forall x y:N, 
I N (succ x) (succ y) -> I N x y).
intros x y p.
apply (I_I_extensionality N N pd (succ x) (succ y)).
apply p.
Defined.

Definition not (A:Set): Set:= (A -> N_0).

Definition isnonzero (n: N): N_2:=
R (fun _ => N_2) zero_2 (fun x y => one_2) n.


Theorem P4 : (forall x:N, 
not (I N (succ x) zero)).
intro x.
intro p.

apply (J N (fun x y z => 
    Tr (isnonzero x) -> Tr (isnonzero y))
    (fun x => (fun t => t)) (succ x) zero)
.
apply p.
simpl.
apply zero_1.
Defined.

Theorem P5 (P:N -> Set):
P zero -> (forall x:N, P x -> P (succ x))
   -> (forall x:N, P x).
intros base step n.
apply R.
apply base.
apply step.
Defined.

(* I(A,-,-) is an equivalence relation *)

Lemma Ireflexive (A:Set): (forall x:A, I A x x).
intro x.
apply r.
Defined.

Lemma Isymmetric (A:Set): (forall x y:A, I A x y -> I A y x).
intros x y P.
induction P.
apply r.
Defined.

Lemma Itransitive (A:Set): 
(forall x y z:A, I A x y -> I A y z -> I A x z).
intros x y z P Q.
induction P.
assumption.
Defined.


Lemma succ_cong : (forall m n:N, I N m n -> I N (succ m) (succ n)).
intros m n H.
induction H.
apply r.
Defined.

Lemma zeroadd: (forall n:N, I N (add zero n) n).
intro n.
induction n.
simpl.
apply r.
apply succ_cong.
auto.

Defined.

Lemma succadd: (forall m n:N, I N (add (succ m) n) (succ (add m n))).
intros.
induction n.
simpl.
apply r.
simpl.
apply succ_cong.
auto.

Defined.

Lemma commutative_add: (forall m n:N, I N (add m n) (add n m)).
intros n m; elim n.
apply zeroadd.
intros y H; elim (succadd m y).
simpl.
rewrite succadd.
apply succ_cong.
assumption.


Defined.

Lemma associative_add: (forall m n k:N, 
I N (add (add m n) k) (add m (add n k))).
intros m n k.
induction k.
simpl.
apply Ireflexive.
simpl.
apply succ_cong.
assumption.
Defined.

Definition or (A B : Set):= sum' A B.


Definition less (m n: N) :=
 Sigma N (fun z => I N (add m (succ z)) n).



Lemma less_lem (x y:N) : 
less x (succ y) -> or (less x y) (I N x y).
intro.
destruct H.
right.

(* Here is where I'm working right now *)

Defined.


Theorem Ntrichotomy: (forall x y:N, 
or (less x y) (or (I N x y) (less y x))).

automated-theorem-proving proof-assistants mathematical-programming coq pengguna11942
sumber

Untuk memahami seberapa jauh yang Anda miliki, akan sangat membantu jika Anda memposting kode Coq Anda sejauh ini, sehingga kami dapat memuatnya dan memeriksa apa yang kami usulkan berfungsi untuk definisi Anda.

Gilles 'SO- berhenti bersikap jahat'

Beberapa komentar dan pertanyaan klarifikasi: - Apakah cukup untuk keperluan Anda hanya menggunakan persamaan sintaksis ("=" dalam Coq) alih-alih I (N, x, y)? Apakah ada alasan untuk menggunakan 'atau' cara Anda mendefinisikannya? Coq (yah, pustaka dasar untuk Coq) memiliki cara ekspresi disjungsi logis yang memfasilitasi aspek bukti tertentu yang bagus. Demikian pula ada cara untuk mendefinisikan 'kurang' yang mungkin lebih bisa diterapkan untuk Anda. Untuk tujuan ini, Anda mungkin ingin melihat bab-bab awal Yayasan Perangkat Lunak . Sementara bagian akhir buku ...

Luke Mathieson

... adalah tentang memverifikasi program dll., permulaannya cukup bagus untuk memperkenalkan Coq, dan memiliki teorema seperti yang Anda miliki sebagai latihan dan contoh. Ini gratis, dan sebenarnya semuanya ditulis sebagai skrip Coq, sehingga Anda dapat melakukan latihan dan kompilasi saat Anda membacanya. Untuk apa yang Anda lakukan di sini, ada potongan-potongan menarik dalam bab-bab Dasar, Induksi, Prop dan Logika - dan mungkin beberapa dependensi dari bit di antara.

Luke Mathieson

Catatan lain, Thm P5 (prinsip induktif) dibangun untuk Coq dalam bentuk yang lebih kuat (induksi struktural), jadi Anda tidak perlu secara eksplisit menganggapnya sebagai aksioma.

Luke Mathieson

Saya telah memposting kode Coq yang telah saya tulis sejauh ini.

user11942

Jawaban:

Coq sedikit lebih kejam daripada bukti kertas: ketika Anda menulis "dan kita selesai" atau "jelas" dalam bukti kertas, sering kali ada lebih banyak yang harus dilakukan untuk meyakinkan Coq.

Sekarang saya melakukan sedikit pembersihan kode Anda, sambil mencoba untuk tetap dalam semangat yang sama. Anda dapat menemukannya di sini .

Beberapa komentar:

Saya menggunakan tipe data bawaan dan definisi di mana saya pikir itu tidak akan merusak niat Anda. Perhatikan bahwa jika saya menggunakan persamaan built-in alih-alih identitydan relasi "kurang-dari" bawaan, bukti akan jauh lebih mudah, karena banyak lemma Anda ada di database teorema yang dikenal, yang diperiksa pada setiap panggilan dari
```
auto with arith.
```
Saya menggunakan beberapa taktik yang mungkin tidak Anda sadari, tetapi pengguna super Coq "asli" akan memiliki taktik yang jauh lebih kuat dan menulis taktiknya sendiri untuk menyederhanakan pekerjaan. Saya selalu merekomendasikan CPDT sebagai tempat untuk belajar tentang menggunakan taktik dengan cara yang kuat.
Saya menggunakan notasi dan tab untuk meningkatkan keterbacaan dan konstruksi bawaan seperti pencocokan dan inductiontaktik untuk membuat hal-hal lebih mudah untuk dibuktikan dan faktor ulang. Khususnya, definisi Anda tentang lesssulit untuk dikerjakan, Anda dapat melihat bagaimana saya sedikit memodifikasinya dari
$\exists x, m + (x + 1) = n$ $\exists x,\ m + (x+1) = n$ $\exists x, (x + m) + 1 = n$ $\exists x,\ (x + m)+1 = n$ semacam ini "definisi tweaking" terjadi suatu banyak di bukti formal.
Meskipun Anda mungkin mendapatkan jawaban untuk pertanyaan-pertanyaan semacam ini di sini, saya sangat menyarankan Anda mengirimkan karya Anda ke Coq-Club yang dibuat dengan tujuan menjawab pertanyaan-pertanyaan semacam ini.

cody
sumber

Jawaban yang bagus Cody! Sungguh luar biasa mengetahui bahwa ada orang-orang dermawan seperti Anda di luar sana, yang bersedia membantu orang lain yang membutuhkan. Saya sangat menghargainya! Saya pasti akan melihat CPDT dan Coq-Club; keduanya yang kemungkinan besar akan saya butuhkan dalam waktu dekat karena saya terus berupaya membuktikan algoritma pembagian dalam Coq.

user11942

Terima kasih! Perhatikan bahwa ini sering disebut "divisi Euclidian" dan sudah ada di beberapa perpustakaan (lebih dari bilangan bulat)

cody

Tidak mengherankan saya, perpustakaan Coq saya telah melihat telah diisi dengan sangat baik dengan definisi, lemma dan teorema. Saya akan berusaha memposting pendekatan saya ke algoritma divisi Euclidian sebagai pertanyaan paling lambat besok.

user11942

Jawaban Cody sangat bagus, dan memenuhi pertanyaan Anda tentang menerjemahkan bukti Anda ke Coq. Sebagai pelengkap untuk itu, saya ingin menambahkan hasil yang sama, tetapi terbukti menggunakan rute yang berbeda, terutama sebagai ilustrasi dari beberapa bit Coq dan untuk menunjukkan apa yang dapat Anda buktikan secara sintaksis dengan sedikit pekerjaan tambahan. Namun ini bukan klaim bahwa ini adalah rute terpendek - hanya rute yang berbeda. Buktinya hanya mencakup satu lemma pembantu tambahan, dan hanya bergantung pada definisi dasar, saya tidak memperkenalkan penambahan, perkalian atau sifat-sifatnya, atau ekstensionalitas fungsional, dan satu-satunya aksioma Peano adalah bentuk sederhana dari <= b -> a + c <= b + c dalam helper helma (hanya untuk c = 1) dan induksi struktural, yang datang dengan tipe induktif gratis pula.

Seperti Cody, di mana saya pikir tidak ada bedanya, saya menggunakan tipe yang telah ditentukan dll, jadi sebelum buktinya, saya akan menjelaskannya:

Saya menggunakan tipe nat bawaan untuk bilangan asli, yang memiliki (hingga penamaan yang tepat) definisi yang sama dengan Anda:

Nat induktif: Set: = O: nat | S: nat -> nat

Saya menggunakan le dan lt built in kurang dari atau sama dan kurang dari masing-masing, yang memiliki singkatan notasi "<=" dan "<" untuk keterbacaan. Mereka didefinisikan:

File induktif: nat -> nat -> Prop: =
| le_n: forall n, le nn
| le_S: forall nm, (le nm) -> (le n (S m)).

dan

Definisi lt (nm: nat): = le (S n) m.

Built in eq (singkatan "=") adalah persamaan sintaksis dan berfungsi sama dengan "Aku" Anda, dengan satu konstruktor yang hanya mengatakan bahwa segala sesuatu sama dengan dirinya sendiri. Properti simetris dan transitif adalah bukti mudah dari sana, tetapi kita tidak akan membutuhkannya dalam kasus ini. Definisi untuk persamaan di bawah ini memiliki notasi yang tertanam di dalamnya.

Persamaan induktif (A: Jenis) (x: A): A -> Prop: = eq_refl: x = x

Terakhir, saya telah menggunakan proposisional atau (singkatan "\ /" - yang merupakan backslash forwardslash), yang memiliki dua konstruktor, pada dasarnya bahwa Anda memiliki bukti untuk argumen kiri, atau argumen kanan. Coq juga memiliki beberapa taktik steno, kiri dan kanan, yang masing-masing berarti "berlaku or_introl" dan "terapkan or_intror".

Induktif atau (AB: Prop): Prop: =
or_introl: A -> A / B | or_intror: B -> A / B

Apa yang sekarang mengikuti adalah bukti saya, pada prinsipnya, jika markup tidak menghalangi, Anda harus dapat memotong dan melewatinya ke dalam file Coq .v dan itu akan berfungsi. Saya telah menyertakan komentar untuk mencatat bit yang menarik, tetapi mereka berada dalam pembatas (* *), jadi Anda tidak harus menghapusnya.

Theorem lt_or_eq: forall (n m : nat),
  n < S m -> n < m \/ n = m.
Proof.
(*
  This proof is just a case analysis on n and m, whether they're zero or
  a successor of something.
*)
destruct n as [|n']; destruct m as [|m']. 

(*n = 0, m = 0*)
intros.
  right. reflexivity.

(*n = 0, m = S m'*)
intros H.
  inversion H.
  inversion H1.
  left. unfold lt. constructor.
  (*The constructor tactic tries to match the goal to a constructor
    that's in the environment.*) 
  left. unfold lt. constructor. assumption.
  (*Assumption tries to match the goal to something that's in the
    current context*)

(*n = S n', m = 0
  This case is false, so we can invert our way out of it.*)
intros.
  inversion H. inversion H1.

(*n = S n', m = S m'*)
intros.
  inversion H.
    right. reflexivity.
    left. unfold lt. assumption.
Qed.


(*
  The following lemma with be useful in the proof of the trichotomy theorem,
  it's pretty obviously true, and easy to prove. The interesting part for
  anyone relatively new to Coq is that the induction is done on the
  hypothesis "a <= b", rather than on either a or b.
*)
Lemma a_le_b_implies_Sa_le_Sb: forall a b, a <= b -> S a <= S b.
Proof.
  intros a b Hyp.
  induction Hyp.
  constructor.
  constructor.
  apply IHHyp.
Qed.

(*
  The proof of the trichotomy theorem is a little more involved than the
  last one but again we don't use anything particularly tricky. 
  Other than the helper lemma above, we don't use anything other than the
  definitions.

  The proof proceeds by induction on n, then induction on m.  My personal
  feeling is that this can probably be shortened.  
*)
Theorem trich: forall (n m : nat),
  n < m \/ n = m \/ m < n.
Proof.
  induction n.
    induction m.
      right. left. reflexivity.
        inversion IHm.
          left. unfold lt. constructor. unfold lt in H. assumption.
          inversion H.
          left. unfold lt. subst. constructor.
          inversion H0.     
    induction m.
      assert (n < 0 \/ n = 0 \/ 0 < n).
      apply IHn.
      inversion H.
      inversion H0.
      inversion H0.
      right. right. subst. unfold lt. constructor.
      right. right. unfold lt. constructor. assumption.
      inversion IHm. unfold lt in H.
      left. unfold lt. constructor. assumption.
      inversion H; subst.
      left. unfold lt. constructor.
      inversion H0.
      right. left. reflexivity.
      right. right. apply lt_or_eq in H0.

      inversion H0.
      apply a_le_b_implies_Sa_le_Sb. assumption.
      subst. unfold lt. apply a_le_b_implies_Sa_le_Sb. assumption.
Qed.

(*
  The following is just to show what can be done with some of the tactics
  The omega tactic implements a Pressburger arithmetic solver, so anything
  with natural numbers, plus, multiplication by constants, and basic logic
  can just be solved. Not very interesting for practicing Coq, but cool to
  know.
*)

Require Import Omega.

Example trich' : forall (n m : nat),
  n < m \/ n = m \/ m < n.
Proof.
  intros.
  omega.
Qed.

Luke Mathieson
sumber

Jawaban indah lainnya! Saya benar-benar berterima kasih kepada Anda untuk waktu dan upaya yang telah Anda lakukan untuk menjawab pertanyaan saya.

user11942