State logical expression for the following circuit diagrams. Simplify the logical expression using the laws of logic. Hence, draw the simplified circuit. a) T1 pq (������ ∧ ������) ∨ (������ ∧ ������) qr T2 ⟺ (������ ∧ ������) ∨ (������ ∧ ������) ⟺ (������ ∨ ������) ∧ ������ Simplified circuit b) T1 p r T2 ¬q r q ¬t ¬t ¬q 93
Exercise 5.2 1. Construct the truth table for (������ → ������) ∧ (������ → ������) and ������ ↔ ������. What is the conclusion that you can make from both of the truth tables? 2. Construct the truth table for ������ → ������ and ¬������ ∨ ������. What is the conclusion that you can make from both of the truth tables? 3. State the converse, inverse and contrapositive of the statements below. a) If I don’t pay my loan, then I will have to leave town. b) If the program does not fail, then the program will begin. c) If I do not specify the initial condition, then my program will not begin. d) ������ → ¬(������ ∧ ������) e) If I am smart, then I am rich. f) If ������E = ������, then ������ = 0 or ������ = 1. 4. Prove the following expressions using the laws of logic. a) ������ ∨ (������ → ������) ⟺ ������> b) (������ ∧ ������) ∧ ¬������ ⟺ ������> c) ������ ∨ B������ ∧ (������ ∨ ������)C ⟺ ������ d) (������ → ������) ∨ ¬������ ⟺ ¬������ ∨ ������ e) (¬������ ∨ ������) ∧ (������ ∧ ������) ⟺ ������ ∧ ������ 5. By using the Laws of Logic, simplify the following expression. (¬������ → ������) ∨ ¬F������ ∨ B(������ ∧ ������) ∨ (������ ∧ ¬������)CG 6. A switching network is given below. p pr q AB p qr Give the logical expression that represents the network above. a) Use the rules of logic to show that expression found in (a) can be simplified as ������ ∧ ������. b) Draw the circuit for the expression ������ ∧ ������. 7. Draw a switching network to represent the following logical expression. (¬(������ ∧ ¬������) ∨ ������) ∧ (¬(������ ∧ ¬������) ∨ ¬������) a) Simplify the logical expression below using the Laws of Logic. b) Hence, draw the simplified version of the circuit. 94
Logical Implication and Rules of Inference Consider the implication hypothesis (������D ∧ ������E ∧ … ∧ ������J) → ������ conclusion ������ = positive integers The statements ������D, ������E, …, ������J are called premises. Definition 5.11 A valid argument is an argument whose conclusion is true whenever all the premises are true. One way to show that an argument is valid is to show that the statement (������D ∧ ������E ∧ … ∧ ������J) → ������ is a tautology. Let ������, ������, and ������ denote the primitive statements given as ������: Dennis studies trigonometry. ������: Dennis memorizes the trigonometric identities. ������: Dennis passes the trigonometry test. Let ������D, ������E, and ������M denote the premises ������D: If Dennis studies trigonometry, then he will pass the trigonometry test. ������E: If Dennis does not memorize the trigonometric identities, then he’ll study trigonometry. ������M: Dennis fails the trigonometry test. ������: Therefore, Dennis memorizes the trigonometric identities. 95
Rewrite ������D, ������E, and ������M in symbolic form. ������D: ������E: ������M: ������: Build the truth table for the implication. ������ ������ ������ ¬������ ������ → ������ ¬������ → ������ ¬������ B(������ → ������) ∧ (¬������ → ������) ∧ ¬������C → ������ ������ ������D ������E ������M ������D ∧ ������E ∧ ������M (������D ∧ ������E ∧ ������M) → ������ Since the final column is all true, the implication is a tautology. Hence, B(������ → ������) ∧ (¬������ → ������) ∧ ¬������C → ������ is a valid argument. For any primitive statements ������, ������, and ������, the implication is a tautology. N������ ∧ B(������ ∧ ������) → ������CO → (������ → ������) ������ ������ ������ N������ ∧ B(������ ∧ ������) → ������CO → (������ → ������) ������D ������E ������ ������D ∧ ������E (������D ∧ ������E) → ������ 96
Consequently, for the premises ������D: ������E: and the conclusion ������: we know that N������ ∧ B(������ ∧ ������) → ������CO → (������ → ������) is a valid argument. Definition 5.12 If ������ and ������ are arbitrary statements such that ������ → ������ is a tautology, then we say that ������ logically implies ������ (written as ������ ⟹ ������). From the previous examples (Example 5.24 & 5.25), we can say that • Since B(������ → ������) ∧ (¬������ → ������) ∧ ¬������C → ������ ⟺ ������>, then B(������ → ������) ∧ (¬������ → ������) ∧ ¬������C logically implies ������ B(������ → ������) ∧ (¬������ → ������) ∧ ¬������C ⟹ ������ • Since N������ ∧ B(������ ∧ ������) → ������CO → (������ → ������) ⟺ ������>, then 97
Rules of Inference A set of rules that can be used to determine the validity of an argument. The validity of an argument can be determined using a truth table. But this method can become tedious, especially when an argument involves too many primitive statements. Thus, a technique called \"Rules of Inference\" should be used as presented below. Rule of Example Name of Rule Inference Rule of Detachment ������ → ������ If I watch Netflix, then today is Sunday. (Modus Ponens) a) ������ ∴ ������ I watch Netflix. Therefore, today is Sunday. ������ → ������ If 100 is divisible by 50, then 50 is even. b) ������ → ������ If 50 is even, then 50 is divisible by 2. Law of Syllogism ∴ ������ → ������ Therefore, 100 is divisible by 2. ������ → ������ If I watch Netflix, then today is Sunday. c) ¬������ ∴ ¬������ Today is not Sunday. Modus Tollens Therefore, I don’t watch Netflix. ������ ∨ ������ Steve is at the library or the coffee shop. Disjunctive d) ¬������ Steve is not at the library. Syllogism ∴ ������ Therefore, Steve is at the coffee shop. ������ Conjunction e) ������ ∴ ������ ∧ ������ f) ������ ∧ ������ Simplification ∴ ������ g) ������ Addition ∴ ������ ∨ ������ All the argument above can be shown to be valid by using truth tables. We can also use equivalent identity to determine the validity of arguments, which includes Contrapositive: ������ → ������ ⟺ ¬������ → ¬������ Implication: ������ → ������ ⟺ ¬������ ∨ ������ 98
Use the rules of inference and equivalent statement to show that the following arguments are valid. a) ������ ∧ ������ ������ → ������ ∴ ������ ∨ ������ No. Reasons 1. ������ ∧ ������ Premise 1 2. ������ → ������ Premise 2 3. ������ 1, simplification 4. ������ 2, 3, Modus Ponens 5. ������ ∨ ������ 4, Addition with r b) ������ → ������ ¬������ → ������ No. ������ → ������ 1. ¬������ → ������ ∴ ¬������ → ������ 2. ������ → ������ 3. ¬������ → ������ Reasons 4. ������ → ������ 5. ¬������ → ¬������ 6. ¬������ → ������ Consider the following argument. If Min is nominated for the team leader post, then Sue will not vote for Min. If Min is the elected team leader, then Min is nominated for the post. Sue did not vote for Min. Therefore, Min is not the elected team leader. a) Write all the primitive statements. 99
b) Write all the premises and the conclusion. c) Show that the above argument is valid by using rules of inference. Find the conclusion for the following argument. If Alex decides to sleep late at night, then he will watch a football match. If Alex decides not to sleep late at night, then he will wake up early. If Alex wakes up early, then he will attend a lecture. 100
Exercise 5.3 1. Use truth tables to determine if each of the following statement is true. a) B¬������ ∧ (������ → ������)C ⟹ ¬������ b) (������ → ������) ∧ (������ → ������) ⟹ ¬������ → ¬������ c) (������ → ������) ∧ ������ ⟹ ������ d) ¬(������ → ������) ⟹ ¬������ e) ¬(������ → ������) ⟹ ¬������ 2. Prove the validity of the following arguments using the rules of inference. a) ������ → ������ b) (������ ∨ ������) → ������ c) ������ ∨ ������ ������ → ������ ¬������ → ������ ¬������ → ¬������ ������ → ������ ∴ ������ ∨ ������ ∴ ������ → ������ ∴ ������ ∨ ������ 3. Given the following hypotheses. If Aiman is in a good mood, then he will study. If he did not study, then he will play computer games. If Aiman plays computer games, then he will not do anything else. Aiman is in a good mood, or he is doing something else. a) Write each primary statement above using the variables ������, ������, ������ and ������. b) Write all the hypotheses or premises. c) Use the Rules of Inference and (or) the Rules of Logic to derive the conclusion. d) Convert the conclusion in words. 4. Determine whether this argument is valid. If Helmi is able and willing to help people, he will do so. If Helmi were unable to help people, he would be incapable. If Helmi is unwilling to help people, then he would be despicable. Helmi does not help people. If Helmi is helpful, then he is neither incapable nor despicable. Therefore, Helmi is not helpful. 101
CHAPTER 6: INDUCTION AND RECURSION Introduction Sequences and summations are a form of a loop function. Mathematicians will study the patterns of these numbers to derive a conjecture. Mathematical induction is used to prove these conjectures. The induction method applies the unique properties of the set of positive integers ℤ\". This chapter gives some notations used in dealing with sequences and defining recursive functions. Sequences and Summations Definition 6.1 A sequence is an ordered list of numbers. The most common way to write a sequence is as follows. ������$, ������&, ������', … , ������) where ������$ is the first term ������& is the second term ������' is the third term ������) is the ������-th term, and so on A sequence may have finite number of terms, for instance a) 1, 3, 5, 7 b) $ , $ , $ , $ , $ , $ , $ , $ & ' / 0 1 2 3 4 c) −2, 4, −6, 8, −10, 12, −14 A sequence may also have infinite number of terms, for instance a) 0, 1, 2, 3, 4, 5, … b) 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, … c) 3, −9, 27, −81, 243, −729, 2187, … 102
A convenient way of writing sums is by using the Greek letter Σ (capital sigma, corresponding to the letter S) and is called sigma notation. Definition 6.2 If ������=, ������=\"$, …, ������) are real numbers and ������ and ������ are integers such that ������ ≤ ������, then the summation of ������ terms is ) B ������C = ������= + ������=\"$ + ⋯ + ������) CD= This tells us to add ������ End with ������ = ������ B ������������ ai represents the general formula for the i-th term ������D������ Start with ������ = ������ Evaluate the following summations. 1 a) B ������ CD$ / b) B ������& CD& ) c) B ������ CDL d) ) ������ ������ B CD$ 2 e) B(2������ + 1) CD$ f) ' ������ − 1 2 + ������' B CD$ 103
Write the sum 2', 3', …, ������' in sigma notation. Sigma notation ������ Formula of ������������ ) 2 2' 3 3' 2' + 3' + ⋯ + ������' = B ������' !! ������ ������' CD& Write the sequences below as a summation of ������ terms using sigma notation. a) 1, 3, 5, 7, … ������ ������������ Formula of ������������ Sigma notation 11 2(1) − 1 23 2(2) − 1 4 5 !! n! b) 1, 4, 9, 16, 25, … Formula of ������������ Sigma notation ������ ������������ 1 2 3 4 5 ! n! 104
Definition 6.3 A conjecture is a guess based on incomplete or doubtful information/experience. Find a suitable conjecture for the following sequences. ������������ = Total Sum a) 1, 4, 9, 16, 25, … ������������ Formula for ������������ ������ ������������ Expanded form 1 12 11 1 4 22 23 9 32 35 1+3 16 47 1+3+5 25 59 n Conjecture: ) B(2������ − 1) = 1 + 3 + 5 + ⋯ + (2������ − 1) = ������& CD$ b) 2, 6, 12, 20, … Expanded form ������������ Formula for ������������ ������ ������������ Conjecture: 105
Exercise 6.1 1. Write the first four terms of the sequences defined by the formulas below. a) ������C = C , ������ ∈ ℤ\" CQ\"$ b) ������) = 3, ������ ≥ 0, ������ ∈ ℤ c) ������V = 5 − V , ������ ∈ ℤ\" & d) ������Y = ZY'[ , ������ ∈ ℤ\" 2. Given the formula ) B(4������ − 3) YD$ a) Find the first three terms. b) Calculate the sum of the first three terms. c) Calculate the sum of the terms when ������ = 5, … ,8. 3. Write the sequence below as summation of ������ terms using sigma notation. a) 2, 4, 6, 8, … b) 1, 8, 27, 64, … c) $ , & , ' , / , 0 , … / 4 $1 &0 '1 d) 1, −4, 9, −16, 25, −36, … 106
The Principle of Mathematical Induction Theorem 6.1 The Principle of Mathematical Induction Let ������(������) denote an open statement for the variable ������ which represents a positive integer. a) If ������(1) is true; and b) If ������(������) is true (for some integer ������ ∈ ℤ\"), then ������(������ + 1) is true; Therefore, ������(������) is true for all positive integers ������ ∈ ℤ\". By using the principle of mathematical induction, prove that for all ������ ∈ ℤ\" ) B(2������ − 1) = 1 + 3 + 5 + ⋯ + (2������ − 1) = ������& CD$ Proof: Let ������(������): 1 + 3 + 5 + ⋯ + (2������ − 1) = ������& 1. Verify that ������(1) is true. ������(1): 2(1) − 1 = (1)& ������������������: 2(1) − 1 = 1 ������������������: (1)& = 1 Since ������������������ = ������������������, then ������(1) is true. 2. Assume that ������(������) is true. ������(������): 1 + 3 + 5 + ⋯ + (2������ − 1) = ������& 3. Show that ������(������ + 1) is true. ������(������ + 1): 1 + 3 + 5 + ⋯ + (2������ − 1) + (2(������ + 1) − 1) = (������ + 1)& ������������������: (������ + 1)& = (������ + 1)(������ + 1) = ������& + 2������ + 1 107
������������������: 1 + 3 + 5 + ⋯ + (2������ − 1) + (2(������ + 1) − 1) = ������(������) + (2(������ + 1) − 1) = ������& + (2������ + 2 − 1) = ������& + 2������ + 1 Since ������������������ = ������������������, then ������(������ + 1) is true. Therefore, ������(������) is true for all positive integers ������ ∈ ℤ\". Important Steps to prove a mathematical conjecture or formula is true. 1. For ������ = 1, verify that ������(1) is true. 2. For ������ = ������, assume that ������(������) is true. 3. For ������ = ������ + 1, show that ������(������ + 1) is true. That is, show that ������(������ + 1) = ������(������) + ������Y\"$, where ������Y\"$ is the (������ + 1)-th term. 108
Show that the following formula is true for all positive integers ������ ≥ 1. ) ������ = ������(������ + 1) 2 B CD$ 109
Prove that for all positive integers ������, ) ������& = ������(������ + 1)(2������ + 1) 6 B CD$ 110
Use mathematical induction to prove that for all ������ ∈ ℤ\" ) ������(������ + 1) = ������(������ + 1)(������ + 2) 3 B CD$ 111
Prove the formula is true using mathematical induction. 1 3 + 1 + 1 + ⋯ + (2������ − 1 + 1) = ������ 1 1∙ 3∙5 5∙7 1)(2������ 2������ + 112
Use mathematical induction to prove that for all ������ ≥ ������, ������ ∈ ℤ\". ) = 3)\"$ − 1 2 B 3C CDL 113
Exercise 6.2 1. Use mathematical induction to prove that 2& + 4& + ⋯ + 4������& = 2������(������ + 1)(2������ + 1) , ∀������ ∈ ℤ\" 4 2. Let the summation of ������ terms defined as follows. a) For all ������ ∈ ℤ\", prove that ) B(4������ − 3) YD$ 1 + 5 + 9 + ⋯ + (4������ − 3) = 2������& − ������ b) Find the sum of the first 50 terms. 3. By induction method, show that the following statement is true. ) 3 ������(������ + 1) = 3 + 9 + ⋯ + 3 ������(������ + 1) = ������(������ + 1)(������ + 2) 2 2 2 B CD$ 4. Use the mathematical induction method to show that 1 + 8 + 27 + ⋯ + ������' = ������&(������ + 1)& 4 114
Recursion Definition 6.4 A recursive function is when the definition of the function refers to itself. Below are some examples of recursive definitions. 1. Consider the factorial function. a) If ������ = 0, then ������! = ������. b) If ������ > 0, then ������! = ������ ∙ (������ − 1)! List down the first seven terms. ������ = 0, 0! = 1 ������ = 1, 1! = 1 ∙ (1 − 1)! = 1 ∙ 0! = 1 ∙ 1 = 1 ������ = 2, 2! = 2 ∙ (2 − 1)! = 2 ∙ 1! = 2 ∙ 1 = 2 ������ = 3, 3! = 3 ∙ (3 − 1)! = 3 ∙ 2! = 3 ∙ 2 = 6 ������ = 4, 4! = 4 ∙ (4 − 1)! = 4 ∙ 3! = 4 ∙ 6 = 24 ������ = 5, 5! = 5 ∙ (5 − 1)! = 5 ∙ 4! = 5 ∙ 24 = 120 ������ = 6, 6! = 6 ∙ (6 − 1)! = 6 ∙ 5 = 6 ∙ 120 = 720 The definition of ������! is recursive because it refers to itself when it uses (������ − 1)! 2. The first six terms of the recursive definition, ������$ = 6, ������)\"$ = ������) + 5 for ������ ∈ ℤ\". ������ = 1, ������& = ������$ + 5 = 6 + 5 = 11 ������ = 2, ������' = ������& + 5 = 11 + 5 = 16 ������ = 3, ������/ = ������' + 5 = 16 + 5 = 21 ������ = 4, ������0 = ������/ + 5 = 21 + 5 = 26 ������ = 5, ������1 = ������0 + 5 = 26 + 5 = 31 ������ = 6, ������2 = ������1 + 5 = 31 + 5 = 36 115
3. Fibonacci sequence is an example of a recursively defined function. a) If ������ = 0 or ������ = 1, then ������) = ������. b) If ������ > 1, then ������) = ������)g& + ������)g$. List down the first seven terms. 4. Find the first six terms of the following recursive function. ������L = 1 ������)\"$ = ������) + ������ 1 2 , ∀������ ≥ 0, ������ ∈ ℤ + 116
Given the following formula of a sequence. ������) = −2������, ∀������ > 1, ������ ∈ ℤ a) List down the first five terms of the sequence. b) Give the recursive formula for the sequence. Find the recursive definition of the following sequences. a) 5, 8, 13, 20, 29, 40, … ������ ������������ Recursive formula 1 ������$ 5 ������$ + (2(1) + 1) ������& + (2(2) + 1) 2 ������& 8 5+3 ������$ + 3 ������' + (2(3) + 1) 8+5 ������& + 5 ������/ + (2(4) + 1) 3 ������' 13 13 + 7 ������' + 7 ������0 + (2(5) + 1) 20 +9 ������/ + 9 ������)g$ + (2������ + 1) 4 ������/ 20 29 +11 ������0 + 11 5 ������0 29 6 ������1 40 n ������) Recursive definition: ������$ = 5; ������) = ������)g$ + (2������ + 1) for ������ ≥ 2, ������ ∈ ℤ\". 117
b) 0.25, −0.5, 1, −2, 4, −8, … c) 2, 5, 26, 677, … d) 4, 10, 22, 46, 94, … 118
Given a recursive sequence. ������)\"$ = − 3 2 If ������/ = 10, find ������$. − 2������) Consider the recursive function defined as follows. ������) = 8������)g$ + 7������)g&, for integers ������ ≥ 2 If ������& = 70 and ������' = 609, calculate ������L and ������$. 119
Exercise 6.3 1. Given the recursive sequence ������$ = 4;������)\"$ = ������) + 2������ for ������ ∈ ℤ\" a) Find the first five terms. 0 b) Evaluate B ������Y YD$ 2. Let the sequence ������$, ������&, …, ������), ... be defined by ������$ = 1; ������& = 3; and for ������ ≥ 3, ������) = 3������)g$ − 2������)g& a) Find ������) for 3 ≤ ������ ≤ 6. b) Give the general formula for the term ������). 3. Let the recursive sequence be defined as ������L = 5; ������$ = 8; ������) = ������)g$ + 2������)g& + 1 for ������ ∈ ℤ\" Find ������1. 4. If ������) = (������)g$ + 2)& and ������/ = 228947161, find ������$. 5. Given the recursive formula below for ������ ≥ 2. ������C = ������Cg& − ������Cg$ ∙ ������Cg$ Given the initial values ������L = 1, ������$ = 0, find the value of ������&. 120
NOTES 121
NOTES 122
REFERENCES Kenneth H. Rosen (2007). Discrete Mathematics and Its Applications, 6th edition, McGraw Hill. Richard Johnsonbaugh (2005). Discrete Mathematics, 6th edition, Prentice Hall International Inc. Ralph P. Grimaldi (2004). Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition. Addison Wesley. Arsmah Ibrahim, Hamidah Maidinsah, Harbans Kaur Cheema, Nor Maizan Abdul Aziz (2001). Matematik Diskret Pra-Universiti, 2nd edition. McGraw-Hill (Malaysia) Sdn.Bhd. Nor Azizah M. Yacob, Yusarima Muhamad (2009). Discrete Mathematics MAT210, 4th edition. Universiti Teknologi MARA.
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