Section 1.4 Predicate Logic
59
and then put the quantifiers back in. The new rules of inference provide mechanisms to strip off and insert quantifiers. Hence there are four new rules—one each
to strip off the universal and existential quantifier, respectively, and one each to
insert the universal and existential quantifier, respectively. The four rules are given
in Table 1.17; their details will be explained shortly. In Table 1.17, the notation P(x)
does not imply that P is a unary predicate with x as its only variable; it simply
means that x is one of the variables in the predicate P. Thus P(x) might actually be
something like (E y)(4z)Q(x, y, z).
Table 1.17
Inference Rules
From
Can Derive
Name/abbreviation for Rule
Restrictions on Use
(4x)P(x)
P(t), where t is a variable or
constant symbol
Universal instantiation—ui
If t is a variable, it must not fall
within the scope of a quantifier
for t.
(E x)P(x)
P(a) where a is a constant
symbol not previously used
in proof sequence
Existential instantiation—ei
Must be the first rule used that
introduces a.
P(x)
(4x)P(x)
Universal generalization—ug
P(x) has not been deduced from
any hypotheses in which x is a
free variable nor has P(x) been
deduced by ei from any wff in
which x is a free variable.
P(x) or P(a)
where a is
a constant
symbol
(E x)P(x)
Existential generalization—eg
To go from P(a) to (E x)P(x), x must
not appear in P(a).
Now let’s examine these rules more closely, particularly the necessity for their
restrictions.
Universal Instantiation
The universal instantiation rule says that from (4x)P(x) we can derive P(x),
P( y), P(z), P(a), and so on, thus stripping off a universal quantifier. The justification is that if P is true for every element of the domain, we can name such an element by an arbitrary variable name like x, y, or z, or we can specify a particular
constant in the domain, and P is still true for all of these things.
eXaMPle 26
Universal instantiation can be used to prove one of the classical “syllogisms” of
the Greek philosopher and scientist Aristotle, who lived from 384 to 322 b.c.e. and
who first developed a system of formal logic.
The argument has the form, “All humans are mortal. Socrates is human. Therefore Socrates is mortal.” Using the notation
H(x) is “x is human.”
s is a constant symbol (Socrates)
M(x) is “x is mortal.”
59
and then put the quantifiers back in. The new rules of inference provide mechanisms to strip off and insert quantifiers. Hence there are four new rules—one each
to strip off the universal and existential quantifier, respectively, and one each to
insert the universal and existential quantifier, respectively. The four rules are given
in Table 1.17; their details will be explained shortly. In Table 1.17, the notation P(x)
does not imply that P is a unary predicate with x as its only variable; it simply
means that x is one of the variables in the predicate P. Thus P(x) might actually be
something like (E y)(4z)Q(x, y, z).
Table 1.17
Inference Rules
From
Can Derive
Name/abbreviation for Rule
Restrictions on Use
(4x)P(x)
P(t), where t is a variable or
constant symbol
Universal instantiation—ui
If t is a variable, it must not fall
within the scope of a quantifier
for t.
(E x)P(x)
P(a) where a is a constant
symbol not previously used
in proof sequence
Existential instantiation—ei
Must be the first rule used that
introduces a.
P(x)
(4x)P(x)
Universal generalization—ug
P(x) has not been deduced from
any hypotheses in which x is a
free variable nor has P(x) been
deduced by ei from any wff in
which x is a free variable.
P(x) or P(a)
where a is
a constant
symbol
(E x)P(x)
Existential generalization—eg
To go from P(a) to (E x)P(x), x must
not appear in P(a).
Now let’s examine these rules more closely, particularly the necessity for their
restrictions.
Universal Instantiation
The universal instantiation rule says that from (4x)P(x) we can derive P(x),
P( y), P(z), P(a), and so on, thus stripping off a universal quantifier. The justification is that if P is true for every element of the domain, we can name such an element by an arbitrary variable name like x, y, or z, or we can specify a particular
constant in the domain, and P is still true for all of these things.
eXaMPle 26
Universal instantiation can be used to prove one of the classical “syllogisms” of
the Greek philosopher and scientist Aristotle, who lived from 384 to 322 b.c.e. and
who first developed a system of formal logic.
The argument has the form, “All humans are mortal. Socrates is human. Therefore Socrates is mortal.” Using the notation
H(x) is “x is human.”
s is a constant symbol (Socrates)
M(x) is “x is mortal.”