reachp: Reachability in ONE or more steps. Note: reachp is called reach+ below | denotes logical disjunction (or) Definition: reach+(x,b,A,F,M) = addr(x) & (\exists k: F*(x,k,A): ~A(k) & reach(M(k),b,A,F,M)) Wp: reach+(x,b,A,F,M[i <- c]) = (definition) addr(x) & (\exists k: F*(x,k,A): ~A(k) & reach(M'(k),b,A,F,M')) = (expanding first term and simplifying) addr(x) & (\exists k: F*(x,k,A): ~A(k) & (k=i & reach(c,b,A,F,M') | k\neq i & reach(M(k),b,A,F,M'))) This becomes, distributing \exists over | (we drop addr(x) in the first few steps for clarity) (\exists k: F*(x,k,A): ~A(k) & k=i & reach(c,b,A,F,M')) | (\exists k: F*(x,k,A): ~A(k) & k\neq i & reach(M(k),b,A,F,M')) = (wlp for reach) (\exists k: F*(x,k,A): ~A(k) & k=i & reach(c,b,Ai,F,M)) | (\exists k: F*(x,k,A): ~A(k) & k\neq i & (reach(M(k),b,Ai,F,M) | ~A(i) & reach(M(k),i,Ai,F,M) & reach(c,b,Ai,F,M))) = (distributing \exists and simplifying) F*(x,i,A) & ~A(i) & reach(c,b,Ai,F,M) | (\exists k: F*(x,k,A): ~A(k) & k\neq i & reach(M(k),b,Ai,F,M)) | (\exists k: F*(x,k,A): ~A(k) & k\neq i & reach(M(k),i,Ai,F,M)) & reach(c,b,Ai,F,M) & ~A(i) = (using definition of Ai, bringing back addr(x), and lemma0) addr(x) & F*(x,i,A) & ~A(i) & reach(c,b,Ai,F,M) | addr(x) & (\exists k: F*(x,k,Ai): ~Ai(k) & reach(M(k),b,Ai,F,M)) | addr(x) & (\exists k: F*(x,k,Ai): ~Ai(k) & reach(M(k),i,Ai,F,M)) & reach(c,b,Ai,F,M) & ~A(i) = (rewriting) addr(x) & F*(x,i,A) & ~A(i) & reach(c,b,Ai,F,M) | reach+(x,b,Ai,F,M) | reach+(x,i,Ai,F,M) & reach(c,b,Ai,F,M) & ~A(i) = (F*(x,i,A) => addr(x)) F*(x,i,A) & ~A(i) & reach(c,b,Ai,F,M) | reach+(x,b,Ai,F,M) | reach+(x,i,Ai,F,M) & reach(c,b,Ai,F,M) & ~A(i) = (re-grouping terms; lemma 0) reach+(x,b,Ai,F,M) | reach(c,b,Ai,F,M) & ~A(i) & (reach+(x,i,Ai,F,M) |F*(x,i,Ai)) = (property of reach) reach+(x,b,Ai,F,M) | reach(c,b,Ai,F,M) & ~A(i) & reach(x,i,Ai,F,M)