First-order Predicate Calculus
First-order predicate calculus classifies the different parts of logical statements as follows:
- Constants.
Sometimes, they are called atoms, since they cannot be broken down into subparts.
For the previous slide, 0 is a constant.
- Predicates.
These are names for functions that are true or false.
For the previous slide, the function
natural is a predicate.
- Functions.
They are all other functions, like
successor in the previous slide, which represent non-Boolean values.
- Variables.
They are as yet unspecified quantities.
In the previous slide,
x is a variable.
- Connectives.
They include the operations
and, or, and not.
Additional connectives in predicate calculus are
- Implication ‘→’:
a→b means that b is true whenever a is, and this is equivalent to the statement “b or not a.”
- Equivalence ‘↔’:
a↔b means the same as (a→b) and (b→a).
- Quantifiers.
These are operations that introduce variables.
- Universal quantifier:
∀ stands for “for all.”
- Existential quantifier:
∃ stands for “there exists.”
A variable introduced by a quantifier is said to be bound by the quantifier.
Variables are free if they are not bound by any quantifier.
- Punctuation symbols.
These include left and right parentheses, the comma, and the period.
Arguments to predicates and functions can only be terms, that is, combinations of variables, constants, and functions.
Terms cannot contain predicates, quantifiers, or connectives.