Not logged in. Log In
Syllabus
Lecture Notes
Exercises

Lecture Notes Unit 3

Contents

  1. The Language of Predicate Logic
  2. Predicate Logic Derivations
  3. Review
(In lazy mode, lowercase letters, except ‘v’, are automatically changed to uppercase.)
PenguinLogic

The Language of Predicate Logic

The Limitations of Sentential Logic

In sentential logic, a letter represents an entire atomic statement.

It cannot represent common features between atomic statements.

Examples of common features in atomic statements:

  1. Kanye West is an egotist.
    shares features in common with:
  2. Kanye West is a musician.
    (Same subject, different predicate.)
  3. Lindsay Lohan is an egotist.
    (Same predicate, different subject.)
  4. Everyone is an egotist.
    (Same predicate, general subject.)
  5. Someone is an egotist.
    (Same predicate, indefinite subject.)

Sentential logic treats these all as simple statements (K, M, L, E, S, etc.), and so loses any connection between them.

A valid argument not captured by sentential logic:

Kanye West is an egotist.
Therefore, someone is an egotist.

However the argument:

K
S

is obviously invalid in sentential logic.

We now introduce a new style of symbolic logic, called predicate logic.

Subjects and Predicates

In predicate logic …

Lowercase letters (except x, y and z) represent specific individual persons, places or things. (Subjects)

Uppercase letters represent things that can be said about the things above. (Predicates)

Example subjects:

Englishbecomes
Amsterdama
Kevink
Britney Spearsb
the Popep
five (or 5)f

Example predicates:

Englishbecomes
_______ is hungry H
_______ plays tennis T
_______ has driven drunk D
_______ is prime P
_______ loves … L

Predicate Logic Statements

We put these together, capital letters first, to form statements.

Example Statements:

  1. Kevin is hungry.
    Translation: Hk

  2. Britney Spears is hungry.
    Translation: Hb

  3. Britney Spears plays tennis.
    Translation: Tb

  4. 5 is prime.
    Translation: Pf

  5. The pope loves Britney Spears.
    Translation: Lpb

Monadic and Polyadic Predicates

Polyadic or relational predicates are those that are applied to more than one thing.

With these, order usually matters.

In principle, predicates can apply to any number of things:

Using “B” to mean “_______ is between _______ and _______”:

Seven is between five and nine.

Translation: Bsfn

“And” with Polyadic Predicates

In unit 1, we saw that sometimes when “and” occurs between two names, it is possible to translate with “&”.

When “and” means “&”:

Chandler and Monica are hungry.

This really means:

Chandler is hungry and Monica is hungry.

Translation: Hc & Hm

However, not always.

When “and” doesn’t mean “&”:

Chandler and Monica are engaged.

This does not mean the same as:

Chandler is engaged and Monica is engaged.

Instead, it means:

Chandler is engaged to Monica.

Translation: Ecm

(I.e., it uses a polyadic predicate.)

Molecular Statements

∨, →, ↔, & and ~ are used just as before:

  1. Peter is a Republican only if he is ignorant.
    Translation: RpIp

  2. Unless Peter plays tennis, then Alison loves him only if he does not drive drunk.
    Translation: ~Tp → (Lap → ~Dp)

  3. If neither Ross nor Phoebe are hungry, then Monica will not cook.
    Translation: (~Hr & ~Hp) → ~Cm  or ~(HrHp) → ~Cm

  4. Alison is unkind if and only if Peter is impolite.
    Translation: ~Ka ↔ ~Pp

“~” can be used to translate prefixes like “non”, “un”, “in” and “im”.

Homework: Exercise Set 6A

Quantifiers

General Statements and Variables

Not all statements are about specific individuals. Some are about all or some unspecified members of a group.

  1. All dentists floss.
  2. Some politicians are alcoholics.
  3. Everyone loves Björk.

To capture these we use variables.

In algebra, variables stand for unspecified numbers.

In predicate logic, variables can stand for anything.

The lowercase letters “x”, “y” and “z” are used as variables.

They replace lowercase letters “a”, “b” for specific particular subjects in predicate logic statements.

If “Hk” means “Kevin is hungry”, then “Hx” means something like “it is hungry”, where it remains ambiguous who or what “it” is.

Such statements containing variables are ambiguous as is.

We remove the ambiguity by prefixing a quantifier and the variable to which the quantifier applies to an ambiguous statement.

The Universal Quantifier, ∀, written with a variable means For every value of the variable …

The Existential Quantifier, ∃, written with a variable means For at least one value of the variable …

Simple quantified statements:

xHx means For at least one value of x, x is hungry. I.e., Something is hungry.

