TSTP Solution File: SWV454+1 by Twee---2.4.2
View Problem
- Process Solution
%------------------------------------------------------------------------------
% File : Twee---2.4.2
% Problem : SWV454+1 : TPTP v8.1.2. Released v4.0.0.
% Transfm : none
% Format : tptp:raw
% Command : parallel-twee %s --tstp --conditional-encoding if --smaller --drop-non-horn --give-up-on-saturation --explain-encoding --formal-proof
% Computer : n007.cluster.edu
% Model : x86_64 x86_64
% CPU : Intel(R) Xeon(R) CPU E5-2620 v4 2.10GHz
% Memory : 8042.1875MB
% OS : Linux 3.10.0-693.el7.x86_64
% CPULimit : 300s
% WCLimit : 300s
% DateTime : Thu Aug 31 23:04:32 EDT 2023
% Result : Theorem 4.07s 0.88s
% Output : Proof 4.59s
% Verified :
% SZS Type : -
% Comments :
%------------------------------------------------------------------------------
%----WARNING: Could not form TPTP format derivation
%------------------------------------------------------------------------------
%----ORIGINAL SYSTEM OUTPUT
% 0.03/0.12 % Problem : SWV454+1 : TPTP v8.1.2. Released v4.0.0.
% 0.03/0.12 % Command : parallel-twee %s --tstp --conditional-encoding if --smaller --drop-non-horn --give-up-on-saturation --explain-encoding --formal-proof
% 0.12/0.33 % Computer : n007.cluster.edu
% 0.12/0.33 % Model : x86_64 x86_64
% 0.12/0.33 % CPU : Intel(R) Xeon(R) CPU E5-2620 v4 @ 2.10GHz
% 0.12/0.33 % Memory : 8042.1875MB
% 0.12/0.33 % OS : Linux 3.10.0-693.el7.x86_64
% 0.12/0.33 % CPULimit : 300
% 0.12/0.33 % WCLimit : 300
% 0.12/0.33 % DateTime : Tue Aug 29 07:20:43 EDT 2023
% 0.12/0.33 % CPUTime :
% 4.07/0.88 Command-line arguments: --no-flatten-goal
% 4.07/0.88
% 4.07/0.88 % SZS status Theorem
% 4.07/0.88
% 4.07/0.89 % SZS output start Proof
% 4.07/0.89 Take the following subset of the input axioms:
% 4.59/0.93 fof(axiom_46, axiom, ![Q, X, Y]: (elem(X, cons(Y, Q)) <=> (X=Y | elem(X, Q)))).
% 4.59/0.94 fof(conj, conjecture, ![X2, Y2, V, W]: ((![Z, Pid0]: (setIn(Pid0, alive) => ~elem(m_Down(Pid0), queue(host(Z)))) & (![Z2, Pid0_2]: (elem(m_Down(Pid0_2), queue(host(Z2))) => ~setIn(Pid0_2, alive)) & (![Z2, Pid0_2]: (elem(m_Down(Pid0_2), queue(host(Z2))) => host(Pid0_2)!=host(Z2)) & (![Z2, Pid0_2]: (elem(m_Halt(Pid0_2), queue(host(Z2))) => ~leq(host(Z2), host(Pid0_2))) & (![Pid20, Z2, Pid0_2]: (elem(m_Ack(Pid0_2, Z2), queue(host(Pid20))) => ~leq(host(Z2), host(Pid0_2))) & (![Z2, Pid0_2]: ((~setIn(Z2, alive) & (leq(Pid0_2, Z2) & host(Pid0_2)=host(Z2))) => ~setIn(Pid0_2, alive)) & (![Z2, Pid0_2]: ((Pid0_2!=Z2 & host(Pid0_2)=host(Z2)) => (~setIn(Z2, alive) | ~setIn(Pid0_2, alive))) & (![Pid30, Z2, Pid0_2, Pid20_2]: ((host(Pid20_2)!=host(Z2) & (setIn(Z2, alive) & (setIn(Pid20_2, alive) & (host(Pid30)=host(Z2) & host(Pid0_2)=host(Pid20_2))))) => ~(elem(m_Down(Pid0_2), queue(host(Z2))) & elem(m_Down(Pid30), queue(host(Pid20_2))))) & queue(host(X2))=cons(m_Down(Y2), V))))))))) => (setIn(X2, alive) => (~leq(host(X2), host(Y2)) => (~((index(ldr, host(X2))=host(Y2) & index(status, host(X2))=norm) | (index(status, host(X2))=wait & host(Y2)=host(index(elid, host(X2))))) => ((![Z2]: ((~leq(host(X2), Z2) & leq(s(zero), Z2)) => (setIn(Z2, index(down, host(X2))) | Z2=host(Y2))) & index(status, host(X2))=elec_1) => (~leq(nbr_proc, host(X2)) => ![Z2]: (s(host(X2))!=host(Z2) => (host(X2)=host(Z2) => ![W0, X0]: (s(host(X2))!=host(X0) => (host(X2)!=host(X0) => ![Y0]: ((host(X0)!=host(Z2) & (setIn(Z2, alive) & (setIn(X0, alive) & (host(W0)=host(Z2) & host(Y0)=host(X0))))) => ~(elem(m_Down(Y0), V) & elem(m_Down(W0), queue(host(X0)))))))))))))))).
% 4.59/0.94
% 4.59/0.94 Now clausify the problem and encode Horn clauses using encoding 3 of
% 4.59/0.94 http://www.cse.chalmers.se/~nicsma/papers/horn.pdf.
% 4.59/0.94 We repeatedly replace C & s=t => u=v by the two clauses:
% 4.59/0.94 fresh(y, y, x1...xn) = u
% 4.59/0.94 C => fresh(s, t, x1...xn) = v
% 4.59/0.94 where fresh is a fresh function symbol and x1..xn are the free
% 4.59/0.94 variables of u and v.
% 4.59/0.94 A predicate p(X) is encoded as p(X)=true (this is sound, because the
% 4.59/0.94 input problem has no model of domain size 1).
% 4.59/0.94
% 4.59/0.94 The encoding turns the above axioms into the following unit equations and goals:
% 4.59/0.94
% 4.59/0.94 Axiom 1 (conj_2): host(w0) = host(z).
% 4.59/0.94 Axiom 2 (conj_3): host(y0) = host(x0).
% 4.59/0.94 Axiom 3 (conj_1): host(x) = host(z).
% 4.59/0.94 Axiom 4 (conj_8): setIn(z, alive) = true2.
% 4.59/0.94 Axiom 5 (conj_9): setIn(x0, alive) = true2.
% 4.59/0.94 Axiom 6 (conj): queue(host(x)) = cons(m_Down(y), v).
% 4.59/0.94 Axiom 7 (conj_6): elem(m_Down(y0), v) = true2.
% 4.59/0.94 Axiom 8 (conj_13): fresh40(X, X, Y, Z) = host(Y).
% 4.59/0.94 Axiom 9 (conj_13): fresh38(X, X, Y, Z, W) = host(W).
% 4.59/0.94 Axiom 10 (axiom_46_1): fresh32(X, X, Y, Z, W) = true2.
% 4.59/0.94 Axiom 11 (conj_5): elem(m_Down(w0), queue(host(x0))) = true2.
% 4.59/0.94 Axiom 12 (conj_13): fresh39(X, X, Y, Z, W, V) = fresh40(host(Z), host(Y), Y, W).
% 4.59/0.94 Axiom 13 (conj_13): fresh37(X, X, Y, Z, W, V) = fresh38(host(V), host(W), Y, Z, W).
% 4.59/0.94 Axiom 14 (axiom_46_1): fresh32(elem(X, Y), true2, X, Z, Y) = elem(X, cons(Z, Y)).
% 4.59/0.94 Axiom 15 (conj_13): fresh35(X, X, Y, Z, W, V) = fresh36(setIn(Y, alive), true2, Y, Z, W, V).
% 4.59/0.94 Axiom 16 (conj_13): fresh36(X, X, Y, Z, W, V) = fresh39(elem(m_Down(Z), queue(host(W))), true2, Y, Z, W, V).
% 4.59/0.94 Axiom 17 (conj_13): fresh35(setIn(X, alive), true2, Y, Z, X, W) = fresh37(elem(m_Down(W), queue(host(Y))), true2, Y, Z, X, W).
% 4.59/0.94
% 4.59/0.94 Lemma 18: host(x) = host(w0).
% 4.59/0.94 Proof:
% 4.59/0.94 host(x)
% 4.59/0.94 = { by axiom 3 (conj_1) }
% 4.59/0.94 host(z)
% 4.59/0.94 = { by axiom 1 (conj_2) R->L }
% 4.59/0.94 host(w0)
% 4.59/0.94
% 4.59/0.94 Lemma 19: host(y0) = host(w0).
% 4.59/0.94 Proof:
% 4.59/0.94 host(y0)
% 4.59/0.94 = { by axiom 2 (conj_3) }
% 4.59/0.94 host(x0)
% 4.59/0.94 = { by axiom 9 (conj_13) R->L }
% 4.59/0.94 fresh38(host(x0), host(x0), z, w0, x0)
% 4.59/0.94 = { by axiom 2 (conj_3) R->L }
% 4.59/0.94 fresh38(host(y0), host(x0), z, w0, x0)
% 4.59/0.94 = { by axiom 13 (conj_13) R->L }
% 4.59/0.94 fresh37(true2, true2, z, w0, x0, y0)
% 4.59/0.94 = { by axiom 10 (axiom_46_1) R->L }
% 4.59/0.94 fresh37(fresh32(true2, true2, m_Down(y0), m_Down(y), v), true2, z, w0, x0, y0)
% 4.59/0.94 = { by axiom 7 (conj_6) R->L }
% 4.59/0.94 fresh37(fresh32(elem(m_Down(y0), v), true2, m_Down(y0), m_Down(y), v), true2, z, w0, x0, y0)
% 4.59/0.94 = { by axiom 14 (axiom_46_1) }
% 4.59/0.94 fresh37(elem(m_Down(y0), cons(m_Down(y), v)), true2, z, w0, x0, y0)
% 4.59/0.94 = { by axiom 6 (conj) R->L }
% 4.59/0.94 fresh37(elem(m_Down(y0), queue(host(x))), true2, z, w0, x0, y0)
% 4.59/0.94 = { by lemma 18 }
% 4.59/0.94 fresh37(elem(m_Down(y0), queue(host(w0))), true2, z, w0, x0, y0)
% 4.59/0.94 = { by axiom 1 (conj_2) }
% 4.59/0.94 fresh37(elem(m_Down(y0), queue(host(z))), true2, z, w0, x0, y0)
% 4.59/0.94 = { by axiom 17 (conj_13) R->L }
% 4.59/0.94 fresh35(setIn(x0, alive), true2, z, w0, x0, y0)
% 4.59/0.94 = { by axiom 5 (conj_9) }
% 4.59/0.94 fresh35(true2, true2, z, w0, x0, y0)
% 4.59/0.94 = { by axiom 15 (conj_13) }
% 4.59/0.94 fresh36(setIn(z, alive), true2, z, w0, x0, y0)
% 4.59/0.94 = { by axiom 4 (conj_8) }
% 4.59/0.94 fresh36(true2, true2, z, w0, x0, y0)
% 4.59/0.94 = { by axiom 16 (conj_13) }
% 4.59/0.94 fresh39(elem(m_Down(w0), queue(host(x0))), true2, z, w0, x0, y0)
% 4.59/0.94 = { by axiom 11 (conj_5) }
% 4.59/0.94 fresh39(true2, true2, z, w0, x0, y0)
% 4.59/0.94 = { by axiom 12 (conj_13) }
% 4.59/0.94 fresh40(host(w0), host(z), z, x0)
% 4.59/0.94 = { by axiom 1 (conj_2) R->L }
% 4.59/0.94 fresh40(host(w0), host(w0), z, x0)
% 4.59/0.94 = { by axiom 8 (conj_13) }
% 4.59/0.94 host(z)
% 4.59/0.94 = { by axiom 1 (conj_2) R->L }
% 4.59/0.94 host(w0)
% 4.59/0.94
% 4.59/0.94 Goal 1 (conj_17): host(x0) = host(z).
% 4.59/0.94 Proof:
% 4.59/0.94 host(x0)
% 4.59/0.94 = { by axiom 2 (conj_3) R->L }
% 4.59/0.94 host(y0)
% 4.59/0.94 = { by lemma 19 }
% 4.59/0.94 host(w0)
% 4.59/0.94 = { by axiom 1 (conj_2) }
% 4.59/0.94 host(z)
% 4.59/0.94
% 4.59/0.94 Goal 2 (conj_15): host(x) = host(x0).
% 4.59/0.94 Proof:
% 4.59/0.94 host(x)
% 4.59/0.94 = { by lemma 18 }
% 4.59/0.94 host(w0)
% 4.59/0.94 = { by lemma 19 R->L }
% 4.59/0.94 host(y0)
% 4.59/0.94 = { by axiom 2 (conj_3) }
% 4.59/0.94 host(x0)
% 4.59/0.94 % SZS output end Proof
% 4.59/0.94
% 4.59/0.94 RESULT: Theorem (the conjecture is true).
%------------------------------------------------------------------------------