1.2. Predicate Logic#

It is often the case that propositional logic is insufficient to represent more complex logical expressions. Enter predicate logic.

In propositional logic, the following cannot be represented.

Propositional logic is insufficient

\(p := \) “All men are mortal” and \(q := \) “Socrates is a man”. Is Socrates a mortal? The answer is yes, but this cannot be expressed in propositional logic.

We need a way to formalize objects, their properties, and relations between them.

1.2.1. Predicates and Variables#

Predicate logic augments propositional logic with variables, predicates, and quantifiers. Variables are simple. They are some symbol, for example \(x\), \(y\), or \(z\), that stands in for some mathematical object.

Definition (predicate)

A symbol which represents a property or relation. Often, the statement or relation itself is called a predicate.

Predicates are typically capital letters \(P, Q, R, S, \ldots\). Predicates are very much like propositional variables in that they stand in for something. Predicates are more general in that they need not have a truth value. Moreover, whereas propositions needed to be a declarative statement (i.e. an independent clause in a sentence), predicates can be an incomplete phrase.

A first few predicates

The following are all predicates.

  • \(D\) := “is a dog”

  • \(R\) := “has rowing as their favourite sport”

  • \(P\) := “is a positive number”

  • \(E\) := “is an even integer”

Notice from these examples that predicates typically lack subjects. Combining predicates with variables allows us to form propositional functions.

Definition (propositional function)

A function formed by a predicate and one or more variables. A proposition is obtained by applying particular values to the variable(s) or by binding the variables by logical quantifiers,

Propositional functions become propositions when their variables are replaced by a value in the domain of discourse, often called simply domain. This domain specifies what are the possible values for the variable. A domain is often denoted by \(U\).

Without a domain, a propositional function makes little sense. If \(P(x)\) stands for “\(x\) passed CS2214”, this only makes sense if the domain for \(x\) is “people who have taken CS2214”.

Propositional function

Let \(P\) be “is greater than 0”. Then, \(P(x)\) is a propositional function denoting “\(x\) is greater than 0”. If we let the domain be the integers, \(x\) may take the value of any integer.

  • \(P(-3)\) is false.

  • \(P(0)\) is false.

  • \(P(2)\) is true.

  • \(P(3.14159)\) is invalid because \(3.14159\) is not an integer.

When we replace (i.e. substitute) a particular value from the domain of discourse for a variable in a propositional function, we say that the variable is bound. We call it a bound variable. In contrast, a variable that is not bound is called a free variable.

Bound variables, propositions, predicates

Let \(R(x,y,z) := x + y = z\). Let \(Q(x,y,z) := x - y = z\). Let \(U\) be the integers for \(x\), \(y\), and \(z\). What are the truth values of the following?

  1. \(R(2, -1, 5)\)

  2. \(R(3,4,7)\)

  3. \(R(x, 3, z)\)

  4. \(Q(2, -1, 3)\)

  5. \(Q(3,4,7)\)

  6. \(Q(x,3,z)\)

Bound variables, propositions, predicates

Let \(R(x,y,z) := x + y = z\). Let \(Q(x,y,z) := x - y = z\). Let \(U\) be the integers for \(x\), \(y\), and \(z\). What are the truth values of the following?

  1. False. \(2 + (-1) \neq 5\).

  2. True. \(3 + 4 = 7\).

  3. Not a proposition. When a propositional function has at least one free variable, it is still a propositional function.

  4. True. \(2 - (-1) = 3\).

  5. False. \(3 - 4 \neq 7\).

  6. Not a proposition. When a propositional function has at least one free variable, it is still a propositional function.

Compound Expressions#

All of the logical connectives of propositional logic also apply to predicate logic. Let’s see some examples.

Connecting predicates

Let \(P(x) := x\) can fly. Let \(Q(x) := x\) are blue. Let the domain of \(x\) be all species of animals.

  • \(P( \text{penguins}) \lor P( \text{geese})\) is true.

  • \(P( \text{blue jays}) \land Q( \text{blue jays})\) is true.

  • \(P( \text{penguins}) \rightarrow Q( \text{tigers})\) is true.

We can also use logical connectives to connect propositional functions. The result is another propositional function with possibly more variables.

