/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files


--------------------------------------------------------------------------------


Graph construction failed
Graph construction failed
Graph construction failed
MAYBE
proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


Left Termination of the query pattern

tautology(g)

w.r.t. the given Prolog program could not be shown:

(0) Prolog
(1) CutEliminatorProof [SOUND, 0 ms]
(2) Prolog
    (3) IfThenElseTransformerProof [EQUIVALENT, 0 ms]
    (4) Prolog
    (5) CallTransformerProof [EQUIVALENT, 0 ms]
    (6) Prolog
    (7) CutEliminatorProof [SOUND, 0 ms]
    (8) Prolog
    (9) FailTransformerProof [EQUIVALENT, 0 ms]
    (10) Prolog
    (11) UnifyTransformerProof [EQUIVALENT, 0 ms]
    (12) Prolog
    (13) OrTransformerProof [EQUIVALENT, 0 ms]
    (14) Prolog
    (15) UndefinedPredicateHandlerProof [SOUND, 0 ms]
    (16) Prolog
(17) IntegerArithmeticTransformerProof [SOUND, 0 ms]
(18) Prolog
    (19) CutEliminatorProof [SOUND, 0 ms]
    (20) Prolog
    (21) IfThenElseTransformerProof [EQUIVALENT, 0 ms]
    (22) Prolog
    (23) CallTransformerProof [EQUIVALENT, 0 ms]
    (24) Prolog
    (25) CutEliminatorProof [SOUND, 0 ms]
    (26) Prolog
    (27) FailTransformerProof [EQUIVALENT, 0 ms]
    (28) Prolog
    (29) UnifyTransformerProof [EQUIVALENT, 0 ms]
    (30) Prolog
    (31) OrTransformerProof [EQUIVALENT, 0 ms]
    (32) Prolog
    (33) UndefinedPredicateHandlerProof [SOUND, 0 ms]
    (34) Prolog


----------------------------------------

(0)
Obligation:
Clauses:

tautology(Wff) :- ','(write('rewriting...'), ','(nl, ','(rewrite(Wff, NewWff), ','(write('proving...'), ','(nl, tautology(NewWff, [], [])))))).
tautology(Wff, Tlist, Flist) :- ','(;(;(->(truep(Wff, Tlist), true), ->(falsep(Wff, Flist), fail)), ->(=(Wff, if(If, Then, Else)), ;(;(->(truep(If, Tlist), tautology(Then, Tlist, Flist)), ->(falsep(If, Flist), tautology(Else, Tlist, Flist))), ','(tautology(Then, .(If, Tlist), Flist), tautology(Else, Tlist, .(If, Flist)))))), !).
rewrite(Atom, Atom) :- ','(atomic(Atom), !).
rewrite(Old, New) :- ','(functor(Old, F, N), ','(functor(Mid, F, N), ','(rewrite_args(N, Old, Mid), ','(;(->(equal(Mid, Next), rewrite(Next, New)), =(New, Mid)), !)))).
rewrite_args(0, X1, X2) :- !.
rewrite_args(N, Old, Mid) :- ','(arg(N, Old, OldArg), ','(arg(N, Mid, MidArg), ','(rewrite(OldArg, MidArg), ','(is(N1, -(N, 1)), rewrite_args(N1, Old, Mid))))).
truep(t, X3) :- !.
truep(Wff, Tlist) :- member(Wff, Tlist).
falsep(f, X4) :- !.
falsep(Wff, Flist) :- member(Wff, Flist).
member(X, .(X, X5)) :- !.
member(X, .(X6, T)) :- member(X, T).
equal(and(P, Q), if(P, if(Q, t, f), f)).
equal(append(append(X, Y), Z), append(X, append(Y, Z))).
equal(assignment(X, append(A, B)), if(assignedp(X, A), assignment(X, A), assignment(X, B))).
equal(assume_false(Var, Alist), cons(cons(Var, f), Alist)).
equal(assume_true(Var, Alist), cons(cons(Var, t), Alist)).
equal(boolean(X), or(equal(X, t), equal(X, f))).
equal(car(gopher(X)), if(listp(X), car(flatten(X)), zero)).
equal(compile(Form), reverse(codegen(optimize(Form), []))).
equal(count_list(Z, sort_lp(X, Y)), plus(count_list(Z, X), count_list(Z, Y))).
equal(countps_(L, Pred), countps_loop(L, Pred, zero)).
equal(difference(A, B), C) :- difference(A, B, C).
equal(divides(X, Y), zerop(remainder(Y, X))).
equal(dsort(X), sort2(X)).
equal(eqp(X, Y), equal(fix(X), fix(Y))).
equal(equal(A, B), C) :- eq(A, B, C).
equal(even1(X), if(zerop(X), t, odd(decr(X)))).
equal(exec(append(X, Y), Pds, Envrn), exec(Y, exec(X, Pds, Envrn), Envrn)).
equal(exp(A, B), C) :- exp(A, B, C).
equal(fact_(I), fact_loop(I, 1)).
equal(falsify(X), falsify1(normalize(X), [])).
equal(fix(X), if(numberp(X), X, zero)).
equal(flatten(cdr(gopher(X))), if(listp(X), cdr(flatten(X)), cons(zero, []))).
equal(gcd(A, B), C) :- gcd(A, B, C).
equal(get(J, set(I, Val, Mem)), if(eqp(J, I), Val, get(J, Mem))).
equal(greatereqp(X, Y), not(lessp(X, Y))).
equal(greatereqpr(X, Y), not(lessp(X, Y))).
equal(greaterp(X, Y), lessp(Y, X)).
equal(if(if(A, B, C), D, E), if(A, if(B, D, E), if(C, D, E))).
equal(iff(X, Y), and(implies(X, Y), implies(Y, X))).
equal(implies(P, Q), if(P, if(Q, t, f), t)).
equal(last(append(A, B)), if(listp(B), last(B), if(listp(A), cons(car(last(A))), B))).
equal(length(A), B) :- mylength(A, B).
equal(lesseqp(X, Y), not(lessp(Y, X))).
equal(lessp(A, B), C) :- lessp(A, B, C).
equal(listp(gopher(X)), listp(X)).
equal(mc_flatten(X, Y), append(flatten(X), Y)).
equal(meaning(A, B), C) :- meaning(A, B, C).
equal(member(A, B), C) :- mymember(A, B, C).
equal(not(P), if(P, f, t)).
equal(nth(A, B), C) :- nth(A, B, C).
equal(numberp(greatest_factor(X, Y)), not(and(or(zerop(Y), equal(Y, 1)), not(numberp(X))))).
equal(or(P, Q), if(P, t, if(Q, t, f), f)).
equal(plus(A, B), C) :- plus(A, B, C).
equal(power_eval(A, B), C) :- power_eval(A, B, C).
equal(prime(X), and(not(zerop(X)), and(not(equal(X, add1(zero))), prime1(X, decr(X))))).
equal(prime_list(append(X, Y)), and(prime_list(X), prime_list(Y))).
equal(quotient(A, B), C) :- quotient(A, B, C).
equal(remainder(A, B), C) :- remainder(A, B, C).
equal(reverse_(X), reverse_loop(X, [])).
equal(reverse(append(A, B)), append(reverse(B), reverse(A))).
equal(reverse_loop(A, B), C) :- reverse_loop(A, B, C).
equal(samefringe(X, Y), equal(flatten(X), flatten(Y))).
equal(sigma(zero, I), quotient(times(I, add1(I)), 2)).
equal(sort2(delete(X, L)), delete(X, sort2(L))).
equal(tautology_checker(X), tautologyp(normalize(X), [])).
equal(times(A, B), C) :- times(A, B, C).
equal(times_list(append(X, Y)), times(times_list(X), times_list(Y))).
equal(value(normalize(X), A), value(X, A)).
equal(zerop(X), or(equal(X, zero), not(numberp(X)))).
difference(X, X, zero) :- !.
difference(plus(X, Y), X, fix(Y)) :- !.
difference(plus(Y, X), X, fix(Y)) :- !.
difference(plus(X, Y), plus(X, Z), difference(Y, Z)) :- !.
difference(plus(B, plus(A, C)), A, plus(B, C)) :- !.
difference(add1(plus(Y, Z)), Z, add1(Y)) :- !.
difference(add1(add1(X)), 2, fix(X)).
eq(plus(A, B), zero, and(zerop(A), zerop(B))) :- !.
eq(plus(A, B), plus(A, C), equal(fix(B), fix(C))) :- !.
eq(zero, difference(X, Y), not(lessp(Y, X))) :- !.
eq(X, difference(X, Y), and(numberp(X), and(or(equal(X, zero), zerop(Y))))) :- !.
eq(times(X, Y), zero, or(zerop(X), zerop(Y))) :- !.
eq(append(A, B), append(A, C), equal(B, C)) :- !.
eq(flatten(X), cons(Y, []), and(nlistp(X), equal(X, Y))) :- !.
eq(greatest_factor(X, Y), zero, and(or(zerop(Y), equal(Y, 1)), equal(X, zero))) :- !.
eq(greatest_factor(X, X8), 1, equal(X, 1)) :- !.
eq(Z, times(W, Z), and(numberp(Z), or(equal(Z, zero), equal(W, 1)))) :- !.
eq(X, times(X, Y), or(equal(X, zero), and(numberp(X), equal(Y, 1)))) :- !.
eq(times(A, B), 1, and(not(equal(A, zero)), and(not(equal(B, zero)), and(numberp(A), and(numberp(B), and(equal(decr(A), zero), equal(decr(B), zero))))))) :- !.
eq(difference(X, Y), difference(Z, Y), if(lessp(X, Y), not(lessp(Y, Z)), if(lessp(Z, Y), not(lessp(Y, X)), equal(fix(X), fix(Z))))) :- !.
eq(lessp(X, Y), Z, if(lessp(X, Y), equal(t, Z), equal(f, Z))).
exp(I, plus(J, K), times(exp(I, J), exp(I, K))) :- !.
exp(I, times(J, K), exp(exp(I, J), K)).
gcd(X, Y, gcd(Y, X)) :- !.
gcd(times(X, Z), times(Y, Z), times(Z, gcd(X, Y))).
mylength(reverse(X), length(X)).
mylength(cons(X9, cons(X10, cons(X11, cons(X12, cons(X13, cons(X14, X7)))))), plus(6, length(X7))).
lessp(remainder(X15, Y), Y, not(zerop(Y))) :- !.
lessp(quotient(I, J), I, and(not(zerop(I)), or(zerop(J), not(equal(J, 1))))) :- !.
lessp(remainder(X, Y), X, and(not(zerop(Y)), and(not(zerop(X)), not(lessp(X, Y))))) :- !.
lessp(plus(X, Y), plus(X, Z), lessp(Y, Z)) :- !.
lessp(times(X, Z), times(Y, Z), and(not(zerop(Z)), lessp(X, Y))) :- !.
lessp(Y, plus(X, Y), not(zerop(X))) :- !.
lessp(length(delete(X, L)), length(L), member(X, L)).
meaning(plus_tree(append(X, Y)), A, plus(meaning(plus_tree(X), A), meaning(plus_tree(Y), A))) :- !.
meaning(plus_tree(plus_fringe(X)), A, fix(meaning(X, A))) :- !.
meaning(plus_tree(delete(X, Y)), A, if(member(X, Y), difference(meaning(plus_tree(Y), A), meaning(X, A)), meaning(plus_tree(Y), A))).
mymember(X, append(A, B), or(member(X, A), member(X, B))) :- !.
mymember(X, reverse(Y), member(X, Y)) :- !.
mymember(A, intersect(B, C), and(member(A, B), member(A, C))).
nth(zero, X16, zero).
nth([], I, if(zerop(I), [], zero)).
nth(append(A, B), I, append(nth(A, I), nth(B, difference(I, length(A))))).
plus(plus(X, Y), Z, plus(X, plus(Y, Z))) :- !.
plus(remainder(X, Y), times(Y, quotient(X, Y)), fix(X)) :- !.
plus(X, add1(Y), if(numberp(Y), add1(plus(X, Y)), add1(X))).
power_eval(big_plus1(L, I, Base), Base, plus(power_eval(L, Base), I)) :- !.
power_eval(power_rep(I, Base), Base, fix(I)) :- !.
power_eval(big_plus(X, Y, I, Base), Base, plus(I, plus(power_eval(X, Base), power_eval(Y, Base)))) :- !.
power_eval(big_plus(power_rep(I, Base), power_rep(J, Base), zero, Base), Base, plus(I, J)).
quotient(plus(X, plus(X, Y)), 2, plus(X, quotient(Y, 2))).
quotient(times(Y, X), Y, if(zerop(Y), zero, fix(X))).
remainder(X17, 1, zero) :- !.
remainder(X, X, zero) :- !.
remainder(times(X18, Z), Z, zero) :- !.
remainder(times(Y, X19), Y, zero).
reverse_loop(X, Y, append(reverse(X), Y)) :- !.
reverse_loop(X, [], reverse(X)).
times(X, plus(Y, Z), plus(times(X, Y), times(X, Z))) :- !.
times(times(X, Y), Z, times(X, times(Y, Z))) :- !.
times(X, difference(C, W), difference(times(C, X), times(W, X))) :- !.
times(X, add1(Y), if(numberp(Y), plus(X, times(X, Y)), fix(X))).
go(T) :- ','(time(X20), ','(wff(X), ','(tautology(X), time(T)))).
time(T) :- statistics(runtime, .(X21, .(T, []))).
wff(implies(and(implies(X, Y), and(implies(Y, Z), and(implies(Z, U), implies(U, W)))), implies(X, W))) :- ','(=(X, f(plus(plus(a, b), plus(c, zero)))), ','(=(Y, f(times(times(a, b), plus(c, d)))), ','(=(Z, f(reverse(append(append(a, b), [])))), ','(=(U, equal(plus(a, b), difference(x, y))), =(W, lessp(remainder(a, b), member(a, length(b)))))))).


Query: tautology(g)
----------------------------------------

(1) CutEliminatorProof (SOUND)
Eliminated all cuts by simply ignoring them[PROLOG].
----------------------------------------

(2)
Obligation:
Clauses:

tautology(Wff) :- ','(write('rewriting...'), ','(nl, ','(rewrite(Wff, NewWff), ','(write('proving...'), ','(nl, tautology(NewWff, [], [])))))).
tautology(Wff, Tlist, Flist) :- ;(;(->(truep(Wff, Tlist), true), ->(falsep(Wff, Flist), fail)), ->(=(Wff, if(If, Then, Else)), ;(;(->(truep(If, Tlist), tautology(Then, Tlist, Flist)), ->(falsep(If, Flist), tautology(Else, Tlist, Flist))), ','(tautology(Then, .(If, Tlist), Flist), tautology(Else, Tlist, .(If, Flist)))))).
rewrite(Atom, Atom) :- atomic(Atom).
rewrite(Old, New) :- ','(functor(Old, F, N), ','(functor(Mid, F, N), ','(rewrite_args(N, Old, Mid), ;(->(equal(Mid, Next), rewrite(Next, New)), =(New, Mid))))).
rewrite_args(0, X1, X2).
rewrite_args(N, Old, Mid) :- ','(arg(N, Old, OldArg), ','(arg(N, Mid, MidArg), ','(rewrite(OldArg, MidArg), ','(is(N1, -(N, 1)), rewrite_args(N1, Old, Mid))))).
truep(t, X3).
truep(Wff, Tlist) :- member(Wff, Tlist).
falsep(f, X4).
falsep(Wff, Flist) :- member(Wff, Flist).
member(X, .(X, X5)).
member(X, .(X6, T)) :- member(X, T).
equal(and(P, Q), if(P, if(Q, t, f), f)).
equal(append(append(X, Y), Z), append(X, append(Y, Z))).
equal(assignment(X, append(A, B)), if(assignedp(X, A), assignment(X, A), assignment(X, B))).
equal(assume_false(Var, Alist), cons(cons(Var, f), Alist)).
equal(assume_true(Var, Alist), cons(cons(Var, t), Alist)).
equal(boolean(X), or(equal(X, t), equal(X, f))).
equal(car(gopher(X)), if(listp(X), car(flatten(X)), zero)).
equal(compile(Form), reverse(codegen(optimize(Form), []))).
equal(count_list(Z, sort_lp(X, Y)), plus(count_list(Z, X), count_list(Z, Y))).
equal(countps_(L, Pred), countps_loop(L, Pred, zero)).
equal(difference(A, B), C) :- difference(A, B, C).
equal(divides(X, Y), zerop(remainder(Y, X))).
equal(dsort(X), sort2(X)).
equal(eqp(X, Y), equal(fix(X), fix(Y))).
equal(equal(A, B), C) :- eq(A, B, C).
equal(even1(X), if(zerop(X), t, odd(decr(X)))).
equal(exec(append(X, Y), Pds, Envrn), exec(Y, exec(X, Pds, Envrn), Envrn)).
equal(exp(A, B), C) :- exp(A, B, C).
equal(fact_(I), fact_loop(I, 1)).
equal(falsify(X), falsify1(normalize(X), [])).
equal(fix(X), if(numberp(X), X, zero)).
equal(flatten(cdr(gopher(X))), if(listp(X), cdr(flatten(X)), cons(zero, []))).
equal(gcd(A, B), C) :- gcd(A, B, C).
equal(get(J, set(I, Val, Mem)), if(eqp(J, I), Val, get(J, Mem))).
equal(greatereqp(X, Y), not(lessp(X, Y))).
equal(greatereqpr(X, Y), not(lessp(X, Y))).
equal(greaterp(X, Y), lessp(Y, X)).
equal(if(if(A, B, C), D, E), if(A, if(B, D, E), if(C, D, E))).
equal(iff(X, Y), and(implies(X, Y), implies(Y, X))).
equal(implies(P, Q), if(P, if(Q, t, f), t)).
equal(last(append(A, B)), if(listp(B), last(B), if(listp(A), cons(car(last(A))), B))).
equal(length(A), B) :- mylength(A, B).
equal(lesseqp(X, Y), not(lessp(Y, X))).
equal(lessp(A, B), C) :- lessp(A, B, C).
equal(listp(gopher(X)), listp(X)).
equal(mc_flatten(X, Y), append(flatten(X), Y)).
equal(meaning(A, B), C) :- meaning(A, B, C).
equal(member(A, B), C) :- mymember(A, B, C).
equal(not(P), if(P, f, t)).
equal(nth(A, B), C) :- nth(A, B, C).
equal(numberp(greatest_factor(X, Y)), not(and(or(zerop(Y), equal(Y, 1)), not(numberp(X))))).
equal(or(P, Q), if(P, t, if(Q, t, f), f)).
equal(plus(A, B), C) :- plus(A, B, C).
equal(power_eval(A, B), C) :- power_eval(A, B, C).
equal(prime(X), and(not(zerop(X)), and(not(equal(X, add1(zero))), prime1(X, decr(X))))).
equal(prime_list(append(X, Y)), and(prime_list(X), prime_list(Y))).
equal(quotient(A, B), C) :- quotient(A, B, C).
equal(remainder(A, B), C) :- remainder(A, B, C).
equal(reverse_(X), reverse_loop(X, [])).
equal(reverse(append(A, B)), append(reverse(B), reverse(A))).
equal(reverse_loop(A, B), C) :- reverse_loop(A, B, C).
equal(samefringe(X, Y), equal(flatten(X), flatten(Y))).
equal(sigma(zero, I), quotient(times(I, add1(I)), 2)).
equal(sort2(delete(X, L)), delete(X, sort2(L))).
equal(tautology_checker(X), tautologyp(normalize(X), [])).
equal(times(A, B), C) :- times(A, B, C).
equal(times_list(append(X, Y)), times(times_list(X), times_list(Y))).
equal(value(normalize(X), A), value(X, A)).
equal(zerop(X), or(equal(X, zero), not(numberp(X)))).
difference(X, X, zero).
difference(plus(X, Y), X, fix(Y)).
difference(plus(Y, X), X, fix(Y)).
difference(plus(X, Y), plus(X, Z), difference(Y, Z)).
difference(plus(B, plus(A, C)), A, plus(B, C)).
difference(add1(plus(Y, Z)), Z, add1(Y)).
difference(add1(add1(X)), 2, fix(X)).
eq(plus(A, B), zero, and(zerop(A), zerop(B))).
eq(plus(A, B), plus(A, C), equal(fix(B), fix(C))).
eq(zero, difference(X, Y), not(lessp(Y, X))).
eq(X, difference(X, Y), and(numberp(X), and(or(equal(X, zero), zerop(Y))))).
eq(times(X, Y), zero, or(zerop(X), zerop(Y))).
eq(append(A, B), append(A, C), equal(B, C)).
eq(flatten(X), cons(Y, []), and(nlistp(X), equal(X, Y))).
eq(greatest_factor(X, Y), zero, and(or(zerop(Y), equal(Y, 1)), equal(X, zero))).
eq(greatest_factor(X, X8), 1, equal(X, 1)).
eq(Z, times(W, Z), and(numberp(Z), or(equal(Z, zero), equal(W, 1)))).
eq(X, times(X, Y), or(equal(X, zero), and(numberp(X), equal(Y, 1)))).
eq(times(A, B), 1, and(not(equal(A, zero)), and(not(equal(B, zero)), and(numberp(A), and(numberp(B), and(equal(decr(A), zero), equal(decr(B), zero))))))).
eq(difference(X, Y), difference(Z, Y), if(lessp(X, Y), not(lessp(Y, Z)), if(lessp(Z, Y), not(lessp(Y, X)), equal(fix(X), fix(Z))))).
eq(lessp(X, Y), Z, if(lessp(X, Y), equal(t, Z), equal(f, Z))).
exp(I, plus(J, K), times(exp(I, J), exp(I, K))).
exp(I, times(J, K), exp(exp(I, J), K)).
gcd(X, Y, gcd(Y, X)).
gcd(times(X, Z), times(Y, Z), times(Z, gcd(X, Y))).
mylength(reverse(X), length(X)).
mylength(cons(X9, cons(X10, cons(X11, cons(X12, cons(X13, cons(X14, X7)))))), plus(6, length(X7))).
lessp(remainder(X15, Y), Y, not(zerop(Y))).
lessp(quotient(I, J), I, and(not(zerop(I)), or(zerop(J), not(equal(J, 1))))).
lessp(remainder(X, Y), X, and(not(zerop(Y)), and(not(zerop(X)), not(lessp(X, Y))))).
lessp(plus(X, Y), plus(X, Z), lessp(Y, Z)).
lessp(times(X, Z), times(Y, Z), and(not(zerop(Z)), lessp(X, Y))).
lessp(Y, plus(X, Y), not(zerop(X))).
lessp(length(delete(X, L)), length(L), member(X, L)).
meaning(plus_tree(append(X, Y)), A, plus(meaning(plus_tree(X), A), meaning(plus_tree(Y), A))).
meaning(plus_tree(plus_fringe(X)), A, fix(meaning(X, A))).
meaning(plus_tree(delete(X, Y)), A, if(member(X, Y), difference(meaning(plus_tree(Y), A), meaning(X, A)), meaning(plus_tree(Y), A))).
mymember(X, append(A, B), or(member(X, A), member(X, B))).
mymember(X, reverse(Y), member(X, Y)).
mymember(A, intersect(B, C), and(member(A, B), member(A, C))).
nth(zero, X16, zero).
nth([], I, if(zerop(I), [], zero)).
nth(append(A, B), I, append(nth(A, I), nth(B, difference(I, length(A))))).
plus(plus(X, Y), Z, plus(X, plus(Y, Z))).
plus(remainder(X, Y), times(Y, quotient(X, Y)), fix(X)).
plus(X, add1(Y), if(numberp(Y), add1(plus(X, Y)), add1(X))).
power_eval(big_plus1(L, I, Base), Base, plus(power_eval(L, Base), I)).
power_eval(power_rep(I, Base), Base, fix(I)).
power_eval(big_plus(X, Y, I, Base), Base, plus(I, plus(power_eval(X, Base), power_eval(Y, Base)))).
power_eval(big_plus(power_rep(I, Base), power_rep(J, Base), zero, Base), Base, plus(I, J)).
quotient(plus(X, plus(X, Y)), 2, plus(X, quotient(Y, 2))).
quotient(times(Y, X), Y, if(zerop(Y), zero, fix(X))).
remainder(X17, 1, zero).
remainder(X, X, zero).
remainder(times(X18, Z), Z, zero).
remainder(times(Y, X19), Y, zero).
reverse_loop(X, Y, append(reverse(X), Y)).
reverse_loop(X, [], reverse(X)).
times(X, plus(Y, Z), plus(times(X, Y), times(X, Z))).
times(times(X, Y), Z, times(X, times(Y, Z))).
times(X, difference(C, W), difference(times(C, X), times(W, X))).
times(X, add1(Y), if(numberp(Y), plus(X, times(X, Y)), fix(X))).
go(T) :- ','(time(X20), ','(wff(X), ','(tautology(X), time(T)))).
time(T) :- statistics(runtime, .(X21, .(T, []))).
wff(implies(and(implies(X, Y), and(implies(Y, Z), and(implies(Z, U), implies(U, W)))), implies(X, W))) :- ','(=(X, f(plus(plus(a, b), plus(c, zero)))), ','(=(Y, f(times(times(a, b), plus(c, d)))), ','(=(Z, f(reverse(append(append(a, b), [])))), ','(=(U, equal(plus(a, b), difference(x, y))), =(W, lessp(remainder(a, b), member(a, length(b)))))))).


Query: tautology(g)
----------------------------------------

(3) IfThenElseTransformerProof (EQUIVALENT)
Transformed all if-then-else-constructs [PROLOG].
----------------------------------------

(4)
Obligation:
Clauses:

tautology(Wff) :- ','(write('rewriting...'), ','(nl, ','(rewrite(Wff, NewWff), ','(write('proving...'), ','(nl, tautology(NewWff, [], [])))))).
tautology(Wff, Tlist, Flist) :- ;(if1(Wff, Tlist, Flist), if2(Wff, If, Then, Else, Tlist, Flist)).
rewrite(Atom, Atom) :- atomic(Atom).
rewrite(Old, New) :- ','(functor(Old, F, N), ','(functor(Mid, F, N), ','(rewrite_args(N, Old, Mid), if3(Mid, Next, New)))).
rewrite_args(0, X1, X2).
rewrite_args(N, Old, Mid) :- ','(arg(N, Old, OldArg), ','(arg(N, Mid, MidArg), ','(rewrite(OldArg, MidArg), ','(is(N1, -(N, 1)), rewrite_args(N1, Old, Mid))))).
truep(t, X3).
truep(Wff, Tlist) :- member(Wff, Tlist).
falsep(f, X4).
falsep(Wff, Flist) :- member(Wff, Flist).
member(X, .(X, X5)).
member(X, .(X6, T)) :- member(X, T).
equal(and(P, Q), if(P, if(Q, t, f), f)).
equal(append(append(X, Y), Z), append(X, append(Y, Z))).
equal(assignment(X, append(A, B)), if(assignedp(X, A), assignment(X, A), assignment(X, B))).
equal(assume_false(Var, Alist), cons(cons(Var, f), Alist)).
equal(assume_true(Var, Alist), cons(cons(Var, t), Alist)).
equal(boolean(X), or(equal(X, t), equal(X, f))).
equal(car(gopher(X)), if(listp(X), car(flatten(X)), zero)).
equal(compile(Form), reverse(codegen(optimize(Form), []))).
equal(count_list(Z, sort_lp(X, Y)), plus(count_list(Z, X), count_list(Z, Y))).
equal(countps_(L, Pred), countps_loop(L, Pred, zero)).
equal(difference(A, B), C) :- difference(A, B, C).
equal(divides(X, Y), zerop(remainder(Y, X))).
equal(dsort(X), sort2(X)).
equal(eqp(X, Y), equal(fix(X), fix(Y))).
equal(equal(A, B), C) :- eq(A, B, C).
equal(even1(X), if(zerop(X), t, odd(decr(X)))).
equal(exec(append(X, Y), Pds, Envrn), exec(Y, exec(X, Pds, Envrn), Envrn)).
equal(exp(A, B), C) :- exp(A, B, C).
equal(fact_(I), fact_loop(I, 1)).
equal(falsify(X), falsify1(normalize(X), [])).
equal(fix(X), if(numberp(X), X, zero)).
equal(flatten(cdr(gopher(X))), if(listp(X), cdr(flatten(X)), cons(zero, []))).
equal(gcd(A, B), C) :- gcd(A, B, C).
equal(get(J, set(I, Val, Mem)), if(eqp(J, I), Val, get(J, Mem))).
equal(greatereqp(X, Y), not(lessp(X, Y))).
equal(greatereqpr(X, Y), not(lessp(X, Y))).
equal(greaterp(X, Y), lessp(Y, X)).
equal(if(if(A, B, C), D, E), if(A, if(B, D, E), if(C, D, E))).
equal(iff(X, Y), and(implies(X, Y), implies(Y, X))).
equal(implies(P, Q), if(P, if(Q, t, f), t)).
equal(last(append(A, B)), if(listp(B), last(B), if(listp(A), cons(car(last(A))), B))).
equal(length(A), B) :- mylength(A, B).
equal(lesseqp(X, Y), not(lessp(Y, X))).
equal(lessp(A, B), C) :- lessp(A, B, C).
equal(listp(gopher(X)), listp(X)).
equal(mc_flatten(X, Y), append(flatten(X), Y)).
equal(meaning(A, B), C) :- meaning(A, B, C).
equal(member(A, B), C) :- mymember(A, B, C).
equal(not(P), if(P, f, t)).
equal(nth(A, B), C) :- nth(A, B, C).
equal(numberp(greatest_factor(X, Y)), not(and(or(zerop(Y), equal(Y, 1)), not(numberp(X))))).
equal(or(P, Q), if(P, t, if(Q, t, f), f)).
equal(plus(A, B), C) :- plus(A, B, C).
equal(power_eval(A, B), C) :- power_eval(A, B, C).
equal(prime(X), and(not(zerop(X)), and(not(equal(X, add1(zero))), prime1(X, decr(X))))).
equal(prime_list(append(X, Y)), and(prime_list(X), prime_list(Y))).
equal(quotient(A, B), C) :- quotient(A, B, C).
equal(remainder(A, B), C) :- remainder(A, B, C).
equal(reverse_(X), reverse_loop(X, [])).
equal(reverse(append(A, B)), append(reverse(B), reverse(A))).
equal(reverse_loop(A, B), C) :- reverse_loop(A, B, C).
equal(samefringe(X, Y), equal(flatten(X), flatten(Y))).
equal(sigma(zero, I), quotient(times(I, add1(I)), 2)).
equal(sort2(delete(X, L)), delete(X, sort2(L))).
equal(tautology_checker(X), tautologyp(normalize(X), [])).
equal(times(A, B), C) :- times(A, B, C).
equal(times_list(append(X, Y)), times(times_list(X), times_list(Y))).
equal(value(normalize(X), A), value(X, A)).
equal(zerop(X), or(equal(X, zero), not(numberp(X)))).
difference(X, X, zero).
difference(plus(X, Y), X, fix(Y)).
difference(plus(Y, X), X, fix(Y)).
difference(plus(X, Y), plus(X, Z), difference(Y, Z)).
difference(plus(B, plus(A, C)), A, plus(B, C)).
difference(add1(plus(Y, Z)), Z, add1(Y)).
difference(add1(add1(X)), 2, fix(X)).
eq(plus(A, B), zero, and(zerop(A), zerop(B))).
eq(plus(A, B), plus(A, C), equal(fix(B), fix(C))).
eq(zero, difference(X, Y), not(lessp(Y, X))).
eq(X, difference(X, Y), and(numberp(X), and(or(equal(X, zero), zerop(Y))))).
eq(times(X, Y), zero, or(zerop(X), zerop(Y))).
eq(append(A, B), append(A, C), equal(B, C)).
eq(flatten(X), cons(Y, []), and(nlistp(X), equal(X, Y))).
eq(greatest_factor(X, Y), zero, and(or(zerop(Y), equal(Y, 1)), equal(X, zero))).
eq(greatest_factor(X, X8), 1, equal(X, 1)).
eq(Z, times(W, Z), and(numberp(Z), or(equal(Z, zero), equal(W, 1)))).
eq(X, times(X, Y), or(equal(X, zero), and(numberp(X), equal(Y, 1)))).
eq(times(A, B), 1, and(not(equal(A, zero)), and(not(equal(B, zero)), and(numberp(A), and(numberp(B), and(equal(decr(A), zero), equal(decr(B), zero))))))).
eq(difference(X, Y), difference(Z, Y), if(lessp(X, Y), not(lessp(Y, Z)), if(lessp(Z, Y), not(lessp(Y, X)), equal(fix(X), fix(Z))))).
eq(lessp(X, Y), Z, if(lessp(X, Y), equal(t, Z), equal(f, Z))).
exp(I, plus(J, K), times(exp(I, J), exp(I, K))).
exp(I, times(J, K), exp(exp(I, J), K)).
gcd(X, Y, gcd(Y, X)).
gcd(times(X, Z), times(Y, Z), times(Z, gcd(X, Y))).
mylength(reverse(X), length(X)).
mylength(cons(X9, cons(X10, cons(X11, cons(X12, cons(X13, cons(X14, X7)))))), plus(6, length(X7))).
lessp(remainder(X15, Y), Y, not(zerop(Y))).
lessp(quotient(I, J), I, and(not(zerop(I)), or(zerop(J), not(equal(J, 1))))).
lessp(remainder(X, Y), X, and(not(zerop(Y)), and(not(zerop(X)), not(lessp(X, Y))))).
lessp(plus(X, Y), plus(X, Z), lessp(Y, Z)).
lessp(times(X, Z), times(Y, Z), and(not(zerop(Z)), lessp(X, Y))).
lessp(Y, plus(X, Y), not(zerop(X))).
lessp(length(delete(X, L)), length(L), member(X, L)).
meaning(plus_tree(append(X, Y)), A, plus(meaning(plus_tree(X), A), meaning(plus_tree(Y), A))).
meaning(plus_tree(plus_fringe(X)), A, fix(meaning(X, A))).
meaning(plus_tree(delete(X, Y)), A, if(member(X, Y), difference(meaning(plus_tree(Y), A), meaning(X, A)), meaning(plus_tree(Y), A))).
mymember(X, append(A, B), or(member(X, A), member(X, B))).
mymember(X, reverse(Y), member(X, Y)).
mymember(A, intersect(B, C), and(member(A, B), member(A, C))).
nth(zero, X16, zero).
nth([], I, if(zerop(I), [], zero)).
nth(append(A, B), I, append(nth(A, I), nth(B, difference(I, length(A))))).
plus(plus(X, Y), Z, plus(X, plus(Y, Z))).
plus(remainder(X, Y), times(Y, quotient(X, Y)), fix(X)).
plus(X, add1(Y), if(numberp(Y), add1(plus(X, Y)), add1(X))).
power_eval(big_plus1(L, I, Base), Base, plus(power_eval(L, Base), I)).
power_eval(power_rep(I, Base), Base, fix(I)).
power_eval(big_plus(X, Y, I, Base), Base, plus(I, plus(power_eval(X, Base), power_eval(Y, Base)))).
power_eval(big_plus(power_rep(I, Base), power_rep(J, Base), zero, Base), Base, plus(I, J)).
quotient(plus(X, plus(X, Y)), 2, plus(X, quotient(Y, 2))).
quotient(times(Y, X), Y, if(zerop(Y), zero, fix(X))).
remainder(X17, 1, zero).
remainder(X, X, zero).
remainder(times(X18, Z), Z, zero).
remainder(times(Y, X19), Y, zero).
reverse_loop(X, Y, append(reverse(X), Y)).
reverse_loop(X, [], reverse(X)).
times(X, plus(Y, Z), plus(times(X, Y), times(X, Z))).
times(times(X, Y), Z, times(X, times(Y, Z))).
times(X, difference(C, W), difference(times(C, X), times(W, X))).
times(X, add1(Y), if(numberp(Y), plus(X, times(X, Y)), fix(X))).
go(T) :- ','(time(X20), ','(wff(X), ','(tautology(X), time(T)))).
time(T) :- statistics(runtime, .(X21, .(T, []))).
wff(implies(and(implies(X, Y), and(implies(Y, Z), and(implies(Z, U), implies(U, W)))), implies(X, W))) :- ','(=(X, f(plus(plus(a, b), plus(c, zero)))), ','(=(Y, f(times(times(a, b), plus(c, d)))), ','(=(Z, f(reverse(append(append(a, b), [])))), ','(=(U, equal(plus(a, b), difference(x, y))), =(W, lessp(remainder(a, b), member(a, length(b)))))))).
if1(Wff, Tlist, Flist) :- ','(call(truep(Wff, Tlist)), ','(!, true)).
if1(Wff, Tlist, Flist) :- if4(Wff, Flist).
if2(Wff, If, Then, Else, Tlist, Flist) :- ','(call(=(Wff, if(If, Then, Else))), ','(!, ;(if5(If, Tlist, Then, Flist, Else), ','(tautology(Then, .(If, Tlist), Flist), tautology(Else, Tlist, .(If, Flist)))))).
if3(Mid, Next, New) :- ','(call(equal(Mid, Next)), ','(!, rewrite(Next, New))).
if3(Mid, Next, New) :- =(New, Mid).
if4(Wff, Flist) :- ','(call(falsep(Wff, Flist)), ','(!, fail)).
if5(If, Tlist, Then, Flist, Else) :- ','(call(truep(If, Tlist)), ','(!, tautology(Then, Tlist, Flist))).
if5(If, Tlist, Then, Flist, Else) :- if6(If, Flist, Else, Tlist).
if6(If, Flist, Else, Tlist) :- ','(call(falsep(If, Flist)), ','(!, tautology(Else, Tlist, Flist))).


