Skip to main content
Logo image

Discrete Math for Shockers

John Hammond

Section 2.3 Propositional Functions and Quantifiers

We often consider very similar propositions over and over: \(3 \lt 5\text{,}\) \(2 \lt 5\text{,}\) \(7 \lt 5\text{,}\) etc... In this section, we take what is in common with these statements and build a generic function whose input is from some domain (in this example, numbers), and whose output is either true or false.

Subsection Predicates

Consider this mathematical sentence: “\(x \lt 5 \)”.
  • \(x\) is a variable, the subject of the sentence.
  • “is less than five” is the predicate
  • A predicate is a property that a subject can have.
  • We can write \(P(x) :=\) “\(x \lt 5 \text{,}\)” where
    • the value of \(P(x)\) is the value of the propositional function \(P\) at \(x\text{.}\)
    • Assigning a value to \(x\) makes \(P\) a proposition (it then has a truth value)

Definition 2.3.1. Domain of Discourse.

The domain of discourse (or universe of discourse) is the collection from which variables can take values.
For example, if my predicate function is “\(x\) is sharp”, the function has a different meaning if my universe of discourse is “all college students” versus “all tools.”
The domain of discourse is the domain of the propositional function. Like all functions, it depends on the particular function we’re considering. The codomain of a propositional function will always be the set \(\{\text{true, false}\}\text{.}\)

Example 2.3.2.

Determine the truth values of the following:
  1. If \(P(x):=\) “The word \(x \) contains the letter a”.
    1. \(P\)(elephant)
    2. \(P\)(purple)
    3. \(P\)(true)
    4. \(P\)(false)
  2. If \(Q(x,y):=\) “\(x^2 + y^2 = 25\)”.
    1. \(\displaystyle Q(4,5)\)
    2. \(\displaystyle Q(3,4)\)
Video / Answer.

Subsection Logical Quantifiers

With the idea of generic propositional functions taken care of, we now want to make sweeping claims about the truth of a propositional function over some domain. Is the statement true for every value in the domain? Is the statement true for some specific value? These questions come up so frequently in mathematics that we give them each their own symbol.

Definition 2.3.3. Universal Quantifier.

The universal quantification of \(P(x)\) is the statement that \(P(x)\) is true for all values of \(x\) in the domain of discourse. We write \(\forall x P(x)\)
A counterexample is an \(x\) value for which \(P(x)\) is false.
Video / Answer.

Definition 2.3.4. Existential Quantifier.

The existential quantification of \(P(x)\) is the statement that there is some value \(x\) in the universe of discourse for which \(P(x)\) is true. We write \(\exists x P(x)\)
Video / Answer.

Example 2.3.5.

Let \(P(x)\) be “\(x^2 \ge 0\)”. What is the truth value of \(\forall x P(x)\) if the domain is:
  1. All real numbers
  2. All complex numbers

Example 2.3.6.

Let the domain be all real numbers. Find a counterexample to the following statements:
  1. \(\displaystyle \forall x (x^2 \not= x)\)
  2. \(\displaystyle \forall x (|x| \gt 0)\)
  3. \(\displaystyle \forall x (x \gt 3 \vee x \lt 2)\)
Video / Answer.

Example 2.3.7.

We can combine quantifiers, where each variable might come from a different domain. Precedence of quantifiers is left to right.
What is the truth value of the following expressions where the domain is all real numbers:
  1. \(\displaystyle \forall x \exists y ( xy = 5)\)
  2. \(\displaystyle \exists x \forall y ( xy = 5)\)
Video / Answer.

Remark 2.3.8. Negating Quantifiers.

The negation of quantifiers is found as follows:
\begin{align*} \neg \forall x P(x) \amp\equiv \exists x \neg P(x) \\ \neg \exists x P(x) \amp\equiv \forall x \neg P(x) \end{align*}
It might help to think “not all...” is equivalent to “some... do not”. While “there isn’t one who...” is the same as “no one does...”.
Video / Answer.