Connecting propositional functions

Let \(P, Q\) be predicates. Let \(x, y\) be variables.

  • \(P(2) \lor Q(5)\) is a proposition since all variables are bound.

  • \(P(3) \land P(x)\) is a propositional function with one variable.

  • \(P(x) \rightarrow P(y)\) is a propositional function with two variables.

  • \(P(y) \lor Q(x)\) is a propositional function with two variables.

1.2.2. Quantifiers#

Quantifiers are used as modifiers to variables, giving rise to the logical formalization of the English words “all”, “some”, “any”, “every”, etc. For example, “all men are mortal” or “some birds cannot fly” cannot be expressed in propositional logic but can be represented in predicate logic using quantifiers. The two main quantifiers are the universal quantifier and the existential quantifier.

Definition (universal quantifier)

“For all”, “For any”, “Given any”. A universal quantifier asserts that a predicate is true for any and every value in the domain. It is denoted \(\forall\).

Definition (existential quantifier)

“There exists”, “For some”, “There is a”, “There is at least one”. An existential quantifier asserts that a predicate is true for at least one value in the domain. It is denoted \(\exists\).

Just as substituting a variable for a value from the domain binds the variable, a quantifier also binds a variable. Let \(P\) be a predicate and \(U\) be the domain. \(\forall x P(x)\) says that \(P(x)\) is true for every choice of \(x\) from the domain. \(\exists x P(x)\) says that \(P(x)\) is true for some x in the domain.

\(\forall \,x\, P(x)\) can be read as “For all \(x\), \(P(x)\)”.

Universal quantifier

  • Let \(P(x) := x > 0\). If \(U\) is all integers, \(\forall x P(x)\) is false.

  • Let \(P(x) := 2x \text{ is even}\). If \(U\) is all integers, \(\forall x P(x)\) is true.

  • Let \(P(x) := x \text{ has feathers}\). If \(U\) is all animals, \(\forall x P(x)\) is false.

  • Let \(P(x) := x \text{ has feathers}\). If \(U\) is all birds, \(\forall x P(x)\) is true.

\(\exists \,x\, P(x)\) can be read as “There exists an \(x\) such that \(P(x)\)”.

Existential quantifier

  • Let \(P(x) := x > 0\). If \(U\) is all integers, \(\exists x P(x)\) is true.

  • Let \(P(x) := 2x \text{ is odd}\). If \(U\) is all integers, \(\exists x P(x)\) is false.

  • Let \(P(x) := x \text{ has feathers}\). If \(U\) is all animals, \(\exists x P(x)\) is true.

  • Let \(P(x) := x \text{ has feathers}\). If \(U\) is all birds, \(\exists x P(x)\) is true.

Notice that the truth value of a propositional function whose variable is bound by a quantifier depends on the particular domain of discourse.

Important

Without specifying a domain of discourse, a quantifier applied to a propositional function cannot give us a truth value. The predicate, the domain, and choice of quantifier together give a truth value.

Quantifiers and domains

Let \(P(x) := x < 2\).

  1. If \(U\) is the positive integers, what is the truth value of \(\forall \,x\, P(x)\)? What is the truth value of \(\exists \,x\, P(x)\)?

  2. If \(U\) is the negative integers, what is the truth value of \(\forall \,x\, P(x)\)? What is the truth value of \(\exists \,x\, P(x)\)?

  3. If \(U\) is the numbers \(3\), \(4\), and \(5\), what is the truth value of \(\forall \,x\, P(x)\)? What is the truth value of \(\exists \,x\, P(x)\)?

Quantifiers and domains

  1. \(\forall \,x\, P(x)\) is false. \(\exists \,x\, P(x)\) is true.

  2. \(\forall \,x\, P(x)\) is true. \(\exists \,x\, P(x)\) is true.

  3. \(\forall \,x\, P(x)\) is false. \(\exists \,x\, P(x)\) is false.

These examples suggest implications between existential and universal quantifiers.

Tip

Let \(P(x)\) be a propositional function with a universe \(U\).

  • If \(\forall \,x\, P(x)\) is true, then \(\exists \,x\, P(x)\) must be true.

  • If \(\exists \,x\, P(x)\) is false, then \(\forall \,x\, P(x)\) must be false.