Query: tautology(g)
----------------------------------------

(5) CallTransformerProof (EQUIVALENT)
Transformed all call-constructs [PROLOG].
----------------------------------------

(6)
Obligation:
Clauses:

tautology(Wff) :- ','(write('rewriting...'), ','(nl, ','(rewrite(Wff, NewWff), ','(write('proving...'), ','(nl, tautology(NewWff, [], [])))))).
tautology(Wff, Tlist, Flist) :- ;(if1(Wff, Tlist, Flist), if2(Wff, If, Then, Else, Tlist, Flist)).
rewrite(Atom, Atom) :- atomic(Atom).
rewrite(Old, New) :- ','(functor(Old, F, N), ','(functor(Mid, F, N), ','(rewrite_args(N, Old, Mid), if3(Mid, Next, New)))).
rewrite_args(0, X1, X2).
rewrite_args(N, Old, Mid) :- ','(arg(N, Old, OldArg), ','(arg(N, Mid, MidArg), ','(rewrite(OldArg, MidArg), ','(is(N1, -(N, 1)), rewrite_args(N1, Old, Mid))))).
truep(t, X3).
truep(Wff, Tlist) :- member(Wff, Tlist).
falsep(f, X4).
falsep(Wff, Flist) :- member(Wff, Flist).
member(X, .(X, X5)).
member(X, .(X6, T)) :- member(X, T).
equal(and(P, Q), if(P, if(Q, t, f), f)).
equal(append(append(X, Y), Z), append(X, append(Y, Z))).
equal(assignment(X, append(A, B)), if(assignedp(X, A), assignment(X, A), assignment(X, B))).
equal(assume_false(Var, Alist), cons(cons(Var, f), Alist)).
equal(assume_true(Var, Alist), cons(cons(Var, t), Alist)).
equal(boolean(X), or(equal(X, t), equal(X, f))).
equal(car(gopher(X)), if(listp(X), car(flatten(X)), zero)).
equal(compile(Form), reverse(codegen(optimize(Form), []))).
equal(count_list(Z, sort_lp(X, Y)), plus(count_list(Z, X), count_list(Z, Y))).
equal(countps_(L, Pred), countps_loop(L, Pred, zero)).
equal(difference(A, B), C) :- difference(A, B, C).
equal(divides(X, Y), zerop(remainder(Y, X))).
equal(dsort(X), sort2(X)).
equal(eqp(X, Y), equal(fix(X), fix(Y))).
equal(equal(A, B), C) :- eq(A, B, C).
equal(even1(X), if(zerop(X), t, odd(decr(X)))).
equal(exec(append(X, Y), Pds, Envrn), exec(Y, exec(X, Pds, Envrn), Envrn)).
equal(exp(A, B), C) :- exp(A, B, C).
equal(fact_(I), fact_loop(I, 1)).
equal(falsify(X), falsify1(normalize(X), [])).
equal(fix(X), if(numberp(X), X, zero)).
equal(flatten(cdr(gopher(X))), if(listp(X), cdr(flatten(X)), cons(zero, []))).
equal(gcd(A, B), C) :- gcd(A, B, C).
equal(get(J, set(I, Val, Mem)), if(eqp(J, I), Val, get(J, Mem))).
equal(greatereqp(X, Y), not(lessp(X, Y))).
equal(greatereqpr(X, Y), not(lessp(X, Y))).
equal(greaterp(X, Y), lessp(Y, X)).
equal(if(if(A, B, C), D, E), if(A, if(B, D, E), if(C, D, E))).
equal(iff(X, Y), and(implies(X, Y), implies(Y, X))).
equal(implies(P, Q), if(P, if(Q, t, f), t)).
equal(last(append(A, B)), if(listp(B), last(B), if(listp(A), cons(car(last(A))), B))).
equal(length(A), B) :- mylength(A, B).
equal(lesseqp(X, Y), not(lessp(Y, X))).
equal(lessp(A, B), C) :- lessp(A, B, C).
equal(listp(gopher(X)), listp(X)).
equal(mc_flatten(X, Y), append(flatten(X), Y)).
equal(meaning(A, B), C) :- meaning(A, B, C).
equal(member(A, B), C) :- mymember(A, B, C).
equal(not(P), if(P, f, t)).
equal(nth(A, B), C) :- nth(A, B, C).
equal(numberp(greatest_factor(X, Y)), not(and(or(zerop(Y), equal(Y, 1)), not(numberp(X))))).
equal(or(P, Q), if(P, t, if(Q, t, f), f)).
equal(plus(A, B), C) :- plus(A, B, C).
equal(power_eval(A, B), C) :- power_eval(A, B, C).
equal(prime(X), and(not(zerop(X)), and(not(equal(X, add1(zero))), prime1(X, decr(X))))).
equal(prime_list(append(X, Y)), and(prime_list(X), prime_list(Y))).
equal(quotient(A, B), C) :- quotient(A, B, C).
equal(remainder(A, B), C) :- remainder(A, B, C).
equal(reverse_(X), reverse_loop(X, [])).
equal(reverse(append(A, B)), append(reverse(B), reverse(A))).
equal(reverse_loop(A, B), C) :- reverse_loop(A, B, C).
equal(samefringe(X, Y), equal(flatten(X), flatten(Y))).
equal(sigma(zero, I), quotient(times(I, add1(I)), 2)).
equal(sort2(delete(X, L)), delete(X, sort2(L))).
equal(tautology_checker(X), tautologyp(normalize(X), [])).
equal(times(A, B), C) :- times(A, B, C).
equal(times_list(append(X, Y)), times(times_list(X), times_list(Y))).
equal(value(normalize(X), A), value(X, A)).
equal(zerop(X), or(equal(X, zero), not(numberp(X)))).
difference(X, X, zero).
difference(plus(X, Y), X, fix(Y)).
difference(plus(Y, X), X, fix(Y)).
difference(plus(X, Y), plus(X, Z), difference(Y, Z)).
difference(plus(B, plus(A, C)), A, plus(B, C)).
difference(add1(plus(Y, Z)), Z, add1(Y)).
difference(add1(add1(X)), 2, fix(X)).
eq(plus(A, B), zero, and(zerop(A), zerop(B))).
eq(plus(A, B), plus(A, C), equal(fix(B), fix(C))).
eq(zero, difference(X, Y), not(lessp(Y, X))).
eq(X, difference(X, Y), and(numberp(X), and(or(equal(X, zero), zerop(Y))))).
eq(times(X, Y), zero, or(zerop(X), zerop(Y))).
eq(append(A, B), append(A, C), equal(B, C)).
eq(flatten(X), cons(Y, []), and(nlistp(X), equal(X, Y))).
eq(greatest_factor(X, Y), zero, and(or(zerop(Y), equal(Y, 1)), equal(X, zero))).
eq(greatest_factor(X, X8), 1, equal(X, 1)).
eq(Z, times(W, Z), and(numberp(Z), or(equal(Z, zero), equal(W, 1)))).
eq(X, times(X, Y), or(equal(X, zero), and(numberp(X), equal(Y, 1)))).
eq(times(A, B), 1, and(not(equal(A, zero)), and(not(equal(B, zero)), and(numberp(A), and(numberp(B), and(equal(decr(A), zero), equal(decr(B), zero))))))).
eq(difference(X, Y), difference(Z, Y), if(lessp(X, Y), not(lessp(Y, Z)), if(lessp(Z, Y), not(lessp(Y, X)), equal(fix(X), fix(Z))))).
eq(lessp(X, Y), Z, if(lessp(X, Y), equal(t, Z), equal(f, Z))).
exp(I, plus(J, K), times(exp(I, J), exp(I, K))).
exp(I, times(J, K), exp(exp(I, J), K)).
gcd(X, Y, gcd(Y, X)).
gcd(times(X, Z), times(Y, Z), times(Z, gcd(X, Y))).
mylength(reverse(X), length(X)).
mylength(cons(X9, cons(X10, cons(X11, cons(X12, cons(X13, cons(X14, X7)))))), plus(6, length(X7))).
lessp(remainder(X15, Y), Y, not(zerop(Y))).
lessp(quotient(I, J), I, and(not(zerop(I)), or(zerop(J), not(equal(J, 1))))).
lessp(remainder(X, Y), X, and(not(zerop(Y)), and(not(zerop(X)), not(lessp(X, Y))))).
lessp(plus(X, Y), plus(X, Z), lessp(Y, Z)).
lessp(times(X, Z), times(Y, Z), and(not(zerop(Z)), lessp(X, Y))).
lessp(Y, plus(X, Y), not(zerop(X))).
lessp(length(delete(X, L)), length(L), member(X, L)).
meaning(plus_tree(append(X, Y)), A, plus(meaning(plus_tree(X), A), meaning(plus_tree(Y), A))).
meaning(plus_tree(plus_fringe(X)), A, fix(meaning(X, A))).
meaning(plus_tree(delete(X, Y)), A, if(member(X, Y), difference(meaning(plus_tree(Y), A), meaning(X, A)), meaning(plus_tree(Y), A))).
mymember(X, append(A, B), or(member(X, A), member(X, B))).
mymember(X, reverse(Y), member(X, Y)).
mymember(A, intersect(B, C), and(member(A, B), member(A, C))).
nth(zero, X16, zero).
nth([], I, if(zerop(I), [], zero)).
nth(append(A, B), I, append(nth(A, I), nth(B, difference(I, length(A))))).
plus(plus(X, Y), Z, plus(X, plus(Y, Z))).
plus(remainder(X, Y), times(Y, quotient(X, Y)), fix(X)).
plus(X, add1(Y), if(numberp(Y), add1(plus(X, Y)), add1(X))).
power_eval(big_plus1(L, I, Base), Base, plus(power_eval(L, Base), I)).
power_eval(power_rep(I, Base), Base, fix(I)).
power_eval(big_plus(X, Y, I, Base), Base, plus(I, plus(power_eval(X, Base), power_eval(Y, Base)))).
power_eval(big_plus(power_rep(I, Base), power_rep(J, Base), zero, Base), Base, plus(I, J)).
quotient(plus(X, plus(X, Y)), 2, plus(X, quotient(Y, 2))).
quotient(times(Y, X), Y, if(zerop(Y), zero, fix(X))).
remainder(X17, 1, zero).
remainder(X, X, zero).
remainder(times(X18, Z), Z, zero).
remainder(times(Y, X19), Y, zero).
reverse_loop(X, Y, append(reverse(X), Y)).
reverse_loop(X, [], reverse(X)).
times(X, plus(Y, Z), plus(times(X, Y), times(X, Z))).
times(times(X, Y), Z, times(X, times(Y, Z))).
times(X, difference(C, W), difference(times(C, X), times(W, X))).
times(X, add1(Y), if(numberp(Y), plus(X, times(X, Y)), fix(X))).
go(T) :- ','(time(X20), ','(wff(X), ','(tautology(X), time(T)))).
time(T) :- statistics(runtime, .(X21, .(T, []))).
wff(implies(and(implies(X, Y), and(implies(Y, Z), and(implies(Z, U), implies(U, W)))), implies(X, W))) :- ','(=(X, f(plus(plus(a, b), plus(c, zero)))), ','(=(Y, f(times(times(a, b), plus(c, d)))), ','(=(Z, f(reverse(append(append(a, b), [])))), ','(=(U, equal(plus(a, b), difference(x, y))), =(W, lessp(remainder(a, b), member(a, length(b)))))))).
if1(Wff, Tlist, Flist) :- ','(call1(Wff, Tlist), ','(!, true)).
if1(Wff, Tlist, Flist) :- if4(Wff, Flist).
if2(Wff, If, Then, Else, Tlist, Flist) :- ','(call2(Wff, If, Then, Else), ','(!, ;(if5(If, Tlist, Then, Flist, Else), ','(tautology(Then, .(If, Tlist), Flist), tautology(Else, Tlist, .(If, Flist)))))).
if3(Mid, Next, New) :- ','(call3(Mid, Next), ','(!, rewrite(Next, New))).
if3(Mid, Next, New) :- =(New, Mid).
if4(Wff, Flist) :- ','(call4(Wff, Flist), ','(!, fail)).
if5(If, Tlist, Then, Flist, Else) :- ','(call5(If, Tlist), ','(!, tautology(Then, Tlist, Flist))).
if5(If, Tlist, Then, Flist, Else) :- if6(If, Flist, Else, Tlist).
if6(If, Flist, Else, Tlist) :- ','(call6(If, Flist), ','(!, tautology(Else, Tlist, Flist))).
call1(Wff, Tlist) :- truep(Wff, Tlist).
call2(Wff, If, Then, Else) :- =(Wff, if(If, Then, Else)).
call3(Mid, Next) :- equal(Mid, Next).
call4(Wff, Flist) :- falsep(Wff, Flist).
call5(If, Tlist) :- truep(If, Tlist).
call6(If, Flist) :- falsep(If, Flist).


Query: tautology(g)
----------------------------------------

(7) CutEliminatorProof (SOUND)
Eliminated all cuts by simply ignoring them[PROLOG].
----------------------------------------

(8)
Obligation:
Clauses:

tautology(Wff) :- ','(write('rewriting...'), ','(nl, ','(rewrite(Wff, NewWff), ','(write('proving...'), ','(nl, tautology(NewWff, [], [])))))).
tautology(Wff, Tlist, Flist) :- ;(if1(Wff, Tlist, Flist), if2(Wff, If, Then, Else, Tlist, Flist)).
rewrite(Atom, Atom) :- atomic(Atom).
rewrite(Old, New) :- ','(functor(Old, F, N), ','(functor(Mid, F, N), ','(rewrite_args(N, Old, Mid), if3(Mid, Next, New)))).
rewrite_args(0, X1, X2).
rewrite_args(N, Old, Mid) :- ','(arg(N, Old, OldArg), ','(arg(N, Mid, MidArg), ','(rewrite(OldArg, MidArg), ','(is(N1, -(N, 1)), rewrite_args(N1, Old, Mid))))).
truep(t, X3).
truep(Wff, Tlist) :- member(Wff, Tlist).
falsep(f, X4).
falsep(Wff, Flist) :- member(Wff, Flist).
member(X, .(X, X5)).
member(X, .(X6, T)) :- member(X, T).
equal(and(P, Q), if(P, if(Q, t, f), f)).
equal(append(append(X, Y), Z), append(X, append(Y, Z))).
equal(assignment(X, append(A, B)), if(assignedp(X, A), assignment(X, A), assignment(X, B))).
equal(assume_false(Var, Alist), cons(cons(Var, f), Alist)).
equal(assume_true(Var, Alist), cons(cons(Var, t), Alist)).
equal(boolean(X), or(equal(X, t), equal(X, f))).
equal(car(gopher(X)), if(listp(X), car(flatten(X)), zero)).
equal(compile(Form), reverse(codegen(optimize(Form), []))).
equal(count_list(Z, sort_lp(X, Y)), plus(count_list(Z, X), count_list(Z, Y))).
equal(countps_(L, Pred), countps_loop(L, Pred, zero)).
equal(difference(A, B), C) :- difference(A, B, C).
equal(divides(X, Y), zerop(remainder(Y, X))).
equal(dsort(X), sort2(X)).
equal(eqp(X, Y), equal(fix(X), fix(Y))).
equal(equal(A, B), C) :- eq(A, B, C).
equal(even1(X), if(zerop(X), t, odd(decr(X)))).
equal(exec(append(X, Y), Pds, Envrn), exec(Y, exec(X, Pds, Envrn), Envrn)).
equal(exp(A, B), C) :- exp(A, B, C).
equal(fact_(I), fact_loop(I, 1)).
equal(falsify(X), falsify1(normalize(X), [])).
equal(fix(X), if(numberp(X), X, zero)).
equal(flatten(cdr(gopher(X))), if(listp(X), cdr(flatten(X)), cons(zero, []))).
equal(gcd(A, B), C) :- gcd(A, B, C).
equal(get(J, set(I, Val, Mem)), if(eqp(J, I), Val, get(J, Mem))).
equal(greatereqp(X, Y), not(lessp(X, Y))).
equal(greatereqpr(X, Y), not(lessp(X, Y))).
equal(greaterp(X, Y), lessp(Y, X)).
equal(if(if(A, B, C), D, E), if(A, if(B, D, E), if(C, D, E))).
equal(iff(X, Y), and(implies(X, Y), implies(Y, X))).
equal(implies(P, Q), if(P, if(Q, t, f), t)).
equal(last(append(A, B)), if(listp(B), last(B), if(listp(A), cons(car(last(A))), B))).
equal(length(A), B) :- mylength(A, B).
equal(lesseqp(X, Y), not(lessp(Y, X))).
equal(lessp(A, B), C) :- lessp(A, B, C).
equal(listp(gopher(X)), listp(X)).
equal(mc_flatten(X, Y), append(flatten(X), Y)).
equal(meaning(A, B), C) :- meaning(A, B, C).
equal(member(A, B), C) :- mymember(A, B, C).
equal(not(P), if(P, f, t)).
equal(nth(A, B), C) :- nth(A, B, C).
equal(numberp(greatest_factor(X, Y)), not(and(or(zerop(Y), equal(Y, 1)), not(numberp(X))))).
equal(or(P, Q), if(P, t, if(Q, t, f), f)).
equal(plus(A, B), C) :- plus(A, B, C).
equal(power_eval(A, B), C) :- power_eval(A, B, C).
equal(prime(X), and(not(zerop(X)), and(not(equal(X, add1(zero))), prime1(X, decr(X))))).
equal(prime_list(append(X, Y)), and(prime_list(X), prime_list(Y))).
equal(quotient(A, B), C) :- quotient(A, B, C).
equal(remainder(A, B), C) :- remainder(A, B, C).
equal(reverse_(X), reverse_loop(X, [])).
equal(reverse(append(A, B)), append(reverse(B), reverse(A))).
equal(reverse_loop(A, B), C) :- reverse_loop(A, B, C).
equal(samefringe(X, Y), equal(flatten(X), flatten(Y))).
equal(sigma(zero, I), quotient(times(I, add1(I)), 2)).
equal(sort2(delete(X, L)), delete(X, sort2(L))).
equal(tautology_checker(X), tautologyp(normalize(X), [])).
equal(times(A, B), C) :- times(A, B, C).
equal(times_list(append(X, Y)), times(times_list(X), times_list(Y))).
equal(value(normalize(X), A), value(X, A)).
equal(zerop(X), or(equal(X, zero), not(numberp(X)))).
difference(X, X, zero).
difference(plus(X, Y), X, fix(Y)).
difference(plus(Y, X), X, fix(Y)).
difference(plus(X, Y), plus(X, Z), difference(Y, Z)).
difference(plus(B, plus(A, C)), A, plus(B, C)).
difference(add1(plus(Y, Z)), Z, add1(Y)).
difference(add1(add1(X)), 2, fix(X)).
eq(plus(A, B), zero, and(zerop(A), zerop(B))).
eq(plus(A, B), plus(A, C), equal(fix(B), fix(C))).
eq(zero, difference(X, Y), not(lessp(Y, X))).
eq(X, difference(X, Y), and(numberp(X), and(or(equal(X, zero), zerop(Y))))).
eq(times(X, Y), zero, or(zerop(X), zerop(Y))).
eq(append(A, B), append(A, C), equal(B, C)).
eq(flatten(X), cons(Y, []), and(nlistp(X), equal(X, Y))).
eq(greatest_factor(X, Y), zero, and(or(zerop(Y), equal(Y, 1)), equal(X, zero))).
eq(greatest_factor(X, X8), 1, equal(X, 1)).
eq(Z, times(W, Z), and(numberp(Z), or(equal(Z, zero), equal(W, 1)))).
eq(X, times(X, Y), or(equal(X, zero), and(numberp(X), equal(Y, 1)))).
eq(times(A, B), 1, and(not(equal(A, zero)), and(not(equal(B, zero)), and(numberp(A), and(numberp(B), and(equal(decr(A), zero), equal(decr(B), zero))))))).
eq(difference(X, Y), difference(Z, Y), if(lessp(X, Y), not(lessp(Y, Z)), if(lessp(Z, Y), not(lessp(Y, X)), equal(fix(X), fix(Z))))).
eq(lessp(X, Y), Z, if(lessp(X, Y), equal(t, Z), equal(f, Z))).
exp(I, plus(J, K), times(exp(I, J), exp(I, K))).
exp(I, times(J, K), exp(exp(I, J), K)).
gcd(X, Y, gcd(Y, X)).
gcd(times(X, Z), times(Y, Z), times(Z, gcd(X, Y))).
mylength(reverse(X), length(X)).
mylength(cons(X9, cons(X10, cons(X11, cons(X12, cons(X13, cons(X14, X7)))))), plus(6, length(X7))).
lessp(remainder(X15, Y), Y, not(zerop(Y))).
lessp(quotient(I, J), I, and(not(zerop(I)), or(zerop(J), not(equal(J, 1))))).
lessp(remainder(X, Y), X, and(not(zerop(Y)), and(not(zerop(X)), not(lessp(X, Y))))).
lessp(plus(X, Y), plus(X, Z), lessp(Y, Z)).
lessp(times(X, Z), times(Y, Z), and(not(zerop(Z)), lessp(X, Y))).
lessp(Y, plus(X, Y), not(zerop(X))).
lessp(length(delete(X, L)), length(L), member(X, L)).
meaning(plus_tree(append(X, Y)), A, plus(meaning(plus_tree(X), A), meaning(plus_tree(Y), A))).
meaning(plus_tree(plus_fringe(X)), A, fix(meaning(X, A))).
meaning(plus_tree(delete(X, Y)), A, if(member(X, Y), difference(meaning(plus_tree(Y), A), meaning(X, A)), meaning(plus_tree(Y), A))).
mymember(X, append(A, B), or(member(X, A), member(X, B))).
mymember(X, reverse(Y), member(X, Y)).
mymember(A, intersect(B, C), and(member(A, B), member(A, C))).
nth(zero, X16, zero).
nth([], I, if(zerop(I), [], zero)).
nth(append(A, B), I, append(nth(A, I), nth(B, difference(I, length(A))))).
plus(plus(X, Y), Z, plus(X, plus(Y, Z))).
plus(remainder(X, Y), times(Y, quotient(X, Y)), fix(X)).
plus(X, add1(Y), if(numberp(Y), add1(plus(X, Y)), add1(X))).
power_eval(big_plus1(L, I, Base), Base, plus(power_eval(L, Base), I)).
power_eval(power_rep(I, Base), Base, fix(I)).
power_eval(big_plus(X, Y, I, Base), Base, plus(I, plus(power_eval(X, Base), power_eval(Y, Base)))).
power_eval(big_plus(power_rep(I, Base), power_rep(J, Base), zero, Base), Base, plus(I, J)).
quotient(plus(X, plus(X, Y)), 2, plus(X, quotient(Y, 2))).
quotient(times(Y, X), Y, if(zerop(Y), zero, fix(X))).
remainder(X17, 1, zero).
remainder(X, X, zero).
remainder(times(X18, Z), Z, zero).
remainder(times(Y, X19), Y, zero).
reverse_loop(X, Y, append(reverse(X), Y)).
reverse_loop(X, [], reverse(X)).
times(X, plus(Y, Z), plus(times(X, Y), times(X, Z))).
times(times(X, Y), Z, times(X, times(Y, Z))).
times(X, difference(C, W), difference(times(C, X), times(W, X))).
times(X, add1(Y), if(numberp(Y), plus(X, times(X, Y)), fix(X))).
go(T) :- ','(time(X20), ','(wff(X), ','(tautology(X), time(T)))).
time(T) :- statistics(runtime, .(X21, .(T, []))).
wff(implies(and(implies(X, Y), and(implies(Y, Z), and(implies(Z, U), implies(U, W)))), implies(X, W))) :- ','(=(X, f(plus(plus(a, b), plus(c, zero)))), ','(=(Y, f(times(times(a, b), plus(c, d)))), ','(=(Z, f(reverse(append(append(a, b), [])))), ','(=(U, equal(plus(a, b), difference(x, y))), =(W, lessp(remainder(a, b), member(a, length(b)))))))).
if1(Wff, Tlist, Flist) :- call1(Wff, Tlist).
if1(Wff, Tlist, Flist) :- if4(Wff, Flist).
if2(Wff, If, Then, Else, Tlist, Flist) :- ','(call2(Wff, If, Then, Else), ;(if5(If, Tlist, Then, Flist, Else), ','(tautology(Then, .(If, Tlist), Flist), tautology(Else, Tlist, .(If, Flist))))).
if3(Mid, Next, New) :- ','(call3(Mid, Next), rewrite(Next, New)).
if3(Mid, Next, New) :- =(New, Mid).
if4(Wff, Flist) :- ','(call4(Wff, Flist), fail).
if5(If, Tlist, Then, Flist, Else) :- ','(call5(If, Tlist), tautology(Then, Tlist, Flist)).
if5(If, Tlist, Then, Flist, Else) :- if6(If, Flist, Else, Tlist).
if6(If, Flist, Else, Tlist) :- ','(call6(If, Flist), tautology(Else, Tlist, Flist)).
call1(Wff, Tlist) :- truep(Wff, Tlist).
call2(Wff, If, Then, Else) :- =(Wff, if(If, Then, Else)).
call3(Mid, Next) :- equal(Mid, Next).
call4(Wff, Flist) :- falsep(Wff, Flist).
call5(If, Tlist) :- truep(If, Tlist).
call6(If, Flist) :- falsep(If, Flist).


Query: tautology(g)
----------------------------------------

(9) FailTransformerProof (EQUIVALENT)
Added clauses for the built-in fail predicate [PROLOG].
----------------------------------------

(10)
Obligation:
Clauses:

