1.4.5: Logical equivalence

To calculate in predicate logic, we need a notion of logical equivalence. Clearly, there are pairs of propositions in predicate logic that mean the same thing. Consider the pro- positions ¬(∀xH(x)) and ∃x(¬H(x)), where H(x) represents ‘x is happy’. The first of these propositions means “Not everyone is happy”, and the second means “Someone is not happy”. These statements have the same truth value: If not everyone is happy, then someone is unhappy and vice versa. But logical equivalence is much stronger than just having the same truth value. In propositional logic, logical equivalence is defined in terms of propositional variables: two compound propositions are logically equivalent if they have the same truth values for all possible truth values of the propositional variables they contain. In predicate logic, two formulas are logically equivalent if they have the same truth value for all possible predicates.

Consider ¬(∀xP(x)) and ∃x(¬P(x)). These formulas make sense for any predicate P, and for any predicate P they have the same truth value. Unfortunately, we can’t— as we did in propositional logic—just check this fact with a truth table: there are no subpropositions, connected by ∧, ∨, etc, out of which to build a table. So, let’s reason it out: To say ¬(∀xP(x)) is true is just to say that it is not the case that P(x) is true for all possible entities x. So, there must be some entity a for which P(a) is false. Since P(a) is false, ¬P(a) is true. But saying that there is an a for which ¬P(a) is true is just saying that∃x(¬P(x)) is true. So, the truth of ¬(∀xP(x)) implies the truth of ∃x(¬P(x)). On the other hand, if ¬(∀xP(x)) is false, then ∀xP(x) is true. Since P(x) is true for every x, ¬P(x)is false for every x; that is, there is no entity a for which the statement ¬P(a) is true. But this just means that the statement ∃x(¬P(x)) is false. In any case, then, the truth values of ¬(∀xP(x)) and ∃x(¬P(x)) are the same. Since this is true for any predicate P, we will say that these two formulas are logically equivalent and write ¬(∀xP(x)) ≡ ∃x(¬P(x)).

Figure 2.10: Four important rules of predicate logic. P can be any one-place predicate, and Q can be any two-place predicate. The first two rules are called DeMorgan’s Laws for predicate logic.

A similar argument would show that ¬(∃xP(x)) ≡ ∀x(¬P(x)). These two equival- ences, which explicate the relation between negation and quantification, are known as DeMorgan’s Laws for predicate logic. (They are closely related to DeMorgan’s Laws for propositional logic; see the exercises.) These laws can be used to help simplify expressions. For example,

\(\neg \forall y(R(y) \vee Q(y)) \equiv \exists y(\neg(R(y) \vee Q(y)))\)

\(\equiv \exists y((\neg R(y)) \wedge(\neg Q(y))\)

It might not be clear exactly why this qualifies as a ‘simplification’, but it’s generally considered simpler to have the negation operator applied to basic propositions such as R(y), rather than to quantified expressions such as ∀y(R(y) ∨ Q(y)). For a more complicated example:

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

≡ ∀x((¬P(x)) ∨ (¬∀y(Q(y) → Q(x))))
≡ ∀x((¬P(x)) ∨ (∃y(¬(Q(y) → Q(x)))))

≡ ∀x((¬P(x)) ∨ (∃y(¬(¬Q(y) ∨ Q(x)))))

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

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

DeMorgan’s Laws are listed in Figure 2.10 along with two other laws of predicate logic. The other laws allow you to interchange the order of the variables when two quantifiers of the same type (both ∃ or ∀) occur together.

Notice however that we may not change the order of quantifiers that are not the same! For instance: ∀x∃y(R(x, y)) ̸≡ ∃y∀x(R(x, y)). If you are not convinced about this, try to draw up a Tarski’s world that shows this unequivalence.

To define logical equivalence in predicate logic more formally, we need to talk about formulas that contain predicate variables, that is, variables that act as place-holders for arbitrary predicates in the same way that propositional variables are place-holders for propositions and entity variables are place-holders for entities. With this in mind, we can define logical equivalence and the closely related concept of tautology for predicate logic. We’ll see that these are crucial pieces of writing proofs.

Definition 2.9.

Let P be a formula of predicate logic which contains one or more predicate variables. P is said to be a tautology if it is true whenever all the predicate variables that it contains are replaced by actual predicates. Two formulas P and Q are said to be logically equivalent if P ↔ Q is a tautology, that is if P and Q always have the same truth value when the predicate variables they contain are replaced by actual predicates. The notation P ≡ Q asserts that P is logically equivalent to Q.

Exercises

1. Simplify each of the following propositions. In your answer, the ¬ operator should be applied only to individual predicates.

a) ¬ ∀x(¬P(x)) b) ¬ ∃x(P(x) ∧ Q(x))