That is, \(\forall \,x\, P(x) \rightarrow \exists \,x\, P(x)\) and \(\neg (\exists \,x\, P(x)) \rightarrow \neg (\forall \,x\, P(x))\).

For some domains of discourse, it is possible to “expand” a quantified expression into an equivalent compound expression with no variables. In particular, when domains are finite.

Finite domains, conjunctions, disjunctions

Let \(P\) be a predicate and \(U\) be the integers \(1\), \(2\), and \(3\).

\[\begin{split} \forall \,x\, P(x) \equiv P(1) \land P(2) \land P(3) \\[1.0em] \exists \,x\, P(x) \equiv P(1) \lor P(2) \lor P(3) \end{split}\]

Precedence of Quantifiers#

Quantifiers have a higher precedence than all other logical connectives.

\(\forall \,x\, P(x) \lor Q(x) \ \equiv\ (\ \forall \,x\, P(x)\ ) \lor Q(x)\)

\(\exists \,x\, P(x) \land Q(x) \ \equiv\ (\ \exists \,x\, P(x)\ ) \land Q(x)\)

\(\forall \,x\, P(x) \rightarrow Q(x) \ \equiv\ (\ \forall \,x\, P(x)\ ) \rightarrow Q(x)\)

\(P(x) \rightarrow \exists \,x\, Q(x) \ \equiv\ P(x) \rightarrow (\ \exists \,x\, Q(x)\ )\)

If we want a quantifier to apply to multiple predicates, we must use parentheses. \(\forall \,x\, P(x) \land Q(x)\) is not the same as \(\forall \,x\, (P(x) \land Q(x))\).

Quantified compounds

Let \(P(x) := \) “\(x\) has a son”. Let \(Q(x) :=\) “\(x\) is a parent”. Let \(U\) be all people.

\(\forall \,x\, P(x) \rightarrow Q(x)\) translates to “if every person has a son, then \(x\) is a parent”. That is, we have not bound the variable in the predicate \(Q(x)\).

\(\forall \,x\, (P(x) \rightarrow Q(x))\) translates to “For all people, if a person has a son then that person is a parent”.

Negating Quantifiers#

When we are negating expressions with quantifiers, special care must be taken. Consider first some English language examples.

Negating English

  1. “Every student in this class knows Python”

    • “It is not the case that every student in this class knows Python”, or

    • “Not every student in this class knows Python”, or

    • “At least one student in this class does not know Python”

  2. “Someone thinks football is the best sport”

    • “It is not that case that someone thinks football is the best sport”,

    • “No one thinks football is the best sport”, or

    • “Everyone thinks football is not the best sport”

Already, we can see that there are two ways to express negation with quantifiers. We can negate the quantifier itself, or we can negate the inner predicate. Formally, this is similar to De Morgan’s law for propositional logic. Negating a universal or existential quantifier “flips” it to become the other one.

\(\neg (\forall \,x\, P(x)) \equiv \exists\, x\, \neg P(x)\)

\(\neg (\exists \,x\, P(x)) \equiv \forall\, x\, \neg P(x)\)

Negating Quantifiers

Let \(P :=\) “knows Python” with \(U\) being all students in this class.

\[ \neg (\forall \,x\, P(x)) \equiv \exists \,x\, \neg P(x) \]

“There exists a student in this class who does not know Python”.

Let \(S :=\) “thinks football is the best sport” with \(U\) being all people.

\[ \neg (\exists \,x\, S(x)) \equiv \forall \,x\, \neg S(x) \]

“Everyone does not think football is the best sport”.

Truth and Fallacy of Quantifiers#

Table 1.6 Quantifiers and truth values#

Quantified Expression

Equivalent Expression

When True?

When False?

\(\forall \,x\, P(x)\)

When \(P(x)\) is true for every possible \(x\)

When \(P(x)\) is false for at least one possible \(x\)

\(\exists \,x\, P(x)\)

When \(P(x)\) is true for at least one possible \(x\)

When \(P(x)\) is false for every possible \(x\)

\(\neg \forall \,x\, P(x)\)

\(\exists \,x\, \neg P(x)\)

