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 one-place predicate.
• If an upper case letter is immediately followed by two lower case letters, then it's a two-place predicate.
• And so on: If an upper case letter is immediately followed by n lower case letters, then it's an n-place 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 backward-E: '%'. (**), then, will be symbolized as follows:

(%x)(Ex&Lxc)

The backward-E is called the "existential" quantifier because it says that something exists.

There is one more quantifier used in PL: the universal quantifier upside-down 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 x-quantifier
                 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 x-quantifier. 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.

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.

           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:

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.

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:

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.

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:

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":

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.

back to chapter six
on to the next chapter
continue with this reference