critical thinking – Philosophy without Bullshit

Predicate Logic Practice 2: The Four Quantifier Rules (Answers)

Difficulty: What the hell

Here are the answers to our second baby predicate-logic practice. This time the main point was to get used to the four quantifier rules—U.I., U.G., E.I., and E.G.—along with the irritating but necessary business of flagging.

If you made it through these without wanting to throw your book across the room, congratulations.

Exercise 1

1. (∀x)(Px ⊃ Qx)

2. (∃x)Px

∴ (∃x)Qx

3. Pa         E.I. 2 (a is a new flagged name)

4. Pa ⊃ Qa   U.I. 1

5. Qa         modus ponens 3, 4

6. (∃x)Qx   E.G. 5

Exercise 2

1. (∀x)(Px ⊃ Qx)

2. (∀x)(Qx ⊃ Rx)

3. (∃x)Px

∴ (∃x)Rx

4. Pa         E.I. 3 (a is a new flagged name)

5. Pa ⊃ Qa   U.I. 1

6. Qa         modus ponens 4, 5

7. Qa ⊃ Ra   U.I. 2

8. Ra         modus ponens 6, 7

9. (∃x)Rx   E.G. 8

Exercise 3

1. ¬(∃x)Px

2. (∃x)Qx

∴ (∃x)(Qx • ¬Px)

3. (∀x)¬Px     Q.N. 1

4. Qa           E.I. 2 (a is a new flagged name)

5. ¬Pa         U.I. 3

6. Qa • ¬Pa   conjunction 4, 5

7. (∃x)(Qx • ¬Px)   E.G. 6

Exercise 4

1. (∀x)(Px ⊃ Qx)

2. (∀x)(Qx ⊃ Rx)

∴ (∀x)(Px ⊃ Rx)

3. Let a be arbitrary.

4. Pa ⊃ Qa   U.I. 1

5. Qa ⊃ Ra   U.I. 2

6. Assume Pa

7. Qa         modus ponens 4, 6

8. Ra         modus ponens 5, 7

9. Pa ⊃ Ra   conditional proof 6–8

10. (∀x)(Px ⊃ Rx)   U.G. 9

That last one is the important one. It shows why flagging matters. You are only allowed to generalize from a because a was treated as arbitrary rather than as some special individual smuggled in from elsewhere.

Next time, we can either do a few more quantifier-rule exercises or move on to slightly nastier proofs that combine the quantifier rules with things like reductio and conditional proof. Predicate logic only gets more annoying from here, but at least now the annoyingness is beginning to take shape.

Predicate Logic Practice 2: The Four Quantifier Rules

Difficulty: What the hell

Today we move from baby predicate logic’s quantified-negation rules to the four quantifier rules themselves:

universal instantiation (U.I.)
universal generalization (U.G.)
existential instantiation (E.I.)
existential generalization (E.G.)

These are the rules that let you move between quantified statements and statements about particular individuals. And yes, this is also where flagging shows up and starts annoying people.

The basic idea

Predicate logic talks not just about whether P and Q are true, but about whether things are true of all individuals or of some individual. That is why we need quantifiers in the first place:

(∀x)Px = everything is P

(∃x)Px = something is P

The quantifier rules tell you when you are allowed to move from those quantified claims to singular claims like Pa, and when you are allowed to move back up again.

1. Universal Instantiation (U.I.)

U.I. is the easy one.

(∀x)Px

∴ Pa

If everything is P, then of course a is P. And likewise:

(∀x)(Px ⊃ Qx)

∴ Pa ⊃ Qa

Whatever is true of everything can be applied to any particular individual you like.

2. Existential Generalization (E.G.)

E.G. is also pretty easy.

Pa

∴ (∃x)Px

If a is P, then something is P. Likewise:

Pa • Qa

∴ (∃x)(Px • Qx)

If some particular individual has the relevant properties, then there exists at least one thing with those properties.

3. Existential Instantiation (E.I.)

This is where the mild irritation begins.

Suppose you know:

(∃x)Px

You are allowed to introduce a new name, say a, and write:

Pa

But only under a restriction: a has to be a new flagged name.