xBx means For every value of x, x is beautiful. I.e., Everything is beautiful.

Quantified Variables and Their Values

“∀xBx” means that ALL of

BaAmherst is beautiful.
BbBritney is beautiful.
BcChicago is beautiful.
BdDetroit is beautiful.
BeEminem is beautiful.
BfFive is beautiful.
BgGanymede is beautiful.
(and so on for everything there is)

must be true.

If even one is false, “∀xBx” is false.

“∃xBx” requires only one or more of these to be true.

It’s false only if all of the above are false.

Homework: Exercise Set 6B

Universal Affirmative Statements

We don’t normally speak of about just everything, but every member of some group. We handle these by applying ∀ to a conditional.

Example universal affirmatives:

  1. All frogs are green.
  2. Every frog is green.
  3. Any frog is green.
  4. Each frog is green.

These all become: ∀x(FxGx)

I.e., for every value of x, if x is a frog, x is green.

Plural and count noun phrases are translated with uppercase letters!

“∀x(FxGx)” means that ALL of these are true:

FaGaIf Amherst is a frog, then Amherst is green. (F,F)
FbGbIf Britney is a frog, then Britney is green. (F,F)
FcGcIf Chicago is a frog, then Chicago is green. (F,F)
FkGkIf Kermit is a frog, Kermit is green. (T,T)
FlGlIf Leaper is a frog, Leaper is green. (T,?)
FsGsIf Shrek is a frog, Shrek is green. (F,T)

The variable is not just restricted to frogs.

But when the if-part is false, the conditional is true.

Particular Affirmative Statements

Any statement about some (unspecified) member(s) of a group is translated with “∃” with a variable applied to a conjunction.

Example particular affirmatives:

  1. Some politician is honest.
  2. Some politicians are honest.
  3. A few politicians are honest.
  4. At least one politician is honest.

All become: ∃x(Px & Hx)

“Some” in English may suggest more than one, but we assume it doesn’t require it.

“∃”-statements can be interpreted as asserting existence: “There are honest politicians”, or “Honest politicians exist”.

Universal Negative Statements

A statement that something is true of no things in a certain group can be seen in one of two ways.

Example universal negatives:

  1. No politician is ethical.
  2. No politicians are ethical.

These can be paraphrased as

For all x, if x is a politician, then x is NOT ethical.

I.e., ∀x(Px → ~Ex)

Or as:

It is NOT the case that there is an x such that x is a politician and x is ethical.

I.e., ~∃x(Px & Ex)

These two formulations are logically equivalent.

Particular Negative Statements

These deny something of some members of a group.

Example particular negatives:

  1. Some politician is not ethical.
  2. Some politicians are not ethical.
  3. Some politicians are unethical.

This can be paraphrased as:

There exists at least one x such that x is politician and x is not ethical.

I.e., ∃x(Px & ~Ex)

Or as: Not all politicians are ethical.

I.e., ~∀x(PxEx)

The Square of Opposition

Universal affirmatives (All Fs are Gs) and particular negatives (Some Fs are not Gs) are true opposites.

Particular affirmatives (Some Fs are Gs) and universal negatives (No Fs and Gs) are true opposites.

The Simple Square of Opposition

~∀xFx is not equivalent with x~Fx, but it is equivalent with x~Fx.

Similarly, ~∃xFx is equivalent not with x~Fx, but x~Fx.

It’s important to watch where you place negations and parentheses.

Some Example Translations

Try them yourself, or check Prof. Klement’s answer.

Homework: Exercise Set 6C, Exercise Set 6D

Translations in Monadic Predicate Logic

Combined Predicates

A quantified statement can involve more than two predicates.

Often they should be joined with “&”. Consider:

Every rockstar is popular and sexy.

Translation: x[Rx → (Px & Sx)]

These are often shortened to adjectives modifying nouns.

  1. All popular rockstars are sexy.
    Translation: x[(Px & Rx) → Sx]

  2. Some carrots are orange vegetables.
    Translation: x[Cx & (Ox & Vx)]

Complex predicates are put together in parentheses, and are not broken up, even when negations are involved.

  1. No hamsters are endangered animals.
    Translation: ~∃x[Hx & (Ex & Ax)]   Or x[Hx → ~(Ex & Ax)]

  2. Some intelligent students are not pathetic geeks.
    Translation: x[(Ix & Sx) & ~(Px & Gx)]

Things can’t always be done this way.

A “computer programmer” isn’t someone who is a computer and is a programmer, but someone who programs computers.

A “basketball player” isn’t someone who is a basketball and a player, but someone who plays basketball, etc.

Homework: Exercise Set 6E

Disjunctive Combined Predicates