When \(P(x)\) is false for at least one possible \(x\)

When \(P(x)\) is true for every possible \(x\)

\(\neg \exists \,x\, P(x)\)

\(\forall \,x\, \neg P(x)\)

When \(P(x)\) is false for every possible \(x\)

When \(P(x)\) is true for at least one possible \(x\)

You should really internalize these subtle differences in each case. You will really need this throughout the course and in the future! Re-read the table and try the do the following checkpoint.

The true and false of quantifiers

Translate the following sentences to predicate logic, using quantifiers as appropriate. Can you discern a truth value from the resulting expression?

  1. “Some student in this class has visited Brazil.”

  2. “Every student in this class has visited Canada or Brazil.”

  3. “An animal that can fly is an animal with wings.”

The true and false of quantifiers

Translate the following sentences to predicate logic, using quantifiers as appropriate. Can you discern a truth value from the resulting expression?

  • Let \(B := \) “has visited Brazil”.

  • Let \(C := \) “has visited Canada”.

  • Let \(W := \) “has wings”.

  • Let \(Y := \) “can fly”.

  1. “Some student in this class has visited Brazil.”

    • If \(U\) is students in this class: \(\exists \,x\, B(x)\).

    • If \(U\) is all people, let \(S :=\) “is a student in this class. Then, we have: \(\exists \,x\, S(x) \rightarrow B(x)\).

    • I personally do not know the truth value of this. However, if you are reading this and you have been to Brazil, then your existence in this class provides an “existence proof” that the statement is true. See more in Section 1.3.

  2. “Every student in this class has visited Canada or Brazil.”

    • If \(U\) is students in this class: \(\forall \,x\, (B(x) \lor C(x))\).

    • If \(U\) is all people: \(\forall \,x\, [\ S(x) \rightarrow (B(x) \lor C(x))\ ]\)

    • The truth value of this statement is true. You are all attending school in Canada, and have been to campus in London, Ontario. The statement is true without even knowing the truth value of \(B(x)\).

  3. “An animal that can fly is an animal with wings.”

    • Let \(U\) be all animals: \(\forall \,x\, (W(x) \rightarrow Y(x))\).

    • Notice that this English statement does not explicitly use “every” or “for all”. However, it is still a statement which is stating a universality. It is stating that any animal that can fly must have wings. Therefore we use the universal quantifier.

    • The truth value of this statement is true. All animals which fly are animals which have wings. Notice that the converse is not true (penguins have wings but cannot fly). Can you prove me wrong? Do you know of an animal that can fly but doesn’t have wings? If you can identify such an animal, that would be a “proof by counterexample”. See more in Section 1.3.

1.2.3. Nested Quantifiers#

Nested quantifiers are necessary for some English sentence with several clauses and variables. It has natural extensions to math and computer science.

A first nested quantifier

“Every real number has a multiplicative inverse.”

Letting \(U\) be the real numbers:

\[ \forall \,x\, \exists \,y\, (x \times y = 1) \]

One way of thinking of nested quantifiers is through nested propositional functions. From the previous example, let \(P(x,y) := (x \times y = 1)\) and \(Q(x) := \exists \,y\, P(x,y)\). \(P(x,y)\) is saying that \(x\) and \(y\) are multiplicative inverses, meanwhile \(Q(x)\) is saying \(x\) has a multiplicative inverse.

Then, “every real number has a multiplicative inverse” can be written as:

\[\begin{split} \begin{align} \forall \,x\, Q(x) &\equiv \forall \,x\, ( \exists \,y\, P(x,y) ) \\ &\equiv \forall \,x\, ( \exists \,y\, (x \times y = 1)) \\ &\equiv \forall \,x\, \exists \,y\, (x \times y = 1) \end{align} \end{split}\]

Order of Quantifiers#

The order of quantifiers is very important. Consider again multiplicative inverses.

Let \(P(x,y) := x \times y = 1\). Are \(\forall x\ \exists y\ P(x,y)\) and \(\exists y\ \forall x\ P(x,y)\) the same?

No! The first says “every real number has a multiplicative inverse”. The second says “there exists a real number which, when multiplied by any real number, equals 1”.

Let’s try another example.