Note 2.3.9.

Counterexamples to universal statements work because if \(\exists x \neg P(x)\) is true, then \(\neg \forall x P(x)\) is also true, that is, \(\forall x P(x)\) is false!

Example 2.3.10.

For each negation below, write the statement using quantifiers to confirm each is correct.
  1. The negation of “There exists a green horse” is “No horse is green.”
  2. The negation of “All people wear hats” is the statement “Some person doesn’t wear hats”.
  3. The negation of “Nobody loves math” is “Someone does love math”.
  4. Find the negation of “some drivers don’t obey the speed limit.”.
Video / Answer.

Example 2.3.11.

If the universe of discourse is all people at the university, and \(P(x)\) is the statement “\(x\) loves to drink coffee,” express each statement in plain English:
  1. \(\displaystyle \forall x P(x)\)
  2. \(\displaystyle \exists x P(x)\)
  3. \(\displaystyle \forall x \neg P(x)\)
Video / Answer.

Example 2.3.12.

Translate the statement into logical expressions using predicates, quantifiers, and logical connectives.
  1. All of your friends are perfect.
  2. Not everybody is your friend or someone is not perfect.
Video / Answer.

Exercises Exercises

1.

Determine the truth value of the each of these statements if the domain consists of all integers
  1. \(\displaystyle \forall n (n+1 > n)\)
  2. \(\displaystyle \exists n (n^3 = -1)\)
  3. \(\displaystyle \exists n (2n = 5n)\)
  4. \(\displaystyle \forall n (3n \le 4n)\)
  5. \(\displaystyle \forall x \forall y ((x^2 = y^2) \to (x = y))\)
Solution.
  1. True
  2. True
  3. True
  4. False
  5. False

2.

Determine the truth value of each of the following statements if the domain consists of all real numbers.
  1. \(\displaystyle \exists x(x^2 = 2)\)
  2. \(\displaystyle \exists x (x^2 = -1)\)
  3. \(\displaystyle \forall x (x^2 + 2 \ge 1)\)
  4. \(\displaystyle \forall x (2x > 2)\)
  5. \(\displaystyle \forall x (x+4)^2 = x^2 + 16\)
Solution.
  1. True
  2. False
  3. True
  4. False
  5. False

3.

Translate these statements into English where \(F(x)\) is “\(x\) is fast” and \(A(x)\) is “\(x\) is an athlete”, here the domain is the set of people.
  1. \(\displaystyle \forall x (A(x) \to F(x))\)
  2. \(\displaystyle \forall x (F(x) \land A(x))\)
  3. \(\displaystyle \exists x (F(x) \to A(x))\)
  4. \(\displaystyle \exists x (A(x) \land \neg F(x))\)
Solution.
Your answer shouldn’t have \(x\) in it anywhere! Regular people don’t say “For all x if x is fast, then...” Here some some ideas (your answer may very)
  1. All athletes are fast.
  2. Everyone is a fast athlete.
  3. Some fast person is an athlete.
  4. There is a slow athlete.

4.

Let \(C(x)\) denote the predicate “\(x\) is in the correct place”, let \(E(x)\) denote “\(x\) is in excellent condition”, and let \(T(x)\) denote “\(x\) is a tool” where the domain of each predicate is the set of objects in a garage. Translate each into plain English:
  1. \(\displaystyle \exists x \neg C(x)\)
  2. \(\displaystyle \exists x (T(x) \land \neg C(x))\)
  3. \(\displaystyle \forall x (T(x) \to (C(x) \land E(x)))\)
Solution.
  1. Something in the garage is out of place.
  2. Some tool is misplaced.
  3. All tools are in excellent condition and in the correct place.

5.

