<< Предыдущая стр. 49(из 107 стр.)ОГЛАВЛЕНИЕ Следующая >>

10.4 в€Ђx Cube(x) в†’ в€ѓy Small(y)
 В¬в€ѓy Small(y)
В¬в€Ђx Cube(x)

10.5 в€Ђx (Tet(x) в†’ LeftOf(x, b)) в€Ё в€Ђx (Tet(x) в†’ RightOf(x, b))
 в€ѓx (Tet(x) в€§ SameCol(x, b)) в†’ В¬в€Ђx (Tet(x) в†’ LeftOf(x, b))
в€Ђx (Tet(x) в†’ RightOf(x, b)) в†’ В¬в€ѓx (Tet(x) в€§ SameCol(x, b))
В¬в€ѓx (Tet(x) в€§ SameCol(x, b))

10.6 в€ѓx (Cube(x) в€§ Large(x)) в†’ (Cube(c) в€§ Large(c))
 Tet(c) в†’ В¬Cube(c)
Tet(c)
в€Ђx В¬(Cube(x) в€§ Large(x))

Section 10.1
266 / The Logic of Quantifiers

10.7 в€ѓx (Cube(x) в€§ Large(x)) в†’ (Cube(c) в€§ Large(c))
 в€Ђx В¬(Cube(x) в€§ Large(x)) в†” В¬в€ѓx (Cube(x) в€§ Large(x))
Tet(c) в†’ В¬Cube(c)
Tet(c)
в€Ђx В¬(Cube(x) в€§ Large(x))

[In 10.6 and 10.7, we could think of the п¬Ѓrst premise as a way of introducing a new constant, c, by
means of the assertion: Let the constant c name a large cube, if there are any; otherwise, it may name
any object. Sentences of this sort are called Henkin witnessing axioms, and are put to important use
in proving completeness for F. The arguments show that if a constant introduced in this way ends up
naming a tetrahedron, it can only be because there arenвЂ™t any large cubes.]

Section 10.2
First-order validity and consequence
When we п¬Ѓrst discussed the intuitive notions of logical truth and logical con-
sequence, we appealed to the idea of a logically possible circumstance. We
described a logically valid argument, for example, as one whose conclusion is
true in every possible circumstance in which all the premises are true. When
we needed more precision than this description allowed, we introduced truth
tables and the concepts of tautology and tautological consequence. These
concepts add precision by modeling possible circumstances as rows of a truth
table. We have seen that this move does a good job of capturing the intu-
itive notions of logical truth and logical consequenceвЂ”provided we limit our
attention to the truth-functional connectives.
Unfortunately, the concepts of tautology and tautological consequence
donвЂ™t get us far in п¬Ѓrst-order logic. We need a more reп¬Ѓned method for ana-
lyzing logical truths and logically valid arguments when they depend on the
quantiп¬Ѓers and identity. We will introduce these notions in this chapter, and
develop them in greater detail in Chapter 18. The notions will give us, for
п¬Ѓrst-order logic, what the concepts of tautology and tautological consequence
gave us for propositional logic: precise approximations of the notions of logical
truth and logical consequence.
First, a terminological point. It is a regrettable fact that there is no single
term like вЂњtautologicalвЂќ that logicians consistently use when applying the
various logical notions to п¬Ѓrst-order sentences and arguments. That is, we
donвЂ™t have a uniform way of п¬Ѓlling out the table:

Chapter 10
First-order validity and consequence / 267

Propositional logic First-order logic General notion
Tautology ?? Logical truth
Tautological consequence ?? Logical consequence
Tautological equivalence ?? Logical equivalence
One option would be to use the terms п¬Ѓrst-order logical truth, п¬Ѓrst-order
logical consequence, and п¬Ѓrst-order logical equivalence. But these are just too
much of a mouthful for repeated use, so we will abbreviate them. Instead of
п¬Ѓrst-order logical consequence, we will use п¬Ѓrst-order consequence or simply п¬Ѓrst-order consequence
FO consequence, and for п¬Ѓrst-order logical equivalence, weвЂ™ll use п¬Ѓrst-order
(or FO) equivalence. We will not, however, use п¬Ѓrst-order truth for п¬Ѓrst-order
logical truth, since this might suggest that we are talking about a true (but
not logically true) sentence of п¬Ѓrst-order logic.
For п¬Ѓrst-order logical truth, it is standard to use the term п¬Ѓrst-order va-
lidity. This may surprise you, since so far weвЂ™ve only used вЂњvalidвЂќ to apply п¬Ѓrst-order validity
to arguments, not sentences. This is a slight terminological inconsistency, but
it shouldnвЂ™t cause any problems so long as youвЂ™re aware of it. In п¬Ѓrst-order
logic, we use valid to apply to both sentences and arguments: to sentences
that canвЂ™t be false, and to arguments whose conclusions canвЂ™t be false if their
premises are true. Our completed table, then, looks like this:

Propositional logic First-order logic General notion
Tautology FO validity Logical truth
Tautological consequence FO consequence Logical consequence
Tautological equivalence FO equivalence Logical equivalence
So what do we mean by the notions of п¬Ѓrst-order validity, п¬Ѓrst-order con-
sequence and п¬Ѓrst-order equivalence? These concepts are meant to apply to
those logical truths, consequences, and equivalences that are such solely in
virtue of the truth-functional connectives, the quantiп¬Ѓers, and the identity
symbol. Thus, for purposes of determining п¬Ѓrst-order consequence, we ignore
the speciп¬Ѓc meanings of names, function symbols, and predicates other than
identity.
There are two reasons for treating identity along with the quantiп¬Ѓers and identity
connectives, rather than like any other predicate. The п¬Ѓrst is that almost
all п¬Ѓrst-order languages use =. Other predicates, by contrast, vary from one
п¬Ѓrst-order language to another. For example, the blocks language uses the
binary predicate LeftOf, while the language of set theory uses в€€, and the
language of arithmetic uses <. This makes it a reasonable division of labor to
try п¬Ѓrst to understand the logic implicit in the connectives, quantiп¬Ѓers, and
identity, without regard to the meanings of the other predicates, names, and

Section 10.2
268 / The Logic of Quantifiers

function symbols. The second reason is that the identity predicate is crucial for
expressing many quantiп¬Ѓed noun phrases of English. For instance, weвЂ™ll soon
see how to express things like at least three tetrahedra and at most four cubes,
but to express these in fol we need identity in addition to the quantiп¬Ѓers в€Ђ
and в€ѓ. There is a sense in which identity and the quantiп¬Ѓers go hand in hand.
If we can recognize that a sentence is logically true without knowing the
meanings of the names or predicates it contains (other than identity), then
weвЂ™ll say the sentence is a п¬Ѓrst-order validity. LetвЂ™s consider some examples
from the blocks language:

в€Ђx SameSize(x, x)
в€Ђx Cube(x) в†’ Cube(b)
(Cube(b) в€§ b = c) в†’ Cube(c)
(Small(b) в€§ SameSize(b, c)) в†’ Small(c)

All of these are arguably logical truths of the blocks language, but only
the middle two are п¬Ѓrst-order validities. One way to see this is to replace
the familiar blocks language predicates with nonsensical predicates, like those
using nonsense
used in Lewis CarrollвЂ™s famous poem Jabberwocky.1 The results would look
predicates to test for
FO validity something like this:

в€Ђx Outgrabe(x, x)
в€Ђx Tove(x) в†’ Tove(b)
(Tove(b) в€§ b = c) в†’ Tove(c)
(Slithy(b) в€§ Outgrabe(b, c)) в†’ Slithy(c)

Notice that we can still see that the second and third sentences must be
true, whatever the predicate Tove may mean. If everything is a tove, and b is
an object in the domain of discourse, then b must surely be a tove. Similarly,
if b is a tove, and c is the same object as b, then c is a tove as well. Contrast
this with the п¬Ѓrst and fourth sentences, which no longer look logically true
at all. Though we know that everything is the same size as itself, we have no
idea whether everything outgrabes itself! Just so, the fact that b is slithy and
outgrabes c hardly guarantees that c is slithy. Maybe it is and maybe it isnвЂ™t!
1 The full text of Jabberwocky can be found at http://english-server.hss.cmu.edu/ po-
etry/jabberwocky.html. The п¬Ѓrst stanza is:

вЂ™Twas brillig, and the slithy toves
Did gyre and gimble in the wabe;
All mimsy were the borogoves,
And the mome raths outgrabe.

вЂњLewis CarrollвЂќ was the pen name of the logician Charles Dodgson (after whom both
CarrollвЂ™s World and DodgsonвЂ™s Sentences were named).

