Lecture Seventeen: The Logic of
Quantifiers
Philosophy 202
|
|
I. Announcements
A.
Questions? II. Logical Equivalences involving
Negation and Quantifiers
A.
DeMorgan
Laws for Quantifiers
1.
When
studying ¬,
Ù, and
Ú, we noticed that there exist certain
equivalences between expression types involving one connective and ¬
and expression types involved the other connective and the negation.
a.
These
were given as DeMorgan's Laws for Conjunction and
Disjunction:
i.
¬(P
Ù Q)
Û (¬P
Ú ¬Q)
ii.
¬(P
Ú Q)
Û (¬P
Ù ¬Q)
b.
(i) says that a conjunction is
false iff one of its conjuncts is false; (ii) says
that a disjunction is false if and only if both disjuncts
are false.
2.
Now,
if you're given a world and asked to claim that each of the objects in that
world are P (assuming all have names) using only propositional logic,
you would say something like
i.
P(a)
Ù P(b)
Ù P(c)
Ù ... If asked to claim that there was at
least one object in the world that was P in propositional logic, it
would look like: ii. P(a)
Ú P(b)
Ú P(c)
Ú ...
a.
If
you denied these claims, you'd get:
i.
¬(P(a)
Ù P(b)
Ù P(c)
Ù ...)
ii.
¬(P(a)
Ú P(b)
Ú P(c)
Ú ...)
b.
By
DeMorgan's Laws for Conjunction and Disjunction,
these become:
i.
¬P(a)
Ú ¬P(b)
Ú ¬P(c)
Ú ...
ii.
¬P(a)
Ù ¬P(b)
Ù ¬P(c)
Ù ...
c.
These
last two, however, are just the claim that there is an object that isn't P
and that all objects aren't P, respectively.
3.
We
don't have the resources to actually make these general claims in
propositional logic, though. Once we
have quantifiers we can. In predicate
logic, we can fill out the ellipses, so to speak, and express the above
claims as follows:
a.
(2.i)
and (2.ii) become:
i.
"x
P(x)
ii.
$x
P(x)
b.
(2.a.i)
and (2.a.ii) become:
i.
¬"x P(x)
ii.
¬$x P(x)
c.
(2.b.i)
and (2.b.ii) become:
i.
$x
¬P(x)
ii.
"x
¬P(x)
4.
Given
that we have used quantifiers to translate the conjunctive and disjunctive
claims into predicate logic, we have DeMorgan's
Laws for Quantifiers that parallel those for conjunction and
disjunction. They are:
a.
¬"xP(x)
Û
$x¬P(x)
b.
¬$xP(x)
Û
"x¬P(x)
5.
These
allow us to push a negation past a quantifier by switching quantifiers, a
move made plausible by DeMorgan's Laws for
Conjunction and Disjunction and relations between conjunction and universal
quantification and between disjunction and existential quantification. III. The Logic of Quantifiers
A.
Recall
that in developing propositional logic, we discussed ways in which the
structure of complex sentences can constrain the truth conditions of those
sentences. In particular, we talked of
tautologies, logical truths, TT-possible sentences, and contradictions. These were explained relative to the
structural elements of propositional logic.
The question before us now is this: are there similar notions for
predicate logic? The short answer:
yes.
B.
Sentences
1.
Tautologies
& Contradictions
a.
Tautologies
remain sentences whose truth value is set at “T” by their complex, connective
structure. We will call this the truth-functional
form of the sentence, where this is tied to the truth functions that
figure into the sentence, viz., the connectives (p.
261).
b.
Contradictions
will also be determined by the truth-functional form of sentences.
c.
Quantifiers
don’t figure into this, nor do any connectives that fall within the scope of
quantifiers. To identify tautologies
in predicate logic, you must treat all quantified sentences as if they were
atomic sentences.
d.
To
get at the truth-functional form of a sentence in a way that is sensitive to
quantifiers, we will use the truth-functional form algorithm (TFFA),
which will enable us to determine if a given FOL sentence is a
tautology. The algorithm goes like
this:
i.
Move
to the right from the beginning of the sentence. When you come to a quantifier, underline
the quantifier and all that lies within its scope.
ii.
When
you come to an atomic sentence, underline it.
iii.
Give
each underlined sentence a letter name (e.g., A, B, C, ...) Be sure to assign the same letter to a
sentence if it appears more than once as a component of the sentence in
question.
iv.
Replace
each underlined sentence with its name.
This yields the truth-functional form of the sentence, which
you can then evaluate to determine whether or not it is a tautology.
e.
This
does reveal tautologies in predicate logic, but it does not reveal all the
logical truths. For that, we must
forge ahead.
2.
Logical
Truths
a.
As
before, these are determined by the atomic structure of a sentence, where
this might involve relationships among interpreted predicates, or logical
relationships grounded in the nature of the quantifiers.
b.
There
is a new term that applies here: First-order validity. This is a first-order logical truth whose
truth is guaranteed by the nature of the quantifiers, identity, and the
connectives (p. 267). NB: ‘validity’ is used here in a new and
different way, as a property of sentences and not arguments.
i.
Aside from identity, no predicate is involved,
so interpretations are irrelevant.
ii.
Identity
is included because it is a part of almost all first-order languages.
c.
Because
FO validity is insensitive to interpreted predicates and there are sentences
that are logical truths because of their interpreted predicates, the class of
FO validities will be a sub-class of the class of logical truths.
Compare: ¬$xLeftOf(x,x)
with
"xCube(x)
® Cube(a).
d.
We
can distinguish these using the replacement method (RM), which aids us
in checking for FO validities. Here is
how this method works:
i.
Replace
all predicates (except identity) and all function symbols with meaningless
symbols. Replace all tokens of the
same predicate symbols and function symbols with the same new symbol.
ii.
Try
to give the new predicates meanings under which the sentence is false; if
this is possible, then the sentence is not a FO
validity.
e.
This
method requires creativity. No monkey can successfully wield this
method! It does test for FO validity,
but there will be logical truths that slip through the net, viz., sentences
that cannot possibly be false because of the specific interpretations of the
predicates.
3.
The
Skinny: If S is a tautology, then it is a FO validity; if S is a FO validity, then it is a
logical truth. But the converses of
these do not hold.
C.
Equivalences
1.
Tautological
Equivalence: Sentences
are tautologically equivalent when their equivalence is underwritten by their
complex, connective structure. In
predicate logic, this amounts to saying that two sentences are equivalent
when they have the same truth-functional form. (Use TFFA to determine this.) Sentences can fail to be tautologically
equivalent and still be FO equivalent.
2.
FO
Equivalence: Sentences
are FO equivalent when their equivalence is underwritten by their atomic
syntactic structure, independently of any specific interpretations other than
identity. If RM reveals that the
sentences have the same structure at this level, they are FO equivalent.
Sentences can fail to be FO equivalent and still be logically equivalent.
3.
The
Skinny: If P
and Q are tautologically equivalent, they are FO equivalent, and if
they are FO equivalent, they are logically equivalent; however, the converses
of these do not hold.
D.
Consequence
1.
Tautological
Consequence: A
sentence is a tautological consequence of some premises if it follows from
them simply in virtue of its complex, connective structure. That is, it must follow from the premises
when all have been rewritten with the help of TFFA. A sentence can fail to be a tautological
consequence and still be an FO consequence.
2.
FO
Consequence: A
sentence is a FO consequence of some premises if it follows from them simply
in virtue of the meanings of the connectives, the quantifiers, and the
predicate identity.
a.
We
use RM to determine this.
b.
In
addition, we use RM to determine a first-order counterexample. We no longer
have the truth tables to help us, so we must be more creative. No monkeys allowed!
3.
The
Skinny: If S is
a tautological consequence of some premises, then it is an FO consequent; if
it is an FO consequent, then it is a logical consequent; however, the
converses of these do not hold.
E.
The
Table:
|