tautology(Wff) :- ','(write('rewriting...'), ','(nl, ','(rewrite(Wff, NewWff), ','(write('proving...'), ','(nl, tautology(NewWff, [], [])))))).
tautology(Wff, Tlist, Flist) :- ;(if1(Wff, Tlist, Flist), if2(Wff, If, Then, Else, Tlist, Flist)).
rewrite(Atom, Atom) :- atomic(Atom).
rewrite(Old, New) :- ','(functor(Old, F, N), ','(functor(Mid, F, N), ','(rewrite_args(N, Old, Mid), if3(Mid, Next, New)))).
rewrite_args(0, X1, X2).
rewrite_args(N, Old, Mid) :- ','(arg(N, Old, OldArg), ','(arg(N, Mid, MidArg), ','(rewrite(OldArg, MidArg), ','(is(N1, -(N, 1)), rewrite_args(N1, Old, Mid))))).
truep(t, X3).
truep(Wff, Tlist) :- member(Wff, Tlist).
falsep(f, X4).
falsep(Wff, Flist) :- member(Wff, Flist).
member(X, .(X, X5)).
member(X, .(X6, T)) :- member(X, T).
equal(and(P, Q), if(P, if(Q, t, f), f)).
equal(append(append(X, Y), Z), append(X, append(Y, Z))).
equal(assignment(X, append(A, B)), if(assignedp(X, A), assignment(X, A), assignment(X, B))).
equal(assume_false(Var, Alist), cons(cons(Var, f), Alist)).
equal(assume_true(Var, Alist), cons(cons(Var, t), Alist)).
equal(boolean(X), or(equal(X, t), equal(X, f))).
equal(car(gopher(X)), if(listp(X), car(flatten(X)), zero)).
equal(compile(Form), reverse(codegen(optimize(Form), []))).
equal(count_list(Z, sort_lp(X, Y)), plus(count_list(Z, X), count_list(Z, Y))).
equal(countps_(L, Pred), countps_loop(L, Pred, zero)).
equal(difference(A, B), C) :- difference(A, B, C).
equal(divides(X, Y), zerop(remainder(Y, X))).
equal(dsort(X), sort2(X)).
equal(eqp(X, Y), equal(fix(X), fix(Y))).
equal(equal(A, B), C) :- eq(A, B, C).
equal(even1(X), if(zerop(X), t, odd(decr(X)))).
equal(exec(append(X, Y), Pds, Envrn), exec(Y, exec(X, Pds, Envrn), Envrn)).
equal(exp(A, B), C) :- exp(A, B, C).
equal(fact_(I), fact_loop(I, 1)).
equal(falsify(X), falsify1(normalize(X), [])).
equal(fix(X), if(numberp(X), X, zero)).
equal(flatten(cdr(gopher(X))), if(listp(X), cdr(flatten(X)), cons(zero, []))).
equal(gcd(A, B), C) :- gcd(A, B, C).
equal(get(J, set(I, Val, Mem)), if(eqp(J, I), Val, get(J, Mem))).
equal(greatereqp(X, Y), not(lessp(X, Y))).
equal(greatereqpr(X, Y), not(lessp(X, Y))).
equal(greaterp(X, Y), lessp(Y, X)).
equal(if(if(A, B, C), D, E), if(A, if(B, D, E), if(C, D, E))).
equal(iff(X, Y), and(implies(X, Y), implies(Y, X))).
equal(implies(P, Q), if(P, if(Q, t, f), t)).
equal(last(append(A, B)), if(listp(B), last(B), if(listp(A), cons(car(last(A))), B))).
equal(length(A), B) :- mylength(A, B).
equal(lesseqp(X, Y), not(lessp(Y, X))).
equal(lessp(A, B), C) :- lessp(A, B, C).
equal(listp(gopher(X)), listp(X)).
equal(mc_flatten(X, Y), append(flatten(X), Y)).
equal(meaning(A, B), C) :- meaning(A, B, C).
equal(member(A, B), C) :- mymember(A, B, C).
equal(not(P), if(P, f, t)).
equal(nth(A, B), C) :- nth(A, B, C).
equal(numberp(greatest_factor(X, Y)), not(and(or(zerop(Y), equal(Y, 1)), not(numberp(X))))).
equal(or(P, Q), if(P, t, if(Q, t, f), f)).
equal(plus(A, B), C) :- plus(A, B, C).
equal(power_eval(A, B), C) :- power_eval(A, B, C).
equal(prime(X), and(not(zerop(X)), and(not(equal(X, add1(zero))), prime1(X, decr(X))))).
equal(prime_list(append(X, Y)), and(prime_list(X), prime_list(Y))).
equal(quotient(A, B), C) :- quotient(A, B, C).
equal(remainder(A, B), C) :- remainder(A, B, C).
equal(reverse_(X), reverse_loop(X, [])).
equal(reverse(append(A, B)), append(reverse(B), reverse(A))).
equal(reverse_loop(A, B), C) :- reverse_loop(A, B, C).
equal(samefringe(X, Y), equal(flatten(X), flatten(Y))).
equal(sigma(zero, I), quotient(times(I, add1(I)), 2)).
equal(sort2(delete(X, L)), delete(X, sort2(L))).
equal(tautology_checker(X), tautologyp(normalize(X), [])).
equal(times(A, B), C) :- times(A, B, C).
equal(times_list(append(X, Y)), times(times_list(X), times_list(Y))).
equal(value(normalize(X), A), value(X, A)).
equal(zerop(X), or(equal(X, zero), not(numberp(X)))).
difference(X, X, zero).
difference(plus(X, Y), X, fix(Y)).
difference(plus(Y, X), X, fix(Y)).
difference(plus(X, Y), plus(X, Z), difference(Y, Z)).
difference(plus(B, plus(A, C)), A, plus(B, C)).
difference(add1(plus(Y, Z)), Z, add1(Y)).
difference(add1(add1(X)), 2, fix(X)).
eq(plus(A, B), zero, and(zerop(A), zerop(B))).
eq(plus(A, B), plus(A, C), equal(fix(B), fix(C))).
eq(zero, difference(X, Y), not(lessp(Y, X))).
eq(X, difference(X, Y), and(numberp(X), and(or(equal(X, zero), zerop(Y))))).
eq(times(X, Y), zero, or(zerop(X), zerop(Y))).
eq(append(A, B), append(A, C), equal(B, C)).
eq(flatten(X), cons(Y, []), and(nlistp(X), equal(X, Y))).
eq(greatest_factor(X, Y), zero, and(or(zerop(Y), equal(Y, 1)), equal(X, zero))).
eq(greatest_factor(X, X8), 1, equal(X, 1)).
eq(Z, times(W, Z), and(numberp(Z), or(equal(Z, zero), equal(W, 1)))).
eq(X, times(X, Y), or(equal(X, zero), and(numberp(X), equal(Y, 1)))).
eq(times(A, B), 1, and(not(equal(A, zero)), and(not(equal(B, zero)), and(numberp(A), and(numberp(B), and(equal(decr(A), zero), equal(decr(B), zero))))))).
eq(difference(X, Y), difference(Z, Y), if(lessp(X, Y), not(lessp(Y, Z)), if(lessp(Z, Y), not(lessp(Y, X)), equal(fix(X), fix(Z))))).
eq(lessp(X, Y), Z, if(lessp(X, Y), equal(t, Z), equal(f, Z))).
exp(I, plus(J, K), times(exp(I, J), exp(I, K))).
exp(I, times(J, K), exp(exp(I, J), K)).
gcd(X, Y, gcd(Y, X)).
gcd(times(X, Z), times(Y, Z), times(Z, gcd(X, Y))).
mylength(reverse(X), length(X)).
mylength(cons(X9, cons(X10, cons(X11, cons(X12, cons(X13, cons(X14, X7)))))), plus(6, length(X7))).
lessp(remainder(X15, Y), Y, not(zerop(Y))).
lessp(quotient(I, J), I, and(not(zerop(I)), or(zerop(J), not(equal(J, 1))))).
lessp(remainder(X, Y), X, and(not(zerop(Y)), and(not(zerop(X)), not(lessp(X, Y))))).
lessp(plus(X, Y), plus(X, Z), lessp(Y, Z)).
lessp(times(X, Z), times(Y, Z), and(not(zerop(Z)), lessp(X, Y))).
lessp(Y, plus(X, Y), not(zerop(X))).
lessp(length(delete(X, L)), length(L), member(X, L)).
meaning(plus_tree(append(X, Y)), A, plus(meaning(plus_tree(X), A), meaning(plus_tree(Y), A))).
meaning(plus_tree(plus_fringe(X)), A, fix(meaning(X, A))).
meaning(plus_tree(delete(X, Y)), A, if(member(X, Y), difference(meaning(plus_tree(Y), A), meaning(X, A)), meaning(plus_tree(Y), A))).
mymember(X, append(A, B), or(member(X, A), member(X, B))).
mymember(X, reverse(Y), member(X, Y)).
mymember(A, intersect(B, C), and(member(A, B), member(A, C))).
nth(zero, X16, zero).
nth([], I, if(zerop(I), [], zero)).
nth(append(A, B), I, append(nth(A, I), nth(B, difference(I, length(A))))).
plus(plus(X, Y), Z, plus(X, plus(Y, Z))).
plus(remainder(X, Y), times(Y, quotient(X, Y)), fix(X)).
plus(X, add1(Y), if(numberp(Y), add1(plus(X, Y)), add1(X))).
power_eval(big_plus1(L, I, Base), Base, plus(power_eval(L, Base), I)).
power_eval(power_rep(I, Base), Base, fix(I)).
power_eval(big_plus(X, Y, I, Base), Base, plus(I, plus(power_eval(X, Base), power_eval(Y, Base)))).
power_eval(big_plus(power_rep(I, Base), power_rep(J, Base), zero, Base), Base, plus(I, J)).
quotient(plus(X, plus(X, Y)), 2, plus(X, quotient(Y, 2))).
quotient(times(Y, X), Y, if(zerop(Y), zero, fix(X))).
remainder(X17, 1, zero).
remainder(X, X, zero).
remainder(times(X18, Z), Z, zero).
remainder(times(Y, X19), Y, zero).
reverse_loop(X, Y, append(reverse(X), Y)).
reverse_loop(X, [], reverse(X)).
times(X, plus(Y, Z), plus(times(X, Y), times(X, Z))).
times(times(X, Y), Z, times(X, times(Y, Z))).
times(X, difference(C, W), difference(times(C, X), times(W, X))).
times(X, add1(Y), if(numberp(Y), plus(X, times(X, Y)), fix(X))).
go(T) :- ','(time(X20), ','(wff(X), ','(tautology(X), time(T)))).
time(T) :- statistics(runtime, .(X21, .(T, []))).
wff(implies(and(implies(X, Y), and(implies(Y, Z), and(implies(Z, U), implies(U, W)))), implies(X, W))) :- ','(=(X, f(plus(plus(a, b), plus(c, zero)))), ','(=(Y, f(times(times(a, b), plus(c, d)))), ','(=(Z, f(reverse(append(append(a, b), [])))), ','(=(U, equal(plus(a, b), difference(x, y))), =(W, lessp(remainder(a, b), member(a, length(b)))))))).
if1(Wff, Tlist, Flist) :- call1(Wff, Tlist).
if1(Wff, Tlist, Flist) :- if4(Wff, Flist).
if2(Wff, If, Then, Else, Tlist, Flist) :- ','(call2(Wff, If, Then, Else), ;(if5(If, Tlist, Then, Flist, Else), ','(tautology(Then, .(If, Tlist), Flist), tautology(Else, Tlist, .(If, Flist))))).
if3(Mid, Next, New) :- ','(call3(Mid, Next), rewrite(Next, New)).
if3(Mid, Next, New) :- =(New, Mid).
if4(Wff, Flist) :- ','(call4(Wff, Flist), fail).
if5(If, Tlist, Then, Flist, Else) :- ','(call5(If, Tlist), tautology(Then, Tlist, Flist)).
if5(If, Tlist, Then, Flist, Else) :- if6(If, Flist, Else, Tlist).
if6(If, Flist, Else, Tlist) :- ','(call6(If, Flist), tautology(Else, Tlist, Flist)).
call1(Wff, Tlist) :- truep(Wff, Tlist).
call2(Wff, If, Then, Else) :- =(Wff, if(If, Then, Else)).
call3(Mid, Next) :- equal(Mid, Next).
call4(Wff, Flist) :- falsep(Wff, Flist).
call5(If, Tlist) :- truep(If, Tlist).
call6(If, Flist) :- falsep(If, Flist).
fail :- failure(a).
failure(b).


Query: tautology(g)
----------------------------------------

(11) UnifyTransformerProof (EQUIVALENT)
Added a fact for the built-in = predicate [PROLOG].
----------------------------------------

(12)
Obligation:
Clauses:

tautology(Wff) :- ','(write('rewriting...'), ','(nl, ','(rewrite(Wff, NewWff), ','(write('proving...'), ','(nl, tautology(NewWff, [], [])))))).
tautology(Wff, Tlist, Flist) :- ;(if1(Wff, Tlist, Flist), if2(Wff, If, Then, Else, Tlist, Flist)).
rewrite(Atom, Atom) :- atomic(Atom).
rewrite(Old, New) :- ','(functor(Old, F, N), ','(functor(Mid, F, N), ','(rewrite_args(N, Old, Mid), if3(Mid, Next, New)))).
rewrite_args(0, X1, X2).
rewrite_args(N, Old, Mid) :- ','(arg(N, Old, OldArg), ','(arg(N, Mid, MidArg), ','(rewrite(OldArg, MidArg), ','(is(N1, -(N, 1)), rewrite_args(N1, Old, Mid))))).
truep(t, X3).
truep(Wff, Tlist) :- member(Wff, Tlist).
falsep(f, X4).
falsep(Wff, Flist) :- member(Wff, Flist).
member(X, .(X, X5)).
member(X, .(X6, T)) :- member(X, T).
equal(and(P, Q), if(P, if(Q, t, f), f)).
equal(append(append(X, Y), Z), append(X, append(Y, Z))).
equal(assignment(X, append(A, B)), if(assignedp(X, A), assignment(X, A), assignment(X, B))).
equal(assume_false(Var, Alist), cons(cons(Var, f), Alist)).
equal(assume_true(Var, Alist), cons(cons(Var, t), Alist)).
equal(boolean(X), or(equal(X, t), equal(X, f))).
equal(car(gopher(X)), if(listp(X), car(flatten(X)), zero)).
equal(compile(Form), reverse(codegen(optimize(Form), []))).
equal(count_list(Z, sort_lp(X, Y)), plus(count_list(Z, X), count_list(Z, Y))).
equal(countps_(L, Pred), countps_loop(L, Pred, zero)).
equal(difference(A, B), C) :- difference(A, B, C).
equal(divides(X, Y), zerop(remainder(Y, X))).
equal(dsort(X), sort2(X)).
equal(eqp(X, Y), equal(fix(X), fix(Y))).
equal(equal(A, B), C) :- eq(A, B, C).
equal(even1(X), if(zerop(X), t, odd(decr(X)))).
equal(exec(append(X, Y), Pds, Envrn), exec(Y, exec(X, Pds, Envrn), Envrn)).
equal(exp(A, B), C) :- exp(A, B, C).
equal(fact_(I), fact_loop(I, 1)).
equal(falsify(X), falsify1(normalize(X), [])).
equal(fix(X), if(numberp(X), X, zero)).
equal(flatten(cdr(gopher(X))), if(listp(X), cdr(flatten(X)), cons(zero, []))).
equal(gcd(A, B), C) :- gcd(A, B, C).
equal(get(J, set(I, Val, Mem)), if(eqp(J, I), Val, get(J, Mem))).
equal(greatereqp(X, Y), not(lessp(X, Y))).
equal(greatereqpr(X, Y), not(lessp(X, Y))).
equal(greaterp(X, Y), lessp(Y, X)).
equal(if(if(A, B, C), D, E), if(A, if(B, D, E), if(C, D, E))).
equal(iff(X, Y), and(implies(X, Y), implies(Y, X))).
equal(implies(P, Q), if(P, if(Q, t, f), t)).
equal(last(append(A, B)), if(listp(B), last(B), if(listp(A), cons(car(last(A))), B))).
equal(length(A), B) :- mylength(A, B).
equal(lesseqp(X, Y), not(lessp(Y, X))).
equal(lessp(A, B), C) :- lessp(A, B, C).
equal(listp(gopher(X)), listp(X)).
equal(mc_flatten(X, Y), append(flatten(X), Y)).
equal(meaning(A, B), C) :- meaning(A, B, C).
equal(member(A, B), C) :- mymember(A, B, C).
equal(not(P), if(P, f, t)).
equal(nth(A, B), C) :- nth(A, B, C).
equal(numberp(greatest_factor(X, Y)), not(and(or(zerop(Y), equal(Y, 1)), not(numberp(X))))).
equal(or(P, Q), if(P, t, if(Q, t, f), f)).
equal(plus(A, B), C) :- plus(A, B, C).
equal(power_eval(A, B), C) :- power_eval(A, B, C).
equal(prime(X), and(not(zerop(X)), and(not(equal(X, add1(zero))), prime1(X, decr(X))))).
equal(prime_list(append(X, Y)), and(prime_list(X), prime_list(Y))).
equal(quotient(A, B), C) :- quotient(A, B, C).
equal(remainder(A, B), C) :- remainder(A, B, C).
equal(reverse_(X), reverse_loop(X, [])).
equal(reverse(append(A, B)), append(reverse(B), reverse(A))).
equal(reverse_loop(A, B), C) :- reverse_loop(A, B, C).
equal(samefringe(X, Y), equal(flatten(X), flatten(Y))).
equal(sigma(zero, I), quotient(times(I, add1(I)), 2)).
equal(sort2(delete(X, L)), delete(X, sort2(L))).
equal(tautology_checker(X), tautologyp(normalize(X), [])).
equal(times(A, B), C) :- times(A, B, C).
equal(times_list(append(X, Y)), times(times_list(X), times_list(Y))).
equal(value(normalize(X), A), value(X, A)).
equal(zerop(X), or(equal(X, zero), not(numberp(X)))).
difference(X, X, zero).
difference(plus(X, Y), X, fix(Y)).
difference(plus(Y, X), X, fix(Y)).
difference(plus(X, Y), plus(X, Z), difference(Y, Z)).
difference(plus(B, plus(A, C)), A, plus(B, C)).
difference(add1(plus(Y, Z)), Z, add1(Y)).
difference(add1(add1(X)), 2, fix(X)).
eq(plus(A, B), zero, and(zerop(A), zerop(B))).
eq(plus(A, B), plus(A, C), equal(fix(B), fix(C))).
eq(zero, difference(X, Y), not(lessp(Y, X))).
eq(X, difference(X, Y), and(numberp(X), and(or(equal(X, zero), zerop(Y))))).
eq(times(X, Y), zero, or(zerop(X), zerop(Y))).
eq(append(A, B), append(A, C), equal(B, C)).
eq(flatten(X), cons(Y, []), and(nlistp(X), equal(X, Y))).
eq(greatest_factor(X, Y), zero, and(or(zerop(Y), equal(Y, 1)), equal(X, zero))).
eq(greatest_factor(X, X8), 1, equal(X, 1)).
eq(Z, times(W, Z), and(numberp(Z), or(equal(Z, zero), equal(W, 1)))).
eq(X, times(X, Y), or(equal(X, zero), and(numberp(X), equal(Y, 1)))).
eq(times(A, B), 1, and(not(equal(A, zero)), and(not(equal(B, zero)), and(numberp(A), and(numberp(B), and(equal(decr(A), zero), equal(decr(B), zero))))))).
eq(difference(X, Y), difference(Z, Y), if(lessp(X, Y), not(lessp(Y, Z)), if(lessp(Z, Y), not(lessp(Y, X)), equal(fix(X), fix(Z))))).
eq(lessp(X, Y), Z, if(lessp(X, Y), equal(t, Z), equal(f, Z))).
exp(I, plus(J, K), times(exp(I, J), exp(I, K))).
exp(I, times(J, K), exp(exp(I, J), K)).
gcd(X, Y, gcd(Y, X)).
gcd(times(X, Z), times(Y, Z), times(Z, gcd(X, Y))).
mylength(reverse(X), length(X)).
mylength(cons(X9, cons(X10, cons(X11, cons(X12, cons(X13, cons(X14, X7)))))), plus(6, length(X7))).
lessp(remainder(X15, Y), Y, not(zerop(Y))).
lessp(quotient(I, J), I, and(not(zerop(I)), or(zerop(J), not(equal(J, 1))))).
lessp(remainder(X, Y), X, and(not(zerop(Y)), and(not(zerop(X)), not(lessp(X, Y))))).
lessp(plus(X, Y), plus(X, Z), lessp(Y, Z)).
lessp(times(X, Z), times(Y, Z), and(not(zerop(Z)), lessp(X, Y))).
lessp(Y, plus(X, Y), not(zerop(X))).
lessp(length(delete(X, L)), length(L), member(X, L)).
meaning(plus_tree(append(X, Y)), A, plus(meaning(plus_tree(X), A), meaning(plus_tree(Y), A))).
meaning(plus_tree(plus_fringe(X)), A, fix(meaning(X, A))).
meaning(plus_tree(delete(X, Y)), A, if(member(X, Y), difference(meaning(plus_tree(Y), A), meaning(X, A)), meaning(plus_tree(Y), A))).
mymember(X, append(A, B), or(member(X, A), member(X, B))).
mymember(X, reverse(Y), member(X, Y)).
mymember(A, intersect(B, C), and(member(A, B), member(A, C))).
nth(zero, X16, zero).
nth([], I, if(zerop(I), [], zero)).
nth(append(A, B), I, append(nth(A, I), nth(B, difference(I, length(A))))).
plus(plus(X, Y), Z, plus(X, plus(Y, Z))).
plus(remainder(X, Y), times(Y, quotient(X, Y)), fix(X)).
plus(X, add1(Y), if(numberp(Y), add1(plus(X, Y)), add1(X))).
power_eval(big_plus1(L, I, Base), Base, plus(power_eval(L, Base), I)).
power_eval(power_rep(I, Base), Base, fix(I)).
power_eval(big_plus(X, Y, I, Base), Base, plus(I, plus(power_eval(X, Base), power_eval(Y, Base)))).
power_eval(big_plus(power_rep(I, Base), power_rep(J, Base), zero, Base), Base, plus(I, J)).
quotient(plus(X, plus(X, Y)), 2, plus(X, quotient(Y, 2))).
quotient(times(Y, X), Y, if(zerop(Y), zero, fix(X))).
remainder(X17, 1, zero).
remainder(X, X, zero).
remainder(times(X18, Z), Z, zero).
remainder(times(Y, X19), Y, zero).
reverse_loop(X, Y, append(reverse(X), Y)).
reverse_loop(X, [], reverse(X)).
times(X, plus(Y, Z), plus(times(X, Y), times(X, Z))).
times(times(X, Y), Z, times(X, times(Y, Z))).
times(X, difference(C, W), difference(times(C, X), times(W, X))).
times(X, add1(Y), if(numberp(Y), plus(X, times(X, Y)), fix(X))).
go(T) :- ','(time(X20), ','(wff(X), ','(tautology(X), time(T)))).
time(T) :- statistics(runtime, .(X21, .(T, []))).
wff(implies(and(implies(X, Y), and(implies(Y, Z), and(implies(Z, U), implies(U, W)))), implies(X, W))) :- ','(=(X, f(plus(plus(a, b), plus(c, zero)))), ','(=(Y, f(times(times(a, b), plus(c, d)))), ','(=(Z, f(reverse(append(append(a, b), [])))), ','(=(U, equal(plus(a, b), difference(x, y))), =(W, lessp(remainder(a, b), member(a, length(b)))))))).
if1(Wff, Tlist, Flist) :- call1(Wff, Tlist).
if1(Wff, Tlist, Flist) :- if4(Wff, Flist).
if2(Wff, If, Then, Else, Tlist, Flist) :- ','(call2(Wff, If, Then, Else), ;(if5(If, Tlist, Then, Flist, Else), ','(tautology(Then, .(If, Tlist), Flist), tautology(Else, Tlist, .(If, Flist))))).
if3(Mid, Next, New) :- ','(call3(Mid, Next), rewrite(Next, New)).
if3(Mid, Next, New) :- =(New, Mid).
if4(Wff, Flist) :- ','(call4(Wff, Flist), fail).
if5(If, Tlist, Then, Flist, Else) :- ','(call5(If, Tlist), tautology(Then, Tlist, Flist)).
if5(If, Tlist, Then, Flist, Else) :- if6(If, Flist, Else, Tlist).
if6(If, Flist, Else, Tlist) :- ','(call6(If, Flist), tautology(Else, Tlist, Flist)).
call1(Wff, Tlist) :- truep(Wff, Tlist).
call2(Wff, If, Then, Else) :- =(Wff, if(If, Then, Else)).
call3(Mid, Next) :- equal(Mid, Next).
call4(Wff, Flist) :- falsep(Wff, Flist).
call5(If, Tlist) :- truep(If, Tlist).
call6(If, Flist) :- falsep(If, Flist).
fail :- failure(a).
failure(b).
=(X, X).


Query: tautology(g)
----------------------------------------

(13) OrTransformerProof (EQUIVALENT)
Transformed all or-constructs[PROLOG].
----------------------------------------

(14)
Obligation:
Clauses:

tautology(Wff) :- ','(write('rewriting...'), ','(nl, ','(rewrite(Wff, NewWff), ','(write('proving...'), ','(nl, tautology(NewWff, [], [])))))).
tautology(Wff, Tlist, Flist) :- if1(Wff, Tlist, Flist).
tautology(Wff, Tlist, Flist) :- if2(Wff, If, Then, Else, Tlist, Flist).
rewrite(Atom, Atom) :- atomic(Atom).
rewrite(Old, New) :- ','(functor(Old, F, N), ','(functor(Mid, F, N), ','(rewrite_args(N, Old, Mid), if3(Mid, Next, New)))).
rewrite_args(0, X1, X2).
rewrite_args(N, Old, Mid) :- ','(arg(N, Old, OldArg), ','(arg(N, Mid, MidArg), ','(rewrite(OldArg, MidArg), ','(is(N1, -(N, 1)), rewrite_args(N1, Old, Mid))))).
truep(t, X3).
truep(Wff, Tlist) :- member(Wff, Tlist).
falsep(f, X4).
falsep(Wff, Flist) :- member(Wff, Flist).
member(X, .(X, X5)).
member(X, .(X6, T)) :- member(X, T).
equal(and(P, Q), if(P, if(Q, t, f), f)).
equal(append(append(X, Y), Z), append(X, append(Y, Z))).
equal(assignment(X, append(A, B)), if(assignedp(X, A), assignment(X, A), assignment(X, B))).
equal(assume_false(Var, Alist), cons(cons(Var, f), Alist)).
equal(assume_true(Var, Alist), cons(cons(Var, t), Alist)).
equal(boolean(X), or(equal(X, t), equal(X, f))).
equal(car(gopher(X)), if(listp(X), car(flatten(X)), zero)).
equal(compile(Form), reverse(codegen(optimize(Form), []))).
equal(count_list(Z, sort_lp(X, Y)), plus(count_list(Z, X), count_list(Z, Y))).
equal(countps_(L, Pred), countps_loop(L, Pred, zero)).
equal(difference(A, B), C) :- difference(A, B, C).
equal(divides(X, Y), zerop(remainder(Y, X))).
equal(dsort(X), sort2(X)).
equal(eqp(X, Y), equal(fix(X), fix(Y))).
equal(equal(A, B), C) :- eq(A, B, C).
equal(even1(X), if(zerop(X), t, odd(decr(X)))).
equal(exec(append(X, Y), Pds, Envrn), exec(Y, exec(X, Pds, Envrn), Envrn)).
equal(exp(A, B), C) :- exp(A, B, C).
equal(fact_(I), fact_loop(I, 1)).
equal(falsify(X), falsify1(normalize(X), [])).
equal(fix(X), if(numberp(X), X, zero)).
equal(flatten(cdr(gopher(X))), if(listp(X), cdr(flatten(X)), cons(zero, []))).
equal(gcd(A, B), C) :- gcd(A, B, C).
equal(get(J, set(I, Val, Mem)), if(eqp(J, I), Val, get(J, Mem))).
equal(greatereqp(X, Y), not(lessp(X, Y))).
equal(greatereqpr(X, Y), not(lessp(X, Y))).
equal(greaterp(X, Y), lessp(Y, X)).
equal(if(if(A, B, C), D, E), if(A, if(B, D, E), if(C, D, E))).
equal(iff(X, Y), and(implies(X, Y), implies(Y, X))).
equal(implies(P, Q), if(P, if(Q, t, f), t)).
equal(last(append(A, B)), if(listp(B), last(B), if(listp(A), cons(car(last(A))), B))).
equal(length(A), B) :- mylength(A, B).
equal(lesseqp(X, Y), not(lessp(Y, X))).
equal(lessp(A, B), C) :- lessp(A, B, C).
equal(listp(gopher(X)), listp(X)).
equal(mc_flatten(X, Y), append(flatten(X), Y)).
equal(meaning(A, B), C) :- meaning(A, B, C).
equal(member(A, B), C) :- mymember(A, B, C).
equal(not(P), if(P, f, t)).
equal(nth(A, B), C) :- nth(A, B, C).
equal(numberp(greatest_factor(X, Y)), not(and(or(zerop(Y), equal(Y, 1)), not(numberp(X))))).
equal(or(P, Q), if(P, t, if(Q, t, f), f)).
equal(plus(A, B), C) :- plus(A, B, C).
equal(power_eval(A, B), C) :- power_eval(A, B, C).
equal(prime(X), and(not(zerop(X)), and(not(equal(X, add1(zero))), prime1(X, decr(X))))).
equal(prime_list(append(X, Y)), and(prime_list(X), prime_list(Y))).
equal(quotient(A, B), C) :- quotient(A, B, C).
equal(remainder(A, B), C) :- remainder(A, B, C).
equal(reverse_(X), reverse_loop(X, [])).
equal(reverse(append(A, B)), append(reverse(B), reverse(A))).
equal(reverse_loop(A, B), C) :- reverse_loop(A, B, C).
equal(samefringe(X, Y), equal(flatten(X), flatten(Y))).
equal(sigma(zero, I), quotient(times(I, add1(I)), 2)).
equal(sort2(delete(X, L)), delete(X, sort2(L))).
equal(tautology_checker(X), tautologyp(normalize(X), [])).
equal(times(A, B), C) :- times(A, B, C).
equal(times_list(append(X, Y)), times(times_list(X), times_list(Y))).
equal(value(normalize(X), A), value(X, A)).
equal(zerop(X), or(equal(X, zero), not(numberp(X)))).
difference(X, X, zero).
difference(plus(X, Y), X, fix(Y)).
difference(plus(Y, X), X, fix(Y)).
difference(plus(X, Y), plus(X, Z), difference(Y, Z)).
difference(plus(B, plus(A, C)), A, plus(B, C)).
difference(add1(plus(Y, Z)), Z, add1(Y)).
difference(add1(add1(X)), 2, fix(X)).
eq(plus(A, B), zero, and(zerop(A), zerop(B))).
eq(plus(A, B), plus(A, C), equal(fix(B), fix(C))).
eq(zero, difference(X, Y), not(lessp(Y, X))).
eq(X, difference(X, Y), and(numberp(X), and(or(equal(X, zero), zerop(Y))))).
eq(times(X, Y), zero, or(zerop(X), zerop(Y))).
eq(append(A, B), append(A, C), equal(B, C)).
eq(flatten(X), cons(Y, []), and(nlistp(X), equal(X, Y))).
eq(greatest_factor(X, Y), zero, and(or(zerop(Y), equal(Y, 1)), equal(X, zero))).
eq(greatest_factor(X, X8), 1, equal(X, 1)).
eq(Z, times(W, Z), and(numberp(Z), or(equal(Z, zero), equal(W, 1)))).
eq(X, times(X, Y), or(equal(X, zero), and(numberp(X), equal(Y, 1)))).
eq(times(A, B), 1, and(not(equal(A, zero)), and(not(equal(B, zero)), and(numberp(A), and(numberp(B), and(equal(decr(A), zero), equal(decr(B), zero))))))).
eq(difference(X, Y), difference(Z, Y), if(lessp(X, Y), not(lessp(Y, Z)), if(lessp(Z, Y), not(lessp(Y, X)), equal(fix(X), fix(Z))))).
eq(lessp(X, Y), Z, if(lessp(X, Y), equal(t, Z), equal(f, Z))).
exp(I, plus(J, K), times(exp(I, J), exp(I, K))).
exp(I, times(J, K), exp(exp(I, J), K)).
gcd(X, Y, gcd(Y, X)).
gcd(times(X, Z), times(Y, Z), times(Z, gcd(X, Y))).
mylength(reverse(X), length(X)).
mylength(cons(X9, cons(X10, cons(X11, cons(X12, cons(X13, cons(X14, X7)))))), plus(6, length(X7))).
lessp(remainder(X15, Y), Y, not(zerop(Y))).
lessp(quotient(I, J), I, and(not(zerop(I)), or(zerop(J), not(equal(J, 1))))).
lessp(remainder(X, Y), X, and(not(zerop(Y)), and(not(zerop(X)), not(lessp(X, Y))))).
lessp(plus(X, Y), plus(X, Z), lessp(Y, Z)).
lessp(times(X, Z), times(Y, Z), and(not(zerop(Z)), lessp(X, Y))).
lessp(Y, plus(X, Y), not(zerop(X))).
lessp(length(delete(X, L)), length(L), member(X, L)).
meaning(plus_tree(append(X, Y)), A, plus(meaning(plus_tree(X), A), meaning(plus_tree(Y), A))).
meaning(plus_tree(plus_fringe(X)), A, fix(meaning(X, A))).
meaning(plus_tree(delete(X, Y)), A, if(member(X, Y), difference(meaning(plus_tree(Y), A), meaning(X, A)), meaning(plus_tree(Y), A))).
mymember(X, append(A, B), or(member(X, A), member(X, B))).
mymember(X, reverse(Y), member(X, Y)).
mymember(A, intersect(B, C), and(member(A, B), member(A, C))).
nth(zero, X16, zero).
nth([], I, if(zerop(I), [], zero)).
nth(append(A, B), I, append(nth(A, I), nth(B, difference(I, length(A))))).
plus(plus(X, Y), Z, plus(X, plus(Y, Z))).
plus(remainder(X, Y), times(Y, quotient(X, Y)), fix(X)).
plus(X, add1(Y), if(numberp(Y), add1(plus(X, Y)), add1(X))).
power_eval(big_plus1(L, I, Base), Base, plus(power_eval(L, Base), I)).
power_eval(power_rep(I, Base), Base, fix(I)).
power_eval(big_plus(X, Y, I, Base), Base, plus(I, plus(power_eval(X, Base), power_eval(Y, Base)))).
power_eval(big_plus(power_rep(I, Base), power_rep(J, Base), zero, Base), Base, plus(I, J)).
quotient(plus(X, plus(X, Y)), 2, plus(X, quotient(Y, 2))).
quotient(times(Y, X), Y, if(zerop(Y), zero, fix(X))).
remainder(X17, 1, zero).
remainder(X, X, zero).
remainder(times(X18, Z), Z, zero).
remainder(times(Y, X19), Y, zero).
reverse_loop(X, Y, append(reverse(X), Y)).
reverse_loop(X, [], reverse(X)).
times(X, plus(Y, Z), plus(times(X, Y), times(X, Z))).
times(times(X, Y), Z, times(X, times(Y, Z))).
times(X, difference(C, W), difference(times(C, X), times(W, X))).
times(X, add1(Y), if(numberp(Y), plus(X, times(X, Y)), fix(X))).
go(T) :- ','(time(X20), ','(wff(X), ','(tautology(X), time(T)))).
time(T) :- statistics(runtime, .(X21, .(T, []))).
wff(implies(and(implies(X, Y), and(implies(Y, Z), and(implies(Z, U), implies(U, W)))), implies(X, W))) :- ','(=(X, f(plus(plus(a, b), plus(c, zero)))), ','(=(Y, f(times(times(a, b), plus(c, d)))), ','(=(Z, f(reverse(append(append(a, b), [])))), ','(=(U, equal(plus(a, b), difference(x, y))), =(W, lessp(remainder(a, b), member(a, length(b)))))))).
if1(Wff, Tlist, Flist) :- call1(Wff, Tlist).
if1(Wff, Tlist, Flist) :- if4(Wff, Flist).
if2(Wff, If, Then, Else, Tlist, Flist) :- ','(call2(Wff, If, Then, Else), if5(If, Tlist, Then, Flist, Else)).
if2(Wff, If, Then, Else, Tlist, Flist) :- ','(call2(Wff, If, Then, Else), ','(tautology(Then, .(If, Tlist), Flist), tautology(Else, Tlist, .(If, Flist)))).
if3(Mid, Next, New) :- ','(call3(Mid, Next), rewrite(Next, New)).
if3(Mid, Next, New) :- =(New, Mid).
if4(Wff, Flist) :- ','(call4(Wff, Flist), fail).
if5(If, Tlist, Then, Flist, Else) :- ','(call5(If, Tlist), tautology(Then, Tlist, Flist)).
if5(If, Tlist, Then, Flist, Else) :- if6(If, Flist, Else, Tlist).
if6(If, Flist, Else, Tlist) :- ','(call6(If, Flist), tautology(Else, Tlist, Flist)).
call1(Wff, Tlist) :- truep(Wff, Tlist).
call2(Wff, If, Then, Else) :- =(Wff, if(If, Then, Else)).
call3(Mid, Next) :- equal(Mid, Next).
call4(Wff, Flist) :- falsep(Wff, Flist).
call5(If, Tlist) :- truep(If, Tlist).
call6(If, Flist) :- falsep(If, Flist).
fail :- failure(a).
failure(b).
=(X, X).