What does that mean? It means you are not allowed to pretend that the existential claim is about some already familiar individual. You are just saying: “Fine, let’s call the thing whose existence is guaranteed by the premise ‘a’.” But that ‘a’ is temporary and special. It is standing in for an arbitrary witness to the existential claim.

So E.I. looks like this:

(∃x)Px

∴ Pa (a is a new flagged name)

Why the flag? Because if you are sloppy here, you can prove ridiculous garbage. Existential claims give you some individual, not necessarily one you were already talking about.

4. Universal Generalization (U.G.)

U.G. goes the other direction:

Pa

∴ (∀x)Px

But again, there is a restriction. You are only allowed to do this when a is a properly flagged arbitrary individual.

In other words, you cannot just notice that Socrates is mortal and then conclude that everyone is mortal. That would be insane. You need a to stand for an arbitrary individual, not a special one. If you prove something about an arbitrary individual, then you are allowed to generalize it to everybody.

So U.G. looks like this:

Pa (a is arbitrary / properly flagged)

∴ (∀x)Px

So what the hell is flagging?

Flagging is just a way of marking a name as special for proof purposes.

There are two main uses:

In E.I., the flagged name is a temporary witness to an existential claim.
In U.G., the flagged name must be arbitrary if you want to generalize from it.

So the short version is:

E.I. gives you a new flagged individual.
U.G. requires an arbitrary flagged individual.

If you blur those roles, predicate logic becomes a mess very quickly.

How Q.N. and C.Q.N. fit in

Q.N. and C.Q.N. often help you get a quantified statement into a form where you can actually use the four quantifier rules.

For example, from:

¬(∃x)Px

you may first use Q.N. to get:

(∀x)¬Px

and only then use U.I. to get:

¬Pa

Likewise, from:

¬(∀x)(Px ⊃ Qx)

you may use C.Q.N. first to get:

(∃x)(Px • ¬Qx)

and then use E.I. to work with:

Pa • ¬Qa

So Q.N. and C.Q.N. are often what let the rest of the machinery start moving.

What students tend to screw up

They instantiate an existential claim with a name that is not new.
They generalize from a name that was never arbitrary.
They forget that Q.N. and C.Q.N. often need to happen before the quantifier rules can be applied nicely.
They panic when they see a flagged name and start pushing symbols around like a raccoon in a trash can.

Exercises

Now derive the indicated conclusions. These are not one-step gimmies. Each of them should take at least several steps if you do them cleanly.

Exercise 1

1. (∀x)(Px ⊃ Qx)

2. (∃x)Px

∴ (∃x)Qx

Exercise 2

1. (∀x)(Px ⊃ Qx)

2. (∀x)(Qx ⊃ Rx)

3. (∃x)Px

∴ (∃x)Rx

Exercise 3

1. ¬(∃x)Px

2. (∃x)Qx

∴ (∃x)(Qx • ¬Px)

Exercise 4

1. (∀x)(Px ⊃ Qx)

2. (∀x)(Qx ⊃ Rx)

∴ (∀x)(Px ⊃ Rx)

That last one is where the idea of an arbitrary flagged individual really starts to matter.

Next time, I’ll probably post the answers. Until then, try not to let the quantifiers and flags make you spiral.

Predicate Logic Practice 1: Q.N. and C.Q.N. Rules (Answers)

Difficulty: What the hell

Here are the answers to our first baby predicate-logic practice. As you probably noticed, Exercises 1 and 2 are basically one-step applications of Q.N. That’s fine. They’re warm-ups. Exercise 3 can also be done as a one-step application of C.Q.N., but I want to make it a little more interesting by breaking it down into multiple steps.

Exercise 1

1. ¬(∀x)Px

∴ (∃x)¬Px

2. (∃x)¬Px Q.N. 1

Exercise 2

1. ¬(∃x)Qx

∴ (∀x)¬Qx

2. (∀x)¬Qx Q.N. 1

Exercise 3

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

∴ (∃x)(Px • ¬Qx)

2. (∃x)¬(Px ⊃ Qx)         Q.N. 1

3. (∃x)¬(¬Px ∨ Qx)       conditional exchange 2

4. (∃x)(¬¬Px • ¬Qx)     De Morgan’s law 3