c) ¬ ∀z(P(z) → Q(z)) b) ¬ ∃x(P(x) ∧ Q(x)))

e) ¬ ∀x∃yP(x, y) f) ¬ ∃x(R(x) ∧ ∀yS(x, y))

g) ¬ ∃y(P(y) ↔ Q(y)) h) ¬(∀x(P(x) → (∃xQ(x,y)))

2. Give a careful argument to show that the second of DeMorgan’s laws for predicate calculus,

¬(∀xP(x)) ≡ ∃x(¬P(x)), is valid.

3. Find the negation of each of the following propositions. Simplify the result; in your answer, the ¬ operator should be applied only to individual predicates.

a) ∃n(∀sC(s, n))
b) ∃n(∀s(L(s, n) → P(s)))

c) ∃n(∀s(L(s, n) → (∃x∃y∃zQ(x, y, z)))).
d) ∃n(∀s(L(s, n) → (∃x∃y∃z(s = xyz ∧ R(x, y) ∧ T(y) ∧ U(x, y, z)))).

4. Suppose that the domain of discourse for a predicate P contains only two entities. Show that∀xP(x) is equivalent to a conjunction of two simple propositions, and ∃xP(x) is equivalent to a disjunction. Show that in this case, DeMorgan’s Laws for propositional logic and DeMorgan’s Laws for predicate logic actually say exactly the same thing. Extend the results to a domain of discourse that contains exactly three entities.

5. Let H(x) stand for “x is happy”, where the domain of discourse consists of people. Express the proposition “There are exactly three happy people” in predicate logic.

6. What is the difference between the following two statements?

∃xRed(x) ∧ ∃xSquare(x) and ∃x(Red(x) ∧ Square(x))

7. Draw a Tarski world for the last exercise.
8. Express Johan Cruyff’s statement “There is only one ball, so you need to have it” in predicate logic.

9. Let T(x, y) stand for ‘x has taken y’, where the domain of discourse for x consists of students and the domain of discourse for y consists of CS courses (at TUDelft). Translate each of the following propositions into an unambiguous English sentence:

a) ∀x ∀y T(x, y) b) ∀x ∃y T(x, y)

c) ∀y ∃x T(x, y) d) ∃x ∃y T(x, y)

e) ∃x ∀y T(x, y) f) ∃y ∀x T(x, y)

10. Let F(x, t) stand for “You can fool person x at time t.” Translate the following sentence into predicate logic: “You can fool some of the people all of the time, and you can fool all of the people some of the time, but you can’t fool all of the people all of the time.”

11. Translate each of the following sentences into a proposition using predicate logic. Make up any predicates you need. State what each predicate means and what its domain of discourse is.

a) All crows are black.
b) Any white bird is not a crow.

c) Not all politicians are honest.
d) All purple elephants have green feet.
e) There is no one who does not like pizza.

f) Anyone who passes the final exam will pass the course.
g) If x is any positive number, then there is a number y such that \(y^{2}=x\).

12. Consider the following description of a Tarski World. Does an instance of a Tarski World exist with these properties? If so, give one with a domain of at most 5 elements. If no such instance exists, explain why not.

• ∀x(Circle(x) → ¬Blue(x))

• ∃x(Circle(x))∧∃x(Blue(x))

• RightOf(a,b)
• LeftOf(a,b)∨Square(c)

13. The sentence “Someone has the answer to every question” is ambiguous. Give two translations of this sentence into predicate logic, and explain the difference in meaning.

14. The sentence “Jane is looking for a dog” is ambiguous. One meaning is that there is some particular dog—maybe the one she lost—that Jane is looking for. The other meaning is that Jane is looking for any old dog—maybe because she wants to buy one. Express the first meaning in predicate logic. Explain why the second meaning is not expressed by ∀x(Dog(x) →LooksFor(jane, x)). In fact, the second meaning cannot be expressed in predicate logic. Philosophers of language spend a lot of time thinking about things like this. They are especially fond of the sentence “Jane is looking for a unicorn”, which is not ambiguous when applied to the real world. Why is that?