Simplify the statements below so that negations are only directly next to the predicates.
  1. \(\neg \exists x \forall y (\neg O(x) \vee E(y))\text{.}\)
  2. \(\neg \forall x \neg \forall y \neg(x \lt y \wedge \exists z (x \lt z \vee y \lt z))\text{.}\)
  3. There is a number \(n\) for which no other number is either less than or equal to \(n\text{.}\)
  4. It is false that for every number \(n\) there are two other numbers which \(n\) is between.
Solution.
  1. \begin{align*} \neg \exists x \forall y (\neg O(x) \vee E(y)) \amp \equiv \forall x \neg \forall y (\neg O(x) \lor E(y))\\ \amp \equiv \forall x \exists y \neg (\neg O(x) \lor E(y))\\ \amp \equiv \forall x \exists y \neg \neg O(x) \land \neg E(y)\\ \amp \equiv \forall x \exists y O(x) \land \neg E(y) \end{align*}
  2. Applying DeMorgan’s laws many, many times and noting that the opposite of \(x\lt a\) is \(x \ge a\text{:}\)
    \begin{align*} \amp\neg \forall x \neg \forall y \neg(x \lt y \wedge \exists z (x \lt z \vee y \lt z)) \\ \amp\equiv \neg \forall x \neg \forall y \neg(x \lt y \wedge \exists z (x \lt z \vee y \lt z)) \\ \amp \equiv \exists x \neg \neg \forall y \neg(x \lt y \wedge \exists z (x \lt z \vee y \lt z)) \\ \amp \equiv \exists x \forall y \neg(x \lt y \wedge \exists z (x \lt z \vee y \lt z)) \\ \amp \equiv \exists x \forall y \neg(x \lt y ) \lor \neg ( \exists z (x \lt z \vee y \lt z)) ) \\ \amp \equiv \exists x \forall y \neg(x \lt y ) \lor \forall z \neg (x \lt z \vee y \lt z)) ) \\ \amp \equiv \exists x \forall y \neg(x \lt y ) \lor \forall z \neg (x \lt z) \land \neg (y \lt z))) \\ \amp \equiv \exists x \forall y (x \ge y ) \lor \forall z (x \ge z) \land (y \ge z))) \end{align*}
  3. This statement can be written \(\exists n \neg \exists x (x \le n)\text{.}\) It can be simplified as \(\exists n \forall x \neg (x \le n)\text{,}\) and even further as \(\exists n \forall x (x \gt n)\)
  4. This statement can be written \(\neg \forall n \exists x \exists y (x \lt n \lt y)\)
    \begin{align*} \neg \forall n \exists x \exists y (x \lt n \lt y) \amp \equiv \exists n \neg \exists x \exists y (x \lt n \lt y) \\ \amp \equiv \exists n \forall x \neg \exists y (x \lt n \lt y) \\ \amp \equiv \exists n \forall x \forall y \neg (x \lt n \lt y) \end{align*}

6.

Consider the statement, “There is a building on the campus of some college in the United States in which every room is painted white.”
  1. Express the statement using quantifiers. Be sure to define your predicate function and specify the domain of each of the three variables.
  2. Express the negation of the above logical quantified statement so that no negation is to the left of a quantifier.
  3. Write the negation of the statement in plain English.
Solution.
Let \(c\) come from the universe of colleges in the US, \(b\) be from the universe of buildings on a chosen campus and \(r\) be the rooms in a chosen building.
  1. We have to first select a college, then find the building on that campus:
    \(\exists c \exists b \forall r (b \text{ on the campus of } c \text{ in which } r \text{ is painted white})\)
  2. Start with the negation on the left and apply DeMorgan’s laws
    \begin{align*} \amp \neg \exists c \exists b \forall r (b \text{ on the campus of } c \text{ in which } r \text{ is painted white})\\ \amp \equiv \forall c \forall b \exists r \neg(b \text{ on the campus of } c \text{ in which } r \text{ is painted white}) \end{align*}
  3. On every campus in the US, every building has at least one room that isn’t painted white.
<Prev^TopNext>