5. (∃x)(Px • ¬Qx)         double negation 4

Of course, Exercise 3 could also have been done in one step by applying C.Q.N. directly. But there’s something satisfying about watching the thing unfold instead of just smashing the correct rule on it like a button.

Next time, we’ll look at the four quantifier rules: universal instantiation, universal generalization, existential instantiation, and existential generalization—along with flagging, which is where predicate logic starts getting a little more annoying. I’m rusty on that stuff myself at the moment, so I’ll have to brush up before pretending to teach it. Until next time, then.

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.

Baby Logic Practice 3: Conditional Proofs

Difficulty: What the hell

Today’s baby logic practice is on conditional proof. The basic idea is simple: if assuming P lets you derive Q, then you are allowed to conclude that P → Q.

So, for each of the following exercises, derive the indicated conclusion using conditional proof. No quantifiers. No modal logic. No funny business. Just assumptions, a little patience, and the sweet smell of valid inference.

Exercise 1

1. P → Q

∴ P → Q

Exercise 2

1. P → Q

2. Q → R

∴ P → R

Exercise 3

1. P ∧ Q

∴ P → Q

Exercise 4

1. P → (Q → R)

2. P

∴ Q → R

Exercise 5

1. P → Q

2. R → S

3. P ∧ R

∴ P → S

Exercise 6

1. P → Q

2. Q → R

3. R → S

∴ P → S

Exercise 7

1. P → Q

2. P → R

∴ P → (Q ∧ R)

Exercise 8

1. P → Q

2. Q → (R ∨ S)

3. ¬R

∴ P → S

Some of these are pretty easy. Good. Conditional proof should start to feel almost annoyingly natural after enough practice. That is the point.

I’ll probably post the answers tomorrow. Have fun.

Baby Logic Practice 2: Derive the Conclusions Using Reductio (Answers)

Difficulty: What the hell

Here are the answers to Baby Logic Practice 2. As promised, each proof uses reductio ad absurdum, even in cases where there are quicker ways to get the conclusion.

Exercise 1

1. P → Q

2. ¬Q

∴ ¬P

3. Assume P

4. Q modus ponens 1, 3

5. ⊥ contradiction 2, 4

6. ¬P reductio 3–5

Exercise 2

1. P ∨ Q

2. ¬P

∴ Q

3. Assume ¬Q

4. ¬P ∧ ¬Q conjunction 2, 3

5. ¬(P ∨ Q) De Morgan’s Law, 4

6. ⊥ contradiction 1, 5

7. Q reductio 3–6

Exercise 3

1. (P ∧ Q) → R

2. P

3. ¬R

∴ ¬Q

4. Assume Q

5. P ∧ Q conjunction 2, 4

6. R modus ponens 1, 5

7. ⊥ contradiction 3, 6

8. ¬Q reductio 4–7

Exercise 4

1. P → Q

2. Q → R

3. ¬R

∴ ¬P

4. Assume P

5. Q modus ponens 1, 4

6. R modus ponens 2, 5

7. ⊥ contradiction 3, 6

8. ¬P reductio 4–7

Exercise 5

1. P → (Q ∨ R)

2. ¬Q

3. ¬R

∴ ¬P

4. Assume P

5. Q ∨ R modus ponens 1, 4

6. ¬Q ∧ ¬R conjunction 2, 3

7. ¬(Q ∨ R) De Morgan’s Law, 6

8. ⊥ contradiction 5, 7

9. ¬P reductio 4–8

Exercise 6

1. P ↔ Q

2. ¬Q

∴ ¬P

3. P → Q biconditional elimination, 1

4. Assume P

5. Q modus ponens 3, 4

6. ⊥ contradiction 2, 5

7. ¬P reductio 4–6

Exercise 7

1. P ∨ Q

2. P → R

3. Q → R

4. ¬R

∴ ¬P ∧ ¬Q

5. Assume P

6. R modus ponens 2, 5

7. ⊥ contradiction 4, 6

8. ¬P reductio 5–7

9. Assume Q

10. R modus ponens 3, 9

11. ⊥ contradiction 4, 10

12. ¬Q reductio 9–11

