Propositional logic is not powerful enough to represent all types of statements in mathematics, computer science and in natural language. For example, suppose that we know that \[\text{"Every computer connected to the university network is functioning properly"}\] No rules of propositional logic allow us to conclude the truth of the statement \[\text{"COMP1 is funtioning properly"}\] where \(\text{COMP1}\) is one of the computers connected to the university network.

Statements involving variables, such as \["x = y + 8"\] and \[\text{"Computer x is under attack by an intruder"}\] and \[\text{Computer x is functioning properly"}\] are often found in mathematical assetions, in computer programs, and in system specifications. These statements are neither true nor false when the values of the variables are not specified.

The statement \[\text{"x is greater than 3"}\] has two parts. The first part, the variable \(x\), is the subject of the statement. The second part, the predicate, \[\text{"is greater than 3"}\], refers to a property that the subject of the statement can have. We can denote the statement \[\text{"x is greater than 3"}\] by \(P(x)\), where \(P\) denontes the predicate \[\text{"is greater than 3"}\] and \(x\) is the variable. The statement \(P(x)\) is said to be the value of the propositional function \(P\) at \(x\), the statement \(P(x)\) becomes a proposition and has a truth value.

Example 2
Let \(A(x)\) denote the statement \(\text{"Computer x is under attack by an intruder"}\). Suppose that of the computers on campus, only \(\text{COMP1}\) and \(\text{COMP3}\) are currently under attack by intruders. What are the truth values of \(A(COMP1)\), \(A(COMP2)\) and \(A(COMP3)\)?
Solution
We obtain the statement \(A(COMP1)\) by setting \(x = COMP1\) in the statement \(\text{"Computer x is under attack by an intruder"}\). Because \(\text{COMP1}\) is on the list of computers under attack, we conclude that \(A(COMP1)\) is true. Similarly, because \(A(COMP2)\) is not on the list of computers under attack and \(A(COMP3)\) is on the list of computers under attack, we know that \(A(COMP2)\) is false and \(A(COMP3)\) is true.

Example 6
What is the truth value of \(\forall x (x^2 > x)\) if the domain consists of all real numbers? What is the truth value of this statement if the domain consists of all integers?
Solution
Because \((\frac{1}{2})^2 \not\geq \frac{1}{2}\) is false, the universal quantification \(\forall x (x^2 > x)\), where the domain consists of all real numbers, is false. Note that \(x^2 - x\) if and only if \(x^2 - x = x(x - 1) \geq 0\). Consequently, \(x^2 - x\) if and only if \(x \leq 0\) or \(x \geq 1\). It follows that \(\forall x (x^2 > x)\) is false if the domain consists of all real numbers (because the inequality is false for all real numbers \(x\) with \((0 < x < 1)\).
If the domain consists of integers, \(\forall x(x^2 \geq x)\) is true, because there are no integers \(x\) with \(0 < x < 1\).

Definition 2 The existential quantification of \(P(x)\) is the statement \[\text{"There exists an element \(x\) in the domain such that P(x)"}\] The notation \(\exists x P(x)\) denotes the existential quantification of \(P(x)\). Here \(\exists\) is called the existential quantifier.

Example 9
What do the statements \(\forall x < 0(x^2 > 0)\), \(\forall y \not= 0(y^3 \not= 0)\), and \(\exists z > 0(z^2 = 2)\) mean, where the domain in each case consists of the real numbers?
Solution
The statement \(\forall x < 0(x^2 > 0)\) states that for every real number \(x\) with \(x < 0\), \(x^2 > 0\). It states "The square of a negative real number is positive". This statement is the same as \(\forall x(x < 0 \implies x^2 > 0)\).
The statement \(\forall y \not= 0(y^3 \not= 0)\) states that for every real number \(y\) with \(y \not= 0\), we have \(y^3 \not= 0\). It states "The cube of every nonzero real number is nonzero". This statement is the same as \(\forall y(y \not= 0 \implies y^3 \not= 0)\).
The statement \(\exists z > 0(z^2 = 2)\) states that there exits a real number \(z\) with \(z > 0\) such that \(z^2 = 2\). It states "There is a positive square root of 2". This statement is equivalent to \(\exists z(z > 0 \land z^2 = 2)\).

Example 10
Show that \(\forall x(P(x) \land Q(x))\) and \(\forall x P(x) \land \forall x Q(x)\) are logically equivalent (where the same domain is used)
Solution
To show that these statements are logically equivalent, we must show that they always take the same truth value, no matter what the predicates \(P\) and \(Q\) are, no matter which domain of discourse is used. We can show that \(\forall x(P(x) \land Q(x))\) and \(\forall x P(x) \land \forall x Q(x)\) are logically equivalent by doing two things. First, we show that if \(\forall x(P(x) \land Q(x))\) is true, then \(\forall x P(x) \land \forall x Q(x)\) is true. Second we show that if \(\forall x P(x) \land \forall x Q(x)\) is true, then \(\forall x(P(x) \land Q(x))\) is true.
Suppose that \(\forall x(P(x) \land Q(x))\) is true. This means that if \(a\) is in the domain, then \(P(a) \land Q(a)\) is true. Hence, \(P(a)\) is true and \(Q(a)\) is true. Because is true. Hence, \(P(a)\) is true and \(Q(a)\) is true for every element in the domain, we can conclude that \(\forall x P(x)\) and \(\forall x Q(x)\) are both true. This means that \(\forall x P(x) \land \forall x Q(x)\) is true.
Next, suppose that \(\forall x P(x) \land \forall x Q(x)\) is true. Hence, if \(a\) is in the domain, then \(P(a)\) and \(Q(a)\) are true. It follows that for all \(a\), \(P(a) \land Q(a)\) is true. It follows that \(\forall x(P(x) \land Q(x))\) is true.

To show that \(\neg \forall x P(x)\) and \(\exists x \neg P(x)\) are logically equivalent no matter what the propositional function \(P(x)\) is and what the domain is, first note that \(\neg \forall x P(x)\) is true if and only if \(\forall x P(x)\) is false. Next, note that \(\forall x P(x)\) is false if and only if there is an element \(x\) in the domain for which \(P(x)\) is false. This holds if and only if there is an element \(x\) in the domain for which \(\neg P(x)\) is true. Finally, note that there is an element \(x\) in the domain for which \(\neg P(x)\) is true if and only if \(\neg \exists x P(x)\) is true. So we can conclude that \(\neg \forall x P(x)\) is true if and only if \(\exists x \neg P(x)\) is true. It follows that \(\neg \forall x P(x)\) and \(\exists x \neg P(x)\) are logically equivalent.

To show that \(\neg \exists x P(x)\) and \(\forall x \neg P(x)\) are logically equivalent no matter what \(P(x)\) is and what the domain is, first note that \(\neg \exists x P(x)\) is true if and only if \(\exists x P(x)\) is false. \(\exists x P(x)\) is true if and only if no \(x\) exists in the domain for which \(Q(x)\) is true. Next, note that no \(x\) exists in the domain for which \(Q(x)\) is true if and only if \(Q(x)\) is false for every \(x\) in the domain. Finally, note that \(Q(x)\) is false for every \(x\) in the domain if and only if \(\neg Q(x)\) is true for all \(x\) in the domain, which holds if and only if \(\forall x \neg P(x)\) is true. We see that \(\neg \exists x P(x)\) is true if and only if \(\forall x \neg P(x)\) is true. It follows that \(\neg \exists x P(x)\) and \(\forall x \neg P(x)\) are logically equivalent.

When the domain of a predicate \(P(x)\) consists of \(n\) elements, where \(n\) is a positive integer greater than one, the rules for negating quantified elements are exactly the same as De Morgan's laws. This is why these rules are called De Morgan's laws for qunatifiers. When the domain has \(n\) elements \(x_1, x_2, \ldots, x_n\), it follows that \(\neg \forall x P(x)\) is the same as \(\neg (P(x_1) \land P(x_2) \land \dots \land P(x_n))\), which is equivalent to \(\neg P(x_1) \lor \neg P(x_2) \lor \dots \lor \neg P(x_n)\) by De Morgan's laws, and this is the same as \(\exists x \neg P(x)\). Similarly \(\neg \exists x P(x)\) is the same as \(\neg (P(x_1) \lor P(x_2) \lor \dots \lor P(x_n))\), which by De Morgan laws is equivalent to \(\neg P(x_1) \land \neg P(x_2) \land \dots \land \neg P(x_n)\), and this is the same as \(\forall x \neg P(x)\).

Example 13
Show that \(\neg \forall x(P(x) \implies Q(x))\) and \(\exists x(P(x) \land Q(x))\) are logically equivalent.
Solution
By De Morgan's laws for universal quantifiers, we know that \(\neg \forall x(P(x) \implies Q(x))\) and \(\exists x \neg (P(x) \implies Q(x))\) are logically equivalent. We know that \((P(x) \implies Q(x))\) and \((P(x) \land \neg Q(x))\) are logically equivalent for every \(x\). It follows that \(\neg \forall x(P(x) \implies Q(x))\) and \(\exists x(P(x) \land Q(x))\) are logically equivalent.

Example 14
Express the statement \(\text{"Every student in this class has studied calculus"}\) using predicates and quantifiers.
Solution
First, we rewrite the statement so that we can clearly identify the appropriate quantifiers to use. Doing so, we obtain: \[\text{"For every student in this class, that student has studied calculus"}\] Next, we introduce a variable \(x\) so that our statement becomes \[\text{"For every student x in this class, x has studied calculus"}\] We introduce \(C(x)\), which is the statement \(\text{"x has studied calculus"}\). Consequently, if the domain for \(x\) consists of the students in the class, we can translate our statement as \(\forall x C(x)\).
If we change the domain to consist of all people, we will need to express our statement as \[\text{"For every person x, if the person x is a student in this class then x has studied calculus"}\] If \(S(x)\) represents the statement that person \(x\) is in this class, we can express the statement as \(\forall x(S(x) \implies C(x))\).
We may prefer to use two-variable quantifier \(Q(x, y)\) for the statement \(\text{"student x has studied subject y"}\). Then we can replace \(C(x)\) by \(Q(x, calculus)\) in both approaches to obtain \(\forall x Q(x, calculus)\) and \(\forall x(S(x) \implies Q(x, calculus))\).

Example 15
Consider these statements. The first two are called premises and the third is called the conclusion. The entire set is called an argument. \[\text{"All lions are fierce"}\] \[\text{"Some lions don't drink coffee"}\] \[\text{"Some fierce creatures do not drink coffee"}\] Let \(P(x)\), \(Q(x)\), and \(R(x)\) be the statements \(\text{"x is a lion"}\), \(\text{"x is fierce"}\), and \(\text{"x drinks coffee"}\) respectively. Assuming the domain consists of all creatures, express the statements in the argument using quantifiers and \(P(x)\), \(Q(x)\), and \(R(x)\).
Solution
We can express these statements as: \[\forall x(P(x) \implies Q(x))\] \[\exists x(P(x) \land \neg R(x))\] \[\exists x(Q(x) \land \neg R(x))\] Notice that the second statement cannot be written as \(\exists x(P(x) \implies \neg R(x))\). The reason is that \(P(x) \implies \neg R(x)\) is true whenever \(x\) is not a lion, so that \(\exists x(P(x) \implies \neg R(x))\) is true as long as there is at least one creature that is not a lion, even if every lion drinks coffee. Similarly, the third statement cannot be written as \[\exists x(Q(x) \implies \neg R(x))\]

Example 16
Translate into english the statement \(\forall x \forall y((x > 0) \land (y < 0) \implies (xy <0))\) where the domain for both variables consist of all real numbers.
Solution
This statement says that for every real number \(x\) and for every real number \(y\), if \(x > 0\) and \(y < 0\), then \(xy < 0\). This can be stated succinctly as "The product of a positive real number and a negative real number is always a negative real number".

Example 17
Let \(P(x, y)\) be the statement \(\text{"x + y = y + x"}\). What are the truth values of the quantifications \(\forall x \forall y P(x, y)\) and \(\forall y \forall x P(x, y)\) where the domain for all variables consists of all real numbers?
Solution
Because \(P(x, y)\) is true for all real numbers \(x\) and \(y\), the proposition \(\forall x \forall y P(x, y)\) is true. Note that the statement \(\forall y \forall x P(x, y)\) says \(\text{"For all real numbers y, for all real numbers x, x + y = y + x"}\). This has the same meaning as the statement \(\text{"For all real numbers x, for all real numbers y, x + y = y + x"}\). That is, \(\forall x \forall y P(x, y)\) and \(\forall y \forall x P(x, y)\) have the same meaning, and both are true.

Example 18
Let \(Q(x, y, z)\) be the statement \(\text{"x + y = z"}\). What are the truth values of the statements \(\forall x \forall y \exists z Q(x, y, z)\) and \(\exists z \forall x \forall y Q(x, y, z)\), where the domain of all variables consists of all real numbers?
Solution
The quantification \(\forall x \forall y \exists z Q(x, y, z)\), which is the statement \(\text{"For all real numbers x and for all real numbers y there is a real number z such that x + y = z"}\) is true.
The quantification \(\exists z \forall x \forall y Q(x, y, z)\), which is the statement \(\text{"There is a real number \(z\) such that for all real numbers \(x\) and for all real numbers \(y\) it is true that \(x + y = z\)"}\) is false, because there is no value of \(z\) that satisfies the equation \(x + y = z\) for all value of \(x\) and \(y\).

Example 19
Translate the statement "The sum of two positive integers is always positive" into a logical expression.
Solution
First, we rewrite it so that the implied quantifiers and a domain are shown: \(\text{"For every two integers, if these integers are both positive, then the sum of these integers is positive"}\). Next, we introduce the variables \(x\) and \(y\) to obtain \(\text{"For all positive numbers x and y, x + y is positive"}\). We can express this statement as \[\forall x \forall y ((x > 0) \land (y > 0) \implies (x + y > 0))\] where the domain for both variables consists of all integers. We could also translate this using the positive integers as the domain. Then the statement becomes \(\text{"For every two positive integers, the sum of these integers is positive"}\). We can express this as \[\forall x \forall y (x + y > 0)\] where the domain for both variables consists of all positive integers.

Example 20
Translate the statement "Every real number except zero has a multiplicative inverse" (A multiplicative inverse of a real number \(x\) is a real number \(y\) such that \(xy = 1\).
Solution
First, we rewrite this as \(\text{"For every real number x except zero, x has a multiplicative inverse"}\). We can rewrite this as \(\text{"For every real number x, if \(x \not= 0\), then there exists a real number y such that xy = 1"}\). This can be written as \[\forall x ((x \not= 0) \implies \exists y (xy = 1))\]

Example 21
Translate the statement \[\forall x(C(x) \lor \exists y(C(y) \land F(x, y)))\] into english, where \(C(x)\) is \(\text{"x has a computer"}\), \(F(x, y)\) is \(\text{"x and y are friends"}\), and the domain for both \(x\) and \(y\) consists of all students in your school.
Solution
The statement says that for every student \(x\) in your school, \(x\) has a computer or there is a student \(y\) such that \(y\) has a computer and \(x\) and \(y\) are friends. In other words, every student in your school has a computer or has a friend who has a computer.

Example 22
Translate the statement \[\exists x \forall y \forall z((F(x, y) \land F(x, z) \land (y \not= z)) \implies \neg F(y, z))\] into english, where \(F(a, b)\) means \(a\) and \(b\) are friends and the domain for \(x\), \(y\), and \(z\) consists of all students in your school.
Solution
The statement \((F(x, y) \land F(x, z) \land (y \not= z)) \implies \neg F(y, z)\) says that if student \(x\) and \(y\) are friends, and student \(x\) and \(z\) are friends, and futhermore if \(y\) and \(z\) are not the same student, then \(y\) and \(z\) are not friends. It follows that the original statement, which is triply quantified, says that there is a student \(x\) such that for all students \(y\) and students \(z\) other than \(y\), if \(x\) and \(y\) are friends and \(x\) and \(z\) are friends, then \(y\) and \(z\) are not friends. In other words, there is a student none of whose friends are also friends with each other.

Example 23
Express the statement "if a person is female and is a parent, then this person is someone's mother" as a logical expression involving predicates, quantifiers with a domain consisting of all people and logical connectives.
Solution
The statement can be expressed as \(\text{"For every person x, if peson x is female and person x is a parent, then there exists a person y such that the person x is the mother of person y"}\). We introduce the proposition functions \(F(x)\) to represent \(\text{"x is female"}\), \(P(x)\) to represent \(\text{"x is a parent"}\) and \(M(x, y)\) to represent \(\text{"x is mother of y"}\). The original statement can be represented as \[\forall x((F(x) \land P(x)) \implies \exists y M(x, y))\] We can move \(\exists y\) to the left so that it appears after \(\forall x\), because \(y\) does not appear in \(F(x) \land P(x)\). We obtain the logically equivalent expression \[\forall x \exists y((F(x) \land P(x)) \implies M(x, y))\]

Example 24
Express the statement "Everyone has exactly one best friend" as a logical expression involving predicates, quantifiers with a domain consisting of all people and logical connectives.
Solution
The statement can be expressed as \(\text{"For every person x, peson x has exactly one best friend"}\). To say that \(x\) has exactly one best friend means that there is a person \(y\) who is the best friend of \(x\), and furthermore, that for every person \(z\), if person \(z\) is not person \(y\), then \(z\) is not the best friend of \(x\). We introduce the predicate \(B(x, y)\) to be the statement \(\text{"y is the best friend of x"}\), the statement that \(x\) has exactly one best friend can be represented as \[\exists y(B(x, y) \land \forall z((z \not= y) \implies \neg B(x, y)))\] The original statement can be written as \[\forall x \exists y(B(x, y) \land \forall z((z \not= y) \implies \neg B(x, y)))\]

Example 25
Use quantifiers to express the statement "There is a woman who has taken a flight on every airline in the world".
Solution
Let \(P(w, f)\) be \(\text{"w has taken f"}\) and \(Q(f, a)\) be \(\text{"f is a flight on a"}\). We can express the statement as \[\exists w \forall a \exists f(P(w, f) \land Q(f, a))\] where the domains of discourse for \(w\), \(f\), and \(a\) consist of all women in the world, all airplane flights, and all airlines, respectively.
The statement could also be expressed as \[\exists w \forall a \exists f R(w, f, a)\] where \(R(w, f, a)\) is \(\text{"w has taken f on a"}\). Although this is more compact, it somewhat obscures the relationships among the variables. Consequently, the first solution is usually preferable.

Example 26
Express the negation of the statement \(\forall x \exists y(xy = 1)\) so that no negation precedes a quantifier.
Solution
By applying De Morgan's laws, we find that \(\neg \forall x \exists y(xy = 1)\) is equivalent to \(\exists x \neg \exists y(xy = 1)\), which is equivalent to \(\exists x \forall y \neg (xy = 1)\). Because \(\neg (xy = 1)\) can be expressed more simply as \(xy \not= 1\), so the statement can be expressed as \(\exists x \forall y (xy \not= 1)\).

Example 27
Use quantifiers to express the statement that "There does not exist a woman who has taken a flight on every airplane in the world".
Solution
This statement is the negation of the statement "There is a woman who has taken a flight on every airplane in the world" from Example 25. By Example 25, that statement is expressed as \(\exists w \forall a \exists f(P(w, f) \land Q(f, a))\). By applying De Morgan's laws, we find the statement "There does not exist a woman who has taken a flight on every airplane the world" is equivalent to each of this sequence of statements: \begin{align} \neg \exists w \forall a \exists f(P(w, f) \land Q(f, a)) & \equiv \forall w \neg \forall a \exists f(P(w, f) \land Q(f, a))\\ & \equiv \forall w \exists a \neg \exists f(P(w, f) \land Q(f, a))\\ & \equiv \forall w \exists a \forall f \neg (P(w, f) \land Q(f, a))\\ & \equiv \forall w \exists a \forall f(\neg P(w, f) \lor \neg Q(f, a)) \end{align}