0.04/0.15 % Problem : theBenchmark.p : TPTP v0.0.0. Released v0.0.0. 0.04/0.15 % Command : twee %s --tstp --casc --quiet --explain-encoding --conditional-encoding if --smaller --drop-non-horn 0.14/0.37 % Computer : n022.cluster.edu 0.14/0.37 % Model : x86_64 x86_64 0.14/0.37 % CPU : Intel(R) Xeon(R) CPU E5-2620 v4 @ 2.10GHz 0.14/0.37 % Memory : 8042.1875MB 0.14/0.37 % OS : Linux 3.10.0-693.el7.x86_64 0.14/0.37 % CPULimit : 180 0.14/0.37 % DateTime : Thu Aug 29 10:42:58 EDT 2019 0.14/0.37 % CPUTime : 0.21/0.46 % SZS status Unsatisfiable 0.21/0.46 0.21/0.46 % SZS output start Proof 0.21/0.46 Take the following subset of the input axioms: 0.21/0.46 fof(prove_meredith_2_basis_1, negated_conjecture, nand(nand(a, a), nand(b, a))!=a). 0.21/0.46 fof(sh_1, axiom, ![B, A, C]: B=nand(nand(A, nand(nand(B, A), A)), nand(B, nand(C, A)))). 0.21/0.46 0.21/0.46 Now clausify the problem and encode Horn clauses using encoding 3 of 0.21/0.46 http://www.cse.chalmers.se/~nicsma/papers/horn.pdf. 0.21/0.46 We repeatedly replace C & s=t => u=v by the two clauses: 0.21/0.46 fresh(y, y, x1...xn) = u 0.21/0.46 C => fresh(s, t, x1...xn) = v 0.21/0.46 where fresh is a fresh function symbol and x1..xn are the free 0.21/0.46 variables of u and v. 0.21/0.46 A predicate p(X) is encoded as p(X)=true (this is sound, because the 0.21/0.46 input problem has no model of domain size 1). 0.21/0.46 0.21/0.46 The encoding turns the above axioms into the following unit equations and goals: 0.21/0.46 0.21/0.47 Axiom 1 (sh_1): X = nand(nand(Y, nand(nand(X, Y), Y)), nand(X, nand(Z, Y))). 0.21/0.47 0.21/0.47 Lemma 2: nand(nand(nand(Y, nand(Z, W)), nand(nand(X, nand(Y, nand(Z, W))), nand(Y, nand(Z, W)))), nand(X, Y)) = X. 0.21/0.47 Proof: 0.21/0.47 nand(nand(nand(Y, nand(Z, W)), nand(nand(X, nand(Y, nand(Z, W))), nand(Y, nand(Z, W)))), nand(X, Y)) 0.21/0.47 = { by axiom 1 (sh_1) } 0.21/0.47 nand(nand(nand(Y, nand(Z, W)), nand(nand(X, nand(Y, nand(Z, W))), nand(Y, nand(Z, W)))), nand(X, nand(nand(W, nand(nand(Y, W), W)), nand(Y, nand(Z, W))))) 0.21/0.47 = { by axiom 1 (sh_1) } 0.21/0.47 X 0.21/0.47 0.21/0.47 Lemma 3: nand(nand(Y, nand(nand(X, Y), Y)), nand(X, nand(Z, nand(nand(Y, Z), Z)))) = X. 0.21/0.47 Proof: 0.21/0.47 nand(nand(Y, nand(nand(X, Y), Y)), nand(X, nand(Z, nand(nand(Y, Z), Z)))) 0.21/0.47 = { by axiom 1 (sh_1) } 0.21/0.47 nand(nand(nand(nand(Z, nand(nand(Y, Z), Z)), nand(Y, nand(?, Z))), nand(nand(X, Y), Y)), nand(X, nand(Z, nand(nand(Y, Z), Z)))) 0.21/0.47 = { by axiom 1 (sh_1) } 0.21/0.47 nand(nand(nand(nand(Z, nand(nand(Y, Z), Z)), nand(Y, nand(?, Z))), nand(nand(X, nand(nand(Z, nand(nand(Y, Z), Z)), nand(Y, nand(?, Z)))), Y)), nand(X, nand(Z, nand(nand(Y, Z), Z)))) 0.21/0.47 = { by axiom 1 (sh_1) } 0.21/0.47 nand(nand(nand(nand(Z, nand(nand(Y, Z), Z)), nand(Y, nand(?, Z))), nand(nand(X, nand(nand(Z, nand(nand(Y, Z), Z)), nand(Y, nand(?, Z)))), nand(nand(Z, nand(nand(Y, Z), Z)), nand(Y, nand(?, Z))))), nand(X, nand(Z, nand(nand(Y, Z), Z)))) 0.21/0.47 = { by lemma 2 } 0.21/0.47 X 0.21/0.47 0.21/0.47 Lemma 4: nand(nand(Y, nand(nand(nand(X, nand(nand(X, X), X)), Y), Y)), X) = nand(X, nand(nand(X, X), X)). 0.21/0.47 Proof: 0.21/0.47 nand(nand(Y, nand(nand(nand(X, nand(nand(X, X), X)), Y), Y)), X) 0.21/0.47 = { by axiom 1 (sh_1) } 0.21/0.47 nand(nand(Y, nand(nand(nand(X, nand(nand(X, X), X)), Y), Y)), nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(Y, X), X)))) 0.21/0.47 = { by lemma 3 } 0.21/0.47 nand(X, nand(nand(X, X), X)) 0.21/0.47 0.21/0.47 Lemma 5: nand(X, nand(nand(X, X), X)) = nand(X, X). 0.21/0.47 Proof: 0.21/0.47 nand(X, nand(nand(X, X), X)) 0.21/0.47 = { by lemma 4 } 0.21/0.47 nand(nand(nand(X, nand(nand(X, X), X)), nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(X, nand(nand(X, X), X)))), X) 0.21/0.47 = { by axiom 1 (sh_1) } 0.21/0.47 nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(X, nand(nand(X, X), X)))), X) 0.21/0.47 = { by lemma 3 } 0.21/0.47 nand(X, X) 0.21/0.47 0.21/0.47 Lemma 6: nand(nand(X, X), nand(X, nand(Y, X))) = X. 0.21/0.47 Proof: 0.21/0.47 nand(nand(X, X), nand(X, nand(Y, X))) 0.21/0.47 = { by lemma 5 } 0.21/0.47 nand(nand(X, nand(nand(X, X), X)), nand(X, nand(Y, X))) 0.21/0.47 = { by axiom 1 (sh_1) } 0.21/0.47 X 0.21/0.47 0.21/0.47 Lemma 7: nand(nand(Y, nand(nand(X, Y), Y)), nand(X, X)) = X. 0.21/0.47 Proof: 0.21/0.47 nand(nand(Y, nand(nand(X, Y), Y)), nand(X, X)) 0.21/0.47 = { by axiom 1 (sh_1) } 0.21/0.47 nand(nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)), nand(X, X)) 0.21/0.47 = { by lemma 5 } 0.21/0.47 nand(nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(X, nand(nand(X, X), X)))), Y), Y)), nand(X, X)) 0.21/0.47 = { by lemma 5 } 0.21/0.47 nand(nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(X, nand(nand(X, X), X)))), Y), Y)), nand(X, nand(nand(X, X), X))) 0.21/0.47 = { by lemma 4 } 0.21/0.47 nand(nand(X, nand(nand(X, X), X)), nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(X, nand(nand(X, X), X)))) 0.21/0.47 = { by lemma 5 } 0.21/0.47 nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))) 0.21/0.47 = { by axiom 1 (sh_1) } 0.21/0.47 X 0.21/0.47 0.21/0.47 Lemma 8: nand(Y, nand(nand(X, nand(nand(Y, X), X)), Y)) = nand(X, nand(nand(Y, X), X)). 0.21/0.47 Proof: 0.21/0.47 nand(Y, nand(nand(X, nand(nand(Y, X), X)), Y)) 0.21/0.47 = { by lemma 6 } 0.21/0.47 nand(nand(nand(Y, Y), nand(Y, nand(Y, Y))), nand(nand(X, nand(nand(Y, X), X)), Y)) 0.21/0.47 = { by axiom 1 (sh_1) } 0.21/0.47 nand(nand(nand(Y, nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?)))), nand(Y, nand(Y, Y))), nand(nand(X, nand(nand(Y, X), X)), Y)) 0.21/0.47 = { by lemma 7 } 0.21/0.47 nand(nand(nand(Y, nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?)))), nand(nand(nand(X, nand(nand(Y, X), X)), nand(Y, Y)), nand(Y, Y))), nand(nand(X, nand(nand(Y, X), X)), Y)) 0.21/0.47 = { by axiom 1 (sh_1) } 0.21/0.47 nand(nand(nand(Y, nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?)))), nand(nand(nand(X, nand(nand(Y, X), X)), nand(Y, nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))))), nand(Y, Y))), nand(nand(X, nand(nand(Y, X), X)), Y)) 0.21/0.47 = { by axiom 1 (sh_1) } 0.21/0.47 nand(nand(nand(Y, nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?)))), nand(nand(nand(X, nand(nand(Y, X), X)), nand(Y, nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))))), nand(Y, nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?)))))), nand(nand(X, nand(nand(Y, X), X)), Y)) 0.21/0.47 = { by lemma 2 } 0.21/0.48 nand(X, nand(nand(Y, X), X)) 0.21/0.48 0.21/0.48 Lemma 9: nand(X, nand(nand(X, X), Y)) = nand(X, X). 0.21/0.48 Proof: 0.21/0.48 nand(X, nand(nand(X, X), Y)) 0.21/0.48 = { by axiom 1 (sh_1) } 0.21/0.48 nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(nand(X, X), Y)) 0.21/0.48 = { by lemma 6 } 0.21/0.48 nand(nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X)))), nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X)))))), nand(nand(X, X), Y)) 0.21/0.48 = { by lemma 7 } 0.21/0.48 nand(nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X)))), nand(nand(nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)), nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))))), nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X)))))), nand(nand(X, X), Y)) 0.21/0.48 = { by lemma 8 } 0.21/0.48 nand(nand(nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)), nand(nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X)))), nand(nand(nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)), nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))))), nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X)))))), nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)))), nand(nand(X, X), Y)) 0.21/0.48 = { by lemma 7 } 0.21/0.48 nand(nand(nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)), nand(nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X)))), nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X)))))), nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)))), nand(nand(X, X), Y)) 0.21/0.48 = { by lemma 6 } 0.21/0.49 nand(nand(nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)), nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)))), nand(nand(X, X), Y)) 0.21/0.49 = { by lemma 5 } 0.21/0.49 nand(nand(nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)), nand(nand(nand(X, nand(nand(X, X), X)), nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(X, nand(nand(X, X), X)))), nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)))), nand(nand(X, X), Y)) 0.21/0.49 = { by lemma 6 } 0.21/0.49 nand(nand(nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)), nand(nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(X, nand(nand(X, X), X)))), nand(nand(X, nand(nand(X, X), X)), nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(X, nand(nand(X, X), X))))), nand(nand(nand(X, nand(nand(X, X), X)), nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(X, nand(nand(X, X), X)))), nand(nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)), nand(nand(X, nand(nand(X, X), X)), nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(X, nand(nand(X, X), X))))))), nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)))), nand(nand(X, X), Y)) 0.21/0.49 = { by axiom 1 (sh_1) } 0.21/0.49 nand(nand(nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)), nand(nand(nand(X, nand(nand(X, X), X)), nand(nand(nand(X, nand(nand(X, X), X)), nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(X, nand(nand(X, X), X)))), nand(nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)), nand(nand(X, nand(nand(X, X), X)), nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(X, nand(nand(X, X), X))))))), nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)))), nand(nand(X, X), Y)) 0.21/0.49 = { by lemma 5 } 0.21/0.49 nand(nand(nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)), nand(nand(nand(X, nand(nand(X, X), X)), nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)), nand(nand(X, nand(nand(X, X), X)), nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(X, nand(nand(X, X), X))))))), nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)))), nand(nand(X, X), Y)) 0.21/0.49 = { by lemma 5 } 0.21/0.49 nand(nand(nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)), nand(nand(nand(X, nand(nand(X, X), X)), nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)), nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X)))))), nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)))), nand(nand(X, X), Y)) 0.21/0.49 = { by lemma 8 } 0.21/0.49 nand(nand(nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)), nand(nand(nand(X, nand(nand(X, X), X)), nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y))), nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)))), nand(nand(X, X), Y)) 0.21/0.49 = { by lemma 5 } 0.21/0.49 nand(nand(nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)), nand(nand(nand(X, nand(nand(X, X), X)), nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y))), nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)))), nand(nand(X, nand(nand(X, X), X)), Y)) 0.21/0.49 = { by lemma 2 } 0.21/0.49 nand(X, nand(nand(X, X), X)) 0.21/0.49 = { by lemma 5 } 0.21/0.49 nand(X, X) 0.21/0.49 0.21/0.49 Goal 1 (prove_meredith_2_basis_1): nand(nand(a, a), nand(b, a)) = a. 0.21/0.49 Proof: 0.21/0.49 nand(nand(a, a), nand(b, a)) 0.21/0.49 = { by lemma 9 } 0.21/0.49 nand(nand(a, nand(nand(a, a), a)), nand(b, a)) 0.21/0.49 = { by lemma 7 } 0.21/0.49 nand(nand(a, nand(nand(a, a), a)), nand(nand(nand(b, a), nand(nand(nand(b, a), nand(b, a)), nand(b, a))), nand(nand(b, a), nand(b, a)))) 0.21/0.49 = { by lemma 8 } 0.21/0.49 nand(nand(a, nand(nand(a, a), a)), nand(nand(nand(b, a), nand(nand(nand(b, a), nand(nand(nand(b, a), nand(b, a)), nand(b, a))), nand(b, a))), nand(nand(b, a), nand(b, a)))) 0.21/0.49 = { by lemma 4 } 0.21/0.49 nand(nand(a, nand(nand(a, a), a)), nand(nand(nand(b, a), nand(nand(nand(a, nand(nand(nand(nand(b, a), nand(nand(nand(b, a), nand(b, a)), nand(b, a))), a), a)), nand(b, a)), nand(b, a))), nand(nand(b, a), nand(b, a)))) 0.21/0.49 = { by lemma 9 } 0.21/0.49 nand(nand(a, nand(nand(a, a), a)), nand(nand(nand(b, a), nand(nand(nand(a, nand(nand(nand(nand(b, a), nand(nand(nand(b, a), nand(b, a)), nand(b, a))), a), a)), nand(b, a)), nand(b, a))), nand(nand(b, a), nand(nand(nand(b, a), nand(b, a)), nand(b, a))))) 0.21/0.49 = { by axiom 1 (sh_1) } 0.21/0.49 nand(nand(a, nand(nand(a, a), a)), nand(nand(nand(b, a), nand(nand(nand(a, nand(nand(nand(nand(b, a), nand(nand(nand(b, a), nand(b, a)), nand(b, a))), a), a)), nand(b, a)), nand(b, a))), nand(nand(a, nand(nand(nand(nand(b, a), nand(nand(nand(b, a), nand(b, a)), nand(b, a))), a), a)), nand(nand(nand(b, a), nand(nand(nand(b, a), nand(b, a)), nand(b, a))), nand(b, a))))) 0.21/0.49 = { by axiom 1 (sh_1) } 0.21/0.49 nand(nand(a, nand(nand(a, a), a)), nand(a, nand(nand(nand(nand(b, a), nand(nand(nand(b, a), nand(b, a)), nand(b, a))), a), a))) 0.21/0.49 = { by lemma 9 } 0.21/0.49 nand(nand(a, nand(nand(a, a), a)), nand(a, nand(nand(nand(nand(b, a), nand(b, a)), a), a))) 0.21/0.49 = { by axiom 1 (sh_1) } 0.21/0.49 a 0.21/0.49 % SZS output end Proof 0.21/0.49 0.21/0.49 RESULT: Unsatisfiable (the axioms are contradictory). 0.21/0.50 EOF