Query: tautology(g)
----------------------------------------

(15) UndefinedPredicateHandlerProof (SOUND)
Added facts for all undefined predicates [PROLOG].
----------------------------------------

(16)
Obligation:
Clauses:

tautology(Wff) :- ','(write('rewriting...'), ','(nl, ','(rewrite(Wff, NewWff), ','(write('proving...'), ','(nl, tautology(NewWff, [], [])))))).
tautology(Wff, Tlist, Flist) :- if1(Wff, Tlist, Flist).
tautology(Wff, Tlist, Flist) :- if2(Wff, If, Then, Else, Tlist, Flist).
rewrite(Atom, Atom) :- atomic(Atom).
rewrite(Old, New) :- ','(functor(Old, F, N), ','(functor(Mid, F, N), ','(rewrite_args(N, Old, Mid), if3(Mid, Next, New)))).
rewrite_args(0, X1, X2).
rewrite_args(N, Old, Mid) :- ','(arg(N, Old, OldArg), ','(arg(N, Mid, MidArg), ','(rewrite(OldArg, MidArg), ','(is(N1, -(N, 1)), rewrite_args(N1, Old, Mid))))).
truep(t, X3).
truep(Wff, Tlist) :- member(Wff, Tlist).
falsep(f, X4).
falsep(Wff, Flist) :- member(Wff, Flist).
member(X, .(X, X5)).
member(X, .(X6, T)) :- member(X, T).
equal(and(P, Q), if(P, if(Q, t, f), f)).
equal(append(append(X, Y), Z), append(X, append(Y, Z))).
equal(assignment(X, append(A, B)), if(assignedp(X, A), assignment(X, A), assignment(X, B))).
equal(assume_false(Var, Alist), cons(cons(Var, f), Alist)).
equal(assume_true(Var, Alist), cons(cons(Var, t), Alist)).
equal(boolean(X), or(equal(X, t), equal(X, f))).
equal(car(gopher(X)), if(listp(X), car(flatten(X)), zero)).
equal(compile(Form), reverse(codegen(optimize(Form), []))).
equal(count_list(Z, sort_lp(X, Y)), plus(count_list(Z, X), count_list(Z, Y))).
equal(countps_(L, Pred), countps_loop(L, Pred, zero)).
equal(difference(A, B), C) :- difference(A, B, C).
equal(divides(X, Y), zerop(remainder(Y, X))).
equal(dsort(X), sort2(X)).
equal(eqp(X, Y), equal(fix(X), fix(Y))).
equal(equal(A, B), C) :- eq(A, B, C).
equal(even1(X), if(zerop(X), t, odd(decr(X)))).
equal(exec(append(X, Y), Pds, Envrn), exec(Y, exec(X, Pds, Envrn), Envrn)).
equal(exp(A, B), C) :- exp(A, B, C).
equal(fact_(I), fact_loop(I, 1)).
equal(falsify(X), falsify1(normalize(X), [])).
equal(fix(X), if(numberp(X), X, zero)).
equal(flatten(cdr(gopher(X))), if(listp(X), cdr(flatten(X)), cons(zero, []))).
equal(gcd(A, B), C) :- gcd(A, B, C).
equal(get(J, set(I, Val, Mem)), if(eqp(J, I), Val, get(J, Mem))).
equal(greatereqp(X, Y), not(lessp(X, Y))).
equal(greatereqpr(X, Y), not(lessp(X, Y))).
equal(greaterp(X, Y), lessp(Y, X)).
equal(if(if(A, B, C), D, E), if(A, if(B, D, E), if(C, D, E))).
equal(iff(X, Y), and(implies(X, Y), implies(Y, X))).
equal(implies(P, Q), if(P, if(Q, t, f), t)).
equal(last(append(A, B)), if(listp(B), last(B), if(listp(A), cons(car(last(A))), B))).
equal(length(A), B) :- mylength(A, B).
equal(lesseqp(X, Y), not(lessp(Y, X))).
equal(lessp(A, B), C) :- lessp(A, B, C).
equal(listp(gopher(X)), listp(X)).
equal(mc_flatten(X, Y), append(flatten(X), Y)).
equal(meaning(A, B), C) :- meaning(A, B, C).
equal(member(A, B), C) :- mymember(A, B, C).
equal(not(P), if(P, f, t)).
equal(nth(A, B), C) :- nth(A, B, C).
equal(numberp(greatest_factor(X, Y)), not(and(or(zerop(Y), equal(Y, 1)), not(numberp(X))))).
equal(or(P, Q), if(P, t, if(Q, t, f), f)).
equal(plus(A, B), C) :- plus(A, B, C).
equal(power_eval(A, B), C) :- power_eval(A, B, C).
equal(prime(X), and(not(zerop(X)), and(not(equal(X, add1(zero))), prime1(X, decr(X))))).
equal(prime_list(append(X, Y)), and(prime_list(X), prime_list(Y))).
equal(quotient(A, B), C) :- quotient(A, B, C).
equal(remainder(A, B), C) :- remainder(A, B, C).
equal(reverse_(X), reverse_loop(X, [])).
equal(reverse(append(A, B)), append(reverse(B), reverse(A))).
equal(reverse_loop(A, B), C) :- reverse_loop(A, B, C).
equal(samefringe(X, Y), equal(flatten(X), flatten(Y))).
equal(sigma(zero, I), quotient(times(I, add1(I)), 2)).
equal(sort2(delete(X, L)), delete(X, sort2(L))).
equal(tautology_checker(X), tautologyp(normalize(X), [])).
equal(times(A, B), C) :- times(A, B, C).
equal(times_list(append(X, Y)), times(times_list(X), times_list(Y))).
equal(value(normalize(X), A), value(X, A)).
equal(zerop(X), or(equal(X, zero), not(numberp(X)))).
difference(X, X, zero).
difference(plus(X, Y), X, fix(Y)).
difference(plus(Y, X), X, fix(Y)).
difference(plus(X, Y), plus(X, Z), difference(Y, Z)).
difference(plus(B, plus(A, C)), A, plus(B, C)).
difference(add1(plus(Y, Z)), Z, add1(Y)).
difference(add1(add1(X)), 2, fix(X)).
eq(plus(A, B), zero, and(zerop(A), zerop(B))).
eq(plus(A, B), plus(A, C), equal(fix(B), fix(C))).
eq(zero, difference(X, Y), not(lessp(Y, X))).
eq(X, difference(X, Y), and(numberp(X), and(or(equal(X, zero), zerop(Y))))).
eq(times(X, Y), zero, or(zerop(X), zerop(Y))).
eq(append(A, B), append(A, C), equal(B, C)).
eq(flatten(X), cons(Y, []), and(nlistp(X), equal(X, Y))).
eq(greatest_factor(X, Y), zero, and(or(zerop(Y), equal(Y, 1)), equal(X, zero))).
eq(greatest_factor(X, X8), 1, equal(X, 1)).
eq(Z, times(W, Z), and(numberp(Z), or(equal(Z, zero), equal(W, 1)))).
eq(X, times(X, Y), or(equal(X, zero), and(numberp(X), equal(Y, 1)))).
eq(times(A, B), 1, and(not(equal(A, zero)), and(not(equal(B, zero)), and(numberp(A), and(numberp(B), and(equal(decr(A), zero), equal(decr(B), zero))))))).
eq(difference(X, Y), difference(Z, Y), if(lessp(X, Y), not(lessp(Y, Z)), if(lessp(Z, Y), not(lessp(Y, X)), equal(fix(X), fix(Z))))).
eq(lessp(X, Y), Z, if(lessp(X, Y), equal(t, Z), equal(f, Z))).
exp(I, plus(J, K), times(exp(I, J), exp(I, K))).
exp(I, times(J, K), exp(exp(I, J), K)).
gcd(X, Y, gcd(Y, X)).
gcd(times(X, Z), times(Y, Z), times(Z, gcd(X, Y))).
mylength(reverse(X), length(X)).
mylength(cons(X9, cons(X10, cons(X11, cons(X12, cons(X13, cons(X14, X7)))))), plus(6, length(X7))).
lessp(remainder(X15, Y), Y, not(zerop(Y))).
lessp(quotient(I, J), I, and(not(zerop(I)), or(zerop(J), not(equal(J, 1))))).
lessp(remainder(X, Y), X, and(not(zerop(Y)), and(not(zerop(X)), not(lessp(X, Y))))).
lessp(plus(X, Y), plus(X, Z), lessp(Y, Z)).
lessp(times(X, Z), times(Y, Z), and(not(zerop(Z)), lessp(X, Y))).
lessp(Y, plus(X, Y), not(zerop(X))).
lessp(length(delete(X, L)), length(L), member(X, L)).
meaning(plus_tree(append(X, Y)), A, plus(meaning(plus_tree(X), A), meaning(plus_tree(Y), A))).
meaning(plus_tree(plus_fringe(X)), A, fix(meaning(X, A))).
meaning(plus_tree(delete(X, Y)), A, if(member(X, Y), difference(meaning(plus_tree(Y), A), meaning(X, A)), meaning(plus_tree(Y), A))).
mymember(X, append(A, B), or(member(X, A), member(X, B))).
mymember(X, reverse(Y), member(X, Y)).
mymember(A, intersect(B, C), and(member(A, B), member(A, C))).
nth(zero, X16, zero).
nth([], I, if(zerop(I), [], zero)).
nth(append(A, B), I, append(nth(A, I), nth(B, difference(I, length(A))))).
plus(plus(X, Y), Z, plus(X, plus(Y, Z))).
plus(remainder(X, Y), times(Y, quotient(X, Y)), fix(X)).
plus(X, add1(Y), if(numberp(Y), add1(plus(X, Y)), add1(X))).
power_eval(big_plus1(L, I, Base), Base, plus(power_eval(L, Base), I)).
power_eval(power_rep(I, Base), Base, fix(I)).
power_eval(big_plus(X, Y, I, Base), Base, plus(I, plus(power_eval(X, Base), power_eval(Y, Base)))).
power_eval(big_plus(power_rep(I, Base), power_rep(J, Base), zero, Base), Base, plus(I, J)).
quotient(plus(X, plus(X, Y)), 2, plus(X, quotient(Y, 2))).
quotient(times(Y, X), Y, if(zerop(Y), zero, fix(X))).
remainder(X17, 1, zero).
remainder(X, X, zero).
remainder(times(X18, Z), Z, zero).
remainder(times(Y, X19), Y, zero).
reverse_loop(X, Y, append(reverse(X), Y)).
reverse_loop(X, [], reverse(X)).
times(X, plus(Y, Z), plus(times(X, Y), times(X, Z))).
times(times(X, Y), Z, times(X, times(Y, Z))).
times(X, difference(C, W), difference(times(C, X), times(W, X))).
times(X, add1(Y), if(numberp(Y), plus(X, times(X, Y)), fix(X))).
go(T) :- ','(time(X20), ','(wff(X), ','(tautology(X), time(T)))).
time(T) :- statistics(runtime, .(X21, .(T, []))).
wff(implies(and(implies(X, Y), and(implies(Y, Z), and(implies(Z, U), implies(U, W)))), implies(X, W))) :- ','(=(X, f(plus(plus(a, b), plus(c, zero)))), ','(=(Y, f(times(times(a, b), plus(c, d)))), ','(=(Z, f(reverse(append(append(a, b), [])))), ','(=(U, equal(plus(a, b), difference(x, y))), =(W, lessp(remainder(a, b), member(a, length(b)))))))).
if1(Wff, Tlist, Flist) :- call1(Wff, Tlist).
if1(Wff, Tlist, Flist) :- if4(Wff, Flist).
if2(Wff, If, Then, Else, Tlist, Flist) :- ','(call2(Wff, If, Then, Else), if5(If, Tlist, Then, Flist, Else)).
if2(Wff, If, Then, Else, Tlist, Flist) :- ','(call2(Wff, If, Then, Else), ','(tautology(Then, .(If, Tlist), Flist), tautology(Else, Tlist, .(If, Flist)))).
if3(Mid, Next, New) :- ','(call3(Mid, Next), rewrite(Next, New)).
if3(Mid, Next, New) :- =(New, Mid).
if4(Wff, Flist) :- ','(call4(Wff, Flist), fail).
if5(If, Tlist, Then, Flist, Else) :- ','(call5(If, Tlist), tautology(Then, Tlist, Flist)).
if5(If, Tlist, Then, Flist, Else) :- if6(If, Flist, Else, Tlist).
if6(If, Flist, Else, Tlist) :- ','(call6(If, Flist), tautology(Else, Tlist, Flist)).
call1(Wff, Tlist) :- truep(Wff, Tlist).
call2(Wff, If, Then, Else) :- =(Wff, if(If, Then, Else)).
call3(Mid, Next) :- equal(Mid, Next).
call4(Wff, Flist) :- falsep(Wff, Flist).
call5(If, Tlist) :- truep(If, Tlist).
call6(If, Flist) :- falsep(If, Flist).
fail :- failure(a).
failure(b).
=(X, X).
write(X0).
nl.
atomic(X0).
functor(X0, X1, X2).
arg(X0, X1, X2).
is(X0, X1).
statistics(X0, X1).


Query: tautology(g)
----------------------------------------

(17) IntegerArithmeticTransformerProof (SOUND)
Added definitions of predefined predicates [PROLOG].
----------------------------------------

(18)
Obligation:
Clauses:

tautology(Wff) :- ','(write('rewriting...'), ','(nl, ','(rewrite(Wff, NewWff), ','(write('proving...'), ','(nl, tautology(NewWff, [], [])))))).
tautology(Wff, Tlist, Flist) :- ','(;(;(->(truep(Wff, Tlist), true), ->(falsep(Wff, Flist), fail)), ->(=(Wff, if(If, Then, Else)), ;(;(->(truep(If, Tlist), tautology(Then, Tlist, Flist)), ->(falsep(If, Flist), tautology(Else, Tlist, Flist))), ','(tautology(Then, .(If, Tlist), Flist), tautology(Else, Tlist, .(If, Flist)))))), !).
rewrite(Atom, Atom) :- ','(atomic(Atom), !).
rewrite(Old, New) :- ','(functor(Old, F, N), ','(functor(Mid, F, N), ','(rewrite_args(N, Old, Mid), ','(;(->(equal(Mid, Next), rewrite(Next, New)), =(New, Mid)), !)))).
rewrite_args(zero, X1, X2) :- !.
rewrite_args(N, Old, Mid) :- ','(arg(N, Old, OldArg), ','(arg(N, Mid, MidArg), ','(rewrite(OldArg, MidArg), ','(isMinus(N, succ(zero), U), ','(=(N1, U), rewrite_args(N1, Old, Mid)))))).
truep(t, X3) :- !.
truep(Wff, Tlist) :- member(Wff, Tlist).
falsep(f, X4) :- !.
falsep(Wff, Flist) :- member(Wff, Flist).
member(X, .(X, X5)) :- !.
member(X, .(X6, T)) :- member(X, T).
equal(and(P, Q), if(P, if(Q, t, f), f)).
equal(append(append(X, Y), Z), append(X, append(Y, Z))).
equal(assignment(X, append(A, B)), if(assignedp(X, A), assignment(X, A), assignment(X, B))).
equal(assume_false(Var, Alist), cons(cons(Var, f), Alist)).
equal(assume_true(Var, Alist), cons(cons(Var, t), Alist)).
equal(boolean(X), or(equal(X, t), equal(X, f))).
equal(car(gopher(X)), if(listp(X), car(flatten(X)), zero1)).
equal(compile(Form), reverse(codegen(optimize(Form), []))).
equal(count_list(Z, sort_lp(X, Y)), plus(count_list(Z, X), count_list(Z, Y))).
equal(countps_(L, Pred), countps_loop(L, Pred, zero1)).
equal(difference(A, B), C) :- difference(A, B, C).
equal(divides(X, Y), zerop(remainder(Y, X))).
equal(dsort(X), sort2(X)).
equal(eqp(X, Y), equal(fix(X), fix(Y))).
equal(equal(A, B), C) :- eq(A, B, C).
equal(even1(X), if(zerop(X), t, odd(decr(X)))).
equal(exec(append(X, Y), Pds, Envrn), exec(Y, exec(X, Pds, Envrn), Envrn)).
equal(exp(A, B), C) :- exp(A, B, C).
equal(fact_(I), fact_loop(I, succ(zero))).
equal(falsify(X), falsify1(normalize(X), [])).
equal(fix(X), if(numberp(X), X, zero1)).
equal(flatten(cdr(gopher(X))), if(listp(X), cdr(flatten(X)), cons(zero1, []))).
equal(gcd(A, B), C) :- gcd(A, B, C).
equal(get(J, set(I, Val, Mem)), if(eqp(J, I), Val, get(J, Mem))).
equal(greatereqp(X, Y), not(lessp(X, Y))).
equal(greatereqpr(X, Y), not(lessp(X, Y))).
equal(greaterp(X, Y), lessp(Y, X)).
equal(if(if(A, B, C), D, E), if(A, if(B, D, E), if(C, D, E))).
equal(iff(X, Y), and(implies(X, Y), implies(Y, X))).
equal(implies(P, Q), if(P, if(Q, t, f), t)).
equal(last(append(A, B)), if(listp(B), last(B), if(listp(A), cons(car(last(A))), B))).
equal(length(A), B) :- mylength(A, B).
equal(lesseqp(X, Y), not(lessp(Y, X))).
equal(lessp(A, B), C) :- lessp(A, B, C).
equal(listp(gopher(X)), listp(X)).
equal(mc_flatten(X, Y), append(flatten(X), Y)).
equal(meaning(A, B), C) :- meaning(A, B, C).
equal(member(A, B), C) :- mymember(A, B, C).
equal(not(P), if(P, f, t)).
equal(nth(A, B), C) :- nth(A, B, C).
equal(numberp(greatest_factor(X, Y)), not(and(or(zerop(Y), equal(Y, succ(zero))), not(numberp(X))))).
equal(or(P, Q), if(P, t, if(Q, t, f), f)).
equal(plus(A, B), C) :- plus(A, B, C).
equal(power_eval(A, B), C) :- power_eval(A, B, C).
equal(prime(X), and(not(zerop(X)), and(not(equal(X, add1(zero1))), prime1(X, decr(X))))).
equal(prime_list(append(X, Y)), and(prime_list(X), prime_list(Y))).
equal(quotient(A, B), C) :- quotient(A, B, C).
equal(remainder(A, B), C) :- remainder(A, B, C).
equal(reverse_(X), reverse_loop(X, [])).
equal(reverse(append(A, B)), append(reverse(B), reverse(A))).
equal(reverse_loop(A, B), C) :- reverse_loop(A, B, C).
equal(samefringe(X, Y), equal(flatten(X), flatten(Y))).
equal(sigma(zero1, I), quotient(times(I, add1(I)), succ(succ(zero)))).
equal(sort2(delete(X, L)), delete(X, sort2(L))).
equal(tautology_checker(X), tautologyp(normalize(X), [])).
equal(times(A, B), C) :- times(A, B, C).
equal(times_list(append(X, Y)), times(times_list(X), times_list(Y))).
equal(value(normalize(X), A), value(X, A)).
equal(zerop(X), or(equal(X, zero1), not(numberp(X)))).
difference(X, X, zero1) :- !.
difference(plus(X, Y), X, fix(Y)) :- !.
difference(plus(Y, X), X, fix(Y)) :- !.
difference(plus(X, Y), plus(X, Z), difference(Y, Z)) :- !.
difference(plus(B, plus(A, C)), A, plus(B, C)) :- !.
difference(add1(plus(Y, Z)), Z, add1(Y)) :- !.
difference(add1(add1(X)), succ(succ(zero)), fix(X)).
eq(plus(A, B), zero1, and(zerop(A), zerop(B))) :- !.
eq(plus(A, B), plus(A, C), equal(fix(B), fix(C))) :- !.
eq(zero1, difference(X, Y), not(lessp(Y, X))) :- !.
eq(X, difference(X, Y), and(numberp(X), and(or(equal(X, zero1), zerop(Y))))) :- !.
eq(times(X, Y), zero1, or(zerop(X), zerop(Y))) :- !.
eq(append(A, B), append(A, C), equal(B, C)) :- !.
eq(flatten(X), cons(Y, []), and(nlistp(X), equal(X, Y))) :- !.
eq(greatest_factor(X, Y), zero1, and(or(zerop(Y), equal(Y, succ(zero))), equal(X, zero1))) :- !.
eq(greatest_factor(X, X8), succ(zero), equal(X, succ(zero))) :- !.
eq(Z, times(W, Z), and(numberp(Z), or(equal(Z, zero1), equal(W, succ(zero))))) :- !.
eq(X, times(X, Y), or(equal(X, zero1), and(numberp(X), equal(Y, succ(zero))))) :- !.
eq(times(A, B), succ(zero), and(not(equal(A, zero1)), and(not(equal(B, zero1)), and(numberp(A), and(numberp(B), and(equal(decr(A), zero1), equal(decr(B), zero1))))))) :- !.
eq(difference(X, Y), difference(Z, Y), if(lessp(X, Y), not(lessp(Y, Z)), if(lessp(Z, Y), not(lessp(Y, X)), equal(fix(X), fix(Z))))) :- !.
eq(lessp(X, Y), Z, if(lessp(X, Y), equal(t, Z), equal(f, Z))).
exp(I, plus(J, K), times(exp(I, J), exp(I, K))) :- !.
exp(I, times(J, K), exp(exp(I, J), K)).
gcd(X, Y, gcd(Y, X)) :- !.
gcd(times(X, Z), times(Y, Z), times(Z, gcd(X, Y))).
mylength(reverse(X), length(X)).
mylength(cons(X9, cons(X10, cons(X11, cons(X12, cons(X13, cons(X14, X7)))))), plus(succ(succ(succ(succ(succ(succ(zero)))))), length(X7))).
lessp(remainder(X15, Y), Y, not(zerop(Y))) :- !.
lessp(quotient(I, J), I, and(not(zerop(I)), or(zerop(J), not(equal(J, succ(zero)))))) :- !.
lessp(remainder(X, Y), X, and(not(zerop(Y)), and(not(zerop(X)), not(lessp(X, Y))))) :- !.
lessp(plus(X, Y), plus(X, Z), lessp(Y, Z)) :- !.
lessp(times(X, Z), times(Y, Z), and(not(zerop(Z)), lessp(X, Y))) :- !.
lessp(Y, plus(X, Y), not(zerop(X))) :- !.
lessp(length(delete(X, L)), length(L), member(X, L)).
meaning(plus_tree(append(X, Y)), A, plus(meaning(plus_tree(X), A), meaning(plus_tree(Y), A))) :- !.
meaning(plus_tree(plus_fringe(X)), A, fix(meaning(X, A))) :- !.
meaning(plus_tree(delete(X, Y)), A, if(member(X, Y), difference(meaning(plus_tree(Y), A), meaning(X, A)), meaning(plus_tree(Y), A))).
mymember(X, append(A, B), or(member(X, A), member(X, B))) :- !.
mymember(X, reverse(Y), member(X, Y)) :- !.
mymember(A, intersect(B, C), and(member(A, B), member(A, C))).
nth(zero1, X16, zero1).
nth([], I, if(zerop(I), [], zero1)).
nth(append(A, B), I, append(nth(A, I), nth(B, difference(I, length(A))))).
plus(plus(X, Y), Z, plus(X, plus(Y, Z))) :- !.
plus(remainder(X, Y), times(Y, quotient(X, Y)), fix(X)) :- !.
plus(X, add1(Y), if(numberp(Y), add1(plus(X, Y)), add1(X))).
power_eval(big_plus1(L, I, Base), Base, plus(power_eval(L, Base), I)) :- !.
power_eval(power_rep(I, Base), Base, fix(I)) :- !.
power_eval(big_plus(X, Y, I, Base), Base, plus(I, plus(power_eval(X, Base), power_eval(Y, Base)))) :- !.
power_eval(big_plus(power_rep(I, Base), power_rep(J, Base), zero1, Base), Base, plus(I, J)).
quotient(plus(X, plus(X, Y)), succ(succ(zero)), plus(X, quotient(Y, succ(succ(zero))))).
quotient(times(Y, X), Y, if(zerop(Y), zero1, fix(X))).
remainder(X17, succ(zero), zero1) :- !.
remainder(X, X, zero1) :- !.
remainder(times(X18, Z), Z, zero1) :- !.
remainder(times(Y, X19), Y, zero1).
reverse_loop(X, Y, append(reverse(X), Y)) :- !.
reverse_loop(X, [], reverse(X)).
times(X, plus(Y, Z), plus(times(X, Y), times(X, Z))) :- !.
times(times(X, Y), Z, times(X, times(Y, Z))) :- !.
times(X, difference(C, W), difference(times(C, X), times(W, X))) :- !.
times(X, add1(Y), if(numberp(Y), plus(X, times(X, Y)), fix(X))).
go(T) :- ','(time(X20), ','(wff(X), ','(tautology(X), time(T)))).
time(T) :- statistics(runtime, .(X21, .(T, []))).
wff(implies(and(implies(X, Y), and(implies(Y, Z), and(implies(Z, U), implies(U, W)))), implies(X, W))) :- ','(=(X, f(plus(plus(a, b), plus(c, zero1)))), ','(=(Y, f(times(times(a, b), plus(c, d)))), ','(=(Z, f(reverse(append(append(a, b), [])))), ','(=(U, equal(plus(a, b), difference(x, y))), =(W, lessp(remainder(a, b), member(a, length(b)))))))).
isPlus(zero, X, X).
isPlus(succ(X), zero, succ(X)).
isPlus(succ(X), succ(Y), succ(succ(Z))) :- isPlus(X, Y, Z).
isPlus(succ(X), pred(Y), Z) :- isPlus(X, Y, Z).
isPlus(pred(X), zero, pred(X)).
isPlus(pred(X), succ(Y), Z) :- isPlus(X, Y, Z).
isPlus(pred(X), pred(Y), pred(pred(Z))) :- isPlus(X, Y, Z).
isMinus(X, zero, X).
isMinus(zero, succ(Y), pred(Z)) :- isMinus(zero, Y, Z).
isMinus(zero, pred(Y), succ(Z)) :- isMinus(zero, Y, Z).
isMinus(succ(X), succ(Y), Z) :- isMinus(X, Y, Z).
isMinus(succ(X), pred(Y), succ(succ(Z))) :- isMinus(X, Y, Z).
isMinus(pred(X), succ(Y), pred(pred(Z))) :- isMinus(X, Y, Z).
isMinus(pred(X), pred(Y), Z) :- isMinus(X, Y, Z).
isTimes(X, zero, zero).
isTimes(zero, succ(Y), zero).
isTimes(zero, pred(Y), zero).
isTimes(succ(X), succ(Y), Z) :- ','(isTimes(succ(X), Y, A), isPlus(A, succ(X), Z)).
isTimes(succ(X), pred(Y), Z) :- ','(isTimes(succ(X), Y, A), isMinus(A, succ(X), Z)).
isTimes(pred(X), succ(Y), Z) :- ','(isTimes(pred(X), Y, A), isPlus(A, pred(X), Z)).
isTimes(pred(X), pred(Y), Z) :- ','(isTimes(pred(X), Y, A), isMinus(A, pred(X), Z)).
isDiv(zero, succ(Y), zero).
isDiv(zero, pred(Y), zero).
isDiv(succ(X), succ(Y), zero) :- isMinus(succ(X), succ(Y), pred(Z)).
isDiv(succ(X), succ(Y), succ(Z)) :- ','(isMinus(succ(X), succ(Y), A), isDiv(A, succ(Y), Z)).
isDiv(succ(X), pred(Y), Z) :- ','(isMinus(zero, pred(Y), A), ','(isDiv(succ(X), A, B), isMinus(zero, B, Z))).
isDiv(pred(X), pred(Y), zero) :- isMinus(pred(X), pred(Y), succ(Z)).
isDiv(pred(X), pred(Y), succ(Z)) :- ','(isMinus(pred(X), pred(Y), A), isDiv(A, pred(Y), Z)).
isDiv(pred(X), succ(Y), Z) :- ','(isMinus(zero, pred(X), A), ','(isDiv(A, succ(Y), B), isMinus(zero, B, Z))).
isModulo(X, Y, Z) :- ','(isDiv(X, Y, A), ','(isTimes(A, Y, B), isMinus(X, B, Z))).


