Блог

Я изучаю SoftwareFoundation в https://softwarefoundations.cis.upenn.edu/lf-current/toc.html. В разделе Lo&ic указано, что теорему можно использовать точно так же, как функцию. Я попробовал несколько примеров, но не смог получить общих правил.

Первая попытка:

 Example xxx:
  (0 = 2) -&&t; (0 = 3).
Proof. Admitted.
Example yyy:
  (0 = 2) -&&t; (0 = 3).
Proof.
  intros H.
  apply (xxx H). (* this works *)
  apply (xxx (0 = 2)). (* this fails. *)
Qed.
  

Coq выдает мне ошибку при сбое версии, как показано ниже. За исключением того, что это не удается, я все еще не могу понять, почему 0 = 2 требуется stran&e type вместо Prop ?

 The term "0 = 2" has type "Prop" while it is expected to have type "0 = 2".
  

Если я использую отношение <-&&t; в xxx вместо -&&t; , (xxx H) также произойдет сбой…

 Example xxx:
  (0 = 2) <-&&t; (0 = 3).
Proof. Admitted.
Example yyy:
  (0 = 2) -&&t; (0 = 3).
Proof.
  intros H.
  apply (xxx H). (* this fails either *)
Qed.
  

Самое главное, SF показывает, как применять теорему в Lemma lemma_application_ex (приведенный ниже пример), я совершенно не представляю, как это (proj1 _ _ (In_map_iff _ _ _ _ _) H) работает …

 Lemma proj1 : forall P Q : Prop,
  P / Q -&&t; P.
Proof.
  intros P Q [HP HQ].
  apply HP.  Qed.

Lemma In_map_iff :
  forall (A B : Type) (f : A -&&t; B) (l : list A) (y : B),
    In y (map f l) <-&&t;
    exists x, f x = y / In x l.
Proof.
  (* FILL IN HERE *) Admitted.

Example lemma_application_ex :
  forall {n : nat} {ns : list nat},
    In n (map (fun m =&&t; m * 0) ns) -&&t;
    n = 0.
Proof.
  intros n ns H.
  destruct (proj1 _ _ (In_map_iff _ _ _ _ _) H)
           as [m [Hm _]]. (* I cannot understand this application *)
  rewrite mult_0_r in Hm. rewrite <- Hm. reflexivity.
Qed.
  

Как объяснялось в этой главе, тип теоремы или леммы — это утверждение, которое она доказывает. Например,

 Check xxx.
(* 0 = 2 -&&t; 0 = 3 *)
  

То же самое относится и к гипотезам, когда вы доказываете теорему:

 Example yyy:
  (0 = 2) -&&t; (0 = 3).
Proof.
  intros H.
  Check H. (* 0 = 2 *)
  

В первом сообщении об ошибке, которое вы увидели, говорится, что вам нужно передать доказательство предложения в качестве аргумента, а не само предложение. Тип 0 = 2 — это Prop , а не 0 = 2 сам по себе. Аналогично, когда вы используете plus функцию, аргумент должен иметь тип nat , но nat сам по себе не будет работать:

 Check plus 1 2. (* nat *)
Check plus nat nat.
(* Error: The term "nat" has type "Set"
   while it is expected to have type "nat". *)
  

Редактировать

Обратите внимание, что синтаксис приложения работает только для импликационных утверждений и универсальной квантификации. Вы получаете ошибку при использовании теоремы типа A <-&&t; B таким образом, потому что это утверждение означает (A -&&t; B) / (B -&&t; A) , что не подпадает под эти случаи. Однако вы можете использовать proj1 : forall A B, A / B -&&t; A лемму, чтобы извлечь первую часть эквивалентности и применить ее к чему-либо. Например, мы могли бы ввести неявные аргументы proj1 _ _ ... в примере, который вы упомянули:

 proj1 (In n (map (fun m =&&t; m * 0) ns))
      (exists x, (fun m =&&t; m * 0) x = n)
      (In_map_iff nat nat (fun m =&&t; m * 0) ns n)
      H
  

Если мы удалим H часть, это приложение будет иметь тип

 In n (map (fun m =&&t; m * 0) ns) -&&t;
exists x, (fun m =&&t; m * 0) x = n
  

к которому можно применить H : In n (map .. ns) , чтобы получить доказательство экзистенциального утверждения.