text: My dissertation Fully Countering Trusting Trust through Diverse Double-Compiling section 5.2 gives a brief summary of FOL in 5.2. In short, in FOL, every expression is a term or a formula. A term (which denotes an object) is defined as: a variable, a constant, or a function application of form f(...) where each of the zero or more comma-separated parameters is a term. A formula (which denotes a truth value of true or false) is defined as being one of the following (if both A and B are formulas):
  There are endless books and pages on FOL; a good library and/or a web search should get you started. “forall x: An introduction to Formal Logic” by P.D. Magnus is an open access introductory textbook in formal logic.
  Unfortunately, FOL has some real weaknesses that are easily extended, but many mathematicians don’t seem to realize that they are weaknesses. For example, you can’t define “if-then-else” easily in FOL. FOL has two “types”: formula (essentially booleans) and terms (everything else). You can define a multi-parameter object that returns a boolean (Predicate) or a term (function), but all parameters have to be terms (non-booleans) - and if-then-else inherently takes a boolean! This email notes why it’s important to add if-then-else for practical languages.
  Prover9/Mace4 (GPLv2+ license) is a really neat combination of tools. Prover9 can be used to search for a proof, and mace4 can be used to search for a counter-example, which is an interesting combination. Prover9’s language is limited (it’s basically FOL), but if you can express your problem using its language, it’s extraordinarily good at automatically finding proofs or counter-examples. Prover9 includes support for equality and lists, and generally it has a "nice" syntax that's faily close to textbook formats (making it easy to use).
  Prover9 is a "theorem prover" that works in a way similar to many other provers. First, it negates the "goal" statement (the idea is that you're trying to prove that there's some contradiction). Then, it tries to generate all possible facts from this set of assumptions (including the negated goal statement), until it finds a contradiction. Obviously, this is not the way that a human would work, but that's okay if you're simply trying to find out if something is true given certain assumptions. This works primarily because computers are remarkably fast, and the developers of prover9 (and other such programs) have honed heuristics that work in many cases.
  Mace4 and prover9 include limited support for integer arithmetic. In Mace4 you can turn on arithmetic support with set(arithmetic), and it's fairly capable. Historically, prover9 couldn't handle arithmetic at all, but as of 2008-2009 its "production mode" can do this (use set(production) to turn this on). However, production mode disables many of prover9's other capabilities so this is much more limited (for example, it won't show the rewrites in the output). Many problems don't require calculation, and these limited capabilities may be sufficient for some problems that do. Prover9 has also recently added an if(boolean,if-term,else-term), which is very convenient but again has limitations. If your problem focuses on in-depth arithmetic calculations, prover9 is probably not the tool for you.
  Prover9 is easy to invoke; just say “prover9 -f FILE.in” on the command line, where FILE.in gives the assumptions and goal to be proved. The prover9 documentation doesn’t describe its input format very clearly; here’s my attempt at documenting the prover9 formula syntax (in BNF).
  There’s a paucity of small, simple examples of prover9 in use. It's hard to be simpler than mortal.in, which is the "Socrates is mortal" proof in prover9 syntax.
  Here’s the proof that the square root of 2 is irrational, as prover9 input and prover9 output. (This is a translation of the Otter proof from Larry Wos, by Michael Beeson and William McCune, as published in “The Seventeen Provers of the World” compiled by Freek Wiedijk). Here’s the square root of 2 proof, as a graphic.
  The “distinct” predicate is useful all by itself, because “distinct” makes it easy to declare that a collection of terms are all different. Basically, “distinct” accepts a list of terms, and then declares that every term is different from all the other terms. For example, you can then state that a, b, c, and d are all different by stating “distinct([a,b,c,d]).”. This is also a useful example of how to do recursive list-handling in prover9.
  Note: due to technical issues in prover9, if you include this definition of "distinct" in your assumptions but you never use it, then you may get a misleading message. If prover9 can find a proof but "distinct" is not used, it may output "SEARCH FAILED" followed by "Exiting with 1 proof" (or some other number). In such cases, prover9 did find a proof, but thought it had to keep searching.
  Unfortunately, FOL doesn’t have any built-in notion of type, so programs like prover9 that implement FOL don’t have types either. You can implement types in prover9, using FOL; whether or not you should do this depends on your problem. If you add types where they aren’t needed, then the assumptions, goal, and proof may become much more complicated. In my dissertation I decided to discuss types in the informal text, but not use them in the actual proof. A trivial way to implement types is to simply make a predicate that is true if the object is a given type, e.g.:
  If there are only two types, then it’s easy to declare that if something is of one type, then it’s not of the other type. Here, we declare that any unknown X cannot be both a human and a penguin:
  That doesn’t scale well to many types if you want to make claims about many types. If you have 30 different types, and an item is at most one of those types, it’d be a pain to directly declare that the same way. Thankfully, you can then use recursion (just like the “distinct” predicate above) to declare that instances of different types are themselves distinct. The file distinct_types.in shows how to do this.
  You can even define that certain types are subclasses of other classes, and so on, but again, you have to build that yourself. The file classes.in is a trivial example.
  File distinct_classes.in demonstrates how to implement partitioned superclasses and subclasses (in a hierarchy), instances of types, and various facts about them using in prover9's first-order logic (FOL).
  My dissertation Fully Countering Trusting Trust through Diverse Double-Compiling has some additional examples of using prover9.