| ⊦ rooted(g) ∧ isroot(g)(a) ∧ isroot(g)(b) → a = b |
a ≠ b, isroot(g)(a), isroot(g)(b), rooted(g) ⊦
| a ≠ b, isroot(g)(a), isroot(g)(b), rooted(g) ⊦ |
a ≠ b, isroot(g)(b), isroot(g)(a), rooted(g) ⊦
| a ≠ b, isroot(g)(b), isroot(g)(a), rooted(g) ⊦ |
⊦ rooted(g) ↔ (∃ a. isroot(g)(a) ∧ (∀ b. path(g)(a, b)))
a ≠ b, isroot(g)(a), isroot(g)(b), ∃ a. isroot(g)(a) ∧ (∀ b. path(g)(a, b)) ⊦
Used terms: g
| ⊦ rooted(g) ↔ (∃ a. isroot(g)(a) ∧ (∀ b. path(g)(a, b))) |
| a ≠ b, isroot(g)(a), isroot(g)(b), ∃ a. isroot(g)(a) ∧ (∀ b. path(g)(a, b)) ⊦ |
a ≠ b, isroot(g)(a0), isroot(g)(b), isroot(g)(a), ∀ b. path(g)(a0, b) ⊦
| a ≠ b, isroot(g)(a0), isroot(g)(b), isroot(g)(a), ∀ b. path(g)(a0, b) ⊦ |
⊦ isroot(g)(b) ↔ dom(g)(b) ∧ (∀ a. ¬ edge(g)(a, b))
a ≠ b, dom(g)(a0), isroot(g)(a), isroot(g)(b), ∀ b. path(g)(a0, b), ∀ a. ¬ edge(g)(a, a0) ⊦
Used terms: a0, g
| ⊦ isroot(g)(b) ↔ dom(g)(b) ∧ (∀ a. ¬ edge(g)(a, b)) |
| a ≠ b, dom(g)(a0), isroot(g)(a), isroot(g)(b), ∀ b. path(g)(a0, b), ∀ a. ¬ edge(g)(a, a0) ⊦ |
⊦ isroot(g)(b) ↔ dom(g)(b) ∧ (∀ a. ¬ edge(g)(a, b))
a ≠ b, dom(g)(a), dom(g)(a0), isroot(g)(b), ∀ a. ¬ edge(g)(a, a0), ∀ b. path(g)(a0, b), ∀ a0. ¬ edge(g)(a0, a) ⊦
Used terms: a, g
| ⊦ isroot(g)(b) ↔ dom(g)(b) ∧ (∀ a. ¬ edge(g)(a, b)) |
| a ≠ b, dom(g)(a), dom(g)(a0), isroot(g)(b), ∀ a. ¬ edge(g)(a, a0), ∀ b. path(g)(a0, b), ∀ a0. ¬ edge(g)(a0, a) ⊦ |
⊦ isroot(g)(b) ↔ dom(g)(b) ∧ (∀ a. ¬ edge(g)(a, b))
a ≠ b, dom(g)(b), dom(g)(a0), dom(g)(a), ∀ a0. ¬ edge(g)(a0, a), ∀ b. path(g)(a0, b), ∀ a. ¬ edge(g)(a, a0), ∀ a. ¬ edge(g)(a, b) ⊦
Used terms: b, g
| ⊦ isroot(g)(b) ↔ dom(g)(b) ∧ (∀ a. ¬ edge(g)(a, b)) |
| a ≠ b, dom(g)(b), dom(g)(a0), dom(g)(a), ∀ a0. ¬ edge(g)(a0, a), ∀ b. path(g)(a0, b), ∀ a. ¬ edge(g)(a, a0), ∀ a. ¬ edge(g)(a, b) ⊦ |
a ≠ b, dom(g)(a), dom(g)(a0), dom(g)(b), path(g)(a0, b), ∀ a. ¬ edge(g)(a, b), ∀ a. ¬ edge(g)(a, a0), ∀ b. path(g)(a0, b), ∀ a0. ¬ edge(g)(a0, a) ⊦
Used terms: b
| a ≠ b, dom(g)(a), dom(g)(a0), dom(g)(b), path(g)(a0, b), ∀ a. ¬ edge(g)(a, b), ∀ a. ¬ edge(g)(a, a0), ∀ b. path(g)(a0, b), ∀ a0. ¬ edge(g)(a0, a) ⊦ |
⊦ path(g)(a, b) ↔ (∃ x. pathp(g)(⌜x⌝ ) ∧ x ≠ [] ∧ a = x.head ∧ b = x.last)
a ≠ b, dom(g)(b), dom(g)(a0), dom(g)(a), ∀ a0. ¬ edge(g)(a0, a), ∀ b. path(g)(a0, b), ∀ a. ¬ edge(g)(a, a0), ∀ a. ¬ edge(g)(a, b), ∃ x. pathp(g)(⌜x⌝ ) ∧ x ≠ [] ∧ a0 = x.head ∧ b = x.last ⊦
Used terms: b, a0, g
| ⊦ path(g)(a, b) ↔ (∃ x. pathp(g)(⌜x⌝ ) ∧ x ≠ [] ∧ a = x.head ∧ b = x.last) |
| a ≠ b, dom(g)(b), dom(g)(a0), dom(g)(a), ∀ a0. ¬ edge(g)(a0, a), ∀ b. path(g)(a0, b), ∀ a. ¬ edge(g)(a, a0), ∀ a. ¬ edge(g)(a, b), ∃ x. pathp(g)(⌜x⌝ ) ∧ x ≠ [] ∧ a0 = x.head ∧ b = x.last ⊦ |
a ≠ x.last, x ≠ [], dom(g)(a), dom(g)(x.head), dom(g)(x.last), pathp(g)(⌜x⌝ ), ∀ a. ¬ edge(g)(a, x.last), ∀ a. ¬ edge(g)(a, x.head), ∀ b. path(g)(x.head, b), ∀ a0. ¬ edge(g)(a0, a) ⊦
| a ≠ x.last, x ≠ [], dom(g)(a), dom(g)(x.head), dom(g)(x.last), pathp(g)(⌜x⌝ ), ∀ a. ¬ edge(g)(a, x.last), ∀ a. ¬ edge(g)(a, x.head), ∀ b. path(g)(x.head, b), ∀ a0. ¬ edge(g)(a0, a) ⊦ |
x = a1 + y, a ≠ x.last, x ≠ [], dom(g)(x.last), dom(g)(a1), dom(g)(a), pathp(g)(⌜x⌝ ), ∀ a0. ¬ edge(g)(a0, a), ∀ b. path(g)(a1, b), ∀ a. ¬ edge(g)(a, a1), ∀ a. ¬ edge(g)(a, x.last) ⊦
Used simplifier rules: x ≠ [] ⊦ a = x.head ∧ y = x.tail ↔ x = a + y; (elim) Used terms: x, a1, y
| x = a1 + y, a ≠ x.last, x ≠ [], dom(g)(x.last), dom(g)(a1), dom(g)(a), pathp(g)(⌜x⌝ ), ∀ a0. ¬ edge(g)(a0, a), ∀ b. path(g)(a1, b), ∀ a. ¬ edge(g)(a, a1), ∀ a. ¬ edge(g)(a, x.last) ⊦ |
a ≠ (a1 ' + y).last, dom(g)(a), dom(g)(a1), dom(g)((a1 ' + y).last), pathp(g)(⌜a1 '⌝ + ⌜y⌝ ), ∀ a. ¬ edge(g)(a, a1), ∀ b. path(g)(a1, b), ∀ a0. ¬ edge(g)(a0, a), ∀ a0. ¬ edge(g)(a0, (a1 ' + y).last) ⊦
Used simplifier rules: ⊦ a + x = a ' + x; (s) a: ⊦ (x + y) + z = x + y + z; from specification list ⊦ ⌜x + y⌝ = ⌜x⌝ + ⌜y⌝ ; (s) ⊦ a ' + x ≠ []; (s)
| a ≠ (a1 ' + y).last, dom(g)(a), dom(g)(a1), dom(g)((a1 ' + y).last), pathp(g)(⌜a1 '⌝ + ⌜y⌝ ), ∀ a. ¬ edge(g)(a, a1), ∀ b. path(g)(a1, b), ∀ a0. ¬ edge(g)(a0, a), ∀ a0. ¬ edge(g)(a0, (a1 ' + y).last) ⊦ |
y = [], a ≠ (a1 ' + y).last, dom(g)((a1 ' + y).last), dom(g)(a1), dom(g)(a), pathp(g)(⌜a1 '⌝ + ⌜y⌝ ), ∀ a0. ¬ edge(g)(a0, (a1 ' + y).last), ∀ a0. ¬ edge(g)(a0, a), ∀ b. path(g)(a1, b), ∀ a. ¬ edge(g)(a, a1) ⊦
a ≠ (a1 ' + y).last, y ≠ [], dom(g)((a1 ' + y).last), dom(g)(a1), dom(g)(a), pathp(g)(⌜a1 '⌝ + ⌜y⌝ ), ∀ a0. ¬ edge(g)(a0, (a1 ' + y).last), ∀ a0. ¬ edge(g)(a0, a), ∀ b. path(g)(a1, b), ∀ a. ¬ edge(g)(a, a1) ⊦
Used formulas: y = []
| y = [], a ≠ (a1 ' + y).last, dom(g)((a1 ' + y).last), dom(g)(a1), dom(g)(a), pathp(g)(⌜a1 '⌝ + ⌜y⌝ ), ∀ a0. ¬ edge(g)(a0, (a1 ' + y).last), ∀ a0. ¬ edge(g)(a0, a), ∀ b. path(g)(a1, b), ∀ a. ¬ edge(g)(a, a1) ⊦ |
a ≠ a1, dom(g)(a), dom(g)(a1), pathp(g)(⌜a1 '⌝ ), ∀ a. ¬ edge(g)(a, a1), ∀ b. path(g)(a1, b), ∀ a0. ¬ edge(g)(a0, a), ∀ a0. ¬ edge(g)(a0, a1) ⊦
Used simplifier rules: ⊦ a '.last = a; (s) a: ⊦ (x + y) + z = x + y + z; from specification list ⊦ x + [] = x; (s) append-assoc: ⊦ (σ + σ1) + σ2 = σ + σ1 + σ2; from specification stream ⊦ σ + [] = σ; (s) ⊦ ⌜[]⌝ = []; (s)
| a ≠ a1, dom(g)(a), dom(g)(a1), pathp(g)(⌜a1 '⌝ ), ∀ a. ¬ edge(g)(a, a1), ∀ b. path(g)(a1, b), ∀ a0. ¬ edge(g)(a0, a), ∀ a0. ¬ edge(g)(a0, a1) ⊦ |
a ≠ a1, dom(g)(a1), dom(g)(a), path(g)(a1, a), pathp(g)(⌜a1 '⌝ ), ∀ a0. ¬ edge(g)(a0, a1), ∀ a0. ¬ edge(g)(a0, a), ∀ a. ¬ edge(g)(a, a1) ⊦
Used terms: a
| a ≠ a1, dom(g)(a1), dom(g)(a), path(g)(a1, a), pathp(g)(⌜a1 '⌝ ), ∀ a0. ¬ edge(g)(a0, a1), ∀ a0. ¬ edge(g)(a0, a), ∀ a. ¬ edge(g)(a, a1) ⊦ |
⊦ path(g)(a, b) ↔ (∃ x. pathp(g)(⌜x⌝ ) ∧ x ≠ [] ∧ a = x.head ∧ b = x.last)
a ≠ a1, dom(g)(a), dom(g)(a1), pathp(g)(⌜a1 '⌝ ), ∀ a. ¬ edge(g)(a, a1), ∀ a0. ¬ edge(g)(a0, a), ∀ a0. ¬ edge(g)(a0, a1), ∃ x. pathp(g)(⌜x⌝ ) ∧ x ≠ [] ∧ a1 = x.head ∧ a = x.last ⊦
Used terms: a, a1, g
| ⊦ path(g)(a, b) ↔ (∃ x. pathp(g)(⌜x⌝ ) ∧ x ≠ [] ∧ a = x.head ∧ b = x.last) |
| a ≠ a1, dom(g)(a), dom(g)(a1), pathp(g)(⌜a1 '⌝ ), ∀ a. ¬ edge(g)(a, a1), ∀ a0. ¬ edge(g)(a0, a), ∀ a0. ¬ edge(g)(a0, a1), ∃ x. pathp(g)(⌜x⌝ ) ∧ x ≠ [] ∧ a1 = x.head ∧ a = x.last ⊦ |
x.last ≠ x.head, x ≠ [], dom(g)(x.head), dom(g)(x.last), pathp(g)(⌜x⌝ ), pathp(g)(⌜x.head '⌝ ), ∀ a0. ¬ edge(g)(a0, x.head), ∀ a0. ¬ edge(g)(a0, x.last), ∀ a. ¬ edge(g)(a, x.head) ⊦
| x.last ≠ x.head, x ≠ [], dom(g)(x.head), dom(g)(x.last), pathp(g)(⌜x⌝ ), pathp(g)(⌜x.head '⌝ ), ∀ a0. ¬ edge(g)(a0, x.head), ∀ a0. ¬ edge(g)(a0, x.last), ∀ a. ¬ edge(g)(a, x.head) ⊦ |
x = a1 + y, x.last ≠ a1, x ≠ [], dom(g)(x.last), dom(g)(a1), pathp(g)(⌜a1 '⌝ ), pathp(g)(⌜x⌝ ), ∀ a. ¬ edge(g)(a, a1), ∀ a0. ¬ edge(g)(a0, x.last), ∀ a0. ¬ edge(g)(a0, a1) ⊦
Used simplifier rules: x ≠ [] ⊦ a = x.head ∧ y = x.tail ↔ x = a + y; (elim) Used terms: x, a1, y
| x = a1 + y, x.last ≠ a1, x ≠ [], dom(g)(x.last), dom(g)(a1), pathp(g)(⌜a1 '⌝ ), pathp(g)(⌜x⌝ ), ∀ a. ¬ edge(g)(a, a1), ∀ a0. ¬ edge(g)(a0, x.last), ∀ a0. ¬ edge(g)(a0, a1) ⊦ |
(a1 ' + y).last ≠ a1, dom(g)(a1), dom(g)((a1 ' + y).last), pathp(g)(⌜a1 '⌝ + ⌜y⌝ ), pathp(g)(⌜a1 '⌝ ), ∀ a0. ¬ edge(g)(a0, a1), ∀ a. ¬ edge(g)(a, a1), ∀ a0. ¬ edge(g)(a0, (a1 ' + y).last) ⊦
Used simplifier rules: ⊦ a + x = a ' + x; (s) a: ⊦ (x + y) + z = x + y + z; from specification list ⊦ ⌜x + y⌝ = ⌜x⌝ + ⌜y⌝ ; (s) ⊦ a ' + x ≠ []; (s)
| (a1 ' + y).last ≠ a1, dom(g)(a1), dom(g)((a1 ' + y).last), pathp(g)(⌜a1 '⌝ + ⌜y⌝ ), pathp(g)(⌜a1 '⌝ ), ∀ a0. ¬ edge(g)(a0, a1), ∀ a. ¬ edge(g)(a, a1), ∀ a0. ¬ edge(g)(a0, (a1 ' + y).last) ⊦ |
⊦ x ≠ [] → (a ' + x).last = x.last
y.last ≠ a1, y ≠ [], dom(g)(y.last), dom(g)(a1), pathp(g)(⌜a1 '⌝ ), pathp(g)(⌜a1 '⌝ + ⌜y⌝ ), ∀ a0. ¬ edge(g)(a0, y.last), ∀ a. ¬ edge(g)(a, a1), ∀ a0. ¬ edge(g)(a0, a1) ⊦
Used simplifier rules: ⊦ x + [] = x; (s) a: ⊦ (x + y) + z = x + y + z; from specification list ⊦ a '.last = a; (s) Used terms: y, a1
| ⊦ x ≠ [] → (a ' + x).last = x.last |
| y.last ≠ a1, y ≠ [], dom(g)(y.last), dom(g)(a1), pathp(g)(⌜a1 '⌝ ), pathp(g)(⌜a1 '⌝ + ⌜y⌝ ), ∀ a0. ¬ edge(g)(a0, y.last), ∀ a. ¬ edge(g)(a, a1), ∀ a0. ¬ edge(g)(a0, a1) ⊦ |
y = y0 + a2 ', a2 ≠ a1, y ≠ [], dom(g)(a1), dom(g)(a2), pathp(g)(⌜a1 '⌝ + ⌜y⌝ ), pathp(g)(⌜a1 '⌝ ), ∀ a0. ¬ edge(g)(a0, a1), ∀ a. ¬ edge(g)(a, a1), ∀ a0. ¬ edge(g)(a0, a2) ⊦
Used simplifier rules: x ≠ [] ⊦ a = x.last ∧ y = x.butlast ↔ x = y + a '; (elim) Used terms: y, a2, y0
| y = y0 + a2 ', a2 ≠ a1, y ≠ [], dom(g)(a1), dom(g)(a2), pathp(g)(⌜a1 '⌝ + ⌜y⌝ ), pathp(g)(⌜a1 '⌝ ), ∀ a0. ¬ edge(g)(a0, a1), ∀ a. ¬ edge(g)(a, a1), ∀ a0. ¬ edge(g)(a0, a2) ⊦ |
a2 ≠ a1, dom(g)(a2), dom(g)(a1), pathp(g)(⌜a1 '⌝ ), pathp(g)(⌜a1 '⌝ + ⌜y0⌝ + ⌜a2 '⌝ ), ∀ a0. ¬ edge(g)(a0, a2), ∀ a. ¬ edge(g)(a, a1), ∀ a0. ¬ edge(g)(a0, a1) ⊦
Used simplifier rules: append-assoc: ⊦ (σ + σ1) + σ2 = σ + σ1 + σ2; from specification stream a: ⊦ (x + y) + z = x + y + z; from specification list ⊦ ⌜x + y⌝ = ⌜x⌝ + ⌜y⌝ ; (s) ⊦ x + a ' ≠ []; (s)
| a2 ≠ a1, dom(g)(a2), dom(g)(a1), pathp(g)(⌜a1 '⌝ ), pathp(g)(⌜a1 '⌝ + ⌜y0⌝ + ⌜a2 '⌝ ), ∀ a0. ¬ edge(g)(a0, a2), ∀ a. ¬ edge(g)(a, a1), ∀ a0. ¬ edge(g)(a0, a1) ⊦ |
⊦ pathp(g)(σ) ↔ (∀ n. ⌜n⌝ < # σ → dom(g)(σ[n])) ∧ (∀ n. ⌜n + 1⌝ < # σ → edge(g)(σ[n], σ[n + 1]))
a2 ≠ a1, dom(g)(a1), dom(g)(a2), pathp(g)(⌜a1 '⌝ ), ∀ a0. ¬ edge(g)(a0, a1), ∀ a. ¬ edge(g)(a, a1), ∀ a0. ¬ edge(g)(a0, a2), ∀ n. ⌜n⌝ < #(⌜a1 '⌝ + ⌜y0⌝ + ⌜a2 '⌝ ) → dom(g)((⌜a1 '⌝ + ⌜y0⌝ + ⌜a2 '⌝ )[n]), ∀ n. ⌜n + 1⌝ < #(⌜a1 '⌝ + ⌜y0⌝ + ⌜a2 '⌝ ) → edge(g)((⌜a1 '⌝ + ⌜y0⌝ + ⌜a2 '⌝ )[n], (⌜a1 '⌝ + ⌜y0⌝ + ⌜a2 '⌝ )[n + 1]) ⊦
Used terms: ⌜a1 '⌝ + ⌜y0⌝ + ⌜a2 '⌝ , g
| ⊦ pathp(g)(σ) ↔ (∀ n. ⌜n⌝ < # σ → dom(g)(σ[n])) ∧ (∀ n. ⌜n + 1⌝ < # σ → edge(g)(σ[n], σ[n + 1])) |
| a2 ≠ a1, dom(g)(a1), dom(g)(a2), pathp(g)(⌜a1 '⌝ ), ∀ a0. ¬ edge(g)(a0, a1), ∀ a. ¬ edge(g)(a, a1), ∀ a0. ¬ edge(g)(a0, a2), ∀ n. ⌜n⌝ < #(⌜a1 '⌝ + ⌜y0⌝ + ⌜a2 '⌝ ) → dom(g)((⌜a1 '⌝ + ⌜y0⌝ + ⌜a2 '⌝ )[n]), ∀ n. ⌜n + 1⌝ < #(⌜a1 '⌝ + ⌜y0⌝ + ⌜a2 '⌝ ) → edge(g)((⌜a1 '⌝ + ⌜y0⌝ + ⌜a2 '⌝ )[n], (⌜a1 '⌝ + ⌜y0⌝ + ⌜a2 '⌝ )[n + 1]) ⊦ |
a2 ≠ a1, dom(g)(a2), dom(g)(a1), pathp(g)(⌜a1 '⌝ ), ∀ a0. ¬ edge(g)(a0, a2), ∀ a. ¬ edge(g)(a, a1), ∀ a0. ¬ edge(g)(a0, a1), ∀ n. ¬ # y0 < n → edge(g)((a1 ' + y0 + a2 ')[n], (y0 + a2 ')[n]), ∀ n. n < 2 + # y0 → dom(g)((a1 ' + y0 + a2 ')[n]) ⊦
Used simplifier rules: append-assoc: ⊦ (σ + σ1) + σ2 = σ + σ1 + σ2; from specification stream ⊦ (⌜x⌝ + ⌜x0⌝ + ⌜x1⌝ )[m] = (x + x0 + x1)[m]; (s) add-comm: ⊦ n∞1 + n∞2 = n∞2 + n∞1; from specification nat-inf add-assoc: ⊦ (n∞ + n∞1) + n∞2 = n∞ + n∞1 + n∞2; from specification nat-inf ⊦ ⌜n⌝ < ⌜m⌝ + ⌜n0⌝ ↔ n < m + n0; (s) c: ⊦ m + n = n + m; from specification nat-basic a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic ⊦ ⌜(* n)⌝ + ⌜(* m)⌝ = ⌜n + m⌝ ; (s) ⊦ # a ' = 0 +1; (s) ⊦ # ⌜x⌝ = ⌜# x⌝ ; (s) ⊦ #(σ + σ1) = # σ + # σ1; (s) ⊦ (⌜x⌝ + ⌜x0⌝ )[m] = (x + x0)[m]; (s) ⊦ (⌜a '⌝ + σ)[n + 1] = σ[n]; (s) ⊦ ⌜m⌝ < ⌜n⌝ ↔ m < n; (s) ⊦ ⌜n⌝ < ⌜1⌝ + n∞ ↔ ¬ n∞ < ⌜n⌝ ; (s) ⊦ m ≤ n → (⌜(* m)⌝ + n∞2 < ⌜(* n)⌝ + n∞1 ↔ n∞2 < ⌜n - m⌝ + n∞1); (s) ⊦ ⌜m + n⌝ = ⌜m⌝ + ⌜n⌝ ; (s)
| a2 ≠ a1, dom(g)(a2), dom(g)(a1), pathp(g)(⌜a1 '⌝ ), ∀ a0. ¬ edge(g)(a0, a2), ∀ a. ¬ edge(g)(a, a1), ∀ a0. ¬ edge(g)(a0, a1), ∀ n. ¬ # y0 < n → edge(g)((a1 ' + y0 + a2 ')[n], (y0 + a2 ')[n]), ∀ n. n < 2 + # y0 → dom(g)((a1 ' + y0 + a2 ')[n]) ⊦ |
a2 ≠ a1, dom(g)(a1), dom(g)(a2), pathp(g)(⌜a1 '⌝ ), ¬ # y0 < # y0 → edge(g)((a1 ' + y0 + a2 ')[# y0], (y0 + a2 ')[# y0]), ∀ n. n < 2 + # y0 → dom(g)((a1 ' + y0 + a2 ')[n]), ∀ a0. ¬ edge(g)(a0, a1), ∀ a. ¬ edge(g)(a, a1), ∀ a0. ¬ edge(g)(a0, a2) ⊦
Used terms: # y0
| a2 ≠ a1, dom(g)(a1), dom(g)(a2), pathp(g)(⌜a1 '⌝ ), ¬ # y0 < # y0 → edge(g)((a1 ' + y0 + a2 ')[# y0], (y0 + a2 ')[# y0]), ∀ n. n < 2 + # y0 → dom(g)((a1 ' + y0 + a2 ')[n]), ∀ a0. ¬ edge(g)(a0, a1), ∀ a. ¬ edge(g)(a, a1), ∀ a0. ¬ edge(g)(a0, a2) ⊦ |
a2 ≠ a1, dom(g)(a2), dom(g)(a1), edge(g)((a1 ' + y0).last, a2), pathp(g)(⌜a1 '⌝ ), ∀ a0. ¬ edge(g)(a0, a2), ∀ a. ¬ edge(g)(a, a1), ∀ a0. ¬ edge(g)(a0, a1), ∀ n. n < 2 + # y0 → dom(g)((a1 ' + y0 + a2 ')[n]) ⊦
Used simplifier rules: a: ⊦ (x + y) + z = x + y + z; from specification list ⊦ (x + a ')[# x] = a; (s) ⊦ (a ' + x + y)[# x] = (a ' + x).last; (s) ⊦ ¬ n < n; (s)
| a2 ≠ a1, dom(g)(a2), dom(g)(a1), edge(g)((a1 ' + y0).last, a2), pathp(g)(⌜a1 '⌝ ), ∀ a0. ¬ edge(g)(a0, a2), ∀ a. ¬ edge(g)(a, a1), ∀ a0. ¬ edge(g)(a0, a1), ∀ n. n < 2 + # y0 → dom(g)((a1 ' + y0 + a2 ')[n]) ⊦ |
Used terms: (a1 ' + y0).last
| a ≠ (a1 ' + y).last, y ≠ [], dom(g)((a1 ' + y).last), dom(g)(a1), dom(g)(a), pathp(g)(⌜a1 '⌝ + ⌜y⌝ ), ∀ a0. ¬ edge(g)(a0, (a1 ' + y).last), ∀ a0. ¬ edge(g)(a0, a), ∀ b. path(g)(a1, b), ∀ a. ¬ edge(g)(a, a1) ⊦ |
a ≠ y.last, y ≠ [], dom(g)(a), dom(g)(a1), dom(g)(y.last), pathp(g)(⌜a1 '⌝ + ⌜y⌝ ), ∀ a. ¬ edge(g)(a, a1), ∀ b. path(g)(a1, b), ∀ a0. ¬ edge(g)(a0, a), ∀ a0. ¬ edge(g)(a0, y.last) ⊦
Used simplifier rules: a: ⊦ (x + y) + z = x + y + z; from specification list ⊦ x ≠ [] → (a ' + x).last = x.last; (s)
| a ≠ y.last, y ≠ [], dom(g)(a), dom(g)(a1), dom(g)(y.last), pathp(g)(⌜a1 '⌝ + ⌜y⌝ ), ∀ a. ¬ edge(g)(a, a1), ∀ b. path(g)(a1, b), ∀ a0. ¬ edge(g)(a0, a), ∀ a0. ¬ edge(g)(a0, y.last) ⊦ |
y = y0 + a2 ', a ≠ a2, y ≠ [], dom(g)(a2), dom(g)(a1), dom(g)(a), pathp(g)(⌜a1 '⌝ + ⌜y⌝ ), ∀ a0. ¬ edge(g)(a0, a2), ∀ a0. ¬ edge(g)(a0, a), ∀ b. path(g)(a1, b), ∀ a. ¬ edge(g)(a, a1) ⊦
Used simplifier rules: x ≠ [] ⊦ a = x.last ∧ y = x.butlast ↔ x = y + a '; (elim) Used terms: y, a2, y0
| y = y0 + a2 ', a ≠ a2, y ≠ [], dom(g)(a2), dom(g)(a1), dom(g)(a), pathp(g)(⌜a1 '⌝ + ⌜y⌝ ), ∀ a0. ¬ edge(g)(a0, a2), ∀ a0. ¬ edge(g)(a0, a), ∀ b. path(g)(a1, b), ∀ a. ¬ edge(g)(a, a1) ⊦ |
a ≠ a2, dom(g)(a), dom(g)(a1), dom(g)(a2), pathp(g)(⌜a1 '⌝ + ⌜y0⌝ + ⌜a2 '⌝ ), ∀ a. ¬ edge(g)(a, a1), ∀ b. path(g)(a1, b), ∀ a0. ¬ edge(g)(a0, a), ∀ a0. ¬ edge(g)(a0, a2) ⊦
Used simplifier rules: append-assoc: ⊦ (σ + σ1) + σ2 = σ + σ1 + σ2; from specification stream a: ⊦ (x + y) + z = x + y + z; from specification list ⊦ ⌜x + y⌝ = ⌜x⌝ + ⌜y⌝ ; (s) ⊦ x + a ' ≠ []; (s)
| a ≠ a2, dom(g)(a), dom(g)(a1), dom(g)(a2), pathp(g)(⌜a1 '⌝ + ⌜y0⌝ + ⌜a2 '⌝ ), ∀ a. ¬ edge(g)(a, a1), ∀ b. path(g)(a1, b), ∀ a0. ¬ edge(g)(a0, a), ∀ a0. ¬ edge(g)(a0, a2) ⊦ |
⊦ pathp(g)(σ) ↔ (∀ n. ⌜n⌝ < # σ → dom(g)(σ[n])) ∧ (∀ n. ⌜n + 1⌝ < # σ → edge(g)(σ[n], σ[n + 1]))
a ≠ a2, dom(g)(a2), dom(g)(a1), dom(g)(a), ∀ a0. ¬ edge(g)(a0, a2), ∀ a0. ¬ edge(g)(a0, a), ∀ b. path(g)(a1, b), ∀ a. ¬ edge(g)(a, a1), ∀ n. ⌜n⌝ < #(⌜a1 '⌝ + ⌜y0⌝ + ⌜a2 '⌝ ) → dom(g)((⌜a1 '⌝ + ⌜y0⌝ + ⌜a2 '⌝ )[n]), ∀ n. ⌜n + 1⌝ < #(⌜a1 '⌝ + ⌜y0⌝ + ⌜a2 '⌝ ) → edge(g)((⌜a1 '⌝ + ⌜y0⌝ + ⌜a2 '⌝ )[n], (⌜a1 '⌝ + ⌜y0⌝ + ⌜a2 '⌝ )[n + 1]) ⊦
Used terms: ⌜a1 '⌝ + ⌜y0⌝ + ⌜a2 '⌝ , g
| ⊦ pathp(g)(σ) ↔ (∀ n. ⌜n⌝ < # σ → dom(g)(σ[n])) ∧ (∀ n. ⌜n + 1⌝ < # σ → edge(g)(σ[n], σ[n + 1])) |
| a ≠ a2, dom(g)(a2), dom(g)(a1), dom(g)(a), ∀ a0. ¬ edge(g)(a0, a2), ∀ a0. ¬ edge(g)(a0, a), ∀ b. path(g)(a1, b), ∀ a. ¬ edge(g)(a, a1), ∀ n. ⌜n⌝ < #(⌜a1 '⌝ + ⌜y0⌝ + ⌜a2 '⌝ ) → dom(g)((⌜a1 '⌝ + ⌜y0⌝ + ⌜a2 '⌝ )[n]), ∀ n. ⌜n + 1⌝ < #(⌜a1 '⌝ + ⌜y0⌝ + ⌜a2 '⌝ ) → edge(g)((⌜a1 '⌝ + ⌜y0⌝ + ⌜a2 '⌝ )[n], (⌜a1 '⌝ + ⌜y0⌝ + ⌜a2 '⌝ )[n + 1]) ⊦ |
a ≠ a2, dom(g)(a), dom(g)(a1), dom(g)(a2), ∀ a. ¬ edge(g)(a, a1), ∀ b. path(g)(a1, b), ∀ a0. ¬ edge(g)(a0, a), ∀ a0. ¬ edge(g)(a0, a2), ∀ n. ¬ # y0 < n → edge(g)((a1 ' + y0 + a2 ')[n], (y0 + a2 ')[n]), ∀ n. n < 2 + # y0 → dom(g)((a1 ' + y0 + a2 ')[n]) ⊦
Used simplifier rules: append-assoc: ⊦ (σ + σ1) + σ2 = σ + σ1 + σ2; from specification stream ⊦ (⌜x⌝ + ⌜x0⌝ + ⌜x1⌝ )[m] = (x + x0 + x1)[m]; (s) add-comm: ⊦ n∞1 + n∞2 = n∞2 + n∞1; from specification nat-inf add-assoc: ⊦ (n∞ + n∞1) + n∞2 = n∞ + n∞1 + n∞2; from specification nat-inf ⊦ ⌜n⌝ < ⌜m⌝ + ⌜n0⌝ ↔ n < m + n0; (s) c: ⊦ m + n = n + m; from specification nat-basic a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic ⊦ ⌜(* n)⌝ + ⌜(* m)⌝ = ⌜n + m⌝ ; (s) ⊦ # a ' = 0 +1; (s) ⊦ # ⌜x⌝ = ⌜# x⌝ ; (s) ⊦ #(σ + σ1) = # σ + # σ1; (s) ⊦ (⌜x⌝ + ⌜x0⌝ )[m] = (x + x0)[m]; (s) ⊦ (⌜a '⌝ + σ)[n + 1] = σ[n]; (s) ⊦ ⌜m⌝ < ⌜n⌝ ↔ m < n; (s) ⊦ ⌜n⌝ < ⌜1⌝ + n∞ ↔ ¬ n∞ < ⌜n⌝ ; (s) ⊦ m ≤ n → (⌜(* m)⌝ + n∞2 < ⌜(* n)⌝ + n∞1 ↔ n∞2 < ⌜n - m⌝ + n∞1); (s) ⊦ ⌜m + n⌝ = ⌜m⌝ + ⌜n⌝ ; (s)
| a ≠ a2, dom(g)(a), dom(g)(a1), dom(g)(a2), ∀ a. ¬ edge(g)(a, a1), ∀ b. path(g)(a1, b), ∀ a0. ¬ edge(g)(a0, a), ∀ a0. ¬ edge(g)(a0, a2), ∀ n. ¬ # y0 < n → edge(g)((a1 ' + y0 + a2 ')[n], (y0 + a2 ')[n]), ∀ n. n < 2 + # y0 → dom(g)((a1 ' + y0 + a2 ')[n]) ⊦ |
a ≠ a2, dom(g)(a2), dom(g)(a1), dom(g)(a), ¬ # y0 < # y0 → edge(g)((a1 ' + y0 + a2 ')[# y0], (y0 + a2 ')[# y0]), ∀ n. n < 2 + # y0 → dom(g)((a1 ' + y0 + a2 ')[n]), ∀ a0. ¬ edge(g)(a0, a2), ∀ a0. ¬ edge(g)(a0, a), ∀ b. path(g)(a1, b), ∀ a. ¬ edge(g)(a, a1) ⊦
Used terms: # y0
| a ≠ a2, dom(g)(a2), dom(g)(a1), dom(g)(a), ¬ # y0 < # y0 → edge(g)((a1 ' + y0 + a2 ')[# y0], (y0 + a2 ')[# y0]), ∀ n. n < 2 + # y0 → dom(g)((a1 ' + y0 + a2 ')[n]), ∀ a0. ¬ edge(g)(a0, a2), ∀ a0. ¬ edge(g)(a0, a), ∀ b. path(g)(a1, b), ∀ a. ¬ edge(g)(a, a1) ⊦ |
a ≠ a2, dom(g)(a), dom(g)(a1), dom(g)(a2), edge(g)((a1 ' + y0).last, a2), ∀ a. ¬ edge(g)(a, a1), ∀ b. path(g)(a1, b), ∀ a0. ¬ edge(g)(a0, a), ∀ a0. ¬ edge(g)(a0, a2), ∀ n. n < 2 + # y0 → dom(g)((a1 ' + y0 + a2 ')[n]) ⊦
Used simplifier rules: a: ⊦ (x + y) + z = x + y + z; from specification list ⊦ (x + a ')[# x] = a; (s) ⊦ (a ' + x + y)[# x] = (a ' + x).last; (s) ⊦ ¬ n < n; (s)
| a ≠ a2, dom(g)(a), dom(g)(a1), dom(g)(a2), edge(g)((a1 ' + y0).last, a2), ∀ a. ¬ edge(g)(a, a1), ∀ b. path(g)(a1, b), ∀ a0. ¬ edge(g)(a0, a), ∀ a0. ¬ edge(g)(a0, a2), ∀ n. n < 2 + # y0 → dom(g)((a1 ' + y0 + a2 ')[n]) ⊦ |
Used terms: (a1 ' + y0).last
The following image shows the proof tree of sequent calculus. The proved goal is at the bottom. You can click on the nodes to view additional rules. See here for details on colors in a proof tree.