Sometimes disjunctions (“∨”-statements) are used to translate combined predicates.

  1. Anything that’s plaid or striped is ugly.
    Translation: x[(PxSx) → Ux]

  2. All athletes are either quick or strong.
    Translation: x[Ax → (QxSx)]

    Or with negations …

  3. Some professors are not either quick or strong.
    Translation: x[Px & ~(QxSx)]

Hidden Disjunctive Combined Predicates

Some statements that use the word “and” in English can actually be translated with “∨”.

Consider:

All doctors and lawyers are rich.

This is NOT: ∀x[(Dx & Lx) → Rx]

That would mean “everything that is a doctor and a lawyer is rich”.

Instead make it: ∀x[(DxLx) → Rx]

This means “everything that is a doctor or a lawyer is rich.”

So where did the “and” come from in the English version?

It is equivalent with a conjunction of universal affirmatives.

An alternative: ∀x(DxRx) & ∀x(LxRx)

Only

What does it mean to say that only As are Bs?

On one way of thinking of it, it means that

No non-As are Bs.

On another, it is the converse of “all”: All Bs are As.

Only cats purr.

Translation: x(~Cx → ~Px)  or ~∃x(Px & ~Cx)  or x(PxCx)

But NOT: ∀x(CxPx) (Every cat purrs.)

Ambiguities Involving “Only”

“Only” creates ambiguities when complex predicates are involved.

Only happy cats purr.

  1. This might be read as just about cats:
    Among cats, only the happy ones purr.
    Translation: x[(Cx & Px) → Hx]  or ~∃x[(Cx & Px) & ~Hx]
     or x[Cx → (~Hx → ~Px)]  or x[Cx → (PxHx)]

  2. Or it might be about everything:
    The only things that purr at all are happy cats.
    Translation: x[Px → (Hx & Cx)]   or x[~(Hx & Cx) → ~Px]
     or ~∃x[Px & ~(Hx & Cx)]

The Only

Note: “the only” does not mean the same as “only”.

Usually, “only A are B” means the same as “the only B are A”.

The only likable teachers are philosophers.

Translation: x[(Lx & Tx) → Px]   or x[~Px → ~(Lx & Tx)]

  or ~∃x[~Px & (Lx & Tx)]

“Only” is the converse of “all”. “The only” is the converse of “only”.

Therefore, “all” and “the only” mean the same thing!

Homework: Exercise Set 6F

The

Normally, statements using “the” are about some specific thing, and may be translated with constant subject letters.

Other times “the”-statements are really about every member of a group.

Contrasting Cases of “The”:

  1. The dog ran away.
    Translation: Rd

  2. The dolphin is a mammal.
    Translation: x(DxMx)

Missing Quantifiers

Sometimes an quantifier word is simply left off in an English sentence.

These can mean different things, in different contexts.

These can mean the same as “all”, as “some” or even “only” statements.

  1. Frogs are amphibians.
    Translation: x(FxAx) (Missing “all”.)

  2. Students work at the library.
    Translation: x(Sx & Wxl) (Missing “some”.)

  3. Employees are allowed in.
    Translation: x(AxEx) (Missing “only”.)

All and Only

Rarely, “all and only” occurs as a single phrase.

This can be translated with “∀” and “↔”.

All and only bachelors are allowed in.

Translation: x(BxAx)

Homework: Exercise Set 6G

Quantified Statements Joined Together

Entire quantified statements can be joined together with logical connectives like “and”, “or”, “if … then … ”, etc.

  1. If nothing is permanent, then everything is illusory.
    Translation: ~∃xPx → ∀xIx

  2. No Republicans are environmentalists but some Democrats are environmentalists.
    Translation: ~∃x(Rx & Ex) & ∃x(Dx & Ex)

  3. If some students are confused, then all students are.
    Translation: x(Sx & Cx) → ∀x(SxCx)

  4. If nothing is permanent and nothing is good, then all religions are fictional.
    Translation: (~∃xPx & ~∃xGx) → ∀x(RxFx)

  5. Unless the host cooks or some local restaurant delivers, no partygoer will be happy.
    Translation: ~{Ch ∨ ∃x[(Lx & Rx) & Dx]} → ~∃x(Px & Hx)

Additional Example Translations

Try them yourself, or check Prof. Klement’s answer.

Homework: Exercise Set 6H, Credit Exercises 3.1

Translations in Polyadic Predicate Logic

Polyadic predicates are those applied to more than one subject.

These are written with two or more names/variables, and the order usually matters.

Atomic Statements with polyadic predicates:

  1. Angelina loves Brad.
    Translation: Lab

  2. Brad loves Angelina.
    Translation: Lba

  3. Brad is loved by Angelina.
    Translation: Lab  (same as “Angelina loves Brad”)

