Predicate Logic Practice 1: Q.N. and C.Q.N. Rules

Difficulty: What the hell

Welcome to the beginning of baby predicate logic.

Predicate logic looks scarier than baby propositional logic because it adds quantifiers like “for all” and “there exists.” But today’s topic is actually manageable. We are just looking at two important families of equivalences: quantifier negation (Q.N.) and categorical quantifier negation (C.Q.N.).

The basic idea is simple: once you negate a quantified statement, the quantifier flips. But there is a bit more than the two bare-bones rules I gave earlier, so let’s do this more carefully.

Q.N. Rules

These are the four standard Q.N. equivalences:

1. ¬(∀x)Px ≡ (∃x)¬Px

2. ¬(∃x)Px ≡ (∀x)¬Px

3. ¬(∀x)¬Px ≡ (∃x)Px

4. ¬(∃x)¬Px ≡ (∀x)Px

In words, those amount to the following:

• It is not the case that everything is P = something is not P.
• It is not the case that something is P = everything is not P.
• It is not the case that everything is not P = something is P.
• It is not the case that something is not P = everything is P.

The last two are just the first two with the negation already built into the predicate.

For example, if Px means “x is pissed,” then:

¬(∀x)Px ≡ (∃x)¬Px

translates as:

It is not the case that everyone is pissed = someone is not pissed.

And:

¬(∃x)Px ≡ (∀x)¬Px

translates as:

It is not the case that someone is pissed = nobody is pissed.

C.Q.N. Rules

The C.Q.N. rules are just more specific quantified negation rules for the standard categorical forms. Lest you are intimidated by scary-looking symbols, we are using P’s and Q’s instead of Greek letters:

1. ¬(∀x)(Px ⊃ Qx) ≡ (∃x)(Px • ¬Qx)

2. ¬(∃x)(Px • Qx) ≡ (∀x)(Px ⊃ ¬Qx)

3. ¬(∀x)(Px ⊃ ¬Qx) ≡ (∃x)(Px • Qx)

4. ¬(∃x)(Px • ¬Qx) ≡ (∀x)(Px ⊃ Qx)

In ordinary English, those are:

• It is not the case that all P are Q = some P are not Q.
• It is not the case that some P are Q = no P are Q.
• It is not the case that no P are Q = some P are Q.
• It is not the case that some P are not Q = all P are Q.

What students tend to screw up

The most common mistake is to negate a quantified statement without flipping the quantifier. Don’t do that.

For instance, if you start with:

¬(∀x)Px

you are not allowed to conclude:

(∀x)¬Px

Why not? Because “not everyone is pissed” does not mean “everyone is not pissed.” It only means that at least one person is not pissed.

But if you start with:

¬(∃x)(Px • ¬Qx)

you are allowed to conclude:

(∀x)(Px ⊃ Qx)

because “it is not the case that some P are not Q” just means “all P are Q.”

A quick summary

For plain Q.N.:

¬(∀x)Px ≡ (∃x)¬Px

¬(∃x)Px ≡ (∀x)¬Px

¬(∀x)¬Px ≡ (∃x)Px

¬(∃x)¬Px ≡ (∀x)Px

For categorical forms:

¬(∀x)(Px ⊃ Qx) ≡ (∃x)(Px • ¬Qx)

¬(∃x)(Px • Qx) ≡ (∀x)(Px ⊃ ¬Qx)

¬(∀x)(Px ⊃ ¬Qx) ≡ (∃x)(Px • Qx)

¬(∃x)(Px • ¬Qx) ≡ (∀x)(Px ⊃ Qx)

Negate the statement, flip the quantifier, and then make sure the predicate or categorical form comes out right.

Exercises

Now derive the indicated conclusions. These are easy on purpose. Predicate logic is annoying enough already.

Exercise 1

1. ¬(∀x)Px

∴ (∃x)¬Px

Exercise 2

1. ¬(∃x)Qx

∴ (∀x)¬Qx

Exercise 3

1. ¬(∀x)(Px ⊃ Qx)

∴ (∃x)(Px • ¬Qx)

I’ll probably post the answers tomorrow. Have fun, and don’t let the quantifiers bully you.