Proof step 1 from proof reachable-nodups-def (conclusion) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 2:

  ⊦ reachable(r, r0, h) ↔ (∃ x. path(r ' + x, h) ∧ (r ' + x).last = r0 ∧ ¬ r ∈ x ∧ ¬ dups(x))

Rule argument

Additional information

Used simplifier rules: a: ⊦ (x + y) + z = x + y + z; from specification polylist ⊦ dups(a ' + x) ↔ a ∈ x ∨ dups(x); (s)

Proof step 2 from proof reachable-nodups-def (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 3:

  ⊦ reachable(r, r0, h) ↔ (∃ x. path(r ' + x, h) ∧ (r ' + x).last = r0)

• Proof step 4:

  ⊦ (∃ x. path(r ' + x, h) ∧ (r ' + x).last = r0) ↔ (∃ x. path(r ' + x, h) ∧ (r ' + x).last = r0 ∧ ¬ r ∈ x ∧ ¬ dups(x))

Rule argument

Additional information

Used terms: h, r0, r

Proof step 3 from proof reachable-nodups-def (previous step) (back to tree)

Lemma reachable-def

Proof step 4 from proof reachable-nodups-def (previous step) (back to tree)

User applied rule case distinction

And obtained the following new goals

• Proof step 5:

  ∃ x. path(r ' + x, h) ∧ (r ' + x).last = r0 ⊦ ∃ x. path(r ' + x, h) ∧ (r ' + x).last = r0 ∧ ¬ r ∈ x ∧ ¬ dups(x)

• Proof step 22:

  ∃ x. path(r ' + x, h) ∧ (r ' + x).last = r0 ∧ ¬ r ∈ x ∧ ¬ dups(x) ⊦ ∃ x. path(r ' + x, h) ∧ (r ' + x).last = r0

Rule argument

Additional information

Proof step 5 from proof reachable-nodups-def (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 6:

  path(r ' + x, h) ⊦ ∃ x0. path(r ' + x0, h) ∧ (r ' + x0).last = (r ' + x).last ∧ ¬ r ∈ x0 ∧ ¬ dups(x0)

Rule argument

Additional information

Proof step 6 from proof reachable-nodups-def (previous step) (back to tree)

User applied rule structural induction

And obtained the following new goals

• Proof step 7:

  path(r ' + [], h) ⊦ ∃ x0. path(r ' + x0, h) ∧ (r ' + x0).last = (r ' + []).last ∧ ¬ r ∈ x0 ∧ ¬ dups(x0)

• Proof step 9:

  path(r ' + (r0 + x0), h), ∀ r, h. path(r ' + x0, h) → (∃ x1. path(r ' + x1, h) ∧ (r ' + x1).last = (r ' + x0).last ∧ ¬ r ∈ x1 ∧ ¬ dups(x1)) ⊦ ∃ x1. path(r ' + x1, h) ∧ (r ' + x1).last = (r ' + (r0 + x0)).last ∧ ¬ r ∈ x1 ∧ ¬ dups(x1)

Rule argument

Additional information

Used simplifier rules: list('a) freely generated by [], +;;

Proof step 7 from proof reachable-nodups-def (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 8:

  r ≠ null, r ∈ h ⊦ ∃ x0. path(r ' + x0, h) ∧ (r ' + x0).last = r ∧ ¬ r ∈ x0 ∧ ¬ dups(x0)

Rule argument

Additional information

Used simplifier rules: path-one: ⊦ path(r ', h) ↔ r ∈ h ∧ r ≠ null; ⊦ a '.last = a; (s) a: ⊦ (x + y) + z = x + y + z; from specification polylist ⊦ x + [] = x; (s)

Proof step 8 from proof reachable-nodups-def (previous step) (back to tree)

User applied rule exists right

And closed the goal!

Rule argument

Additional information

Used simplifier rules: path-one: ⊦ path(r ', h) ↔ r ∈ h ∧ r ≠ null; ⊦ x + [] = x; (s) a: ⊦ (x + y) + z = x + y + z; from specification polylist ⊦ a '.last = a; (s) ⊦ ¬ a ∈ []; (s) ⊦ ¬ dups([]); (s) Used terms: []

Proof step 9 from proof reachable-nodups-def (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 10:

  r ≠ null, path(h[r].nxt ' + x0, h), r ∈ h, ∀ r, h. path(r ' + x0, h) → (∃ x1. path(r ' + x1, h) ∧ (r ' + x1).last = (r ' + x0).last ∧ ¬ r ∈ x1 ∧ ¬ dups(x1)) ⊦ ∃ x1. path(r ' + x1, h) ∧ (r ' + x1).last = (h[r].nxt ' + x0).last ∧ ¬ r ∈ x1 ∧ ¬ dups(x1)

Rule argument

Additional information

Used simplifier rules: path-cons: ⊦ path(r ' + r0 ' + x, h) ↔ r ∈ h ∧ r ≠ null ∧ h[r].nxt = r0 ∧ path(r0 ' + x, h); a: ⊦ (x + y) + z = x + y + z; from specification polylist ⊦ (b ' + a ' + x).last = (a ' + x).last; (s) ⊦ a + x = a ' + x; (s)

Proof step 10 from proof reachable-nodups-def (previous step) (back to tree)

User applied rule all left

And obtained the following new goals

• Proof step 11:

  r ≠ null, path(h[r].nxt ' + x0, h), r ∈ h, path(h[r].nxt ' + x0, h) → (∃ x1. path(h[r].nxt ' + x1, h) ∧ (h[r].nxt ' + x1).last = (h[r].nxt ' + x0).last ∧ ¬ h[r].nxt ∈ x1 ∧ ¬ dups(x1)), ∀ r, h. path(r ' + x0, h) → (∃ x1. path(r ' + x1, h) ∧ (r ' + x1).last = (r ' + x0).last ∧ ¬ r ∈ x1 ∧ ¬ dups(x1)) ⊦ ∃ x1. path(r ' + x1, h) ∧ (r ' + x1).last = (h[r].nxt ' + x0).last ∧ ¬ r ∈ x1 ∧ ¬ dups(x1)

Rule argument

Additional information

Used terms: h[r].nxt, h

Proof step 11 from proof reachable-nodups-def (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 12:

  (h[r].nxt ' + x1).last = (h[r].nxt ' + x0).last, r ≠ null, path(h[r].nxt ' + x0, h), path(h[r].nxt ' + x1, h), r ∈ h, ¬ dups(x1), ¬ h[r].nxt ∈ x1, ∀ r, h. path(r ' + x0, h) → (∃ x1. path(r ' + x1, h) ∧ (r ' + x1).last = (r ' + x0).last ∧ ¬ r ∈ x1 ∧ ¬ dups(x1)) ⊦ ∃ x1. path(r ' + x1, h) ∧ (r ' + x1).last = (h[r].nxt ' + x0).last ∧ ¬ r ∈ x1 ∧ ¬ dups(x1)

Rule argument

Additional information

Proof step 12 from proof reachable-nodups-def (previous step) (back to tree)

User applied rule exists right

And obtained the following new goals

• Proof step 13:

  (h[r].nxt ' + x1).last = (h[r].nxt ' + x0).last, r ≠ null, path(h[r].nxt ' + x1, h), path(h[r].nxt ' + x0, h), r ∈ h, ¬ dups(x1), ¬ h[r].nxt ∈ x1, ∀ r, h. path(r ' + x0, h) → (∃ x1. path(r ' + x1, h) ∧ (r ' + x1).last = (r ' + x0).last ∧ ¬ r ∈ x1 ∧ ¬ dups(x1)) ⊦ ∃ x1. path(r ' + x1, h) ∧ (r ' + x1).last = (h[r].nxt ' + x0).last ∧ ¬ r ∈ x1 ∧ ¬ dups(x1), path(r ' + h[r].nxt ' + x1, h) ∧ (r ' + h[r].nxt ' + x1).last = (h[r].nxt ' + x0).last ∧ ¬ r ∈ h[r].nxt ' + x1 ∧ ¬ dups(h[r].nxt ' + x1)

Rule argument

Additional information

Used terms: h[r].nxt ' + x1

Proof step 13 from proof reachable-nodups-def (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 14:

  (h[r].nxt ' + x1).last = (h[r].nxt ' + x0).last, r ≠ null, path(h[r].nxt ' + x0, h), path(h[r].nxt ' + x1, h), r ∈ h, ¬ dups(x1), ¬ h[r].nxt ∈ x1, ∀ r, h. path(r ' + x0, h) → (∃ x1. path(r ' + x1, h) ∧ (r ' + x1).last = (r ' + x0).last ∧ ¬ r ∈ x1 ∧ ¬ dups(x1)) ⊦ ∃ x1. path(r ' + x1, h) ∧ (r ' + x1).last = (h[r].nxt ' + x0).last ∧ ¬ r ∈ x1 ∧ ¬ dups(x1), r ≠ h[r].nxt ∧ ¬ r ∈ x1

Rule argument

Additional information

Used simplifier rules: path-cons: ⊦ path(r ' + r0 ' + x, h) ↔ r ∈ h ∧ r ≠ null ∧ h[r].nxt = r0 ∧ path(r0 ' + x, h); a: ⊦ (x + y) + z = x + y + z; from specification polylist ⊦ dups(a ' + x) ↔ a ∈ x ∨ dups(x); (s) ⊦ a ∈ a0 ' + x ↔ a = a0 ∨ a ∈ x; (s) ⊦ (b ' + a ' + x).last = (a ' + x).last; (s)

Proof step 14 from proof reachable-nodups-def (previous step) (back to tree)

User applied rule cut formula

And obtained the following new goals

• Proof step 15:

  (h[r].nxt ' + x1).last = (h[r].nxt ' + x0).last, r ≠ h[r].nxt, r ≠ null, path(h[r].nxt ' + x1, h), path(h[r].nxt ' + x0, h), r ∈ h, ¬ dups(x1), ¬ h[r].nxt ∈ x1, ∀ r, h. path(r ' + x0, h) → (∃ x1. path(r ' + x1, h) ∧ (r ' + x1).last = (r ' + x0).last ∧ ¬ r ∈ x1 ∧ ¬ dups(x1)) ⊦ ∃ x1. path(r ' + x1, h) ∧ (r ' + x1).last = (h[r].nxt ' + x0).last ∧ ¬ r ∈ x1 ∧ ¬ dups(x1), r ≠ h[r].nxt ∧ ¬ r ∈ x1

• Proof step 20:

  (h[r].nxt ' + x1).last = (h[r].nxt ' + x0).last, r = h[r].nxt, r ≠ null, path(h[r].nxt ' + x1, h), path(h[r].nxt ' + x0, h), r ∈ h, ¬ dups(x1), ¬ h[r].nxt ∈ x1, ∀ r, h. path(r ' + x0, h) → (∃ x1. path(r ' + x1, h) ∧ (r ' + x1).last = (r ' + x0).last ∧ ¬ r ∈ x1 ∧ ¬ dups(x1)) ⊦ ∃ x1. path(r ' + x1, h) ∧ (r ' + x1).last = (h[r].nxt ' + x0).last ∧ ¬ r ∈ x1 ∧ ¬ dups(x1), r ≠ h[r].nxt ∧ ¬ r ∈ x1

Rule argument

Additional information

Used formulas: r ≠ h[r].nxt

Proof step 15 from proof reachable-nodups-def (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 16:

  x1.last = (h[r].nxt ' + x0).last, r ≠ h[r].nxt, r ≠ null, path(h[r].nxt ' + x0, h), path(h[r].nxt ' + x1, h), r ∈ h, r ∈ x1, ¬ dups(x1), ¬ h[r].nxt ∈ x1, ∀ r, h. path(r ' + x0, h) → (∃ x1. path(r ' + x1, h) ∧ (r ' + x1).last = (r ' + x0).last ∧ ¬ r ∈ x1 ∧ ¬ dups(x1)) ⊦ ∃ x1. path(r ' + x1, h) ∧ (r ' + x1).last = (h[r].nxt ' + x0).last ∧ ¬ r ∈ x1 ∧ ¬ dups(x1)

Rule argument

Additional information

Used simplifier rules: a: ⊦ (x + y) + z = x + y + z; from specification polylist ⊦ a ∈ x → (b ' + x).last = x.last; (s)

Proof step 16 from proof reachable-nodups-def (previous step) (back to tree)

User applied rule apply rewrite lemma

And obtained the following new goals

• Proof step 17:

  ⊦ a ∈ x ↔ (∃ y, z. x = y + a ' + z ∧ ¬ a ∈ z)

• Proof step 18:

  x1.last = (h[r].nxt ' + x0).last, r ≠ h[r].nxt, r ≠ null, path(h[r].nxt ' + x1, h), path(h[r].nxt ' + x0, h), r ∈ h, ¬ dups(x1), ¬ h[r].nxt ∈ x1, ∀ r, h. path(r ' + x0, h) → (∃ x1. path(r ' + x1, h) ∧ (r ' + x1).last = (r ' + x0).last ∧ ¬ r ∈ x1 ∧ ¬ dups(x1)), ∃ y, z. x1 = y + r ' + z ∧ ¬ r ∈ z ⊦ ∃ x1. path(r ' + x1, h) ∧ (r ' + x1).last = (h[r].nxt ' + x0).last ∧ ¬ r ∈ x1 ∧ ¬ dups(x1)

Rule argument

Additional information

Used terms: x1, r

Proof step 17 from proof reachable-nodups-def (previous step) (back to tree)

A spec-lemma

Proof step 18 from proof reachable-nodups-def (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 19:

  (r ' + x).last = (h[r].nxt ' + x0).last, r ≠ h[r].nxt, r ≠ null, path(h[r].nxt ' + x0, h), path(h[r].nxt ' + y + r ' + x, h), r ∈ h, ¬ dups(y + x), ¬ dups(y), ¬ dups(x), ¬ r ∈ x, ¬ r ∈ y, ¬ h[r].nxt ∈ y, ¬ h[r].nxt ∈ x, ∀ r, h. path(r ' + x0, h) → (∃ x1. path(r ' + x1, h) ∧ (r ' + x1).last = (r ' + x0).last ∧ ¬ r ∈ x1 ∧ ¬ dups(x1)) ⊦ ∃ x1. path(r ' + x1, h) ∧ (r ' + x1).last = (r ' + x).last ∧ ¬ r ∈ x1 ∧ ¬ dups(x1)

Rule argument

Additional information

Used simplifier rules: a: ⊦ (x + y) + z = x + y + z; from specification polylist a: ⊦ ¬ dups(x + y) → ¬ dups(x) ∧ ¬ dups(y); (forward) from specification polylist-dup ⊦ a ≠ a0 → (a ∈ a0 ' + x ↔ a ∈ x); (s) ⊦ a ∈ x + y ↔ a ∈ x ∨ a ∈ y; (s) ⊦ dups(x + a ' + y) ↔ a ∈ x ∨ a ∈ y ∨ dups(x + y); (ws) ⊦ (x + a ' + y).last = (a ' + y).last; (s)

Proof step 19 from proof reachable-nodups-def (previous step) (back to tree)

Heuristic quantifier closing applied rule exists right

And closed the goal!

Rule argument

Additional information

Used simplifier rules: path-postfix: ⊦ path(x + r ' + y, h) → (path(r ' + y, h) ↔ true); a: ⊦ (x + y) + z = x + y + z; from specification polylist Used terms: x

Proof step 20 from proof reachable-nodups-def (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 21:

  (r ' + x1).last = (r ' + x0).last, r = h[r].nxt, r ≠ null, path(r ' + x0, h), path(r ' + x1, h), r ∈ h, ¬ dups(x1), ¬ r ∈ x1, ∀ r, h. path(r ' + x0, h) → (∃ x1. path(r ' + x1, h) ∧ (r ' + x1).last = (r ' + x0).last ∧ ¬ r ∈ x1 ∧ ¬ dups(x1)) ⊦ ∃ x1. path(r ' + x1, h) ∧ (r ' + x1).last = (r ' + x0).last ∧ ¬ r ∈ x1 ∧ ¬ dups(x1)

Rule argument

Additional information

Proof step 21 from proof reachable-nodups-def (previous step) (back to tree)

Heuristic quantifier closing applied rule exists right

And closed the goal!

Rule argument

Additional information

Used terms: x1

Proof step 22 from proof reachable-nodups-def (previous step) (back to tree)

Heuristic simplifier applied rule simplifier

And obtained the following new goals

• Proof step 23:

  path(r ' + x, h), ¬ dups(x), ¬ r ∈ x ⊦ ∃ x0. path(r ' + x0, h) ∧ (r ' + x0).last = (r ' + x).last

Rule argument

Additional information

Proof step 23 from proof reachable-nodups-def (previous step) (back to tree)

Heuristic quantifier closing applied rule exists right

And closed the goal!

Rule argument

Additional information

Used terms: x