0.07/0.12 % Problem : theBenchmark.p : TPTP v0.0.0. Released v0.0.0. 0.07/0.12 % Command : twee %s --tstp --casc --quiet --explain-encoding --conditional-encoding if --smaller --drop-non-horn 0.12/0.33 % Computer : n023.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 : 180 0.12/0.33 % DateTime : Thu Aug 29 13:37:07 EDT 2019 0.12/0.33 % CPUTime : 14.06/14.28 % SZS status Unsatisfiable 14.06/14.28 14.06/14.28 % SZS output start Proof 14.06/14.28 Take the following subset of the input axioms: 14.06/14.28 fof(prove_meredith_2_basis_2, negated_conjecture, nand(nand(nand(c, b), b), a)!=nand(a, nand(b, nand(a, c)))). 14.06/14.28 fof(sh_1, axiom, ![A, B, C]: nand(nand(A, nand(nand(B, A), A)), nand(B, nand(C, A)))=B). 14.06/14.28 14.06/14.28 Now clausify the problem and encode Horn clauses using encoding 3 of 14.06/14.28 http://www.cse.chalmers.se/~nicsma/papers/horn.pdf. 14.06/14.28 We repeatedly replace C & s=t => u=v by the two clauses: 14.06/14.28 fresh(y, y, x1...xn) = u 14.06/14.28 C => fresh(s, t, x1...xn) = v 14.06/14.28 where fresh is a fresh function symbol and x1..xn are the free 14.06/14.28 variables of u and v. 14.06/14.28 A predicate p(X) is encoded as p(X)=true (this is sound, because the 14.06/14.28 input problem has no model of domain size 1). 14.06/14.28 14.06/14.28 The encoding turns the above axioms into the following unit equations and goals: 14.06/14.28 14.06/14.30 Axiom 1 (sh_1): nand(nand(X, nand(nand(Y, X), X)), nand(Y, nand(Z, X))) = Y. 14.06/14.30 14.06/14.30 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. 14.06/14.30 Proof: 14.06/14.30 nand(nand(nand(Y, nand(Z, W)), nand(nand(X, nand(Y, nand(Z, W))), nand(Y, nand(Z, W)))), nand(X, Y)) 14.06/14.30 = { by axiom 1 (sh_1) } 14.06/14.30 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))))) 14.06/14.30 = { by axiom 1 (sh_1) } 14.06/14.30 X 14.06/14.30 14.06/14.30 Lemma 3: nand(nand(Y, nand(nand(X, Y), Y)), nand(X, nand(Z, nand(nand(Y, Z), Z)))) = X. 14.06/14.30 Proof: 14.06/14.30 nand(nand(Y, nand(nand(X, Y), Y)), nand(X, nand(Z, nand(nand(Y, Z), Z)))) 14.06/14.30 = { by axiom 1 (sh_1) } 14.06/14.30 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)))) 14.06/14.30 = { by axiom 1 (sh_1) } 14.06/14.30 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)))) 14.06/14.30 = { by axiom 1 (sh_1) } 14.06/14.30 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)))) 14.06/14.30 = { by lemma 2 } 14.06/14.30 X 14.06/14.30 14.06/14.30 Lemma 4: nand(nand(Y, nand(nand(nand(X, nand(nand(X, X), X)), Y), Y)), X) = nand(X, nand(nand(X, X), X)). 14.06/14.30 Proof: 14.06/14.30 nand(nand(Y, nand(nand(nand(X, nand(nand(X, X), X)), Y), Y)), X) 14.06/14.30 = { by axiom 1 (sh_1) } 14.06/14.30 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)))) 14.06/14.30 = { by lemma 3 } 14.06/14.30 nand(X, nand(nand(X, X), X)) 14.06/14.30 14.06/14.30 Lemma 5: nand(X, nand(nand(X, X), X)) = nand(X, X). 14.06/14.30 Proof: 14.06/14.30 nand(X, nand(nand(X, X), X)) 14.06/14.30 = { by lemma 4 } 14.06/14.30 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) 14.06/14.30 = { by axiom 1 (sh_1) } 14.06/14.30 nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(X, nand(nand(X, X), X)))), X) 14.06/14.30 = { by lemma 3 } 14.06/14.30 nand(X, X) 14.06/14.30 14.06/14.30 Lemma 6: nand(nand(X, X), nand(X, nand(Y, X))) = X. 14.06/14.30 Proof: 14.06/14.30 nand(nand(X, X), nand(X, nand(Y, X))) 14.06/14.30 = { by lemma 5 } 14.06/14.30 nand(nand(X, nand(nand(X, X), X)), nand(X, nand(Y, X))) 14.06/14.30 = { by axiom 1 (sh_1) } 14.06/14.30 X 14.06/14.30 14.06/14.30 Lemma 7: nand(nand(Y, nand(nand(nand(X, X), Y), Y)), X) = nand(X, X). 14.06/14.30 Proof: 14.06/14.30 nand(nand(Y, nand(nand(nand(X, X), Y), Y)), X) 14.06/14.30 = { by lemma 5 } 14.06/14.30 nand(nand(Y, nand(nand(nand(X, nand(nand(X, X), X)), Y), Y)), X) 14.06/14.30 = { by lemma 4 } 14.06/14.30 nand(X, nand(nand(X, X), X)) 14.06/14.30 = { by lemma 5 } 14.06/14.30 nand(X, X) 14.06/14.30 14.06/14.30 Lemma 8: nand(nand(Y, nand(nand(X, Y), Y)), nand(X, X)) = X. 14.06/14.30 Proof: 14.06/14.30 nand(nand(Y, nand(nand(X, Y), Y)), nand(X, X)) 14.06/14.30 = { by axiom 1 (sh_1) } 14.06/14.30 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)) 14.06/14.30 = { by lemma 5 } 14.06/14.30 nand(nand(Y, nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), Y), Y)), nand(X, nand(nand(X, X), X))) 14.06/14.30 = { by lemma 7 } 14.06/14.30 nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))) 14.06/14.30 = { by axiom 1 (sh_1) } 14.06/14.30 X 14.06/14.30 14.06/14.30 Lemma 9: nand(nand(nand(Y, Z), nand(nand(X, nand(Y, Z)), nand(Y, Z))), nand(X, Y)) = X. 14.06/14.30 Proof: 14.06/14.30 nand(nand(nand(Y, Z), nand(nand(X, nand(Y, Z)), nand(Y, Z))), nand(X, Y)) 14.06/14.30 = { by axiom 1 (sh_1) } 14.06/14.30 nand(nand(nand(Y, nand(nand(?, nand(nand(Z, ?), ?)), nand(Z, nand(?, ?)))), nand(nand(X, nand(Y, Z)), nand(Y, Z))), nand(X, Y)) 14.06/14.30 = { by axiom 1 (sh_1) } 14.06/14.30 nand(nand(nand(Y, nand(nand(?, nand(nand(Z, ?), ?)), nand(Z, nand(?, ?)))), nand(nand(X, nand(Y, nand(nand(?, nand(nand(Z, ?), ?)), nand(Z, nand(?, ?))))), nand(Y, Z))), nand(X, Y)) 14.06/14.30 = { by axiom 1 (sh_1) } 14.06/14.30 nand(nand(nand(Y, nand(nand(?, nand(nand(Z, ?), ?)), nand(Z, nand(?, ?)))), nand(nand(X, nand(Y, nand(nand(?, nand(nand(Z, ?), ?)), nand(Z, nand(?, ?))))), nand(Y, nand(nand(?, nand(nand(Z, ?), ?)), nand(Z, nand(?, ?)))))), nand(X, Y)) 14.06/14.30 = { by lemma 2 } 14.06/14.30 X 14.06/14.30 14.06/14.30 Lemma 10: nand(Y, nand(nand(X, nand(nand(Y, X), X)), Y)) = nand(X, nand(nand(Y, X), X)). 14.06/14.30 Proof: 14.06/14.30 nand(Y, nand(nand(X, nand(nand(Y, X), X)), Y)) 14.06/14.30 = { by lemma 6 } 14.06/14.30 nand(nand(nand(Y, Y), nand(Y, nand(Y, Y))), nand(nand(X, nand(nand(Y, X), X)), Y)) 14.06/14.30 = { by lemma 8 } 14.06/14.30 nand(nand(nand(Y, Y), nand(nand(nand(X, nand(nand(Y, X), X)), nand(Y, Y)), nand(Y, Y))), nand(nand(X, nand(nand(Y, X), X)), Y)) 14.06/14.30 = { by lemma 9 } 14.06/14.30 nand(X, nand(nand(Y, X), X)) 14.06/14.30 14.06/14.30 Lemma 11: nand(nand(X, X), nand(X, Y)) = X. 14.06/14.30 Proof: 14.06/14.30 nand(nand(X, X), nand(X, Y)) 14.06/14.30 = { by lemma 6 } 14.06/14.30 nand(nand(nand(nand(X, X), nand(X, X)), nand(nand(X, X), nand(nand(X, X), nand(X, X)))), nand(X, Y)) 14.06/14.30 = { by lemma 8 } 14.06/14.30 nand(nand(nand(nand(X, X), nand(X, X)), nand(nand(nand(Y, nand(nand(nand(X, X), Y), Y)), nand(nand(X, X), nand(X, X))), nand(nand(X, X), nand(X, X)))), nand(X, Y)) 14.06/14.30 = { by lemma 10 } 14.06/14.30 nand(nand(nand(Y, nand(nand(nand(X, X), Y), Y)), nand(nand(nand(nand(X, X), nand(X, X)), nand(nand(nand(Y, nand(nand(nand(X, X), Y), Y)), nand(nand(X, X), nand(X, X))), nand(nand(X, X), nand(X, X)))), nand(Y, nand(nand(nand(X, X), Y), Y)))), nand(X, Y)) 14.06/14.30 = { by lemma 8 } 14.06/14.31 nand(nand(nand(Y, nand(nand(nand(X, X), Y), Y)), nand(nand(nand(nand(X, X), nand(X, X)), nand(nand(X, X), nand(nand(X, X), nand(X, X)))), nand(Y, nand(nand(nand(X, X), Y), Y)))), nand(X, Y)) 14.06/14.31 = { by lemma 6 } 14.06/14.31 nand(nand(nand(Y, nand(nand(nand(X, X), Y), Y)), nand(nand(X, X), nand(Y, nand(nand(nand(X, X), Y), Y)))), nand(X, Y)) 14.06/14.31 = { by lemma 5 } 14.06/14.31 nand(nand(nand(Y, nand(nand(nand(X, X), Y), Y)), nand(nand(X, nand(nand(X, X), X)), nand(Y, nand(nand(nand(X, X), Y), Y)))), nand(X, Y)) 14.06/14.31 = { by lemma 6 } 14.06/14.31 nand(nand(nand(Y, nand(nand(nand(X, X), Y), Y)), 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(nand(Y, nand(nand(nand(X, X), Y), Y)), nand(X, nand(nand(X, X), X))))), nand(Y, nand(nand(nand(X, X), Y), Y)))), nand(X, Y)) 14.06/14.31 = { by axiom 1 (sh_1) } 14.06/14.31 nand(nand(nand(Y, nand(nand(nand(X, X), Y), Y)), nand(nand(X, nand(nand(X, nand(nand(X, X), X)), nand(nand(Y, nand(nand(nand(X, X), Y), Y)), nand(X, nand(nand(X, X), X))))), nand(Y, nand(nand(nand(X, X), Y), Y)))), nand(X, Y)) 14.06/14.31 = { by lemma 5 } 14.06/14.31 nand(nand(nand(Y, nand(nand(nand(X, X), Y), Y)), nand(nand(X, nand(nand(X, X), nand(nand(Y, nand(nand(nand(X, X), Y), Y)), nand(X, nand(nand(X, X), X))))), nand(Y, nand(nand(nand(X, X), Y), Y)))), nand(X, Y)) 14.06/14.31 = { by lemma 5 } 14.06/14.31 nand(nand(nand(Y, nand(nand(nand(X, X), Y), Y)), nand(nand(X, nand(nand(X, X), nand(nand(Y, nand(nand(nand(X, X), Y), Y)), nand(X, X)))), nand(Y, nand(nand(nand(X, X), Y), Y)))), nand(X, Y)) 14.06/14.31 = { by lemma 10 } 14.06/14.31 nand(nand(nand(Y, nand(nand(nand(X, X), Y), Y)), nand(nand(X, nand(Y, nand(nand(nand(X, X), Y), Y))), nand(Y, nand(nand(nand(X, X), Y), Y)))), nand(X, Y)) 14.06/14.31 = { by lemma 2 } 14.06/14.31 X 14.06/14.31 14.06/14.31 Lemma 12: nand(X, nand(nand(X, X), Y)) = nand(X, X). 14.06/14.31 Proof: 14.06/14.31 nand(X, nand(nand(X, X), Y)) 14.06/14.31 = { by axiom 1 (sh_1) } 14.06/14.31 nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(nand(X, X), Y)) 14.06/14.31 = { by lemma 5 } 14.06/14.31 nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(nand(X, nand(nand(X, X), X)), Y)) 14.06/14.31 = { by lemma 11 } 14.06/14.31 nand(X, nand(nand(X, X), X)) 14.06/14.31 = { by lemma 5 } 14.06/14.31 nand(X, X) 14.06/14.31 14.06/14.31 Lemma 13: nand(nand(nand(Z, X), nand(nand(nand(X, nand(nand(Y, X), X)), nand(Z, X)), nand(Z, X))), Y) = nand(X, nand(nand(Y, X), X)). 14.06/14.31 Proof: 14.06/14.31 nand(nand(nand(Z, X), nand(nand(nand(X, nand(nand(Y, X), X)), nand(Z, X)), nand(Z, X))), Y) 14.06/14.31 = { by axiom 1 (sh_1) } 14.06/14.31 nand(nand(nand(Z, X), nand(nand(nand(X, nand(nand(Y, X), X)), nand(Z, X)), nand(Z, X))), nand(nand(X, nand(nand(Y, X), X)), nand(Y, nand(Z, X)))) 14.06/14.31 = { by axiom 1 (sh_1) } 14.06/14.31 nand(X, nand(nand(Y, X), X)) 14.06/14.31 14.06/14.31 Lemma 14: nand(X, nand(nand(nand(nand(Y, X), nand(Y, X)), X), X)) = nand(Y, X). 14.06/14.31 Proof: 14.06/14.31 nand(X, nand(nand(nand(nand(Y, X), nand(Y, X)), X), X)) 14.06/14.31 = { by lemma 12 } 14.06/14.31 nand(X, nand(nand(nand(nand(Y, X), nand(nand(nand(Y, X), nand(Y, X)), nand(Y, X))), X), X)) 14.06/14.31 = { by lemma 13 } 14.06/14.31 nand(nand(nand(Y, X), nand(nand(nand(X, nand(nand(nand(nand(Y, X), nand(nand(nand(Y, X), nand(Y, X)), nand(Y, X))), X), X)), nand(Y, X)), nand(Y, X))), nand(nand(Y, X), nand(nand(nand(Y, X), nand(Y, X)), nand(Y, X)))) 14.06/14.31 = { by lemma 4 } 14.06/14.31 nand(nand(nand(Y, X), nand(nand(nand(Y, X), nand(nand(nand(Y, X), nand(Y, X)), nand(Y, X))), nand(Y, X))), nand(nand(Y, X), nand(nand(nand(Y, X), nand(Y, X)), nand(Y, X)))) 14.06/14.31 = { by lemma 10 } 14.06/14.31 nand(nand(nand(Y, X), nand(nand(nand(Y, X), nand(Y, X)), nand(Y, X))), nand(nand(Y, X), nand(nand(nand(Y, X), nand(Y, X)), nand(Y, X)))) 14.06/14.31 = { by lemma 12 } 14.06/14.31 nand(nand(nand(Y, X), nand(nand(nand(Y, X), nand(Y, X)), nand(Y, X))), nand(nand(Y, X), nand(Y, X))) 14.06/14.31 = { by lemma 8 } 14.06/14.31 nand(Y, X) 14.06/14.31 14.06/14.31 Lemma 15: nand(nand(X, W), nand(X, nand(X, W))) = X. 14.06/14.31 Proof: 14.06/14.31 nand(nand(X, W), nand(X, nand(X, W))) 14.06/14.31 = { by lemma 11 } 14.06/14.31 nand(nand(X, W), nand(nand(nand(X, X), nand(X, W)), nand(X, W))) 14.06/14.31 = { by lemma 2 } 14.06/14.31 nand(nand(X, W), nand(nand(nand(nand(nand(nand(W, nand(?, ?)), nand(nand(X, nand(W, nand(?, ?))), nand(W, nand(?, ?)))), nand(X, W)), X), nand(X, W)), nand(X, W))) 14.06/14.31 = { by lemma 2 } 14.06/14.31 nand(nand(X, W), nand(nand(nand(nand(nand(nand(W, nand(?, ?)), nand(nand(X, nand(W, nand(?, ?))), nand(W, nand(?, ?)))), nand(X, W)), nand(nand(nand(W, nand(?, ?)), nand(nand(X, nand(W, nand(?, ?))), nand(W, nand(?, ?)))), nand(X, W))), nand(X, W)), nand(X, W))) 14.06/14.31 = { by lemma 14 } 14.06/14.31 nand(nand(nand(W, nand(?, ?)), nand(nand(X, nand(W, nand(?, ?))), nand(W, nand(?, ?)))), nand(X, W)) 14.06/14.31 = { by lemma 2 } 14.06/14.31 X 14.06/14.31 14.06/14.31 Lemma 16: nand(nand(X, X), nand(Y, X)) = X. 14.06/14.31 Proof: 14.06/14.31 nand(nand(X, X), nand(Y, X)) 14.06/14.31 = { by lemma 12 } 14.06/14.31 nand(nand(X, nand(nand(X, X), X)), nand(Y, X)) 14.06/14.31 = { by lemma 14 } 14.06/14.31 nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(nand(nand(Y, X), nand(Y, X)), X), X))) 14.06/14.31 = { by axiom 1 (sh_1) } 14.06/14.31 X 14.06/14.31 14.06/14.31 Lemma 17: nand(nand(Y, X), nand(X, nand(Y, X))) = X. 14.06/14.31 Proof: 14.06/14.31 nand(nand(Y, X), nand(X, nand(Y, X))) 14.06/14.31 = { by lemma 16 } 14.06/14.31 nand(nand(Y, X), nand(nand(nand(X, X), nand(Y, X)), nand(Y, X))) 14.06/14.31 = { by lemma 12 } 14.06/14.31 nand(nand(Y, X), nand(nand(nand(X, nand(nand(X, X), nand(Y, X))), nand(Y, X)), nand(Y, X))) 14.06/14.31 = { by lemma 16 } 14.06/14.31 nand(nand(Y, X), nand(nand(nand(nand(nand(X, X), nand(Y, X)), nand(nand(X, X), nand(Y, X))), nand(Y, X)), nand(Y, X))) 14.06/14.31 = { by lemma 14 } 14.06/14.31 nand(nand(X, X), nand(Y, X)) 14.06/14.31 = { by lemma 16 } 14.06/14.31 X 14.06/14.31 14.06/14.31 Lemma 18: nand(Y, nand(nand(X, Y), Y)) = nand(X, Y). 14.06/14.31 Proof: 14.06/14.31 nand(Y, nand(nand(X, Y), Y)) 14.06/14.31 = { by lemma 15 } 14.06/14.31 nand(nand(nand(Y, nand(X, Y)), nand(Y, nand(Y, nand(X, Y)))), nand(nand(X, Y), Y)) 14.06/14.31 = { by lemma 17 } 14.06/14.31 nand(nand(nand(Y, nand(X, Y)), nand(nand(nand(X, Y), nand(Y, nand(X, Y))), nand(Y, nand(X, Y)))), nand(nand(X, Y), Y)) 14.06/14.31 = { by lemma 2 } 14.06/14.31 nand(X, Y) 14.06/14.31 14.06/14.31 Lemma 19: nand(X, nand(nand(X, Y), X)) = nand(X, Y). 14.06/14.31 Proof: 14.06/14.31 nand(X, nand(nand(X, Y), X)) 14.06/14.31 = { by lemma 15 } 14.06/14.31 nand(nand(nand(X, nand(X, Y)), nand(X, nand(X, nand(X, Y)))), nand(nand(X, Y), X)) 14.06/14.31 = { by lemma 15 } 14.06/14.31 nand(nand(nand(X, nand(X, Y)), nand(nand(nand(X, Y), nand(X, nand(X, Y))), nand(X, nand(X, Y)))), nand(nand(X, Y), X)) 14.06/14.31 = { by lemma 2 } 14.06/14.31 nand(X, Y) 14.06/14.31 14.06/14.31 Lemma 20: nand(nand(X, Y), nand(X, X)) = X. 14.06/14.31 Proof: 14.06/14.31 nand(nand(X, Y), nand(X, X)) 14.06/14.31 = { by lemma 15 } 14.06/14.31 nand(nand(nand(nand(X, Y), X), nand(nand(X, Y), nand(nand(X, Y), X))), nand(X, X)) 14.06/14.31 = { by lemma 19 } 14.06/14.31 nand(nand(nand(nand(X, Y), X), nand(nand(X, nand(nand(X, Y), X)), nand(nand(X, Y), X))), nand(X, X)) 14.06/14.31 = { by lemma 8 } 14.06/14.31 X 14.06/14.31 14.06/14.31 Lemma 21: nand(X, Y) = nand(Y, X). 14.06/14.31 Proof: 14.06/14.31 nand(X, Y) 14.06/14.31 = { by lemma 18 } 14.06/14.31 nand(Y, nand(nand(X, Y), Y)) 14.06/14.31 = { by lemma 13 } 14.06/14.31 nand(nand(nand(Y, Y), nand(nand(nand(Y, nand(nand(X, Y), Y)), nand(Y, Y)), nand(Y, Y))), X) 14.06/14.31 = { by lemma 20 } 14.06/14.31 nand(nand(nand(Y, Y), nand(Y, nand(Y, Y))), X) 14.06/14.31 = { by lemma 17 } 14.06/14.31 nand(Y, X) 14.06/14.31 14.06/14.31 Lemma 22: nand(Y, nand(nand(X, Z), nand(X, Y))) = nand(X, Y). 14.06/14.31 Proof: 14.06/14.31 nand(Y, nand(nand(X, Z), nand(X, Y))) 14.06/14.31 = { by lemma 21 } 14.06/14.31 nand(Y, nand(nand(X, Y), nand(X, Z))) 14.06/14.31 = { by lemma 21 } 14.06/14.31 nand(Y, nand(nand(Y, X), nand(X, Z))) 14.06/14.31 = { by lemma 21 } 14.06/14.31 nand(Y, nand(nand(Y, X), nand(Z, X))) 14.06/14.31 = { by lemma 21 } 14.06/14.31 nand(nand(nand(Y, X), nand(Z, X)), Y) 14.06/14.31 = { by lemma 18 } 14.06/14.31 nand(nand(nand(X, nand(nand(Y, X), X)), nand(Z, X)), Y) 14.06/14.31 = { by lemma 18 } 14.06/14.31 nand(nand(nand(Z, X), nand(nand(nand(X, nand(nand(Y, X), X)), nand(Z, X)), nand(Z, X))), Y) 14.06/14.31 = { by lemma 13 } 14.06/14.31 nand(X, nand(nand(Y, X), X)) 14.06/14.31 = { by lemma 18 } 14.06/14.31 nand(Y, X) 14.06/14.31 = { by lemma 21 } 14.06/14.31 nand(X, Y) 14.06/14.31 14.06/14.31 Lemma 23: nand(X, nand(Z, nand(X, nand(Y, Z)))) = nand(X, nand(Y, Z)). 14.06/14.31 Proof: 14.06/14.31 nand(X, nand(Z, nand(X, nand(Y, Z)))) 14.06/14.31 = { by lemma 21 } 14.06/14.31 nand(X, nand(Z, nand(X, nand(Z, Y)))) 14.06/14.31 = { by lemma 21 } 14.06/14.31 nand(X, nand(nand(X, nand(Z, Y)), Z)) 14.06/14.31 = { by lemma 21 } 14.06/14.31 nand(nand(nand(X, nand(Z, Y)), Z), X) 14.06/14.31 = { by lemma 18 } 14.06/14.31 nand(nand(nand(nand(Z, Y), nand(nand(X, nand(Z, Y)), nand(Z, Y))), Z), X) 14.06/14.31 = { by lemma 9 } 14.06/14.31 nand(nand(nand(nand(Z, Y), nand(nand(X, nand(Z, Y)), nand(Z, Y))), Z), nand(nand(nand(Z, Y), nand(nand(X, nand(Z, Y)), nand(Z, Y))), nand(X, Z))) 14.06/14.31 = { by lemma 21 } 14.06/14.31 nand(nand(nand(nand(Z, Y), nand(nand(X, nand(Z, Y)), nand(Z, Y))), nand(X, Z)), nand(nand(nand(Z, Y), nand(nand(X, nand(Z, Y)), nand(Z, Y))), Z)) 14.06/14.31 = { by lemma 18 } 14.06/14.31 nand(nand(nand(X, Z), nand(nand(nand(nand(Z, Y), nand(nand(X, nand(Z, Y)), nand(Z, Y))), nand(X, Z)), nand(X, Z))), nand(nand(nand(Z, Y), nand(nand(X, nand(Z, Y)), nand(Z, Y))), Z)) 14.06/14.31 = { by lemma 18 } 14.06/14.31 nand(nand(nand(Z, nand(nand(X, Z), Z)), nand(nand(nand(nand(Z, Y), nand(nand(X, nand(Z, Y)), nand(Z, Y))), nand(X, Z)), nand(X, Z))), nand(nand(nand(Z, Y), nand(nand(X, nand(Z, Y)), nand(Z, Y))), Z)) 14.06/14.31 = { by lemma 18 } 14.06/14.31 nand(nand(nand(Z, nand(nand(X, Z), Z)), nand(nand(nand(nand(Z, Y), nand(nand(X, nand(Z, Y)), nand(Z, Y))), nand(Z, nand(nand(X, Z), Z))), nand(X, Z))), nand(nand(nand(Z, Y), nand(nand(X, nand(Z, Y)), nand(Z, Y))), Z)) 14.06/14.31 = { by lemma 18 } 14.06/14.31 nand(nand(nand(Z, nand(nand(X, Z), Z)), nand(nand(nand(nand(Z, Y), nand(nand(X, nand(Z, Y)), nand(Z, Y))), nand(Z, nand(nand(X, Z), Z))), nand(Z, nand(nand(X, Z), Z)))), nand(nand(nand(Z, Y), nand(nand(X, nand(Z, Y)), nand(Z, Y))), Z)) 14.06/14.31 = { by lemma 2 } 14.06/14.31 nand(nand(Z, Y), nand(nand(X, nand(Z, Y)), nand(Z, Y))) 14.06/14.31 = { by lemma 18 } 14.06/14.31 nand(X, nand(Z, Y)) 14.16/14.31 = { by lemma 21 } 14.16/14.31 nand(X, nand(Y, Z)) 14.16/14.31 14.16/14.31 Lemma 24: nand(nand(X, Y), nand(X, nand(Y, Z))) = X. 14.16/14.31 Proof: 14.16/14.31 nand(nand(X, Y), nand(X, nand(Y, Z))) 14.16/14.31 = { by lemma 18 } 14.16/14.31 nand(nand(Y, nand(nand(X, Y), Y)), nand(X, nand(Y, Z))) 14.16/14.31 = { by lemma 21 } 14.16/14.31 nand(nand(Y, nand(nand(X, Y), Y)), nand(X, nand(Z, Y))) 14.16/14.31 = { by axiom 1 (sh_1) } 14.16/14.31 X 14.16/14.31 14.16/14.31 Lemma 25: nand(X, nand(Y, nand(X, Y))) = nand(X, X). 14.16/14.31 Proof: 14.16/14.31 nand(X, nand(Y, nand(X, Y))) 14.16/14.31 = { by lemma 23 } 14.16/14.31 nand(X, nand(nand(X, Y), nand(X, nand(Y, nand(X, Y))))) 14.16/14.31 = { by lemma 24 } 14.16/14.31 nand(X, X) 14.16/14.31 14.16/14.31 Lemma 26: nand(X, nand(Y, nand(Y, X))) = nand(X, X). 14.16/14.31 Proof: 14.16/14.31 nand(X, nand(Y, nand(Y, X))) 14.16/14.31 = { by lemma 21 } 14.16/14.31 nand(X, nand(Y, nand(X, Y))) 14.16/14.31 = { by lemma 25 } 14.16/14.31 nand(X, X) 14.16/14.31 14.16/14.31 Lemma 27: nand(X, nand(X, Y)) = nand(X, nand(Y, Y)). 14.16/14.31 Proof: 14.16/14.31 nand(X, nand(X, Y)) 14.16/14.31 = { by lemma 21 } 14.16/14.31 nand(X, nand(Y, X)) 14.16/14.31 = { by lemma 3 } 14.16/14.31 nand(nand(Y, nand(nand(nand(X, nand(Y, X)), Y), Y)), nand(nand(X, nand(Y, X)), nand(X, nand(nand(Y, X), X)))) 14.16/14.31 = { by lemma 18 } 14.16/14.31 nand(nand(nand(X, nand(Y, X)), Y), nand(nand(X, nand(Y, X)), nand(X, nand(nand(Y, X), X)))) 14.16/14.31 = { by lemma 24 } 14.16/14.31 nand(nand(nand(X, nand(Y, X)), Y), X) 14.16/14.31 = { by lemma 21 } 14.16/14.31 nand(X, nand(nand(X, nand(Y, X)), Y)) 14.16/14.31 = { by lemma 21 } 14.16/14.31 nand(X, nand(Y, nand(X, nand(Y, X)))) 14.16/14.31 = { by lemma 21 } 14.16/14.31 nand(X, nand(Y, nand(X, nand(X, Y)))) 14.16/14.31 = { by lemma 26 } 14.16/14.31 nand(X, nand(Y, Y)) 14.16/14.31 14.16/14.31 Lemma 28: nand(X, nand(Y, Y)) = nand(X, nand(Y, X)). 14.16/14.31 Proof: 14.16/14.31 nand(X, nand(Y, Y)) 14.16/14.31 = { by lemma 27 } 14.16/14.31 nand(X, nand(X, Y)) 14.16/14.31 = { by lemma 21 } 14.16/14.31 nand(X, nand(Y, X)) 14.16/14.31 14.16/14.31 Lemma 29: nand(nand(X, nand(Y, Z)), nand(nand(X, Z), nand(X, Z))) = nand(X, nand(X, nand(Y, Z))). 14.16/14.31 Proof: 14.16/14.31 nand(nand(X, nand(Y, Z)), nand(nand(X, Z), nand(X, Z))) 14.16/14.31 = { by lemma 21 } 14.16/14.31 nand(nand(X, nand(Z, Y)), nand(nand(X, Z), nand(X, Z))) 14.16/14.31 = { by lemma 21 } 14.16/14.31 nand(nand(nand(X, Z), nand(X, Z)), nand(X, nand(Z, Y))) 14.16/14.31 = { by lemma 21 } 14.16/14.31 nand(nand(nand(Z, X), nand(X, Z)), nand(X, nand(Z, Y))) 14.16/14.31 = { by lemma 21 } 14.16/14.31 nand(nand(nand(Z, X), nand(Z, X)), nand(X, nand(Z, Y))) 14.16/14.31 = { by lemma 18 } 14.16/14.31 nand(nand(nand(Z, X), nand(Z, X)), nand(nand(Z, Y), nand(nand(X, nand(Z, Y)), nand(Z, Y)))) 14.16/14.31 = { by lemma 21 } 14.16/14.31 nand(nand(nand(Z, Y), nand(nand(X, nand(Z, Y)), nand(Z, Y))), nand(nand(Z, X), nand(Z, X))) 14.16/14.31 = { by lemma 28 } 14.16/14.31 nand(nand(nand(Z, Y), nand(nand(X, nand(Z, Y)), nand(Z, Y))), nand(nand(Z, X), nand(nand(Z, Y), nand(nand(X, nand(Z, Y)), nand(Z, Y))))) 14.16/14.31 = { by lemma 18 } 14.16/14.31 nand(nand(X, nand(Z, Y)), nand(nand(Z, X), nand(nand(Z, Y), nand(nand(X, nand(Z, Y)), nand(Z, Y))))) 14.16/14.31 = { by lemma 21 } 14.16/14.31 nand(nand(X, nand(Z, Y)), nand(nand(nand(Z, Y), nand(nand(X, nand(Z, Y)), nand(Z, Y))), nand(Z, X))) 14.16/14.31 = { by lemma 21 } 14.16/14.31 nand(nand(X, nand(Z, Y)), nand(nand(nand(Z, Y), nand(nand(X, nand(Z, Y)), nand(Z, Y))), nand(X, Z))) 14.16/14.31 = { by lemma 9 } 14.16/14.31 nand(nand(X, nand(Z, Y)), X) 14.16/14.31 = { by lemma 21 } 14.16/14.31 nand(X, nand(X, nand(Z, Y))) 14.16/14.31 = { by lemma 21 } 14.16/14.32 nand(X, nand(X, nand(Y, Z))) 14.16/14.32 14.16/14.32 Lemma 30: nand(nand(nand(X, Y), nand(X, Y)), nand(nand(Z, Y), nand(Z, Y))) = nand(X, nand(X, nand(Y, Z))). 14.16/14.32 Proof: 14.16/14.32 nand(nand(nand(X, Y), nand(X, Y)), nand(nand(Z, Y), nand(Z, Y))) 14.16/14.32 = { by lemma 22 } 14.16/14.32 nand(nand(nand(X, Y), nand(X, Y)), nand(nand(Y, nand(nand(Z, ?), nand(Z, Y))), nand(Z, Y))) 14.16/14.32 = { by lemma 21 } 14.16/14.32 nand(nand(nand(X, Y), nand(X, Y)), nand(nand(nand(nand(Z, ?), nand(Z, Y)), Y), nand(Z, Y))) 14.16/14.32 = { by lemma 22 } 14.16/14.32 nand(nand(nand(X, Y), nand(X, Y)), nand(nand(nand(nand(Z, ?), nand(Z, Y)), Y), nand(Y, nand(nand(Z, ?), nand(Z, Y))))) 14.16/14.32 = { by lemma 21 } 14.16/14.32 nand(nand(nand(X, Y), nand(X, Y)), nand(nand(nand(nand(Z, ?), nand(Z, Y)), Y), nand(nand(nand(Z, ?), nand(Z, Y)), Y))) 14.16/14.32 = { by lemma 26 } 14.16/14.32 nand(nand(nand(X, Y), nand(X, Y)), nand(nand(nand(nand(Z, ?), nand(Z, Y)), Y), nand(X, nand(X, nand(nand(nand(Z, ?), nand(Z, Y)), Y))))) 14.16/14.32 = { by lemma 29 } 14.16/14.32 nand(nand(nand(X, Y), nand(X, Y)), nand(nand(nand(nand(Z, ?), nand(Z, Y)), Y), nand(nand(X, nand(nand(nand(Z, ?), nand(Z, Y)), Y)), nand(nand(X, Y), nand(X, Y))))) 14.16/14.32 = { by lemma 21 } 14.16/14.32 nand(nand(nand(X, Y), nand(X, Y)), nand(nand(nand(nand(Z, ?), nand(Z, Y)), Y), nand(nand(nand(X, Y), nand(X, Y)), nand(X, nand(nand(nand(Z, ?), nand(Z, Y)), Y))))) 14.16/14.32 = { by lemma 23 } 14.16/14.32 nand(nand(nand(X, Y), nand(X, Y)), nand(X, nand(nand(nand(Z, ?), nand(Z, Y)), Y))) 14.16/14.32 = { by lemma 21 } 14.16/14.32 nand(nand(X, nand(nand(nand(Z, ?), nand(Z, Y)), Y)), nand(nand(X, Y), nand(X, Y))) 14.16/14.32 = { by lemma 29 } 14.16/14.32 nand(X, nand(X, nand(nand(nand(Z, ?), nand(Z, Y)), Y))) 14.16/14.32 = { by lemma 21 } 14.16/14.32 nand(X, nand(X, nand(Y, nand(nand(Z, ?), nand(Z, Y))))) 14.16/14.32 = { by lemma 22 } 14.16/14.32 nand(X, nand(X, nand(Z, Y))) 14.16/14.32 = { by lemma 21 } 14.16/14.32 nand(X, nand(X, nand(Y, Z))) 14.16/14.32 14.16/14.32 Lemma 31: nand(X, nand(nand(Y, Y), X)) = nand(X, Y). 14.16/14.32 Proof: 14.16/14.32 nand(X, nand(nand(Y, Y), X)) 14.16/14.32 = { by lemma 18 } 14.16/14.32 nand(X, nand(nand(Y, nand(nand(Y, Y), Y)), X)) 14.16/14.32 = { by lemma 28 } 14.16/14.32 nand(X, nand(nand(Y, nand(nand(Y, Y), Y)), nand(Y, nand(nand(Y, Y), Y)))) 14.16/14.32 = { by axiom 1 (sh_1) } 14.16/14.32 nand(X, Y) 14.16/14.32 14.16/14.32 Lemma 32: nand(nand(X, X), X) = nand(X, nand(X, X)). 14.16/14.32 Proof: 14.16/14.32 nand(nand(X, X), X) 14.16/14.32 = { by lemma 17 } 14.16/14.32 nand(nand(nand(X, X), nand(nand(X, X), X)), nand(nand(nand(X, X), X), nand(nand(X, X), nand(nand(X, X), X)))) 14.16/14.32 = { by lemma 16 } 14.16/14.32 nand(X, nand(nand(nand(X, X), X), nand(nand(X, X), nand(nand(X, X), X)))) 14.16/14.32 = { by axiom 1 (sh_1) } 14.16/14.32 nand(X, nand(nand(nand(X, X), nand(nand(nand(nand(nand(X, X), X), nand(nand(X, X), nand(nand(X, X), X))), nand(X, X)), nand(X, X))), nand(nand(nand(nand(X, X), X), nand(nand(X, X), nand(nand(X, X), X))), nand(X, nand(X, X))))) 14.16/14.32 = { by lemma 9 } 14.16/14.32 nand(X, nand(nand(nand(X, X), nand(nand(nand(nand(nand(X, X), X), nand(nand(nand(nand(X, X), nand(nand(nand(X, X), nand(X, X)), nand(X, X))), nand(nand(X, X), X)), nand(nand(X, X), X))), nand(X, X)), nand(X, X))), nand(nand(nand(nand(X, X), X), nand(nand(X, X), nand(nand(X, X), X))), nand(X, nand(X, X))))) 14.16/14.32 = { by lemma 4 } 14.16/14.32 nand(X, nand(nand(nand(X, X), nand(nand(nand(X, X), nand(nand(nand(X, X), nand(X, X)), nand(X, X))), nand(X, X))), nand(nand(nand(nand(X, X), X), nand(nand(X, X), nand(nand(X, X), X))), nand(X, nand(X, X))))) 14.16/14.32 = { by lemma 5 } 14.16/14.32 nand(X, nand(nand(nand(X, X), nand(nand(nand(X, X), nand(X, X)), nand(X, X))), nand(nand(nand(nand(X, X), X), nand(nand(X, X), nand(nand(X, X), X))), nand(X, nand(X, X))))) 14.16/14.32 = { by lemma 5 } 14.16/14.32 nand(X, nand(nand(nand(X, X), nand(nand(nand(X, X), nand(X, X)), nand(X, X))), nand(nand(nand(nand(X, X), X), nand(nand(X, nand(nand(X, X), X)), nand(nand(X, X), X))), nand(X, nand(X, X))))) 14.16/14.32 = { by lemma 9 } 14.16/14.32 nand(X, nand(nand(nand(X, X), nand(nand(nand(X, X), nand(X, X)), nand(X, X))), X)) 14.16/14.32 = { by lemma 7 } 14.16/14.32 nand(X, nand(X, X)) 14.16/14.32 14.16/14.32 Lemma 33: nand(nand(X, Y), nand(nand(X, Y), nand(X, Y))) = nand(X, nand(X, X)). 14.16/14.32 Proof: 14.16/14.32 nand(nand(X, Y), nand(nand(X, Y), nand(X, Y))) 14.16/14.32 = { by lemma 32 } 14.16/14.32 nand(nand(nand(X, Y), nand(X, Y)), nand(X, Y)) 14.16/14.32 = { by lemma 9 } 14.16/14.32 nand(nand(nand(X, Y), nand(nand(nand(nand(nand(X, Y), nand(X, Y)), nand(X, Y)), nand(X, Y)), nand(X, Y))), nand(nand(nand(nand(X, Y), nand(X, Y)), nand(X, Y)), X)) 14.16/14.32 = { by lemma 16 } 14.16/14.32 nand(nand(nand(X, Y), nand(nand(nand(nand(nand(X, Y), nand(X, Y)), nand(X, Y)), nand(nand(nand(X, Y), nand(X, Y)), nand(nand(nand(X, Y), nand(X, Y)), nand(X, Y)))), nand(X, Y))), nand(nand(nand(nand(X, Y), nand(X, Y)), nand(X, Y)), X)) 14.16/14.32 = { by lemma 15 } 14.16/14.32 nand(nand(nand(X, Y), nand(nand(nand(X, Y), nand(X, Y)), nand(X, Y))), nand(nand(nand(nand(X, Y), nand(X, Y)), nand(X, Y)), X)) 14.16/14.32 = { by lemma 31 } 14.16/14.32 nand(nand(nand(X, Y), nand(X, Y)), nand(nand(nand(nand(X, Y), nand(X, Y)), nand(X, Y)), X)) 14.16/14.32 = { by lemma 32 } 14.16/14.32 nand(nand(nand(X, Y), nand(X, Y)), nand(nand(nand(X, Y), nand(nand(X, Y), nand(X, Y))), X)) 14.16/14.32 = { by lemma 21 } 14.16/14.32 nand(nand(nand(X, Y), nand(X, Y)), nand(X, nand(nand(X, Y), nand(nand(X, Y), nand(X, Y))))) 14.16/14.32 = { by lemma 18 } 14.16/14.32 nand(nand(nand(X, Y), nand(X, Y)), nand(X, nand(nand(Y, nand(nand(X, Y), Y)), nand(nand(X, Y), nand(X, Y))))) 14.16/14.32 = { by lemma 18 } 14.16/14.32 nand(nand(nand(X, Y), nand(X, Y)), nand(X, nand(nand(Y, nand(nand(X, Y), Y)), nand(nand(Y, nand(nand(X, Y), Y)), nand(X, Y))))) 14.16/14.32 = { by lemma 18 } 14.16/14.32 nand(nand(nand(X, Y), nand(X, Y)), nand(X, nand(nand(Y, nand(nand(X, Y), Y)), nand(nand(Y, nand(nand(X, Y), Y)), nand(Y, nand(nand(X, Y), Y)))))) 14.16/14.32 = { by lemma 32 } 14.16/14.32 nand(nand(nand(X, Y), nand(X, Y)), nand(X, nand(nand(nand(Y, nand(nand(X, Y), Y)), nand(Y, nand(nand(X, Y), Y))), nand(Y, nand(nand(X, Y), Y))))) 14.16/14.32 = { by lemma 8 } 14.16/14.32 nand(nand(nand(X, Y), nand(X, Y)), nand(X, nand(nand(nand(Y, nand(nand(X, Y), Y)), nand(Y, nand(nand(X, Y), Y))), nand(nand(nand(X, X), nand(nand(nand(Y, nand(nand(X, Y), Y)), nand(X, X)), nand(X, X))), nand(nand(Y, nand(nand(X, Y), Y)), nand(Y, nand(nand(X, Y), Y))))))) 14.16/14.32 = { by lemma 8 } 14.16/14.32 nand(nand(nand(X, Y), nand(X, Y)), nand(X, nand(nand(nand(Y, nand(nand(X, Y), Y)), nand(Y, nand(nand(X, Y), Y))), nand(nand(nand(X, X), nand(X, nand(X, X))), nand(nand(Y, nand(nand(X, Y), Y)), nand(Y, nand(nand(X, Y), Y))))))) 14.16/14.32 = { by lemma 6 } 14.16/14.32 nand(nand(nand(X, Y), nand(X, Y)), nand(X, nand(nand(nand(Y, nand(nand(X, Y), Y)), nand(Y, nand(nand(X, Y), Y))), nand(X, nand(nand(Y, nand(nand(X, Y), Y)), nand(Y, nand(nand(X, Y), Y))))))) 14.16/14.32 = { by lemma 25 } 14.16/14.32 nand(nand(nand(X, Y), nand(X, Y)), nand(X, X)) 14.16/14.32 = { by lemma 21 } 14.16/14.32 nand(nand(X, X), nand(nand(X, Y), nand(X, Y))) 14.16/14.32 = { by lemma 28 } 14.16/14.32 nand(nand(X, X), nand(nand(X, Y), nand(X, X))) 14.16/14.32 = { by lemma 20 } 14.16/14.32 nand(nand(X, X), X) 14.16/14.32 = { by lemma 32 } 14.16/14.32 nand(X, nand(X, X)) 14.16/14.32 14.16/14.32 Lemma 34: nand(X, nand(X, X)) = nand(?, nand(?, ?)). 14.16/14.32 Proof: 14.16/14.32 nand(X, nand(X, X)) 14.16/14.32 = { by lemma 33 } 14.16/14.32 nand(nand(X, nand(nand(Y, X), X)), nand(nand(X, nand(nand(Y, X), X)), nand(X, nand(nand(Y, X), X)))) 14.16/14.32 = { by lemma 33 } 14.16/14.32 nand(nand(nand(X, nand(nand(Y, X), X)), nand(Y, nand(Z, X))), nand(nand(nand(X, nand(nand(Y, X), X)), nand(Y, nand(Z, X))), nand(nand(X, nand(nand(Y, X), X)), nand(Y, nand(Z, X))))) 14.16/14.32 = { by axiom 1 (sh_1) } 14.16/14.32 nand(Y, nand(nand(nand(X, nand(nand(Y, X), X)), nand(Y, nand(Z, X))), nand(nand(X, nand(nand(Y, X), X)), nand(Y, nand(Z, X))))) 14.16/14.32 = { by axiom 1 (sh_1) } 14.16/14.32 nand(nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(Z, ?))), nand(nand(nand(X, nand(nand(Y, X), X)), nand(Y, nand(Z, X))), nand(nand(X, nand(nand(Y, X), X)), nand(Y, nand(Z, X))))) 14.16/14.32 = { by axiom 1 (sh_1) } 14.16/14.32 nand(nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(Z, ?))), nand(Y, nand(nand(X, nand(nand(Y, X), X)), nand(Y, nand(Z, X))))) 14.16/14.32 = { by axiom 1 (sh_1) } 14.16/14.32 nand(nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(Z, ?))), nand(nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(Z, ?))), nand(nand(X, nand(nand(Y, X), X)), nand(Y, nand(Z, X))))) 14.16/14.32 = { by axiom 1 (sh_1) } 14.16/14.32 nand(nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(Z, ?))), nand(nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(Z, ?))), Y)) 14.16/14.32 = { by axiom 1 (sh_1) } 14.16/14.32 nand(nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(Z, ?))), nand(nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(Z, ?))), nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(Z, ?))))) 14.16/14.32 = { by lemma 33 } 14.16/14.32 nand(nand(?, nand(nand(Y, ?), ?)), nand(nand(?, nand(nand(Y, ?), ?)), nand(?, nand(nand(Y, ?), ?)))) 14.16/14.32 = { by lemma 33 } 14.16/14.32 nand(?, nand(?, ?)) 14.16/14.32 14.16/14.32 Lemma 35: nand(nand(Y, nand(X, Y)), Y) = nand(X, Y). 14.16/14.32 Proof: 14.16/14.32 nand(nand(Y, nand(X, Y)), Y) 14.16/14.32 = { by lemma 17 } 14.16/14.32 nand(nand(Y, nand(X, Y)), nand(nand(X, Y), nand(Y, nand(X, Y)))) 14.16/14.32 = { by lemma 17 } 14.16/14.32 nand(X, Y) 14.16/14.32 14.16/14.32 Lemma 36: nand(nand(X, X), nand(X, X)) = X. 14.16/14.32 Proof: 14.16/14.32 nand(nand(X, X), nand(X, X)) 14.16/14.32 = { by lemma 5 } 14.16/14.32 nand(nand(X, nand(nand(X, X), X)), nand(X, X)) 14.16/14.32 = { by lemma 5 } 14.16/14.32 nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))) 14.16/14.32 = { by axiom 1 (sh_1) } 14.16/14.33 X 14.16/14.33 14.16/14.33 Lemma 37: nand(nand(?, nand(?, ?)), nand(X, nand(?, nand(?, ?)))) = X. 14.16/14.33 Proof: 14.16/14.33 nand(nand(?, nand(?, ?)), nand(X, nand(?, nand(?, ?)))) 14.16/14.33 = { by lemma 21 } 14.16/14.33 nand(nand(X, nand(?, nand(?, ?))), nand(?, nand(?, ?))) 14.16/14.33 = { by lemma 21 } 14.16/14.33 nand(nand(nand(?, nand(?, ?)), X), nand(?, nand(?, ?))) 14.16/14.33 = { by lemma 35 } 14.16/14.33 nand(nand(nand(X, nand(nand(?, nand(?, ?)), X)), X), nand(?, nand(?, ?))) 14.16/14.33 = { by axiom 1 (sh_1) } 14.16/14.33 nand(nand(nand(nand(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X))), nand(nand(?, nand(?, ?)), X)), X), nand(?, nand(?, ?))) 14.16/14.33 = { by lemma 34 } 14.16/14.33 nand(nand(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(nand(X, nand(nand(X, X), X)), nand(X, nand(nand(X, X), X)))), X)), X), nand(?, nand(?, ?))) 14.16/14.33 = { by axiom 1 (sh_1) } 14.16/14.33 nand(nand(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(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))))), X), nand(?, nand(?, ?))) 14.16/14.33 = { by lemma 4 } 14.16/14.33 nand(nand(X, nand(nand(X, X), X)), nand(?, nand(?, ?))) 14.16/14.33 = { by lemma 31 } 14.16/14.33 nand(nand(X, X), nand(?, nand(?, ?))) 14.16/14.33 = { by lemma 34 } 14.16/14.33 nand(nand(X, X), nand(X, nand(X, X))) 14.16/14.33 = { by lemma 36 } 14.16/14.33 nand(nand(X, X), nand(nand(nand(X, X), nand(X, X)), nand(X, X))) 14.16/14.33 = { by lemma 5 } 14.16/14.33 nand(nand(X, X), nand(X, X)) 14.16/14.33 = { by lemma 36 } 14.16/14.33 X 14.16/14.33 14.16/14.33 Lemma 38: nand(nand(X, nand(?, nand(?, ?))), nand(X, Y)) = X. 14.16/14.33 Proof: 14.16/14.33 nand(nand(X, nand(?, nand(?, ?))), nand(X, Y)) 14.16/14.33 = { by lemma 21 } 14.16/14.33 nand(nand(X, Y), nand(X, nand(?, nand(?, ?)))) 14.16/14.33 = { by axiom 1 (sh_1) } 14.16/14.33 nand(nand(X, nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?)))), nand(X, nand(?, nand(?, ?)))) 14.16/14.33 = { by lemma 21 } 14.16/14.33 nand(nand(X, nand(?, nand(?, ?))), nand(X, nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))))) 14.16/14.33 = { by lemma 37 } 14.16/14.33 nand(nand(nand(?, nand(?, ?)), nand(nand(X, nand(?, nand(?, ?))), nand(?, nand(?, ?)))), nand(X, nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))))) 14.16/14.33 = { by lemma 34 } 14.16/14.33 nand(nand(nand(nand(?, nand(nand(Y, ?), ?)), nand(nand(?, nand(nand(Y, ?), ?)), nand(?, nand(nand(Y, ?), ?)))), nand(nand(X, nand(?, nand(?, ?))), nand(?, nand(?, ?)))), nand(X, nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))))) 14.16/14.33 = { by lemma 33 } 14.16/14.33 nand(nand(nand(nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))), nand(nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))), nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))))), nand(nand(X, nand(?, nand(?, ?))), nand(?, nand(?, ?)))), nand(X, nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))))) 14.16/14.33 = { by lemma 34 } 14.16/14.33 nand(nand(nand(nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))), nand(nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))), nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))))), nand(nand(X, nand(nand(?, nand(nand(Y, ?), ?)), nand(nand(?, nand(nand(Y, ?), ?)), nand(?, nand(nand(Y, ?), ?))))), nand(?, nand(?, ?)))), nand(X, nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))))) 14.16/14.33 = { by lemma 33 } 14.16/14.33 nand(nand(nand(nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))), nand(nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))), nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))))), nand(nand(X, nand(nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))), nand(nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))), nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?)))))), nand(?, nand(?, ?)))), nand(X, nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))))) 14.16/14.33 = { by lemma 34 } 14.16/14.33 nand(nand(nand(nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))), nand(nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))), nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))))), nand(nand(X, nand(nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))), nand(nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))), nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?)))))), nand(nand(?, nand(nand(Y, ?), ?)), nand(nand(?, nand(nand(Y, ?), ?)), nand(?, nand(nand(Y, ?), ?)))))), nand(X, nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))))) 14.16/14.33 = { by lemma 33 } 14.16/14.33 nand(nand(nand(nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))), nand(nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))), nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))))), nand(nand(X, nand(nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))), nand(nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))), nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?)))))), nand(nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))), nand(nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))), nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))))))), nand(X, nand(nand(?, nand(nand(Y, ?), ?)), nand(Y, nand(?, ?))))) 14.16/14.33 = { by lemma 2 } 14.16/14.33 X 14.16/14.33 14.16/14.33 Lemma 39: nand(nand(nand(X, Z), nand(X, Z)), nand(X, nand(Y, Z))) = nand(X, nand(X, nand(Y, Z))). 14.16/14.33 Proof: 14.16/14.33 nand(nand(nand(X, Z), nand(X, Z)), nand(X, nand(Y, Z))) 14.16/14.33 = { by lemma 21 } 14.16/14.33 nand(nand(X, nand(Y, Z)), nand(nand(X, Z), nand(X, Z))) 14.16/14.33 = { by lemma 29 } 14.16/14.34 nand(X, nand(X, nand(Y, Z))) 14.16/14.34 14.16/14.34 Lemma 40: nand(X, nand(Y, nand(Y, nand(Z, X)))) = nand(X, nand(Y, Z)). 14.16/14.34 Proof: 14.16/14.34 nand(X, nand(Y, nand(Y, nand(Z, X)))) 14.16/14.34 = { by lemma 30 } 14.16/14.34 nand(X, nand(nand(nand(Y, Z), nand(Y, Z)), nand(nand(X, Z), nand(X, Z)))) 14.16/14.34 = { by lemma 21 } 14.16/14.34 nand(X, nand(nand(nand(X, Z), nand(X, Z)), nand(nand(Y, Z), nand(Y, Z)))) 14.16/14.34 = { by lemma 30 } 14.16/14.34 nand(X, nand(X, nand(X, nand(Z, Y)))) 14.16/14.34 = { by lemma 21 } 14.16/14.34 nand(X, nand(X, nand(X, nand(Y, Z)))) 14.16/14.34 = { by lemma 21 } 14.16/14.34 nand(nand(X, nand(X, nand(Y, Z))), X) 14.16/14.34 = { by lemma 37 } 14.16/14.34 nand(nand(X, nand(nand(?, nand(?, ?)), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))))), X) 14.16/14.34 = { by lemma 21 } 14.16/14.34 nand(nand(X, nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(?, nand(?, ?)))), X) 14.16/14.34 = { by lemma 38 } 14.16/14.34 nand(nand(X, nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(?, nand(?, ?)))), nand(nand(X, nand(?, nand(?, ?))), nand(X, nand(?, nand(?, ?))))) 14.16/14.34 = { by lemma 29 } 14.16/14.34 nand(X, nand(X, nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(?, nand(?, ?))))) 14.16/14.34 = { by lemma 21 } 14.16/14.34 nand(X, nand(X, nand(nand(?, nand(?, ?)), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))))) 14.16/14.34 = { by lemma 35 } 14.16/14.34 nand(X, nand(X, nand(nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(?, nand(?, ?)), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))))) 14.16/14.34 = { by axiom 1 (sh_1) } 14.16/14.34 nand(X, nand(X, nand(nand(nand(nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))))), nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))))), nand(nand(?, nand(?, ?)), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))))) 14.16/14.34 = { by lemma 34 } 14.16/14.34 nand(X, nand(X, nand(nand(nand(nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))))), nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))))), nand(nand(nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))))), nand(nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))))), nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))))))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))))) 14.16/14.34 = { by axiom 1 (sh_1) } 14.16/14.34 nand(X, nand(X, nand(nand(nand(nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))))), nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))))), nand(nand(nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))))), nand(nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))))), nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))))))), nand(nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))))), nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))))))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))))) 14.16/14.34 = { by lemma 4 } 14.16/14.34 nand(X, nand(X, nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))))))) 14.16/14.34 = { by lemma 31 } 14.16/14.34 nand(X, nand(X, nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))))) 14.16/14.34 = { by lemma 27 } 14.16/14.34 nand(X, nand(X, nand(X, nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))))) 14.16/14.34 = { by lemma 18 } 14.16/14.34 nand(X, nand(X, nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(X, nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))))))) 14.16/14.34 = { by lemma 21 } 14.16/14.34 nand(X, nand(nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(X, nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))))), X)) 14.16/14.34 = { by lemma 10 } 14.16/14.34 nand(nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))), nand(nand(X, nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))), nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?))))) 14.16/14.34 = { by lemma 18 } 14.16/14.34 nand(X, nand(nand(X, nand(Y, Z)), nand(?, nand(?, ?)))) 14.16/14.34 = { by lemma 34 } 14.16/14.34 nand(X, nand(nand(X, nand(Y, Z)), nand(nand(Y, Z), nand(nand(Y, Z), nand(Y, Z))))) 14.16/14.34 = { by lemma 21 } 14.16/14.34 nand(nand(nand(X, nand(Y, Z)), nand(nand(Y, Z), nand(nand(Y, Z), nand(Y, Z)))), X) 14.16/14.34 = { by lemma 18 } 14.16/14.34 nand(nand(nand(nand(Y, Z), nand(nand(Y, Z), nand(Y, Z))), nand(nand(nand(X, nand(Y, Z)), nand(nand(Y, Z), nand(nand(Y, Z), nand(Y, Z)))), nand(nand(Y, Z), nand(nand(Y, Z), nand(Y, Z))))), X) 14.16/14.34 = { by lemma 24 } 14.16/14.34 nand(nand(nand(nand(Y, Z), nand(nand(Y, Z), nand(Y, Z))), nand(nand(nand(X, nand(Y, Z)), nand(nand(Y, Z), nand(nand(Y, Z), nand(Y, Z)))), nand(nand(Y, Z), nand(nand(Y, Z), nand(Y, Z))))), nand(nand(X, nand(Y, Z)), nand(X, nand(nand(Y, Z), nand(nand(Y, Z), nand(Y, Z)))))) 14.16/14.34 = { by axiom 1 (sh_1) } 14.16/14.34 nand(X, nand(Y, Z)) 14.16/14.34 14.16/14.34 Lemma 41: nand(nand(nand(Z, X), nand(Z, X)), Y) = nand(X, nand(X, nand(Y, Z))). 14.16/14.34 Proof: 14.16/14.34 nand(nand(nand(Z, X), nand(Z, X)), Y) 14.16/14.34 = { by lemma 21 } 14.16/14.34 nand(Y, nand(nand(Z, X), nand(Z, X))) 14.16/14.34 = { by lemma 27 } 14.16/14.34 nand(Y, nand(Y, nand(Z, X))) 14.16/14.34 = { by lemma 30 } 14.16/14.34 nand(nand(nand(Y, Z), nand(Y, Z)), nand(nand(X, Z), nand(X, Z))) 14.16/14.34 = { by lemma 21 } 14.16/14.34 nand(nand(nand(X, Z), nand(X, Z)), nand(nand(Y, Z), nand(Y, Z))) 14.16/14.34 = { by lemma 30 } 14.16/14.34 nand(X, nand(X, nand(Z, Y))) 14.16/14.34 = { by lemma 21 } 14.16/14.34 nand(X, nand(X, nand(Y, Z))) 14.16/14.34 14.16/14.34 Goal 1 (prove_meredith_2_basis_2): nand(nand(nand(c, b), b), a) = nand(a, nand(b, nand(a, c))). 14.16/14.34 Proof: 14.16/14.34 nand(nand(nand(c, b), b), a) 14.16/14.34 = { by lemma 21 } 14.16/14.34 nand(a, nand(nand(c, b), b)) 14.16/14.34 = { by lemma 21 } 14.16/14.34 nand(a, nand(b, nand(c, b))) 14.16/14.34 = { by lemma 40 } 14.16/14.34 nand(a, nand(b, nand(b, nand(nand(c, b), a)))) 14.16/14.34 = { by lemma 41 } 14.16/14.34 nand(a, nand(nand(nand(a, b), nand(a, b)), nand(c, b))) 14.16/14.34 = { by lemma 40 } 14.16/14.34 nand(a, nand(nand(nand(a, b), nand(a, b)), nand(nand(nand(a, b), nand(a, b)), nand(nand(c, b), a)))) 14.16/14.34 = { by lemma 21 } 14.16/14.34 nand(a, nand(nand(nand(a, b), nand(a, b)), nand(nand(nand(a, b), nand(a, b)), nand(a, nand(c, b))))) 14.16/14.34 = { by lemma 39 } 14.16/14.34 nand(a, nand(nand(nand(a, b), nand(a, b)), nand(a, nand(a, nand(c, b))))) 14.16/14.34 = { by lemma 41 } 14.16/14.34 nand(a, nand(b, nand(b, nand(nand(a, nand(a, nand(c, b))), a)))) 14.16/14.34 = { by lemma 40 } 14.16/14.34 nand(a, nand(b, nand(a, nand(a, nand(c, b))))) 14.16/14.34 = { by lemma 40 } 14.16/14.34 nand(a, nand(b, nand(a, c))) 14.16/14.34 % SZS output end Proof 14.16/14.34 14.16/14.34 RESULT: Unsatisfiable (the axioms are contradictory). 14.16/14.35 EOF