3 - First-order logic

Summary

We now move from propositional logic to richer first-order logic, where propositions can involve non-propositional variables that may be universally or existentially quantified. We show how proof in first-order logic can be mechanized naively via Herbrand's theorem. We then introduce various refinements, notably unification, that help make automated proof more efficient.

First-order logic and its implementation

Propositional logic only allows us to build formulas from primitive propositions that may independently be true or false. However, this is too restrictive to capture patterns of reasoning where the truth or falsity of propositions depends on the values of non-propositional variables. For example, a typical proposition about numbers is ‘m < n’, and its truth depends on the values of m and n. If we simply introduce a distinct propositional variable for each such proposition, we lose the ability to interrelate different instances according to the variables they contain, e.g. to assert that ¬(m < nΛn < m). Firstorder (predicate) logic extends propositional logic in two ways to accommodate this need:

• the atomic propositions can be built up from non-propositional variables and constants using functions and predicates;

• the non-propositional variables can be bound with quantifiers.

We make a syntactic distinction between formulas, which are intuitively intended to be true or false, and terms, which are intended to denote ‘objects’ in the domain being reasoned about (numbers, people, sets or whatever). Terms are built up from (object-denoting) variables using functions. In discussions we use f(s, t, u) for a term built from subterms s, t and u using the function f, or sometimes infix notation like s + t rather than +(s, t) where it seems more natural or familiar.