13. ¬P ∧ ¬Q conjunction 8, 12

Exercise 8

1. (P ∨ Q) → R

2. ¬R

∴ ¬P

3. Assume P

4. P ∨ Q addition 3

5. R modus ponens 1, 4

6. ⊥ contradiction 2, 5

7. ¬P reductio 3–6

So there you have it—the answers to our second baby logic quiz. Reductio can feel a little roundabout, but that’s part of what makes it useful: it forces you to see exactly where an assumption blows up.

Baby Logic Practice 2: Derive the Conclusions Using Reductio

Difficulty: What the hell

Today’s baby logic practice is on reductio ad absurdum, also known as indirect proof. The basic idea is simple: if assuming the opposite of what you want to prove leads to a contradiction, then the thing you wanted to prove must be true.

So, for each of the following exercises, derive the indicated conclusion using reductio. No quantifiers. No modal logic. No funny business. Just contradiction, negation, and a little patience.

Exercise 1

1. P → Q

2. ¬Q

∴ ¬P

Exercise 2

1. P ∨ Q

2. ¬P

∴ Q

Exercise 3

1. (P ∧ Q) → R

2. P

3. ¬R

∴ ¬Q

Exercise 4

1. P → Q

2. Q → R

3. ¬R

∴ ¬P

Exercise 5

1. P → (Q ∨ R)

2. ¬Q

3. ¬R

∴ ¬P

Exercise 6

1. P ↔ Q

2. ¬Q

∴ ¬P

Exercise 7

1. P ∨ Q

2. P → R

3. Q → R

4. ¬R

∴ ¬P ∧ ¬Q

Exercise 8

1. (P ∨ Q) → R

2. ¬R

∴ ¬P

In some of these, reductio will feel a little artificial because there are quicker ways to get the conclusion. Too bad. The point today is to practice reductio, not to be efficient.

I’ll probably post the answers tomorrow. Have fun.

Baby Logic Practice 1: Derive the Conclusions (Answers)

Difficulty: What the hell

Here are the answers to yesterday’s baby logic practice.

Exercise 1

1. P → Q

2. Q → R

3. P ∨ S

4. ¬R

∴ S

5. ¬Q modus tollens 2, 4

6. ¬P modus tollens 1, 5

7. S disjunctive syllogism 3, 6

Exercise 2

1. P → (Q ∧ R)

2. ¬R ∨ S

3. P

∴ S

4. Q ∧ R modus ponens 1, 3

5. R simplification 4

6. ¬¬R double negation 5

7. S disjunctive syllogism 2, 6

Exercise 3

1. P → Q

2. R → S

3. ¬Q

4. P ∨ R

∴ S

5. Q ∨ S constructive dilemma 1, 2, 4

6. S disjunctive syllogism 3, 5

Exercise 4

1. (P ∨ Q) → R

2. ¬R

∴ ¬P ∧ ¬Q

3. ¬(P ∨ Q) modus tollens 1, 2

4. ¬P ∧ ¬Q De Morgan’s Law 3

Exercise 5

1. P → Q

2. Q → (R ∨ S)

3. ¬R

4. P

∴ S

5. P → (R ∨ S) hypothetical syllogism 1, 2

6. R ∨ S modus ponens 4, 5

7. S disjunctive syllogism 3, 6

Exercise 6

1. P ↔ Q

2. Q → R

3. ¬R

∴ ¬P

4. P → Q biconditional elimination/material equivalence 1

5. P → R hypothetical syllogism 2, 4

6. ¬P modus tollens 3, 5

Exercise 7

1. (P ∧ Q) → R

2. P

3. ¬R

∴ ¬Q

4. ¬(P ∧ Q) modus tollens 1, 3

5. ¬P ∨ ¬Q De Morgan’s Law 4

6. ¬¬P double negation 2

7. ¬Q disjunctive syllogism 5, 6

Exercise 8

1. P → Q

2. Q → R

3. R → S

4. ¬S

∴ ¬P

5. P → R hypothetical syllogism 1, 2

6. P → S hypothetical syllogism 3, 5

7. ¬P modus tollens 4, 6

So there you have it–the answers to our first baby logic quiz.

