The logical equivalences given in previous sections can be used to construct additional logical equivalences.
The reason for this is that a proposition in a compound proposition can be replaced by a compound proposition that is logically equivalent to it without changing the truth value of the original compound proposition.
Q. Show that ¬(p ∨ (¬p ∧ q)) and ¬p ∧ ¬q are logically equivalent by developing a series of logical equivalences.
¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬(¬p ∧ q) by the second De Morgan law
≡¬p ∧ [¬(¬p) ∨ ¬q] by the first De Morgan law
≡¬p ∧ (p ∨ ¬q) by the double negation law
≡ (¬p ∧ p) ∨ (¬p ∧ ¬q) by the second distributive law
≡ F ∨ (¬p ∧ ¬q) because ¬p ∧ p ≡ F
≡ (¬p ∧ ¬q) ∨ F by the commutative law for disjunction
≡¬p ∧ ¬q by the identity law for F
Show that (p ∧ q) → (p ∨ q) is a tautology.
To show that this statement is a tautology, we will use logical equivalences to demonstrate that it is logically equivalent to T
(p ∧ q) → (p ∨ q) ≡ ¬(p ∧ q) ∨ (p ∨ q)
≡ (¬p ∨¬q) ∨ (p ∨ q) by the first De Morgan law
≡ (¬p ∨ p) ∨ (¬q ∨ q) by the associative and commutative laws for disjunction
≡ T ∨ T by the commutative law for disjunction
≡ T by the domination law
A compound proposition is satisfiable if there is an assignment of truth values to its variables that makes it true.
When the compound proposition is false for all assignments of truth values to its variables, the compound proposition is unsatisfiable.
When we find a particular assignment of truth values that makes a compound proposition true, we have shown that it is satisfiable; such an assignment is called a solution of this particular satisfiability problem
Q. Determine whether each of the compound propositions (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p), (p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r), and (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p) ∧ (p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r) is satisfiable.
(p ∨¬q) ∧ (q ∨¬r) ∧ (r ∨¬p) is true when the three variable p, q, and r have the same truth values. Hence, it is satisfiable as there is at least one assignment of truth values for p, q, and r that makes it true.
(p ∨ q ∨ r) ∧ (¬p ∨¬q ∨¬r) is true when at least one of p, q, and r is true and at least one is false
For (p ∨¬q) ∧ (q ∨¬r) ∧ (r ∨¬p) ∧ (p ∨ q ∨ r) ∧ (¬p ∨¬q ∨¬r) to be true, (p ∨¬q) ∧ (q ∨¬r) ∧ (r ∨¬p) and (p ∨ q ∨ r) ∧ (¬p ∨¬q ∨¬r) must both be true.
For the first to be true, the three variables must have the same truth values, and for the second to be true, at least one of three variables must be true and at least one must be false.
However, these conditions are contradictory. From these observations we conclude that no assignment of truth values to p, q, and r makes (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨¬p) ∧ (p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r) true. Hence, it is unsatisfiable.
Statements involving variables, such as :
“x>3,” “x = y + 3,”, “x + y = z,”
computer x is under attack by an intruder,”
“computer x is functioning properly,”
The statement “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, “is greater than 3” — refers to a property that the subject of the statement can have.
We can denote the statement “x is greater than 3” by P(x), where P denotes the predicate “is greater than 3” and x is the variable.
The statement P(x) is also said to be the value of the propositional function P at x.
Q. Let P(x) denote the statement “x>3.” What are the truth values of P(4) and P(2)?
We obtain the statement P(4) by setting x = 4 in the statement “x > 3.” Hence, P(4), which is the statement “4 > 3,” is true. However, P(2), which is the statement “2 > 3,” is false.
Q. Let A(x) denote the statement “Computer x is under attack by an intruder.” Suppose that of the computers on campus, only CS2 and MATH1 are currently under attack by intruders. What are truth values of A(CS1), A(CS2), and A(MATH1)?
We obtain the statement A(CS1) by setting x = CS1 in the statement “Computer x is under attack by an intruder.”
Because CS1 is not on the list of computers currently under attack, we conclude that A(CS1) is false.
Similarly, because CS2 and MATH1 are on the list of computers under attack, we know that A(CS2) and A(MATH1) are true.
Q. Let Q(x, y) denote the statement “x = y + 3.” What are the truth values of the propositions Q(1, 2) and Q(3, 0)?
To obtain Q(1, 2), set x = 1 and y = 2 in the statement Q(x, y). Hence, Q(1, 2) is the statement “1 = 2 + 3,” which is false. The statement Q(3, 0) is the proposition “3 = 0 + 3,” which is true.
Quantification expresses the extent to which a predicate is true over a range of elements.
In English, the words all, some, many, none, and few are used in quantifications
There are two types of quantification here: universal quantification, which tells us that a predicate is true for every element under consideration, and existential quantification, which tells us that there is one or more element under consideration for which the predicate is true.
THE UNIVERSAL QUANTIFIER
Mathematical statements assert that a property is true for all values of a variable in a particular domain, called the domain of discourse OR the domain.
The universal quantification of P(x)for a particular domain is the proposition that asserts that P(x) is true for all values of x in this domain.
Note that the domain specifies the possible values of the variable x.
The universal quantification of P(x) is the statement “P(x) for all values of x in the domain.” The notation ∀xP(x) denotes the universal quantification of P(x). Here ∀ is called the universal quantifier. We read ∀xP(x) as “for all xP(x)” or “for every x P(x).”
THE EXISTENTIAL QUANTIFIER
The existential quantification of P(x) is the proposition “There exists an element x in the domain such that P(x).” We use the notation ∃xP(x) for the existential quantification of P(x). Here ∃ is called the existential quantifier.
The existential quantification ∃xP(x) is read as :
“There is an x such that P(x),”
There is at least one x such that P(x),” OR “For some xP(x).”
Quantifiers.
| Statement | When True? | When False? |
|---|---|---|
| ∀ x P(x) | P(x) is true for every x. | There is an x for which P(x) is false. |
| ∃ x P(x) | There is an x for which P(x) is true. | P(x) is false for every x |
Q. Let P(x) be the statement “x + 1 > x.” What is the truth value of the quantification ∀xP(x), where the domain consists of all real numbers?
Because P(x) is true for all real numbers x, the quantification ∀xP(x) is true.
Q. Let Q(x) be the statement “x < 2.” What is the truth value of the quantification ∀ x Q(x), where the domain consists of all real numbers?
Q(x) is not true for every real number x, because, for instance, Q(3) is false. That is, x = 3 is a counterexample for the statement ∀ x Q(x). Thus ∀ x Q(x) is false.
Q. What is the truth value of ∀xP(x), where P(x) is the statement “x2 < 10” and the domain consists of the positive integers not exceeding 4?
The statement ∀xP(x) is the same as the conjunction P(1) ∧ P(2) ∧ P(3) ∧ P(4), because the domain consists of the integers 1, 2, 3, and 4.
Because P(4), which is the statement “42 < 10,” is false, it follows that ∀xP(x) is false.
Q. Let P(x) denote the statement “x>3.” What is the truth value of the quantification ∃xP(x), where the domain consists of all real numbers?
Because “x>3” is sometimes true - for instance, when x = 4 the existential quantification of P(x), which is ∃xP(x), is true.
Q. Let Q(x) denote the statement “x = x + 1.” What is the truth value of the quantification ∃xQ(x), where the domain consists of all real numbers?
Because Q(x) is false for every real number x, the existential quantification of Q(x), which is ∃xQ(x), is false.
Precedence of Quantifiers
The quantifiers ∀ and ∃ have higher precedence than all logical operators from propositional calculus
For example : ∀xP(x) ∨ Q(x) is the disjunction of ∀xP(x) and Q(x). In other words, it means (∀xP(x)) ∨ Q(x) rather than ∀x(P(x) ∨ Q(x)).
De Morgan’s laws for quantifiers : Rules for negations for quantifiers
| Negation | Equivalent Statement |
|---|---|
| ¬∃xP(x) | ∀x¬P(x) |
| ¬∀xP(x) | ∃x¬P(x) |
Q. Every student in your class has taken a course in calculus. The negation of this statement is
Answer : It is not the case that every student in your class has taken a course in calculus.
Answer : There is a student in your class who has not taken a course in calculus.
Q. There is a student in this class who has taken a course in calculus. The negation of this statement is the proposition :
Answer : It is not the case that there is a student in this class who has taken a course in calculus
Answer : Every student in this class has not taken calculus
Q. What are the negations of the statements “There is an honest politician” and “All Americans eat cheeseburgers”?
Let H(x) denote “x is honest.” Then the statement “There is an honest politician” is represented by ∃xH(x), where the domain consists of all politicians.
The negation of this statement is ¬∃xH(x), which is equivalent to ∀x¬H(x). This negation can be expressed as “Every politician is dishonest.”
Q. What are the negations of the statements ∀x(x2 > x) and ∃x(x2 = x)is the statement?
negations of the statements ∀x(x2 > x) is ¬∀x(x2 > x) which is equivalent to ∃x¬(x2 > x).
This can be written as : ∃x(x2 ≤ x)
The negations of the statement ∃x(x2 = x)is the statement is the statement ¬∃x(x2 = x).
This is equal to ∀x¬(x2 = x) and ∀x(x2 ≠ x)
Nested Quantifiers and their Meaning
| Statement | When True? | When False? |
|---|---|---|
| ∀x∀yP(x, y) and ∀y∀xP(x, y) | P(x, y) is true for every pair x, y. | There is a pair x, y for which P(x, y) is false |
| ∀x∃yP(x, y) | For every x there is a y for which P(x, y) is true. | There is an x such that P(x, y) is false for every y. |
| ∃x∀yP(x, y) | There is an x for which P(x, y) is true for every y. | For every x there is a y for which P(x, y) is false. |
| ∃x∃yP(x, y) and ∃y∃xP(x, y) | There is a pair x, y for which P(x, y) is true. | P(x, y) is false for every pair x, y. |