Dafny rejects a simple postcondition -

below first attempt prove various simple theorems, in case parity. dafny /v. 1.9.9.40414/ verifies adding 2 number yields number not accept either of commented out conditions.

function iseven(a : int) : bool requires >= 0 {     if == 0      true      else if == 1 false      else                iseven(a - 2) }  method check1(a : int) requires >= 0 ensures iseven(a) ==> iseven(a + 2) //ensures iseven(a) ==> iseven(a + a) //ensures iseven(a) ==> iseven(a * a) { } 

as have started study wonderful tool, approach or implementation might incorrect. advice appreciated.

there few different things going on here. discuss each of 3 postconditions in turn.

the first , second postconditions

since iseven recursively defined predicate, in general, facts require proofs induction. first post condition simple enough not require induction, why goes through.

your second postcondition require induction proved. dafny has heuristics automatically performing induction, these heuristics invoked in contexts. in particular, dafny attempt induction on "ghost methods" (also called "lemmas").

if add keyword ghost in front of method in check1 (or change method lemma, equivalent), see second postcondition goes through. because dafny's induction heuristic gets invoked , manages complete proof.

the third postcondition

the third postcondition more complex, because involves nonlinear arithmetic. (in other words, involves nontrivial reasoning multiplying 2 variables together.) dafny's underlying solver has trouble reasoning such things, , heuristic proof induction doesn't go through.

a proof a * a if a even

one way prove here. have factored out iseven(a) ==> iseven(a * a) own lemma, called evensquare. have changed require iseven(a) precondition, rather put implication in postcondition. (a similar proof goes through implication instead, using preconditions on lemmas instead of implications idiomatic dafny.)

the proof of evensquare (manual) induction on a. base case handled automatically. in inductive case (the body of if statement), invoke induction hypothesis (ie, make recursive method call evensquare establish (a - 2) * (a - 2) even). assert a * a can written sum of (a - 2) * (a - 2) , offset. assertion dispatched automatically. proof done if can show right hand side of equality even.

to this, know (a - 2) * (a - 2) even, first invoke lemma show offset even, because twice else. finally, invoke 1 last lemma show sum of 2 numbers even.

this completes proof, assuming 2 lemmas.

proofs of 2 lemmas

it remains show twice even, , sum of 2 numbers even. while not trivial, neither complex evensquare.

the lemma evendouble proves twice even. (this in fact stronger version of second postcondition. second postcondition says doubling even number even. in fact, doubling (non-negative, under definition of evenness) number @ even.) proof of evendouble proceeds (manual) induction on a. base case handled automatically. inductive case requires explicitly invoking induction hypothesis.

the lemma evenplus proved automatically dafny's induction heuristic, except trips on bug or other problem causes loop in solver. after little debugging, determined annotation {:induction x} (or {:induction y}, matter) makes proof not loop. these annotations tell dafny's heuristics variable(s) try induct on. default in case, dafny tries induct on both x , y, reason causes solver loop. inducting on either variable alone works. i'm investigating problem further, current solution works.