The Logic Café
Reference
Chapter Six — Predicate Logic Introduction
It is recommended that you
print this reference.
Contents: Section
1: Introduction; Section 2:
Syntax for PL; Section 3: Introduction to PL Symbolization
This chapter introduces a language for "predicate logic" we
will call "PL". With predicate logic, we greatly increase
the expressive power of our language and so significantly enhance
our logic. Happily, the new language gains its power with only
a few additions to the lexicon of SL. Most things we do in
this chapter, indeed in all the remaining chapters, will remind you of
SL.
While SL can only represent simple sentences as uppercase letters, PL
is powerful because it allows the analysis of simple sentences into parts.
The first thing to notice will be that PL includes "names" to
refer to individual objects and "predicates" to refer to properties
of individual objects. PL also represents relationships between individual
objects and (most importantly) allows a quantitative representation of
individuals: We will have quantifier symbols to represent "all"
and "some".
Once again, the introduction to a language given in the tutorial is very
different from that of this reference. Here in the reference, we give
a more systematic but less intuitive presentation of PL. So, if you have
not already done so, read the introductory tutorials for chapter six before
tackling the details below!
1. Introduction
The first and easiest way to see PL as an extension of SL is to think
about names, predicates, and relations. So, we will be able to represent
something like
(*) Both Jeremy and Karla passed the bar exam, but Jeremy
did so before Karla.
In SL, we would have to represent (*) with something like '(J&K)&B'.
But in PL, we can get at the structure of the atomic sentences.
First we might use 'j' and 'k' as names for Jeremy and Karla; then we
might use 'P' to symbolize the predicate "passed the bar exam"
and 'B' to symbolized the relationship "passing the bar exam
before". We will write 'Pj' for "Jeremy passed the bar exam,
'Pk' for "Karla passed the bar exam" and 'Bjk' for "Jeremy
passed before Karla". So, (*) can be symbolized as:
(Pj&Pk)&Bjk
A relationship, like that expressed by 'B' in 'Bjk', is sometimes called
a "two place predicate" because it's a predicate relating two
things. Can you think of an example of a three place predicate?
To summarize, in PL, our names are lower case letters.
So, we can symbolize "Agnes" as 'a' (or any other lower
case letter from 'a' through 'u'; 'v'  'z' are reserved for other uses).
Furthermore, in PL predicates are represented by upper case letters,
as are atomic sentences. How will we tell the predicates apart from the
atomic sentences?
 If an upper case letter is immediately followed by no
lower case letters, then it's a sentence letter.
 If an upper case letter is immediately followed by one
lower case letters, then it's a oneplace predicate.
 If an upper case letter is immediately followed by two
lower case letters, then it's a twoplace predicate.
 And so on: If an upper case letter is immediately followed by n
lower case letters, then it's an nplace predicate.
The most important new aspect of PL is the quantifier.
Thinking about numbers will help us see how to quantify.
For example, the English
There is an even number less than three
means that there is at least one thing x, which is even and less than
three. In other words:
(*) There is an x, x is even and x is less than three.
Bear with me! There's a reason to go through this example involving the
variable 'x' (which you remember using in high school, yes?). Let's begin
translating into PL; the above comes to:
(**) There is an x such that: Ex & Lxc
The phrase "there is" indicates a quantifier. It specifies
that there is something having certain properties. We will write this
with a new symbol, the backwardE: '%'. (**),
then, will be symbolized as follows:
(%x)(Ex&Lxc)
The backwardE is called the "existential" quantifier because
it says that something exists.
There is one more quantifier used in PL: the universal quantifier upsidedown
A: '^'. This quantifier means "all"
or "every". We can use it to symbolize the following.
Everyone will attend law school and need a loan
would be:
(^x)(Wx&Nx)
This should be understood to mean:
Everything x is such that it, x, is both W and N.
One last point is in order. When we talk about "something"
or "everything" in English, we usually have some particular
group of things in mind. For instance, if we say that everyone will attend
law school, we don't mean literally everyone in the world. Instead, we
may have some circle of friends in mind.
Similarly, all quantification in PL assumes a "universe of
discourse" the collection of all objects under discussion.
2. Syntax for PL
We need now say precisely what counts as a sentence of our language PL.
This is a little more complicated than the syntax for SL; it's best for
the reader to make sure he or she has a handle on the tutorials of chapter
six, all of them!, before reading through the following compact presentation.
We first give a recursive definition of a formula
of our language. To do so we bear in mind that the lexicon includes
 Predicate letters: A,B,C...Z (excluding 'V' but allowing subscripts)
 Names: a  u (subscripts allowed)
 Variables: w  z (again, subscripts allowed)
 Truth Functional Connectives: &,v,>,=,~
 Quantifiers: %,^
 Parentheses: (,)