Normally we match the English order … except when passive voice is used (i.e., “ … is _______ed by … ”).

Quantifiers with Polyadic Predicates

Even with a single predicate, the possibilities are many.

EnglishTranslations
Everything loves Fergie. xLxf
Something loves Fergie. xLxf
Fergie loves everything. xLfx
Fergie loves something. xLfx
Nothing loves Fergie. ~∃xLxf / ∀x~Lxf
Fergie loves nothing. ~∃xLfx / ∀x~Lfx
Something doesn’t love Fergie. x~Lxf / ~∀xLxf
Fergie does not love something. x~Lfx / ~∀xLfx
Not everything loves Fergie. ~∀xLxf
Everything loves itself. xLxx
etc.
Homework: Exercise Set 7A

Reflexive Constructions

Reflexive constructions are translated by repeating the same subject letter or variable.

  1. Fergie loves herself.
    Translation: Lff  (“Fergie loves Fergie.”)

  2. Every singer who respects him/herself is happy.
    Translation: x[(Sx & Rxx) → Hx]

The “self-” prefix may be treated similarly.

No self-respecting musician admires Sanjaya.

Translation: x[(Mx & Rxx) → ~Axs]

Some additional examples:

  1. All men love Fergie.
    Translation: x(MxLxf)

  2. No beautiful women love Diddy.
    Translation: x[(Bx & Wx) → ~Lxd]  or ~∃x[(Bx & Wx) & Lxd]

  3. All men love themselves.
    Translation: x(MxLxx)

  4. Only morons love Diddy.
    Translation: x(~Mx → ~Lxd)
     or x(LxdMx)  or ~∃x(~Mx & Lxd)

  5. Something Diddy loves loves itself.
    Translation: x(Ldx & Lxx)

Quantifier Movement

When the quantifier word occurs in the middle of the statement, try rewording it with the quantifier out in front.

Usually, this will result in a switch from active to passive voice

  1. Diddy loves all guns.
    This is the same as:
    All guns are loved by Diddy.
    Translation: x(GxLdx)

  2. Angelina loves nothing that loves Brad.
    This is the same as:
    Nothing that loves Brad is loved by Angelina.
    Translation: x(Lxb → ~Lax)  or ~∃x(Lxb & Lax)

Multiple Quantification with Polyadic Predicates

Quantifiers can be applied to both terms of a polyadic predicate.

When multiple quantifiers are applied to the same part of the same statement, different variables (e.g., “x” and “y”) must be used.

The order of the quantifiers matters, and often points to subtle distinctions not often unambiguously marked in English.

Everything loves something.

Varieties of Multiple Quantification

The possibilities are endless! Here are just a few::

Something loves something. xyLxy
Everything loves everything.xyLxy
Something loves everything.xyLxy
Everything is loved by everything.xyLyx
Something is loved by something.xyLyx
Something is loved by everything.*xyLyx
Everything is loved by something.*xyLyx
Something loves nothing.x~∃yLxy / ∃xy~Lxy
Nothing loves everything.x~∀yLxy / ~∃xyLxy
Something does not love everything.x~∀yLxy
Nothing loves anything.xy~Lxy / ~∃xyLxy

Those marked with * are possibly ambigious; I have given the most likely meaning.

More Complicated Forms of Multiple Quantification

These are perhaps best seen by example:

  1. Every rockstar loves something.
    Translation: x(Rx → ∃yLxy)

  2. Something is loved by every rockstar.
    Translation: xy(RyLyx)

  3. Every man loves every woman.
    Translation: x[Mx → ∀y(WyLxy)]

  4. Every beautiful woman is loved by some man (or other).
    Translation: x[(Bx & Wx) → ∃y(My & Lyx)]

  5. Some men are not loved by every woman.
    Translation: x[Mx & ~∀y(WyLyx)]

  6. No beautiful women love every man.
    Translation: x[(Bx & Wx) → ~∀y(MyLxy)]
     or ~∃x[(Bx & Wx) & ∀y(MyLxy)]

Homework: Exercise Set 7B, Exercise Set 7C

Restrictive Clauses

The words “that”, “which”, “who”, and “whom” are used to introduce restrictive clauses.

These operate much like complex predicates translated with “&”.

Example that/which/who/whom clauses:

  1. All rockstars that dance are sexy.
    = All dancing rockstars are sexy.
    Translation: x[(Rx & Dx) → Sx]

  2. Some rockstars that love Diddy dance.
    = Some Diddy-loving rockstars dance.
    Translation: x[(Rx & Lxd) & Dx]

When applied to “something” or “everything”, they take the place of the predicate they’d otherwise restrict.