Query: tautology(g)
----------------------------------------

(19) CutEliminatorProof (SOUND)
Eliminated all cuts by simply ignoring them[PROLOG].
----------------------------------------

(20)
Obligation:
Clauses:

tautology(Wff) :- ','(write('rewriting...'), ','(nl, ','(rewrite(Wff, NewWff), ','(write('proving...'), ','(nl, tautology(NewWff, [], [])))))).
tautology(Wff, Tlist, Flist) :- ;(;(->(truep(Wff, Tlist), true), ->(falsep(Wff, Flist), fail)), ->(=(Wff, if(If, Then, Else)), ;(;(->(truep(If, Tlist), tautology(Then, Tlist, Flist)), ->(falsep(If, Flist), tautology(Else, Tlist, Flist))), ','(tautology(Then, .(If, Tlist), Flist), tautology(Else, Tlist, .(If, Flist)))))).
rewrite(Atom, Atom) :- atomic(Atom).
rewrite(Old, New) :- ','(functor(Old, F, N), ','(functor(Mid, F, N), ','(rewrite_args(N, Old, Mid), ;(->(equal(Mid, Next), rewrite(Next, New)), =(New, Mid))))).
rewrite_args(zero, X1, X2).
rewrite_args(N, Old, Mid) :- ','(arg(N, Old, OldArg), ','(arg(N, Mid, MidArg), ','(rewrite(OldArg, MidArg), ','(isMinus(N, succ(zero), U), ','(=(N1, U), rewrite_args(N1, Old, Mid)))))).
truep(t, X3).
truep(Wff, Tlist) :- member(Wff, Tlist).
falsep(f, X4).
falsep(Wff, Flist) :- member(Wff, Flist).
member(X, .(X, X5)).
member(X, .(X6, T)) :- member(X, T).
equal(and(P, Q), if(P, if(Q, t, f), f)).
equal(append(append(X, Y), Z), append(X, append(Y, Z))).
equal(assignment(X, append(A, B)), if(assignedp(X, A), assignment(X, A), assignment(X, B))).
equal(assume_false(Var, Alist), cons(cons(Var, f), Alist)).
equal(assume_true(Var, Alist), cons(cons(Var, t), Alist)).
equal(boolean(X), or(equal(X, t), equal(X, f))).
equal(car(gopher(X)), if(listp(X), car(flatten(X)), zero1)).
equal(compile(Form), reverse(codegen(optimize(Form), []))).
equal(count_list(Z, sort_lp(X, Y)), plus(count_list(Z, X), count_list(Z, Y))).
equal(countps_(L, Pred), countps_loop(L, Pred, zero1)).
equal(difference(A, B), C) :- difference(A, B, C).
equal(divides(X, Y), zerop(remainder(Y, X))).
equal(dsort(X), sort2(X)).
equal(eqp(X, Y), equal(fix(X), fix(Y))).
equal(equal(A, B), C) :- eq(A, B, C).
equal(even1(X), if(zerop(X), t, odd(decr(X)))).
equal(exec(append(X, Y), Pds, Envrn), exec(Y, exec(X, Pds, Envrn), Envrn)).
equal(exp(A, B), C) :- exp(A, B, C).
equal(fact_(I), fact_loop(I, succ(zero))).
equal(falsify(X), falsify1(normalize(X), [])).
equal(fix(X), if(numberp(X), X, zero1)).
equal(flatten(cdr(gopher(X))), if(listp(X), cdr(flatten(X)), cons(zero1, []))).
equal(gcd(A, B), C) :- gcd(A, B, C).
equal(get(J, set(I, Val, Mem)), if(eqp(J, I), Val, get(J, Mem))).
equal(greatereqp(X, Y), not(lessp(X, Y))).
equal(greatereqpr(X, Y), not(lessp(X, Y))).
equal(greaterp(X, Y), lessp(Y, X)).
equal(if(if(A, B, C), D, E), if(A, if(B, D, E), if(C, D, E))).
equal(iff(X, Y), and(implies(X, Y), implies(Y, X))).
equal(implies(P, Q), if(P, if(Q, t, f), t)).
equal(last(append(A, B)), if(listp(B), last(B), if(listp(A), cons(car(last(A))), B))).
equal(length(A), B) :- mylength(A, B).
equal(lesseqp(X, Y), not(lessp(Y, X))).
equal(lessp(A, B), C) :- lessp(A, B, C).
equal(listp(gopher(X)), listp(X)).
equal(mc_flatten(X, Y), append(flatten(X), Y)).
equal(meaning(A, B), C) :- meaning(A, B, C).
equal(member(A, B), C) :- mymember(A, B, C).
equal(not(P), if(P, f, t)).
equal(nth(A, B), C) :- nth(A, B, C).
equal(numberp(greatest_factor(X, Y)), not(and(or(zerop(Y), equal(Y, succ(zero))), not(numberp(X))))).
equal(or(P, Q), if(P, t, if(Q, t, f), f)).
equal(plus(A, B), C) :- plus(A, B, C).
equal(power_eval(A, B), C) :- power_eval(A, B, C).
equal(prime(X), and(not(zerop(X)), and(not(equal(X, add1(zero1))), prime1(X, decr(X))))).
equal(prime_list(append(X, Y)), and(prime_list(X), prime_list(Y))).
equal(quotient(A, B), C) :- quotient(A, B, C).
equal(remainder(A, B), C) :- remainder(A, B, C).
equal(reverse_(X), reverse_loop(X, [])).
equal(reverse(append(A, B)), append(reverse(B), reverse(A))).
equal(reverse_loop(A, B), C) :- reverse_loop(A, B, C).
equal(samefringe(X, Y), equal(flatten(X), flatten(Y))).
equal(sigma(zero1, I), quotient(times(I, add1(I)), succ(succ(zero)))).
equal(sort2(delete(X, L)), delete(X, sort2(L))).
equal(tautology_checker(X), tautologyp(normalize(X), [])).
equal(times(A, B), C) :- times(A, B, C).
equal(times_list(append(X, Y)), times(times_list(X), times_list(Y))).
equal(value(normalize(X), A), value(X, A)).
equal(zerop(X), or(equal(X, zero1), not(numberp(X)))).
difference(X, X, zero1).
difference(plus(X, Y), X, fix(Y)).
difference(plus(Y, X), X, fix(Y)).
difference(plus(X, Y), plus(X, Z), difference(Y, Z)).
difference(plus(B, plus(A, C)), A, plus(B, C)).
difference(add1(plus(Y, Z)), Z, add1(Y)).
difference(add1(add1(X)), succ(succ(zero)), fix(X)).
eq(plus(A, B), zero1, and(zerop(A), zerop(B))).
eq(plus(A, B), plus(A, C), equal(fix(B), fix(C))).
eq(zero1, difference(X, Y), not(lessp(Y, X))).
eq(X, difference(X, Y), and(numberp(X), and(or(equal(X, zero1), zerop(Y))))).
eq(times(X, Y), zero1, or(zerop(X), zerop(Y))).
eq(append(A, B), append(A, C), equal(B, C)).
eq(flatten(X), cons(Y, []), and(nlistp(X), equal(X, Y))).
eq(greatest_factor(X, Y), zero1, and(or(zerop(Y), equal(Y, succ(zero))), equal(X, zero1))).
eq(greatest_factor(X, X8), succ(zero), equal(X, succ(zero))).
eq(Z, times(W, Z), and(numberp(Z), or(equal(Z, zero1), equal(W, succ(zero))))).
eq(X, times(X, Y), or(equal(X, zero1), and(numberp(X), equal(Y, succ(zero))))).
eq(times(A, B), succ(zero), and(not(equal(A, zero1)), and(not(equal(B, zero1)), and(numberp(A), and(numberp(B), and(equal(decr(A), zero1), equal(decr(B), zero1))))))).
eq(difference(X, Y), difference(Z, Y), if(lessp(X, Y), not(lessp(Y, Z)), if(lessp(Z, Y), not(lessp(Y, X)), equal(fix(X), fix(Z))))).
eq(lessp(X, Y), Z, if(lessp(X, Y), equal(t, Z), equal(f, Z))).
exp(I, plus(J, K), times(exp(I, J), exp(I, K))).
exp(I, times(J, K), exp(exp(I, J), K)).
gcd(X, Y, gcd(Y, X)).
gcd(times(X, Z), times(Y, Z), times(Z, gcd(X, Y))).
mylength(reverse(X), length(X)).
mylength(cons(X9, cons(X10, cons(X11, cons(X12, cons(X13, cons(X14, X7)))))), plus(succ(succ(succ(succ(succ(succ(zero)))))), length(X7))).
lessp(remainder(X15, Y), Y, not(zerop(Y))).
lessp(quotient(I, J), I, and(not(zerop(I)), or(zerop(J), not(equal(J, succ(zero)))))).
lessp(remainder(X, Y), X, and(not(zerop(Y)), and(not(zerop(X)), not(lessp(X, Y))))).
lessp(plus(X, Y), plus(X, Z), lessp(Y, Z)).
lessp(times(X, Z), times(Y, Z), and(not(zerop(Z)), lessp(X, Y))).
lessp(Y, plus(X, Y), not(zerop(X))).
lessp(length(delete(X, L)), length(L), member(X, L)).
meaning(plus_tree(append(X, Y)), A, plus(meaning(plus_tree(X), A), meaning(plus_tree(Y), A))).
meaning(plus_tree(plus_fringe(X)), A, fix(meaning(X, A))).
meaning(plus_tree(delete(X, Y)), A, if(member(X, Y), difference(meaning(plus_tree(Y), A), meaning(X, A)), meaning(plus_tree(Y), A))).
mymember(X, append(A, B), or(member(X, A), member(X, B))).
mymember(X, reverse(Y), member(X, Y)).
mymember(A, intersect(B, C), and(member(A, B), member(A, C))).
nth(zero1, X16, zero1).
nth([], I, if(zerop(I), [], zero1)).
nth(append(A, B), I, append(nth(A, I), nth(B, difference(I, length(A))))).
plus(plus(X, Y), Z, plus(X, plus(Y, Z))).
plus(remainder(X, Y), times(Y, quotient(X, Y)), fix(X)).
plus(X, add1(Y), if(numberp(Y), add1(plus(X, Y)), add1(X))).
power_eval(big_plus1(L, I, Base), Base, plus(power_eval(L, Base), I)).
power_eval(power_rep(I, Base), Base, fix(I)).
power_eval(big_plus(X, Y, I, Base), Base, plus(I, plus(power_eval(X, Base), power_eval(Y, Base)))).
power_eval(big_plus(power_rep(I, Base), power_rep(J, Base), zero1, Base), Base, plus(I, J)).
quotient(plus(X, plus(X, Y)), succ(succ(zero)), plus(X, quotient(Y, succ(succ(zero))))).
quotient(times(Y, X), Y, if(zerop(Y), zero1, fix(X))).
remainder(X17, succ(zero), zero1).
remainder(X, X, zero1).
remainder(times(X18, Z), Z, zero1).
remainder(times(Y, X19), Y, zero1).
reverse_loop(X, Y, append(reverse(X), Y)).
reverse_loop(X, [], reverse(X)).
times(X, plus(Y, Z), plus(times(X, Y), times(X, Z))).
times(times(X, Y), Z, times(X, times(Y, Z))).
times(X, difference(C, W), difference(times(C, X), times(W, X))).
times(X, add1(Y), if(numberp(Y), plus(X, times(X, Y)), fix(X))).
go(T) :- ','(time(X20), ','(wff(X), ','(tautology(X), time(T)))).
time(T) :- statistics(runtime, .(X21, .(T, []))).
wff(implies(and(implies(X, Y), and(implies(Y, Z), and(implies(Z, U), implies(U, W)))), implies(X, W))) :- ','(=(X, f(plus(plus(a, b), plus(c, zero1)))), ','(=(Y, f(times(times(a, b), plus(c, d)))), ','(=(Z, f(reverse(append(append(a, b), [])))), ','(=(U, equal(plus(a, b), difference(x, y))), =(W, lessp(remainder(a, b), member(a, length(b)))))))).
isPlus(zero, X, X).
isPlus(succ(X), zero, succ(X)).
isPlus(succ(X), succ(Y), succ(succ(Z))) :- isPlus(X, Y, Z).
isPlus(succ(X), pred(Y), Z) :- isPlus(X, Y, Z).
isPlus(pred(X), zero, pred(X)).
isPlus(pred(X), succ(Y), Z) :- isPlus(X, Y, Z).
isPlus(pred(X), pred(Y), pred(pred(Z))) :- isPlus(X, Y, Z).
isMinus(X, zero, X).
isMinus(zero, succ(Y), pred(Z)) :- isMinus(zero, Y, Z).
isMinus(zero, pred(Y), succ(Z)) :- isMinus(zero, Y, Z).
isMinus(succ(X), succ(Y), Z) :- isMinus(X, Y, Z).
isMinus(succ(X), pred(Y), succ(succ(Z))) :- isMinus(X, Y, Z).
isMinus(pred(X), succ(Y), pred(pred(Z))) :- isMinus(X, Y, Z).
isMinus(pred(X), pred(Y), Z) :- isMinus(X, Y, Z).
isTimes(X, zero, zero).
isTimes(zero, succ(Y), zero).
isTimes(zero, pred(Y), zero).
isTimes(succ(X), succ(Y), Z) :- ','(isTimes(succ(X), Y, A), isPlus(A, succ(X), Z)).
isTimes(succ(X), pred(Y), Z) :- ','(isTimes(succ(X), Y, A), isMinus(A, succ(X), Z)).
isTimes(pred(X), succ(Y), Z) :- ','(isTimes(pred(X), Y, A), isPlus(A, pred(X), Z)).
isTimes(pred(X), pred(Y), Z) :- ','(isTimes(pred(X), Y, A), isMinus(A, pred(X), Z)).
isDiv(zero, succ(Y), zero).
isDiv(zero, pred(Y), zero).
isDiv(succ(X), succ(Y), zero) :- isMinus(succ(X), succ(Y), pred(Z)).
isDiv(succ(X), succ(Y), succ(Z)) :- ','(isMinus(succ(X), succ(Y), A), isDiv(A, succ(Y), Z)).
isDiv(succ(X), pred(Y), Z) :- ','(isMinus(zero, pred(Y), A), ','(isDiv(succ(X), A, B), isMinus(zero, B, Z))).
isDiv(pred(X), pred(Y), zero) :- isMinus(pred(X), pred(Y), succ(Z)).
isDiv(pred(X), pred(Y), succ(Z)) :- ','(isMinus(pred(X), pred(Y), A), isDiv(A, pred(Y), Z)).
isDiv(pred(X), succ(Y), Z) :- ','(isMinus(zero, pred(X), A), ','(isDiv(A, succ(Y), B), isMinus(zero, B, Z))).
isModulo(X, Y, Z) :- ','(isDiv(X, Y, A), ','(isTimes(A, Y, B), isMinus(X, B, Z))).


Query: tautology(g)
----------------------------------------

(21) IfThenElseTransformerProof (EQUIVALENT)
Transformed all if-then-else-constructs [PROLOG].
----------------------------------------

(22)
Obligation:
Clauses:

tautology(Wff) :- ','(write('rewriting...'), ','(nl, ','(rewrite(Wff, NewWff), ','(write('proving...'), ','(nl, tautology(NewWff, [], [])))))).
tautology(Wff, Tlist, Flist) :- ;(if1(Wff, Tlist, Flist), if2(Wff, If, Then, Else, Tlist, Flist)).
rewrite(Atom, Atom) :- atomic(Atom).
rewrite(Old, New) :- ','(functor(Old, F, N), ','(functor(Mid, F, N), ','(rewrite_args(N, Old, Mid), if3(Mid, Next, New)))).
rewrite_args(zero, X1, X2).
rewrite_args(N, Old, Mid) :- ','(arg(N, Old, OldArg), ','(arg(N, Mid, MidArg), ','(rewrite(OldArg, MidArg), ','(isMinus(N, succ(zero), U), ','(=(N1, U), rewrite_args(N1, Old, Mid)))))).
truep(t, X3).
truep(Wff, Tlist) :- member(Wff, Tlist).
falsep(f, X4).
falsep(Wff, Flist) :- member(Wff, Flist).
member(X, .(X, X5)).
member(X, .(X6, T)) :- member(X, T).
equal(and(P, Q), if(P, if(Q, t, f), f)).
equal(append(append(X, Y), Z), append(X, append(Y, Z))).
equal(assignment(X, append(A, B)), if(assignedp(X, A), assignment(X, A), assignment(X, B))).
equal(assume_false(Var, Alist), cons(cons(Var, f), Alist)).
equal(assume_true(Var, Alist), cons(cons(Var, t), Alist)).
equal(boolean(X), or(equal(X, t), equal(X, f))).
equal(car(gopher(X)), if(listp(X), car(flatten(X)), zero1)).
equal(compile(Form), reverse(codegen(optimize(Form), []))).
equal(count_list(Z, sort_lp(X, Y)), plus(count_list(Z, X), count_list(Z, Y))).
equal(countps_(L, Pred), countps_loop(L, Pred, zero1)).
equal(difference(A, B), C) :- difference(A, B, C).
equal(divides(X, Y), zerop(remainder(Y, X))).
equal(dsort(X), sort2(X)).
equal(eqp(X, Y), equal(fix(X), fix(Y))).
equal(equal(A, B), C) :- eq(A, B, C).
equal(even1(X), if(zerop(X), t, odd(decr(X)))).
equal(exec(append(X, Y), Pds, Envrn), exec(Y, exec(X, Pds, Envrn), Envrn)).
equal(exp(A, B), C) :- exp(A, B, C).
equal(fact_(I), fact_loop(I, succ(zero))).
equal(falsify(X), falsify1(normalize(X), [])).
equal(fix(X), if(numberp(X), X, zero1)).
equal(flatten(cdr(gopher(X))), if(listp(X), cdr(flatten(X)), cons(zero1, []))).
equal(gcd(A, B), C) :- gcd(A, B, C).
equal(get(J, set(I, Val, Mem)), if(eqp(J, I), Val, get(J, Mem))).
equal(greatereqp(X, Y), not(lessp(X, Y))).
equal(greatereqpr(X, Y), not(lessp(X, Y))).
equal(greaterp(X, Y), lessp(Y, X)).
equal(if(if(A, B, C), D, E), if(A, if(B, D, E), if(C, D, E))).
equal(iff(X, Y), and(implies(X, Y), implies(Y, X))).
equal(implies(P, Q), if(P, if(Q, t, f), t)).
equal(last(append(A, B)), if(listp(B), last(B), if(listp(A), cons(car(last(A))), B))).
equal(length(A), B) :- mylength(A, B).
equal(lesseqp(X, Y), not(lessp(Y, X))).
equal(lessp(A, B), C) :- lessp(A, B, C).
equal(listp(gopher(X)), listp(X)).
equal(mc_flatten(X, Y), append(flatten(X), Y)).
equal(meaning(A, B), C) :- meaning(A, B, C).
equal(member(A, B), C) :- mymember(A, B, C).
equal(not(P), if(P, f, t)).
equal(nth(A, B), C) :- nth(A, B, C).
equal(numberp(greatest_factor(X, Y)), not(and(or(zerop(Y), equal(Y, succ(zero))), not(numberp(X))))).
equal(or(P, Q), if(P, t, if(Q, t, f), f)).
equal(plus(A, B), C) :- plus(A, B, C).
equal(power_eval(A, B), C) :- power_eval(A, B, C).
equal(prime(X), and(not(zerop(X)), and(not(equal(X, add1(zero1))), prime1(X, decr(X))))).
equal(prime_list(append(X, Y)), and(prime_list(X), prime_list(Y))).
equal(quotient(A, B), C) :- quotient(A, B, C).
equal(remainder(A, B), C) :- remainder(A, B, C).
equal(reverse_(X), reverse_loop(X, [])).
equal(reverse(append(A, B)), append(reverse(B), reverse(A))).
equal(reverse_loop(A, B), C) :- reverse_loop(A, B, C).
equal(samefringe(X, Y), equal(flatten(X), flatten(Y))).
equal(sigma(zero1, I), quotient(times(I, add1(I)), succ(succ(zero)))).
equal(sort2(delete(X, L)), delete(X, sort2(L))).
equal(tautology_checker(X), tautologyp(normalize(X), [])).
equal(times(A, B), C) :- times(A, B, C).
equal(times_list(append(X, Y)), times(times_list(X), times_list(Y))).
equal(value(normalize(X), A), value(X, A)).
equal(zerop(X), or(equal(X, zero1), not(numberp(X)))).
difference(X, X, zero1).
difference(plus(X, Y), X, fix(Y)).
difference(plus(Y, X), X, fix(Y)).
difference(plus(X, Y), plus(X, Z), difference(Y, Z)).
difference(plus(B, plus(A, C)), A, plus(B, C)).
difference(add1(plus(Y, Z)), Z, add1(Y)).
difference(add1(add1(X)), succ(succ(zero)), fix(X)).
eq(plus(A, B), zero1, and(zerop(A), zerop(B))).
eq(plus(A, B), plus(A, C), equal(fix(B), fix(C))).
eq(zero1, difference(X, Y), not(lessp(Y, X))).
eq(X, difference(X, Y), and(numberp(X), and(or(equal(X, zero1), zerop(Y))))).
eq(times(X, Y), zero1, or(zerop(X), zerop(Y))).
eq(append(A, B), append(A, C), equal(B, C)).
eq(flatten(X), cons(Y, []), and(nlistp(X), equal(X, Y))).
eq(greatest_factor(X, Y), zero1, and(or(zerop(Y), equal(Y, succ(zero))), equal(X, zero1))).
eq(greatest_factor(X, X8), succ(zero), equal(X, succ(zero))).
eq(Z, times(W, Z), and(numberp(Z), or(equal(Z, zero1), equal(W, succ(zero))))).
eq(X, times(X, Y), or(equal(X, zero1), and(numberp(X), equal(Y, succ(zero))))).
eq(times(A, B), succ(zero), and(not(equal(A, zero1)), and(not(equal(B, zero1)), and(numberp(A), and(numberp(B), and(equal(decr(A), zero1), equal(decr(B), zero1))))))).
eq(difference(X, Y), difference(Z, Y), if(lessp(X, Y), not(lessp(Y, Z)), if(lessp(Z, Y), not(lessp(Y, X)), equal(fix(X), fix(Z))))).
eq(lessp(X, Y), Z, if(lessp(X, Y), equal(t, Z), equal(f, Z))).
exp(I, plus(J, K), times(exp(I, J), exp(I, K))).
exp(I, times(J, K), exp(exp(I, J), K)).
gcd(X, Y, gcd(Y, X)).
gcd(times(X, Z), times(Y, Z), times(Z, gcd(X, Y))).
mylength(reverse(X), length(X)).
mylength(cons(X9, cons(X10, cons(X11, cons(X12, cons(X13, cons(X14, X7)))))), plus(succ(succ(succ(succ(succ(succ(zero)))))), length(X7))).
lessp(remainder(X15, Y), Y, not(zerop(Y))).
lessp(quotient(I, J), I, and(not(zerop(I)), or(zerop(J), not(equal(J, succ(zero)))))).
lessp(remainder(X, Y), X, and(not(zerop(Y)), and(not(zerop(X)), not(lessp(X, Y))))).
lessp(plus(X, Y), plus(X, Z), lessp(Y, Z)).
lessp(times(X, Z), times(Y, Z), and(not(zerop(Z)), lessp(X, Y))).
lessp(Y, plus(X, Y), not(zerop(X))).
lessp(length(delete(X, L)), length(L), member(X, L)).
meaning(plus_tree(append(X, Y)), A, plus(meaning(plus_tree(X), A), meaning(plus_tree(Y), A))).
meaning(plus_tree(plus_fringe(X)), A, fix(meaning(X, A))).
meaning(plus_tree(delete(X, Y)), A, if(member(X, Y), difference(meaning(plus_tree(Y), A), meaning(X, A)), meaning(plus_tree(Y), A))).
mymember(X, append(A, B), or(member(X, A), member(X, B))).
mymember(X, reverse(Y), member(X, Y)).
mymember(A, intersect(B, C), and(member(A, B), member(A, C))).
nth(zero1, X16, zero1).
nth([], I, if(zerop(I), [], zero1)).
nth(append(A, B), I, append(nth(A, I), nth(B, difference(I, length(A))))).
plus(plus(X, Y), Z, plus(X, plus(Y, Z))).
plus(remainder(X, Y), times(Y, quotient(X, Y)), fix(X)).
plus(X, add1(Y), if(numberp(Y), add1(plus(X, Y)), add1(X))).
power_eval(big_plus1(L, I, Base), Base, plus(power_eval(L, Base), I)).
power_eval(power_rep(I, Base), Base, fix(I)).
power_eval(big_plus(X, Y, I, Base), Base, plus(I, plus(power_eval(X, Base), power_eval(Y, Base)))).
power_eval(big_plus(power_rep(I, Base), power_rep(J, Base), zero1, Base), Base, plus(I, J)).
quotient(plus(X, plus(X, Y)), succ(succ(zero)), plus(X, quotient(Y, succ(succ(zero))))).
quotient(times(Y, X), Y, if(zerop(Y), zero1, fix(X))).
remainder(X17, succ(zero), zero1).
remainder(X, X, zero1).
remainder(times(X18, Z), Z, zero1).
remainder(times(Y, X19), Y, zero1).
reverse_loop(X, Y, append(reverse(X), Y)).
reverse_loop(X, [], reverse(X)).
times(X, plus(Y, Z), plus(times(X, Y), times(X, Z))).
times(times(X, Y), Z, times(X, times(Y, Z))).
times(X, difference(C, W), difference(times(C, X), times(W, X))).
times(X, add1(Y), if(numberp(Y), plus(X, times(X, Y)), fix(X))).
go(T) :- ','(time(X20), ','(wff(X), ','(tautology(X), time(T)))).
time(T) :- statistics(runtime, .(X21, .(T, []))).
wff(implies(and(implies(X, Y), and(implies(Y, Z), and(implies(Z, U), implies(U, W)))), implies(X, W))) :- ','(=(X, f(plus(plus(a, b), plus(c, zero1)))), ','(=(Y, f(times(times(a, b), plus(c, d)))), ','(=(Z, f(reverse(append(append(a, b), [])))), ','(=(U, equal(plus(a, b), difference(x, y))), =(W, lessp(remainder(a, b), member(a, length(b)))))))).
isPlus(zero, X, X).
isPlus(succ(X), zero, succ(X)).
isPlus(succ(X), succ(Y), succ(succ(Z))) :- isPlus(X, Y, Z).
isPlus(succ(X), pred(Y), Z) :- isPlus(X, Y, Z).
isPlus(pred(X), zero, pred(X)).
isPlus(pred(X), succ(Y), Z) :- isPlus(X, Y, Z).
isPlus(pred(X), pred(Y), pred(pred(Z))) :- isPlus(X, Y, Z).
isMinus(X, zero, X).
isMinus(zero, succ(Y), pred(Z)) :- isMinus(zero, Y, Z).
isMinus(zero, pred(Y), succ(Z)) :- isMinus(zero, Y, Z).
isMinus(succ(X), succ(Y), Z) :- isMinus(X, Y, Z).
isMinus(succ(X), pred(Y), succ(succ(Z))) :- isMinus(X, Y, Z).
isMinus(pred(X), succ(Y), pred(pred(Z))) :- isMinus(X, Y, Z).
isMinus(pred(X), pred(Y), Z) :- isMinus(X, Y, Z).
isTimes(X, zero, zero).
isTimes(zero, succ(Y), zero).
isTimes(zero, pred(Y), zero).
isTimes(succ(X), succ(Y), Z) :- ','(isTimes(succ(X), Y, A), isPlus(A, succ(X), Z)).
isTimes(succ(X), pred(Y), Z) :- ','(isTimes(succ(X), Y, A), isMinus(A, succ(X), Z)).
isTimes(pred(X), succ(Y), Z) :- ','(isTimes(pred(X), Y, A), isPlus(A, pred(X), Z)).
isTimes(pred(X), pred(Y), Z) :- ','(isTimes(pred(X), Y, A), isMinus(A, pred(X), Z)).
isDiv(zero, succ(Y), zero).
isDiv(zero, pred(Y), zero).
isDiv(succ(X), succ(Y), zero) :- isMinus(succ(X), succ(Y), pred(Z)).
isDiv(succ(X), succ(Y), succ(Z)) :- ','(isMinus(succ(X), succ(Y), A), isDiv(A, succ(Y), Z)).
isDiv(succ(X), pred(Y), Z) :- ','(isMinus(zero, pred(Y), A), ','(isDiv(succ(X), A, B), isMinus(zero, B, Z))).
isDiv(pred(X), pred(Y), zero) :- isMinus(pred(X), pred(Y), succ(Z)).
isDiv(pred(X), pred(Y), succ(Z)) :- ','(isMinus(pred(X), pred(Y), A), isDiv(A, pred(Y), Z)).
isDiv(pred(X), succ(Y), Z) :- ','(isMinus(zero, pred(X), A), ','(isDiv(A, succ(Y), B), isMinus(zero, B, Z))).
isModulo(X, Y, Z) :- ','(isDiv(X, Y, A), ','(isTimes(A, Y, B), isMinus(X, B, Z))).
if1(Wff, Tlist, Flist) :- ','(call(truep(Wff, Tlist)), ','(!, true)).
if1(Wff, Tlist, Flist) :- if4(Wff, Flist).
if2(Wff, If, Then, Else, Tlist, Flist) :- ','(call(=(Wff, if(If, Then, Else))), ','(!, ;(if5(If, Tlist, Then, Flist, Else), ','(tautology(Then, .(If, Tlist), Flist), tautology(Else, Tlist, .(If, Flist)))))).
if3(Mid, Next, New) :- ','(call(equal(Mid, Next)), ','(!, rewrite(Next, New))).
if3(Mid, Next, New) :- =(New, Mid).
if4(Wff, Flist) :- ','(call(falsep(Wff, Flist)), ','(!, fail)).
if5(If, Tlist, Then, Flist, Else) :- ','(call(truep(If, Tlist)), ','(!, tautology(Then, Tlist, Flist))).
if5(If, Tlist, Then, Flist, Else) :- if6(If, Flist, Else, Tlist).
if6(If, Flist, Else, Tlist) :- ','(call(falsep(If, Flist)), ','(!, tautology(Else, Tlist, Flist))).


