Skip to main content

Section 1.4 Propositional Functions and Quantifiers

In mathematics we frequently wish to consider sentences (propositions) which involve variables. Since for different values of the variables (called propositional variables) we get different propositions with possibly different truth values, we call such sentences propositional functions or open sentences.

For each real number \(x\) consider the sentence \(x^2 + x = 1\text{.}\) Thus, \(x^2 + x = 1\) is a propositional function which has different truth values. The proposition is true for \(x = 1\) and \(x = -2\) and false for all other values of the propositional variable.

We can limit propositional functions by prefixing various expressions we call quantifiers, the most important of which are existential quantifiers and universal quantifiers. Phrases such as

  • “there exists a value \(x\)”
  • “there are \(x\text{,}\) \(y\text{,}\) and \(z\)”
  • “for some values of \(x\)”
  • “at least one value of \(x\)”

make use of existential quantifiers. On the other hand, phrases such as

  • “for each value of \(x\)”
  • “for every value of \(x\)”
  • “for all values of \(x\)”
  • “no value of \(x\)”

are called universal quantifiers.

For each real number \(x\) consider the propositional function \(p(x)\) that states \(x^2 + x = 1\text{.}\) We can alter that propositional function using the two types of quantifiers.

  1. There exists \(x\) such that \(p(x)\) is true.
  2. For all \(x\text{,}\) \(p(x)\) is true.

Clearly, (1) is true and (2) is false.

Notationally, we will let \(p(x)\) be a propositional function which states \(p\) is true for each \(x\text{.}\) Using the existential quantifier, we change \(p(x)\) into a proposition, namely “There exists \(x\) such that \(p(x)\text{.}\)” In mathematics, “there exists” is replaced by the symbol \(\exists\text{,}\) and we replace the statement above by \((\exists x)(p(x))\text{,}\) which is read “There exists \(x\) such that \(p(x)\) is true.”Similarly, we use the notation for the universal quantifier, \(\forall\text{,}\) and we have the proposition \((\forall x)(p(x))\text{,}\) which is read “For all \(x\text{,}\) \(p(x)\) is true.”

Consider all states in the USA and the propositional function \(p(x)\text{,}\) which states that \(x\) is a state which borders on the Pacific Ocean. The proposition \((\forall x)(p(x))\) is false, while the proposition \((\exists x)(p(x))\text{,}\) is true.

Remark 1.4.4. Caution!

Be careful when using the symbols \(\exists\) and \(\forall\text{.}\) While their use is quite common in logic, it is very easy to write confusing sentences. You will rarely see these symbols used in an algebra or calculus textbook. You may wish to avoid using these symbols for the time being.

General forms of qualified statements with their negations can be found in Table 1.4.5.

Statement Negation
Some \(a\) are \(b\text{.}\) No \(a\) is \(b\text{.}\)
Some \(a\) are not \(b\text{.}\) All \(a\) are \(b\text{.}\)
All \(a\) are \(b\text{.}\) Some \(a\) are not \(b\text{.}\)
No \(a\) is \(b\text{.}\) Some \(a\) are \(b\text{.}\)
Table 1.4.5. Truth table for negation

Exercises 1.4.1 Exercises

1.

Write each of the following statements in “if-then” form.

  1. Every figure that is a square is a rectangle.
  2. All integers are rational numbers.
  3. Figures with exactly \(3\) sides may be triangles.
  4. It rains only if it is cloudy.
2.

The open sentence “\(x^2 + 8 = 6x\text{,}\)” can be made either true or false by using different quantifiers. For example, “For some whole number \(x\text{,}\) \(x^2 + 8 = 6x\)” is true, since \(x = 4\) or \(x = 2\) make the equation true; however, “For all whole numbers \(x\text{.}\) \(x^2 + 8 = 6x\text{,}\)” is false since the equation is false for the whole number \(x = 0\) (and for countless other values of \(x\)).

Use an appropriate quantifier to make each of the following open sentences true, where \(x\) is a whole number. Then use quantifiers to make each statement false.

  1. \(\displaystyle x + 5 = 8\)
  2. \(\displaystyle x + x^2 = x(x + 1)\)
  3. \(\displaystyle x \cdot 1 = x \cdot 3\)
  4. \(\displaystyle x^2 + 1 = 0\)
3.

Negate the following statements.

  1. There exists at least one real number \(x\) such that \(x^2 = 9\text{.}\)
  2. There is no real number \(x\) that makes the sentence \(x^2 = -1\) true.
  3. Some students attend night school.
  4. No children are allowed in this building.
  5. There is some number that is both odd and even.
  6. All college students are math or engineering majors.
  7. For all real numbers \(x\text{,}\) if \(x\) is positive, then \(-x\) is negative.
  8. Some cars are red, and all students take math.
  9. There are some people who go to school in the morning and work in the afternoons.
  10. Not all numbers are rational and positive.
  11. All dogs have \(4\) legs.
  12. Not all rectangles are squares.
4.

Find the negation of each of the following.

  1. \(\displaystyle p \wedge (q \vee r)\)
  2. \(\displaystyle \negate p \wedge (q \rightarrow p)\)
  3. \(\displaystyle [p \wedge (q \rightarrow r)] \vee (\negate q \wedge p)\)
  4. \(x^2\) is even only if \(x\) is even.
  5. There is an integer \(x\) such that \(x/2\) is an integer, and for every integer \(y\text{,}\) \(x/(2y)\) is not an integer.
  6. For every postive integer \(x\text{,}\) either \(x\) is prime or \(x^2 + 1\) is prime.