Ordering quantifiers

Let \(P(x,y) := x+y = 0\) and the domain of \(x\) and \(y\) be the real numbers. The truth value of the following expressions are:

\(\forall x\ \forall y\ P(x,y)\)

\(\forall y\ \forall x\ P(x,y)\)

\(\exists x\ \forall y\ P(x,y)\)

\(\forall y\ \exists x\ P(x,y)\)

\(\exists x\ \exists y\ P(x,y)\)

False

False

False

True

True

This previous exemplifies that the order of two universal quantifiers (or existential quantifiers) applied to a single propositional function does not change the truth value. However, the order between a universal quantifier and an existential quantifier does matter.

Tip

One way to think about nested quantifiers is that variables are bound or “fixed” left to right. In \(\exists x\ \forall y\ P(x,y)\), \(x\) is bound first, regardless of what happens to \(y\). Then \(y\) is bound.

Yet another way of thinking about nested quantifiers is as nested loops. Consider the below loop and the following quantified expressions.

for i in range(n) :
    for j in range(m) :
        P(i, j)

Expression

When is it true?

\(\forall i\ \forall j\ P(i,j)\)

This expression is only true if all iterations of both loops are true.

\(\forall i\ \exists j\ P(i,j)\)

This expression is true when, for every iteration of the outer loop, at least one iteration of the inner loop is true.

\(\exists i\ \forall j\ P(i,j)\)

This expression is true when, for at least one iteration of the outer loop, every iteration of the inner loop is true.

\(\exists i\ \exists j\ P(i,j)\)

This expression is true if at least one iteration of the inner loop is true, for any iteration of the outer loop.

Of course, when the domains of discourse are infinite, we cannot actually loop through all of the possible elements. However, it is a useful way to think about quantifiers.

Translating between English and Logic#

We have seen a several example of translating English to predicates. But what about the opposite?

Quantifiers to English

Let \(C(x) := x\) has a computer, \(F(x,y) := x\) and \(y\) are friends, where \(U\) is all students at Western.

\[ \forall x\ (C(x) \lor \exists y\ (C(y) \land F(x,y))) \]

In English, this says “every student at Western has a computer or has a friend with a computer”.

Before we start thinking about translating more interesting mathematical statements, let’s check in and make sure we understand nested quantifiers and their ordering.

Translating predicates to English

Let \(C(x) := x\) has a computer, \(F(x,y) := x\) and \(y\) are friends, where \(U\) is all students at Western.

Express the following expression in English.

\[ \exists x\ \forall y\ \forall z\ (\ (F(x,y) \land F(x,z) \land (y \neq z)) \rightarrow \neg F(y,z)\ ) \]

Translating predicates to English

Let \(C(x) := x\) has a computer, \(F(x,y) := x\) and \(y\) are friends, where \(U\) is all students at Western.

Express the following expression in English.

\[ \exists x\ \forall y\ \forall z\ (\ (F(x,y) \land F(x,z) \land (y \neq z)) \rightarrow \neg F(y,z)\ ) \]

“There exists a student with two different friends who are not friends with each other.”

Once we conclude this chapter on logic and proofs, the rest of the course will be much more mathematical. We will use the language of logic to formally state many mathematical properties, theorems, and facts. Let’s see a taste of that before returning to “fun” English statements.

Unfortunately, a large part of being able to understand, and translate, mathematical statements comes with practice. But, there is a general methodology we can use to convert mathematical statements to logic.

  1. First re-write the statement to be more verbose. Replace phrases like “\(q\) whenever \(p\)” with “if \(p\) then \(q\)” to bring the statement closer to a “direct translation”.

  2. Explicitly introduce variables. Replace phrases like “a number greater than two” with “a number \(x\) such that \(x > 2\)”.

  3. Finally, translate that sentence to a logical expression using quantifiers, predicates, and logical connectives.

Translating mathematical statements

Write “the sum of two positive integers is always positive” as a logical expression.

  1. Re-write the sentence to be more verbose: “for any two integers, if they are both positive, then their sum is positive.”

  2. Use variables explicitly: “for any two integers \(x\) and \(y\), if \(x\) and \(y\) are both positive, then their sum is positive”.

  3. Translate to a logical expression:

