The propositional
calculus provides adequate tools for reasoning about propositional wffs, which are combinations of propositions. But a
proposition is a sentence taken as a whole. With this restrictive definition,
propositional calculus doesn't provide the tools to do everyday reasoning. For
example, in the following argument it is impossible to find a formal way to
test the correctness of the inference without further analysis of each
sentence:
All computer
science majors own a personal computer.
Socrates does not
own a personal computer.
Therefore Socrates
is not a computer science major.
To discuss such an
argument, we need to break up the sentences into parts. The words in the set
(All, own, not) are important to understand the argument. Somehow we need to
symbolize a sentence so that the information needed for reasoning is
characterized in some way. Therefore we will study the inner structure of
sentences.
The statement
"x owns a personal
computer" is not a proposition because its truth value depends on x. If we give x a value, like x =
Socrates, then the statement becomes a proposition because it has the value
true or false. From the grammar point of view, the property "owns a
personal computer" is a predicate, where a predicate is the part of a
sentence that gives a property of the subject. A predicate usually contains a
verb, like "owns" in our example. The word predicate comes from the
Latin word praedicare,
which means to proclaim.
From the logic
point of view, a predicate is a relation,
which of course we can also think of as a property. For example, suppose we let
p(x) mean “x owns a personal computer." Then p is a predicate that describes the
relation (i.e., property) of owning a personal computer. Sometimes it's
convenient to call p(x) a predicate,
although p is the actual predicate. If we replace the variable x by some definite value such as
Socrates, then we obtain the proposition p(Socrates).
For another example, suppose that for any two natural numbers x and y we let q(x, y) mean
"x < y" Then q is the
predicate that we all know of as the "less than" relation. For
example, the proposition q(1, 5) is true, and the proposition q(8, 3) is false.
Let p(x) mean
"x is an odd integer." Then
the proposition p(9) is true, and the proposition p(20) is false. Similarly, the following
proposition is true:
.
We can describe
this proposition by saying, "There exists an element x in the set {2, 3, 4, 5} such that p(x) is true." By letting D
= {2, 3, 4, 5} the statement can be shortened to "There exists x Î D such that p(x) is
true." If we don't care about the truth of the statement, then we can
still describe the preceding disjunction by saying, "There exists x Î D such that p(x)"
Still more formally, we can write the expression
$ x Î D: p(x).
Now if we want to consider the truth of the
expression for a different set of numbers, say S, then we would write
$ x Î S: p(x).
This expression
would be true if S contained an odd
integer. If we want to consider the statement without regard to any particular
set of numbers, then we write
$ x p(x).
This expression is not a proposition because
we don't have a specific set of elements over which x can vary. Thus $ x p(x) cannot
be given a truth value. If we don't know what p stands for, we can still say, "There exists an x such that p(x)" The symbol $ x is called an existential
quantifier.
Now let's look at
conjunctions rather than disjunctions. Suppose we have the following
proposition:
.
This conjunction
can be represented by the expression " x Î D: p(x), where D = {1, 3,
5, 7}. We say, "Every x in D is
an odd integer." If we want to consider the statement without regard to
any particular set of numbers, then we write
" x p(x).
The expression " x p(x)
is read, "For every x p(x)".
The symbol " x is called an universal quantifier. Let's see how the
quantifiers can be used together to represent certain statements. If p(x, y) is a predicate and we let the
variables x and y vary over the set D = {0, 1}, then the proposition
![]()
can be represented by
the following expression:
![]()
To see this, notice
that each of the two disjunctions in the proposition can be expressed in the
following form, where x Î D:
![]()
Now we use the
universal quantifier "x to represent the conjunction of the two disjunctions
to obtain the desired expression, as follows:
![]()
.
Now let's go the
other way. We'll start with an expression containing different quantifiers and
try to write it as a proposition. For example, if we use the same set of values
D = {0, 1}, the expression
![]()
denotes the proposition
.
It's easier to see
why this is the case. All we need to do is evaluate the expression as follows:
![]()
.
Of course, not
every expression containing quantifiers results in a proposition. For example, if D = {0, 1}, then the expression
can be written as
follows:
.
To obtain a
proposition, each variable of the expression must be quantified or assigned
some value in D. We'll discuss this shortly,
when we talk about semantics.
Now let's look at
two examples, which will introduce us to the important process of formalizing
English sentences with quantifiers.
EXAMPLE. We'll formalize
the three sentences about Socrates that we listed at the beginning of the
section. Let P be the set of all
people, let cs(x)
mean that x is a computer science
major, and let pc(x) mean that x owns a personal computer. Then the
sentence "All computer science majors own a personal computer" can be
formalized as follows:
.
The sentence
"Socrates does not own a personal computer" becomes
Ø pc(Socrates).
The sentence
"Socrates is not a computer science major" becomes
Ø cs(Socrates).
EXAMPLE
(Natural Numbers). Suppose we consider the following two elementary
facts about the natural numbers N:
1. Every natural
number has a successor.
2. There is no
natural number whose successor is 0.
Let's formalize
these sentences. We'll begin by writing down a semiformal version of the first
sentence:
For each x Î N there exists y Î N such that the successor of x is y.
If we let s(x, y) mean that the successor of x is y, then the formal
version of the sentence can then be written as follows:
.
Now let's look at
the second sentence. It can be written in a semiformal version as follows:
There does not
exist x Î N such that the successor of x
is 0.
The formal version
of this sentence is Ø $ x Î N : s(x, 0).
These notions of
quantification belong to a logic called first-order predicate calculus. The
words "first-order" refer to the fact that quantifiers can quantify
only variables that occur in predicates. To discuss first-order predicate
calculus, we need to give a precise description of its well-formed formulas and
their meanings.