Proof step 1 from proof map-putex (conclusion) (back to tree)

System applied rule normalize

And obtained the following new goals

• Proof step 2:

  ¬(((r => o0 * hP))(h[r, o1]) ↔ o0 = o1 ∧ ((r =>_ * hP))(h)), r ∈ h ⊦

Rule argument

Additional information

Proof step 2 from proof map-putex (previous step) (back to tree)

User applied rule case distinction

And obtained the following new goals

• Proof step 3:

  ((r => o0 * hP))(h[r, o1]), r ∈ h ⊦ o0 = o1 ∧ ((r =>_ * hP))(h)

• Proof step 13:

  o0 = o1, ((r =>_ * hP))(h), r ∈ h, ¬ ((r => o0 * hP))(h[r, o1]) ⊦

Rule argument

Additional information

Proof step 3 from proof map-putex (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 4:

  ((r => o0 * hP))(h[r, o1]), r ∈ h ⊦ o0 = o1 ∧ (∃ o. ((r => o * hP))(h))

Rule argument

Additional information

Used simplifier rules: mapex: ⊦ r =>_ = _∃(λ o. r => o); ex3-shift: ⊦ ((_∃ oP * hP))(h) ↔ (∃ o. ((oP(o) * hP))(h)); sep-com: ⊦ hP0 * hP1 = hP1 * hP0; from specification heap-sep sep-ass: ⊦ (hP0 * hP1) * hP2 = hP0 * hP1 * hP2; from specification heap-sep

Proof step 4 from proof map-putex (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 5:

  ⊦ r ≠ null → (r ∈ h ↔ (∃ h0, o. h = (h0 ++ r)[r, o] ∧ ¬ r ∈ h0))

• Proof step 6:

  r ≠ null, ((r => o0 * hP))(h[r, o1]), ∃ h0, o. h = (h0 ++ r)[r, o] ∧ ¬ r ∈ h0 ⊦ o0 = o1 ∧ (∃ o. ((r => o * hP))(h))

Rule argument

Additional information

Used simplifier rules: ⊦ ¬ null ∈ h; (s) Used terms: h, r

Proof step 5 from proof map-putex (previous step) (back to tree)

A spec-lemma

Proof step 6 from proof map-putex (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 7:

  r ≠ null, ((r => o1 * hP))((h0 ++ r)[r, o1]), ¬ r ∈ h0 ⊦ ∃ o0. ((r => o0 * hP))((h0 ++ r)[r, o])

Rule argument

Additional information

Used simplifier rules: map-write: r ∈ h ⊦ ((r => o0 * hP))(h[r, o1]) → o0 = o1; sep-com: ⊦ hP0 * hP1 = hP1 * hP0; from specification heap-sep sep-ass: ⊦ (hP0 * hP1) * hP2 = hP0 * hP1 * hP2; from specification heap-sep r0 ≠ null, ¬ r0 ∈ h ⊦ r ∈ h ++ r0 ↔ r = r0 ∨ r ∈ h; (s) ⊦ h[r, o0][r, o1] = h[r, o1]; (s)

Proof step 7 from proof map-putex (previous step) (back to tree)

User applied rule exists right

And obtained the following new goals

• Proof step 8:

  r ≠ null, ((r => o1 * hP))((h0 ++ r)[r, o1]), ¬ ((r => o * hP))((h0 ++ r)[r, o]), ¬ r ∈ h0 ⊦

Rule argument

Additional information

Used terms: o

Proof step 8 from proof map-putex (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 9:

  ⊦ ((r => o * hP))(h) ↔ hP(h -- r) ∧ r ∈ h ∧ h[r] = o

• Proof step 10:

  r ≠ null, ((r => o1 * hP))((h0 ++ r)[r, o1]), ¬ r ∈ h0, ¬ hP((h0 ++ r)[r, o] -- r) ∨ ¬ r ∈ (h0 ++ r)[r, o] ∨ (h0 ++ r)[r, o][r] ≠ o ⊦

Rule argument

Additional information

Used terms: (h0 ++ r)[r, o], hP, o, r

Proof step 9 from proof map-putex (previous step) (back to tree)

Lemma map-del

Proof step 10 from proof map-putex (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 11:

  r ≠ null, ((r => o1 * hP))((h0 ++ r)[r, o1]), ¬ hP(h0), ¬ r ∈ h0 ⊦

Rule argument

Additional information

Used simplifier rules: r0 ≠ null, ¬ r0 ∈ h ⊦ r ∈ h ++ r0 ↔ r = r0 ∨ r ∈ h; (s) ⊦ h[r0, o][r] = (r = r0 ∧ r0 ∈ h ⊃ o;h[r]); (s) ⊦ r ∈ h[r0, o] ↔ r ∈ h; (s) ¬ r ∈ h, r ≠ null ⊦ (h ++ r) -- r = h; (s) r ∈ h ⊦ h[r, o] -- r = h -- r; (s)

Proof step 11 from proof map-putex (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 12:

  ⊦ ((r => o * hP))(h) ↔ hP(h -- r) ∧ r ∈ h ∧ h[r] = o

Rule argument

Additional information

Used simplifier rules: ⊦ h[r0, o][r] = (r = r0 ∧ r0 ∈ h ⊃ o;h[r]); (s) ⊦ r ∈ h[r0, o] ↔ r ∈ h; (s) r ∈ h ⊦ h[r, o] -- r = h -- r; (s) ⊦ r ∈ h → r ≠ null; (s) ¬ r ∈ h, r ≠ null ⊦ (h ++ r) -- r = h; (s) r0 ≠ null, ¬ r0 ∈ h ⊦ r ∈ h ++ r0 ↔ r = r0 ∨ r ∈ h; (s) Used terms: (h0 ++ r)[r, o1], hP, o1, r

Proof step 12 from proof map-putex (previous step) (back to tree)

Lemma map-del

Proof step 13 from proof map-putex (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 14:

  ((r => o * hP))(h), ¬ ((r => o1 * hP))(h[r, o1]) ⊦

Rule argument

Additional information

Used simplifier rules: mapex-in: ⊦ ((r =>_ * hP))(h) → r ∈ h; mapex: ⊦ r =>_ = _∃(λ o. r => o); ex3-shift: ⊦ ((_∃ oP * hP))(h) ↔ (∃ o. ((oP(o) * hP))(h)); sep-com: ⊦ hP0 * hP1 = hP1 * hP0; from specification heap-sep sep-ass: ⊦ (hP0 * hP1) * hP2 = hP0 * hP1 * hP2; from specification heap-sep

Proof step 14 from proof map-putex (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 15:

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

• Proof step 16:

  ¬ ((r => o1 * hP))(h[r, o1]), ∃ h0, h1. h0 ⊥ h1 ∧ h = h0 ∪ h1 ∧ ((r => o))(h0) ∧ hP(h1) ⊦

Rule argument

Additional information

Used terms: h, hP, r => o

Proof step 15 from proof map-putex (previous step) (back to tree)

A spec-lemma

Proof step 16 from proof map-putex (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 17:

  r ≠ null, hP(h1), ¬ ((r => o1 * hP))(((∅ ++ r)[r, o] ∪ h1)[r, o1]), ¬ r ∈ h1 ⊦

Rule argument

Additional information

Used simplifier rules: maplet: ⊦ ((r => o))(h) ↔ h = (∅ ++ r)[r, o] ∧ r ≠ null; r ≠ null ⊦ (∅ ++ r)[r, o] ⊥ h ↔ ¬ r ∈ h; (s)

Proof step 17 from proof map-putex (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 18:

  ⊦ r ∈ h0 ∧ h0 ⊥ h1 → (h0 ∪ h1)[r, o] = h0[r, o] ∪ h1

• Proof step 19:

  r ≠ null, hP(h1), r ∈ (∅ ++ r)[r, o], (∅ ++ r)[r, o] ⊥ h1, ¬ ((r => o1 * hP))((∅ ++ r)[r, o][r, o1] ∪ h1), ¬ r ∈ h1 ⊦

Rule argument

Additional information

Used simplifier rules: ⊦ r ∈ h[r0, o] ↔ r ∈ h; (s) ⊦ ¬ r ∈ ∅; (s) r0 ≠ null, ¬ r0 ∈ h ⊦ r ∈ h ++ r0 ↔ r = r0 ∨ r ∈ h; (s) r ≠ null ⊦ (∅ ++ r)[r, o] ⊥ h ↔ ¬ r ∈ h; (s) Used terms: o1, r, h1, (∅ ++ r)[r, o]

Proof step 18 from proof map-putex (previous step) (back to tree)

A spec-lemma

Proof step 19 from proof map-putex (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 20:

  hP(h1), r ∈ ∅ ++ r, ¬ ((r => o1 * hP))((∅ ++ r)[r, o1] ∪ h1), ¬ r ∈ h1 ⊦

Rule argument

Additional information

Used simplifier rules: ⊦ h[r, o0][r, o1] = h[r, o1]; (s) ⊦ r ∈ h[r0, o] ↔ r ∈ h; (s) r ≠ null ⊦ (∅ ++ r)[r, o] ⊥ h ↔ ¬ r ∈ h; (s) ⊦ r ∈ h → r ≠ null; (s)

Proof step 20 from proof map-putex (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 21:

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

• Proof step 22:

  hP(h1), r ∈ ∅ ++ r, ¬ r ∈ h1, ∀ h0, h2. ¬(h0 ⊥ h2 ∧ (∅ ++ r)[r, o1] ∪ h1 = h0 ∪ h2 ∧ ((r => o1))(h0) ∧ hP(h2)) ⊦

Rule argument

Additional information

Used terms: (∅ ++ r)[r, o1] ∪ h1, hP, r => o1

Proof step 21 from proof map-putex (previous step) (back to tree)

A spec-lemma

Proof step 22 from proof map-putex (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 23:

  hP(h1), r ∈ ∅ ++ r, ¬ r ∈ h1, ∀ h2. r ∈ h2 ∨ (∅ ++ r)[r, o1] ∪ h1 ≠ (∅ ++ r)[r, o1] ∪ h2 ∨ ¬ hP(h2) ⊦

Rule argument

Additional information

Used simplifier rules: maplet: ⊦ ((r => o))(h) ↔ h = (∅ ++ r)[r, o] ∧ r ≠ null; r ≠ null ⊦ (∅ ++ r)[r, o] ⊥ h ↔ ¬ r ∈ h; (s) ⊦ r ∈ h → r ≠ null; (s)

Proof step 23 from proof map-putex (previous step) (back to tree)

Heuristic quantifier closing applied rule all left

And closed the goal!

Rule argument

Additional information

Used terms: h1