\[ \forall x\ \forall y\ (\ (x > 0) \land (y > 0) \rightarrow (x+y > 0)\ ), \]

where \(U\) is all integers.

Revisiting System Specifications#

Predicate logic is exceptionally useful for system specifications (recall Formal Specifications). This application requires special care with nested quantifiers and precedence between quantifiers and logical connectives. Let’s take an example.

System specifications with predicates

Consider a mail server with limited bandwidth. The designer specifies three requirements:

  1. “Every message larger than 1 megabyte must be compressed.”

  2. “Messages larger than 10 megabytes cannot be sent.”

We leave the domains implicit since they are obvious.

Let \(L(m,y) :=\) “message \(m\) is larger than \(x\) megabytes”. Let \(C(m) :=\) “message \(m\) is compressed”. Let \(S(u, m) := \) user \(u\) can send message \(m\).

  1. \(\forall\,m\, (L(m,1) \rightarrow C(m))\)

  2. \(\forall\,m\, (L(m,10) \rightarrow \forall u \neg S(u,m)) \equiv \forall\,m\, (L(m, 10) \rightarrow \neg \exists u S(u, m))\).

1.2.4. Possible Pitfalls#

We have seen that ordering or quantifiers is very important. Predicates, quantifiers, and logical connectives have a strict order of precedence that can drastically change their interpretation. When in doubt, use parentheses!

Negating many Quantifiers#

Let’s revisit that idea with the negation of a predicates. We know from Negating Quantifiers that negation “flips” a universal quantifier or existential quantifier to become the other. But what happens when we have nested quantifiers? Simply use parentheses and proceed one at a time.

\[\begin{split} \begin{align} \neg \forall x\ \exists y\ \forall z\ P(x,y,z) &\equiv \neg \left( \forall x\ \left( \exists y\ \left( \forall z\ P(x,y,z)\right)\right)\right)\\ &\equiv \left( \exists x\ \neg \left( \exists y\ \left( \forall z\ P(x,y,z)\right)\right)\right)\\ &\equiv \left( \exists x\ \left( \forall y\ \neg \left( \forall z\ P(x,y,z)\right)\right)\right)\\ &\equiv \left( \exists x\ \left( \forall y\ \left( \exists z\ \neg P(x,y,z)\right)\right)\right) \end{align} \end{split}\]

Quantifiers and Connectives#

Recall from Precedence of Quantifiers that quantifiers have a higher precedence than logical connectives. We had to use parenthesis to apply a quantifier to a compound expression.

Now, you may be wondering, is it possible to “distribute” a quantifier into a compound expression as we did with negation? The answer is sometimes.

The following are valid.

\[\begin{split} \forall x\ (P(x) \land Q(x)) \equiv \forall x\ P(x) \land \forall x\ Q(x)\\[1em] \exists x\ (P(x) \lor Q(x)) \equiv \exists x\ P(x) \lor \exists x\ Q(x) \end{split}\]

To see why, let the domain of \(x\) be \(a\), \(b\), \(c\).

\[\begin{split} \begin{align} \forall x\ (P(x) \land Q(x)) &\equiv (P(a) \land Q(a)) \land (P(b) \land Q(b)) \land (P(c) \land Q(c)) \\ &\equiv P(a) \land P(b) \land P(c) \land Q(a) \land Q(b) \land Q(c) \\ &\equiv \forall x\ P(x) \land \forall x\ Q(x) \end{align} \end{split}\]
\[\begin{split} \begin{align} \exists x\ (P(x) \lor Q(x)) &\equiv P(a) \lor P(b) \lor P(c) \lor Q(a) \lor Q(b) \lor Q(c) \\ &\equiv P(a) \lor P(b) \lor P(c) \lor Q(a) \lor Q(b) \lor Q(c) \\ &\equiv \exists x\ P(x) \lor \exists x\ Q(x) \end{align} \end{split}\]

However, in more cases, quantifiers do not distribute. Here are some counterexamples.

