Theorem Prover
An automated theorem prover for first-order predicate logic written in TypeScript. It can prove provable closed formulae by using resolution principle.
How it works
- Let F1 be a closed formula, validity of which is in concern.
- Get formula F2 by negating F1.
- F2 is unsatisfiable if and only if F1 is valid.
- Get formula F3 which is logically equivalent to F2 and does not contain implications.
- F3 is unsutisfiable if and only if F2 is unsatisfiable.
- This is possible using the fact that
A implies B
is logically equivalent to(not A) or B
.
- Get formula F4 which is logically equivalent to F3 and negations in which are pushed inward as much as possible.
- F4 is unsutisfiable if and only if F3 is unsatisfiable.
- Introduce skolem functions to F4 and remove all its quantifiers, let the obtained formula be F5.
- F5 is unsutisfiable if and only if F4 is unsatisfiable.
- By pushsing disjunctions inward as much as possible, we can obtain a formula in CNF from F5. Let it be F6.
- Let the corresponding set of clauses be C.
- Perform resolution refutation on C.
- If the refutation succeeds (that is, if we obtain an empty clause from C by variabe replacements and resolutions), F6 is unsatisfiable. From this, we can say that F1 is valid.
Usage
- Requirements: Node.js (>=10)
$ npm i theorem-prover -g$ theorem-prover
By default, a timeout error is thrown if it takes more than 5 seconds for resolutions. That can be overwritten as follows.
$ THEOREM_PROVER_TIMEOUT=10 theorem-prover
Examples
Provable formulae
$ theorem-prover> implies(forall(x, or(P(x), Q(x))), forall(x, implies(not(P(x)), Q(x))))(∀x0.((P(x0) ⋁ Q(x0))) → ∀x1.((¬(P(x1)) → Q(x1)))) negating¬((∀x0.((P(x0) ⋁ Q(x0))) → ∀x1.((¬(P(x1)) → Q(x1))))) eliminating implications¬((¬(∀x0.((P(x0) ⋁ Q(x0)))) ⋁ ∀x1.((¬(¬(P(x1))) ⋁ Q(x1))))) pushing negations inward(∀x0.((P(x0) ⋁ Q(x0))) ⋀ ∃x1.((¬(P(x1)) ⋀ ¬(Q(x1))))) pushing quantifiers outward∀x0.(∃x1.(((P(x0) ⋁ Q(x0)) ⋀ (¬(P(x1)) ⋀ ¬(Q(x1)))))) skolemizing((P(x0) ⋁ Q(x0)) ⋀ (¬(P(sko0(x0))) ⋀ ¬(Q(sko0(x0))))) pushing disjunctions inward((P(x0) ⋁ Q(x0)) ⋀ (¬(P(sko0(x0))) ⋀ ¬(Q(sko0(x0))))) getting clauses{P(x0), Q(x0)}, {¬P(sko0(x0))}, {¬Q(sko0(x0))} proof found instantiations{P(x0), Q(x0)} -> {P(sko0(_())), Q(sko0(_()))}{¬Q(sko0(x0))} -> {¬Q(sko0(_()))}{¬P(sko0(x0))} -> {¬P(sko0(_()))} resolutions({P(sko0(_())), Q(sko0(_()))}, {¬Q(sko0(_()))}) -> {P(sko0(_()))}({¬P(sko0(_()))}, {P(sko0(_()))}) -> {} > implies(and(forall(x, forall(y, forall(z, implies(A(x, y, z), A(s(x), y, s(z)))))), forall(x, A(z(), x, x))), A(s(z()), s(s(z())), s(s(s(z())))))((∀x0.(∀y0.(∀z0.((A(x0, y0, z0) → A(s(x0), y0, s(z0)))))) ⋀ ∀x1.(A(z(), x1, x1))) → A(s(z()), s(s(z())), s(s(s(z()))))) negating¬(((∀x0.(∀y0.(∀z0.((A(x0, y0, z0) → A(s(x0), y0, s(z0)))))) ⋀ ∀x1.(A(z(), x1, x1))) → A(s(z()), s(s(z())), s(s(s(z())))))) eliminating implications¬((¬((∀x0.(∀y0.(∀z0.((¬(A(x0, y0, z0)) ⋁ A(s(x0), y0, s(z0)))))) ⋀ ∀x1.(A(z(), x1, x1)))) ⋁ A(s(z()), s(s(z())), s(s(s(z())))))) pushing negations inward((∀x0.(∀y0.(∀z0.((¬(A(x0, y0, z0)) ⋁ A(s(x0), y0, s(z0)))))) ⋀ ∀x1.(A(z(), x1, x1))) ⋀ ¬(A(s(z()), s(s(z())), s(s(s(z())))))) pushing quantifiers outward∀x0.(∀y0.(∀z0.(∀x1.((((¬(A(x0, y0, z0)) ⋁ A(s(x0), y0, s(z0))) ⋀ A(z(), x1, x1)) ⋀ ¬(A(s(z()), s(s(z())), s(s(s(z())))))))))) skolemizing(((¬(A(x0, y0, z0)) ⋁ A(s(x0), y0, s(z0))) ⋀ A(z(), x1, x1)) ⋀ ¬(A(s(z()), s(s(z())), s(s(s(z())))))) pushing disjunctions inward(((¬(A(x0, y0, z0)) ⋁ A(s(x0), y0, s(z0))) ⋀ A(z(), x1, x1)) ⋀ ¬(A(s(z()), s(s(z())), s(s(s(z())))))) getting clauses{¬A(x0, y0, z0), A(s(x0), y0, s(z0))}, {A(z(), x1, x1)}, {¬A(s(z()), s(s(z())), s(s(s(z()))))} proof found instantiations{¬A(x0, y0, z0), A(s(x0), y0, s(z0))} -> {¬A(z(), s(s(z())), s(s(z()))), A(s(z()), s(s(z())), s(s(s(z()))))}{¬A(s(z()), s(s(z())), s(s(s(z()))))} -> {¬A(s(z()), s(s(z())), s(s(s(z()))))}{A(z(), x1, x1)} -> {A(z(), s(s(z())), s(s(z())))} resolutions({¬A(z(), s(s(z())), s(s(z()))), A(s(z()), s(s(z())), s(s(s(z()))))}, {¬A(s(z()), s(s(z())), s(s(s(z()))))}) -> {¬A(z(), s(s(z())), s(s(z())))}({A(z(), s(s(z())), s(s(z())))}, {¬A(z(), s(s(z())), s(s(z())))}) -> {}
Unprovable formulae
$ theorem-prover> and(P(), not(P()))(P() ⋀ ¬(P())) negating¬((P() ⋀ ¬(P()))) eliminating implications¬((P() ⋀ ¬(P()))) pushing negations inward(¬(P()) ⋁ P()) pushing quantifiers outward(¬(P()) ⋁ P()) skolemizing(¬(P()) ⋁ P()) pushing disjunctions inward(¬(P()) ⋁ P()) getting clauses{¬P(), P()} cannot be proven > and(exists(x, P(x)), forall(x, not(P(x))))(∃x0.(P(x0)) ⋀ ∀x1.(¬(P(x1)))) negating¬((∃x0.(P(x0)) ⋀ ∀x1.(¬(P(x1))))) eliminating implications¬((∃x0.(P(x0)) ⋀ ∀x1.(¬(P(x1))))) pushing negations inward(∀x0.(¬(P(x0))) ⋁ ∃x1.(P(x1))) pushing quantifiers outward∀x0.(∃x1.((¬(P(x0)) ⋁ P(x1)))) skolemizing(¬(P(x0)) ⋁ P(sko0(x0))) pushing disjunctions inward(¬(P(x0)) ⋁ P(sko0(x0))) getting clauses{¬P(x0), P(sko0(x0))} error: refutation timeout