Skip to main content

Subsection 5.1.4 We Inherit All the Rules From Boolean Logic

We’ve already developed a large collection of tools for working with Boolean logic sentences. Fortunately they generalize to predicate logic in two important ways:

  • The identities can be used to transform wffs, whether or not they are statements.

  • The inference rules can be applied to fully quantified wffs.

Let’s look first at how we can use the Boolean identities. Recall that the job of the identities is to let us rewrite expressions into forms that we may find more useful.

We may want to do that to a wff that is inside the scope of one or more quantifiers. In that case, the wff itself is not a statement as it doesn’t have a truth value. We are allowed to transform such a wff into another one as long as we preserve the property that, once it is fully quantified, it will have the same truth value as the original one did. All of our Boolean identities do that. This shouldn’t come as a surprise. All of the operators that we use to build predicate logic wffs are defined in exactly the same way that they are in Boolean logic. So they have all the same properties.

For example, we can exploit the fact that and is commutative. Using that fact, we can rewrite the underlined wff on the left as the underlined one on the right:

\(\forall\) x(P(x) \(\wedge\) Q(x)) can be rewritten as \(\forall\)x(Q(x) \(\wedge\) P(x)).

Recall that one of the Boolean De Morgan’s Laws tells us that, if we “push” not through an and, the and becomes an or:

(\(\forall\)(p \(\wedge\) q)) \(\equiv\) ((\(\neg\)p) \(\vee\) (\(\neg\)q))

So suppose we want to say that late sleepers and breakfast eaters don’t overlap. We could say that everyone has the property that they don’t both sleep late and eat breakfast. We write:

\(\forall\)x (\(\forall\)(SleepsLate(x) \(\forall\) EatsBreakfast(x)))

Then, we could use De Morgan to rewrite the underlined wff above as the underlined wff below (which we can read as everyone either doesn’t sleep late or doesn’t eat breakfast, or possibly doesn’t do either):

\(\forall\)x (\(\neg\)SleepsLate(x) \(\vee\)\(\neg\)EatsBreakfast(x))

Now suppose that we are dealing with not just any wff but one that is in fact a statement. All variables in it are bound. It has a truth value. Now we can work with it in all the ways we could work with Boolean statements. We can, of course, apply the identities. And, now, we can also apply inference rules that allow us to combine statements to derive new statements that follow from the statements that we started with.

Let’s do an example of the use of a Boolean logic inference rule. Suppose that we have a close but somewhat fractious family whose dynamics can be described with the following premises (assuming that the universe is the family members):

[1] If everyone comes to the party then there will be at least one dispute:

(\(\forall\) x (HasComeToTheParty(x))) \(\rightarrow\) (\(\exists\)y (Dispute(y)))

[2] Everyone has come to the party:

(\(\forall\)x (HasComeToTheParty(x)))

We’ve underlined three wffs in [1] and [2], above. All three of them are statements. (One way to check this, in the case of [1], is to observe that  doesn’t occur inside the scope of any quantifier. There is a fully quantified wff on its left, and another one on its right.)

Recall Modus Ponens: From premises p \(\rightarrow\) q and p, infer q.

Observe that [1] has the form p \(\rightarrow\) q. And [2] is p. So we can conclude that there will be a dispute:

[1] (\(\forall\) x (HasComeToTheParty(x))) \(\rightarrow\) (\(\exists\) y (Dispute(y))) Premise

[2] (\(\forall\) x (HasComeToTheParty(x))) Premise

[3] (\(\exists\) y (Dispute(y))) Modus Ponens [1], [2]

The one thing that we’re still stuck on is the use of inference rules within the scope of quantifiers. We’ll soon see how to do that.

Exercises Exercises

Exercise Group.

1.

Consider the following dialogue:

Brady: What I think is that people who don’t watch tv are clueless.

Drew: Nah, the real truth is that clueless people don’t watch tv.

Is it possible for both Brady and Drew to be right? (Hint, write both of them in predicate logic. You can use predicates like WatchTV(x) and Clueless(x).)

  1. Yes

  2. No

Answer.
Correct answer is A.
Solution.

Explanation: They could both be right. To see why, write the claims as (assuming a domain of people):

Brady: \(\forall\)x (\(\neg\)WatchTV(x) \(\rightarrow\) Clueless(x))

Drew: \(\forall\)x (Clueless(x) \(\rightarrow\) \(\neg\)WatchTV(x))

We can rewrite both of them using Conditional Disjunction to make them a bit easier to work with:

Brady: \(\forall\)x (WatchTV(x) \(\vee\) Clueless(x))

Drew: \(\forall\)x (\(\neg\)Clueless(x) \(\vee\) \(\neg\)WatchTV(x))

If everyone watches tv then Brady is right. If no one is clueless. (i.e., everyone fails to be clueless), then Drew is right. So they can both be right.

2.

Consider the following dialogue:

Chris: What I think is that dogs that won’t play Frisbee are pretentious.

Jody: Nah, the real truth is that unpretentious dogs think Frisbee is silly and refuse to play.

Is it possible for both Jody and Chris to be right?

  1. Yes

  2. No

Answer.
Correct answer is A.
Solution.

Explanation: They could both be right. To see why, write the claims as (assuming a domain of dogs):

