"Making the Transition to First-Order Logic"
We want to be able to state rules that apply to whole classes of objects.
We want to be able to make statements about existence of particular objects or kinds of objects.
We want a richer realm of inference-making methods.
These inferences can be performed
by a computer.
"Every murderer is guilty.
Claythorne is a murderer"
How can we represent these to permit us to prove "Claythorne is guilty" ?
Possible atomic propositions
P1: Every murderer is guilty.
P2: Claythorne is a murderer.
P3: Claythorne is guilty.
P4. X is a murderer.
P5. X is guilty.
The following syllogism is valid...
1. P2 -> P3
2. P2
therefore
P3
Suppose we add P6: "Armstrong is
a murderer".
We cannot prove Armstrong is guilty
unless we add
"If Armstrong is a murderer then
Armstrong is guilty".
To take advantage of the knowledge
that every murderer is guilty,
we need to "get inside" the proposition
and use variables.
Predicate Calculus Syntax
Any formula of the propositional calculus is also a formula of the predicate calculus.
However, the atomic propositions can take on an additional form: a predicate symbol followed by one or more arguments in parentheses.
P(x, a, f(x))
Each argument is represented by a term.
A term is either a variable, a constant, or a function of one or more terms.
If F is a formula of the predicate
calculus, then the following are also formulas:
Forall x F
Exists x F
Informal interpretation:
Thirteen is a prime number and
the square of every prime number greater than two is odd.
For the example:
1. domain: the integers
2. constant a: 13.
3. function f: f(x) = x^2
4. predicates: P: {(2), (3), (5),
(7), (11),... } i.e., primes; Q: {(3), (4), (5), (6), ... } i.e., numbers
greater than 2; R: { (1), (-1), (3), (-3), ... }, i.e., odd numbers.
We can easily combine them into
one formula by ANDing them together.
F1 ^ F2 ^ ... ^ Fn
It is customary, however, to talk
about a set of formulas, even though what is usually meant is the conjunction
of them.
Suppose M is an interpretation that satisfies every member of S.
Then M is a model for S.
Let S = { P(a), Forall x (P(x) -> Q(x)) }
Take domain = { John, Mary, James
}
constant a = John
predicates P(x) iff x is a male, i.e., {(John), (James) }
Q(x) iff the name of x starts with J, i.e., {(John), (James)}
This interpretation satisfies P(a)
because John is a male.
It also satisfies Forall x (P(x)
-> Q(x)) because every male in the domain has a name that begins
with J.
Therefore, this interpretation is
a model for S.
A set S of formulas is inconsistent iff every interpretation of S fails to satisfy at least one formula in S.
An inconsistent formula (one that has no model) is called a contradiction.
A formula for which every interpretation is a model is called a tautology.
A formula for which at least one
model exists but not all interpretations are models is called a satisfiable
nontautology.
Term substitution as a means of inference
P(x)
substitute any term for variable
x.
P(a)
Note that P(x) here is assumed
to by universally quantified.
Example: Show that S = { ~P(f(y), P(x) } is inconsistent.
Substitute f(y) for x in P(x) to
get P(f(y))
Now P(f(y)) and ~P(f(y)) are opposites.
No single interpretation can satisfy both of them. Therefore, S has
no model.
Last modified: October 19, 1998
Steve Tanimoto