Examples:

  1. Everything that loves Fergie dances.
    = Every Fergie-lover dances.
    Translation: x(LxfDx)

  2. Something that Diddy owns is not a gun.
    = Some Diddy-owned-thing is not a gun.
    Translation: x(Odx & ~Gx)

Quantified Restrictive Clauses

These can get very complex.

In such cases, it is usually best to break the problem into steps.

Everything that loves all women loves Fergie.

Overall, this is an all-statement, which gets translated with “∀” along with “→”.

Mixing English and symbolic logic, we can do our first step as:

x[x loves all women → x loves Fergie]

Now “x loves all women” becomes: y(WyLxy)

And “x loves Fergie” becomes: Lxf.

Together we get: x[∀y(WyLxy) → Lxf].

More examples:

  1. Some rockstars whom all women love dance.

    STEP 1: x{x is a rockstar whom all women love & x dances}
    STEP 2: x{[Rx & all women love x] & Dx}
    STEP 3: x{[Rx & ∀y(WyLyx)] & Dx}

  2. Some rockstars who own some guns are loved by no women.

    STEP 1: x{x is rockstar who owns some guns & x is loved by no women}
    STEP 2: x{[x is rockstar & some guns are owned by x] & no women love x}
    STEP 3: x{[Rx & some guns are owned by x] & ∀y(Wy → ~Lyx)}
    STEP 4: x{[Rx & ∃y(Gy & Oxy)] & ∀y(Wy → ~Lyx)}

  3. Every jabberwock that only outgribes those things that every bandernatch outgribes gimbles no toves that gimble themselves.

    STEP 1: x{x is a jabberwock that only outgribes those things that every bandersnatch outgribes → x gimbles no toves that gimble themselves}
    STEP 2: x{[Jx & the only things that x outgribes are things that every bandersnatch outgribes] → no toves that gimble themselves are gimbled by x}
    STEP 3: x{[Jx & ∀y(x outgribes y → every bandernatch outgribes y)] → ∀y[y is a tove that gimbles itself → ~(y is gimbled by x)]}
    STEP 4: x{[Jx & ∀y(Oxy → ∀z(z is a bandersnatch → z outgribes y))] → ∀y[(Ty & Gyy) → ~Gxy]}
    STEP 5: x{[Jx & ∀y(Oxy → ∀z(BzOzy))] → ∀y[(Ty & Gyy) → ~Gxy]}

Homework: Exercise Set 7D, Exercise Set 7E

Predicate Logic Derivations

Abacus

We can use the method of derivations, like in unit 2, as a means to demonstrate that arguments in predicate logic are valid.

This method is particularly important for predicate logic, because, unlike sentential logic, there is no alternative method such as truth tables to use to show that an argument is valid.

The basic idea of a derivation in predicate logic is the same as for sentential logic.

Moreover, all the rules of derivation you learned for sentential logic (&O, &I, ∨O, ∨I, ↔O, ↔I, →O, DN, etc.) carry over to predicate logic.

The only difference is that, although in stating the rules, we use single letters to represent places where we can “plug in” formulas, the formulas themselves will never consist of single letters.

At minimum, they will consist of a capital letter and lowercase letter. They may also contain quantifiers and/or other logical operators.

Example:

The techniques of ID and CD also carry over.

Warning: we can only use CD for SHOW lines whose “main operator” is the if-then (→). This does not include statements that have if-thens within the scope of quantifiers.

If our show line is SHOW: ∀x(NxOx), we cannot use CD, or, at least, not right away.

We could, however use it for SHOW: ∀xNx → ∀xOx.


Universal Out

We need new rules to use for our new logical signs: the quantifiers.

Again, these can be divided into “in” rules and “out” rules. Our first such rule is called “Universal Out”.

The “official” way of writing this is as follows:

∀O (official)
∀vA
A[a/v]


(a can be any name)

This requires some explanation. The “v” is any variable (x, y, or z). The A is some statement containing that variable. A[a/v] represents what that formula becomes when some name “a” replaces the variable “v”.

More informally, we could write the rule as follows:

∀O (informal)
xx
a


(or any other variable and name)

The quantifier must extend over the whole statement. We cannot apply this rule, or any other rule, to part of a line.

We start with something that says that some formula is true for all things x. (Or, for all things y …) Therefore, that formula would be true for any particular thing. So we can replace the variable that goes with the quantifier everywhere it occurs afterwards with the same name, and the result will be true. (We must replace every occurrence of the variable letter with the same name.)

For example, consider this argument:

For everything, if it is human, then it is mortal.
Therefore, if Socrates is human, then Socrates is mortal.

This argument has this form:

x(HxMx)
HsMs

This is a valid reasoning step by ∀O.

Some example problems:

We must do the ∀O steps before →O steps.

We can do ∀O to any letter we like, and even to multiple letters within the same derivation. The only thing we are restricted from doing is replacing different occurrences of the variable with different letters in one step.

Here’s a use of ∀O within an ID.

Take multiple quantifiers in the same statement one at a time.

Homework: Exercise Set 8A

Existential In

Our next rule deals with existential quantifiers. Here, we move in the opposite direction. We begin with a statement about some particular individual: a, b, c, etc. We then conclude that the statement is true about something (or someone).

∃I (official)
A[a/v]
∃vA


(a can be any name)

∃I (informal)
a
xx


(or any other name, and variable not already in the statement)

Here, you replace one or more occurrences of the letter with a variable, and introduce an existential quantifier, which will extend over the whole statement. (You may need to add parentheses.) If the letter “x” already occurs in the statement, you need to use “y” or “z”, etc., as required.

Consider the argument:

The Bandersnatch is frumious.
Therefore, something is frumious.

This has the form:

Fb
xFx

This is a valid step of ∃I reasoning.

Some examples:

Unlike ∀O, we do not need to replace all occurrences of the letter; we can replace only one—or more—as required.

Homework: Exercise Set 8B, Credit Exercises 3.2

Existential Out

The next rule we are going to learn is trickier. Recall that ∀O allows us to drop off a universal quantifier and replace the variable with any letter we like. Of course, a universal quantifier is used to say that something is true about everything there is. An existential quantifier just says that something is true for at least one thing, but it doesn’t tell us what that thing is.

Therefore, we can’t drop off an existential quantifier to any letter we like. Instead, we make up a new name for the person or thing that makes the existentially quantified statement true. Then we use that name. The process is somewhat like this.

Something lives on Venus.
(Let’s arbitrarily call that something ALF.)
Therefore, ALF lives on Venus.

This argument has this form.

xLxv
Lav

∃O (official)
∃vA
A[n/v]


(n must be a new name)

∃O (informal)
xx
n


(n must be a new name, x may be any variable)

A new name is one that does not occur anywhere previously in the derivation, not even on a SHOW line.

We must pick a new letter. We cannot assume that the thing making the quantified statement true is the same thing as anything we already know something about. So if we already have “a” earlier in our derivation, we must use “b”. If we already have “a” and “b”, we must use “c”, and so forth.

An example derivation.

We can use “a” at line 4 since it doesn’t appear above.

This problem shows that it’s almost always better to do ∃O steps before ∀O steps.

Notice that if we had done the ∀O step first, we would have had to use a different letter—say “b”—for the ∃O step, and then we wouldn’t be able to do →O!

Some more examples:

We used “c” since “a” and “b” already appear.


Universal Derivation

There is no rule “Universal In”. Instead, we have a new form of derivation. (Remember we did not have a rule of →I, only CD.)

It takes a lot to prove that a certain formula holds of everything. Certainly, it is not enough to prove that the formula holds of some particular things, or some particular things you know things about.

However, suppose you made up a new name, “Frabjous”, and you could prove that some formula was true of Frabjous, without knowing anything else at all about “Frabjous”. It must be that you could give the same proof about anything else in the world, since it couldn’t be anything special about Frabjous.

This is the basic idea behind universal deviation. If you want to SHOW: ∀xx…, it suffices to show …n…, where “n” is a new, made-up name that doesn’t occur anywhere above in your derivation.

Unlike CD and ID, universal derivation (UD), does not involve making an assumption.

To set one up, we simply write in a new SHOW line, making use of a new letter.

Here’s an example.

First we write “UD” on the right. Then, without any assumption line, our next line will be a new show line where we drop off the quantifier, and replace all the occurrences of the variable with the same new name:

The idea is that, if I can show the formula about some arbitrary thing I know nothing about, I can prove the universally quantified formula.

Notice that 4 is a SHOW line. I can’t use it. I still don’t really know anything about this entity “a”. I’m just giving myself something new to prove. I can prove it using the other techniques: CD, ID, or DD.

Now that I’ve shown Fa & Ga, and crossed off the “SHOW” for that line, I remember that I used the letter “a” arbitrarily—I could have done the same derivation for any other individual. Therefore, I am entitled to cross off the “SHOW” at line 3, by UD.

Here’s a UD within a CD:

Here’s an ID within a UD.

Here’s an ID within a UD within a CD.

Homework: Exercise Set 8C, Exercise Set 8D

Negation Rules

If a quantifier has a negation in front of it, we cannot use ∃O or ∀O. Remember our rules apply only to whole lines.