Query: tautology(g)
----------------------------------------

(23) CallTransformerProof (EQUIVALENT)
Transformed all call-constructs [PROLOG].
----------------------------------------

(24)
Obligation:
Clauses:

tautology(Wff) :- ','(write('rewriting...'), ','(nl, ','(rewrite(Wff, NewWff), ','(write('proving...'), ','(nl, tautology(NewWff, [], [])))))).
tautology(Wff, Tlist, Flist) :- ;(if1(Wff, Tlist, Flist), if2(Wff, If, Then, Else, Tlist, Flist)).
rewrite(Atom, Atom) :- atomic(Atom).
rewrite(Old, New) :- ','(functor(Old, F, N), ','(functor(Mid, F, N), ','(rewrite_args(N, Old, Mid), if3(Mid, Next, New)))).
rewrite_args(zero, X1, X2).
rewrite_args(N, Old, Mid) :- ','(arg(N, Old, OldArg), ','(arg(N, Mid, MidArg), ','(rewrite(OldArg, MidArg), ','(isMinus(N, succ(zero), U), ','(=(N1, U), rewrite_args(N1, Old, Mid)))))).
truep(t, X3).
truep(Wff, Tlist) :- member(Wff, Tlist).
falsep(f, X4).
falsep(Wff, Flist) :- member(Wff, Flist).
member(X, .(X, X5)).
member(X, .(X6, T)) :- member(X, T).
equal(and(P, Q), if(P, if(Q, t, f), f)).
equal(append(append(X, Y), Z), append(X, append(Y, Z))).
equal(assignment(X, append(A, B)), if(assignedp(X, A), assignment(X, A), assignment(X, B))).
equal(assume_false(Var, Alist), cons(cons(Var, f), Alist)).
equal(assume_true(Var, Alist), cons(cons(Var, t), Alist)).
equal(boolean(X), or(equal(X, t), equal(X, f))).
equal(car(gopher(X)), if(listp(X), car(flatten(X)), zero1)).
equal(compile(Form), reverse(codegen(optimize(Form), []))).
equal(count_list(Z, sort_lp(X, Y)), plus(count_list(Z, X), count_list(Z, Y))).
equal(countps_(L, Pred), countps_loop(L, Pred, zero1)).
equal(difference(A, B), C) :- difference(A, B, C).
equal(divides(X, Y), zerop(remainder(Y, X))).
equal(dsort(X), sort2(X)).
equal(eqp(X, Y), equal(fix(X), fix(Y))).
equal(equal(A, B), C) :- eq(A, B, C).
equal(even1(X), if(zerop(X), t, odd(decr(X)))).
equal(exec(append(X, Y), Pds, Envrn), exec(Y, exec(X, Pds, Envrn), Envrn)).
equal(exp(A, B), C) :- exp(A, B, C).
equal(fact_(I), fact_loop(I, succ(zero))).
equal(falsify(X), falsify1(normalize(X), [])).
equal(fix(X), if(numberp(X), X, zero1)).
equal(flatten(cdr(gopher(X))), if(listp(X), cdr(flatten(X)), cons(zero1, []))).
equal(gcd(A, B), C) :- gcd(A, B, C).
equal(get(J, set(I, Val, Mem)), if(eqp(J, I), Val, get(J, Mem))).
equal(greatereqp(X, Y), not(lessp(X, Y))).
equal(greatereqpr(X, Y), not(lessp(X, Y))).
equal(greaterp(X, Y), lessp(Y, X)).
equal(if(if(A, B, C), D, E), if(A, if(B, D, E), if(C, D, E))).
equal(iff(X, Y), and(implies(X, Y), implies(Y, X))).
equal(implies(P, Q), if(P, if(Q, t, f), t)).
equal(last(append(A, B)), if(listp(B), last(B), if(listp(A), cons(car(last(A))), B))).
equal(length(A), B) :- mylength(A, B).
equal(lesseqp(X, Y), not(lessp(Y, X))).
equal(lessp(A, B), C) :- lessp(A, B, C).
equal(listp(gopher(X)), listp(X)).
equal(mc_flatten(X, Y), append(flatten(X), Y)).
equal(meaning(A, B), C) :- meaning(A, B, C).
equal(member(A, B), C) :- mymember(A, B, C).
equal(not(P), if(P, f, t)).
equal(nth(A, B), C) :- nth(A, B, C).
equal(numberp(greatest_factor(X, Y)), not(and(or(zerop(Y), equal(Y, succ(zero))), not(numberp(X))))).
equal(or(P, Q), if(P, t, if(Q, t, f), f)).
equal(plus(A, B), C) :- plus(A, B, C).
equal(power_eval(A, B), C) :- power_eval(A, B, C).
equal(prime(X), and(not(zerop(X)), and(not(equal(X, add1(zero1))), prime1(X, decr(X))))).
equal(prime_list(append(X, Y)), and(prime_list(X), prime_list(Y))).
equal(quotient(A, B), C) :- quotient(A, B, C).
equal(remainder(A, B), C) :- remainder(A, B, C).
equal(reverse_(X), reverse_loop(X, [])).
equal(reverse(append(A, B)), append(reverse(B), reverse(A))).
equal(reverse_loop(A, B), C) :- reverse_loop(A, B, C).
equal(samefringe(X, Y), equal(flatten(X), flatten(Y))).
equal(sigma(zero1, I), quotient(times(I, add1(I)), succ(succ(zero)))).
equal(sort2(delete(X, L)), delete(X, sort2(L))).
equal(tautology_checker(X), tautologyp(normalize(X), [])).
equal(times(A, B), C) :- times(A, B, C).
equal(times_list(append(X, Y)), times(times_list(X), times_list(Y))).
equal(value(normalize(X), A), value(X, A)).
equal(zerop(X), or(equal(X, zero1), not(numberp(X)))).
difference(X, X, zero1).
difference(plus(X, Y), X, fix(Y)).
difference(plus(Y, X), X, fix(Y)).
difference(plus(X, Y), plus(X, Z), difference(Y, Z)).
difference(plus(B, plus(A, C)), A, plus(B, C)).
difference(add1(plus(Y, Z)), Z, add1(Y)).
difference(add1(add1(X)), succ(succ(zero)), fix(X)).
eq(plus(A, B), zero1, and(zerop(A), zerop(B))).
eq(plus(A, B), plus(A, C), equal(fix(B), fix(C))).
eq(zero1, difference(X, Y), not(lessp(Y, X))).
eq(X, difference(X, Y), and(numberp(X), and(or(equal(X, zero1), zerop(Y))))).
eq(times(X, Y), zero1, or(zerop(X), zerop(Y))).
eq(append(A, B), append(A, C), equal(B, C)).
eq(flatten(X), cons(Y, []), and(nlistp(X), equal(X, Y))).
eq(greatest_factor(X, Y), zero1, and(or(zerop(Y), equal(Y, succ(zero))), equal(X, zero1))).
eq(greatest_factor(X, X8), succ(zero), equal(X, succ(zero))).
eq(Z, times(W, Z), and(numberp(Z), or(equal(Z, zero1), equal(W, succ(zero))))).
eq(X, times(X, Y), or(equal(X, zero1), and(numberp(X), equal(Y, succ(zero))))).
eq(times(A, B), succ(zero), and(not(equal(A, zero1)), and(not(equal(B, zero1)), and(numberp(A), and(numberp(B), and(equal(decr(A), zero1), equal(decr(B), zero1))))))).
eq(difference(X, Y), difference(Z, Y), if(lessp(X, Y), not(lessp(Y, Z)), if(lessp(Z, Y), not(lessp(Y, X)), equal(fix(X), fix(Z))))).
eq(lessp(X, Y), Z, if(lessp(X, Y), equal(t, Z), equal(f, Z))).
exp(I, plus(J, K), times(exp(I, J), exp(I, K))).
exp(I, times(J, K), exp(exp(I, J), K)).
gcd(X, Y, gcd(Y, X)).
gcd(times(X, Z), times(Y, Z), times(Z, gcd(X, Y))).
mylength(reverse(X), length(X)).
mylength(cons(X9, cons(X10, cons(X11, cons(X12, cons(X13, cons(X14, X7)))))), plus(succ(succ(succ(succ(succ(succ(zero)))))), length(X7))).
lessp(remainder(X15, Y), Y, not(zerop(Y))).
lessp(quotient(I, J), I, and(not(zerop(I)), or(zerop(J), not(equal(J, succ(zero)))))).
lessp(remainder(X, Y), X, and(not(zerop(Y)), and(not(zerop(X)), not(lessp(X, Y))))).
lessp(plus(X, Y), plus(X, Z), lessp(Y, Z)).
lessp(times(X, Z), times(Y, Z), and(not(zerop(Z)), lessp(X, Y))).
lessp(Y, plus(X, Y), not(zerop(X))).
lessp(length(delete(X, L)), length(L), member(X, L)).
meaning(plus_tree(append(X, Y)), A, plus(meaning(plus_tree(X), A), meaning(plus_tree(Y), A))).
meaning(plus_tree(plus_fringe(X)), A, fix(meaning(X, A))).
meaning(plus_tree(delete(X, Y)), A, if(member(X, Y), difference(meaning(plus_tree(Y), A), meaning(X, A)), meaning(plus_tree(Y), A))).
mymember(X, append(A, B), or(member(X, A), member(X, B))).
mymember(X, reverse(Y), member(X, Y)).
mymember(A, intersect(B, C), and(member(A, B), member(A, C))).
nth(zero1, X16, zero1).
nth([], I, if(zerop(I), [], zero1)).
nth(append(A, B), I, append(nth(A, I), nth(B, difference(I, length(A))))).
plus(plus(X, Y), Z, plus(X, plus(Y, Z))).
plus(remainder(X, Y), times(Y, quotient(X, Y)), fix(X)).
plus(X, add1(Y), if(numberp(Y), add1(plus(X, Y)), add1(X))).
power_eval(big_plus1(L, I, Base), Base, plus(power_eval(L, Base), I)).
power_eval(power_rep(I, Base), Base, fix(I)).
power_eval(big_plus(X, Y, I, Base), Base, plus(I, plus(power_eval(X, Base), power_eval(Y, Base)))).
power_eval(big_plus(power_rep(I, Base), power_rep(J, Base), zero1, Base), Base, plus(I, J)).
quotient(plus(X, plus(X, Y)), succ(succ(zero)), plus(X, quotient(Y, succ(succ(zero))))).
quotient(times(Y, X), Y, if(zerop(Y), zero1, fix(X))).
remainder(X17, succ(zero), zero1).
remainder(X, X, zero1).
remainder(times(X18, Z), Z, zero1).
remainder(times(Y, X19), Y, zero1).
reverse_loop(X, Y, append(reverse(X), Y)).
reverse_loop(X, [], reverse(X)).
times(X, plus(Y, Z), plus(times(X, Y), times(X, Z))).
times(times(X, Y), Z, times(X, times(Y, Z))).
times(X, difference(C, W), difference(times(C, X), times(W, X))).
times(X, add1(Y), if(numberp(Y), plus(X, times(X, Y)), fix(X))).
go(T) :- ','(time(X20), ','(wff(X), ','(tautology(X), time(T)))).
time(T) :- statistics(runtime, .(X21, .(T, []))).
wff(implies(and(implies(X, Y), and(implies(Y, Z), and(implies(Z, U), implies(U, W)))), implies(X, W))) :- ','(=(X, f(plus(plus(a, b), plus(c, zero1)))), ','(=(Y, f(times(times(a, b), plus(c, d)))), ','(=(Z, f(reverse(append(append(a, b), [])))), ','(=(U, equal(plus(a, b), difference(x, y))), =(W, lessp(remainder(a, b), member(a, length(b)))))))).
isPlus(zero, X, X).
isPlus(succ(X), zero, succ(X)).
isPlus(succ(X), succ(Y), succ(succ(Z))) :- isPlus(X, Y, Z).
isPlus(succ(X), pred(Y), Z) :- isPlus(X, Y, Z).
isPlus(pred(X), zero, pred(X)).
isPlus(pred(X), succ(Y), Z) :- isPlus(X, Y, Z).
isPlus(pred(X), pred(Y), pred(pred(Z))) :- isPlus(X, Y, Z).
isMinus(X, zero, X).
isMinus(zero, succ(Y), pred(Z)) :- isMinus(zero, Y, Z).
isMinus(zero, pred(Y), succ(Z)) :- isMinus(zero, Y, Z).
isMinus(succ(X), succ(Y), Z) :- isMinus(X, Y, Z).
isMinus(succ(X), pred(Y), succ(succ(Z))) :- isMinus(X, Y, Z).
isMinus(pred(X), succ(Y), pred(pred(Z))) :- isMinus(X, Y, Z).
isMinus(pred(X), pred(Y), Z) :- isMinus(X, Y, Z).
isTimes(X, zero, zero).
isTimes(zero, succ(Y), zero).
isTimes(zero, pred(Y), zero).
isTimes(succ(X), succ(Y), Z) :- ','(isTimes(succ(X), Y, A), isPlus(A, succ(X), Z)).
isTimes(succ(X), pred(Y), Z) :- ','(isTimes(succ(X), Y, A), isMinus(A, succ(X), Z)).
isTimes(pred(X), succ(Y), Z) :- ','(isTimes(pred(X), Y, A), isPlus(A, pred(X), Z)).
isTimes(pred(X), pred(Y), Z) :- ','(isTimes(pred(X), Y, A), isMinus(A, pred(X), Z)).
isDiv(zero, succ(Y), zero).
isDiv(zero, pred(Y), zero).
isDiv(succ(X), succ(Y), zero) :- isMinus(succ(X), succ(Y), pred(Z)).
isDiv(succ(X), succ(Y), succ(Z)) :- ','(isMinus(succ(X), succ(Y), A), isDiv(A, succ(Y), Z)).
isDiv(succ(X), pred(Y), Z) :- ','(isMinus(zero, pred(Y), A), ','(isDiv(succ(X), A, B), isMinus(zero, B, Z))).
isDiv(pred(X), pred(Y), zero) :- isMinus(pred(X), pred(Y), succ(Z)).
isDiv(pred(X), pred(Y), succ(Z)) :- ','(isMinus(pred(X), pred(Y), A), isDiv(A, pred(Y), Z)).
isDiv(pred(X), succ(Y), Z) :- ','(isMinus(zero, pred(X), A), ','(isDiv(A, succ(Y), B), isMinus(zero, B, Z))).
isModulo(X, Y, Z) :- ','(isDiv(X, Y, A), ','(isTimes(A, Y, B), isMinus(X, B, Z))).
if1(Wff, Tlist, Flist) :- ','(call1(Wff, Tlist), ','(!, true)).
if1(Wff, Tlist, Flist) :- if4(Wff, Flist).
if2(Wff, If, Then, Else, Tlist, Flist) :- ','(call2(Wff, If, Then, Else), ','(!, ;(if5(If, Tlist, Then, Flist, Else), ','(tautology(Then, .(If, Tlist), Flist), tautology(Else, Tlist, .(If, Flist)))))).
if3(Mid, Next, New) :- ','(call3(Mid, Next), ','(!, rewrite(Next, New))).
if3(Mid, Next, New) :- =(New, Mid).
if4(Wff, Flist) :- ','(call4(Wff, Flist), ','(!, fail)).
if5(If, Tlist, Then, Flist, Else) :- ','(call5(If, Tlist), ','(!, tautology(Then, Tlist, Flist))).
if5(If, Tlist, Then, Flist, Else) :- if6(If, Flist, Else, Tlist).
if6(If, Flist, Else, Tlist) :- ','(call6(If, Flist), ','(!, tautology(Else, Tlist, Flist))).
call1(Wff, Tlist) :- truep(Wff, Tlist).
call2(Wff, If, Then, Else) :- =(Wff, if(If, Then, Else)).
call3(Mid, Next) :- equal(Mid, Next).
call4(Wff, Flist) :- falsep(Wff, Flist).
call5(If, Tlist) :- truep(If, Tlist).
call6(If, Flist) :- falsep(If, Flist).


Query: tautology(g)
----------------------------------------

(25) CutEliminatorProof (SOUND)
Eliminated all cuts by simply ignoring them[PROLOG].
----------------------------------------

(26)
Obligation:
Clauses:

tautology(Wff) :- ','(write('rewriting...'), ','(nl, ','(rewrite(Wff, NewWff), ','(write('proving...'), ','(nl, tautology(NewWff, [], [])))))).
tautology(Wff, Tlist, Flist) :- ;(if1(Wff, Tlist, Flist), if2(Wff, If, Then, Else, Tlist, Flist)).
rewrite(Atom, Atom) :- atomic(Atom).
rewrite(Old, New) :- ','(functor(Old, F, N), ','(functor(Mid, F, N), ','(rewrite_args(N, Old, Mid), if3(Mid, Next, New)))).
rewrite_args(zero, X1, X2).
rewrite_args(N, Old, Mid) :- ','(arg(N, Old, OldArg), ','(arg(N, Mid, MidArg), ','(rewrite(OldArg, MidArg), ','(isMinus(N, succ(zero), U), ','(=(N1, U), rewrite_args(N1, Old, Mid)))))).
truep(t, X3).
truep(Wff, Tlist) :- member(Wff, Tlist).
falsep(f, X4).
falsep(Wff, Flist) :- member(Wff, Flist).
member(X, .(X, X5)).
member(X, .(X6, T)) :- member(X, T).
equal(and(P, Q), if(P, if(Q, t, f), f)).
equal(append(append(X, Y), Z), append(X, append(Y, Z))).
equal(assignment(X, append(A, B)), if(assignedp(X, A), assignment(X, A), assignment(X, B))).
equal(assume_false(Var, Alist), cons(cons(Var, f), Alist)).
equal(assume_true(Var, Alist), cons(cons(Var, t), Alist)).
equal(boolean(X), or(equal(X, t), equal(X, f))).
equal(car(gopher(X)), if(listp(X), car(flatten(X)), zero1)).
equal(compile(Form), reverse(codegen(optimize(Form), []))).
equal(count_list(Z, sort_lp(X, Y)), plus(count_list(Z, X), count_list(Z, Y))).
equal(countps_(L, Pred), countps_loop(L, Pred, zero1)).
equal(difference(A, B), C) :- difference(A, B, C).
equal(divides(X, Y), zerop(remainder(Y, X))).
equal(dsort(X), sort2(X)).
equal(eqp(X, Y), equal(fix(X), fix(Y))).
equal(equal(A, B), C) :- eq(A, B, C).
equal(even1(X), if(zerop(X), t, odd(decr(X)))).
equal(exec(append(X, Y), Pds, Envrn), exec(Y, exec(X, Pds, Envrn), Envrn)).
equal(exp(A, B), C) :- exp(A, B, C).
equal(fact_(I), fact_loop(I, succ(zero))).
equal(falsify(X), falsify1(normalize(X), [])).
equal(fix(X), if(numberp(X), X, zero1)).
equal(flatten(cdr(gopher(X))), if(listp(X), cdr(flatten(X)), cons(zero1, []))).
equal(gcd(A, B), C) :- gcd(A, B, C).
equal(get(J, set(I, Val, Mem)), if(eqp(J, I), Val, get(J, Mem))).
equal(greatereqp(X, Y), not(lessp(X, Y))).
equal(greatereqpr(X, Y), not(lessp(X, Y))).
equal(greaterp(X, Y), lessp(Y, X)).
equal(if(if(A, B, C), D, E), if(A, if(B, D, E), if(C, D, E))).
equal(iff(X, Y), and(implies(X, Y), implies(Y, X))).
equal(implies(P, Q), if(P, if(Q, t, f), t)).
equal(last(append(A, B)), if(listp(B), last(B), if(listp(A), cons(car(last(A))), B))).
equal(length(A), B) :- mylength(A, B).
equal(lesseqp(X, Y), not(lessp(Y, X))).
equal(lessp(A, B), C) :- lessp(A, B, C).
equal(listp(gopher(X)), listp(X)).
equal(mc_flatten(X, Y), append(flatten(X), Y)).
equal(meaning(A, B), C) :- meaning(A, B, C).
equal(member(A, B), C) :- mymember(A, B, C).
equal(not(P), if(P, f, t)).
equal(nth(A, B), C) :- nth(A, B, C).
equal(numberp(greatest_factor(X, Y)), not(and(or(zerop(Y), equal(Y, succ(zero))), not(numberp(X))))).
equal(or(P, Q), if(P, t, if(Q, t, f), f)).
equal(plus(A, B), C) :- plus(A, B, C).
equal(power_eval(A, B), C) :- power_eval(A, B, C).
equal(prime(X), and(not(zerop(X)), and(not(equal(X, add1(zero1))), prime1(X, decr(X))))).
equal(prime_list(append(X, Y)), and(prime_list(X), prime_list(Y))).
equal(quotient(A, B), C) :- quotient(A, B, C).
equal(remainder(A, B), C) :- remainder(A, B, C).
equal(reverse_(X), reverse_loop(X, [])).
equal(reverse(append(A, B)), append(reverse(B), reverse(A))).
equal(reverse_loop(A, B), C) :- reverse_loop(A, B, C).
equal(samefringe(X, Y), equal(flatten(X), flatten(Y))).
equal(sigma(zero1, I), quotient(times(I, add1(I)), succ(succ(zero)))).
equal(sort2(delete(X, L)), delete(X, sort2(L))).
equal(tautology_checker(X), tautologyp(normalize(X), [])).
equal(times(A, B), C) :- times(A, B, C).
equal(times_list(append(X, Y)), times(times_list(X), times_list(Y))).
equal(value(normalize(X), A), value(X, A)).
equal(zerop(X), or(equal(X, zero1), not(numberp(X)))).
difference(X, X, zero1).
difference(plus(X, Y), X, fix(Y)).
difference(plus(Y, X), X, fix(Y)).
difference(plus(X, Y), plus(X, Z), difference(Y, Z)).
difference(plus(B, plus(A, C)), A, plus(B, C)).
difference(add1(plus(Y, Z)), Z, add1(Y)).
difference(add1(add1(X)), succ(succ(zero)), fix(X)).
eq(plus(A, B), zero1, and(zerop(A), zerop(B))).
eq(plus(A, B), plus(A, C), equal(fix(B), fix(C))).
eq(zero1, difference(X, Y), not(lessp(Y, X))).
eq(X, difference(X, Y), and(numberp(X), and(or(equal(X, zero1), zerop(Y))))).
eq(times(X, Y), zero1, or(zerop(X), zerop(Y))).
eq(append(A, B), append(A, C), equal(B, C)).
eq(flatten(X), cons(Y, []), and(nlistp(X), equal(X, Y))).
eq(greatest_factor(X, Y), zero1, and(or(zerop(Y), equal(Y, succ(zero))), equal(X, zero1))).
eq(greatest_factor(X, X8), succ(zero), equal(X, succ(zero))).
eq(Z, times(W, Z), and(numberp(Z), or(equal(Z, zero1), equal(W, succ(zero))))).
eq(X, times(X, Y), or(equal(X, zero1), and(numberp(X), equal(Y, succ(zero))))).
eq(times(A, B), succ(zero), and(not(equal(A, zero1)), and(not(equal(B, zero1)), and(numberp(A), and(numberp(B), and(equal(decr(A), zero1), equal(decr(B), zero1))))))).
eq(difference(X, Y), difference(Z, Y), if(lessp(X, Y), not(lessp(Y, Z)), if(lessp(Z, Y), not(lessp(Y, X)), equal(fix(X), fix(Z))))).
eq(lessp(X, Y), Z, if(lessp(X, Y), equal(t, Z), equal(f, Z))).
exp(I, plus(J, K), times(exp(I, J), exp(I, K))).
exp(I, times(J, K), exp(exp(I, J), K)).
gcd(X, Y, gcd(Y, X)).
gcd(times(X, Z), times(Y, Z), times(Z, gcd(X, Y))).
mylength(reverse(X), length(X)).
mylength(cons(X9, cons(X10, cons(X11, cons(X12, cons(X13, cons(X14, X7)))))), plus(succ(succ(succ(succ(succ(succ(zero)))))), length(X7))).
lessp(remainder(X15, Y), Y, not(zerop(Y))).
lessp(quotient(I, J), I, and(not(zerop(I)), or(zerop(J), not(equal(J, succ(zero)))))).
lessp(remainder(X, Y), X, and(not(zerop(Y)), and(not(zerop(X)), not(lessp(X, Y))))).
lessp(plus(X, Y), plus(X, Z), lessp(Y, Z)).
lessp(times(X, Z), times(Y, Z), and(not(zerop(Z)), lessp(X, Y))).
lessp(Y, plus(X, Y), not(zerop(X))).
lessp(length(delete(X, L)), length(L), member(X, L)).
meaning(plus_tree(append(X, Y)), A, plus(meaning(plus_tree(X), A), meaning(plus_tree(Y), A))).
meaning(plus_tree(plus_fringe(X)), A, fix(meaning(X, A))).
meaning(plus_tree(delete(X, Y)), A, if(member(X, Y), difference(meaning(plus_tree(Y), A), meaning(X, A)), meaning(plus_tree(Y), A))).
mymember(X, append(A, B), or(member(X, A), member(X, B))).
mymember(X, reverse(Y), member(X, Y)).
mymember(A, intersect(B, C), and(member(A, B), member(A, C))).
nth(zero1, X16, zero1).
nth([], I, if(zerop(I), [], zero1)).
nth(append(A, B), I, append(nth(A, I), nth(B, difference(I, length(A))))).
plus(plus(X, Y), Z, plus(X, plus(Y, Z))).
plus(remainder(X, Y), times(Y, quotient(X, Y)), fix(X)).
plus(X, add1(Y), if(numberp(Y), add1(plus(X, Y)), add1(X))).
power_eval(big_plus1(L, I, Base), Base, plus(power_eval(L, Base), I)).
power_eval(power_rep(I, Base), Base, fix(I)).
power_eval(big_plus(X, Y, I, Base), Base, plus(I, plus(power_eval(X, Base), power_eval(Y, Base)))).
power_eval(big_plus(power_rep(I, Base), power_rep(J, Base), zero1, Base), Base, plus(I, J)).
quotient(plus(X, plus(X, Y)), succ(succ(zero)), plus(X, quotient(Y, succ(succ(zero))))).
quotient(times(Y, X), Y, if(zerop(Y), zero1, fix(X))).
remainder(X17, succ(zero), zero1).
remainder(X, X, zero1).
remainder(times(X18, Z), Z, zero1).
remainder(times(Y, X19), Y, zero1).
reverse_loop(X, Y, append(reverse(X), Y)).
reverse_loop(X, [], reverse(X)).
times(X, plus(Y, Z), plus(times(X, Y), times(X, Z))).
times(times(X, Y), Z, times(X, times(Y, Z))).
times(X, difference(C, W), difference(times(C, X), times(W, X))).
times(X, add1(Y), if(numberp(Y), plus(X, times(X, Y)), fix(X))).
go(T) :- ','(time(X20), ','(wff(X), ','(tautology(X), time(T)))).
time(T) :- statistics(runtime, .(X21, .(T, []))).
wff(implies(and(implies(X, Y), and(implies(Y, Z), and(implies(Z, U), implies(U, W)))), implies(X, W))) :- ','(=(X, f(plus(plus(a, b), plus(c, zero1)))), ','(=(Y, f(times(times(a, b), plus(c, d)))), ','(=(Z, f(reverse(append(append(a, b), [])))), ','(=(U, equal(plus(a, b), difference(x, y))), =(W, lessp(remainder(a, b), member(a, length(b)))))))).
isPlus(zero, X, X).
isPlus(succ(X), zero, succ(X)).
isPlus(succ(X), succ(Y), succ(succ(Z))) :- isPlus(X, Y, Z).
isPlus(succ(X), pred(Y), Z) :- isPlus(X, Y, Z).
isPlus(pred(X), zero, pred(X)).
isPlus(pred(X), succ(Y), Z) :- isPlus(X, Y, Z).
isPlus(pred(X), pred(Y), pred(pred(Z))) :- isPlus(X, Y, Z).
isMinus(X, zero, X).
isMinus(zero, succ(Y), pred(Z)) :- isMinus(zero, Y, Z).
isMinus(zero, pred(Y), succ(Z)) :- isMinus(zero, Y, Z).
isMinus(succ(X), succ(Y), Z) :- isMinus(X, Y, Z).
isMinus(succ(X), pred(Y), succ(succ(Z))) :- isMinus(X, Y, Z).
isMinus(pred(X), succ(Y), pred(pred(Z))) :- isMinus(X, Y, Z).
isMinus(pred(X), pred(Y), Z) :- isMinus(X, Y, Z).
isTimes(X, zero, zero).
isTimes(zero, succ(Y), zero).
isTimes(zero, pred(Y), zero).
isTimes(succ(X), succ(Y), Z) :- ','(isTimes(succ(X), Y, A), isPlus(A, succ(X), Z)).
isTimes(succ(X), pred(Y), Z) :- ','(isTimes(succ(X), Y, A), isMinus(A, succ(X), Z)).
isTimes(pred(X), succ(Y), Z) :- ','(isTimes(pred(X), Y, A), isPlus(A, pred(X), Z)).
isTimes(pred(X), pred(Y), Z) :- ','(isTimes(pred(X), Y, A), isMinus(A, pred(X), Z)).
isDiv(zero, succ(Y), zero).
isDiv(zero, pred(Y), zero).
isDiv(succ(X), succ(Y), zero) :- isMinus(succ(X), succ(Y), pred(Z)).
isDiv(succ(X), succ(Y), succ(Z)) :- ','(isMinus(succ(X), succ(Y), A), isDiv(A, succ(Y), Z)).
isDiv(succ(X), pred(Y), Z) :- ','(isMinus(zero, pred(Y), A), ','(isDiv(succ(X), A, B), isMinus(zero, B, Z))).
isDiv(pred(X), pred(Y), zero) :- isMinus(pred(X), pred(Y), succ(Z)).
isDiv(pred(X), pred(Y), succ(Z)) :- ','(isMinus(pred(X), pred(Y), A), isDiv(A, pred(Y), Z)).
isDiv(pred(X), succ(Y), Z) :- ','(isMinus(zero, pred(X), A), ','(isDiv(A, succ(Y), B), isMinus(zero, B, Z))).
isModulo(X, Y, Z) :- ','(isDiv(X, Y, A), ','(isTimes(A, Y, B), isMinus(X, B, Z))).
if1(Wff, Tlist, Flist) :- call1(Wff, Tlist).
if1(Wff, Tlist, Flist) :- if4(Wff, Flist).
if2(Wff, If, Then, Else, Tlist, Flist) :- ','(call2(Wff, If, Then, Else), ;(if5(If, Tlist, Then, Flist, Else), ','(tautology(Then, .(If, Tlist), Flist), tautology(Else, Tlist, .(If, Flist))))).
if3(Mid, Next, New) :- ','(call3(Mid, Next), rewrite(Next, New)).
if3(Mid, Next, New) :- =(New, Mid).
if4(Wff, Flist) :- ','(call4(Wff, Flist), fail).
if5(If, Tlist, Then, Flist, Else) :- ','(call5(If, Tlist), tautology(Then, Tlist, Flist)).
if5(If, Tlist, Then, Flist, Else) :- if6(If, Flist, Else, Tlist).
if6(If, Flist, Else, Tlist) :- ','(call6(If, Flist), tautology(Else, Tlist, Flist)).
call1(Wff, Tlist) :- truep(Wff, Tlist).
call2(Wff, If, Then, Else) :- =(Wff, if(If, Then, Else)).
call3(Mid, Next) :- equal(Mid, Next).
call4(Wff, Flist) :- falsep(Wff, Flist).
call5(If, Tlist) :- truep(If, Tlist).
call6(If, Flist) :- falsep(If, Flist).


