X

### Constructing New Logical Equivalences

• 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 ﬁrst 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 ﬁrst 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

### Propositional Satisfiability

• A compound proposition is satisﬁable 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 unsatisﬁable.

• When we ﬁnd a particular assignment of truth values that makes a compound proposition true, we have shown that it is satisﬁable; such an assignment is called a solution of this particular satisﬁability 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 satisﬁable.

• (p ∨¬q) ∧ (q ∨¬r) ∧ (r ∨¬p) is true when the three variable p, q, and r have the same truth values. Hence, it is satisﬁable 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 ﬁrst 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 unsatisﬁable.

### Predicates and Quantiﬁers

• Statements involving variables, such as :

1. `“x>3,” “x = y + 3,”, “x + y = z,”`

2. `computer x is under attack by an intruder,”`

3. `“computer x is functioning properly,”`

• The statement “x is greater than 3” has two parts. The ﬁrst 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.

### Quantiﬁers

• Quantiﬁcation 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 quantiﬁcations

• There are two types of quantiﬁcation here: universal quantiﬁcation, which tells us that a predicate is true for every element under consideration, and existential quantiﬁcation, 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 quantiﬁcation 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 speciﬁes the possible values of the variable x.

• The universal quantiﬁcation of P(x) is the statement “P(x) for all values of x in the domain.” The notation ∀xP(x) denotes the universal quantiﬁcation of P(x). Here ∀ is called the universal quantiﬁer. We read ∀xP(x) as “for all xP(x)” or “for every x P(x).”

THE EXISTENTIAL QUANTIFIER

• The existential quantiﬁcation 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 quantiﬁcation of P(x). Here ∃ is called the existential quantiﬁer.

• The existential quantiﬁcation ∃xP(x) is read as :

1. “There is an x such that P(x),”

2. There is at least one x such that P(x),” OR “For some xP(x).”

Quantiﬁers.

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 quantiﬁcation ∀xP(x), where the domain consists of all real numbers?

• Because P(x) is true for all real numbers x, the quantiﬁcation ∀xP(x) is true.

Q. Let Q(x) be the statement “x < 2.” What is the truth value of the quantiﬁcation ∀ 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 quantiﬁcation ∃xP(x), where the domain consists of all real numbers?

• Because “x>3” is sometimes true - for instance, when x = 4 the existential quantiﬁcation 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 quantiﬁcation ∃xQ(x), where the domain consists of all real numbers?

• Because Q(x) is false for every real number x, the existential quantiﬁcation of Q(x), which is ∃xQ(x), is false.

Precedence of Quantiﬁers

• The quantiﬁers ∀ 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.
 Previous Next