CODEWITHSUNDEEP
coq
abhishek
abhishek

Reputation: 880

How can I prove following lemma in Coq?

I am trying to write a Coq poof for the following lemma:

Require Export Coq.Structures.OrderedTypeEx.
Require Import FMapAVL.
Module M := FMapAVL.Make(Nat_as_OT).

Fixpoint cc (n: nat) (c: M.t nat):bool :=
match M.find n c with
| None => false
| _ => true
end.

Lemma l: forall (n: nat) (k:nat) (m: M.t nat), cc n m = true  -> cc n (M.add k k m) = true.

I'm unable to simplify (M.add k k m) part.

Upvotes: 0

Views: 370

Answers (1)

Yves
Yves

Reputation: 4236

First, there is no recursive call in cc, so you should make this definition a plain definition (using keyword Definition instead of Fixpoint).

Second, if you want to reason about the behavior of M.find and M.add, you should look at the theorems stating things about these functions: theorems M.find_2, M.add_2, M.E.eq_dec, and M.add_1 will be useful (I found these lemmas by using the Search command). So start by unfolding cc, then reason by cases on the value of (M.find n m), then use these theorems to progress logically about the functions occurring in your statements. Please note that function M.MapsTo plays a key role in this problem.

I would rather not give you the solution because it looks like an elementary exercise in reasoning about tables.

Upvotes: 1

Related Questions