Skip to content
Textbook Guides

Solution Manual for Introduction to Mathematical Thinking: Algebra and Number Systems, 1st Edition

Solve textbook problems with ease using Solution Manual for Introduction to Mathematical Thinking: Algebra and Number Systems, 1st Edition, featuring detailed solutions and step-by-step guides.

Preview 16 of 450 pages

See the first 16 pages exactly as they appear in the document.

  1. Page 1
    Read page 1 as text

    Chapter 1 Solutions An Introduction to Mathematical Thinking: Algebra and Number Systems William J. Gilbert and Scott A. Vanstone, Prentice Hall, 2005 Solutions prepared by William J. Gilbert and Alejandro Morales Exercise 1-1: Determine which of the following sentences are statements. What are the truth values of those that are statements? 7 > 5 Solution: It is a statement and it is true. Exercise 1-2: Determine which of the following sentences are statements. What are the truth values of those that are statements? 5 > 7 Solution: It is a statement and its truth value is FALSE. Exercise 1-3: Determine which of the following sentences are statements. What are the truth values of those that are statements? Is 5 > 7? Solution: It is not a statement because it is a question. Exercise 1-4: Determine which of the following sentences are statements. What are the truth values of those that are statements? √ 2 is an integer. Solution: This is a statement. It is false as there is no integer whose square is 2 . Exercise 1-5: Determine which of the following sentences are statements. What are the truth values of those that are statements? 1.1

  2. Page 2
  3. Page 3
    Read page 3 as text

    Show that √ 2 is not an integer. Solution: It is not a statement because the sentence does not have a truth value, it is a command. Exercise 1-6: Determine which of the following sentences are statements. What are the truth values of those that are statements? If 5 is even then 6 = 7. Solution: It is a statement and its truth value is TRUE. Exercise 1-7: Write down the truth tables for each expression. NOT(NOT P ). Solution: P NOT P NOT(NOT P ) T F T F T F Exercise 1-8: Write down the truth tables for each expression. NOT( P OR Q ) Solution: P Q P OR Q NOT ( P OR Q ) T T T F T F T F F T T F F F F T Exercise 1-9: Write down the truth tables for each expression. P = ⇒ ( Q OR R ) Solution: P Q R Q OR R P = ⇒ ( Q OR R ) T T T T T T T F T T T F T T T T F F F F F T T T T F T F T T F F T T T F F F F T 1.2

  4. Page 4
    Read page 4 as text

    Exercise 1-10: Write down the truth tables for each expression. ( P AND Q ) = ⇒ R Solution: P Q R P AND Q ( P AND Q ) = ⇒ R T T T T T T T F T F T F T F T T F F F T F T T F T F T F F T F F T F T F F F F T Exercise 1-11: Write down the truth tables for each expression. ( P OR NOT Q ) = ⇒ R . Solution: P Q R NOT Q P OR (NOT Q ) ( P OR NOT Q ) = ⇒ R T T T F T T T T F F T F T F T T T T T F F T T F F T T F F T F T F F F T F F T T T T F F F T T F Exercise 1-12: Write down the truth tables for each expression. NOT P = ⇒ ( Q ⇐⇒ R ). Solution: P Q R Q ⇐⇒ R NOT P = ⇒ ( Q ⇐⇒ R ) T T T T T T T F F T T F T F T T F F T T F T T T T F T F F F F F T F F F F F T T 1.3

  5. Page 5
    Read page 5 as text

    Exercise 1-13: P UNLESS Q is defined as (NOT Q ) = ⇒ P . Show that this statement has the same truth table as P OR Q . Give an example in common English showing the equivalence of P UNLESS Q and P OR Q . Solution: Defining P UNLESS Q as (NOT Q ) = ⇒ P , then P Q NOT Q P UNLESS Q P OR Q T T F T T T F T T T F T F T T F F T F F Since the last two columns are the same the statement P UNLESS Q defined as (NOT Q ) = ⇒ P is equivalent to P OR Q . “I will go unless I forget” and “I will go or I forget”. Exercise 1-14: Write down the truth table for the exclusive or connective XOR, where the statement P XOR Q means ( P OR Q ) AND NOT ( P AND Q ). Show that this is equivalent to NOT( P ⇐⇒ Q ). Solution: P Q P OR Q P AND Q P XOR Q NOT( P ⇐⇒ Q ) T T T T F F T F T F T T F T T F T T F F F F F F Since the last two columns are the same, the statements are equivalent. Exercise 1-15: Write down the truth table for the not or connective NOR, where the statement P NOR Q means NOT( P OR Q ). Solution: Defining P NOR Q as NOT( P OR Q ), then the truth table for the N OR connective is P Q P OR Q P NOR Q T T T F T F T F F T T F F F F T 1.4

  6. Page 6
    Read page 6 as text

    Exercise 1-16: Write down the truth table for the not and connective NAND, where the state- ment P NAND Q means NOT( P AND Q ). Solution: P Q P AND Q P NAND Q T T T F T F F T F T F T F F F T Exercise 1-17: Write each statement using P , Q , and connectives. P whenever Q . Solution: Q = ⇒ P . Exercise 1-18: Write each statement using P , Q , and connectives. P is necessary for Q Solution: Q = ⇒ P . Exercise 1-19: Write each statement using P , Q , and connectives. P is sufficient for Q . Solution: P = ⇒ Q . Exercise 1-20: Write each statement using P , Q , and connectives. P only if Q Solution: P = ⇒ Q. Exercise 1-21: Write each statement using P , Q , and connectives. P is necessary and sufficient for Q . Solution: P ⇐⇒ Q . Another equivalent answer is Q ⇐⇒ P . Exercise 1-22: Show that the statements NOT ( P OR Q ) and (NOT P ) AND (NOT Q ) have the same truth tables and give an example of the equivalence of these statements in everyday language. Solution: 1.5

  7. Page 7
    Read page 7 as text

    P Q P OR Q NOT (P OR Q) T T T F T F T F F T T F F F F T P Q NOT P NOT Q (NOT P ) AND (NOT Q ) T T F F F T F F T F F T T F F F F T T T The final columns of each table are the same, so the two statements have the same truth tables. This equivalence can be illustrated in everyday language. Consider the state- ment “I do not want cabbage or broccoli”. This means that “I do not want cabbage” and “I do not want broccoli”. Exercise 1-23: Show that the statements P AND ( Q AND R ) and ( P AND Q ) AND R have the same truth tables. This is the associative law for AND. Solution: P Q R Q AND R P AND ( Q AND R ) T T T T T T T F F F T F T F F T F F F F F T T T F F T F F F F F T F F F F F F F P Q R P AND Q ( P AND Q ) AND R T T T T T T T F T F T F T F F T F F F F F T T F F F T F F F F F T F F F F F F F The final columns of each table are equal, so the two statements have the same truth tables. 1.6

  8. Page 8
    Read page 8 as text

    Exercise 1-24: Show that the statements P AND ( Q OR R ) and ( P AND Q ) OR ( P AND R ) have the same truth tables. This is a distributive law . Solution: P Q R Q OR R P AND ( Q OR R ) T T T T T T T F T T T F T T T T F F F F F T T T F F T F T F F F T T F F F F F F P Q R P AND Q P AND R ( P AND Q ) OR ( P AND R ) T T T T T T T T F T F T T F T F T T T F F F F F F T T F F F F T F F F F F F T F F F F F F F F F The final columns of each table are the same, so the two statements have the same truth tables. Exercise 1-25: Is ( P AND Q ) = ⇒ R equivalent to P = ⇒ ( Q = ⇒ R ) ? Give reasons. Solution 1: Suppose ( P AND Q ) = ⇒ R is false. Then P AND Q is true and R is false. Because both P and Q are true then Q = ⇒ R is false, and thus P = ⇒ ( Q = ⇒ R ) is also false. Now suppose that P = ⇒ ( Q = ⇒ R ) is false. Then P is true and ( Q = ⇒ R ) is false. This last statement implies that Q is true and R is false. Therefore P AND Q is true, and ( P AND Q ) = ⇒ R is false. We have shown that whenever one statement is false, then the other one is also false. It follows that the statements are equivalent. Solution 2: 1.7

  9. Page 9
    Read page 9 as text

    P Q R P AND Q ( P AND Q ) = ⇒ R T T T T T T T F T F T F T F T T F F F T F T T F T F T F F T F F T F T F F F F T P Q R Q = ⇒ R P = ⇒ ( Q = ⇒ R ) T T T T T T T F F F T F T T T T F F T T F T T T T F T F F T F F T T T F F F T T The final columns of each table are the same, so the two statements have the same truth tables, and the statements are equivalent. Exercise 1-26: Let P be the statement ‘It is snowing’ and let Q be the statement ‘It is freezing.’ Write each statement using P , Q , and connectives. It is snowing, then it is freezing Solution: P = ⇒ Q . Exercise 1-27: Let P be the statement ‘It is snowing’ and let Q be the statement ‘It is freezing.’ Write each statement using P , Q , and connectives. It is freezing but not snowing, Solution: Q AND (NOT P ). Exercise 1-28: Let P be the statement ‘It is snowing’ and let Q be the statement ‘It is freezing.’ Write each statement using P , Q , and connectives. When it is not freezing, it is not snowing. Solution: NOT Q = ⇒ NOT P . 1.8

  10. Page 10
    Read page 10 as text

    Exercise 1-29: Let P be the statement ‘I can walk,’ Q be the statement ‘I have broken my leg’ and R be the statement ‘I take the bus.’ Express each statement as an English sentence. Q = ⇒ NOT P . Solution: It can be “If I have broken my leg then I cannot walk”. Exercise 1-30: Let P be the statement ‘I can walk,’ Q be the statement ‘I have broken my leg’ and R be the statement ‘I take the bus.’ Express each statement as an English sentence. P ⇐⇒ NOT Q Solution: It can be “I can walk if and only if I have not broken my leg”. Exercise 1-31: Let P be the statement ‘I can walk’ Q be the statement ‘I have broken my leg’ and R be the statement ‘I take the bus.’ Express each statement as an English sentence. R = ⇒ ( Q OR NOT P ) Solution: It can be “If I take the bus then I have broken my leg or I cannot walk”. Exercise 1-32: Let P be the statement ‘I can walk,’ Q be the statement ‘I have broken my leg’ and R be the statement ‘I take the bus.’ Express each statement as an English sentence. R = ⇒ ( Q ⇐⇒ NOT P ) Solution: It can be “I take the bus only if I have broken my leg is equivalent to I cannot walk”. Exercise 1-33: Express each statement as a logical expression using quantifiers. State the universe of discourse. There is a smallest positive integer. Solution: If we assume that the universe of discourse is the set of integers, we can express the statement as ∃ x ∀ y, (0 < x ≤ y ) . 1.9

  11. Page 11
    Read page 11 as text

    Exercise 1-34: Express each statement as a logical expression using quantifiers. State the universe of discourse. There is no smallest positive real number. Solution: The universe of discourse is the set of all positive real numbers. The state- ment “there is no smallest positive real number” is equivalent to ∀ r ∃ x, ( x < r ) . Exercise 1-35: Express each statement as a logical expression using quantifiers. State the universe of discourse. Every integer is the product of two integers. Solution: If we assume that the universe of discourse is the set of integers, we can express the statement as ∀ x ∃ y ∃ z ( x = yz ) . Exercise 1-36: Express each statement as a logical expression using quantifiers. State the universe of discourse. Every pair of integers has a common divisor. Solution: The universe of discourse is the set of integers. The given statement is ∀ x ∀ y ∃ z, ( z divides x AND z divides y ) . 1.10

  12. Page 12
    Read page 12 as text

    Exercise 1-37: Express each statement as a logical expression using quantifiers. State the universe of discourse. There is a real number x such that, for every real number y , x 3 + x = y . Solution: If we assume that the universe of discourse is the set of real numbers, we can express the statement as ∃ x ∀ y, ( x 3 + x = y ) . Exercise 1-38: Express each statement as a logical expression using quantifiers. State the universe of discourse. For every real number y , there is a real number x such that x 3 + x = y . Solution: If we assume that the universe of discourse is the set of real numbers, we can express the statement as ∀ y ∃ x, ( x 3 + x = y ) . Exercise 1-39: Express each statement as a logical expression using quantifiers. State the universe of discourse. The equation x 2 − 2 y 2 = 3 has an integer solution. Solution: If we assume that the universe of discourse is the set of integers, we can express the statement as ∃ x ∃ y, ( x 2 − 2 y 2 = 3) . Exercise 1-40: Express the following quote due to Abraham Lincoln as a logical expression using quantifiers: “You can fool some of the people all of the time, and all of the people some of the time, but you can not fool all of the people all of the time.” Solution: Let x and t be variables. Let the universe of discourse of x to be the set of all people, and the universe of discourse of t to be the set of all times. And Let F ( x, t ) stand for fooling a person x at time t . The quote from Abraham Lincoln can be expressed as ∃ x ∀ t, F ( x, t ) AND ∀ x ∃ t, F ( x, t ) AND NOT ( ∀ x ∀ t, F ( x, t )) . 1.11

  13. Page 13
    Read page 13 as text

    Exercise 1-41: Negate each expression, and simplify your answer. ∀ x, ( P ( x ) OR Q ( x )) Solution: NOT [ ∀ x, ( P ( x ) OR Q ( x ))] ∃ x, NOT ( P ( x ) OR Q ( x )) ∃ x, (NOT P ( x ) AND NOT Q ( x )) . Exercise 1-42: Negate each expression, and simplify your answer. ∀ x, (( P ( x ) AND Q ( x )) = ⇒ R ( x )). Solution: Using Example 1.23. , NOT ( A = ⇒ B ) is equivalent to A AND NOT B , we have NOT ∀ x, [( P ( x ) AND Q ( x )) = ⇒ R ( x )] ∃ x, NOT [( P ( x ) AND Q ( x )) = ⇒ R ( x )] ∃ x, [( P ( x ) AND Q ( x )) AND NOT R ( x )] Exercise 1-43: Negate each expression, and simplify your answer. ∃ x, ( P ( x ) = ⇒ Q ( x )). Solution: Using Example 1.23. , NOT ( A = ⇒ B ) is equivalent to A AND NOT B , we have NOT ∃ x ( P ( x ) = ⇒ Q ( x )) ∀ x, NOT ( P ( x ) = ⇒ Q ( x )) ∀ x, ( P ( x ) AND NOT Q ( x )) . Exercise 1-44: Negate each expression, and simplify your answer. ∃ x ∀ y, ( P ( x ) AND Q ( y )). Solution: NOT ∃ x ∀ y, ( P ( x ) AND Q ( y ))] ∀ x NOT ∀ y, ( P ( x ) AND Q ( y )) ∀ x ∃ y, NOT ( P ( x ) AND Q ( y )) ∀ x ∃ y, (NOT P ( x )) OR (NOT Q ( y )) Exercise 1-45: If the universe of discourse is the real numbers, what does each statement mean in English? Are they true or false? ∀ x ∀ y, ( x ≥ y ) . Solution: Every real number is as large as any real number. This statement is false, if you let x = 1 and y = 2 then 1 < 2. 1.12

  14. Page 14
    Read page 14 as text

    Exercise 1-46: If the universe of discourse is the real numbers, what does each statement mean in English? Are they true or false? ∃ x ∃ y, ( x ≥ y ) . Solution: For some real number there is a real number that is less than or equal to it. This statement is always true because we can always take y = x/ 2 Exercise 1-47: If the universe of discourse is the real numbers, what does each statement mean in English? Are they true or false? ∃ y ∀ x, ( x ≥ y ). Solution: There is a smallest real number. This statement is false, if y is the smallest real number and you let x = y − 1 then y − 1 < y . Exercise 1-48: If the universe of discourse is the real numbers, what does each statement mean in English? Are they true or false? ∀ x ∃ y, ( x ≥ y ). Solution: For every real number there is a smaller or equal real number. This statement is true, if you let y = x/ 2 then x ≥ x/ 2. Exercise 1-49: If the universe of discourse is the real numbers, what does each statement mean in English? Are they true or false? ∀ x ∃ y, ( x 2 + y 2 = 1) . Solution: For all real numbers x there exists a real number y such that x 2 + y 2 = 1. This statement is false, if you let | x | > 1 then 1 − x 2 < 0 and for all real y , y 2 ≥ 0, so there is no real number y satisfying the equation. Exercise 1-50: If the universe of discourse is the real numbers, what does each statement mean in English? Are they true or false? ∃ y ∀ x, ( x 2 + y 2 = 1) . Solution: There exists a real number y such that for all real numbers x , x 2 + y 2 = 1 . This statement is false, for every y let | x | > 1 then x 2 > 1 and because y 2 > 0 then x 2 + y 2 > 1. 1.13

  15. Page 15
    Read page 15 as text

    Exercise 1-51: Determine whether each pair of statements is equivalent. Give reasons. ∃ x, ( P ( x ) OR Q ( x )). ( ∃ x, P ( x )) OR ( ∃ x, Q ( x )). Solution: These statements are equivalent. Suppose ∃ x, ( P ( x ) OR Q ( x )) is true. Hence ∃ x, , P ( x ) is true or Q ( x ) is true. We can assume that there exists an x such that P ( x ) is true, therefore for that particular x , ( ∃ x, P ( x )) OR ( ∃ x, Q ( x )) is true regardless of the value of ∃ x, Q ( x ). This also holds if ∃ x, Q ( x ) is true. Now suppose that ( ∃ x, P ( x )) OR ( ∃ x, Q ( x )) is true. Hence at least one of ( ∃ x P ( x )) or ( ∃ x Q ( x )) is true. Assume that there exists an x such that P ( x ) is true, therefore for that particular x , P ( x ) OR Q ( x ) is true regardless of the value of Q ( x ). So ∃ x, ( P ( x ) OR Q ( x )) is true. This also holds if ( ∃ x, Q ( x )) is true. We have shown that whenever one of the statements is true, then the other one is also true. Hence they are equivalent. Exercise 1-52: Determine whether each pair of statements is equivalent. Give reasons. ∃ x, ( P ( x ) AND Q ( x )). ( ∃ x P ( x )) AND ( ∃ x, Q ( x )). Solution: These statements are not equivalent. Assume the universe of discourse is the set of real numbers. Let P ( x ) be the statement x > 0 and Q ( x ) the statement x ≤ 0. Then ∃ x, ( P ( x ) AND Q ( x )) is false while ( ∃ x, P ( x )) AND ( ∃ x, Q ( x )) is true. (It may not be the same x in both parts of the second statement!) Exercise 1-53: Determine whether each pair of statements is equivalent. Give reasons. ∀ x, ( P ( x ) = ⇒ Q ( x )). ( ∀ x, P ( x )) = ⇒ ( ∀ x, Q ( x )). Solution: These statements are not always equivalent. We can give a particular exam- ple in which they do not have the same meaning. Let the universe of discourse be the set of real numbers. Let P ( x ) be the expression x < 0 and Q ( x ) be the expression x 2 < 0. Then for all real numbers x , if x < 0 then x 2 > 0 so P ( x ) = ⇒ Q ( x ) is false. However, ( ∀ x, P ( x )) is not true, and ( ∀ x, Q ( x )) is not true so ( ∀ x, P ( x )) = ⇒ ( ∀ x, Q ( x )) is true. Exercise 1-54: Determine whether each pair of statements is equivalent. Give reasons. ∀ x, ( P ( x ) OR Q ( y )). ( ∀ x, P ( x )) OR Q ( y ). Solution: These statements are equivalent. Because the variable x does not occur in Q ( y ), this statement does not depend on the quantifiers of x , it depends only on the particular choice of y . 1.14

  16. Page 16
    Read page 16 as text

    Therefore, the statement ∀ x, ( P ( x ) OR Q ( y )) is true when ∀ x, P ( x ) is true or when Q ( y ) is true. This is exactly the second statement. Exercise 1-55: Write the contrapositive, and the converse of each statement. If Tom goes to the party then I will go to the party. Solution: Contrapositive: If I don’t go to the party the Tom will not go to the party. Converse: If I go to the party then Tom will go to the party. Exercise 1-56: Write the contrapositive, and the converse of each statement. If I do my assignments then I get a good mark in the course. Solution: Contrapositive: If I do not get a good mark in the course then I do not do my assignments. Converse: If I get a good mark in the course then I do my assignments. Exercise 1-57: Write the contrapositive, and the converse of each statement. If x > 3 then x 2 > 9. Solution: Contrapositive: If x 2 ≤ 9 then x ≤ 3. Converse: If x 2 > 9 then x > 3. Exercise 1-58: Write the contrapositive, and the converse of each statement. If x < − 3 then x 2 > 9. Solution: Contrapositive: If x 2 ≤ 9 then x ≥ − 3. Converse: If x 2 > 9 then x < − 3. Exercise 1-59: Write the contrapositive, and the converse of each statement. If an integer is divisible by 2 then it is not prime. Solution: Contrapositive: If an integer is a prime then it is not divisible by 2. Converse: If an integer is not prime then it is divisible by 2. Exercise 1-60: Write the contrapositive, and the converse of each statement. If x ≥ 0 and y ≥ 0 then xy ≥ 0. Solution: Contrapositive: If xy < 0 then x < 0 or y < 0. Converse: If xy ≥ 0 then x ≥ 0 and y ≥ 0. Exercise 1-61: Write the contrapositive, and the converse of each statement. If x 2 + y 2 = 9 then − 3 ≤ x ≤ 3. Solution: 1.15

434 more pages in the full document

Unlock it once and it stays in your library, ready to chat with or turn into flashcards.

Unlock the full document

More Mathematics study materials

See all

Study this document with CramX

Once it is in your library, every tool can work from it.