| ⊦ DQinit(dqs) → DQINV(dqs) |
DQinit(dqs), ¬ DQINV(dqs) ⊦
| DQinit(dqs), ¬ DQINV(dqs) ⊦ |
dqs.gstate.queue = [], ∀ tid. dqs.pcf(tid) = idle ∧ dqs.lsf(tid).tid = tid ⊦ DQInv(dqs.gstate, dqs.lsf, dqs.pcf) ∧ fininvdeq(dqs.pcf)
Used simplifier rules: DQinit: ⊦ DQinit(dqs) ↔ dqs.gstate.queue = [] ∧ (∀ tid. dqs.pcf(tid) = idle ∧ dqs.lsf(tid).tid = tid); DQINV-def: ⊦ DQINV(dqs) ↔ DQInv(dqs.gstate, dqs.lsf, dqs.pcf) ∧ fininvdeq(dqs.pcf);
| dqs.gstate.queue = [], ∀ tid. dqs.pcf(tid) = idle ∧ dqs.lsf(tid).tid = tid ⊦ DQInv(dqs.gstate, dqs.lsf, dqs.pcf) ∧ fininvdeq(dqs.pcf) |
gs.queue = [], dqs = mkstate(gs, lsf, pcf), ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦ DQInv(gs, lsf, pcf) ∧ fininvdeq(pcf)
Used simplifier rules: ⊦ (gstate = s.gstate ∧ lsf = s.lsf) ∧ pcf = s.pcf ↔ s = mkstate(gstate, lsf, pcf); (elim) Used terms: dqs, gstate, lsf, pcf
| gs.queue = [], dqs = mkstate(gs, lsf, pcf), ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦ DQInv(gs, lsf, pcf) ∧ fininvdeq(pcf) |
gs.queue = [], ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦ DQInv(gs, lsf, pcf) ∧ fininvdeq(pcf)
| gs.queue = [], ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦ DQInv(gs, lsf, pcf) ∧ fininvdeq(pcf) |
gs = mkgs(queue), queue = [], ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦ DQInv(gs, lsf, pcf) ∧ fininvdeq(pcf)
Used simplifier rules: ⊦ queue = gs.queue ↔ gs = mkgs(queue); (elim) Used terms: gs, queue
| gs = mkgs(queue), queue = [], ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦ DQInv(gs, lsf, pcf) ∧ fininvdeq(pcf) |
∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦ DQInv(mkgs([]), lsf, pcf) ∧ fininvdeq(pcf)
| ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦ DQInv(mkgs([]), lsf, pcf) ∧ fininvdeq(pcf) |
¬ DQInv(mkgs([]), lsf, pcf), ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦
¬ fininvdeq(pcf), ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦
| ¬ DQInv(mkgs([]), lsf, pcf), ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦ |
(gs.queue = [] ∧ pcf = (λ tid. idle)) ∧ (∀ tid. tid = lsf(tid).tid) ⊦ DQInv(gs, lsf, pcf)
¬ DQInv(mkgs([]), lsf, pcf), ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦ (mkgs([]).queue = [] ∧ pcf = (λ tid. idle)) ∧ (∀ tid. tid = lsf(tid).tid)
Used terms: mkgs([]), lsf, pcf
| (gs.queue = [] ∧ pcf = (λ tid. idle)) ∧ (∀ tid. tid = lsf(tid).tid) ⊦ DQInv(gs, lsf, pcf) |
| ¬ DQInv(mkgs([]), lsf, pcf), ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦ (mkgs([]).queue = [] ∧ pcf = (λ tid. idle)) ∧ (∀ tid. tid = lsf(tid).tid) |
¬ DQInv(mkgs([]), lsf, pcf), ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦ pcf(tid) = idle ∧ tid0 = lsf(tid0).tid
Used simplifier rules: ⊦ mkgs(queue).queue = queue; (s)
| ¬ DQInv(mkgs([]), lsf, pcf), ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦ pcf(tid) = idle ∧ tid0 = lsf(tid0).tid |
lsf(tid0) = mkls(tid1, obsEmpty, val, optval, val0, optval0), ¬ DQInv(mkgs([]), lsf, pcf), ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦ pcf(tid) = idle ∧ tid0 = tid1
Used simplifier rules: ⊦ ( ( ((tid = ls.tid ∧ (obsEmpty ↔ ls.obsEmpty)) ∧ ival = ls.ival) ∧ oval = ls.oval) ∧ value = ls.value) ∧ optval = ls.optval ↔ ls = mkls(tid, obsEmpty, ival, oval, value, optval); (elim) Used terms: value, ival, obsEmpty, lsf(tid0), oval, tid1, optval
| lsf(tid0) = mkls(tid1, obsEmpty, val, optval, val0, optval0), ¬ DQInv(mkgs([]), lsf, pcf), ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦ pcf(tid) = idle ∧ tid0 = tid1 |
lsf(tid).tid = tid, lsf(tid0) = mkls(tid1, obsEmpty, val, optval, val0, optval0), pcf(tid) = idle, ¬ DQInv(mkgs([]), lsf, pcf), ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦ pcf(tid) = idle ∧ tid0 = tid1
Used terms: tid
| lsf(tid).tid = tid, lsf(tid0) = mkls(tid1, obsEmpty, val, optval, val0, optval0), pcf(tid) = idle, ¬ DQInv(mkgs([]), lsf, pcf), ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦ pcf(tid) = idle ∧ tid0 = tid1 |
lsf(tid).tid = tid, lsf(tid0) = mkls(tid1, obsEmpty, val, optval, val0, optval0), pcf(tid) = idle, tid0 ≠ tid1, ¬ DQInv(mkgs([]), lsf, pcf), ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦
| lsf(tid).tid = tid, lsf(tid0) = mkls(tid1, obsEmpty, val, optval, val0, optval0), pcf(tid) = idle, tid0 ≠ tid1, ¬ DQInv(mkgs([]), lsf, pcf), ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦ |
lsf(tid0) = mkls(tid1, obsEmpty, val, optval, val0, optval0), lsf(tid) = mkls(tid2, obsEmpty0, val1, optval1, val2, optval2), pcf(tid) = idle, tid2 = tid, tid0 ≠ tid1, ¬ DQInv(mkgs([]), lsf, pcf), ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦
Used simplifier rules: ⊦ ( ( ((tid = ls.tid ∧ (obsEmpty ↔ ls.obsEmpty)) ∧ ival = ls.ival) ∧ oval = ls.oval) ∧ value = ls.value) ∧ optval = ls.optval ↔ ls = mkls(tid, obsEmpty, ival, oval, value, optval); (elim) Used terms: value, ival, obsEmpty0, lsf(tid), oval, tid2, optval1
| lsf(tid0) = mkls(tid1, obsEmpty, val, optval, val0, optval0), lsf(tid) = mkls(tid2, obsEmpty0, val1, optval1, val2, optval2), pcf(tid) = idle, tid2 = tid, tid0 ≠ tid1, ¬ DQInv(mkgs([]), lsf, pcf), ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦ |
lsf(tid) = mkls(tid, obsEmpty0, val1, optval1, val2, optval2), lsf(tid0) = mkls(tid1, obsEmpty, val, optval, val0, optval0), pcf(tid) = idle, tid0 ≠ tid1, ¬ DQInv(mkgs([]), lsf, pcf), ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦
| lsf(tid) = mkls(tid, obsEmpty0, val1, optval1, val2, optval2), lsf(tid0) = mkls(tid1, obsEmpty, val, optval, val0, optval0), pcf(tid) = idle, tid0 ≠ tid1, ¬ DQInv(mkgs([]), lsf, pcf), ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦ |
Used simplifier rules: ⊦ mkls(tid, obsEmpty, ival, oval, ival0, oval0).tid = tid; (s) Used terms: tid0
| ¬ fininvdeq(pcf), ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦ |
⊦ fininvdeq(pcf) ↔ (∃ tids. ∀ tid. pcf(tid) = invDeq ↔ tid ∈ tids)
∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid, ∀ tids. ¬(∀ tid. pcf(tid) = invDeq ↔ tid ∈ tids) ⊦
Used terms: pcf
| ⊦ fininvdeq(pcf) ↔ (∃ tids. ∀ tid. pcf(tid) = invDeq ↔ tid ∈ tids) |
| ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid, ∀ tids. ¬(∀ tid. pcf(tid) = invDeq ↔ tid ∈ tids) ⊦ |
∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦ ∀ tid. pcf(tid) = invDeq ↔ tid ∈ ∅
Used terms: ∅
| ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦ ∀ tid. pcf(tid) = invDeq ↔ tid ∈ ∅ |
pcf(tid) = invDeq, ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦
Used simplifier rules: ⊦ ¬ a ∈ ∅; (s)
| pcf(tid) = invDeq, ∀ tid. pcf(tid) = idle ∧ lsf(tid).tid = tid ⊦ |
Used simplifier rules: ⊦ idle ≠ invDeq; (s) Used terms: tid
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.