Skip to content
Textbook Guides

Solution Manual for A Transition to Advanced Mathematics, 7th Edition

Solution Manual for A Transition to Advanced Mathematics, 7th Edition helps you understand textbook content with detailed solutions and explanations for each problem.

Preview 16 of 144 pages

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

  1. Page 1
    Read page 1 as text

    CONTENTS Chapter 1.1 Propositions and Connectives 1 1.2 Conditionals and Biconditionals 6 1.3 Quantifiers 13 1.4 Basic Proof Methods I 17 1.5 Basic Proof Methods II 22 1.6 Proofs Involving Quantifiers 26 1.7 Additional Examples of Proofs 29 Chapter 2.1 Basic Concepts of Set Theory 38 2.2 Set Operations 40 2.3 Extended Set Operations and Indexed Families of Sets 46 2.4 Mathematical Induction 49 2.5 Equivalent Forms of Induction 59 2.6 Principles of Counting 62 Chapter 3.1 Cartesian Products and Relations 67 3.2 Equivalence Relations 70 3.3 Partitions 75 3.4 Ordering Relations 78 3.5 Graphs 82 Chapter 4.1 Functions as Relations 85 4.2 Constructions of Functions 88 4.3 Functions That Are Onto; One-to-One Functions 92 4.4 One-to-One Correspondences and Inverse Functions 95 4.5 Images of Sets 199 4.6 Sequences 102 Chapter 5.1 Equivalent Sets; Finite Sets 105 5.2 Infinite Sets 108 5.3 Countable Sets 111 5.4 The Ordering of Cardinal Numbers 114 5.5 Comparability of Cardinal Numbers and the Axiom of Choice 117 Chapter 6.1 Algebraic Structures 119 6.2 Groups 122 6.3 Subgroups 126 6.4 Operation Preserving Maps 128 6.5 Rings and Fields 131 Chapter 7.1 Completeness of the Real Numbers 133 7.2 The Heine-Borel Theorem 136 7.3 The Bolzano-Weierstrass Theorem 139 7.4 The Bounded Monotone Sequence Theorem 140 7.5 Equivalents of Completeness 143

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

    1 Logic and Proofs 1.1 Propositions and Connectives 1. (a) true (b) false (c) true (d) false (e) false (f) false (g) false (h) false 2. (a) Not a proposition (b) False proposition (c) Not a proposition. It would be a proposition if a value for x had been assigned. (d) Not a proposition. It would be a proposition if values for x and y had been assigned. (e) False proposition (f) True proposition (g) False proposition (h) True proposition (i) False proposition (j) Not a proposition. It is neither true nor false. 3. (a) P ∼ P P ∧ ∼ P T F T F T F (b) P ∼ P P ∨ ∼ P T F T F T T (c) P Q ∼ Q P ∧ ∼ Q T T F F F T F F T F T T F F T F (d) P Q ∼ Q Q ∨ ∼ Q P ∧ ( Q ∨ ∼ Q ) T T F T T F T F T F T F T T T F F T T F (e) P Q ∼ Q P ∧ Q ( P ∧ Q ) ∨ ∼ Q T T F T T F T F F F T F T F T F F T F T (f) P Q P ∧ Q ∼ ( P ∧ Q ) T T T F F T F T T F F T F F F T 1

  4. Page 4
    Read page 4 as text

    1 LOGIC AND PROOFS 2 (g) P Q R ∼ Q P ∨ ∼ Q ( P ∨ ∼ Q ) ∧ R T T T F T T F T T F F F T F T T T T F F T T T T T T F F T F F T F F F F T F F T T F F F F T T F (h) P Q ∼ P ∼ Q ∼ P ∧ ∼ Q T T F F F F T T F F T F F T F F F T T T (i) P Q R Q ∨ R P ∧ ( Q ∨ R ) T T T T T F T T T F T F T T T F F T T F T T F T T F T F T F T F F F F F F F F F (j) P Q R P ∧ Q P ∧ R ( P ∧ Q ) ∨ ( P ∧ R ) T T T T T T F T T F F F T F T F T T F F T F F F T T F T F T F T F F F F T F F F F F F F F F F F 4. (a) false (b) true (c) true (d) true (e) false (f) false (g) false (h) false (i) true (j) true (k) false (1) false 5. (a) No solution. (b) P Q P ∨ Q Q ∨ P T T T T F T T T T F T T F F F F Since the third and fourth columns are the same, the propositions are equivalent.

  5. Page 5
    Read page 5 as text

    1 LOGIC AND PROOFS 3 (c) P Q P ∧ Q Q ∧ P T T T T F T F F T F F F F F F F Since the third and fourth columns are the same, the propositions are equivalent. (d) P Q R Q ∨ R P ∨ ( Q ∨ R ) P ∨ Q ( P ∨ Q ) ∨ R T T T T T T T F T T T T T T T F T T T T T F F T T T F T T T F T T T T F T F T T T T T F F F T T T F F F F F F F Since the fifth and seventh columns are the same, the propositions are equivalent. (e) P Q R Q ∧ R P ∧ ( Q ∧ R ) P ∧ Q ( P ∧ Q ) ∧ R T T T T T T T F T T T F F F T F T F F F F F F T F F F F T T F F F T F F T F F F F F T F F F F F F F F F F F F F Since the fifth and seventh columns are the same, the propositions are equivalent. (f) P Q R Q ∨ R P ∧ ( Q ∨ R ) P ∧ Q P ∧ R ( P ∧ Q ) ∨ ( P ∧ R ) T T T T T T T T F T T T F F F F T F T T T F T T F F T T F F F F T T F T T T F T F T F T F F F F T F F F F F F F F F F F F F F F Since the fifth and eighth columns are the same, the propositions are equivalent. (g) P Q R Q ∧ R P ∨ ( Q ∧ R ) P ∨ Q P ∨ R ( P ∨ Q ) ∧ ( P ∨ R ) T T T T T T T T F T T T T T T T T F T F T T T T F F T F F F T F T T F F T T T T F T F F F T F F T F F F T T T T F F F F F F F F

  6. Page 6
    Read page 6 as text

    1 LOGIC AND PROOFS 4 Since the fifth and eighth columns are the same, the propositions are equivalent. (h) No solution. (i) P Q P ∨ Q ∼ ( P ∨ Q ) ∼ P ∼ Q ∼ P ∧ ∼ Q T T T F F F F F T T F T F F T F T F F T F F F F T T T T Since the fourth and eighth columns are the same, the propositions are equivalent. 6. (a) equivalent (b) equivalent (c) equivalent (d) equivalent (e) equivalent (f) not equivalent (g) not equivalent (h) not equivalent 7. (a) ∼ P , true (b) P ∧ Q , true (c) P Q , true (d) P ∨ Q ∨ R , true 8. (a) Since P is equivalent to Q , P has the same truth table as Q . Therefore, Q has the same truth table as P , so Q is equivalent to P . (b) Since P is equivalent to Q , P and Q have the same truth table. Since Q is equivalent to R , Q and R have the same truth table. Thus, P and R have the same truth table so P is equivalent to R . (c) Since P is equivalent to Q , P and Q have the same truth table. That is, the truth table for P has value true on exactly the same lines that the truth table for Q has value true. Therefore the truth table for ∼ Q has value false on exactly the same lines that the truth table for ∼ P has the value false. Thus ∼ Q and ∼ P have the same truth table. 9. (a) ( P ∧ Q ) ∨ ( ∼ P ∧ ∼ Q ) is neither. P Q ∼ P ∼ Q P ∧ Q ∼ P ∧ ∼ Q ( P ∧ Q ) ∨ ( ∼ P ∧ ∼ Q ) T T F F T F T F T T F F F F T F F T F F F F F T T F T T (b) ∼ ( P ∧ ∼ P ) is a tautology. P ∼ P P ∧ ∼ P ∼ ( P ∧ ∼ P ) T F F T F T F T (c) ( P ∧ Q ) ∨ ( ∼ P ∨ ∼ Q ) is a tautology. P Q ∼ P ∼ Q P ∧ Q ∼ P ∨ ∼ Q ( P ∧ Q ) ∨ ( ∼ P ∨ ∼ Q ) T T F F T F T F T T F F T T T F F T F T T F F T T F T T (d) ( A ∧ B ) ∨ ( A ∧ ∼ B ) ∨ ( ∼ A ∧ B ) ∨ ( ∼ A ∧ ∼ B ) is a tautology.

  7. Page 7
    Read page 7 as text

    1 LOGIC AND PROOFS 5 ( A ∧ B ) ∨ ( A ∧ ∼ B ) ∨ A B ∼ A ∼ B A ∧ B A ∧ ∼ B ∼ A ∧ B ∼ A ∧ ∼ B ( ∼ A ∧ B ) ∨ ( ∼ A ∧ ∼ B ) T T F F T F F F T F T T F F F T F T T F F T F T F F T F F T T F F F T T (e) ( Q ∧ ∼ P ) ∧ ∼ ( P ∧ R ) is neither. P Q R ∼ P Q ∧ ∼ P P ∧ R ∼ ( P ∧ R ) ( Q ∧ ∼ P ) ∧ ∼ ( P ∧ R ) T T T F F T F F F T T T T F T T T F T F F T F F F F T T F F T F T T F F F F T F F T F T T F T T T F F F F F T F F F F T F F T F (f) P ∨ [( ∼ Q ∧ P ) ∧ ( R ∨ Q )] is neither. P Q R ∼ Q ∼ Q ∧ P R ∨ Q [( ∼ Q ∧ P ) ∧ ( R ∨ Q )] P ∨ [( ∼ Q ∧ P ) ∧ ( R ∨ Q )] T T T F F T F T F T T F F T F F T F T T T T T T F F T T F T F F T T F F F T F T F T F F F T F F T F F T T F F T F F F T F F F F 10. (a) contradiction (b) tautology (c) tautology (d) tautology 11. (a) x is not a positive integer. (b) Cleveland will lose the first game and the second game. Or, Cleveland will lose both games. (c) 5 < 3 (d) 641,371 is not composite. Or 641,371 is prime. (e) Roses are not red or violets are not blue. (f) T is bounded and T is not compact. (g) M is not odd or M is not one-to-one. (h) The function. f does not have a positive first derivative at x or does not have a positive second derivative at x . (i) The function g does not have a relative maximum at x = 2 (deleted comma) and does not have a relative maximum at x = 4, or else g does not have a relative minimum at x = 3. (j) z < s or z ≤ t . (k) R is not transitive or R is reflexive. (l) If the function g has a relative minimum at x = 2 or x = 4, then g does not have a relative minimum at x = 3. 12. (a) [ ∼ ( ∼ P )] ∨ [( ∼ Q ) ∧ ( ∼ S )] (b) [ Q ∧ ( ∼ S )] ∨ ∼ ( P ∧ [ Q ∧ ( ∼ S )] ∨ ∼ (( ∼ P ∧ Q ). (c) [[ P ∧ ( ∼ Q )] ∨ [( ∼ P ) ∧ ( ∼ R )]] ∨ [( ∼ P ) ∧ S ] (d) [( ∼ P ) ∨ ([ Q ∧ ( ∼ ( ∼ P ))] ∧ Q )] ∨ R .

  8. Page 8
    Read page 8 as text

    1 LOGIC AND PROOFS 6 13. (a) i. A B A © ∨ B T T F F T T T F T F F F ii. A B A ∨ B A ∧ B ∼ ( A ∧ B ) ( A ∨ B ) ∧ ∼ ( A ∧ B ) T T T T F F F T T F T T T F T F T T F F F F T F Since the final columns of the two tables are identical, the two propo- sitions have the same truth table, thus they are equivalent. (b) i. A B A NAND B A NOR B T T F F F T T F T F T F F F T T ii. A B A NAND B A NOR B ( A NAND B ) ∨ ( A NOR B ) T T F F F F T T F T T F T F T F F T T T Since the third and last columns are equal, the propositions are equiv- alent. iii. A B A NAND B A NOR B ( A NAND B ) ∧ ( A NOR B ) T T F F F F T T F F T F T F F F F T T T Since the fourth and last columns are equal, the propositions are equivalent. 1.2 Conditionals and Biconditionals 1. (a) Antecedent: squares have three. Consequent: triangles have four sides. (b) Antecedent: The moon is made of cheese. Consequent: 8 is an irrational number. (c) Antecedent: b divides 3. Consequent: b divides 9. (d) Antecedent: f is differentiable. Consequent: f is continuous. (e) Antecedent: a is convergent. Consequent: a is bounded. (f) Antecedent: f if integrable. Consequent: f is bounded. (g) Antecedent: 1 + 1 = 2. Consequent: 1 + 2 = 3.

  9. Page 9
    Read page 9 as text

    1 LOGIC AND PROOFS 7 (h) Antecedent: the fish bite. Consequent: the moon is full. (i) Antecedent: An athlete qualifies for the Olympic team. Consequent: The athlete has a time of 3 minutes, 48 seconds or less ( in the event). 2. (a) Converse: If triangles have four sides, then squares have three sides. Contrapositive: If triangles do not have four sides, then squares do not have three sides. (b) Converse: If 8 is irrational, then the moon is made of cheese. Contrapositive: If 8 is rational, then the moon is not made of cheese. (c) Converse: If b divides 9, then b divides 3. Contrapositive: If b does not divide 9, then b does not divide 3. (d) Converse: If f is continuous, then f is differentiable. Contrapositive: If f is not continuous, then f is not differentiable. (e) Converse: If a is bounded, then a is convergent. Contrapositive: If a is not bounded, then a is not convergent. (f) Converse: If f is bounded, then f is integrable. Contrapositive: If f is not bounded, then f is not integrable. (g) Converse: If 1 + 2 = 3, then 1 + 1 = 2. Contrapositive: If 1 + 1  = 2, then 1 + 2  = 3. (h) Converse: If the moon is full, then fish will bite. Contrapositive: If the moon is not full, then fish will not bite. (i) Converse: A time of 3 minutes, 48 seconds or less is sufficient to qualify for the Olympic team. Contrapositive: If an athlete records a time that is not 3 minutes and 48 seconds or less, then that athlete does not qualify for the Olympic team. 3. (a) Q may be either true or false. (b) Q must be true. (c) Q must be false. (d) Q must be false. (e) Q must be false. 4. (a) Antecedent: A ( x ) is an open sentence with variable x . Consequent: ∼ ( ∀ x ) A ( x ) is equivalent to ( ∃ x ) ∼ A ( x ). (b) Antecedent: Every even natural number greater than 2 is the sum of two primes. Consequent: Every odd natural number greater than 5 is the sum of three primes. (c) Antecedent: A is a set with n elements. Consequent: P ( A ) is a set with 2 n elements. (d) Antecedent: S is a subset of N such that 1 ∈ S and, for all n ∈ N , if n ∈ S , then n + 1 ∈ S . Consequent: S = N . (e) Antecedent: A is a finite set with m elements and B is a finite set with n elements. Consequent: A × B = mn .

  10. Page 10
    Read page 10 as text

    1 LOGIC AND PROOFS 8 (f) Antecedent: R is a partial order for A and B ⊆ A . Consequent: If sup( B ) exists, it is unique. (g) Antecedent: A , B , C , and D are sets, f is a function from A to B , g is a function from B to C , and h is a function from C to D . Consequent: ( h ◦ g ) ◦ f = h ◦ ( g ◦ f ). (h) Antecedent: A and B are disjoint finite sets. Consequent: A ∪ B is finite and A ∪ B = A + B . 5. (a) true (b) false (c) true (d) true (e) true (f) true (g) true (h) false 6. (a) true (b) true (c) true (d) true (e) false (f) true (g) false (The symbol for helium is He.) (h) true (i) false (j) true (k) false 7. (a) P Q Q ∧ P P ⇒ ( Q ∧ P ) T T T T F T F T T F F F F F F T (b) P Q ∼ P ∼ P ⇒ Q Q ⇔ P ( ∼ P ⇒ Q ) ∨ ( Q ⇔ P ) T T F T T T F T T T F T T F F T F T F F T F T T (c) P Q ∼ Q Q ⇔ P ∼ Q ⇒ ( Q ⇔ P ) T T F T T F T F F T T F T F F F F T T T (d) P Q P ∨ Q P ∧ Q ( P ∨ Q ) ⇒ ( P ∧ Q ) T T T T T F T T F F T F T F F F F F F T (e) P Q R P ∧ Q Q ∧ R P ∨ R ( P ∧ Q ) ∨ ( Q ∧ R ) ( P ∧ Q ) ∨ ( Q ∧ R ) ⇒ P ∨ R T T T T T T T T F T T F T T T T T F T F F T F T F F T F F T F T T T F T F T T T F T F F F F F T T F F F F T F T F F F F F F F T

  11. Page 11
    Read page 11 as text

    1 LOGIC AND PROOFS 9 (f) P Q R S Q ⇒ S Q ⇒ R P ∨ Q S ∨ R ( Q ⇒ S ) ∧ ( Q ⇒ R ) T T T T T T T T T F T T T T T T T T T F T T T T T T T F F T T T T F T T T T F T T F T T F F T F T T F T T F T F F T T T T T T F F F T T T F T T T T T F F T T T F F T T F F T T T F T F T F T T T T T F F T F T T F T T T T F F F F T F F F T F F F F T F F T F F F T T T F T F F F F T T F F T P Q R S ( P ∨ Q ) ⇒ ( S ∨ R ) [( Q ⇒ S ) ∧ ( Q ⇒ R )] ⇒ [( P ∨ Q ) ⇒ ( S ∨ R )] T T T T T T F T T T T T T F T T T T F F T T T T T T F T T T F T F T T T T F F T T T F F F T T T T T T F T T F T T F T T T F T F T T F F T F T T T T F F F T F T F F F T T F F F F F F F F F T T 8. (a) P Q ∼ P P ⇒ Q ( ∼ P ) ∨ Q T T F T T F T T T T T F F F F F F T T T Since the fourth and fifth columns are the same, the propositions P ⇒ Q and ( ∼ P ) ∨ Q are equivalent. (b) P Q P ⇒ Q Q ⇒ P P ⇔ Q ( P ⇒ Q ) ∧ ( Q ⇒ P ) T T T T T T F T T F F F T F F T F F F F T T T T Since the fifth and sixth columns are the same, the propositions P ⇔ Q and ( P ⇒ Q ) ∧ ( Q ⇒ P ) are equivalent. (c) P Q ∼ Q P ⇒ Q ∼ ( P ⇒ Q ) P ∧ ∼ Q T T F T F F F T F T F F T F T F T T F F T T F F Since the fifth and sixth columns are the same, the propositions ∼ ( P ⇒ Q ) and P ∧ ∼ Q are equivalent.

  12. Page 12
    Read page 12 as text

    1 LOGIC AND PROOFS 10 (d) P Q ∼ P ∼ Q P ∧ Q ∼ ( P ∧ Q ) P ⇒∼ Q P ⇒∼ Q T T F F T F F F F T T F F T T T T F F T F T T T F F T T F T T T Since the sixth, seventh and eighth columns are the same, all three propo- sitions are equivalent. (e) P Q R Q ⇒ R P ⇒ ( Q ⇒ R ) P ∧ Q ( P ∧ Q ) ⇒ R T T T T T T T F T T T T F T T F T T T F T F F T T T F T T T F F F T F F T F F T F T T F F T T F T F F F T T F T Since the fifth and seventh columns are the same, the propositions are equivalent. (f) P Q R Q ∧ R P ⇒ ( Q ∧ R ) P ⇒ Q P ⇒ R ( P ⇒ Q ) ∧ ( P ⇒ R ) T T T T T T T T F T T T T T T T T F T F F F T F F F T F T T T T T T F F F T F F F T F F T T T T T F F F F F F F F F F F T T T T Since the fifth and eighth columns are the same, the propositions are equivalent. (g) P Q R P ∨ Q P ∨ Q ) ⇒ R P ⇒ R Q ⇒ R ( P ⇒ R ) ∧ ( Q ⇒ R ) T T T T T T T T F T T T T T T T T F T T T T T T F F T F T T T T T T F T F F F F F T F T F T F F T F F T F F T F F F F F T T T T Since the fifth and seventh columns are the same, the propositions are equivalent. 9. (a) yes (b) no (c) yes (d) yes (e) no (f) no 10. (a) [( f has a relative minimum at x 0 ) ∧ ( f is differentiable at x 0 )] ⇒ ( f ′ ( x 0 ) = 0) (b) ( n is prime) ⇒ [( n = 2) ∨ ( n is odd)] (c) ( x is irrational) ⇒ [( x is real) ∧ ∼ ( x is rational)] (d) [( x = 1) ∨ ( x = − 1)] ⇒ ( | x | = 1) (e) ( x 0 is a critical point for f ) ⇔ [( f ′ ( x 0 ) = 0) ∨ ( f ′ ( x 0 ) does not exist)] (f) ( S is compact) ⇔ [( S is closed) ∧ ( S is bounded)] (g) (B is invertible) ⇔ (det B  =0)

  13. Page 13
    Read page 13 as text

    1 LOGIC AND PROOFS 11 (h) (6 ≥ n − 3) ⇒ ( n > 4) ∨ ( n > 10) (i) ( x is Cauchy) ⇒ ( x is convergent) (j) (lim x → x 0 f ( x ) = f ( x 0 )) ⇒ ( f is continuous at x 0 ) (k) [( f is differentiable at x 0 ) ∧ ( f is strictly increasing at x 0 )] ⇒ ( f ′ ( x 0 )) 11. (a) Let S be “I go to the store” and R be “It rains.” The preferred translation: is ∼ S ⇒ R (or, equivalently, ∼ R ⇒ S ). This could be read as “If it doesn’t rain, then I go to the store.” The speaker might mean “I go to the store if and only if it doesn’t rain ( S ⇒∼ R ) or possibly “If it rains, then I don’t go to the store” ( R ⇒∼ S ). (b) There are three nonequivalent ways to translate the sentence, using the symbols D : “The Dolphins make the playoffs” and B : “The Bears win all the rest of their games.” The first translation is preferred, but the speaker may have intended any of the three. ∼ B ⇒∼ D or, equivalently, D ⇒ B ∼ D ⇒∼ B or, equivalently, B ⇒ D ∼ B ⇔∼ D or, equivalently, B ⇔ D (c) Let G be “You can go to the game” and H be “You do your homework first.” It is most likely that a student and parent both interpret this statement as a biconditional, G ⇔ H . (d) Let W be “You win the lottery” and T be “You buy a ticket.” Of the three common interpretations for the word “unless,” only the form ∼ T ⇒∼ W (or, equivalently, W ⇒ T ) makes sense here. 12. (a) P Q R P ∨ Q ( P ∨ Q ) ⇒ R ∼ P ∧ ∼ Q ∼ R ⇒ ( ∼ P ∧ ∼ Q ) T T T T T F T F T T T T F T T F T T T F T F F T F T T T T T F T F F F F T F T F F F T F F T F F F F F F F T T T Since the fifth and seventh columns are the same, ( P ∨ Q ) ⇒ R and ∼ R ⇒ ( ∼ P ∧ ∼ Q ) are equivalent. (b) P Q R P ∧ Q ( P ∧ Q ) ⇒ R ∼ Q ∼ R P ∧ ∼ R ( P ∧ ∼ R ) ⇒∼ Q T T T T T F F F T F T T F T F F F T T F T F T T F F T F F T F T T F F T T T F T F F T T F F T F F T F T F T T F F F T T T T T F F F F T T T F T Since the fifth and ninth columns are the same, the propositions ( P ∧ Q ) ⇒ R and ( P ∧ ∼ R ) ⇒∼ Q are equivalent.

  14. Page 14
    Read page 14 as text

    1 LOGIC AND PROOFS 12 (c) P Q R Q ∧ R P ⇒ ( Q ∧ R ) ∼ Q ∨ ∼ R ( ∼ Q ∨ ∼ R ) ⇒∼ P T T T T T F T F T T T T F T T F T F F T F F F T F T T T T T F F F T F F T F F T T T T F F F F T F F F F F T T T Since the fifth and seventh columns are the same, the propositions P ⇒ ( Q ∧ R ) and ( ∼ Q ∨ ∼ R ) ⇒∼ P are equivalent. (d) P Q R Q ∨ R P ⇒ ( Q ∨ R ) P ∧ ∼ R ( P ∧ ∼ R ) ⇒ Q T T T T T F T F T T T T F T T F T T T F T F F T T T F T T T F T T T T F T F T T F T T F F F F T F F F F F T F T Since the fifth and seventh columns are the same, the propositions P ⇒ ( Q ∨ R ) and ( P ∧ ∼ R ) ⇒ Q are equivalent. (e) P Q R P ⇒ Q ( P ⇒ Q ) ⇒ R P ∧ ∼ Q ( P ∧ ∼ Q ) ∨ R T T T T T F T F T T T T F T T F T F T T T F F T T T F T T T F T F F F F T F T F F F T F F F T T T F F F T F F F Since the fifth and seventh columns are the same, the propositions ( P ⇒ Q ) ⇒ R and ( P ∧ ∼ Q ) ∨ R are equivalent. (f) P Q P ⇔ Q ∼ P ∨ Q ∼ Q ∨ P ( ∼ P ∨ Q ) ∧ ( ∼ Q ∨ P ) T T T T T T F T F T F F T F F F T F F F T T T T Since the third and sixth columns are the same, the propositions P ⇔ Q and ( ∼ P ∨ Q ) ∧ ( ∼ Q ∨ P ) are equivalent. 13. (a) If 6 is an even integer, then 7 is an odd integer. (b) If 6 is an odd integer, then 7 is an odd integer. (c) This is not possible. (d) If 6 is an even integer, then 7 is an even integer. (Any true conditional statement will work here.) 14. (a) If 7 is an odd integer, then 6 is an odd integer. (b) This is not possible.

  15. Page 15
    Read page 15 as text

    1 LOGIC AND PROOFS 13 (c) This is not possible. (d) If 7 is an odd integer, then 6 is an odd integer. (Any false conditional statement will work here.) 15. (a) Converse: If f ′ ( x 0 ) = 0, then f has a relative minimum at x 0 and is differentiable at x 0 . False: f ( x ) = x 3 has first derivative 0 but no minimum at x 0 = 0. Contrapositive: If f ′ ( x 0 )  = 0, then f either has no relative minimum at x 0 or is not differentiable at x 0 . True. (b) Converse: If n = 2 or n is odd, then n is prime. False: 9 is odd but not prime. Contrapositive: If n is even and not equal to 2, then n is not prime. True. (c) Converse: If x is irrational, then x is real and not rational. True Contrapositive: If x is not irrational, then x is not real or x is rational. True (d) Converse: If | x | = 1, then x = 1 or x = − 1. True. Contrapositive: If | x |  = 1, then x  = 1 and x  = − 1. True. 16. (a) tautology (b) tautology (c) contradiction (d) neither (e) tautology (f) neither (g) contradiction (h) tautology (i) contradiction (j) neither (k) tautology (l) neither 17. (a) P Q P ⇒ Q ∼ P ∼ Q ∼ P ⇒∼ Q T T T F F T F T T T F F T F F F T T F F T T T T Comparison of the third and sixth columns of the truth table shows that P ⇒ Q and ∼ P ⇒∼ Q are not equivalent. (b) We see from the truth table in part (a) that both propositions P ⇒ Q and ∼ P ⇒∼ Q are true only when P and Q have the same truth value. (c) The converse of P ⇒ Q is Q ⇒ P . The contrapositive of the inverse of P ⇒ Q is ∼∼ Q ⇒∼∼ P , so the converse and the contrapositive of the inverse are equivalent. The inverse of the contrapositive of P ⇒ Q is also ∼∼ Q ⇒∼∼ P , so it too is equivalent to the converse. 1.3 Quantifiers 1. (a) ∼ ( ∀ x )( x is precious ⇒ x is beautiful) or ( ∃ x )( x is precious and x is not beautiful) (b) ( ∀ x )( x is precious ⇒ x is not beautiful) (c) ( ∃ x )( x is isosceles ∧ x is a right triangle) (d) ( ∀ x )( x is a right triangle ⇒ x is not isosceles) or ∼ ( ∃ x )( x is a right triangle ∧ x is isosceles) (e) ( ∀ x )( x is honest) ∨ ∼ ( ∃ x )( x is honest) (f) ( ∃ x )( x is honest) ∧ ( ∃ x )( x is not honest) (g) ( ∀ x )( x  = 0 ⇒ ( x > 0 ∨ x < 0)) (h) ( ∀ x )( x is an integer ⇒ ( x > − 4 ∨ x < 6)) or ( ∀ x ∈ Z )( x > − 4 ∨ x < 6)

  16. Page 16
    Read page 16 as text

    1 LOGIC AND PROOFS 14 (i) ( ∀ x )( ∃ y )( x > y ) (j) ( ∀ x )( ∃ y )( x < y ) (k) ( ∀ x )( ∀ y )[( x is an integer ∧ y is an integer ∧ y > x ) ⇒ ( ∃ z )( y > z > x )] or ( ∀ x ∈ Z )( ∀ y ∈ Z )[ y > x ⇒ ( ∃ z )( y > z > x )] (l) ( ∃ x )( x is a positive integer and x is smaller than all other positive integers) or ( ∃ x )( x is a positive integer and ( ∀ y )( y is a positive integer ⇒ x ≤ y )) or ( ∃ x ∈ Z )[ x > 0 ∧ ( ∀ y ∈ Z )( y > 0 ⇒ y > x )] (m) ( ∀ x )( ∼ ( ∀ y )( x loves y )) or ∼ ( ∃ x )( ∀ y )( x loves y ) or ( ∀ x )( ∃ y )( x does not love y ) (n) ( ∀ x )( ∃ y )( x loves y ) (o) ( ∀ x )( x > 0 ⇒ ( ∃ ! y )(2 y = x ) 2. (a) ( ∀ x )( x is precious ⇒ x is beautiful) All precious stones are beautiful. (b) ( ∃ x )( x is precious ∧ x is beautiful) There is a beautiful precious stone, or Some precious stones are beautiful. (c) ∼ ( ∃ x )( x is isosceles and x is a right triangle) or ( ∀ x )( x is not isosceles or x is not a right triangle) or ( ∀ x )( x is right triangle ⇒ x is not isosceles) or ( ∀ x )( x is isosceles ⇒ x is not a right triangle). There is no isosceles right triangle. (d) ( ∃ x )( x is isosceles ∧ x is a right triangle) There is an isosceles right triangle. (e) ( ∃ x )( x is dishonest) ∧ ( ∃ x )( x is dishonest) Some people are honest and some people are dishonest. (f) ( ∀ x )( x is honest) ∨ ( ∀ x )( x is dishonest) All people are honest or no one is honest. (g) ( ∃ x )( x  = 0 ∧ x is not positive ∧ x is not negative) There is a nonzero real number that is neither positive nor negative. (h) ( ∃ x )( x is an integer ∧ x ≤ − 4 ∧ x ≥ 6)) or ( ∃ x ∈ Z )( x ≤ − 4 ∧ x ≥ 6) There is an integer that is less than or equal to − 4 and greater than or equal to 6. (i) ( ∃ x )( ∀ y )( x ≤ y ) Some integer is less than or equal to every integer, or There is a smallest integer. (j) ( ∃ x )( ∀ y )( x ≥ y ) Some integer is greater than every other integer, or There is a largest integer. (k) ( ∃ x )( ∃ y )[ x is an integer ∧ y is an integer y > x ∧ ( ∀ z )( z ≤ y ∨ x ≤ z )] or ( ∃ x ∈ Z )( ∃ y ∈ Z )[ y > x ∧ ( ∀ z )( z ≤ y ∨ x ≤ z )] There is an integer x and a larger integer y such that there is no real number between them. (l) ( ∀ x )( x is a positive integer ⇒ ( ∃ y )( y is a positive integer) ∧ x > y ) or ( ∀ x ∈ Z )[ x ≤ 0 ∨ ( ∃ y ∈ Z )( y > 0 ∧ x > y )]. For every positive integer there is a smaller positive integer. Or, ∼ ( ∃ x )( x is a positive integer ∧ ( ∀ y )( y is a positive integer ⇒ x ≤ y )) or ∼ ( ∃ x ∈ Z )[ x > 0 ∧ ( ∀ y ∈ Z ( y > 0 ⇒ y > x )] There is no smallest positive integer.

128 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.