| ⊦ trace(IOAut(startf, stepf))(⌜al⌝ + α) → (trace(IOAut(startf, stepf))(⌜al⌝ ) ↔ true) |
¬(trace(IOAut(startf, stepf))(⌜al⌝ ) ↔ true), trace(IOAut(startf, stepf))(⌜al⌝ + α) ⊦
| ¬(trace(IOAut(startf, stepf))(⌜al⌝ ) ↔ true), trace(IOAut(startf, stepf))(⌜al⌝ + α) ⊦ |
trace(IOAut(startf, stepf))(⌜al⌝ + α), ¬ trace(IOAut(startf, stepf))(⌜al⌝ ) ⊦
| trace(IOAut(startf, stepf))(⌜al⌝ + α), ¬ trace(IOAut(startf, stepf))(⌜al⌝ ) ⊦ |
⊦ trace(IOAut(startf, stepf))(α) ↔ (∃ σ, β. α = β ^ ∧ exec(IOAut(startf, stepf))(σ, β))
¬ trace(IOAut(startf, stepf))(⌜al⌝ ), ∃ σ, β. ⌜al⌝ + α = β ^ ∧ exec(IOAut(startf, stepf))(σ, β) ⊦
Used terms: ⌜al⌝ + α, stepf, startf
| ⊦ trace(IOAut(startf, stepf))(α) ↔ (∃ σ, β. α = β ^ ∧ exec(IOAut(startf, stepf))(σ, β)) |
| ¬ trace(IOAut(startf, stepf))(⌜al⌝ ), ∃ σ, β. ⌜al⌝ + α = β ^ ∧ exec(IOAut(startf, stepf))(σ, β) ⊦ |
⌜al⌝ + α = α0 ^, frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ¬ trace(IOAut(startf, stepf))(⌜al⌝ ) ⊦
Used simplifier rules: exec: ⊦ exec(IOAut(startf, stepf))(σ, β) ↔ frag(IOAut(startf, stepf))(σ, β) ∧ startf(σ[0]);
| ⌜al⌝ + α = α0 ^, frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ¬ trace(IOAut(startf, stepf))(⌜al⌝ ) ⊦ |
⊦ trace(IOAut(startf, stepf))(α) ↔ (∃ σ, β. α = β ^ ∧ exec(IOAut(startf, stepf))(σ, β))
⌜al⌝ + α = α0 ^, frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ∀ σ, β. ¬(⌜al⌝ = β ^ ∧ exec(IOAut(startf, stepf))(σ, β)) ⊦
Used terms: ⌜al⌝ , stepf, startf
| ⊦ trace(IOAut(startf, stepf))(α) ↔ (∃ σ, β. α = β ^ ∧ exec(IOAut(startf, stepf))(σ, β)) |
| ⌜al⌝ + α = α0 ^, frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ∀ σ, β. ¬(⌜al⌝ = β ^ ∧ exec(IOAut(startf, stepf))(σ, β)) ⊦ |
⌜al⌝ + α = α0 ^, frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ∀ σ0, β. ⌜al⌝ ≠ β ^ ∨ ¬ frag(IOAut(startf, stepf))(σ0, β) ∨ ¬ startf(σ0[0]) ⊦
Used simplifier rules: exec: ⊦ exec(IOAut(startf, stepf))(σ, β) ↔ frag(IOAut(startf, stepf))(σ, β) ∧ startf(σ[0]);
| ⌜al⌝ + α = α0 ^, frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ∀ σ0, β. ⌜al⌝ ≠ β ^ ∨ ¬ frag(IOAut(startf, stepf))(σ0, β) ∨ ¬ startf(σ0[0]) ⊦ |
⊦ ¬ # α ^ < ⌜n⌝ → (∃ m. ¬ # α < ⌜m⌝ ∧ α ^ to n = (α to m)^)
⌜al⌝ + α = α0 ^, frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ¬ # α0 ^ < ⌜# al⌝ → (∃ m. ¬ # α0 < ⌜m⌝ ∧ α0 ^ to # al = (α0 to m)^), ∀ σ0, β. ⌜al⌝ ≠ β ^ ∨ ¬ frag(IOAut(startf, stepf))(σ0, β) ∨ ¬ startf(σ0[0]) ⊦
Used terms: α0, # al
| ⊦ ¬ # α ^ < ⌜n⌝ → (∃ m. ¬ # α < ⌜m⌝ ∧ α ^ to n = (α to m)^) |
| ⌜al⌝ + α = α0 ^, frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ¬ # α0 ^ < ⌜# al⌝ → (∃ m. ¬ # α0 < ⌜m⌝ ∧ α0 ^ to # al = (α0 to m)^), ∀ σ0, β. ⌜al⌝ ≠ β ^ ∨ ¬ frag(IOAut(startf, stepf))(σ0, β) ∨ ¬ startf(σ0[0]) ⊦ |
⌜al⌝ + α = α0 ^, frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ¬ # α0 ^ < ⌜# al⌝ → ¬ # α0 < ⌜m⌝ ∧ α0 ^ to # al = (α0 to m)^, ∀ σ0, β. ⌜al⌝ ≠ β ^ ∨ ¬ frag(IOAut(startf, stepf))(σ0, β) ∨ ¬ startf(σ0[0]) ⊦
| ⌜al⌝ + α = α0 ^, frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ¬ # α0 ^ < ⌜# al⌝ → ¬ # α0 < ⌜m⌝ ∧ α0 ^ to # al = (α0 to m)^, ∀ σ0, β. ⌜al⌝ ≠ β ^ ∨ ¬ frag(IOAut(startf, stepf))(σ0, β) ∨ ¬ startf(σ0[0]) ⊦ |
⌜al⌝ + α = α0 ^, # α0 ^ < ⌜# al⌝ , frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ∀ σ0, β. ⌜al⌝ ≠ β ^ ∨ ¬ frag(IOAut(startf, stepf))(σ0, β) ∨ ¬ startf(σ0[0]) ⊦
⌜al⌝ + α = α0 ^, α0 ^ to # al = (α0 to m)^, frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ¬ # α0 < ⌜m⌝ , ∀ σ0, β. ⌜al⌝ ≠ β ^ ∨ ¬ frag(IOAut(startf, stepf))(σ0, β) ∨ ¬ startf(σ0[0]) ⊦
| ⌜al⌝ + α = α0 ^, # α0 ^ < ⌜# al⌝ , frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ∀ σ0, β. ⌜al⌝ ≠ β ^ ∨ ¬ frag(IOAut(startf, stepf))(σ0, β) ∨ ¬ startf(σ0[0]) ⊦ |
⌜al⌝ + α = α0 ^, # α0 ^ < ⌜# al⌝ , frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ∀ σ0, β. ⌜al⌝ ≠ β ^ ∨ ¬ frag(IOAut(startf, stepf))(σ0, β) ∨ ¬ startf(σ0[0]) ⊦
| ⌜al⌝ + α = α0 ^, # α0 ^ < ⌜# al⌝ , frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ∀ σ0, β. ⌜al⌝ ≠ β ^ ∨ ¬ frag(IOAut(startf, stepf))(σ0, β) ∨ ¬ startf(σ0[0]) ⊦ |
Used simplifier rules: ⊦ #(σ + σ1) = # σ + # σ1; (s) ⊦ # ⌜x⌝ = ⌜# x⌝ ; (s) append-assoc: ⊦ (σ + σ1) + σ2 = σ + σ1 + σ2; from specification stream[actionstream] ⊦ ¬ n∞ + n∞1 < n∞1; (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
| ⌜al⌝ + α = α0 ^, α0 ^ to # al = (α0 to m)^, frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ¬ # α0 < ⌜m⌝ , ∀ σ0, β. ⌜al⌝ ≠ β ^ ∨ ¬ frag(IOAut(startf, stepf))(σ0, β) ∨ ¬ startf(σ0[0]) ⊦ |
⌜al⌝ + α = α0 ^, α0 ^ to # al = (α0 to m)^, frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ¬ # α0 < ⌜m⌝ , ∀ σ0, β. ⌜al⌝ ≠ β ^ ∨ ¬ frag(IOAut(startf, stepf))(σ0, β) ∨ ¬ startf(σ0[0]) ⊦
| ⌜al⌝ + α = α0 ^, α0 ^ to # al = (α0 to m)^, frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ¬ # α0 < ⌜m⌝ , ∀ σ0, β. ⌜al⌝ ≠ β ^ ∨ ¬ frag(IOAut(startf, stepf))(σ0, β) ∨ ¬ startf(σ0[0]) ⊦ |
⌜al⌝ + α = α0 ^, α0 ^ to # al = (α0 to m)^, frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ¬ # α0 < ⌜m⌝ , ⌜al⌝ ≠ (α0 to m)^ ∨ ¬ frag(IOAut(startf, stepf))(σ to m + 1, α0 to m) ∨ ¬ startf((σ to m + 1)[0]) ⊦
Used terms: σ to m + 1, α0 to m
| ⌜al⌝ + α = α0 ^, α0 ^ to # al = (α0 to m)^, frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ¬ # α0 < ⌜m⌝ , ⌜al⌝ ≠ (α0 to m)^ ∨ ¬ frag(IOAut(startf, stepf))(σ to m + 1, α0 to m) ∨ ¬ startf((σ to m + 1)[0]) ⊦ |
⌜al⌝ + α = α0 ^, α0 ^ to # al = (α0 to m)^, frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ¬ # α0 < ⌜m⌝ , ⌜al⌝ ≠ α0 ^ to # al ∨ ¬ startf((σ to m + 1)[0]) ⊦
Used simplifier rules: frag-to-1: ⊦ frag(IOAut(startf, stepf))(σ, α) ∧ ¬ # α < ⌜n⌝ → (frag(IOAut(startf, stepf))(σ to n + 1, α to n) ↔ true); c: ⊦ m + n = n + m; from specification nat-basic a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic
| ⌜al⌝ + α = α0 ^, α0 ^ to # al = (α0 to m)^, frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ¬ # α0 < ⌜m⌝ , ⌜al⌝ ≠ α0 ^ to # al ∨ ¬ startf((σ to m + 1)[0]) ⊦ |
⌜al⌝ + α = α0 ^, α0 ^ to # al = (α0 to m)^, ⌜al⌝ ≠ α0 ^ to # al, frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ¬ # α0 < ⌜m⌝ ⊦
⌜al⌝ + α = α0 ^, α0 ^ to # al = (α0 to m)^, frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ¬ # α0 < ⌜m⌝ , ¬ startf((σ to m + 1)[0]) ⊦
| ⌜al⌝ + α = α0 ^, α0 ^ to # al = (α0 to m)^, ⌜al⌝ ≠ α0 ^ to # al, frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ¬ # α0 < ⌜m⌝ ⊦ |
Used simplifier rules: ⊦ ⌜x⌝ + σ to # x = ⌜x⌝ ; (s) append-assoc: ⊦ (σ + σ1) + σ2 = σ + σ1 + σ2; from specification stream[actionstream] ⊦ ⌜x⌝ = ⌜x0⌝ ↔ x = x0; (s)
| ⌜al⌝ + α = α0 ^, α0 ^ to # al = (α0 to m)^, frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ¬ # α0 < ⌜m⌝ , ¬ startf((σ to m + 1)[0]) ⊦ |
m < n, ¬ # σ < ⌜n⌝ ⊦ (σ to n)[m] = σ[m]
⌜al⌝ + α = α0 ^, α0 ^ to # al = (α0 to m)^, frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ¬ # α0 < ⌜m⌝ , ¬ startf((σ to m + 1)[0]) ⊦ 0 < m + 1 ∧ ¬ # σ < ⌜m + 1⌝
Used terms: 0, m + 1, σ
| m < n, ¬ # σ < ⌜n⌝ ⊦ (σ to n)[m] = σ[m] |
| ⌜al⌝ + α = α0 ^, α0 ^ to # al = (α0 to m)^, frag(IOAut(startf, stepf))(σ, α0), startf(σ[0]), ¬ # α0 < ⌜m⌝ , ¬ startf((σ to m + 1)[0]) ⊦ 0 < m + 1 ∧ ¬ # σ < ⌜m + 1⌝ |
⌜al⌝ + α = ⌜af⌝ ^, ⌜al⌝ = ⌜af to m⌝ ^, frag(IOAut(startf, stepf))(σ, ⌜af⌝ ), startf(σ[0]), ¬ ⌜m⌝ < # σ, ¬ startf((σ to m + 1)[0]) ⊦
Used simplifier rules: frag-size-2: ⊦ frag(IOAut(startf, stepf))(σ, α) → (# α < # σ ↔ finp(α)); append-assoc: ⊦ (σ + σ1) + σ2 = σ + σ1 + σ2; from specification stream[actionstream] ⊦ ⌜x⌝ + σ to # x = ⌜x⌝ ; (s) ⊦ ¬ finp(⌜nf⌝ ); (s) ⊦ ⌜nf⌝ to n = ⌜nf to n⌝ ; (s) stream-inf-forward: ⊦ ¬ finp(σ) → (∃ nf. ⌜nf⌝ = σ); (forward) from specification stream-basic[actionstream] ⊦ ¬ ∞ < n∞; (s) ⊦ ¬ finp(σ) → # σ = ∞; (s) lele-trans: ⊦ ¬ n∞1 < n∞ ∧ ¬ n∞2 < n∞1 → ¬ n∞2 < n∞; (forward) from specification nat-inf 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⌝ + ⌜1⌝ ↔ ¬ ⌜n⌝ < # σ; (s) c: ⊦ m + n = n + m; from specification nat-basic a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic ⊦ ⌜m + n⌝ = ⌜m⌝ + ⌜n⌝ ; (s) ⊦ m + 1 ≠ 0; (s) ⊦ 0 < m ↔ m ≠ 0; (s)
| ⌜al⌝ + α = ⌜af⌝ ^, ⌜al⌝ = ⌜af to m⌝ ^, frag(IOAut(startf, stepf))(σ, ⌜af⌝ ), startf(σ[0]), ¬ ⌜m⌝ < # σ, ¬ startf((σ to m + 1)[0]) ⊦ |
⊦ frag(IOAut(startf, stepf))(σ, β) ↔ # σ = # β + ⌜1⌝ ∧ (∀ n. ⌜n⌝ < # β → stepf(σ[n], β[n], σ[n +1]))
Used simplifier rules: ⊦ # ⌜nf⌝ = ∞; (s) ⊦ ⌜m⌝ + ∞ = ∞; (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 ⊦ 0 < m ↔ m ≠ 0; (s) ⊦ m + 1 ≠ 0; (s) ⊦ ⌜m + n⌝ = ⌜m⌝ + ⌜n⌝ ; (s) a: ⊦ (m + n0) + n1 = m + n0 + n1; from specification nat-basic c: ⊦ m + n = n + m; from specification nat-basic ⊦ ¬ ∞ < n∞; (s) m < n, ¬ # σ < ⌜n⌝ ⊦ (σ to n)[m] = σ[m]; (s) Used terms: startf, stepf, σ, ⌜af⌝
| ⊦ frag(IOAut(startf, stepf))(σ, β) ↔ # σ = # β + ⌜1⌝ ∧ (∀ n. ⌜n⌝ < # β → stepf(σ[n], β[n], σ[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.