Baby Logic Practice 1: Derive the Conclusions

Difficulty: What the hell

Today’s post is simple: a few symbolic-logic proof exercises. No quantifiers. No modal logic. Just derive the indicated conclusions from the premises supplied. These are not one-step gimmies, so slow down and actually work through them.

I’ll likely post solutions tomorrow.

Exercise 1

1. P → Q

2. Q → R

3. P ∨ S

4. ¬R

∴ S

Exercise 2

1. P → (Q ∧ R)

2. ¬R ∨ S

3. P

∴ S

Exercise 3

1. P → Q

2. R → S

3. ¬Q

4. P ∨ R

∴ S

Exercise 4

1. (P ∨ Q) → R

2. ¬R

∴ ¬P ∧ ¬Q

Exercise 5

1. P → Q

2. Q → (R ∨ S)

3. ¬R

4. P

∴ S

Exercise 6

1. P ↔ Q

2. Q → R

3. ¬R

∴ ¬P

Exercise 7

1. (P ∧ Q) → R

2. P

3. ¬R

∴ ¬Q

Exercise 8

1. P → Q

2. Q → R

3. R → S

4. ¬S

∴ ¬P

If these still feel too easy, good. Basic logical competence should eventually feel boringly obvious. That’s the point.

Baby Logic: What the Heck are Sufficient and Necessary Conditions?

Difficulty: What the heck

In logic, words like “if,” “only if,” “if and only if,” and “unless” express different logical relationships. So if you conflate those terms and symbolize them incorrectly, you end up with confused garbage. Today’s post is on what “if,” “only if,” “if and only if,” and “unless” mean in logic.

“If”

This one is pretty straightforward. When we say “If P, then Q,” we mean that P is a sufficient condition for Q. That means that if P is true, that is enough for us to say that Q is true.

For instance, in the sentence “If Einstein is a parrot, then he is a bird,” Einstein’s being a parrot is sufficient for us to say that he is a bird. We symbolize a statement like this as follows:

P → Q

In this conditional, P is called the antecedent, and Q is called the consequent.

“Only if”

Now, that is logically equivalent to saying, “Einstein is a parrot only if he is a bird.” In ordinary language, whatever immediately follows “only if” is the necessary condition.

So the sentence “Einstein is a parrot only if he is a bird” means that being a bird is necessary for being a parrot. In other words, if it is true that Einstein is a parrot, then it must also be true that Einstein is a bird. So, once again, we symbolize the sentence like this:

P → Q

This is one reason people get confused: the phrase “only if” often makes them want to reverse the conditional. Don’t. The thing after “only if” gives you the necessary condition, not the antecedent.

Also note that this is equivalent to saying, “Only if Einstein is a bird is he a parrot.” That sounds more awkward, but the logical relationship is the same.

“If and only if”

Now consider the following sentence:

I will kick your ass if and only if you kick my ass.

This is what is called a biconditional. It means that each side is both necessary and sufficient for the other. In other words, the sentence can be broken down into two conditionals:

If you kick my ass, I will kick your ass.

If I kick your ass, you will kick my ass.

These can be symbolized as follows:

P → Q

Q → P

And those two together can be symbolized like this:

P ↔ Q

So “if and only if” means both directions hold. That is why it is stronger than plain old “if.”

“Unless”

And then there is “unless,” which seems like a pain in the ass to symbolize, but is not that hard once you get the hang of it. A useful rule of thumb is that “unless” can often be translated as “if not.”

So, “You will die unless you upload your brain to a computer” is logically equivalent to, “If you do not upload your brain to a computer, you will die.” This can be symbolized as:

¬B → D

where ‘¬’ means ‘not’, ‘B’ = ‘you upload your brain to a computer’, and ‘D’ = ‘you will die’.

So you can think of “unless” this way: “Unless B, D” means “If not B, then D.”

One last quick summary

Here is the baby-logic version:

If = sufficient condition
Only if = necessary condition
If and only if = necessary and sufficient condition
Unless = usually easiest to symbolize as “if not”

If you keep those straight, you will already be ahead of a whole lot of students who mangle conditionals into logical mush.

Apologies for the morbid tone today. Oh well. Until next time, then!