However, we now introduce new rules that allow us to make use of statements that begin with negations of quantifiers in front.

(These rules are redundant, but very helpful.)

~∀O (official)
~∀vA
∃v~A
~∃O (official)
~∃vA
∀v~A

~∀O (informal)
~∀xx
x~…x


(or other variable)
~∃O (informal)
~∃xx
x~…x


(or other variable)

A little reflection shows these rules to be valid.

If it’s not true that everything is F, then something must not be F.

If it’s not true that something is F, then everything must not be F.

Consider these arguments:

Not everything is colored.
Therefore, something is not colored.

It’s not true that something is omnipotent.
Therefore, everything is not omnipotent.

These arguments exemplify the patterns of reasoning above.

Another way of putting these rules is that you can “push” a negation through a quantifier if you change the quantifier.

However, you must change the quantifier. One cannot go from ~∀xx… to ∀x~…x…!

Yes, we get a double negation at line 7.

The rule only pushes the negation through: it cannot eliminate it.

Homework: Exercise Set 8E

Multiple Quantifiers, Relational Quantification

Nothing special is needed to do problems with multiple quantifiers. Simply them one at a time, and treat the letters that occur in different places as different when they’re different, and the same when they’re the same.

Also remember you can’t apply the rules to parts of lines.

Here’s a problem using two universal derivations, one right after another.

At line 3, you only change the “x”s to “a”, and at line 4 you only change the “y”s to “b”. We push negations through one at a time as well.

Only the “x”s change at line 6.

Here’s my favorite problem:

Everyone loves a lover.
Someone loves someone.
Therefore, everyone loves everyone.

The key to the problem is realizing that you can use the first premise more than once, and that you can juggle the names around as needed.

We can show everyone loves everyone by showing that, for arbitrary “people” a and b, a loves b. We do this by going through the universal statement twice. Since someone loves someone, we give them names, and call them c and d. Since c loves d, c is a lover. Since c is a lover, everyone loves c. If everyone loves c, everyone, including b, is a lover. If b is a lover, everyone, including a, loves b. So a loves b, and everyone loves everyone.

Homework: Exercise Set 8F, Exercise Set 8G

Strategies and Steps

This chart suggests a kind of derivation to do depending on your SHOW line.

SHOW lineFormTryAssumeNew SHOW
AtomicFaID~Fa
Negation~AID*A
DisjunctionABID~(AB)
ExistentialxxID**~∃xx
ConditionalABCDAB
UniversalxxUD(none)n… (new)
SplatDD(none)(none)

* = This is my advice regardless of what is being negated: ~Fa, ~(AB), ~(AB), ~(A & B), ~(AB), and even ~∃xx… and ~∀xx… should all be done by ID.

** = Most existentials can be done by DD, but IDs are often easier.

For “and” and “iff” statements, break the problem into two parts, and put them together at the end with &I or ↔I.

SHOW lineFormTryAssumeNew SHOW
BiconditionalSHOW: ABDD
first:SHOW: ABCDAB
then:SHOW: BACDBA
ConjunctionSHOW: A & BDD
first:SHOW: A ID~A
then:SHOW: B ID~B

This is the same as a chart I gave you for unit 2, adding that universals should be proven by UD, and existentials by ID.

There is also a step-by-step procedure I recommend for completing the problems after they’ve been set up.

If you’re not having trouble with derivations, you needn’t make use of these instructions, but for many students they may provide valuable help.

(This is basically the procedure “ProofAMaTron” uses when you click the “Give full answer” button.)

  1. Look at SHOW line; consult the table above and set-up the derivation.
  2. Look at the new SHOW line; if it is SHOW ✖, proceed to step 3. If it is anything else, repeat step 1 for the new SHOW line.
  3. Do any ~∃O and ~∀O steps you can. (I.e., push any negations through the quantifiers.)
  4. Do all the ∃O steps you can. Use a new letter every time.
  5. For every universal statement, do a ∀O step to every name you already have in the derivation, however many there are.
  6. Apply the DD rules. (∃I, DN, ∨O, →O, &O, ↔O, etc.)
  7. Look at results from step 6. If you got a contradiction, you can finish the derivation with ✖I. If you don’t have one, you may need to repeat steps 3–6 until you get one. If you still can’t get one, you may need to try a “desperate measures” strategy. (Remember those?)

Here are some problems that make use of these strategies and directions.

Lines 1–5 are STEPS 1–2.
Line 6 is STEP 3.
Line 7 is STEP 4.
Lines 8–9 are STEP 5.
Lines 10–13 are STEP 6.
Line 14 is STEP 7.