Query: tautology(g)
----------------------------------------

(27) FailTransformerProof (EQUIVALENT)
Added clauses for the built-in fail predicate [PROLOG].
----------------------------------------

(28)
Obligation:
Clauses:

tautology(Wff) :- ','(write('rewriting...'), ','(nl, ','(rewrite(Wff, NewWff), ','(write('proving...'), ','(nl, tautology(NewWff, [], [])))))).
tautology(Wff, Tlist, Flist) :- ;(if1(Wff, Tlist, Flist), if2(Wff, If, Then, Else, Tlist, Flist)).
rewrite(Atom, Atom) :- atomic(Atom).
rewrite(Old, New) :- ','(functor(Old, F, N), ','(functor(Mid, F, N), ','(rewrite_args(N, Old, Mid), if3(Mid, Next, New)))).
rewrite_args(zero, X1, X2).
rewrite_args(N, Old, Mid) :- ','(arg(N, Old, OldArg), ','(arg(N, Mid, MidArg), ','(rewrite(OldArg, MidArg), ','(isMinus(N, succ(zero), U), ','(=(N1, U), rewrite_args(N1, Old, Mid)))))).
truep(t, X3).
truep(Wff, Tlist) :- member(Wff, Tlist).
falsep(f, X4).
falsep(Wff, Flist) :- member(Wff, Flist).
member(X, .(X, X5)).
member(X, .(X6, T)) :- member(X, T).
equal(and(P, Q), if(P, if(Q, t, f), f)).
equal(append(append(X, Y), Z), append(X, append(Y, Z))).
equal(assignment(X, append(A, B)), if(assignedp(X, A), assignment(X, A), assignment(X, B))).
equal(assume_false(Var, Alist), cons(cons(Var, f), Alist)).
equal(assume_true(Var, Alist), cons(cons(Var, t), Alist)).
equal(boolean(X), or(equal(X, t), equal(X, f))).
equal(car(gopher(X)), if(listp(X), car(flatten(X)), zero1)).
equal(compile(Form), reverse(codegen(optimize(Form), []))).
equal(count_list(Z, sort_lp(X, Y)), plus(count_list(Z, X), count_list(Z, Y))).
equal(countps_(L, Pred), countps_loop(L, Pred, zero1)).
equal(difference(A, B), C) :- difference(A, B, C).
equal(divides(X, Y), zerop(remainder(Y, X))).
equal(dsort(X), sort2(X)).
equal(eqp(X, Y), equal(fix(X), fix(Y))).
equal(equal(A, B), C) :- eq(A, B, C).
equal(even1(X), if(zerop(X), t, odd(decr(X)))).
equal(exec(append(X, Y), Pds, Envrn), exec(Y, exec(X, Pds, Envrn), Envrn)).
equal(exp(A, B), C) :- exp(A, B, C).
equal(fact_(I), fact_loop(I, succ(zero))).
equal(falsify(X), falsify1(normalize(X), [])).
equal(fix(X), if(numberp(X), X, zero1)).
equal(flatten(cdr(gopher(X))), if(listp(X), cdr(flatten(X)), cons(zero1, []))).
equal(gcd(A, B), C) :- gcd(A, B, C).
equal(get(J, set(I, Val, Mem)), if(eqp(J, I), Val, get(J, Mem))).
equal(greatereqp(X, Y), not(lessp(X, Y))).
equal(greatereqpr(X, Y), not(lessp(X, Y))).
equal(greaterp(X, Y), lessp(Y, X)).
equal(if(if(A, B, C), D, E), if(A, if(B, D, E), if(C, D, E))).
equal(iff(X, Y), and(implies(X, Y), implies(Y, X))).
equal(implies(P, Q), if(P, if(Q, t, f), t)).
equal(last(append(A, B)), if(listp(B), last(B), if(listp(A), cons(car(last(A))), B))).
equal(length(A), B) :- mylength(A, B).
equal(lesseqp(X, Y), not(lessp(Y, X))).
equal(lessp(A, B), C) :- lessp(A, B, C).
equal(listp(gopher(X)), listp(X)).
equal(mc_flatten(X, Y), append(flatten(X), Y)).
equal(meaning(A, B), C) :- meaning(A, B, C).
equal(member(A, B), C) :- mymember(A, B, C).
equal(not(P), if(P, f, t)).
equal(nth(A, B), C) :- nth(A, B, C).
equal(numberp(greatest_factor(X, Y)), not(and(or(zerop(Y), equal(Y, succ(zero))), not(numberp(X))))).
equal(or(P, Q), if(P, t, if(Q, t, f), f)).
equal(plus(A, B), C) :- plus(A, B, C).
equal(power_eval(A, B), C) :- power_eval(A, B, C).
equal(prime(X), and(not(zerop(X)), and(not(equal(X, add1(zero1))), prime1(X, decr(X))))).
equal(prime_list(append(X, Y)), and(prime_list(X), prime_list(Y))).
equal(quotient(A, B), C) :- quotient(A, B, C).
equal(remainder(A, B), C) :- remainder(A, B, C).
equal(reverse_(X), reverse_loop(X, [])).
equal(reverse(append(A, B)), append(reverse(B), reverse(A))).
equal(reverse_loop(A, B), C) :- reverse_loop(A, B, C).
equal(samefringe(X, Y), equal(flatten(X), flatten(Y))).
equal(sigma(zero1, I), quotient(times(I, add1(I)), succ(succ(zero)))).
equal(sort2(delete(X, L)), delete(X, sort2(L))).
equal(tautology_checker(X), tautologyp(normalize(X), [])).
equal(times(A, B), C) :- times(A, B, C).
equal(times_list(append(X, Y)), times(times_list(X), times_list(Y))).
equal(value(normalize(X), A), value(X, A)).
equal(zerop(X), or(equal(X, zero1), not(numberp(X)))).
difference(X, X, zero1).
difference(plus(X, Y), X, fix(Y)).
difference(plus(Y, X), X, fix(Y)).
difference(plus(X, Y), plus(X, Z), difference(Y, Z)).
difference(plus(B, plus(A, C)), A, plus(B, C)).
difference(add1(plus(Y, Z)), Z, add1(Y)).
difference(add1(add1(X)), succ(succ(zero)), fix(X)).
eq(plus(A, B), zero1, and(zerop(A), zerop(B))).
eq(plus(A, B), plus(A, C), equal(fix(B), fix(C))).
eq(zero1, difference(X, Y), not(lessp(Y, X))).
eq(X, difference(X, Y), and(numberp(X), and(or(equal(X, zero1), zerop(Y))))).
eq(times(X, Y), zero1, or(zerop(X), zerop(Y))).
eq(append(A, B), append(A, C), equal(B, C)).
eq(flatten(X), cons(Y, []), and(nlistp(X), equal(X, Y))).
eq(greatest_factor(X, Y), zero1, and(or(zerop(Y), equal(Y, succ(zero))), equal(X, zero1))).
eq(greatest_factor(X, X8), succ(zero), equal(X, succ(zero))).
eq(Z, times(W, Z), and(numberp(Z), or(equal(Z, zero1), equal(W, succ(zero))))).
eq(X, times(X, Y), or(equal(X, zero1), and(numberp(X), equal(Y, succ(zero))))).
eq(times(A, B), succ(zero), and(not(equal(A, zero1)), and(not(equal(B, zero1)), and(numberp(A), and(numberp(B), and(equal(decr(A), zero1), equal(decr(B), zero1))))))).
eq(difference(X, Y), difference(Z, Y), if(lessp(X, Y), not(lessp(Y, Z)), if(lessp(Z, Y), not(lessp(Y, X)), equal(fix(X), fix(Z))))).
eq(lessp(X, Y), Z, if(lessp(X, Y), equal(t, Z), equal(f, Z))).
exp(I, plus(J, K), times(exp(I, J), exp(I, K))).
exp(I, times(J, K), exp(exp(I, J), K)).
gcd(X, Y, gcd(Y, X)).
gcd(times(X, Z), times(Y, Z), times(Z, gcd(X, Y))).
mylength(reverse(X), length(X)).
mylength(cons(X9, cons(X10, cons(X11, cons(X12, cons(X13, cons(X14, X7)))))), plus(succ(succ(succ(succ(succ(succ(zero)))))), length(X7))).
lessp(remainder(X15, Y), Y, not(zerop(Y))).
lessp(quotient(I, J), I, and(not(zerop(I)), or(zerop(J), not(equal(J, succ(zero)))))).
lessp(remainder(X, Y), X, and(not(zerop(Y)), and(not(zerop(X)), not(lessp(X, Y))))).
lessp(plus(X, Y), plus(X, Z), lessp(Y, Z)).
lessp(times(X, Z), times(Y, Z), and(not(zerop(Z)), lessp(X, Y))).
lessp(Y, plus(X, Y), not(zerop(X))).
lessp(length(delete(X, L)), length(L), member(X, L)).
meaning(plus_tree(append(X, Y)), A, plus(meaning(plus_tree(X), A), meaning(plus_tree(Y), A))).
meaning(plus_tree(plus_fringe(X)), A, fix(meaning(X, A))).
meaning(plus_tree(delete(X, Y)), A, if(member(X, Y), difference(meaning(plus_tree(Y), A), meaning(X, A)), meaning(plus_tree(Y), A))).
mymember(X, append(A, B), or(member(X, A), member(X, B))).
mymember(X, reverse(Y), member(X, Y)).
mymember(A, intersect(B, C), and(member(A, B), member(A, C))).
nth(zero1, X16, zero1).
nth([], I, if(zerop(I), [], zero1)).
nth(append(A, B), I, append(nth(A, I), nth(B, difference(I, length(A))))).
plus(plus(X, Y), Z, plus(X, plus(Y, Z))).
plus(remainder(X, Y), times(Y, quotient(X, Y)), fix(X)).
plus(X, add1(Y), if(numberp(Y), add1(plus(X, Y)), add1(X))).
power_eval(big_plus1(L, I, Base), Base, plus(power_eval(L, Base), I)).
power_eval(power_rep(I, Base), Base, fix(I)).
power_eval(big_plus(X, Y, I, Base), Base, plus(I, plus(power_eval(X, Base), power_eval(Y, Base)))).
power_eval(big_plus(power_rep(I, Base), power_rep(J, Base), zero1, Base), Base, plus(I, J)).
quotient(plus(X, plus(X, Y)), succ(succ(zero)), plus(X, quotient(Y, succ(succ(zero))))).
quotient(times(Y, X), Y, if(zerop(Y), zero1, fix(X))).
remainder(X17, succ(zero), zero1).
remainder(X, X, zero1).
remainder(times(X18, Z), Z, zero1).
remainder(times(Y, X19), Y, zero1).
reverse_loop(X, Y, append(reverse(X), Y)).
reverse_loop(X, [], reverse(X)).
times(X, plus(Y, Z), plus(times(X, Y), times(X, Z))).
times(times(X, Y), Z, times(X, times(Y, Z))).
times(X, difference(C, W), difference(times(C, X), times(W, X))).
times(X, add1(Y), if(numberp(Y), plus(X, times(X, Y)), fix(X))).
go(T) :- ','(time(X20), ','(wff(X), ','(tautology(X), time(T)))).
time(T) :- statistics(runtime, .(X21, .(T, []))).
wff(implies(and(implies(X, Y), and(implies(Y, Z), and(implies(Z, U), implies(U, W)))), implies(X, W))) :- ','(=(X, f(plus(plus(a, b), plus(c, zero1)))), ','(=(Y, f(times(times(a, b), plus(c, d)))), ','(=(Z, f(reverse(append(append(a, b), [])))), ','(=(U, equal(plus(a, b), difference(x, y))), =(W, lessp(remainder(a, b), member(a, length(b)))))))).
isPlus(zero, X, X).
isPlus(succ(X), zero, succ(X)).
isPlus(succ(X), succ(Y), succ(succ(Z))) :- isPlus(X, Y, Z).
isPlus(succ(X), pred(Y), Z) :- isPlus(X, Y, Z).
isPlus(pred(X), zero, pred(X)).
isPlus(pred(X), succ(Y), Z) :- isPlus(X, Y, Z).
isPlus(pred(X), pred(Y), pred(pred(Z))) :- isPlus(X, Y, Z).
isMinus(X, zero, X).
isMinus(zero, succ(Y), pred(Z)) :- isMinus(zero, Y, Z).
isMinus(zero, pred(Y), succ(Z)) :- isMinus(zero, Y, Z).
isMinus(succ(X), succ(Y), Z) :- isMinus(X, Y, Z).
isMinus(succ(X), pred(Y), succ(succ(Z))) :- isMinus(X, Y, Z).
isMinus(pred(X), succ(Y), pred(pred(Z))) :- isMinus(X, Y, Z).
isMinus(pred(X), pred(Y), Z) :- isMinus(X, Y, Z).
isTimes(X, zero, zero).
isTimes(zero, succ(Y), zero).
isTimes(zero, pred(Y), zero).
isTimes(succ(X), succ(Y), Z) :- ','(isTimes(succ(X), Y, A), isPlus(A, succ(X), Z)).
isTimes(succ(X), pred(Y), Z) :- ','(isTimes(succ(X), Y, A), isMinus(A, succ(X), Z)).
isTimes(pred(X), succ(Y), Z) :- ','(isTimes(pred(X), Y, A), isPlus(A, pred(X), Z)).
isTimes(pred(X), pred(Y), Z) :- ','(isTimes(pred(X), Y, A), isMinus(A, pred(X), Z)).
isDiv(zero, succ(Y), zero).
isDiv(zero, pred(Y), zero).
isDiv(succ(X), succ(Y), zero) :- isMinus(succ(X), succ(Y), pred(Z)).
isDiv(succ(X), succ(Y), succ(Z)) :- ','(isMinus(succ(X), succ(Y), A), isDiv(A, succ(Y), Z)).
isDiv(succ(X), pred(Y), Z) :- ','(isMinus(zero, pred(Y), A), ','(isDiv(succ(X), A, B), isMinus(zero, B, Z))).
isDiv(pred(X), pred(Y), zero) :- isMinus(pred(X), pred(Y), succ(Z)).
isDiv(pred(X), pred(Y), succ(Z)) :- ','(isMinus(pred(X), pred(Y), A), isDiv(A, pred(Y), Z)).
isDiv(pred(X), succ(Y), Z) :- ','(isMinus(zero, pred(X), A), ','(isDiv(A, succ(Y), B), isMinus(zero, B, Z))).
isModulo(X, Y, Z) :- ','(isDiv(X, Y, A), ','(isTimes(A, Y, B), isMinus(X, B, Z))).
if1(Wff, Tlist, Flist) :- call1(Wff, Tlist).
if1(Wff, Tlist, Flist) :- if4(Wff, Flist).
if2(Wff, If, Then, Else, Tlist, Flist) :- ','(call2(Wff, If, Then, Else), ;(if5(If, Tlist, Then, Flist, Else), ','(tautology(Then, .(If, Tlist), Flist), tautology(Else, Tlist, .(If, Flist))))).
if3(Mid, Next, New) :- ','(call3(Mid, Next), rewrite(Next, New)).
if3(Mid, Next, New) :- =(New, Mid).
if4(Wff, Flist) :- ','(call4(Wff, Flist), fail).
if5(If, Tlist, Then, Flist, Else) :- ','(call5(If, Tlist), tautology(Then, Tlist, Flist)).
if5(If, Tlist, Then, Flist, Else) :- if6(If, Flist, Else, Tlist).
if6(If, Flist, Else, Tlist) :- ','(call6(If, Flist), tautology(Else, Tlist, Flist)).
call1(Wff, Tlist) :- truep(Wff, Tlist).
call2(Wff, If, Then, Else) :- =(Wff, if(If, Then, Else)).
call3(Mid, Next) :- equal(Mid, Next).
call4(Wff, Flist) :- falsep(Wff, Flist).
call5(If, Tlist) :- truep(If, Tlist).
call6(If, Flist) :- falsep(If, Flist).
fail :- failure(a).
failure(b).


Query: tautology(g)
----------------------------------------

(29) UnifyTransformerProof (EQUIVALENT)
Added a fact for the built-in = predicate [PROLOG].
----------------------------------------

(30)
Obligation:
Clauses:

tautology(Wff) :- ','(write('rewriting...'), ','(nl, ','(rewrite(Wff, NewWff), ','(write('proving...'), ','(nl, tautology(NewWff, [], [])))))).
tautology(Wff, Tlist, Flist) :- ;(if1(Wff, Tlist, Flist), if2(Wff, If, Then, Else, Tlist, Flist)).
rewrite(Atom, Atom) :- atomic(Atom).
rewrite(Old, New) :- ','(functor(Old, F, N), ','(functor(Mid, F, N), ','(rewrite_args(N, Old, Mid), if3(Mid, Next, New)))).
rewrite_args(zero, X1, X2).
rewrite_args(N, Old, Mid) :- ','(arg(N, Old, OldArg), ','(arg(N, Mid, MidArg), ','(rewrite(OldArg, MidArg), ','(isMinus(N, succ(zero), U), ','(=(N1, U), rewrite_args(N1, Old, Mid)))))).
truep(t, X3).
truep(Wff, Tlist) :- member(Wff, Tlist).
falsep(f, X4).
falsep(Wff, Flist) :- member(Wff, Flist).
member(X, .(X, X5)).
member(X, .(X6, T)) :- member(X, T).
equal(and(P, Q), if(P, if(Q, t, f), f)).
equal(append(append(X, Y), Z), append(X, append(Y, Z))).
equal(assignment(X, append(A, B)), if(assignedp(X, A), assignment(X, A), assignment(X, B))).
equal(assume_false(Var, Alist), cons(cons(Var, f), Alist)).
equal(assume_true(Var, Alist), cons(cons(Var, t), Alist)).
equal(boolean(X), or(equal(X, t), equal(X, f))).
equal(car(gopher(X)), if(listp(X), car(flatten(X)), zero1)).
equal(compile(Form), reverse(codegen(optimize(Form), []))).
equal(count_list(Z, sort_lp(X, Y)), plus(count_list(Z, X), count_list(Z, Y))).
equal(countps_(L, Pred), countps_loop(L, Pred, zero1)).
equal(difference(A, B), C) :- difference(A, B, C).
equal(divides(X, Y), zerop(remainder(Y, X))).
equal(dsort(X), sort2(X)).
equal(eqp(X, Y), equal(fix(X), fix(Y))).
equal(equal(A, B), C) :- eq(A, B, C).
equal(even1(X), if(zerop(X), t, odd(decr(X)))).
equal(exec(append(X, Y), Pds, Envrn), exec(Y, exec(X, Pds, Envrn), Envrn)).
equal(exp(A, B), C) :- exp(A, B, C).
equal(fact_(I), fact_loop(I, succ(zero))).
equal(falsify(X), falsify1(normalize(X), [])).
equal(fix(X), if(numberp(X), X, zero1)).
equal(flatten(cdr(gopher(X))), if(listp(X), cdr(flatten(X)), cons(zero1, []))).
equal(gcd(A, B), C) :- gcd(A, B, C).
equal(get(J, set(I, Val, Mem)), if(eqp(J, I), Val, get(J, Mem))).
equal(greatereqp(X, Y), not(lessp(X, Y))).
equal(greatereqpr(X, Y), not(lessp(X, Y))).
equal(greaterp(X, Y), lessp(Y, X)).
equal(if(if(A, B, C), D, E), if(A, if(B, D, E), if(C, D, E))).
equal(iff(X, Y), and(implies(X, Y), implies(Y, X))).
equal(implies(P, Q), if(P, if(Q, t, f), t)).
equal(last(append(A, B)), if(listp(B), last(B), if(listp(A), cons(car(last(A))), B))).
equal(length(A), B) :- mylength(A, B).
equal(lesseqp(X, Y), not(lessp(Y, X))).
equal(lessp(A, B), C) :- lessp(A, B, C).
equal(listp(gopher(X)), listp(X)).
equal(mc_flatten(X, Y), append(flatten(X), Y)).
equal(meaning(A, B), C) :- meaning(A, B, C).
equal(member(A, B), C) :- mymember(A, B, C).
equal(not(P), if(P, f, t)).
equal(nth(A, B), C) :- nth(A, B, C).
equal(numberp(greatest_factor(X, Y)), not(and(or(zerop(Y), equal(Y, succ(zero))), not(numberp(X))))).
equal(or(P, Q), if(P, t, if(Q, t, f), f)).
equal(plus(A, B), C) :- plus(A, B, C).
equal(power_eval(A, B), C) :- power_eval(A, B, C).
equal(prime(X), and(not(zerop(X)), and(not(equal(X, add1(zero1))), prime1(X, decr(X))))).
equal(prime_list(append(X, Y)), and(prime_list(X), prime_list(Y))).
equal(quotient(A, B), C) :- quotient(A, B, C).
equal(remainder(A, B), C) :- remainder(A, B, C).
equal(reverse_(X), reverse_loop(X, [])).
equal(reverse(append(A, B)), append(reverse(B), reverse(A))).
equal(reverse_loop(A, B), C) :- reverse_loop(A, B, C).
equal(samefringe(X, Y), equal(flatten(X), flatten(Y))).
equal(sigma(zero1, I), quotient(times(I, add1(I)), succ(succ(zero)))).
equal(sort2(delete(X, L)), delete(X, sort2(L))).
equal(tautology_checker(X), tautologyp(normalize(X), [])).
equal(times(A, B), C) :- times(A, B, C).
equal(times_list(append(X, Y)), times(times_list(X), times_list(Y))).
equal(value(normalize(X), A), value(X, A)).
equal(zerop(X), or(equal(X, zero1), not(numberp(X)))).
difference(X, X, zero1).
difference(plus(X, Y), X, fix(Y)).
difference(plus(Y, X), X, fix(Y)).
difference(plus(X, Y), plus(X, Z), difference(Y, Z)).
difference(plus(B, plus(A, C)), A, plus(B, C)).
difference(add1(plus(Y, Z)), Z, add1(Y)).
difference(add1(add1(X)), succ(succ(zero)), fix(X)).
eq(plus(A, B), zero1, and(zerop(A), zerop(B))).
eq(plus(A, B), plus(A, C), equal(fix(B), fix(C))).
eq(zero1, difference(X, Y), not(lessp(Y, X))).
eq(X, difference(X, Y), and(numberp(X), and(or(equal(X, zero1), zerop(Y))))).
eq(times(X, Y), zero1, or(zerop(X), zerop(Y))).
eq(append(A, B), append(A, C), equal(B, C)).
eq(flatten(X), cons(Y, []), and(nlistp(X), equal(X, Y))).
eq(greatest_factor(X, Y), zero1, and(or(zerop(Y), equal(Y, succ(zero))), equal(X, zero1))).
eq(greatest_factor(X, X8), succ(zero), equal(X, succ(zero))).
eq(Z, times(W, Z), and(numberp(Z), or(equal(Z, zero1), equal(W, succ(zero))))).
eq(X, times(X, Y), or(equal(X, zero1), and(numberp(X), equal(Y, succ(zero))))).
eq(times(A, B), succ(zero), and(not(equal(A, zero1)), and(not(equal(B, zero1)), and(numberp(A), and(numberp(B), and(equal(decr(A), zero1), equal(decr(B), zero1))))))).
eq(difference(X, Y), difference(Z, Y), if(lessp(X, Y), not(lessp(Y, Z)), if(lessp(Z, Y), not(lessp(Y, X)), equal(fix(X), fix(Z))))).
eq(lessp(X, Y), Z, if(lessp(X, Y), equal(t, Z), equal(f, Z))).
exp(I, plus(J, K), times(exp(I, J), exp(I, K))).
exp(I, times(J, K), exp(exp(I, J), K)).
gcd(X, Y, gcd(Y, X)).
gcd(times(X, Z), times(Y, Z), times(Z, gcd(X, Y))).
mylength(reverse(X), length(X)).
mylength(cons(X9, cons(X10, cons(X11, cons(X12, cons(X13, cons(X14, X7)))))), plus(succ(succ(succ(succ(succ(succ(zero)))))), length(X7))).
lessp(remainder(X15, Y), Y, not(zerop(Y))).
lessp(quotient(I, J), I, and(not(zerop(I)), or(zerop(J), not(equal(J, succ(zero)))))).
lessp(remainder(X, Y), X, and(not(zerop(Y)), and(not(zerop(X)), not(lessp(X, Y))))).
lessp(plus(X, Y), plus(X, Z), lessp(Y, Z)).
lessp(times(X, Z), times(Y, Z), and(not(zerop(Z)), lessp(X, Y))).
lessp(Y, plus(X, Y), not(zerop(X))).
lessp(length(delete(X, L)), length(L), member(X, L)).
meaning(plus_tree(append(X, Y)), A, plus(meaning(plus_tree(X), A), meaning(plus_tree(Y), A))).
meaning(plus_tree(plus_fringe(X)), A, fix(meaning(X, A))).
meaning(plus_tree(delete(X, Y)), A, if(member(X, Y), difference(meaning(plus_tree(Y), A), meaning(X, A)), meaning(plus_tree(Y), A))).
mymember(X, append(A, B), or(member(X, A), member(X, B))).
mymember(X, reverse(Y), member(X, Y)).
mymember(A, intersect(B, C), and(member(A, B), member(A, C))).
nth(zero1, X16, zero1).
nth([], I, if(zerop(I), [], zero1)).
nth(append(A, B), I, append(nth(A, I), nth(B, difference(I, length(A))))).
plus(plus(X, Y), Z, plus(X, plus(Y, Z))).
plus(remainder(X, Y), times(Y, quotient(X, Y)), fix(X)).
plus(X, add1(Y), if(numberp(Y), add1(plus(X, Y)), add1(X))).
power_eval(big_plus1(L, I, Base), Base, plus(power_eval(L, Base), I)).
power_eval(power_rep(I, Base), Base, fix(I)).
power_eval(big_plus(X, Y, I, Base), Base, plus(I, plus(power_eval(X, Base), power_eval(Y, Base)))).
power_eval(big_plus(power_rep(I, Base), power_rep(J, Base), zero1, Base), Base, plus(I, J)).
quotient(plus(X, plus(X, Y)), succ(succ(zero)), plus(X, quotient(Y, succ(succ(zero))))).
quotient(times(Y, X), Y, if(zerop(Y), zero1, fix(X))).
remainder(X17, succ(zero), zero1).
remainder(X, X, zero1).
remainder(times(X18, Z), Z, zero1).
remainder(times(Y, X19), Y, zero1).
reverse_loop(X, Y, append(reverse(X), Y)).
reverse_loop(X, [], reverse(X)).
times(X, plus(Y, Z), plus(times(X, Y), times(X, Z))).
times(times(X, Y), Z, times(X, times(Y, Z))).
times(X, difference(C, W), difference(times(C, X), times(W, X))).
times(X, add1(Y), if(numberp(Y), plus(X, times(X, Y)), fix(X))).
go(T) :- ','(time(X20), ','(wff(X), ','(tautology(X), time(T)))).
time(T) :- statistics(runtime, .(X21, .(T, []))).
wff(implies(and(implies(X, Y), and(implies(Y, Z), and(implies(Z, U), implies(U, W)))), implies(X, W))) :- ','(=(X, f(plus(plus(a, b), plus(c, zero1)))), ','(=(Y, f(times(times(a, b), plus(c, d)))), ','(=(Z, f(reverse(append(append(a, b), [])))), ','(=(U, equal(plus(a, b), difference(x, y))), =(W, lessp(remainder(a, b), member(a, length(b)))))))).
isPlus(zero, X, X).
isPlus(succ(X), zero, succ(X)).
isPlus(succ(X), succ(Y), succ(succ(Z))) :- isPlus(X, Y, Z).
isPlus(succ(X), pred(Y), Z) :- isPlus(X, Y, Z).
isPlus(pred(X), zero, pred(X)).
isPlus(pred(X), succ(Y), Z) :- isPlus(X, Y, Z).
isPlus(pred(X), pred(Y), pred(pred(Z))) :- isPlus(X, Y, Z).
isMinus(X, zero, X).
isMinus(zero, succ(Y), pred(Z)) :- isMinus(zero, Y, Z).
isMinus(zero, pred(Y), succ(Z)) :- isMinus(zero, Y, Z).
isMinus(succ(X), succ(Y), Z) :- isMinus(X, Y, Z).
isMinus(succ(X), pred(Y), succ(succ(Z))) :- isMinus(X, Y, Z).
isMinus(pred(X), succ(Y), pred(pred(Z))) :- isMinus(X, Y, Z).
isMinus(pred(X), pred(Y), Z) :- isMinus(X, Y, Z).
isTimes(X, zero, zero).
isTimes(zero, succ(Y), zero).
isTimes(zero, pred(Y), zero).
isTimes(succ(X), succ(Y), Z) :- ','(isTimes(succ(X), Y, A), isPlus(A, succ(X), Z)).
isTimes(succ(X), pred(Y), Z) :- ','(isTimes(succ(X), Y, A), isMinus(A, succ(X), Z)).
isTimes(pred(X), succ(Y), Z) :- ','(isTimes(pred(X), Y, A), isPlus(A, pred(X), Z)).
isTimes(pred(X), pred(Y), Z) :- ','(isTimes(pred(X), Y, A), isMinus(A, pred(X), Z)).
isDiv(zero, succ(Y), zero).
isDiv(zero, pred(Y), zero).
isDiv(succ(X), succ(Y), zero) :- isMinus(succ(X), succ(Y), pred(Z)).
isDiv(succ(X), succ(Y), succ(Z)) :- ','(isMinus(succ(X), succ(Y), A), isDiv(A, succ(Y), Z)).
isDiv(succ(X), pred(Y), Z) :- ','(isMinus(zero, pred(Y), A), ','(isDiv(succ(X), A, B), isMinus(zero, B, Z))).
isDiv(pred(X), pred(Y), zero) :- isMinus(pred(X), pred(Y), succ(Z)).
isDiv(pred(X), pred(Y), succ(Z)) :- ','(isMinus(pred(X), pred(Y), A), isDiv(A, pred(Y), Z)).
isDiv(pred(X), succ(Y), Z) :- ','(isMinus(zero, pred(X), A), ','(isDiv(A, succ(Y), B), isMinus(zero, B, Z))).
isModulo(X, Y, Z) :- ','(isDiv(X, Y, A), ','(isTimes(A, Y, B), isMinus(X, B, Z))).
if1(Wff, Tlist, Flist) :- call1(Wff, Tlist).
if1(Wff, Tlist, Flist) :- if4(Wff, Flist).
if2(Wff, If, Then, Else, Tlist, Flist) :- ','(call2(Wff, If, Then, Else), ;(if5(If, Tlist, Then, Flist, Else), ','(tautology(Then, .(If, Tlist), Flist), tautology(Else, Tlist, .(If, Flist))))).
if3(Mid, Next, New) :- ','(call3(Mid, Next), rewrite(Next, New)).
if3(Mid, Next, New) :- =(New, Mid).
if4(Wff, Flist) :- ','(call4(Wff, Flist), fail).
if5(If, Tlist, Then, Flist, Else) :- ','(call5(If, Tlist), tautology(Then, Tlist, Flist)).
if5(If, Tlist, Then, Flist, Else) :- if6(If, Flist, Else, Tlist).
if6(If, Flist, Else, Tlist) :- ','(call6(If, Flist), tautology(Else, Tlist, Flist)).
call1(Wff, Tlist) :- truep(Wff, Tlist).
call2(Wff, If, Then, Else) :- =(Wff, if(If, Then, Else)).
call3(Mid, Next) :- equal(Mid, Next).
call4(Wff, Flist) :- falsep(Wff, Flist).
call5(If, Tlist) :- truep(If, Tlist).
call6(If, Flist) :- falsep(If, Flist).
fail :- failure(a).
failure(b).
=(X, X).


Query: tautology(g)
----------------------------------------

(31) OrTransformerProof (EQUIVALENT)
Transformed all or-constructs[PROLOG].
----------------------------------------

(32)
Obligation:
Clauses:

