Exercise 2.56 March 2017 Q5(a) Given the following arguments: Today is raining and Alia will go to school by bus. If today is raining, then Alia had breakfast at home and she is going to school by bus. If Alia had breakfast at home, then Alia will play the piano or she will walk to school. Alia is not playing the piano. Therefore, Alia walks to school. i) Write the primary propositions above using symbols ������, ������, ������, ������ and ������. ii) Write the premises of the arguments using ������, ������, ������, ������ and ������. iii) Validate the arguments by using rules of inference. 95
Exercise 2.57 January 2018 Q5 Consider the following arguments : Sofia works part time or full time. If Sofia does not play on the team, then she does not work part time. If Sofia plays on the team, she is busy. Sofia does not work full time. i) Write the primary statement using variables p, q, r and s. ii) Write all the premises using the variables in (i). iii) Determine the conclusion of the argument using the rules of inference. 96
Exercise 2.58 December 2018 Q5(a) Consider the following arguments: Yasmeen and Eyka go to the library only if Eyka not going to the town. If Yasmeen does not go to the bookstore then Eyka will go to the town. Yasmeen does not go to the bookstore. i) Declare the primitive propositions using symbols ������, ������, ������ and ������. ii) Write the premises of the argument using those symbols. iii) Find the conclusion of the argument using the rules of inference. 97
Exercise 2.59 June 2019 Q5(a) Consider the following arguments: If Siti does not go shopping then she is staying at home. If Siti goes shopping then she has accompanies. Siti has accompanies only if her friends agree to meet. Therefore, Siti is staying at home or her friends agree to meet. i) Declare the primitive proposition using symbols ������, ������, ������ and ������. ii) Write the premises of the argument using those symbols. iii) Use the rules of inference to prove the argument. 98
Exercise 2.60 June 2019 Q5(b) Show that the argument below is valid using a truth table and state your reason. ������ → ������ ������ ∴ ������ 99
2.6 Quantifiers and Nested Quantifiers Definition 2.15 A declarative sentence is an open statement if (i) it contains one or more variables, and (ii) it is not a statement, but (iii) it becomes a statement when the variables in it are replaced by certain allowable choices. Example 2.35 Consider the following statements. a) There are 366 days in a leap year. b) 2 + 3 = 7 c) ������ − 2 is even. Statement 1 is true. Statement 2 is false. Statement 3 is an open statement, because it is • true when ������ = 2, 4, 6, … (even integers) • false when ������ = 1, 3, 5, … (odd integers) • certain allowable choices made it become a statement. Open statement is denoted by ������(������), ������(������), and so on. Allowable substitution depends on the universal set that is considered. Example 2.36 ������(������): ������ + 2 is an even integer. ������(������, ������):The number ������ − 2������ is odd. ¬������(������): ������ + 2 is an odd (not even) integer. ¬������(������, ������):The number ������ − 2������ is even (not odd). Consider the universal set of integers (the set ℤ), then • ������(10): 10 + 2=12 is an even integer is true. • ������(8,2):The number 8 − 2(2) = 4 is odd is false. 100
• ¬������(6): 6 + 2 = 8 is an odd integer is false. • ¬������(12,3):The number 12 − 2(3) is even is true. Since some substitution results in true statements, the following true statements can be made. • For some ������, ������(������). • For some ������, ������, ������(������, ������). • For some ������, ¬������(������). • For some ������, ������, ¬������(������, ������). “For some ������” and “For some ������, ������” quantify the statements. There are two types of quantifiers: existential quantifier and universal quantifier. Quantifier Existential Universal ∀ Notation ∃ Translated as For all For some For each There exists For every For at least one Example 2.37 ∃������, ������(������): There exists an integer ������ such that ������ + 2 is even. ∃������, ������, ������(������, ������): For some integers ������ and ������, the number ������ − 2������ is odd. However, the statements ∀������, ������(������) and ∀������, ������, ������(������, ������) are both false. ∀������, ������(������): ∀������, ������, ������(������, ������): 101
Example 2.38 Let the universe consists of all integers, and the open statements are given by ������(������): ������ ≥ 0 ������(������): ������y ≥ 0 ������(������): ������y − 3������ − 4 = 0 ������(������): ������y − 3 > 0 Translate the following statements in words. Determine the truth values and provide an example or counterexample. a) ∃������[������(������) ∧ ������(������)] Statement: There is an integer such that ������(������) ∧ ������(������). Truth value: TRUE Example: For ������ = 4, ������(4) ∧ ������(4) is true. b) ∀������[������(������) → ������(������)] Statement: For every integer ������, if ������ ≥ 0, then ������y ≥ 0. Truth value: TRUE Example: For ������ = 1, 2, 3, … (positive integers), the square of ������ will always be positive. c) ∀������[������(������) → ������(������)] Statement: For all integer ������, if ������y ≥ 0 then ������y − 3 > 0. Truth value: FALSE Counterexample: For ������ = 1, 1y is positive but 1y − 3 is not, therefore ������(1) → ������(1) is false. d) ∀������[������(������) ∨ ������(������)] Statement: For each integer ������, ������y − 3������ − 4 = 0 or ������y − 3 > 0. Truth value: FALSE Counterexample: For ������ = 0, ������(0) is false, ������(0) is false, therefore ������(0) ∨ ������(0) is false. 102
e) ∃������[������(������) → ������(������)] Statement: Truth value: Example/Counterexample: f) ∀������[������(������) → ������(������)] Statement: Truth value: Example/Counterexample: Table below summarizes when a quantified is true or false. Statement When is it TRUE? When is it FALSE? For every ������ in the universe, ������(������) is ∃������ ������(������) For some (at least one) ������ in the false. universe, ������(������) is true. There is at least one replacement ������ from the universe for which ������(������) is ∀������ ������(������) For every replacement ������ from the false. universe, ������(������) is true. For every replacement ������ from the ∃������ ¬������(������) For at least one choice ������ in the universe, ������(������) is true. ∀������ ¬������(������) universe, ������(������) is false, so its negation ¬������(������) is true. There is at least one replacement ������ For every replacement ������ from the from the universe for which ¬������(������) universe, ������(������) is false and its is false and ������(������) is true. negation ¬������(������) is true. 103
Example 2.39 Translate the following English sentences into symbolic statements containing one quantifier. Indicate the truth value of each statement. a) For every natural number ������, 2������ + 1 > 0. Symbolic form: ∀������ ∈ ℕ, (2������ + 1 > 0) Truth value: TRUE Example/Counterexample: b) For every integer ������, 2������ + 1 > 0. Symbolic form: ∀������ ∈ ℤ, (2������ + 1 > 0). Truth value: Example/Counterexample: c) There exists an integer ������ such that 2������ + 1 < 0. Symbolic form: ∃������ ∈ ℤ, (2������ + 1 < 0) Truth value: Example/Counterexample: d) There exists a natural number ������ such that ������y + ������ + 41 is a prime number. Symbolic form: Truth value: Example/Counterexample: e) For every natural number ������, ������y + ������ + 41 is a prime number. Symbolic form: Truth value: Example/Counterexample: 104
Sometimes the quantifiers and variables may not appear explicitly in an English sentence. Hence it is a challenge to translate English sentences into symbolic statements. It becomes more challenging when the phrases “for all”, “for every”, “for any”, “for each”, “for some”, “there exists”, or “there is” may not appear in the sentence. Nevertheless, it is fairly easier to translate symbolic statements into English sentences. Table below summarizes the symbolic statements and their corresponding English sentences, for any open statements ������(������) and ������(������). Statement Type Symbolic Form English Sentence Universal Affirmative ∀������ [������(������) → ������(������)] All ������(������) are ������(������). Universal Denial ∀������ [������(������) → ¬������(������)] No ������(������) are ������(������). Particular Affirmative ∃������ [������(������) ∧ ������(������)] Some ������(������) are ������(������). Particular Denial ∃������ [������(������) ∧ ¬������(������)] Some ������(������) are not ������(������). Example 2.40 Let the universe of discourse be the set of integers, ������. Translate the following symbolic statements into English sentences and indicate the truth value of each statement. a) ∀������, [(������ ∈ ������) → (������ ∈ ������)], Statement: (i) For all x, if x is a natural number, then x is an integer. (ii) Every natural number is an integer. Truth value: b) ∀������, [(������ ∈ ������) → (������ ∈ ������)] Statement: (i) For all x, if x is an integer, then x is a natural number. (ii) Every integer is a natural number. Truth value: c) ∃������, [(������ ∈ ������) ∧ (������ ∈ ������)] Statement: (i) There is a number x which is an integer and a natural number. (ii) Some integer is a natural number. Truth value: 105
d) ∃������, [(������ ∈ ������) ∧ (������ ∉ ������)] Statement: (i) For some x, x is an integer and x is not a natural number. (ii) Some integer is not a natural number. Truth value: e) ∃������, [(������ ∈ ������) ∧ (������ ∉ ������)] Statement: (i) For some x, x is a natural number and x is not an integer. (ii) Some natural number is not an integer. Truth value: f) ∀������, [(������ is a prime) → (������ is not a composite)] Statement: (i) For all x, if x is a prime, then x is not a composite. (ii) No prime is a composite. Truth value: The negation of statements with quantifiers follows the rules similar to basic logical connectives. Rules for Negating Statements with Quantifier Let ������(������) be an open statement of distinct variable ������ ¬[∀������ ������(������)] ⟺ ∃������ ¬������(������) ¬[∃������ ������(������)] ⟺ ∀������ ¬������(������) ¬[∀������ ¬������(������)] ⟺ ∃������ ¬¬������(������) ⟺ ∃������ ������(������) ¬[∃������ ¬������(������)] ⟺ ∀������ ¬¬������(������) ⟺ ∀������ ������(������) 106
Example 2.41 ������(������): ������y − 1 is even Let ������(������) and ������(������) be given by ������(������): ������ is odd English sentence: For all integer ������, if ������ is odd, then ������2 − 1 is even. Symbolic statement: ∀������[������(������) → ������(������)] The negation of the statement ¬¿∀������[������(������) → ������(������)]Á ⟺ ∃������¬[������(������) → ������(������)] ⟺ ∃������¬[¬������(������) ∨ ������(������)] ⟺ ∃������ [¬¬������(������) ∧ ¬������(������)] ⟺ ∃ [������(������) ∧ ¬������(������)] Negation statement: There exists an integer ������ such that x is odd and ������y − 1 is odd (not even). The original statement is TRUE and its negation is FALSE. Can you explain why? Example 2.42 ������(������): ������y = 9 Let ������(������) and ������(������) be the open statements: ������(������): 2������ + 1 = 5 The quantified statement ∃������[������(������) ∧ ������(������)] is false, because there is no integer ������ that will make the statement be true. Negation statement: For every integer ������, 2������ + 1 ≠ 5 or ������y ≠ 9. 107
Many mathematical statements contain nested quantifiers which involves more than one quantifiers and also variables. Sometimes the order of the quantifiers in a statement affects its truth value. Rules for Statements with Nested Quantifiers Let ������(������, ������) be an open statement of distinct variables, ������, ������ ∀������ ∀������ [������(������, ������)] ⇔ ∀������ ∀������ [������(������, ������)] ∃������ ∃������ [������(������, ������)] ⇔ ∃������ ∃������ [������(������, ������)] ∃������ ∀������ [������(������, ������)] ⇒ ∀������ ∃������ [������(������, ������)] Example 2.43 Let the universe be the set of all integers and let ������(������, ������): ������ + ������ = 17. Consider the following mathematical statements with nested quantifiers. a) For every integer ������, there exists an integer ������ such that ������ + ������ = 17. Symbolic statement: Truth value: True Example: For every integer ������, there exists an integer ������ = 17 − ������. For ������ = 3, there is ������ = 17 − 3 = 14 so that ������ + ������ = 3 + 14 = 17. b) There exists an integer ������ such that for all integer ������, ������ + ������ = 17. Symbolic statement: Truth value: False Counterexample: For ������ = 3, it must be that ������ = 17 − 3 = 14 so that ������ + ������ = 3 + 14 = 17. Note that ������ cannot be any other number. 108
Example 2.44 Let the following statements with the universe of discourse being the set of integers, ℤ. Determine the truth value of each statement and give an example or a counterexample for each statement. a) ∀������ ∀������ (������ + ������ = 0) Statement: For all integers ������, ������, ������ + ������ = 0. Truth value: FALSE Counterexample: For ������ = 2 and ������ = 3, ������ + ������ = 2 + 3 = 5 ≠ 0 b) ∀������ ∀������ (������ + ������ = 0) Statement: For all integers ������, ������, ������ + ������ = 0. Truth value: FALSE Counterexample: For ������ = 2 and ������ = 3, ������ + ������ = 2 + 3 = 5 ≠ 0. c) ∀������ ∃������ (������ + ������ = 0) Statement: For every integer ������ there exists an integer ������ such that ������ + ������ = 0. Truth value: TRUE Example: For every integer ������, there exists an integer ������ = −������. For ������ = 3, there is ������ = −3 so that ������ + ������ = 3 + (−3) = 0. d) ∃������ ∀������ (������ + ������ = 0) Statement: There exists an integer ������ such that for every integer ������, ������ + ������ = 0. Truth value: FALSE Counterexample: For ������ = 3, it must be that ������ = −3 so that ������ + ������ = 0. ������ cannot be any number. e) ∃������ ∃������ (������ + ������ = 0) Statement: There exists integers ������ and ������ such that ������ + ������ = 0. Truth value: TRUE Example: For ������ = 3, there is ������ = −3 so that ������ + ������ = 3 + (−3) = 0. 109
Exercise 2.61 March 2012 Q4(a) Given the following open statements, ������(������): ������y − ������ − 2 = 0 ������(������): ������y + 4������ + 3 = 0 ������(������): ������ ≥ 0 ������(������, ������): ������ < ������Ê ������(������, ������): ������������ = 10 Determine the truth values of the following quantified statements where the universal set is the set of all integers. Explain your answer by giving an example or counterexample. i) ∃������[������(������) ∧ ������(������)] ii) ∀������[������(������) → ������(������)] iii) ∃������∀������[������(������, ������)] iv) ∀������∃������[������(������, ������)] 110
Exercise 2.62 March 2012 Q4(b) Consider the following open statements where the universal set is the set of all animals: ������(������): ������ is a crocodile ������(������): ������ has blue eyes i) Express the statement \"All crocodiles have blue eyes\" in symbolic form. ii) Write the negation of the statement in i) in English. 111
Exercise 2.63 March 2013 Q5(a) For the universe of all integers, consider the open statements ������(������): ������ ≥ 0 ������(������): ������y + ������ − 12 = 0 ������(������, ������): ������y������ ≥ 0 Determine the truth value of each statement and give an example or a counter example for each. i) ������(1) ii) ∃������[������(������) ∧ ������(������)] iii) ∃������[������(������)] ∧ ∃������[������(������)] iv) ∃������∀������[������(������, ������)] v) ∀������∃������[������(������, ������)] 112
Exercise 2.64 March 2013 Q5(b) Negate and simplify each of the following. i) ∃������∀������(������y������ + 5 > 0) ii) ∃������∀������[������(������) → ������(������)] Exercise 2.65 September 2013 Q6(a) Consider the universe of all real numbers and determine whether these statements are true or false. Justify your answers. i) ∃������ ∈ ������ such that ������y + 1 = 0. ii) ∀������ ∈ ������, ∃������ ∈ ������ such that ������ + 3������ = 4. iii) ∀������ ∈ ������, ������k ≥ ������y. iv) ∃������ ∈ ������ such that ∀������ ∈ ������, ������ + ������ = 0. 113
Exercise 2.66 September 2013 Q6(b)&(c) b) Rewrite each of the following statement in symbolic forms: i) There exist integers ������ and ������ such that both ������������ < 0 and ������ + ������ > 0. ii) For all real numbers ������ and ������, ������ ≠ ������ implies that ������y + ������y > 0. c) Express in symbols and words the negation of the statement in part b ii) above. 114
Exercise 2.67 March 2014 Q5(a) Consider the following open statements where the universal set is the set of positive integers. ������(������): ������ is odd ������(������): ������ is a multiple of 4 ������(������, ������): ������ + ������ divides 56 ������(������, ������): ������������ is even Translate each of the following statements into an English sentence and determine whether the statement is true or false. i) ∀������œ¬������(������)• ii) ∀������œ������(������)• iii) ∃������∃������œ������(������, ������)• iv) ∃������∀������œ������(������, ������)• Exercise 2.68 March 2014 Q5(b) Find the negation of the following statement: ∀������∀������[(������y < ������) ∧ (������y − 16 ≠ 0)] 115
Exercise 2.69 September 2014 Q5(a) Write the negation of each of the following statement: i) There is a real number ������ ≥ 2 such that ������y + ������ − 6 ≥ 0. ii) For each element ������ in the set ������, ������ is in the set ������. Exercise 2.70 September 2014 Q5(b) Consider the universe of all integers, determine the truth value of each of the following quantified statement. Give a reason to support your answer. i) ∀������(������k > 0) ii) ∃������(������k ≥ ������) iii) ∃������∃������œ(2������ + ������ = 5) ∧ (������ − 3������ = −8)• 116
Exercise 2.71 March 2015 Q6(a) Determine the truth value for each of the following statements with the indicated universal set and briefly explain why. i) ∀������∃������, ������ + ������ = 0; universal set ������, the set of integers. ii) ∃������∃������, ������ + 5 = 2 + ������; ������ = {0, 1, 2}. iii) ∃������∀������, ������ ≤ ������; universal set ������, the set of natural numbers. Exercise 2.72 March 2015 Q6(b) Find the negation for each of the following statements and simplify your answers. i) ∃������∀������ ¤������y������ + y > 0¥ k ii) ∀������¿œ������(������) ∧ ������(������)• → ������(������)Á iii) ∀������∃������[(������ ≥ ������) ∧ (������������ = 2)] 117
Exercise 2.73 September 2015 Q4(a) Determine the truth value for each of the following statements with the indicated universal set and briefly explain your answer. i) ∃������∀������(������������ = 0) universal set = All real numbers. ii) ∀������∃������(������ < ������) universal set = ������G, the set of positive integers. iii) ∃������∀������(������ < ������y) universal set = ������G, the set of positive real numbers. Exercise 2.74 September 2015 Q4(b) Negate each of the following statement. i) ∀������ > 0, ∃������ > 0 (������ + ������ = 0 and ������ > ������) ii) ∀������ ∈ ������, ∃������ ∈ ������ œ������(������, ������) → ������(������, ������)• 118
Exercise 2.75 September 2015 Q5 Given the open statement: ������(������): ������ is a student ������(������): ������ is smart ������(������): ������ wears glasses Universe: All people Translate the following statement into logical symbols involving quantifiers. i) All students wear glasses ii) Some students are not smart iii) No smart people wear glasses 119
Exercise 2.76 March 2016 Q3(b) Determine the truth value of each statement with the indicated universal set. i) ∃������∃������(������ + ������ = 3) universal set = {1, 2, 3}. ii) ∃������∀������œ(������ + 1) < ������• universal set = ������G, the set of positive integers. iii) ∀������∃������(������ + ������ = 5) universal set = {0, 1, 2, 3, 4, 5}. Exercise 2.77 March 2016 Q4(a) Consider the following statements where the universal set is the set of all philosophers. ������(������): ������ is a philosopher ������(������): ������ has brilliant ideas Express the statement \"All philosophers have brilliant ideas\" in symbolic form and negate the statement. Give your answer in words. 120
Exercise 2.78 March 2016 Q4(b) Express each of the following statements in symbolic form and negate the statement: i) For any integer ������, there exists an integer ������ such that ������������y − 5 > 0. ii) There exist real numbers ������ and ������ such that ������ ≠ ������ implies ������y + ������y > 0. iii) For any integer ������, there exists an integer ������ such that ������������ ≤ 0 and ������ > ������. Exercise 2.79 October 2016 Q4(b) Determine the truth value of each of the following statements if the domain for all variables consists of all integers. Give an example or counterexample for each statement. i) ∃������∃������(������ + ������y = 4) ii) ∃������∃������œ(������ + ������ = 3) ∧ (������ − ������ = 0)• iii) ∃������∃������œ(������ + ������ = 8) ∧ (������ − ������ = 2)• 121
Exercise 2.80 October 2016 Q4(a) Consider the following statements where the universal set is the set of all writers. ������(������): ������ is a writer ������(������): ������ has writer's block Express the statement \"Every writer has writer's block\" in symbolic form and negate the statement. Give your answer in words. Exercise 2.81 October 2016 Q4(b) Express each of the following statements in symbolic form and negate the statement: i) For any integer ������, there exists an integer ������ such that Ë������������ − 5 > 0. ii) There exist real numbers ������ and ������ such that ������ < ������ implies ������ + ������y > 0. iii) For any integer ������, there exists an integer ������ such that ������������ ≤ 0 and ������y > ������. 122
Exercise 2.82 March 2017 Q3(b) Determine the truth value of each of the following statements with the indicated universal set. Justify your answer by giving examples or counterexamples. i) ∀������ ∈ ������G, ∃������ ∈ ������G (������ + ������ > 1) ii) ∀������ ∈ ������, ∃������ ∈ ������ (������������ > 0) iii) ∃������ ∈ ������, ∀������ ∈ ������ (������y < ������y + 1) Exercise 2.83 March 2017 Q4(a) Let the following statement be the universal sets of all mathematicians. \"Every mathematician good in physics if he says that physics and mathematics are easy subjects.\" i) Express the statement above in symbolic form. ii) Negate the statement. iii) Based on your answer in part (ii), give your answer in words. 123
Example 2.45 March 2017 Q4(b) Find the negation of the following quantified statement. i) ∀������ > 0 ∃������ < 0, [������(������, ������) → ¬������(������, ������)] ii) ∃������ ∈ ������ ∀������ ∈ ������G, [(������y + ������y > 0) ∧ (������������ ≤ 0)] Exercise 2.84 January 2018 Q4(a) Consider the following statement where the universal set is the set of all integers. \"For every ������, there exists ������ such that ������������ ≤ 2\" i) Express the statement in symbolic form. ii) Determine the truth value and negate the given statement. 124
Exercise 2.85 January 2018 Q4(b) Determine the truth value of the following quantified statements where the universal set is the set of all integers. Explain your answer by giving an example or a counterexample. i) ∀������∀������, (4 − ������y < ������) ii) ∃������∃������ ∋ (4 − ������y < ������) iii) ∀������∃������ ∋ ������y < ������ Exercise 2.86 December 2018 Q4(a) Negate the following statement: ∃������∀������ (������k + ������k < 0) 125
Exercise 2.87 December 2018 Q4(b) Determine the truth value of each statement with indicated universal set. Justify your answer by giving an example or counter example. i) ∀������∃������(������y < ������) universal set= ������, the set of natural numbers. ii) ∀������∃������(������ + ������ = 0) universal set =������G, the set of positive integers. iii) ∃������∃������(������y + ������y = 13) universal set = ������, the set of integer numbers. iv) ∀������(2������ + 1 = 6) universal set = ������, the set of real numbers. Exercise 2.88 June 2019 Q3 Determine the truth value of each statement with the indicated universal set and justify your answer by giving an example or counter example. Hence, negate and simplify each statement. a) ∀������, [(������ > 0) ∨ (������ = 0) ∨ (������ < 0)], universal set is the set of real numbers. b) ∀������∃������(������ + ������ is even), universal set is the set of integers. c) ¬(∃������, (������ is odd)), universal set is the set of integers. 126
Chapter 3: Proving Techniques “Mathematics” is the language of mathematicians. “Proof” is a method of communicating a mathematical truth to another person who also “speaks” the language. Like learning language, much practice is needed to become fluent. In this chapter, we will learn some of the basic techniques used to prove mathematical propositions. 3.1 Introduction We start by revisiting the concept of “statement”. A statement is a sentence that is either true or false. Example 3.1 Consider a) 2 = 0 b) 3������ = 5 and ������ = 1. c) ������ ≯ 0 d) A square has four equal sides. • Statement (a) is always false and statement (d) is always true. • Statements (b) and (c) are open (conditional) statements. We need some kind of method in proving open statements are true. Consider proving an implication is true. Refer to the truth table for ������ → ������, where ������ is the hypothesis and ������ is the conclusion. ������ ������ ������ → ������ TRUE TRUE TRUE TRUE FALSE FALSE FALSE TRUE TRUE FALSE FALSE TRUE 127
Example 3.2 Determine the truth value of the following statements. (Use Table 1 to determine the truth value.) If 1 < 2, then 4 < 3. If 2 < 1, then 3 < 4. Example 3.3 Prove that the following statement is true. If ������ > 2, then ������y > 4. The truth values of ������: ������ > 2 and ������: ������y > 4 depend on the variable ������ whose value is not known. By reasoning (based on Table 1): ������ can be either true or false. Assume ������ is false, then ������ is either true or false. In either case, ������ implies ������ is true. Therefore, we only need to consider the case which ������ is true. When A is true, then B is either true or false. Because we want to prove ������ implies ������ is true, so ������ must be true. ������ ������ ������ → ������ TT T If ������: ������ > ������ is true, then ������: ������������ > ������ must be true, so that ������ → ������ is true. TF F If ������: ������ > ������ is false, then ������: ������������ > ������ can be either true or false, FT T so that ������ → ������ is true. FF T Hence, when trying to prove “������ implies ������” is true, I. Assume ������ is true. II. Use this assumption to reach (prove) the conclusion that ������ is true. 128
Exercise 3.1 September 2013 Q8 Prove the following statement: Let ������ be a real number. Then ������ = 1 if and only if ������k + ������y + 2������ − 4 = 0. 129
3.2 The Forward – Backward Method Before proving any propositions, we need to identify the statements A and B. ������: The statement assumed to be true. (Hypothesis) ������: The statement to be proven. (Conclusion) Generally, Everything between the words “if” and “then” is the hypothesis. Everything that comes after the word “then” is the conclusion. Example 3.4 If the right triangle ������������������ with sides of lengths ������ and ������ and hypotenuse ������ has an area of ÐÊÑ, then the triangle ������������������ is isosceles. ������ ������ ������ ������ ������ ������ Analysis of Proof: ������: If the right triangle ������������������ with sides of lengths ������ and ������ and hypotenuse ������ has an area of ÐÊÑ. ������: The triangle ������������������ is isosceles. Backward Process I. Ask a key question, “How can I show that …?” The question should be general and contain no symbols. II. Provide an answer to the key question in general, avoid symbols. III. Apply this answer to the problem using appropriate notations. From ������: The triangle ������������������ is isosceles. I. Key question: How can I show that a triangle is isosceles? II. General answer: Show that a triangle has two equal sides. III. Apply answer to problem: Since the hypotenuse is of length ������, then it must be that sides of lengths ������ and ������ are equal. Show that ������ = ������. 130
Hence, we obtained a new statement, ������������: ������ = ������ Now, continuing the backward process. From ������������: ������ = ������ I. Key question: How can I show that two numbers are equal? II. General answer: Show that the difference between the two numbers is zero. III. Apply answer to problem: Show that ������ − ������ = 0 Hence, we obtained a new statement, ������������: ������ − ������ = ������ Sometimes it might be hard to answer key questions and we may get stuck during the backward process. Therefore, we should try the forward process. Forward Process I. Derive statements from ������ which we assume is true. Hence, these statements are true as a result of ������ being true. II. These statements should be directed towards proving ������ is true. ������1: ������������ = ������y Area of ������������������ using formula ¬ × height × base = given area ������������������ 2 4 y ������2: ������y + ������y = ������y Since ������������������ is a right triangle, apply Pythagorean Theorem Substitute ������2 into ������1 ������3: ������������ = ������y + ������y 2 4 ������4: ������y − 2������������ + ������y = 0 Simplify ������3 Simplify ������4 ������5: (������ − ������)y = 0 Simplify ������5 ������6: ������ − ������ = 0 ������6 ⟺ ������2 Proof Complete Condensed Proof: From the hypothesis and the formula for the area of right triangle, the area of ������������������ = ØÙ = ÐÊÑ. y By the Pythagorean theorem, ������y + ������y = ������y and on substituting ������y + ������y for ������y, and performing some algebraic manipulations, one obtains (������ − ������)y = 0. Hence, ������ = ������ and so the triangle ������������������ is isosceles. 131
Exercise 3.2 September 2013 Q10 Use the forward-backward method to prove that: If triangle ������������������ is equilateral, then the area is √3/4 times the square of the length of a side. Your answer should have an analysis of the proof and the condensed proof. ������ ������ ������ Analysis of Proof: ������: Triangle ������������������ is equilateral. ������: The area is √3/4 times the square of the length of a side. ������1: Area = √3 (���ÜÜ���Ü���Ü���)y 4 ������1: Let a line ������������ divides ������������������ into two equal right triangles such that ������������������ = ������������������ ������2: ���ÜÜ���Ü���Ü��� = Ü���Ü���Ü���Ü��� ������3: ���ÜÜ���Ü���Ü��� = Ü���Ü���Ü���Ü��� 2 ������4: (Ü���Ü���Ü���Ü���)y + (Ü���Ü���Ü���Ü���)y = (���ÜÜ���Ü���Ü���)y Ý���ÜÜ���2Ü���Ü���Þy + (Ü���Ü���Ü���Ü���)y = (���ÜÜ���Ü���Ü���)y (Ü���Ü���Ü���Ü���)y = (���ÜÜ���Ü���Ü���)y − ÝÜ���Ü���2Ü���Ü���Þy (Ü���Ü���Ü���Ü���)y = 4(���ÜÜ���Ü���Ü���)y − (���ÜÜ���Ü���Ü���)y 4 (Ü���Ü���Ü���Ü���)y = 3(���ÜÜ���4Ü���Ü���)y Condensed Proof: Ü���Ü���Ü���Ü��� = √3 Ü���Ü���Ü���Ü��� If the triangle ������������������ is equilateral, then let a line ������������ 2 divides ������������������ into two equal right triangles such that ������5: 1 Area = 2 × ���ÜÜ���Ü���Ü��� × ���ÜÜ���Ü���Ü��� ������������������ = ������������������. Then, Ü���Ü���Ü���Ü��� = ���ÜÜ���Ü���Ü��� and ���ÜÜ���Ü���Ü��� = ÜßÜyÜàÜ. Apply the Pythagorean theorem, it follows that (���ÜÜ���Ü���Ü���)y + (���ÜÜ���Ü���Ü���)y = = 1 × ���ÜÜ���Ü���Ü��� × √32 Ü���Ü���Ü���Ü��� 2 2 (Ü���Ü���Ü���Ü���)y and we can rewrite ���ÜÜ���Ü���Ü��� = √ky ßÜÜÜàÜ. Hence, it can be = √3 (���ÜÜ���Ü���Ü���)y 4 Area = √k (Ü���Ü���Ü���Ü���)y, √3/4 shown that Ê that is the area is ������5 ⟺ ������1 Proof Complete times the square of the length of a side. 132
Exercise 3.3 September 2015 Q6 Use Forward-Backward Method to prove the following proposition. If the right triangle ������������������ is an isosceles triangle then the perimeter of the triangle ������������������ is œ√2 + 2• times one of the congruent sides. Your answer should have an analysis of the proof and the condensed proof. 133
Exercise 3.4 October 2016 Q6 Use the Forward-Backward Method to prove the following proposition. If ������ and ������ are two positive real numbers, then ¤áGkâ¥y > Êáãâ. Your answer should have an analysis of the proof and the condensed proof. 134
Exercise 3.5 March 2017 Q6 Use the Forward-backward Method to prove the following proposition. If ������������������ is a triangle with ������������ = ������������ and ∠������ = 90°, then the area of triangle is ¤ßyæ¥y. Show the analysis of proof and condensed proof. 135
Exercise 3.6 January 2018 Q6 Prove using the Forward - Backward Method. If ������: ������ → ������ and ������: ������ → ������ are both one-to-one functions, then ������ ∘ ������ is one-to-one. Show the analysis of proof and the condensed proof. [Hint : A function ������: ������ → ������ is said to be one-to-one if and only if ������(������¬) = ������(������y) implies that ������¬ = ������y for all ������¬, ������y in ������] 136
Exercise 3.7 December 2018 Q6 Prove using forward-backward method. If a function ������ is continuous on [������, ������] and differentiable on (������, ������) , then there exist a real number ������ ∈ (������, ������) such that ������T(������) = è(ââ)IIáè(á). Given that ������(������) = ������y − 5������ + 7 on [−1, 3]. Show the analysis of proof only. 137
3.3 Definition and Mathematical Terminology One of the ways to answer a key question is by using definitions. Some definitions are presented as follows. Definition 3.1 An integer n divides an integer ������ (written ������|������) if ������ = ������������, for some integer ������. Definition 3.2 A positive integer ������ > 1 is prime if the only positive integers that divide ������ are 1 and ������. Definition 3.3 A triangle is isosceles if two of its sides have equal length. Definition 3.4 Two pairs of real numbers (������¬, ������¬) and (������y, ������y) are equal if ������¬ = ������y and ������¬ = ������y. Definition 3.5 An integer ������ is even if and only if the remainder on dividing ������ by 2 is 0. Definition 3.6 An integer ������ is odd if and only if ������ = 2������ + 1 for some integer ������. Definition 3.7 A real number ������ is rational if and only if ������ can be expressed as the ratio of two integers ������ and ������ in which the denominator ������ is not 0. Definition 3.8 Two statements ������ and ������ are equivalent if and only if “������ implies ������” and “������ implies ������”. Definition 3.9 The statement ������ AND ������ (written ������ ∧ ������) is true if and only if ������ is true and ������ is true. Definition 3.10 The statement ������ OR ������ (written ������ ∨ ������) is true in all cases except when ������ is false and ������ is false. Example 3.5 If n is an even integer, then n2 is an even integer. Analysis of Proof: ������: n is an even integer. ������: ������y is an even integer. ������1: ������y can be expressed as 2 times some other integer. 138
������1: ������ = 2������, for some integer ������. (Definition of even integer) ������2: ������y = ������ × ������ = 2������ × 2������ = 4������y = 2(2������y) ������3: ������y is 2 times some other integer. ������3 ⟺ ������1 Proof Complete Condensed Proof: Because ������ is an even integer, there is an integer ������ for which ������ = 2������. Consequently ������y = (2������)y = 2(2������y), and so ������y is an even integer. Example 3.6 If the right triangle ������������������ with sides of lengths ������ and ������ and hypotenuse of length ������ satisfies ������ = √2������������, then the triangle ������������������ is isosceles. Analysis of Proof: ������: The right triangle ������������������ with sides of lengths ������ and ������ and hypotenuse of length ������ satisfies ������ = √2������������. ������: The triangle ������������������ is isosceles. ������1: The area of triangle ������������������ equals éÊÑ. (From previous example, Example 3.4) ������2: ������������ = ������y 2 4 ������1: ������y = 2������������. ������2: ������������ = ������y 2 4 ������2 ⟺ ������2 Proof Complete Condensed Proof: By the hypothesis, ������ = √2������������., so ������2 = 2������������. or equivalently, ������������ = ���4���2. Thus the area of the right triangle 2 ������������������ = éÊÑ. As such, the hypothesis, and hence the conclusion of Example 3.4 is true. Consequently, the triangle ������������������ is isosceles. 139
Exercise 3.8 March 2012 Q8 a) Define an odd integer ������. b) Let ������ and ������ be odd integers. By forward-backward method, prove that ������ + ������ is even and ������������ is odd. 140
Exercise 3.9 March 2013 Q6 Prove using the forward-backward method, that for all integers x and y: If ������ is odd and ������ is odd, then ������������ is odd Your answer should have an analysis of the proof and the condensed proof. 141
Exercise 3.10 September 2013 Q10(a) State brief definitions of the following: i) upper bound. ii) rational number. Exercise 3.11 March 2014 Q6 Use the forward-backward method, prove that: If ������ is an even integer and ������ is an odd integer, then 4 divides ������y������y . Your answer should have an analysis of the proof and the condensed proof. 142
Exercise 3.12 March 2014 Q7(a) Define ������|������ where ������, ������ are both integers. Exercise 3.13 September 2014 Q6 By using forward-backward method, prove the following proposition. If ������ and ������ are consecutive integers and ������ is even, then ������y − ������y + 7 is divisible by 2. Your answer should have an analysis of proof and the condensed proof. 143
Exercise 3.14 March 2015 Q8 Use Forward-Backward Method to prove the following proposition, If ������ and ������ are consecutive integers, then (������ + ������)y is an odd integer. Your answer should have the analysis of proof only. 144
Search
Read the Text Version
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220