Skip to content
jalivertPublic

About

A toy Automated Theorem Prover for First Order Classical Logic built on Resolution.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Latest commit

 

History

12 Commits

Folders and files

Repository files navigation

Resin

Haskell CI

An implementation of a toy automated theorem prover for classical FOL built on resolution.

Background

This project is a direct implementation of the material presented in the two texts listed under Resources below. The resolution machinery follows the Handbook of Practical Logic and Automated Reasoning, supplemented by background from Artificial Intelligence: A Modern Approach (chapters 7–9); the structure of the implementation reflects those texts.

What does this project implement?

The prover is based on a given clause algorithm for resolution; see the Resources section for the relevant references.

The Handbook describes several optimizations as well as specific forms of resolution. Those specific forms are not (yet) implemented here. The optimization it mentions — subsumption — is implemented, but it made the prover unbearably slow in practice, so it is currently disabled.

Structure of the Files

For more examples, look into the examples directory.

The Resin files are meant to have a .rin extension. They might look something like the following snippet:

constants: zero .

aliases: 0 = zero
       , 1 = suc(0) .

axioms: ∀ n (Nat(n)) ==> Nat(suc(n))
      , (zero-is-nat: Nat(0)) .

theorem 1-is-nat: Nat(1) .

theorem some-nats : ∃ n Nat(n) . using { zero-is-nat }

theorem prop-modus-tollens: A ==> B
                          , ¬B
                          ⊢ ¬A .

theorem double-prop-modus-ponens: (a-b: A ==> B)
                                , B ==> C
                                , (a: A)
                                ⊢ C
proof: lemma have-b: B using { a-b, a }
     , lemma have-c: C
     . using { have-c }

The syntax is quite simple. A file is split into three parts:

  • constants—so that you don't have to write zero() and so on,

  • aliases—a list of non-recursive lexical rewrite rules,

  • axioms—those formulae will be available to all the theorems in the file,

  • theorems—in general, they are in the shape of entialment but you can omit the assumptions part if there aren't any. Theorems can have semi-automatic proofs. A proof is a sequence of assertions, those are named or un-named statements that state that a certain formula is logically valid. Assertions can have using { } clause that specifies which axioms, theorems, and previous assertions can be used to prove this one. Theorems can also have using { } clause that does the same for the conclusion. When it comes to checking the conclusion of the theorem, assumptions are always included even when the using { } clause is present.

All the first three sections must either define one or more constants, axioms or aliases or not be there at all.

Syntax

The snippet above uses a few unicode characters. You don't have to use those, the following shows the groups of symbols with the same meaning:

Unicode ASCII
∀ forall
∃ exists
⊤ True, Tautology
⊥ False, Contradiction
∧ AND, &&
∨ OR, ||, |
¬ NOT
⟹ ==>, =>
⟺ <=>, <==>

Identifiers

Resin differentiates between two types of identifiers—the ones used mainly for object variables and the ones used for propositional variables and for functions.

All variables can contain a few special symbols. However, those special symbols may only come after a letter. The special symbols are: -, _, and '. The variable identifiers may technically start with a digit character (this is useful for the theorem names).

When we write ∀ x P(f(x)), the x is an object variable, the P is a propositional variable (or rather a constant) and the f is a function constant.

The object variables need to begin with a lower-case letter and the propositional variables (names for relations) need to begin with an upper-case letter.

Usually, functions share the lexical requirements with object variables—they start with a lower-case letter.

When it comes to constants the situation is a little bit more relaxed—a function or a constant defined beforehand (in the constants section) can start with both, lower-case and upper-case letters. In such a case, however, a constant must not be written lexically like a nullary function!

There is one more way to modify this behavior—to make writing function identifiers and constants starting with both lower-case and capital-case letters possible and also easier. There is a special character ᶜ that can be written at the end of an identifier that starts with any letter. This makes that identifier be recognized as a constant or a function, depending on the situation, even without it being defined beforehand.

Example: ∃ x Prop(x, Sucᶜ(Zeroᶜ))

This can be especially useful in the REPL where you can't write a constants section. It also makes upper-case functions possible at all.

Aliases

Only quite restricted alias definitions are allowed. A valid alias is a constant which means it does not have an argument list at the use site—they must be fully applied. At the use site, aliases can not go with the ᶜ modifier as that would not make sense. Aliases can be numbers.

Numbers

To make some propositions look nicer Resin also supports numbers as constant symbols. In files, they can be defined in the constants section, like this: constants: 1, 2, 3 .... In the REPL one can also use the ᶜ trick like so: 0ᶜ.

Quantifiers

If there's a sequence of the same kind of quantifier like ∀ x ∀ y ∀ z ... you can shorten it to just ∀ x y z ....

Usage

To build and run, type cabal build and cabal run.

The Interface of the REPL

  1. To check all the theorems in a file, type :check <file-path>.

The prompt has the shape of an entailment, that is by design.

  1. To assert that a particular formula ƒ is an assumption, type :assume <ƒ>.

The prompt is kept short for convenience.

  1. To print all the assumptions, type :show.

  2. To see if a formula ƒ is entailed by the current set of assumptions, type :entails <ƒ> or just enter the formula directly. That is why the prompt has that shape.

  3. To check that the current set of assumptions is consistent (does not contain a contradiction), type :consistent.

  4. To reset the current set of assumptions back to ⊤, type :clear.

There are also a few commands for a simple transformation on formulae.

  1. To put a formula ƒ into a Negation Normal Form, type :nnf <ƒ>.

  2. To put a formula ƒ into a Prenex Normal Form, type :pnf <ƒ>.

  3. To put a formula ƒ into a Skolem Normal Form, type :skolemize <ƒ>.

  4. To put a propositional formula ƒ into a Conjunction Normal Form, type :cnf <ƒ>. However, be aware that this will only really work when the formula does not contain existential quantifiers. Those require skolemization and that leads to only equisatisfiable not equivalent formulae. The tool will complain a bit but it will produce the equisatisfiable formula for the input.

Q&A

Q: Why does this exist?

A: For me, to learn about things, to implement those things (to make sure I learned them right), and to write about them (to make sure that I really got it right), and also to share the experience, knowledge and fun of it.

Resources

  1. Handbook of Practical Logic and Automated Reasoning, accompanied by informal reading notes on the text.

  2. Artificial Intelligence: A Modern Approach, accompanied by informal reading notes on the text.

The first book is where the source code comes from. It has been only slightly modified to end up being as close to the book's implementation as possible while having a slightly different approach. The book seems to be using the resolution to prove or rather find contradictions in a single formula. This tool handles statements in the form of a logical entailment.

The second book's chapters 7 - 9 contain a lot of information. The whole book is a good starting place for beginners in the topic, however, sometimes the book does not go into much detail regarding some operations—one must use a different resource for that, perhaps the first book.

In a future, I might write a short write-up about the implementation, all the differences between the code in the book and the one here and how the "trick" from the second book (to produce constructive proofs if applicable) fits into the framework.

Special Note: The code from the first book seems to not be handling situations where a contradiction (as a formula) is already a part of the original formula. In such cases it seems to me that the cl pattern-variable in the function res'loop becomes an empty list (empty disjunction, that is equivalent to ⊥). In those cases the set of resolvents is empty and therefore we don't recognise it as a place to stop. It is clear to me, however, that we should terminate with a found contradiction right at this moment. I will look more into it, hopefully later.

About

A toy Automated Theorem Prover for First Order Classical Logic built on Resolution.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Contributors

Languages