coq - 在 coq 中推广一组证明

Question

我正在尝试完成 6.826 MIT 类(class)的第一部分实验，但我不确定其中一个练习上面的评论，该评论说我可以使用相同的证明解决一堆示例。这就是我的意思:

(* A `nattree` is a tree of natural numbers, where every internal
   node has an associated number and leaves are empty. There are
   two constructors, L (empty leaf) and I (internal node).
   I's arguments are: left-subtree, number, right-subtree. *)
Inductive nattree : Set :=
  | L : nattree                                (* Leaf *)
  | I : nattree -> nat -> nattree -> nattree.  (* Internal nodes *)

(* Some example nattrees. *)
Definition empty_nattree := L.
Definition singleton_nattree := I L 0 L.
Definition right_nattree := I L 0 (I L 1 (I L 2 (I L 3 L))).
Definition left_nattree := I (I (I (I L 0 L) 1 L) 2 L) 3 L.
Definition balanced_nattree := I (I L 0 (I L 1 L)) 2 (I L 3 L).
Definition unsorted_nattree := I (I L 3 (I L 1 L)) 0 (I L 2 L).

(* EXERCISE: Complete this proposition, which should be `True`
   iff `x` is located somewhere in `t` (even if `t` is unsorted,
   i.e., not a valid binary search tree). *)
Function btree_in (x:nat) (t:nattree) : Prop :=
  match t with
    | L => False
    | I l n r => n = x \/ btree_in x l \/ btree_in x r
  end.

(* EXERCISE: Complete these examples, which show `btree_in` works.
   Hint: The same proof will work for every example.
   End each example with `Qed.`. *)
Example btree_in_ex1 : ~ btree_in 0 empty_nattree.
  simpl. auto.
Qed.
Example btree_in_ex2 : btree_in 0 singleton_nattree.
  simpl. auto.
Qed.
Example btree_in_ex3 : btree_in 2 right_nattree.
  simpl. right. auto.
Qed.
Example btree_in_ex4 : btree_in 2 left_nattree.
  simpl. right. auto.
Qed.
Example btree_in_ex5 : btree_in 2 balanced_nattree.
  simpl. auto.
Qed.
Example btree_in_ex6 : btree_in 2 unsorted_nattree.
  simpl. auto.
Qed.
Example btree_in_ex7 : ~ btree_in 10 balanced_nattree.
  simpl. intros G. destruct G. inversion H. destruct H. destruct H. inversion H. 
  destruct H. inversion H. destruct H. inversion H. destruct H. inversion H.  
  destruct H. destruct H. inversion H. destruct H. inversion H. destruct H.
Qed.
Example btree_in_ex8 : btree_in 3 unsorted_nattree.
  simpl. auto.
Qed.

注释EXERCISE下的代码已作为练习完成(尽管ex7需要一些谷歌搜索...)，第二个练习的提示为“提示:同样的证明适用于每个例子。但我不确定如何为每个不特定于该案例的证明编写。

相关类(class) Material 可以在这里找到:http://6826.csail.mit.edu/2017/lab/lab0.html

作为 Coq 的初学者，我希望能够被引导到正确的方向，而不是仅仅得到解决方案。如果有一个特定的策略在这里有用但我可能错过了，那么最好指出这一点......

Answer 1

我认为你只是错过了直觉策略，当intro看到A -> B时，它会展开intro的假设>~P 到 P -> False 和 intro 的意思是，在假设中分割/\s 和/s，在目标中打破/\s分成多个子目标，并使用 auto 搜索目标中 \/ 的两个分支。这可能看起来很多，但请注意，这些都是逻辑的基本策略(除了对 auto 的调用)。

在对每个练习运行 simpl 后，您会发现它适合这种形式，然后直觉就会发挥作用。