tautology(Wff) :- ','(write('rewriting...'), ','(nl, ','(rewrite(Wff, NewWff), ','(write('proving...'), ','(nl, tautology(NewWff, [], [])))))).
tautology(Wff, Tlist, Flist) :- if1(Wff, Tlist, Flist).
tautology(Wff, Tlist, Flist) :- if2(Wff, If, Then, Else, Tlist, Flist).
rewrite(Atom, Atom) :- atomic(Atom).
rewrite(Old, New) :- ','(functor(Old, F, N), ','(functor(Mid, F, N), ','(rewrite_args(N, Old, Mid), if3(Mid, Next, New)))).
rewrite_args(zero, X1, X2).
rewrite_args(N, Old, Mid) :- ','(arg(N, Old, OldArg), ','(arg(N, Mid, MidArg), ','(rewrite(OldArg, MidArg), ','(isMinus(N, succ(zero), U), ','(=(N1, U), rewrite_args(N1, Old, Mid)))))).
truep(t, X3).
truep(Wff, Tlist) :- member(Wff, Tlist).
falsep(f, X4).
falsep(Wff, Flist) :- member(Wff, Flist).
member(X, .(X, X5)).
member(X, .(X6, T)) :- member(X, T).
equal(and(P, Q), if(P, if(Q, t, f), f)).
equal(append(append(X, Y), Z), append(X, append(Y, Z))).
equal(assignment(X, append(A, B)), if(assignedp(X, A), assignment(X, A), assignment(X, B))).
equal(assume_false(Var, Alist), cons(cons(Var, f), Alist)).
equal(assume_true(Var, Alist), cons(cons(Var, t), Alist)).
equal(boolean(X), or(equal(X, t), equal(X, f))).
equal(car(gopher(X)), if(listp(X), car(flatten(X)), zero1)).
equal(compile(Form), reverse(codegen(optimize(Form), []))).
equal(count_list(Z, sort_lp(X, Y)), plus(count_list(Z, X), count_list(Z, Y))).
equal(countps_(L, Pred), countps_loop(L, Pred, zero1)).
equal(difference(A, B), C) :- difference(A, B, C).
equal(divides(X, Y), zerop(remainder(Y, X))).
equal(dsort(X), sort2(X)).
equal(eqp(X, Y), equal(fix(X), fix(Y))).
equal(equal(A, B), C) :- eq(A, B, C).
equal(even1(X), if(zerop(X), t, odd(decr(X)))).
equal(exec(append(X, Y), Pds, Envrn), exec(Y, exec(X, Pds, Envrn), Envrn)).
equal(exp(A, B), C) :- exp(A, B, C).
equal(fact_(I), fact_loop(I, succ(zero))).
equal(falsify(X), falsify1(normalize(X), [])).
equal(fix(X), if(numberp(X), X, zero1)).
equal(flatten(cdr(gopher(X))), if(listp(X), cdr(flatten(X)), cons(zero1, []))).
equal(gcd(A, B), C) :- gcd(A, B, C).
equal(get(J, set(I, Val, Mem)), if(eqp(J, I), Val, get(J, Mem))).
equal(greatereqp(X, Y), not(lessp(X, Y))).
equal(greatereqpr(X, Y), not(lessp(X, Y))).
equal(greaterp(X, Y), lessp(Y, X)).
equal(if(if(A, B, C), D, E), if(A, if(B, D, E), if(C, D, E))).
equal(iff(X, Y), and(implies(X, Y), implies(Y, X))).
equal(implies(P, Q), if(P, if(Q, t, f), t)).
equal(last(append(A, B)), if(listp(B), last(B), if(listp(A), cons(car(last(A))), B))).
equal(length(A), B) :- mylength(A, B).
equal(lesseqp(X, Y), not(lessp(Y, X))).
equal(lessp(A, B), C) :- lessp(A, B, C).
equal(listp(gopher(X)), listp(X)).
equal(mc_flatten(X, Y), append(flatten(X), Y)).
equal(meaning(A, B), C) :- meaning(A, B, C).
equal(member(A, B), C) :- mymember(A, B, C).
equal(not(P), if(P, f, t)).
equal(nth(A, B), C) :- nth(A, B, C).
equal(numberp(greatest_factor(X, Y)), not(and(or(zerop(Y), equal(Y, succ(zero))), not(numberp(X))))).
equal(or(P, Q), if(P, t, if(Q, t, f), f)).
equal(plus(A, B), C) :- plus(A, B, C).
equal(power_eval(A, B), C) :- power_eval(A, B, C).
equal(prime(X), and(not(zerop(X)), and(not(equal(X, add1(zero1))), prime1(X, decr(X))))).
equal(prime_list(append(X, Y)), and(prime_list(X), prime_list(Y))).
equal(quotient(A, B), C) :- quotient(A, B, C).
equal(remainder(A, B), C) :- remainder(A, B, C).
equal(reverse_(X), reverse_loop(X, [])).
equal(reverse(append(A, B)), append(reverse(B), reverse(A))).
equal(reverse_loop(A, B), C) :- reverse_loop(A, B, C).
equal(samefringe(X, Y), equal(flatten(X), flatten(Y))).
equal(sigma(zero1, I), quotient(times(I, add1(I)), succ(succ(zero)))).
equal(sort2(delete(X, L)), delete(X, sort2(L))).
equal(tautology_checker(X), tautologyp(normalize(X), [])).
equal(times(A, B), C) :- times(A, B, C).
equal(times_list(append(X, Y)), times(times_list(X), times_list(Y))).
equal(value(normalize(X), A), value(X, A)).
equal(zerop(X), or(equal(X, zero1), not(numberp(X)))).
difference(X, X, zero1).
difference(plus(X, Y), X, fix(Y)).
difference(plus(Y, X), X, fix(Y)).
difference(plus(X, Y), plus(X, Z), difference(Y, Z)).
difference(plus(B, plus(A, C)), A, plus(B, C)).
difference(add1(plus(Y, Z)), Z, add1(Y)).
difference(add1(add1(X)), succ(succ(zero)), fix(X)).
eq(plus(A, B), zero1, and(zerop(A), zerop(B))).
eq(plus(A, B), plus(A, C), equal(fix(B), fix(C))).
eq(zero1, difference(X, Y), not(lessp(Y, X))).
eq(X, difference(X, Y), and(numberp(X), and(or(equal(X, zero1), zerop(Y))))).
eq(times(X, Y), zero1, or(zerop(X), zerop(Y))).
eq(append(A, B), append(A, C), equal(B, C)).
eq(flatten(X), cons(Y, []), and(nlistp(X), equal(X, Y))).
eq(greatest_factor(X, Y), zero1, and(or(zerop(Y), equal(Y, succ(zero))), equal(X, zero1))).
eq(greatest_factor(X, X8), succ(zero), equal(X, succ(zero))).
eq(Z, times(W, Z), and(numberp(Z), or(equal(Z, zero1), equal(W, succ(zero))))).
eq(X, times(X, Y), or(equal(X, zero1), and(numberp(X), equal(Y, succ(zero))))).
eq(times(A, B), succ(zero), and(not(equal(A, zero1)), and(not(equal(B, zero1)), and(numberp(A), and(numberp(B), and(equal(decr(A), zero1), equal(decr(B), zero1))))))).
eq(difference(X, Y), difference(Z, Y), if(lessp(X, Y), not(lessp(Y, Z)), if(lessp(Z, Y), not(lessp(Y, X)), equal(fix(X), fix(Z))))).
eq(lessp(X, Y), Z, if(lessp(X, Y), equal(t, Z), equal(f, Z))).
exp(I, plus(J, K), times(exp(I, J), exp(I, K))).
exp(I, times(J, K), exp(exp(I, J), K)).
gcd(X, Y, gcd(Y, X)).
gcd(times(X, Z), times(Y, Z), times(Z, gcd(X, Y))).
mylength(reverse(X), length(X)).
mylength(cons(X9, cons(X10, cons(X11, cons(X12, cons(X13, cons(X14, X7)))))), plus(succ(succ(succ(succ(succ(succ(zero)))))), length(X7))).
lessp(remainder(X15, Y), Y, not(zerop(Y))).
lessp(quotient(I, J), I, and(not(zerop(I)), or(zerop(J), not(equal(J, succ(zero)))))).
lessp(remainder(X, Y), X, and(not(zerop(Y)), and(not(zerop(X)), not(lessp(X, Y))))).
lessp(plus(X, Y), plus(X, Z), lessp(Y, Z)).
lessp(times(X, Z), times(Y, Z), and(not(zerop(Z)), lessp(X, Y))).
lessp(Y, plus(X, Y), not(zerop(X))).
lessp(length(delete(X, L)), length(L), member(X, L)).
meaning(plus_tree(append(X, Y)), A, plus(meaning(plus_tree(X), A), meaning(plus_tree(Y), A))).
meaning(plus_tree(plus_fringe(X)), A, fix(meaning(X, A))).
meaning(plus_tree(delete(X, Y)), A, if(member(X, Y), difference(meaning(plus_tree(Y), A), meaning(X, A)), meaning(plus_tree(Y), A))).
mymember(X, append(A, B), or(member(X, A), member(X, B))).
mymember(X, reverse(Y), member(X, Y)).
mymember(A, intersect(B, C), and(member(A, B), member(A, C))).
nth(zero1, X16, zero1).
nth([], I, if(zerop(I), [], zero1)).
nth(append(A, B), I, append(nth(A, I), nth(B, difference(I, length(A))))).
plus(plus(X, Y), Z, plus(X, plus(Y, Z))).
plus(remainder(X, Y), times(Y, quotient(X, Y)), fix(X)).
plus(X, add1(Y), if(numberp(Y), add1(plus(X, Y)), add1(X))).
power_eval(big_plus1(L, I, Base), Base, plus(power_eval(L, Base), I)).
power_eval(power_rep(I, Base), Base, fix(I)).
power_eval(big_plus(X, Y, I, Base), Base, plus(I, plus(power_eval(X, Base), power_eval(Y, Base)))).
power_eval(big_plus(power_rep(I, Base), power_rep(J, Base), zero1, Base), Base, plus(I, J)).
quotient(plus(X, plus(X, Y)), succ(succ(zero)), plus(X, quotient(Y, succ(succ(zero))))).
quotient(times(Y, X), Y, if(zerop(Y), zero1, fix(X))).
remainder(X17, succ(zero), zero1).
remainder(X, X, zero1).
remainder(times(X18, Z), Z, zero1).
remainder(times(Y, X19), Y, zero1).
reverse_loop(X, Y, append(reverse(X), Y)).
reverse_loop(X, [], reverse(X)).
times(X, plus(Y, Z), plus(times(X, Y), times(X, Z))).
times(times(X, Y), Z, times(X, times(Y, Z))).
times(X, difference(C, W), difference(times(C, X), times(W, X))).
times(X, add1(Y), if(numberp(Y), plus(X, times(X, Y)), fix(X))).
go(T) :- ','(time(X20), ','(wff(X), ','(tautology(X), time(T)))).
time(T) :- statistics(runtime, .(X21, .(T, []))).
wff(implies(and(implies(X, Y), and(implies(Y, Z), and(implies(Z, U), implies(U, W)))), implies(X, W))) :- ','(=(X, f(plus(plus(a, b), plus(c, zero1)))), ','(=(Y, f(times(times(a, b), plus(c, d)))), ','(=(Z, f(reverse(append(append(a, b), [])))), ','(=(U, equal(plus(a, b), difference(x, y))), =(W, lessp(remainder(a, b), member(a, length(b)))))))).
isPlus(zero, X, X).
isPlus(succ(X), zero, succ(X)).
isPlus(succ(X), succ(Y), succ(succ(Z))) :- isPlus(X, Y, Z).
isPlus(succ(X), pred(Y), Z) :- isPlus(X, Y, Z).
isPlus(pred(X), zero, pred(X)).
isPlus(pred(X), succ(Y), Z) :- isPlus(X, Y, Z).
isPlus(pred(X), pred(Y), pred(pred(Z))) :- isPlus(X, Y, Z).
isMinus(X, zero, X).
isMinus(zero, succ(Y), pred(Z)) :- isMinus(zero, Y, Z).
isMinus(zero, pred(Y), succ(Z)) :- isMinus(zero, Y, Z).
isMinus(succ(X), succ(Y), Z) :- isMinus(X, Y, Z).
isMinus(succ(X), pred(Y), succ(succ(Z))) :- isMinus(X, Y, Z).
isMinus(pred(X), succ(Y), pred(pred(Z))) :- isMinus(X, Y, Z).
isMinus(pred(X), pred(Y), Z) :- isMinus(X, Y, Z).
isTimes(X, zero, zero).
isTimes(zero, succ(Y), zero).
isTimes(zero, pred(Y), zero).
isTimes(succ(X), succ(Y), Z) :- ','(isTimes(succ(X), Y, A), isPlus(A, succ(X), Z)).
isTimes(succ(X), pred(Y), Z) :- ','(isTimes(succ(X), Y, A), isMinus(A, succ(X), Z)).
isTimes(pred(X), succ(Y), Z) :- ','(isTimes(pred(X), Y, A), isPlus(A, pred(X), Z)).
isTimes(pred(X), pred(Y), Z) :- ','(isTimes(pred(X), Y, A), isMinus(A, pred(X), Z)).
isDiv(zero, succ(Y), zero).
isDiv(zero, pred(Y), zero).
isDiv(succ(X), succ(Y), zero) :- isMinus(succ(X), succ(Y), pred(Z)).
isDiv(succ(X), succ(Y), succ(Z)) :- ','(isMinus(succ(X), succ(Y), A), isDiv(A, succ(Y), Z)).
isDiv(succ(X), pred(Y), Z) :- ','(isMinus(zero, pred(Y), A), ','(isDiv(succ(X), A, B), isMinus(zero, B, Z))).
isDiv(pred(X), pred(Y), zero) :- isMinus(pred(X), pred(Y), succ(Z)).
isDiv(pred(X), pred(Y), succ(Z)) :- ','(isMinus(pred(X), pred(Y), A), isDiv(A, pred(Y), Z)).
isDiv(pred(X), succ(Y), Z) :- ','(isMinus(zero, pred(X), A), ','(isDiv(A, succ(Y), B), isMinus(zero, B, Z))).
isModulo(X, Y, Z) :- ','(isDiv(X, Y, A), ','(isTimes(A, Y, B), isMinus(X, B, Z))).
if1(Wff, Tlist, Flist) :- call1(Wff, Tlist).
if1(Wff, Tlist, Flist) :- if4(Wff, Flist).
if2(Wff, If, Then, Else, Tlist, Flist) :- ','(call2(Wff, If, Then, Else), if5(If, Tlist, Then, Flist, Else)).
if2(Wff, If, Then, Else, Tlist, Flist) :- ','(call2(Wff, If, Then, Else), ','(tautology(Then, .(If, Tlist), Flist), tautology(Else, Tlist, .(If, Flist)))).
if3(Mid, Next, New) :- ','(call3(Mid, Next), rewrite(Next, New)).
if3(Mid, Next, New) :- =(New, Mid).
if4(Wff, Flist) :- ','(call4(Wff, Flist), fail).
if5(If, Tlist, Then, Flist, Else) :- ','(call5(If, Tlist), tautology(Then, Tlist, Flist)).
if5(If, Tlist, Then, Flist, Else) :- if6(If, Flist, Else, Tlist).
if6(If, Flist, Else, Tlist) :- ','(call6(If, Flist), tautology(Else, Tlist, Flist)).
call1(Wff, Tlist) :- truep(Wff, Tlist).
call2(Wff, If, Then, Else) :- =(Wff, if(If, Then, Else)).
call3(Mid, Next) :- equal(Mid, Next).
call4(Wff, Flist) :- falsep(Wff, Flist).
call5(If, Tlist) :- truep(If, Tlist).
call6(If, Flist) :- falsep(If, Flist).
fail :- failure(a).
failure(b).
=(X, X).


Query: tautology(g)
----------------------------------------

(33) UndefinedPredicateHandlerProof (SOUND)
Added facts for all undefined predicates [PROLOG].
----------------------------------------

(34)
Obligation:
Clauses:

tautology(Wff) :- ','(write('rewriting...'), ','(nl, ','(rewrite(Wff, NewWff), ','(write('proving...'), ','(nl, tautology(NewWff, [], [])))))).
tautology(Wff, Tlist, Flist) :- if1(Wff, Tlist, Flist).
tautology(Wff, Tlist, Flist) :- if2(Wff, If, Then, Else, Tlist, Flist).
rewrite(Atom, Atom) :- atomic(Atom).
rewrite(Old, New) :- ','(functor(Old, F, N), ','(functor(Mid, F, N), ','(rewrite_args(N, Old, Mid), if3(Mid, Next, New)))).
rewrite_args(zero, X1, X2).
rewrite_args(N, Old, Mid) :- ','(arg(N, Old, OldArg), ','(arg(N, Mid, MidArg), ','(rewrite(OldArg, MidArg), ','(isMinus(N, succ(zero), U), ','(=(N1, U), rewrite_args(N1, Old, Mid)))))).
truep(t, X3).
truep(Wff, Tlist) :- member(Wff, Tlist).
falsep(f, X4).
falsep(Wff, Flist) :- member(Wff, Flist).
member(X, .(X, X5)).
member(X, .(X6, T)) :- member(X, T).
equal(and(P, Q), if(P, if(Q, t, f), f)).
equal(append(append(X, Y), Z), append(X, append(Y, Z))).
equal(assignment(X, append(A, B)), if(assignedp(X, A), assignment(X, A), assignment(X, B))).
equal(assume_false(Var, Alist), cons(cons(Var, f), Alist)).
equal(assume_true(Var, Alist), cons(cons(Var, t), Alist)).
equal(boolean(X), or(equal(X, t), equal(X, f))).
equal(car(gopher(X)), if(listp(X), car(flatten(X)), zero1)).
equal(compile(Form), reverse(codegen(optimize(Form), []))).
equal(count_list(Z, sort_lp(X, Y)), plus(count_list(Z, X), count_list(Z, Y))).
equal(countps_(L, Pred), countps_loop(L, Pred, zero1)).
equal(difference(A, B), C) :- difference(A, B, C).
equal(divides(X, Y), zerop(remainder(Y, X))).
equal(dsort(X), sort2(X)).
equal(eqp(X, Y), equal(fix(X), fix(Y))).
equal(equal(A, B), C) :- eq(A, B, C).
equal(even1(X), if(zerop(X), t, odd(decr(X)))).
equal(exec(append(X, Y), Pds, Envrn), exec(Y, exec(X, Pds, Envrn), Envrn)).
equal(exp(A, B), C) :- exp(A, B, C).
equal(fact_(I), fact_loop(I, succ(zero))).
equal(falsify(X), falsify1(normalize(X), [])).
equal(fix(X), if(numberp(X), X, zero1)).
equal(flatten(cdr(gopher(X))), if(listp(X), cdr(flatten(X)), cons(zero1, []))).
equal(gcd(A, B), C) :- gcd(A, B, C).
equal(get(J, set(I, Val, Mem)), if(eqp(J, I), Val, get(J, Mem))).
equal(greatereqp(X, Y), not(lessp(X, Y))).
equal(greatereqpr(X, Y), not(lessp(X, Y))).
equal(greaterp(X, Y), lessp(Y, X)).
equal(if(if(A, B, C), D, E), if(A, if(B, D, E), if(C, D, E))).
equal(iff(X, Y), and(implies(X, Y), implies(Y, X))).
equal(implies(P, Q), if(P, if(Q, t, f), t)).
equal(last(append(A, B)), if(listp(B), last(B), if(listp(A), cons(car(last(A))), B))).
equal(length(A), B) :- mylength(A, B).
equal(lesseqp(X, Y), not(lessp(Y, X))).
equal(lessp(A, B), C) :- lessp(A, B, C).
equal(listp(gopher(X)), listp(X)).
equal(mc_flatten(X, Y), append(flatten(X), Y)).
equal(meaning(A, B), C) :- meaning(A, B, C).
equal(member(A, B), C) :- mymember(A, B, C).
equal(not(P), if(P, f, t)).
equal(nth(A, B), C) :- nth(A, B, C).
equal(numberp(greatest_factor(X, Y)), not(and(or(zerop(Y), equal(Y, succ(zero))), not(numberp(X))))).
equal(or(P, Q), if(P, t, if(Q, t, f), f)).
equal(plus(A, B), C) :- plus(A, B, C).
equal(power_eval(A, B), C) :- power_eval(A, B, C).
equal(prime(X), and(not(zerop(X)), and(not(equal(X, add1(zero1))), prime1(X, decr(X))))).
equal(prime_list(append(X, Y)), and(prime_list(X), prime_list(Y))).
equal(quotient(A, B), C) :- quotient(A, B, C).
equal(remainder(A, B), C) :- remainder(A, B, C).
equal(reverse_(X), reverse_loop(X, [])).
equal(reverse(append(A, B)), append(reverse(B), reverse(A))).
equal(reverse_loop(A, B), C) :- reverse_loop(A, B, C).
equal(samefringe(X, Y), equal(flatten(X), flatten(Y))).
equal(sigma(zero1, I), quotient(times(I, add1(I)), succ(succ(zero)))).
equal(sort2(delete(X, L)), delete(X, sort2(L))).
equal(tautology_checker(X), tautologyp(normalize(X), [])).
equal(times(A, B), C) :- times(A, B, C).
equal(times_list(append(X, Y)), times(times_list(X), times_list(Y))).
equal(value(normalize(X), A), value(X, A)).
equal(zerop(X), or(equal(X, zero1), not(numberp(X)))).
difference(X, X, zero1).
difference(plus(X, Y), X, fix(Y)).
difference(plus(Y, X), X, fix(Y)).
difference(plus(X, Y), plus(X, Z), difference(Y, Z)).
difference(plus(B, plus(A, C)), A, plus(B, C)).
difference(add1(plus(Y, Z)), Z, add1(Y)).
difference(add1(add1(X)), succ(succ(zero)), fix(X)).
eq(plus(A, B), zero1, and(zerop(A), zerop(B))).
eq(plus(A, B), plus(A, C), equal(fix(B), fix(C))).
eq(zero1, difference(X, Y), not(lessp(Y, X))).
eq(X, difference(X, Y), and(numberp(X), and(or(equal(X, zero1), zerop(Y))))).
eq(times(X, Y), zero1, or(zerop(X), zerop(Y))).
eq(append(A, B), append(A, C), equal(B, C)).
eq(flatten(X), cons(Y, []), and(nlistp(X), equal(X, Y))).
eq(greatest_factor(X, Y), zero1, and(or(zerop(Y), equal(Y, succ(zero))), equal(X, zero1))).
eq(greatest_factor(X, X8), succ(zero), equal(X, succ(zero))).
eq(Z, times(W, Z), and(numberp(Z), or(equal(Z, zero1), equal(W, succ(zero))))).
eq(X, times(X, Y), or(equal(X, zero1), and(numberp(X), equal(Y, succ(zero))))).
eq(times(A, B), succ(zero), and(not(equal(A, zero1)), and(not(equal(B, zero1)), and(numberp(A), and(numberp(B), and(equal(decr(A), zero1), equal(decr(B), zero1))))))).
eq(difference(X, Y), difference(Z, Y), if(lessp(X, Y), not(lessp(Y, Z)), if(lessp(Z, Y), not(lessp(Y, X)), equal(fix(X), fix(Z))))).
eq(lessp(X, Y), Z, if(lessp(X, Y), equal(t, Z), equal(f, Z))).
exp(I, plus(J, K), times(exp(I, J), exp(I, K))).
exp(I, times(J, K), exp(exp(I, J), K)).
gcd(X, Y, gcd(Y, X)).
gcd(times(X, Z), times(Y, Z), times(Z, gcd(X, Y))).
mylength(reverse(X), length(X)).
mylength(cons(X9, cons(X10, cons(X11, cons(X12, cons(X13, cons(X14, X7)))))), plus(succ(succ(succ(succ(succ(succ(zero)))))), length(X7))).
lessp(remainder(X15, Y), Y, not(zerop(Y))).
lessp(quotient(I, J), I, and(not(zerop(I)), or(zerop(J), not(equal(J, succ(zero)))))).
lessp(remainder(X, Y), X, and(not(zerop(Y)), and(not(zerop(X)), not(lessp(X, Y))))).
lessp(plus(X, Y), plus(X, Z), lessp(Y, Z)).
lessp(times(X, Z), times(Y, Z), and(not(zerop(Z)), lessp(X, Y))).
lessp(Y, plus(X, Y), not(zerop(X))).
lessp(length(delete(X, L)), length(L), member(X, L)).
meaning(plus_tree(append(X, Y)), A, plus(meaning(plus_tree(X), A), meaning(plus_tree(Y), A))).
meaning(plus_tree(plus_fringe(X)), A, fix(meaning(X, A))).
meaning(plus_tree(delete(X, Y)), A, if(member(X, Y), difference(meaning(plus_tree(Y), A), meaning(X, A)), meaning(plus_tree(Y), A))).
mymember(X, append(A, B), or(member(X, A), member(X, B))).
mymember(X, reverse(Y), member(X, Y)).
mymember(A, intersect(B, C), and(member(A, B), member(A, C))).
nth(zero1, X16, zero1).
nth([], I, if(zerop(I), [], zero1)).
nth(append(A, B), I, append(nth(A, I), nth(B, difference(I, length(A))))).
plus(plus(X, Y), Z, plus(X, plus(Y, Z))).
plus(remainder(X, Y), times(Y, quotient(X, Y)), fix(X)).
plus(X, add1(Y), if(numberp(Y), add1(plus(X, Y)), add1(X))).
power_eval(big_plus1(L, I, Base), Base, plus(power_eval(L, Base), I)).
power_eval(power_rep(I, Base), Base, fix(I)).
power_eval(big_plus(X, Y, I, Base), Base, plus(I, plus(power_eval(X, Base), power_eval(Y, Base)))).
power_eval(big_plus(power_rep(I, Base), power_rep(J, Base), zero1, Base), Base, plus(I, J)).
quotient(plus(X, plus(X, Y)), succ(succ(zero)), plus(X, quotient(Y, succ(succ(zero))))).
quotient(times(Y, X), Y, if(zerop(Y), zero1, fix(X))).
remainder(X17, succ(zero), zero1).
remainder(X, X, zero1).
remainder(times(X18, Z), Z, zero1).
remainder(times(Y, X19), Y, zero1).
reverse_loop(X, Y, append(reverse(X), Y)).
reverse_loop(X, [], reverse(X)).
times(X, plus(Y, Z), plus(times(X, Y), times(X, Z))).
times(times(X, Y), Z, times(X, times(Y, Z))).
times(X, difference(C, W), difference(times(C, X), times(W, X))).
times(X, add1(Y), if(numberp(Y), plus(X, times(X, Y)), fix(X))).
go(T) :- ','(time(X20), ','(wff(X), ','(tautology(X), time(T)))).
time(T) :- statistics(runtime, .(X21, .(T, []))).
wff(implies(and(implies(X, Y), and(implies(Y, Z), and(implies(Z, U), implies(U, W)))), implies(X, W))) :- ','(=(X, f(plus(plus(a, b), plus(c, zero1)))), ','(=(Y, f(times(times(a, b), plus(c, d)))), ','(=(Z, f(reverse(append(append(a, b), [])))), ','(=(U, equal(plus(a, b), difference(x, y))), =(W, lessp(remainder(a, b), member(a, length(b)))))))).
isPlus(zero, X, X).
isPlus(succ(X), zero, succ(X)).
isPlus(succ(X), succ(Y), succ(succ(Z))) :- isPlus(X, Y, Z).
isPlus(succ(X), pred(Y), Z) :- isPlus(X, Y, Z).
isPlus(pred(X), zero, pred(X)).
isPlus(pred(X), succ(Y), Z) :- isPlus(X, Y, Z).
isPlus(pred(X), pred(Y), pred(pred(Z))) :- isPlus(X, Y, Z).
isMinus(X, zero, X).
isMinus(zero, succ(Y), pred(Z)) :- isMinus(zero, Y, Z).
isMinus(zero, pred(Y), succ(Z)) :- isMinus(zero, Y, Z).
isMinus(succ(X), succ(Y), Z) :- isMinus(X, Y, Z).
isMinus(succ(X), pred(Y), succ(succ(Z))) :- isMinus(X, Y, Z).
isMinus(pred(X), succ(Y), pred(pred(Z))) :- isMinus(X, Y, Z).
isMinus(pred(X), pred(Y), Z) :- isMinus(X, Y, Z).
isTimes(X, zero, zero).
isTimes(zero, succ(Y), zero).
isTimes(zero, pred(Y), zero).
isTimes(succ(X), succ(Y), Z) :- ','(isTimes(succ(X), Y, A), isPlus(A, succ(X), Z)).
isTimes(succ(X), pred(Y), Z) :- ','(isTimes(succ(X), Y, A), isMinus(A, succ(X), Z)).
isTimes(pred(X), succ(Y), Z) :- ','(isTimes(pred(X), Y, A), isPlus(A, pred(X), Z)).
isTimes(pred(X), pred(Y), Z) :- ','(isTimes(pred(X), Y, A), isMinus(A, pred(X), Z)).
isDiv(zero, succ(Y), zero).
isDiv(zero, pred(Y), zero).
isDiv(succ(X), succ(Y), zero) :- isMinus(succ(X), succ(Y), pred(Z)).
isDiv(succ(X), succ(Y), succ(Z)) :- ','(isMinus(succ(X), succ(Y), A), isDiv(A, succ(Y), Z)).
isDiv(succ(X), pred(Y), Z) :- ','(isMinus(zero, pred(Y), A), ','(isDiv(succ(X), A, B), isMinus(zero, B, Z))).
isDiv(pred(X), pred(Y), zero) :- isMinus(pred(X), pred(Y), succ(Z)).
isDiv(pred(X), pred(Y), succ(Z)) :- ','(isMinus(pred(X), pred(Y), A), isDiv(A, pred(Y), Z)).
isDiv(pred(X), succ(Y), Z) :- ','(isMinus(zero, pred(X), A), ','(isDiv(A, succ(Y), B), isMinus(zero, B, Z))).
isModulo(X, Y, Z) :- ','(isDiv(X, Y, A), ','(isTimes(A, Y, B), isMinus(X, B, Z))).
if1(Wff, Tlist, Flist) :- call1(Wff, Tlist).
if1(Wff, Tlist, Flist) :- if4(Wff, Flist).
if2(Wff, If, Then, Else, Tlist, Flist) :- ','(call2(Wff, If, Then, Else), if5(If, Tlist, Then, Flist, Else)).
if2(Wff, If, Then, Else, Tlist, Flist) :- ','(call2(Wff, If, Then, Else), ','(tautology(Then, .(If, Tlist), Flist), tautology(Else, Tlist, .(If, Flist)))).
if3(Mid, Next, New) :- ','(call3(Mid, Next), rewrite(Next, New)).
if3(Mid, Next, New) :- =(New, Mid).
if4(Wff, Flist) :- ','(call4(Wff, Flist), fail).
if5(If, Tlist, Then, Flist, Else) :- ','(call5(If, Tlist), tautology(Then, Tlist, Flist)).
if5(If, Tlist, Then, Flist, Else) :- if6(If, Flist, Else, Tlist).
if6(If, Flist, Else, Tlist) :- ','(call6(If, Flist), tautology(Else, Tlist, Flist)).
call1(Wff, Tlist) :- truep(Wff, Tlist).
call2(Wff, If, Then, Else) :- =(Wff, if(If, Then, Else)).
call3(Mid, Next) :- equal(Mid, Next).
call4(Wff, Flist) :- falsep(Wff, Flist).
call5(If, Tlist) :- truep(If, Tlist).
call6(If, Flist) :- falsep(If, Flist).
fail :- failure(a).
failure(b).
=(X, X).
write(X0).
nl.
atomic(X0).
functor(X0, X1, X2).
arg(X0, X1, X2).
statistics(X0, X1).


Query: tautology(g)