Proof step 1 from proof Sep-forall (conclusion) (back to tree)

System applied rule normalize

And obtained the following new goals

• Proof step 2:

  ((adP0 ⊗_ st))(h), ¬ ((adP ⊗_ st))(h), ∀ a, h. a ∈ st ∧ adP0(a, st[a])(h) → adP(a, st[a])(h) ⊦

Rule argument

Additional information

Proof step 2 from proof Sep-forall (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 3:

  ((adP0 ⊗_ st))(h), ¬ ((adP ⊗_ st))(h), ∀ a, h. a ∈ st ∧ adP0(a, st[a])(h) → adP(a, st[a])(h) ⊦

Rule argument

Additional information

Proof step 3 from proof Sep-forall (previous step) (back to tree)

User applied rule induction

And obtained the following new goals

• Proof step 4:

  ((adP0 ⊗_ st))(h), ¬ ((adP ⊗_ st))(h), ∀ a, h. a ∈ st ∧ adP0(a, st[a])(h) → adP(a, st[a])(h), ∀ st0, adP0, h, adP. # st0 < # st → ((adP0 ⊗_ st0))(h) ∧ ¬ ((adP ⊗_ st0))(h) ∧ (∀ a, h. a ∈ st0 ∧ adP0(a, st0[a])(h) → adP(a, st0[a])(h)) → false ⊦

Rule argument

Additional information

Used simplifier rules: <; (wellfounded) Used terms: # st

Proof step 4 from proof Sep-forall (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 5:

  ((adP0 ⊗_ st))(h), ¬ ((adP ⊗_ st))(h), ∀ a, h. a ∈ st ∧ adP0(a, st[a])(h) → adP(a, st[a])(h), ∀ st0, adP0, h, adP. # st0 < # st → ((adP0 ⊗_ st0))(h) ∧ ¬ ((adP ⊗_ st0))(h) ∧ (∀ a, h. a ∈ st0 ∧ adP0(a, st0[a])(h) → adP(a, st0[a])(h)) → false ⊦

Rule argument

Additional information

Proof step 5 from proof Sep-forall (previous step) (back to tree)

User applied rule cut formula

And obtained the following new goals

• Proof step 6:

  st ≠ ∅, ((adP0 ⊗_ st))(h), ¬ ((adP ⊗_ st))(h), ∀ a, h. a ∈ st ∧ adP0(a, st[a])(h) → adP(a, st[a])(h), ∀ st0, adP0, h, adP. # st0 < # st → ((adP0 ⊗_ st0))(h) ∧ ¬ ((adP ⊗_ st0))(h) ∧ (∀ a, h. a ∈ st0 ∧ adP0(a, st0[a])(h) → adP(a, st0[a])(h)) → false ⊦

Rule argument

Additional information

Used simplifier rules: Sep-emp: ⊦ adP ⊗_ ∅ = emp; ⊦ emp(h) ↔ h = ∅; (s) Used formulas: st = ∅

Proof step 6 from proof Sep-forall (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 7:

  ⊦ st = ∅ ↔ ¬(∃ a, d, st0. st = st0[a, d] ∧ ¬ a ∈ st0)

• Proof step 8:

  ((adP0 ⊗_ st))(h), ¬ ((adP ⊗_ st))(h), ∀ a, h. a ∈ st ∧ adP0(a, st[a])(h) → adP(a, st[a])(h), ∃ a, d, st0. st = st0[a, d] ∧ ¬ a ∈ st0, ∀ st0, adP0, h, adP. # st0 < # st → ((adP0 ⊗_ st0))(h) ∧ ¬ ((adP ⊗_ st0))(h) ∧ (∀ a, h. a ∈ st0 ∧ adP0(a, st0[a])(h) → adP(a, st0[a])(h)) → false ⊦

Rule argument

Additional information

Used terms: st

Proof step 7 from proof Sep-forall (previous step) (back to tree)

A spec-lemma

Proof step 8 from proof Sep-forall (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 9:

  ((adP0(a, d) * adP0 ⊗_ st0))(h), ¬ ((adP(a, d) * adP ⊗_ st0))(h), ¬ a ∈ st0, ∀ a0, h. a0 ∈ st0[a, d] ∧ adP0(a0, st0[a, d][a0])(h) → adP(a0, st0[a, d][a0])(h), ∀ st1, adP0, h, adP. # st1 < # st0[a, d] → ((adP0 ⊗_ st1))(h) ∧ ¬ ((adP ⊗_ st1))(h) ∧ (∀ a, h. a ∈ st1 ∧ adP0(a, st1[a])(h) → adP(a, st1[a])(h)) → false ⊦

Rule argument

Additional information

Used simplifier rules: Sep-ins: ⊦ ¬ a ∈ st → adP ⊗_ st[a, d] = adP(a, d) * adP ⊗_ st;

Proof step 9 from proof Sep-forall (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 10:

  ⊦ ((hP0 * hP1))(h) ↔ (∃ h0, h1. h0 ⊥ h1 ∧ h = h0 ∪ h1 ∧ hP0(h0) ∧ hP1(h1))

• Proof step 11:

  ¬ ((adP(a, d) * adP ⊗_ st0))(h), ¬ a ∈ st0, ∀ a0, h. a0 ∈ st0[a, d] ∧ adP0(a0, st0[a, d][a0])(h) → adP(a0, st0[a, d][a0])(h), ∃ h0, h1. h0 ⊥ h1 ∧ h = h0 ∪ h1 ∧ adP0(a, d)(h0) ∧ ((adP0 ⊗_ st0))(h1), ∀ st1, adP0, h, adP. # st1 < # st0[a, d] → ((adP0 ⊗_ st1))(h) ∧ ¬ ((adP ⊗_ st1))(h) ∧ (∀ a, h. a ∈ st1 ∧ adP0(a, st1[a])(h) → adP(a, st1[a])(h)) → false ⊦

Rule argument

Additional information

Used terms: h, adP0 ⊗_ st0, adP0(a, d)

Proof step 10 from proof Sep-forall (previous step) (back to tree)

A spec-lemma

Proof step 11 from proof Sep-forall (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 12:

  adP0(a, d)(h0), ((adP0 ⊗_ st0))(h1), h0 ⊥ h1, ¬ ((adP(a, d) * adP ⊗_ st0))(h0 ∪ h1), ¬ a ∈ st0, ∀ a0, h. a0 ∈ st0[a, d] ∧ adP0(a0, st0[a, d][a0])(h) → adP(a0, st0[a, d][a0])(h), ∀ st1, adP0, h, adP. # st1 < # st0[a, d] → ((adP0 ⊗_ st1))(h) ∧ ¬ ((adP ⊗_ st1))(h) ∧ (∀ a, h. a ∈ st1 ∧ adP0(a, st1[a])(h) → adP(a, st1[a])(h)) → false ⊦

Rule argument

Additional information

Proof step 12 from proof Sep-forall (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 13:

  ⊦ hP0(h0) ∧ hP1(h1) ∧ h0 ⊥ h1 → ((hP0 * hP1))(h0 ∪ h1)

• Proof step 14:

  adP0(a, d)(h0), ((adP0 ⊗_ st0))(h1), h0 ⊥ h1, ¬ ((adP(a, d) * adP ⊗_ st0))(h0 ∪ h1), ¬ a ∈ st0, ∀ a0, h. a0 ∈ st0[a, d] ∧ adP0(a0, st0[a, d][a0])(h) → adP(a0, st0[a, d][a0])(h), ∀ st1, adP0, h, adP. # st1 < # st0[a, d] → ((adP0 ⊗_ st1))(h) ∧ ¬ ((adP ⊗_ st1))(h) ∧ (∀ a, h. a ∈ st1 ∧ adP0(a, st1[a])(h) → adP(a, st1[a])(h)) → false ⊦ adP(a, d)(h0) ∧ ((adP ⊗_ st0))(h1) ∧ h0 ⊥ h1

Rule argument

Additional information

Used terms: h1, h0, adP ⊗_ st0, adP(a, d)

Proof step 13 from proof Sep-forall (previous step) (back to tree)

A spec-lemma

Proof step 14 from proof Sep-forall (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 15:

  adP0(a, d)(h0), ((adP0 ⊗_ st0))(h1), h0 ⊥ h1, ¬ ((adP(a, d) * adP ⊗_ st0))(h0 ∪ h1), ¬ a ∈ st0, ∀ a0, h. a0 ∈ st0[a, d] ∧ adP0(a0, st0[a, d][a0])(h) → adP(a0, st0[a, d][a0])(h), ∀ st1, adP0, h, adP. # st1 < # st0[a, d] → ((adP0 ⊗_ st1))(h) ∧ ¬ ((adP ⊗_ st1))(h) ∧ (∀ a, h. a ∈ st1 ∧ adP0(a, st1[a])(h) → adP(a, st1[a])(h)) → false ⊦ adP(a, d)(h0) ∧ ((adP ⊗_ st0))(h1)

Rule argument

Additional information

Proof step 15 from proof Sep-forall (previous step) (back to tree)

User applied rule apply induction

And obtained the following new goals

• Proof step 16:

  adP0(a, d)(h0), ((adP0 ⊗_ st0))(h1), h0 ⊥ h1, ¬ ((adP(a, d) * adP ⊗_ st0))(h0 ∪ h1), ¬ a ∈ st0, ∀ a0, h. a0 ∈ st0[a, d] ∧ adP0(a0, st0[a, d][a0])(h) → adP(a0, st0[a, d][a0])(h), ∀ st1, adP0, h, adP. # st1 < # st0[a, d] → ((adP0 ⊗_ st1))(h) ∧ ¬ ((adP ⊗_ st1))(h) ∧ (∀ a, h. a ∈ st1 ∧ adP0(a, st1[a])(h) → adP(a, st1[a])(h)) → false ⊦ adP(a, d)(h0) ∧ ((adP ⊗_ st0))(h1), ((adP0 ⊗_ st0))(h1) ∧ ¬ ((adP ⊗_ st0))(h1) ∧ (∀ a, h. a ∈ st0 ∧ adP0(a, st0[a])(h) → adP(a, st0[a])(h))

Rule argument

Additional information

Used simplifier rules: ⊦ ¬ a ∈ st → # st[a, d] = # st + 1; (s) ⊦ m < n + 1 ↔ ¬ n < m; (s) ⊦ ¬ n < n; (s) a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic c: ⊦ m + n = n + m; from specification nat-basic Used terms: st0, adP0, h1, adP

Proof step 16 from proof Sep-forall (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 17:

  adP0(a, d)(h0), ((adP0 ⊗_ st0))(h1), h0 ⊥ h1, ¬ ((adP(a, d) * adP ⊗_ st0))(h0 ∪ h1), ¬ a ∈ st0, ∀ a0, h. a0 ∈ st0[a, d] ∧ adP0(a0, st0[a, d][a0])(h) → adP(a0, st0[a, d][a0])(h), ∀ st1, adP0, h, adP. # st1 < # st0[a, d] → ((adP0 ⊗_ st1))(h) ∧ ¬ ((adP ⊗_ st1))(h) ∧ (∀ a, h. a ∈ st1 ∧ adP0(a, st1[a])(h) → adP(a, st1[a])(h)) → false ⊦ adP(a, d)(h0) ∧ ((adP ⊗_ st0))(h1), ¬ ((adP ⊗_ st0))(h1) ∧ (a0 ∈ st0 ∧ adP0(a0, st0[a0])(h) → adP(a0, st0[a0])(h))

Rule argument

Additional information

Proof step 17 from proof Sep-forall (previous step) (back to tree)

User applied rule all left

And obtained the following new goals

• Proof step 18:

  adP0(a, d)(h0), ((adP0 ⊗_ st0))(h1), h0 ⊥ h1, ¬ ((adP(a, d) * adP ⊗_ st0))(h0 ∪ h1), ¬ a ∈ st0, a ∈ st0[a, d] ∧ adP0(a, st0[a, d][a])(h0) → adP(a, st0[a, d][a])(h0), ∀ a0, h. a0 ∈ st0[a, d] ∧ adP0(a0, st0[a, d][a0])(h) → adP(a0, st0[a, d][a0])(h), ∀ st1, adP0, h, adP. # st1 < # st0[a, d] → ((adP0 ⊗_ st1))(h) ∧ ¬ ((adP ⊗_ st1))(h) ∧ (∀ a, h. a ∈ st1 ∧ adP0(a, st1[a])(h) → adP(a, st1[a])(h)) → false ⊦ ¬ ((adP ⊗_ st0))(h1) ∧ (a0 ∈ st0 ∧ adP0(a0, st0[a0])(h) → adP(a0, st0[a0])(h)), adP(a, d)(h0) ∧ ((adP ⊗_ st0))(h1)

Rule argument

Additional information

Used terms: a, h0

Proof step 18 from proof Sep-forall (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 19:

  adP(a, d)(h0), adP0(a, d)(h0), adP0(a0, st0[a0])(h), a0 ∈ st0, ((adP0 ⊗_ st0))(h1), h0 ⊥ h1, ¬ ((adP(a, d) * adP ⊗_ st0))(h0 ∪ h1), ¬ adP(a0, st0[a0])(h), ¬ a ∈ st0, ¬ ((adP ⊗_ st0))(h1), ∀ a0, h. a0 ∈ st0[a, d] ∧ adP0(a0, st0[a, d][a0])(h) → adP(a0, st0[a, d][a0])(h), ∀ st1, adP0, h, adP. # st1 < # st0[a, d] → ((adP0 ⊗_ st1))(h) ∧ ¬ ((adP ⊗_ st1))(h) ∧ (∀ a, h. a ∈ st1 ∧ adP0(a, st1[a])(h) → adP(a, st1[a])(h)) → false ⊦

Rule argument

Additional information

Used simplifier rules: ⊦ st[a, d][a] = d; (s) ⊦ a ∈ st[a, d]; (s)

Proof step 19 from proof Sep-forall (previous step) (back to tree)

User applied rule all left

And closed the goal!

Rule argument

Additional information

Used simplifier rules: ⊦ b ∈ st ∧ ¬ a ∈ st → st[a, d][b] = st[b]; (s) precise(hP0) ⊦ hP0(h0) ∧ h0 ⊥ h1 → (((hP0 * hP1))(h0 ∪ h1) ↔ hP1(h1)); (s) sep-ass: ⊦ (hP0 * hP1) * hP2 = hP0 * hP1 * hP2; from specification heap-sep sep-com: ⊦ hP0 * hP1 = hP1 * hP0; from specification heap-sep ⊦ a ∈ st[b, d] ↔ a = b ∨ a ∈ st; (ws) Used terms: a0, h