Lines 1–4 are STEPS 1–2.
STEP 3 is skipped, since there are no negations before quantifiers.
Line 5 is STEP 4.
STEP 5 is skipped.
Lines 6–7 are STEP 6.
STEP 7 tells us to repeat steps 3–6.
Lines 8–9 are STEP 3 repeated.
Lines 10–12 are STEP 5 repeated.
Line 13 is a new STEP 6.
Line 14 is STEP 7.

We did an unnecessary step at line 10, but that’s OK.

Biconditionals can make problems quite long, but easily do-able.

Notice that for a biconditional, we have to cycle through the steps independently for the two halves of the problem.

Homework: Exercise Set 8H

“Desperate Measures” Revisited

This is review from something we learned at the end of unit 2.

If you get stuck in a proof, look at your “if-then” and “or”-statements. What you need is a way to use →O or ∨O. To do this, you may need to introduce a new SHOW line to try to prove either that one half of an “or”-statement is false, or that the if-part of an if-then is true, or the then-part is false.

The problem is set up normally. We get stuck at line 7, so we introduce a SHOW line to give us what we would need to do ∨O on line 1.

Once SHOW is crossed off at line 8, we can use it.

Homework: Credit Exercises 3.3

REVIEW

Translations Review

REVIEW: Basics

Lower case letters (subjects/names) stand for specific individual persons, places or things.

Do not use them for plural or count noun phrases!

Upper case letters (predicates) stand for properties, traits and characteristics of specific things.

We write them before their subjects.

Monadic predicates stand for a property a thing has on its own.

Polyadic predicates stand for a relation between multiple things, and are followed by multiple subjects.

Tk Kevin is tall.
Lfa France is larger than Amherst.
Pn Neptune is a planet.
Lnf Neptune is larger than France.
Df France is democratic.
Age Gabrielle admires (X)ena.

REVIEW: Connectives vs. Polyadic Predicates

“and”/“or” between names and predicates is sometimes translated with “&”/“∨” and sometimes with a polyadic predicate.

Think about whether it can be broken into two separate thoughts.

Examples:

  1. France and Britain are democratic.
    Translation: Df & Db

  2. Either Orion or Callisto is a constellation.
    Translation: CoCc

  3. Sanjukta is intelligent and talented.
    Translation: Is & Ts

  4. Mercury and Pluto are similar.
    Translation: Smp

  5. Callisto orbits either Jupiter or Neptune.
    Translation: OcjOcn

Warning: Logical connectives “&”, “∨”, etc. must always be flanked by things that can be true or false.

Never use them simply between two subjects or predicates. The first example cannot be written as D(f & b), etc.

REVIEW: Quantifiers

Quantifiers in English are words like “all”, “some”, “only”, etc.

In predicate logic, we have two quantifiers.

x — for all values of (variable) x

x — there is a value of (variable) x

The simplest use of the quantifiers is to translate statements about “everything”, “something”, “nothing”, etc.

  1. Everything is good.
    Translation: xGx

  2. Something is infinite.
    Translation: xIx

  3. Nothing is free.
    Translation: x~Fx   or ~∃xFx

  4. Not everything is good.
    Translation: ~∀xGx  or x~Gx

  5. Everything is either good or bad.
    Translation: x(GxBx)

REVIEW: Categorical Judgments

More often we speak about all/some members of a group.

All … are _______ = ∀x( … x … → ___ x ___)
Some … are _______ = ∃x( … x … & ___x___)
No … are _______ = ∀x( … x … → ~___x___)
or ~∃x( … x … & ___x___)
Some … are not _______ = ∃x( … x … & ~___x___)

∀ almost always goes with →

∃ almost always goes with &

Be sure not to use the wrong combination!

All birds fly.

Translation: x(BxFx)

NOT: ∀x(Bx & Fx) (Everything is a bird that flies.)

REVIEW: Combined Predicates

Adjectives modifying nouns are translated using an “&”.

Something similar happens with “that”, “who”, “whom” clauses, etc.

  1. Some democratic countries are socialist.
    Translation: x[(Dx & Cx) & Sx]

  2. Some countries are not socialist democracies.
    Translation: x[Cx & ~(Dx & Sx)]

  3. No planets that rotate are inhabitable.
    Translation: x[(Px & Rx) → ~Ix]

Sometimes combined predicates require “∨”, surprisingly.

All trucks and motorcycles are prohibited.

Translation: x[(TxMx) → Px]

Not: ∀x[(Tx & Mx) → Px]

REVIEW: Practice Translations

Try them yourself, or view Prof. Klement’s answer.


Derivations Review

Homework: Unit 3 Practice Exam, Credit Exercises 3.4

And that’s all for the semester!

Time to dance!


© 2017 Kevin C. Klement