代码之家  ›  专栏  ›  技术社区  ›  danbroooks

coq中一组证明的推广

  •  2
  • danbroooks  · 技术社区  · 6 年前

    我正在努力完成麻省理工学院6.826课程的第一部分实验,但我不确定上面的一个练习中是否有评论说我可以用相同的证明来解决一堆例子。我的意思是:

    (* 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

    有关课程材料可在以下位置找到: http://6826.csail.mit.edu/2017/lab/lab0.html

    作为一个Coq的初学者,我很感激被引导到正确的方向,而不是仅仅被给出一个解决方案。如果有一个特别的战术,这将是有用的,在这里,我也许错过了它将是很好的指向这一点。。。

    1 回复  |  直到 6 年前
        1
  •  2
  •   Tej Chajed    6 年前

    我想你只是错过了机会 intuition 战术,哪个 intro 当它看到 A -> B ~P P -> False 也就是说,将假设中的/\s和/s分开,将目标中的/\s分成多个子目标,并使用 auto 搜索两个分支 \/ 球进了。这看起来可能很多,但请注意,这些都是逻辑的基本策略(除了调用 汽车

    在每个练习上运行simpl之后,您将看到它符合此表单,然后 直觉