Chris: \(\forall\)x (\(\neg\)PlayFrisbee(x) \(\rightarrow\) Pretentious(x))

Jody: \(\forall\)x (\(\neg\)Pretentious(x) \(\rightarrow\) \(\neg\)PlayFrisbee (x))

We can rewrite both of them using Conditional Disjunction to make them a bit easier to work with:

Chris: \(\forall\)x (PlayFrisbee(x) \(\rightarrow\) Pretentious(x))

Jody: \(\forall\)x (Pretentious(x) \(\rightarrow\) \(\neg\)PlayFrisbee (x))

If, for example, all dogs are pretentious, then both Chris and Jody would be right.

3.

Consider the following dialogue:

Bryn: There aren’t any unhappy smart people.

Kelly: The way I see it, everyone is happy or not at all smart.

Is there any disagreement between Bryn and Kelly?

  1. Yes

  2. No

Answer.
Correct answer is B.
Solution.

Explanation: Bryn and Kelly have said the same thing. To see why, write the claims as (assuming a domain of people):

Bryn: \(\forall\)x (\(\neg\)(Unhappy(x) \(\wedge\) Smart(x)))

Kelly: \(\forall\)x (Happy(x) \(\vee\) \(\neg\)Smart(x))

Assuming that we can rewrite Unhappy(x) as Happy(x), and applying De Morgan to Bryn’s statement, we get:

\(\forall\)x (Happy(x) \(\vee\)\(\neg\)Smart(x))

This is exactly what Kelly said.

4.

Consider the following sentence:

∀x (∃y (¬(P(x) ∧ Q(y))))

We can use the Boolean identities to manipulate the wff that is inside the scope of the two quantifiers. Which of the following statements can be derived in that way? (Hint: Another way to ask this question is: Which of the following statements is/are equivalent to the one we started with?)

  1. ∀x (¬∃y (P(x) ∧ ¬Q(y)))

  2. ∀x (∃y (¬P(x) ∨ ¬Q(y)))

  3. ∀x (∃y (P(x) → ¬Q(y)))

  1. Just I.

  2. Just II.

  3. Just III.

  4. I and II.

  5. II and III.

Answer.
Correct answer is E.
Solution.
Explanation: It is possible to derive II from the starting statement by applying De Morgan. Then we can derive III from that by applying Conditional Disjunction. I does not mean the same thing as the other three.
5.

Consider the following sentence:

∀x ((P(x) ∧ ¬Q(x)) → R(x))

We can use the Boolean identities to manipulate the wff that is inside the scope of the quantifier. Which of the following statements can be derived in that way? (Hint: Another way to ask this question is: Which of the following statements is/are equivalent to the one we started with?)

I. ∀x (¬(P(x) ∧ ¬Q(x)) ∨ R(x))

II. ∀x ((¬P(x) ∨ ¬¬Q(x)) ∨ R(x))

III. ∀x ((¬P(x) ∨ Q(x)) ∨ R(x))

  1. Just I.

  2. Just II.

  3. Just III.

  4. Two of the three.

  5. All three.

Answer.
Correct answer is E.
Solution.
Explanation: It is possible to derive I by applying Conditional Disjunction. From that, we can derive II by applying De Morgan. From that, we can derive III by applying Double Negation.

Exercise Group.

Contagious Disgruntledness

Suppose that we have a group of people among whom grumpiness is highly contagious. If even one person gets disgruntled, the bad vibes will quickly spread to the whole group. So assume that the universe is our group of people. Then we might write:

[1] (∃x (Disgruntled(x))) → (∀x (Disgruntled(x)))

6.

(Part 1) Let’s first use everyday reasoning. (In other words, we’re not limited to the formal inference rules that we’ve so far described.) Which of the following additional premises would be sufficient, when combined with [1], to allow us to conclude that everyone is disgruntled:

I. Disgruntled(Grouchy)

II. ¬Disgruntled(Sunshine)

III. (∃x (Disgruntled(x)))

  1. Just I.

  2. Just II.

  3. Just III.

  4. I or II.

  5. I or III.

Answer.
Correct answer is E.
Solution.
Explanation: Either I or III would be sufficient. I tells us that Grouchy is disgruntled. If Grouchy is disgruntled, then we know that at least one person is. That makes (x (Disgruntled(x))) true. Given that, we can use Modus Ponens to derive that everyone is disgruntled. Alternatively, if we’re told directly that at least one person is disgruntled, we can use Modus Ponens directly.
7.

(Part 2) Now let’s use just the formal inference rules that we’ve described. Which of the following additional premises would be sufficient, when combined with [1], to allow us to conclude that everyone is disgruntled:

I. Disgruntled(Grouchy)

II. ¬Disgruntled(Sunshine)

III. (∃x (Disgruntled(x)))

  1. Just I.

  2. Just II.

  3. Just III.

  4. I or II.

  5. I or III.

Answer.
Correct answer is C.
Solution.
Explanation: Now I isn’t sufficient. Our common sense tells us that the existence of a particular disgruntled person proves that there exists such a person. But we don’t yet have a formal rule for reasoning in that way. We’ll introduce what we need soon. But for now, only III is sufficient. Given it, we can use Modus Ponens directly to derive the required conclusion.