We build up formulas from atomic formulas. So, first define the the latter:
A term is any name or variable.
An expression is an atomic formula in
PL if and only if it is a predicate letter followed by 0, 1, or
more terms (i.e., names and/or variables).
We may now give the "recursive" definition of a formula —
the definition in terms of a building process which uses atomic formulas
as a basis.
I) Each atomic formula of PL is a formula
of PL.
II) If P and Q
are formulas of PL, then so are
a) (PvQ),
(P&Q),
(P>Q),
(P=Q),
~P, and
b) (^x)Px,
(%x)Px
(provided an xquantifier
does not occur in P)
A subformula of a formula P
is any formula used or produced in the building of P.
So, for example, we can construct '(^x)(Tx>(%y)Lxy)'
by starting with the atomic formulas Tx and 'Lxy'. So, these two are subformulas.
Then, by an application of clause b), '(%y)Lxy)'
is produced and is a subformula. By an application of a), '(Tx>(%y)Lxy)'
is also a subformula. Finally, by a second application of b) the whole
sentence '(^x)(Tx>(%y)Lxy)' is produced;
it too is a subformula. (We may call it an "improper
subformula" of itself.)
P is an immediate
subformula of a formula Q if and
only if P is a subformula of Q
and is used in the final step of the building process of Q.
The only immediate subformula of '(^x)(Tx>(%y)Lxy)'
is '(Tx>(%y)Lxy)' (because the last step
is the addition of the 'x'quantifier). We call the 'x'quantifier the
"main connective" of '(^x)(Tx>(%y)Lxy)'.
The main connective (or main
logical operator) of a formula P
is the last quantifier or truth functional connective used in P's
building process.
Much like with SL, atomic formulas have no main connective; all other
formulas have exactly one main connective.
Also, we can define a PL form as we did in
SL. For example, (^x)P
is the form for any PL formula with '^'
main connective. And (^x)P>Q
is the form for any formula with horseshoe and main connective and antecedent
with main connective '^'.
Yet again, like SL, we allow ourselves to drop outside parentheses
or substitute brackets for parentheses. This will cause no ambiguity.
Now, we are almost ready to define a sentence of PL. To do so, we need
a few preliminary definitions. For these notions, keep the following two
formulas in mind.
(*) (%x)(Tx&Lx)
and
(**) Tx&(%x)Lx
First,
The scope of a quantifier
in a PL formula P is the subformula of P for which that quantifier is
main connective.
So, in (*) the scope of the quantifier is the whole formula
while in (**) the scope is only the second conjunct.
An instance of a variable x
in a formula is bound if and only if it is within
the scope of an xquantifier. Otherwise
we say it is free.
In (*), '(%x)(Tx&Lx)', all instances of
'x' are bound, while in (**), Tx&(%x)Lx',
the first instance is free. This is what makes (*) but not (**)
a sentence of PL.
A formula of PL is a sentence if
and only if it has no free variables.
One final syntactical definition will come in handy when we discuss the
semantical issues and derivations of the next two chapters:
If a sentence is of the form '(^x)P'
or '(%x)P',
then the substitution instance P(a/x)
is the result of taking P and replacing
every occurrence of x with a.
3. Introduction to PL Symbolization
Now that we have a sure handle on the syntax (or "grammar")
of our new language, we can press forward with semantical issues. The
easiest way to do this is to relate PL to English.
Some Symbolization Basics
English has many ways to name an object. The easiest way is the
proper name. But there other types of English expressions used to refer
to a unique individual. The following English expression are typically
used to signify a specific individual and so can be symbolized with PL
names.
Names
Proper Nouns like "Paris", "Earth", "Mary",
"Oakland University", "Waiting for Godot", "tomorrow",
etc.
Kind Names like "oxygen", "Homo Sapiens"
(the species), "logic", etc.
Pronouns like: "this", "that", "he",
"she", "it", "who", "what", "there",
etc.
Definite Descriptions like: "the boy in the field",
"Smith's murderer", "the square root of 4", "my
son", etc.
Other tags like numerals or symbols, e.g., '(*)' as used
in this reference manual.
Natural language has many ways to specify predication. No list is particularly
helpful for these. But lists of English means to quantify are useful. Begin
with the existential quantifier.
Words
often symbolized with '%':
"some", "something", "someone", "somewhere",
"at least one", "there is", "a", "an",
"one"
(Warning: The last three of these fairly often mean something different
and not to be symbolized with '%'. More on this
below.)
It's good to keep some very basic examples in mind:
English 
PL 
Symbolization Key 
Jason knows someone. 
(%y)Kjy 
j: Jason, Kxy: x knows y 
I did something. 
(%x)Dix 
i: me, Dxy: x did y 
I see a person in my office. 
(%x)Sixo 
o: my office, Sxyz: x sees y in z 
We may do much the same thing with the universal quantifier.
Words
often symbolized with '^':
"all", "every", "each", "whatever",
"whenever", "always", "any", "anyone"
(Warning: The last two of these fairly often mean something
different and not to be symbolized with '^'.
More on this below.)
Here are some examples.
English 
PL 
Symbolization Key 
Jason knows everyone. 
(^y)Kjy 
j: Jason, Kxy: x knows y 
I can do anything. 
(^x)Dix 
i: me, Dxy: x can do y 
I need to see all students in my office. 
(^x)Sixo 
o: my office, Sxyz: x needs to see y in z 
Complications
A number of the words English uses to indicate quantification are ambiguous.
"Any" and related words are examples. On the one hand, "any"
as used in "I can do anything" and "anyone can walk to
class" is a universal quantifier:
Typical uses of "any":

English 
Hybrid 
Symbolization 
I can do anything. 
All actions x are such that I can perform x. 
(^x)Dix 
Anyone can walk to class. 
All people can walk to class. 
(^z)Wz 
However, "any" is not always used this way...
Exception: "I don't see anyone" means that it's
not the case that I see someone, so may be symbolized as
~(%x)Six
Another example to think about is the question: "Do you see anyone?"
The question is quite different from "Do you see everyone?".
Another exception involves the indefinite article 'a'. Often this is
used to quantify existentially. We have seen examples like the following
in previous pages.
Typical uses of "a":

English 
Hybrid 
Symbolization 
I see a buffalo. 
There is a buffalo w and I see w. 
(%w)(Mw&Niw) 
A friend of mine is coming over. 
There is a y who is a friend of mine and y is coming over. 
(%y)(Fyi&Cy) 
But there can be an...
Exception: "A rule is meant to be broken". This
does not mean just that there is some rule meant to be broken.
Instead, it's about rules in general: All rules are meant
to be broken. If the universe of discourse is rules, then we can symbolize
this simply as '(^x)Mx' (where 'Mx' means "x
is meant to be broken".)
Just to summarize our exceptions:
Exceptions

English 
Hybrid 
Symbolization 
I don't see anyone. 
It's not the case that there is even one person I see. 
~(%x)Six 
A rule is meant to be broken. 
All rules are meant to be broken. 
(^x)Mx 
How can you tell which quantifier to use? It's not always easy, but mostly
with practice you'll be able to answer this question on a case by case
basis.
Negation and Quantification
Negation relates to quantifiers in interesting ways. For example, "No
one is awake" is logically equivalent to "Everyone is asleep"
and to "It's not the case that even one person is awake".
Take a moment to really think about this example! Now, to symbolize
these, use 'Ax' for "x is awake":
No one is awake.
Everyone is not awake.
Everyone is sleeping. 
Can each be symbolized as either of: 
(^x)~Ax
~(%x)Ax 
Notice that "not everyone is awake" means something different
from "everyone is not awake"! The former means that at least
one person is asleep; the latter that everyone is asleep.
Not everyone is awake.
Someone is not awake.
Someone is sleeping. 
Can each be symbolized as either of:

(%x)~Ax
~(^x)Ax 
back to chapter six
on to the next chapter
continue with this reference