Chapter 10
First-order validity and consequence / 269

The concepts of п¬Ѓrst-order consequence and п¬Ѓrst-order equivalence work
similarly. For example, if you can recognize that an argument is logically valid
without appealing to the meanings of the names or predicates (other than
identity), then the conclusion is a п¬Ѓrst-order consequence of the premises.
The following argument is an example:

в€Ђx (Tet(x) в†’ Large(x))
В¬Large(b)
В¬Tet(b)

This argument is obviously valid. WhatвЂ™s more, if we replace the predicates
Tet and Large with nonsense predicates, say Borogove and Mimsy, the result
is the following:

в€Ђx (Borogove(x) в†’ Mimsy(x))
В¬Mimsy(b)
В¬Borogove(b)

Again, itвЂ™s easy to see that if the borogoves (whatever they may be) are
all mimsy (whatever that may mean), and if b is not mimsy, then it canвЂ™t
possibly be a borogove. So the conclusion is not just a logical consequence of
the premises, it is a п¬Ѓrst-order consequence.
Recall that to show that a sentence was not a tautological consequence
of some premises, it suп¬ѓced to п¬Ѓnd a truth-value assignment to the atomic
sentences that made the premises true and the conclusion false. A similar pro-
cedure can be used to show that a conclusion is not a п¬Ѓrst-order consequence
of its premises, except instead of truth-value assignments what we look for is
a bit more complicated. Suppose we are given the following argument:

В¬в€ѓx Larger(x, a)
В¬в€ѓx Larger(b, x)
Larger(c, d)
Larger(a, b)

The п¬Ѓrst premise tells you that nothing is larger than a and the second tells you
that b is not larger than anything. If you were trying to build a counterexample
world, you might reason that a must be the largest object in the world (or
one of them) and that b must be the smallest (or one of them). Since the third
premise guarantees that the objects in the world arenвЂ™t all the same size, the
conclusion canвЂ™t be falsiп¬Ѓed in a world in which the premises are true.

Section 10.2
270 / The Logic of Quantifiers

Figure 10.1: A п¬Ѓrst-order counterexample.

Is this conclusion a п¬Ѓrst-order consequence of the premises? To show that
п¬Ѓrst-order
counterexamples itвЂ™s not, weвЂ™ll do two things. First, letвЂ™s replace the predicate Larger with a
meaningless predicate, to help clear our minds of any constraints suggested
by the predicate:

В¬в€ѓx R(x, a)
В¬в€ѓx R(b, x)
R(c, d)
R(a, b)

Next, weвЂ™ll describe a speciп¬Ѓc interpretation of R (and the names a, b,
c, and d), along with a possible circumstance that would count as a coun-
terexample to the new argument. This is easy. Suppose R means likes, and we
are describing a situation with four individuals: Romeo and Juliet (who like
each other), and Moriarty and Scrooge (who like nobody, and the feelings are
mutual).
If we let a refer to Moriarty, b refer to Scrooge, c and d refer to Romeo
and Juliet, then the premises of our argument are all true, though the con-
clusion is false. This possible circumstance, like an alternate truth assignment
in propositional logic, shows that our original conclusion is not a п¬Ѓrst-order
consequence of the premises. Thus we call it a п¬Ѓrst-order counterexample.
LetвЂ™s codify this procedure.
Replacement Method:
replacement method

1. To check for п¬Ѓrst-order validity or п¬Ѓrst-order consequence, systematically
replace all of the predicates, other than identity, with new, meaningless
predicate symbols, making sure that if a predicate appears more than
once, you replace all instances of it with the same meaningless predicate.
(If there are function symbols, replace these as well.)

2. To see if S is a п¬Ѓrst-order validity, try to describe a circumstance, along
with interpretations for the names, predicates, and functions in S, in

Chapter 10
First-order validity and consequence / 271

which the sentence is false. If there is no such circumstance, the original
sentence is a п¬Ѓrst-order validity.

3. To see if S is a п¬Ѓrst-order consequence of P1 , . . . , Pn , try to п¬Ѓnd a cir-
cumstance and interpretation in which S is false while P1 , . . . , Pn are all
true. If there is no such circumstance, the original inference counts as a
п¬Ѓrst-order consequence.
 << Предыдущая стр. 49(из 107 стр.)ОГЛАВЛЕНИЕ Следующая >>