TSTP Solution File: SWV236+1 by Twee---2.4.2
View Problem
- Process Solution
%------------------------------------------------------------------------------
% File : Twee---2.4.2
% Problem : SWV236+1 : TPTP v8.1.2. Released v3.2.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 : n010.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:03:07 EDT 2023
% Result : Theorem 34.21s 5.00s
% Output : Proof 34.21s
% Verified :
% SZS Type : -
% Comments :
%------------------------------------------------------------------------------
%----WARNING: Could not form TPTP format derivation
%------------------------------------------------------------------------------
%----ORIGINAL SYSTEM OUTPUT
% 0.00/0.13 % Problem : SWV236+1 : TPTP v8.1.2. Released v3.2.0.
% 0.00/0.14 % Command : parallel-twee %s --tstp --conditional-encoding if --smaller --drop-non-horn --give-up-on-saturation --explain-encoding --formal-proof
% 0.13/0.37 % Computer : n010.cluster.edu
% 0.13/0.37 % Model : x86_64 x86_64
% 0.13/0.37 % CPU : Intel(R) Xeon(R) CPU E5-2620 v4 @ 2.10GHz
% 0.13/0.37 % Memory : 8042.1875MB
% 0.13/0.37 % OS : Linux 3.10.0-693.el7.x86_64
% 0.13/0.37 % CPULimit : 300
% 0.13/0.37 % WCLimit : 300
% 0.13/0.37 % DateTime : Tue Aug 29 04:08:34 EDT 2023
% 0.13/0.37 % CPUTime :
% 34.21/5.00 Command-line arguments: --ground-connectedness --complete-subsets
% 34.21/5.00
% 34.21/5.00 % SZS status Theorem
% 34.21/5.02
% 34.21/5.03 % SZS output start Proof
% 34.21/5.03 Take the following subset of the input axioms:
% 34.21/5.03 fof(an_account_number, axiom, p(a)).
% 34.21/5.03 fof(combine_with_XOR, axiom, ![X1, X2]: ((p(X1) & p(X2)) => p(xor(X1, X2)))).
% 34.21/5.03 fof(find_known_exporter, conjecture, ?[X]: (p(crypt(xor(km, exp), X)) & p(X))).
% 34.21/5.03 fof(initial_knowledge_of_intruder_1, axiom, p(kp)).
% 34.21/5.03 fof(initial_knowledge_of_intruder_9, axiom, p(exp)).
% 34.21/5.03 fof(key_part_import___part_1, axiom, ![Xtype, Xk]: ((p(Xk) & p(Xtype)) => p(crypt(xor(km, xor(kp, Xtype)), Xk)))).
% 34.21/5.03 fof(xor_associative, axiom, ![X3, X1_2, X2_2]: xor(X1_2, xor(X2_2, X3))=xor(xor(X1_2, X2_2), X3)).
% 34.21/5.04 fof(xor_commutative, axiom, ![X1_2, X2_2]: xor(X1_2, X2_2)=xor(X2_2, X1_2)).
% 34.21/5.04 fof(xor_rules_1, axiom, ![X1_2]: xor(X1_2, id)=X1_2).
% 34.21/5.04 fof(xor_rules_2, axiom, ![X1_2]: xor(X1_2, X1_2)=id).
% 34.21/5.04
% 34.21/5.04 Now clausify the problem and encode Horn clauses using encoding 3 of
% 34.21/5.04 http://www.cse.chalmers.se/~nicsma/papers/horn.pdf.
% 34.21/5.04 We repeatedly replace C & s=t => u=v by the two clauses:
% 34.21/5.04 fresh(y, y, x1...xn) = u
% 34.21/5.04 C => fresh(s, t, x1...xn) = v
% 34.21/5.04 where fresh is a fresh function symbol and x1..xn are the free
% 34.21/5.04 variables of u and v.
% 34.21/5.04 A predicate p(X) is encoded as p(X)=true (this is sound, because the
% 34.21/5.04 input problem has no model of domain size 1).
% 34.21/5.04
% 34.21/5.04 The encoding turns the above axioms into the following unit equations and goals:
% 34.21/5.04
% 34.21/5.04 Axiom 1 (an_account_number): p(a) = true2.
% 34.21/5.04 Axiom 2 (initial_knowledge_of_intruder_1): p(kp) = true2.
% 34.21/5.04 Axiom 3 (initial_knowledge_of_intruder_9): p(exp) = true2.
% 34.21/5.04 Axiom 4 (xor_rules_2): xor(X, X) = id.
% 34.21/5.04 Axiom 5 (xor_commutative): xor(X, Y) = xor(Y, X).
% 34.21/5.04 Axiom 6 (xor_rules_1): xor(X, id) = X.
% 34.21/5.04 Axiom 7 (key_part_import___part_1): fresh24(X, X, Y, Z) = true2.
% 34.21/5.04 Axiom 8 (combine_with_XOR): fresh13(X, X, Y, Z) = true2.
% 34.21/5.04 Axiom 9 (combine_with_XOR): fresh12(X, X, Y, Z) = p(xor(Y, Z)).
% 34.21/5.04 Axiom 10 (xor_associative): xor(X, xor(Y, Z)) = xor(xor(X, Y), Z).
% 34.21/5.04 Axiom 11 (key_part_import___part_1): fresh23(X, X, Y, Z) = fresh24(p(Y), true2, Y, Z).
% 34.21/5.04 Axiom 12 (combine_with_XOR): fresh12(p(X), true2, Y, X) = fresh13(p(Y), true2, Y, X).
% 34.21/5.04 Axiom 13 (key_export): fresh2(X, X, Y, Z, W) = p(crypt(xor(W, Y), Z)).
% 34.21/5.04 Axiom 14 (key_part_import___part_1): fresh23(p(X), true2, Y, X) = p(crypt(xor(km, xor(kp, X)), Y)).
% 34.21/5.04
% 34.21/5.04 Lemma 15: fresh2(V, V, W, Z, Y) = fresh2(X, X, Y, Z, W).
% 34.21/5.04 Proof:
% 34.21/5.04 fresh2(V, V, W, Z, Y)
% 34.21/5.04 = { by axiom 13 (key_export) }
% 34.21/5.04 p(crypt(xor(Y, W), Z))
% 34.21/5.04 = { by axiom 5 (xor_commutative) R->L }
% 34.21/5.04 p(crypt(xor(W, Y), Z))
% 34.21/5.04 = { by axiom 13 (key_export) R->L }
% 34.21/5.04 fresh2(X, X, Y, Z, W)
% 34.21/5.04
% 34.21/5.04 Goal 1 (find_known_exporter): tuple(p(X), p(crypt(xor(km, exp), X))) = tuple(true2, true2).
% 34.21/5.04 The goal is true when:
% 34.21/5.04 X = a
% 34.21/5.04
% 34.21/5.04 Proof:
% 34.21/5.04 tuple(p(a), p(crypt(xor(km, exp), a)))
% 34.21/5.04 = { by axiom 13 (key_export) R->L }
% 34.21/5.04 tuple(p(a), fresh2(Z, Z, exp, a, km))
% 34.21/5.04 = { by lemma 15 }
% 34.21/5.04 tuple(p(a), fresh2(Y, Y, km, a, exp))
% 34.21/5.04 = { by axiom 6 (xor_rules_1) R->L }
% 34.21/5.04 tuple(p(a), fresh2(Y, Y, km, a, xor(exp, id)))
% 34.21/5.04 = { by axiom 5 (xor_commutative) }
% 34.21/5.04 tuple(p(a), fresh2(Y, Y, km, a, xor(id, exp)))
% 34.21/5.04 = { by axiom 4 (xor_rules_2) R->L }
% 34.21/5.04 tuple(p(a), fresh2(Y, Y, km, a, xor(xor(kp, kp), exp)))
% 34.21/5.04 = { by axiom 10 (xor_associative) R->L }
% 34.21/5.04 tuple(p(a), fresh2(Y, Y, km, a, xor(kp, xor(kp, exp))))
% 34.21/5.04 = { by lemma 15 }
% 34.21/5.04 tuple(p(a), fresh2(X, X, xor(kp, xor(kp, exp)), a, km))
% 34.21/5.05 = { by axiom 13 (key_export) }
% 34.21/5.05 tuple(p(a), p(crypt(xor(km, xor(kp, xor(kp, exp))), a)))
% 34.21/5.05 = { by axiom 14 (key_part_import___part_1) R->L }
% 34.21/5.05 tuple(p(a), fresh23(p(xor(kp, exp)), true2, a, xor(kp, exp)))
% 34.21/5.05 = { by axiom 5 (xor_commutative) R->L }
% 34.21/5.05 tuple(p(a), fresh23(p(xor(exp, kp)), true2, a, xor(kp, exp)))
% 34.21/5.05 = { by axiom 9 (combine_with_XOR) R->L }
% 34.21/5.05 tuple(p(a), fresh23(fresh12(true2, true2, exp, kp), true2, a, xor(kp, exp)))
% 34.21/5.05 = { by axiom 2 (initial_knowledge_of_intruder_1) R->L }
% 34.21/5.05 tuple(p(a), fresh23(fresh12(p(kp), true2, exp, kp), true2, a, xor(kp, exp)))
% 34.21/5.05 = { by axiom 12 (combine_with_XOR) }
% 34.21/5.05 tuple(p(a), fresh23(fresh13(p(exp), true2, exp, kp), true2, a, xor(kp, exp)))
% 34.21/5.05 = { by axiom 3 (initial_knowledge_of_intruder_9) }
% 34.21/5.05 tuple(p(a), fresh23(fresh13(true2, true2, exp, kp), true2, a, xor(kp, exp)))
% 34.21/5.05 = { by axiom 8 (combine_with_XOR) }
% 34.21/5.05 tuple(p(a), fresh23(true2, true2, a, xor(kp, exp)))
% 34.21/5.05 = { by axiom 11 (key_part_import___part_1) }
% 34.21/5.05 tuple(p(a), fresh24(p(a), true2, a, xor(kp, exp)))
% 34.21/5.05 = { by axiom 1 (an_account_number) }
% 34.21/5.05 tuple(p(a), fresh24(true2, true2, a, xor(kp, exp)))
% 34.21/5.05 = { by axiom 7 (key_part_import___part_1) }
% 34.21/5.05 tuple(p(a), true2)
% 34.21/5.05 = { by axiom 1 (an_account_number) }
% 34.21/5.05 tuple(true2, true2)
% 34.21/5.05 % SZS output end Proof
% 34.21/5.05
% 34.21/5.05 RESULT: Theorem (the conjecture is true).
%------------------------------------------------------------------------------