| n ≤ # al ⊦ ¬ # ⌜al⌝ ^ < # ⌜al to n⌝ ^ |
# ⌜al⌝ ^ < # ⌜al to n⌝ ^, n ≤ # al ⊦
| # ⌜al⌝ ^ < # ⌜al to n⌝ ^, n ≤ # al ⊦ |
# ⌜al⌝ ^ < # ⌜al to n⌝ ^, n ≤ # al ⊦
| # ⌜al⌝ ^ < # ⌜al to n⌝ ^, n ≤ # al ⊦ |
# ⌜a + al0⌝ ^ < # ⌜a + al0 to n⌝ ^, n ≤ #(a + al0), ∀ n. ¬(# ⌜al0⌝ ^ < # ⌜al0 to n⌝ ^ ∧ n ≤ # al0) ⊦
Used simplifier rules: remtau-empty: ⊦ [] ^ = []; actionlist freely generated by [], +;; ⊦ # [] = 0; (s) ⊦ m ≤ 0 ↔ m = 0; (s) ⊦ # [] = ⌜0⌝ ; (s) ⊦ ⌜0⌝ < # σ ↔ σ ≠ []; (s) ⊦ x to 0 = []; (s) ⊦ ⌜[]⌝ = []; (s)
| # ⌜a + al0⌝ ^ < # ⌜a + al0 to n⌝ ^, n ≤ #(a + al0), ∀ n. ¬(# ⌜al0⌝ ^ < # ⌜al0 to n⌝ ^ ∧ n ≤ # al0) ⊦ |
# ⌜a '⌝ ^ + # ⌜al0⌝ ^ < # ⌜a ' + al0 to n⌝ ^, n ≤ # al0 + 1, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦
Used simplifier rules: remtau-fin-append: ⊦ (⌜al⌝ + ⌜al2⌝ )^ = ⌜al⌝ ^ + ⌜al2⌝ ^; ⊦ a + x = a ' + x; (s) append-assoc: ⊦ (σ + σ1) + σ2 = σ + σ1 + σ2; from specification stream[actionstream] ⊦ #(σ + σ1) = # σ + # σ1; (s) a: ⊦ (x + y) + z = x + y + z; from specification list[actionstream] ⊦ ⌜x + y⌝ = ⌜x⌝ + ⌜y⌝ ; (s) ⊦ m +1 = m + 1; (s) ⊦ #(a ' + x) = (# x)+1; (s)
| # ⌜a '⌝ ^ + # ⌜al0⌝ ^ < # ⌜a ' + al0 to n⌝ ^, n ≤ # al0 + 1, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦ |
⊦ a ≠ τ → ⌜a '⌝ ^ = ⌜a '⌝
a = τ, # ⌜a '⌝ ^ + # ⌜al0⌝ ^ < # ⌜a ' + al0 to n⌝ ^, n ≤ # al0 + 1, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦
a ≠ τ, # ⌜a '⌝ + # ⌜al0⌝ ^ < # ⌜a ' + al0 to n⌝ ^, n ≤ # al0 + 1, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦
Used terms: a
| ⊦ a ≠ τ → ⌜a '⌝ ^ = ⌜a '⌝ |
| a = τ, # ⌜a '⌝ ^ + # ⌜al0⌝ ^ < # ⌜a ' + al0 to n⌝ ^, n ≤ # al0 + 1, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦ |
# ⌜al0⌝ ^ < # ⌜τ ' + al0 to n⌝ ^, n ≤ # al0 + 1, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦
Used simplifier rules: remtau-onetau: ⊦ ⌜τ '⌝ ^ = []; 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∞ + ⌜0⌝ = n∞; (s) ⊦ # [] = ⌜0⌝ ; (s)
| # ⌜al0⌝ ^ < # ⌜τ ' + al0 to n⌝ ^, n ≤ # al0 + 1, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦ |
⊦ # x < n → x + y to n = x + (y to (n - # x))
# ⌜al0⌝ ^ < # ⌜τ ' + (al0 to (n - # τ '))⌝ ^, # τ ' < n, n ≤ # al0 + 1, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦
Used simplifier rules: remtau-empty: ⊦ [] ^ = []; remtau-onetau: ⊦ ⌜τ '⌝ ^ = []; ⊦ # a ' = 0 +1; (s) ⊦ 1 < m ↔ ¬(m = 0 ∨ m = 1); (s) ⊦ 0 ≤ m; (s) ⊦ x to 0 = []; (s) ⊦ ⌜[]⌝ = []; (s) ⊦ m ≤ m + n; (s) a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic c: ⊦ m + n = n + m; from specification nat-basic ⊦ a ' + y to 1 = a '; (s) a: ⊦ (x + y) + z = x + y + z; from specification list[actionstream] ⊦ # [] = ⌜0⌝ ; (s) ⊦ ¬ n∞ < ⌜0⌝ ; (s) Used terms: n, al0, τ '
| ⊦ # x < n → x + y to n = x + (y to (n - # x)) |
| # ⌜al0⌝ ^ < # ⌜τ ' + (al0 to (n - # τ '))⌝ ^, # τ ' < n, n ≤ # al0 + 1, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦ |
n ≠ 1, n ≠ 0, # ⌜al0⌝ ^ < # ⌜al0 to (n - 1)⌝ ^, n ≤ # al0 + 1, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦
Used simplifier rules: remtau-tau-lem: ⊦ (⌜τ '⌝ + α)^ = α ^; append-assoc: ⊦ (σ + σ1) + σ2 = σ + σ1 + σ2; from specification stream[actionstream] a: ⊦ (x + y) + z = x + y + z; from specification list[actionstream] ⊦ ⌜x + y⌝ = ⌜x⌝ + ⌜y⌝ ; (s) ⊦ # a ' = 0 +1; (s) ⊦ 1 < m ↔ ¬(m = 0 ∨ m = 1); (s)
| n ≠ 1, n ≠ 0, # ⌜al0⌝ ^ < # ⌜al0 to (n - 1)⌝ ^, n ≤ # al0 + 1, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦ |
n = n1 + 1, n ≠ 1, n ≠ 0, # ⌜al0⌝ ^ < # ⌜al0 to n1⌝ ^, n ≤ # al0 + 1, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦
Used simplifier rules: n ≠ 0 ⊦ m = n - 1 ↔ n = m + 1; (elim) Used terms: n, m
| n = n1 + 1, n ≠ 1, n ≠ 0, # ⌜al0⌝ ^ < # ⌜al0 to n1⌝ ^, n ≤ # al0 + 1, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦ |
n1 ≠ 0, # ⌜al0⌝ ^ < # ⌜al0 to n1⌝ ^, n1 ≤ # al0, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦
Used simplifier rules: c: ⊦ m + n = n + m; from specification nat-basic a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic ⊦ m + n ≤ m + n0 ↔ n ≤ n0; (s) ⊦ m + 1 ≠ 0; (s) ⊦ m + n = 1 ↔ m = 0 ∧ n = 1 ∨ n = 0 ∧ m = 1; (ws)
| n1 ≠ 0, # ⌜al0⌝ ^ < # ⌜al0 to n1⌝ ^, n1 ≤ # al0, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦ |
Used terms: n1
| a ≠ τ, # ⌜a '⌝ + # ⌜al0⌝ ^ < # ⌜a ' + al0 to n⌝ ^, n ≤ # al0 + 1, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦ |
a ≠ τ, ⌜1⌝ + # ⌜al0⌝ ^ < # ⌜a ' + al0 to n⌝ ^, n ≤ # al0 + 1, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦
Used simplifier rules: ⊦ # a ' = 0 +1; (s) ⊦ # ⌜x⌝ = ⌜# x⌝ ; (s)
| a ≠ τ, ⌜1⌝ + # ⌜al0⌝ ^ < # ⌜a ' + al0 to n⌝ ^, n ≤ # al0 + 1, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦ |
⊦ n ≤ # x → x + y to n = x to n
a ≠ τ, ⌜1⌝ + # ⌜al0⌝ ^ < # ⌜a ' + al0 to n⌝ ^, n ≤ # al0 + 1, ¬ n ≤ # a ', ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦
a ≠ τ, ⌜1⌝ + # ⌜al0⌝ ^ < # ⌜a ' to n⌝ ^, n ≤ # al0 + 1, n ≤ # a ', ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦
Used terms: n, al0, a '
| ⊦ n ≤ # x → x + y to n = x to n |
| a ≠ τ, ⌜1⌝ + # ⌜al0⌝ ^ < # ⌜a ' + al0 to n⌝ ^, n ≤ # al0 + 1, ¬ n ≤ # a ', ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦ |
a ≠ τ, n ≠ 0, n ≠ 1, ⌜1⌝ + # ⌜al0⌝ ^ < # ⌜a ' + al0 to n⌝ ^, n ≤ # al0 + 1, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦
Used simplifier rules: ⊦ 1 < m ↔ ¬(m = 0 ∨ m = 1); (s) ⊦ m ≤ n ↔ ¬ n < m; (ss) ⊦ # a ' = 0 +1; (s)
| a ≠ τ, n ≠ 0, n ≠ 1, ⌜1⌝ + # ⌜al0⌝ ^ < # ⌜a ' + al0 to n⌝ ^, n ≤ # al0 + 1, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦ |
⊦ # x < n → x + y to n = x + (y to (n - # x))
a ≠ τ, n ≠ 0, n ≠ 1, ⌜1⌝ + # ⌜al0⌝ ^ < # ⌜a ' + (al0 to (n - # a '))⌝ ^, # a ' < n, n ≤ # al0 + 1, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦
Used simplifier rules: ⊦ # a ' = 0 +1; (s) ⊦ m ≠ 0 → (1 < m ↔ m ≠ 1); (ss) Used terms: n, al0, a '
| ⊦ # x < n → x + y to n = x + (y to (n - # x)) |
| a ≠ τ, n ≠ 0, n ≠ 1, ⌜1⌝ + # ⌜al0⌝ ^ < # ⌜a ' + (al0 to (n - # a '))⌝ ^, # a ' < n, n ≤ # al0 + 1, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦ |
a ≠ τ, n ≠ 1, n ≠ 0, # ⌜al0⌝ ^ < # ⌜al0 to (n - 1)⌝ ^, n ≤ # al0 + 1, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦
Used simplifier rules: remtau-nontau-lem: ⊦ a ≠ τ → (⌜a '⌝ + β)^ = ⌜a '⌝ + β ^; 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∞ + ⌜0⌝ = n∞; (s) ⊦ m ≤ n → (⌜(* m)⌝ + n∞2 < ⌜(* n)⌝ + n∞1 ↔ n∞2 < ⌜n - m⌝ + n∞1); (s) append-assoc: ⊦ (σ + σ1) + σ2 = σ + σ1 + σ2; from specification stream[actionstream] ⊦ # a ' = 0 +1; (s) ⊦ # ⌜x⌝ = ⌜# x⌝ ; (s) ⊦ #(σ + σ1) = # σ + # σ1; (s) a: ⊦ (x + y) + z = x + y + z; from specification list[actionstream] ⊦ ⌜x + y⌝ = ⌜x⌝ + ⌜y⌝ ; (s) ⊦ 1 < m ↔ ¬(m = 0 ∨ m = 1); (s) ⊦ m < n → n ≠ 0; (s)
| a ≠ τ, n ≠ 1, n ≠ 0, # ⌜al0⌝ ^ < # ⌜al0 to (n - 1)⌝ ^, n ≤ # al0 + 1, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦ |
n = n1 + 1, a ≠ τ, n ≠ 1, n ≠ 0, # ⌜al0⌝ ^ < # ⌜al0 to n1⌝ ^, n ≤ # al0 + 1, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦
Used simplifier rules: n ≠ 0 ⊦ m = n - 1 ↔ n = m + 1; (elim) Used terms: n, m
| n = n1 + 1, a ≠ τ, n ≠ 1, n ≠ 0, # ⌜al0⌝ ^ < # ⌜al0 to n1⌝ ^, n ≤ # al0 + 1, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦ |
a ≠ τ, n1 ≠ 0, # ⌜al0⌝ ^ < # ⌜al0 to n1⌝ ^, n1 ≤ # al0, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦
Used simplifier rules: c: ⊦ m + n = n + m; from specification nat-basic a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic ⊦ m + n ≤ m + n0 ↔ n ≤ n0; (s) ⊦ m + 1 ≠ 0; (s) ⊦ m + n = 1 ↔ m = 0 ∧ n = 1 ∨ n = 0 ∧ m = 1; (ws)
| a ≠ τ, n1 ≠ 0, # ⌜al0⌝ ^ < # ⌜al0 to n1⌝ ^, n1 ≤ # al0, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦ |
Used terms: n1
| a ≠ τ, ⌜1⌝ + # ⌜al0⌝ ^ < # ⌜a ' to n⌝ ^, n ≤ # al0 + 1, n ≤ # a ', ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦ |
a ≠ τ, ⌜1⌝ + # ⌜al0⌝ ^ < # ⌜a ' to n⌝ ^, n ≤ # al0 + 1, n ≤ 1, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦
Used simplifier rules: ⊦ # a ' = 0 +1; (s)
| a ≠ τ, ⌜1⌝ + # ⌜al0⌝ ^ < # ⌜a ' to n⌝ ^, n ≤ # al0 + 1, n ≤ 1, ∀ n0. ¬ # ⌜al0⌝ ^ < # ⌜al0 to n0⌝ ^ ∨ ¬ n0 ≤ # al0 ⊦ |
Used simplifier rules: remtau-one: ⊦ a ≠ τ → ⌜a '⌝ ^ = ⌜a '⌝ ; remtau-empty: ⊦ [] ^ = []; ⊦ m ≠ n → (m ≤ n ↔ m < n); (s) ⊦ m < 1 ↔ m = 0; (s) ⊦ 0 ≤ m; (s) ⊦ x to 0 = []; (s) ⊦ ⌜[]⌝ = []; (s) ⊦ # [] = ⌜0⌝ ; (s) ⊦ m < n → (⌜n⌝ + n∞ < ⌜m⌝ ↔ false); (s) add-assoc: ⊦ (n∞ + n∞1) + n∞2 = n∞ + n∞1 + n∞2; from specification nat-inf add-comm: ⊦ n∞1 + n∞2 = n∞2 + n∞1; from specification nat-inf ⊦ m ≤ m + n; (s) a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic c: ⊦ m + n = n + m; from specification nat-basic ⊦ a ' to 1 = a '; (s) ⊦ # ⌜x⌝ = ⌜# x⌝ ; (s) ⊦ # a ' = 0 +1; (s) ⊦ m ≤ n → (⌜(* m)⌝ + n∞2 < ⌜(* n)⌝ ↔ n∞2 < ⌜n - m⌝ ); (s) ⊦ ¬ n∞ < ⌜0⌝ ; (s) Used formulas: n = 1
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.