\[\begin{split} \exists x\ (P(x) \land Q(x)) \not\equiv \exists x\ P(x) \land \exists x\ Q(x)\\[1em] \forall x\ (P(x) \lor Q(x)) \not\equiv \forall x\ P(x) \lor \forall x\ Q(x)\\[1em] \exists x\ (P(x) \rightarrow Q(x)) \not\equiv \exists x\ P(x) \rightarrow \exists x\ Q(x)\\[1em] \forall x\ (P(x) \rightarrow Q(x)) \not\equiv \forall x\ P(x) \rightarrow \forall x\ Q(x)\\[1em] \end{split}\]

A key reason why existential quantifiers do not distribute is because the two quantifiers bind the variable in different ways. \(\exists x\ P(x) \land \exists x\ Q(x)\) means “there exists some \(x\) such that \(P(x)\) AND there exists some \(x\) such that \(Q(x)\)”. The \(x\) in the first clause is not the same \(x\) in the second clause; \(x\) was quantified twice in different contexts.

This is very different from saying \(\exists x (P(x) \land Q(x))\), which says “there exists some \(x\) such that \(P(x)\) and \(Q(x)\) are true”. In the latter, the same object \(x\) is being applied simultaneously to \(P\) and \(Q\).

Can you reason about the other expressions?

1.2.5. Exercises#

Predicates and Variables#

Exercise 1.17

Rewrite the following statements, as appropriate, using the quantifiers “for all” and “there exists”.

  1. “Not all continuous functions are differentiable.”

  2. “There is no largest real number.”

  3. “Every positive integer is the product of some collection of primes.”

Exercise 1.18

Rewrite the following statements, as appropriate, using the quantifiers “for all” and “there exists”. You don’t have to translate to predicate logic, just re-write in English being more verbose and including the phrases “for all” and “there exists” as appropriate.

  1. A polynomial with integer coefficients may have integer roots.

  2. A polygon may not be both convex and concave.

  3. Trigonometric functions are periodic.

Quantifiers#

Exercise 1.19

  • Let \(F(x) :=\) “\(x\) is a fish”

  • Let \(H(x) :=\) “\(x\) is a whale”

  • Let \(W(x) :=\) “\(x\) inhabits the water”

  • Let \(S(x) :=\) “\(x\) has scales”

If the domain of \(x\) is all animals, what is the truth value of the following?

  1. \(\forall x\ (F(x) \rightarrow W(x))\)

  2. \(\exists x\ (S(x) \rightarrow \neg W(x))\)

  3. \(\exists x\ (F(x) \land \neg S(x) \land W(x))\)

  4. \(\forall x\ S(x) \rightarrow \forall x\ W(x)\)

Exercise 1.20

  • Let \(B(x) :=\) “\(x\) is a bird”

  • Let \(E(x) :=\) “\(x\) lays eggs”

  • Let \(M(x) :=\) “\(x\) is a mammal”

  • Let \(P(x) :=\) “\(x\) is a plant”

  • Let \(W(x) :=\) “\(x\) inhabits the water”

If the domain of \(x\) is all plants and animals, translate each of these quantified statements to a natural language statement. What is the truth value of each of them?

  1. \(\forall x\ (B(x) \rightarrow E(x))\)

  2. \(\forall x\ (E(x) \rightarrow B(x))\)

  3. \(\exists x\ (W(x) \land P(x))\)

  4. \(\exists x\ (W(x) \land E(x))\)

  5. \(\forall x\ (P(x) \lor M(x) \lor B(x))\)

  6. \(\forall x\ (W(x) \rightarrow \neg M(x))\)

Exercise 1.21

Write the following English statements in predicate logic. Do this in two steps. First, re-write the statement so that any implicit quantifiers or logical connectives are explicit. Second, convert that statement to predicate logic, quantified as necessary.

  1. “Of the positive integers, there is a smallest.”

  2. “Some polynomials do not have real roots.”

  3. “Two sets may have no elements in common.”

Exercise 1.22

Let \(U\) be the set of imaginary creatures consisting of drackles, klabs, and grebbits.

  • \(D(x) := x\) is a drackle.

  • \(K(x) := x\) is a klab.

  • \(G(x) := x\) is a grebbit.

Translate the following into predicate logic statements.

  1. Everything is a drackle.

  2. Nothing is a klab.

  3. All drackles are klabs.

  4. Some drackles are grebbits.

  5. No klab is a grebbit.

