Book of Proof

Home > Other > Book of Proof > Page 8
Book of Proof Page 8

by Richard Hammack


  semester your professor makes the following promise.

  You pass the class if and only if you get an “A” on the final or you get

  a “B” on the final.

  This promise has the form P ⇔ (Q ∨ R), so its truth values are tabulated in

  the above table. Imagine it turned out that you got an “A” on the exam

  but failed the course. Then surely your professor lied to you. In fact, P is

  false, Q is true and R is false. This scenario is reflected in the sixth line

  of the table, and indeed P ⇔ (Q ∨ R) is false (i.e., it is a lie).

  The moral of this example is that people can lie, but true mathematical

  statements never lie.

  We close this section with a word about the use of parentheses. The

  symbol ∼ is analogous to the minus sign in algebra.

  It negates the

  expression it precedes. Thus ∼ P ∨ Q means (∼ P) ∨ Q, not ∼ (P ∨ Q). In

  ∼ (P ∨ Q), the value of the entire expression P ∨ Q is negated.

  Exercises for Section 2.5

  Write a truth table for the logical statements in problems 1–9:

  1. P ∨ (Q ⇒ R)

  4. ∼ (P ∨ Q) ∨ (∼ P)

  7. (P∧ ∼ P) ⇒ Q

  2. (Q ∨ R) ⇔ (R ∧ Q)

  5. (P∧ ∼ P) ∨ Q

  8. P ∨ (Q∧ ∼ R)

  3. ∼ (P ⇒ Q)

  6. (P∧ ∼ P) ∧ Q

  9. ∼ (∼ P∨ ∼ Q)

  10. Suppose the statement ((P ∧ Q) ∨ R) ⇒ (R ∨ S) is false. Find the truth values of

  P, Q, R and S. (This can be done without a truth table.)

  11. Suppose P is false and that the statement (R ⇒ S) ⇔ (P ∧ Q) is true. Find the

  truth values of R and S. (This can be done without a truth table.)

  Logical Equivalence

  49

  2.6 Logical Equivalence

  In contemplating the truth table for P ⇔ Q, you probably noticed that

  P ⇔ Q is true exactly when P and Q are both true or both false. In other

  words, P ⇔ Q is true precisely when at least one of the statements P ∧ Q

  or ∼ P∧ ∼ Q is true. This may tempt us to say that P ⇔ Q means the same

  thing as (P ∧ Q) ∨ (∼ P∧ ∼ Q).

  To see if this is really so, we can write truth tables for P ⇔ Q and

  (P ∧ Q) ∨ (∼ P∧ ∼ Q). In doing this, it is more efficient to put these two

  statements into the same table, as follows. (This table has helper columns

  for the intermediate expressions ∼ P, ∼ Q, (P ∧ Q) and (∼ P∧ ∼ Q).)

  P

  Q

  ∼ P

  ∼ Q

  (P ∧ Q) (∼ P∧ ∼ Q)

  (P ∧ Q) ∨ (∼ P∧ ∼ Q)

  P ⇔ Q

  T

  T

  F

  F

  T

  F

  T

  T

  T

  F

  F

  T

  F

  F

  F

  F

  F

  T

  T

  F

  F

  F

  F

  F

  F

  F

  T

  T

  F

  T

  T

  T

  The table shows that P ⇔ Q and (P ∧ Q) ∨ (∼ P∧ ∼ Q) have the same truth

  value, no matter the values P and Q. It is as if P ⇔ Q and (P ∧Q)∨(∼ P∧ ∼ Q)

  are algebraic expressions that are equal no matter what is “plugged into”

  variables P and Q. We express this state of affairs by writing

  P ⇔ Q = (P ∧ Q) ∨ (∼ P∧ ∼ Q)

  and saying that P ⇔ Q and (P ∧ Q) ∨ (∼ P∧ ∼ Q) are logically equivalent.

  In general, two statements are logically equivalent if their truth

  values match up line-for-line in a truth table.

  Logical equivalence is important because it can give us different (and

  potentially useful) ways of looking at the same thing. As an example, the

  following table shows that P ⇒ Q is logically equivalent to (∼ Q) ⇒ (∼ P).

  P

  Q

  ∼ P

  ∼ Q

  (∼ Q) ⇒ (∼ P)

  P ⇒ Q

  T

  T

  F

  F

  T

  T

  T

  F

  F

  T

  F

  F

  F

  T

  T

  F

  T

  T

  F

  F

  T

  T

  T

  T

  The fact that P ⇒ Q = (∼ Q) ⇒ (∼ P) is useful because so many theorems

  have the form P ⇒ Q. As we will see in Chapter 5, proving such a theorem

  may be easier if we express it in the logically equivalent form (∼ Q) ⇒ (∼ P).

  50

  Logic

  There are two pairs of logically equivalent statements that come up

  again and again throughout this book and beyond. They are prevalent

  enough to be dignified by a special name: DeMorgan’s laws.

  Fact 2.1

  (DeMorgan’s Laws)

  1.

  ∼ (P ∧ Q) = (∼ P) ∨ (∼ Q)

  2.

  ∼ (P ∨ Q) = (∼ P) ∧ (∼ Q)

  The first of DeMorgan’s laws is verified by the following table. You are

  asked to verify the second in one of the exercises.

  P

  Q

  ∼ P

  ∼ Q

  P ∧ Q

  ∼ (P ∧ Q)

  (∼ P) ∨ (∼ Q)

  T

  T

  F

  F

  T

  F

  F

  T

  F

  F

  T

  F

  T

  T

  F

  T

  T

  F

  F

  T

  T

  F

  F

  T

  T

  F

  T

  T

  DeMorgan’s laws are actually very natural and intuitive. Consider the

  statement ∼ (P ∧ Q), which we can interpret as meaning that it is not the

  case that both P and Q are true. If it is not the case that both P and Q

  are true, then at least one of P or Q is false, in which case (∼ P) ∨ (∼ Q) is

  true. Thus ∼ (P ∧ Q) means the same thing as (∼ P) ∨ (∼ Q).

  DeMorgan’s laws can be very useful. Suppose we happen to know that

  some statement having form ∼ (P ∨ Q) is true. The second of DeMorgan’s

  laws tells us that (∼ Q) ∧ (∼ P) is also true, hence ∼ P and ∼ Q are both true

  as well. Being able to quickly obtain such additional pieces of information

  can be extremely useful.

  Here is a summary of some significant logical equivalences. Those that

  are not immediately obvious can be verified with a truth table.

  P ⇒ Q = (∼ Q) ⇒ (∼ P)

  Contrapositive law

  (2.1)

  ∼ (P ∧ Q) = ∼ P∨ ∼ Q o

  ∼ (P ∨ Q) = ∼ P∧ ∼ Q

  DeMorgan’s laws

  (2.2)

  P ∧ Q = Q ∧ P o

  P ∨ Q = Q ∨ P

  Commutative laws

  (2.3)

  P ∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R) o

  P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R)

  Distributive laws

  (2.4
)

  P ∧ (Q ∧ R) = (P ∧ Q) ∧ R o

  P ∨ (Q ∨ R) = (P ∨ Q) ∨ R

  Associative laws

  (2.5)

  Notice how the distributive law P ∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R) has the

  same structure as the distributive law p · (q + r) = p · q + p · r from algebra.

  Quantifiers

  51

  Concerning the associative laws, the fact that P ∧(Q ∧ R) = (P ∧Q)∧ R means

  that the position of the parentheses is irrelevant, and we can write this as

  P ∧ Q ∧ R without ambiguity. Similarly, we may drop the parentheses in

  an expression such as P ∨ (Q ∨ R).

  But parentheses are essential when there is a mix of ∧ and ∨, as in

  P ∨ (Q ∧ R). Indeed, P ∨ (Q ∧ R) and (P ∨ Q) ∧ R are not logically equivalent.

  (See Exercise 13 for Section 2.6, below.)

  Exercises for Section 2.6

  A. Use truth tables to show that the following statements are logically equivalent.

  1. P ∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R)

  5. ∼ (P ∨ Q ∨ R) = (∼ P) ∧ (∼ Q) ∧ (∼ R)

  2. P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R)

  6. ∼ (P ∧ Q ∧ R) = (∼ P) ∨ (∼ Q) ∨ (∼ R)

  3. P ⇒ Q = (∼ P) ∨ Q

  7. P ⇒ Q = (P∧ ∼ Q) ⇒ (Q∧ ∼ Q)

  4. ∼ (P ∨ Q) = (∼ P) ∧ (∼ Q)

  8. ∼ P ⇔ Q = (P ⇒∼ Q) ∧ (∼ Q ⇒ P)

  B. Decide whether or not the following pairs of statements are logically equivalent.

  9. P ∧ Q and ∼ (∼ P∨ ∼ Q)

  12. ∼ (P ⇒ Q) and P∧ ∼ Q

  10. (P ⇒ Q) ∨ R and ∼ ((P∧ ∼ Q)∧ ∼ R) 13. P ∨ (Q ∧ R) and (P ∨ Q) ∧ R

  11. (∼ P) ∧ (P ⇒ Q) and ∼ (Q ⇒ P)

  14. P ∧ (Q∨ ∼ Q) and (∼ P) ⇒ (Q∧ ∼ Q)

  2.7 Quantifiers

  Using symbols ∧, ∨, ∼, ⇒ and ⇔, we can deconstruct many English

  sentences into a symbolic form. As we have seen, this symbolic form can

  help us understand the logical structure of sentences and how different

  sentences may actually have the same meaning (as in logical equivalence).

  But these symbols alone are not powerful enough to capture the full

  meaning of every statement. To help overcome this defect, we introduce

  two new symbols that correspond to common mathematical phrases. The

  symbol “∀” stands for the phrase “For all” or “For every.” The symbol “∃”

  stands for the phrase “There exists a” or “There is a.” Thus the statement

  For every n ∈ Z, 2n is even,

  can be expressed in either of the following ways:

  ∀ n ∈ Z, 2n is even,

  ∀ n ∈ Z, E(2n).

  52

  Logic

  Likewise, a statement such as

  There exists a subset X of N for which |X | = 5.

  can be translated as

  ∃ X , (X ⊆ N) ∧ (|X | = 5)

  or

  ∃ X ⊆ N, |X | = 5

  or

  ∃ X ∈ P(N),|X | = 5.

  The symbols ∀ and ∃ are called quantifiers because they refer in some

  sense to the quantity (i.e., all or some) of the variable that follows them.

  Symbol ∀ is called the universal quantifier and ∃ is called the existen-

  tial quantifier. Statements which contain them are called quantified

  statements. A statement beginning with ∀ is called a universally quan-

  tified statement, and one beginning with ∃ is called an existentially

  quantified statement.

  Example 2.5

  The following English statements are paired with their

  translations into symbolic form.

  Every integer that is not odd is even.

  ∀ n ∈ Z, ∼ (n is odd ) ⇒ (n is even),

  or

  ∀ n ∈ Z, ∼ O(n) ⇒ E(n).

  There is an integer that is not even.

  ∃ n ∈ Z, ∼ E(n).

  For every real number x, there is a real number y for which y3 = x.

  ∀ x ∈ R, ∃ y ∈ R, y3 = x.

  Given any two rational numbers a and b, it follows that ab is rational.

  ∀ a, b ∈ Q, ab ∈ Q.

  Given a set S (such as, but not limited to, N, Z, Q etc.), a quantified

  statement of form ∀ x ∈ S, P(x) is understood to be true if P(x) is true

  for every x ∈ S. If there is at least one x ∈ S for which P(x) is false, then

  ∀ x ∈ S, P(x) is a false statement. Similarly, ∃ x ∈ S, P(x) is true provided that

  P(x) is true for at least one element x ∈ S; otherwise it is false. Thus each

  statement in Example 2.5 is true. Here are some examples of quantified

  statements that are false:

  Example 2.6

  The following false quantified statements are paired with

  their translations.

  Every integer is even.

  ∀ n ∈ Z, E(n).

  Quantifiers

  53

  There is an integer n for which n2 = 2.

  ∃ n ∈ Z, n2 = 2.

  For every real number x, there is a real number y for which y2 = x.

  ∀ x ∈ R, ∃ y ∈ R, y2 = x.

  p

  Given any two rational numbers a and b, it follows that

  ab is rational.

  p

  ∀ a, b ∈ Q, ab ∈ Q.

  Example 2.7

  When a statement contains two quantifiers you must be

  very alert to their order, for reversing the order can change the meaning.

  Consider the following statement from Example 2.5.

  ∀ x ∈ R, ∃ y ∈ R, y3 = x.

  This statement is true, for no matter what number x is there exists a

  p

  number y = 3 x for which y3 = x. Now reverse the order of the quantifiers

  to get the new statement

  ∃ y ∈ R, ∀ x ∈ R, y3 = x.

  This new statement says that there exists a particular number y with

  the property that y3 = x for every real number x. Since no number y can

  have this property, the statement is false. The two statements above have

  entirely different meanings.

  Quantified statements are often misused in casual conversation. Maybe

  you’ve heard someone say “All students do not pay full tuition.” when they

  mean “Not all students pay full tuition.” While the mistake is perhaps

  marginally forgivable in casual conversation, it must never be made in a

  mathematical context. Do not say “All integers are not even.” because that

  means there are no even integers. Instead, say “Not all integers are even.”

  Exercises for Section 2.7

  Write the following as English sentences. Say whether they are true or false.

  1. ∀ x ∈ R, x2 > 0

  6. ∃ n ∈ N,∀ X ∈ P(N),|X | < n

  2. ∀ x ∈ R,∃ n ∈ N, xn ≥ 0

  7. ∀ X ⊆ N,∃ n ∈ Z,|X | = n

  3. ∃ a ∈ R,∀ x ∈ R, ax = x

  8. ∀ n ∈ Z, ∃ X ⊆ N,|X | = n

  4. ∀ X ∈ P(N), X ⊆ R

  9. ∀ n ∈ Z,∃ m ∈ Z, m = n + 5

  5. ∀ n ∈ N,∃ X ∈ P(N),|X | < n

  10. ∃ m ∈ Z,∀ n ∈ Z, m = n + 5

  54

  Logic

  2.8 More on Conditional Statements

  It is time to address a very important point about conditional statements

  that contain variables. To motivate this, let’s return to the following

  example concerning integers x:

  (x is a multiple of 6) ⇒ (x is even).

  As noted earlier, since every multiple of 6 is even, this is a true statement


  no matter what integer x is. We could even underscore this fact by writing

  this true statement as

  ∀ x ∈ Z, (x is a multiple of 6) ⇒ (x is even).

  But now switch things around to get the different statement

  (x is even) ⇒ (x is a multiple of 6).

  This is true for some values of x such as −6, 12, 18, etc., but false for

  others (such as 2, 4, etc.). Thus we do not have a statement, but rather an

  open sentence. (Recall from Section 2.1 that an open sentence is a sentence

  whose truth value depends on the value of a certain variable or variables.)

  However, by putting a universal quantifier in front we get

  ∀ x ∈ Z, (x is even) ⇒ (x is a multiple of 6),

  which is definitely false, so this new expression is a statement, not an open

  sentence. In general, given any two open sentences P(x) and Q(x) about

  integers x, the expression ∀ x ∈ Z, P(x) ⇒ Q(x) is either true or false, so it is

  a statement, not an open sentence.

  Now we come to the very important point. In mathematics, whenever

  P(x) and Q(x) are open sentences concerning elements x in some set S

  (depending on context), an expression of form P(x) ⇒ Q(x) is understood

  to be the statement ∀ x ∈ S, P(x) ⇒ Q(x). In other words, if a conditional

  statement is not explicitly quantified then there is an implied universal

  quantifier in front of it. This is done because statements of the form

  ∀ x ∈ S, P(x) ⇒ Q(x) are so common in mathematics that we would get tired

  of putting the ∀ x ∈ S in front of them.

  Thus the following sentence is a true statement (as it is true for all x).

  If x is a multiple of 6, then x is even.

  Translating English to Symbolic Logic

  55

  Likewise, the next sentence is a false statement (as it is not true for all x).

  If x is even, then x is a multiple of 6.

  This leads to the following significant interpretation of a conditional

  statement, which is more general than (but consistent with) the interpre-

  tation from Section 2.3.

  Definition 2.1

  If P and Q are statements or open sentences, then

  “If P , then Q ,”

  is a statement. This statement is true if it’s impossible for P to be true

  while Q is false. It is false if there is at least one instance in which P is

  true but Q is false.

  Thus the following are true statements:

  If x ∈ R, then x2 + 1 > 0.

  If a function f is differentiable on R, then f is continuous on R.

  Likewise, the following are false statements:

  If p is a prime number, then p is odd.

  (2 is prime.)

  If f is a rational function, then f has an asymptote. (x2 is rational.)

  2.9 Translating English to Symbolic Logic

  In writing (and reading) proofs of theorems, we must always be alert to the

 

‹ Prev