Exercise 1.23

In some Far Far Away Kingdom, the Queens’s court is composed of a number of members and ranks. Let \(U\) be the set of all such ranks.

  • \(K(x) := x\) is a Knight.

  • \(B(x) := x\) is a Bard.

  • \(R(x) := x\) is royalty.

  • \(T(x) := x\) is a Thane.

Translate the following into predicate logic statements.

  1. Some people are both Knights and Bards.

  2. There are no Bards which are royal.

  3. A Thane must be a Knight.

  4. A royal may not be a Thane nor a Bard.

  5. A person who is both Knight and Bard is a Thane.

Exercise 1.24

Consider the following set of requirements.

  1. “If a user is active, then they are connected to the server”

  2. “Only users connected to the server can receive messages”

  3. “A user that requests encryption must receive encrypted messages”

Let the domain of \(u\) be all users of the system and the domain of \(e\) be “encrypted” or “unencrypted”. Let:

  • \(A(u) := u\) is an active user,

  • \(C(u) := u\) is connected to the server,

  • \(R(u, e) := u\) can receive messages of type \(e\),

  • \(E(u) := u\) has requested encryption.

Translate these requirements to quantified predicates. Is that set of propositions consistent? If so, give a satisfying truth assignment. If not, what can you add to one of these requirements (using the already supplied predicates) to make the requirements consistent?

Nested Quantifiers#

Exercise 1.25

Let \(U\) be the positive real numbers. Let \(P(x,y) := \frac{x}{y} = 1\).

What is the truth value of the following expressions?

  1. \(\forall x\ \forall y\ P(x,y)\)

  2. \(\forall x\ \exists y\ P(x,y)\)

  3. \(\exists x\ \forall y\ P(x,y)\)

  4. \(\exists x\ \exists y\ P(x,y)\)

  5. \(\forall x\ P(x,x)\)

Exercise 1.26

Let \(T(x,y)\) be the predicate “\(x\) is taking \(y\)” where the domain of \(x\) is all students and the domain of \(y\) is all courses.

Translate the following English statements into quantified predicate statements.

  1. “Every course is being taken by at least one student”

  2. “Some student is taking every course”

  3. “No student is taking all courses”

  4. “There is a course that all students are taking”

  5. “Every student is taking at least one course”

  6. “There is a course that no students are taking”

  7. “Some students are taking no courses”

  8. “No course is being taken by all students”

  9. “Some courses are being taken by no students”

  10. “No student is taking any course”

Exercise 1.27

Express the following English sentences in predicate logic. First define a predicate and then write the English sentence as a quantified predicate statement.

  1. “Brothers are siblings.”

  2. “Siblinghood is symmetric.”

  3. “Everybody loves someone.”

  4. “There is someone who is loved by everyone.”

  5. “There is someone who loves someone.”

Exercise 1.28

Let \(E(m, p) :=\) “man \(m\) has eaten pizza \(p\)” and \(T(p, i) :=\) “pizza \(p\) has ingredient \(i\) as a topping”. Let the domains of \(m\) be all men, \(i\) be all toppings available at Pizza Hut, and \(p\) be all pizzas made at Pizza Hut.

What are the English equivalents of the following logical expressions?

  1. \(\exists m\ \forall i\ \exists p\ ( T(p,i) \land E(m, p) )\)

  2. \(\exists m\ \exists p\ \forall i\ ( T(p,i) \land E(m, p) )\)

Exercise 1.29

Negate each of the logical expressions in Exercise 1.28. Ensure to distribute the negation inside of any quantifiers.

Exercise 1.30

Use quantifiers and predicates to express the statement “there is a woman who has taken a flight on every airline in the world”.

Exercise 1.31

Use quantifiers and predicates to express the statement “there is a person that has visited every country or that country no longer exists”.

Then, negate the quantified expression. What is a natural language interpretation of the negated statement?

Exercise 1.32

Use quantifiers to express the statement “there does not exist a woman who has taken a flight on every airline in the world.” That is, negate the solution to Exercise 1.30. Distribute the negation so that there is no negation applied to a quantifier.

Finally, translate that modified expression back to English.