Discrete Mathematics Lecture Notes PDF

Discrete Mathematics Lecture Notes Raymond Calvin Mien April - July 2023 Institute of Mathematical Sciences, Strathmore University Expected Learning Outcomes ▶ By the end of the course, the learner shoul...

Discrete Mathematics Lecture Notes Raymond Calvin Mien April - July 2023 Institute of Mathematical Sciences, Strathmore University Expected Learning Outcomes ▶ By the end of the course, the learner should be in a position to: 1. Explain, solve and apply various aspects of logical relationships. 2. Explain and apply concepts of sets and relations in solving problems. 3. Apply properties of numbers, relations and functions in solving problems. 4. Explain and apply the principles of inclusion and exclusion. 5. Resolve the problems related to elementary graph theory. 1: Set Theory  Set Theory ▶ A set is a group of well defined collection of objects or numbers. ▶ Each object or number in a set is a member or element of the set. ▶ Sets are denoted by upper case letters while the elements of the set are denoted by lower case letters. ▶ Curl brackets i.e. {} are used to describe the contents of the set e.g. A = {a, b, c} N = {1, 2, 3, · · · , 9} a is an element of A ∴ a ∈ A x is not an element of A ∴ x ∈ /A Set Theory: Specifying a Set (a) List Notation ▶ The conventional way of specifying a set is to list its members in between curl brackets and separate each member with a comma e.g. set of currencies common in Kenya: C = {Kshs, USD, Euro, Pound} ▶ The order in which they are listed is irrelevant i.e.. C = {USD, Kshs, Euro, Pound} C = {Pound, USD, Euro, Kshs} C = {Euro, Kshs, USD, Pound} ▶ All the above listed sets are one and the same thing. Specifying a Set contd... (b) Predicate Notation ▶ Mainly used when we do not know the complete membership of the set. ▶ A set is specified by indicating the condition that they all meet e.g. A = {x x is any natural number } K = {k : k is any currency used in the world} C = {c : c is any computer brand} where the notation ( ) and ( : ) denotes “such that” Set Theory: Definition of Terms ▶ Singleton Set: is a set having only one element e.g. set K of Kenyan currency is the shilling i.e. K = {shilling } ▶ Empty/Null Set: is a set with no element. - It’s denoted by ∅ or {}. - Formally: ∅ = {x x ∈ / x} ▶ Subset of a set: Subset A of a set B is such that every element of A is also an element of B e.g. ▶ B = {a, b, c, d, e, f , g } ▶ A = {b, e, g } ▶ ∴ A is a subset of B i.e. A ⊆ B or B ⊇ A. ▶ Proper Subset: If A is a subset of B and A is not equal to B, we call A a proper subset of B i.e. A ⊂ B Set Theory: Definition of Terms contd... ▶ Equal/Identical Sets: Two sets A and B are said to be equal if and only if they have exactly the same elements i.e. every element of A is an element of B and vice versa. e.g. (i) {x, y } = {y , x} (ii) {x, x} = {x} (iii) If A = {a, b, c}, then A = {a, b, a, c} A = {b, c, a, b, c} i.e all these sets in (iii) are equal. ▶ However, {x 3 } ≠ {x}. Remarks: 1. A = B if and only if A ⊆ B and B ⊆ A. 2. An empty set is a subset of every set. Set Theory: Definition of Terms contd... ▶ A Venn Diagram: is a family of simple closed curves (circles or ellipses) arranged in a plane so that all possible intersections of the interiors are non-empty and connected. ▶ Let A = {Dell, Acer , Hp, Compaq, Lenovo} B = {Samsung , Acer , Sony , Hp, IDM} ▶ The intersection is Acer and Hp i.e Set Theory: Definition of Terms contd... ▶ Universal Set: Is the set that contains all sets under consideration in a certain study. - It’s denoted by ∪ or Ω. - The rectangle of a Venn diagram represents a universal set. ▶ Power Set: A set of all subsets of a set A denoted by P(A) e.g. P(A) = {a, b, c} is given by n o P(A) = ∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, A Set Theory: Definition of Terms contd... Exercise: Find the power set of B = {Dell, Hp, Acer , IDM} Note: The number of elements of a power set is given by: 2|A| , where |A| is the number of elements of set A. ▶ Cardinality of a Set: The number of elements of a set A is called the cardinality of A denoted by |A| or n(A) e.g. (i) Cardinality of S, a singleton is : |S| = 1 or n(S) = 1. (ii) Cardinality of a null set is 0, i.e n(∅) = 0 or |∅| = 0 (iii) If S is an infinite set, its cardinality will be: n(S) = ∞ or |S| = ∞ Set Theory: Definition of Terms contd... ▶ Disjointed Sets: Any two sets are said to be disjointed if they have no common elements. ▶ Partition of a Set: Let S = Φ. ▶ The partition of S is a subdivision of S into non-overlapping and non-empty subsets i.e. the union, (∪), of the elements of the partition is equal to S and the intersection, (∩), of any two elements of the partition is empty. Set Theory: Definition of Terms contd... Example 1: A = {a, b, c} can be partitioned in 5 ways as follows: 1. [{a, b, c}] 2. [{a}, {b, c}] 3. [{b}, {a, c}] 4. [{c}, {a, b}] 5. [{a}, {b}, {c}] Set Theory: Definition of Terms contd... Example 2: Consider the subset of S given by S = {1, 2, 3, · · · , 9}. (a) [{1, 3, 5}, {2, 6}, {4, 8, 9}] is not a partition of S since 7 ∈ S but not in the partition. (b) [{1, 3, 5}, {2, 4, 6, 8}, {5, 7, 9}] is not a partition of S since [{1, 3, 5} and {5, 7, 9}] are not disjoint. (c) [{1, 3, 5}, {2, 4, 6, 8}, {7, 9}] is a partition of S since (i) The union {1, 3, 5} ∪ {2, 4, 6, 8} ∪ {7, 9} = S (ii) {1, 3, 5} ∩ {2, 4, 6, 8} = ∅ {1, 3, 5} ∩ {7, 9} = ∅ {2, 4, 6, 8} ∩ {7, 9} = ∅ ∴ [{1, 3, 5}, {2, 4, 6, 8}, {7, 9}] is a partition of S. Set Theory: Definition of Terms contd... Set Operations ▶ Union of Sets: Let A and B be any two arbitrary sets, then: ▶ Union of A and B denoted by A ∪ B is the set whose elements are the elements of A or B or both, i.e. n o A ∪ B = x x ∈ A or x ∈ B for all x ▶ Let K = {a, b}, L = {c, d} and M = {b, d}; then K ∪ M = {a, b, d} K ∪ L = {a, b, c, d} L ∪ M = {b, c, d} Set Theory: Definition of Terms contd... ▶ Intersection of Sets: ▶ The intersection of A and B denoted by A ∩ B is the set whose elements are just the elements common to both A and B i.e. n o A ∩ B = x x ∈ A and x ∈ B for all x ▶ Let K = {a, b}, L = {c, d} and M = {b, d}; then K ∩L=∅ M ∩ L = {d} K ∩ M = {b} Set Theory: Definition of Terms contd... ▶ Complement of a Set: Let A be a subset or a universal set. ▶ The complement of A is the set of all elements in the universal set that are not elements of A. ▶ It’s denoted by Ac , Ā or A′ ▶ It’s expressed as n o Ac = x x ∈ ∪ and x ∈ /A ▶ Suppose S = {1, 2, 3, · · · , 9} and A = {1, 2, 9} then Ac = {3, 4, 5, 6, 7, 8} Set Theory: Definition of Terms contd... ▶ Set Difference: The set difference of A and B denoted by A − B or (A/B) is the set of all elements of A which do not belong to B i.e. n o A/B = A − B = x x ∈ A but x ∈ /B n o B/A = B − A = x x ∈ B but x ∈ /A ▶ E.g. let K = {a, b}, L = {c, d}, M = {b, d}, then K − L = {a, b} K − M = {a} L − K = {c, d} L − M = {c} M − K = {d} M − L = {b} ▶ For any distinct sets A and B: A − B ̸= B − A. Set Theory: Definition of Terms contd... ▶ Symmetric Difference: The symmetric difference of the sets A and B, denoted by A∆B or A ⊕ B is defined by n o A ⊕ B = A∆B = x [x ∈ (A − B)] ∪ [x ∈ (B − A)] ▶ E.g. using the examples from the set difference above: ▶ K − M = {a} M − K = {d} ▶ ∴ n o n o K ⊕ M = (K − M) ∪ (M − K ) = {a} ∪ {d} = {a, d} Set Theory contd... Theorem ▶ Let A, B and C be any finite sets: (i) |A ∪ B| = |A| + |B| − |A ∩ B| (ii) |A ∪ B| = |A| + |B| if and only if A and B are disjointed sets i.e. |A ∩ B| = |∅| = 0 (iii) |A ∪ B ∪ C | = |A| + |B| + |C | − |A ∩ B| − |A ∩ C | − |B ∩ C | + |A ∩ B ∩ C | Example 1: Let A = {a, b, c}, B = {1, 2, 3, 4}, then |A| = 3, |B| = 4 A ∪ B = {a, b, c, 1, 2, 3, 4} ∴ |A ∪ B| = 7 = 3 + 4 = |A| + |B| Set Theory contd... Example 2: In a group of 60 customers, 27 prefer to pay by cash and 42 prefer cashless payment. If each customer prefers atleast one of the two modes of payments, how many like both modes of payment? Solution: Let A = set of customers that prefer paying cash Let B = set of customers that prefer cashless |A| = 27, |B| = 42, |A ∪ B| = 60 |A ∪ B| = |A| + |B| − |A ∩ B| =⇒ 60 = 27 + 42 − |A ∩ B| =⇒ |A ∩ B| = 9 Set Theory contd... Example 3: A survey has been conducted on methods of commuter travel. Each respondent was asked to choose a bus, train or car as the means of travelling to work. More than one answer was permitted and the following results were reported. Bus (B) = 30, Train (T) = 35, Car (C) = 100, Bus and Train = 15, Bus and Car = 15, Train and Car = 20, All three methods = 5 How many people completed the survey form? Set Theory contd... Solution: B → set of bus commuters T → set of train commuters C → set of car commuters |B| = 30, |T | = 35, |C | = 100, |B ∩ T | = 15, |B ∩ C | = 15, |T ∩ C | = 20, |B ∩ T ∩ C | = 5 |B ∪ T ∪ C | =? |B ∪ T ∪ C | = |B| + |T | + |C | − |B ∩ C | − |T ∩ C | − |B ∩ T | + |B ∩ T ∩ C | = 50 + 35 + 100 − 15 − 15 − 20 + 5 = 120 Set Theory contd... Solution contd...: ▶ B & T excluding C = 15-5=10 ▶ T & C excluding B = 20-5=15 ▶ B & C excluding T = 15-5=10 ▶ B excluding C & T = 30-(10+5+10)=5 ▶ T excluding B & C = 35-(10+5+15)=5 ▶ C excluding B & T = 100-(15+5+10)=70 Set Theory contd... Example 4: A survey on a sample of 25 new cars sold by a local dealer was conducted to see which of the popular options air conditioning (A), radio (R) and power windows (W) were already installed. The survey found that 15 had A, 12 had R, 5 had A & W, 9 had A & R, 4 had R & W, 3 had A, R & W while 2 had none. (i) Find the number of cars that had: (a) Only power windows (W) (b) Only air conditioning (A) (c) Only radio (R) (d) Radio and power windows (R & W) but no air conditioning (A) (e) Air conditioning and radio (A & R) but no power windows (W) (f) Only one of the three options. Set Theory contd... Example 5 contd..: (ii) If a car that has none of the options is sold at Kshs. 0.7M, one that has only one option is sold at Kshs. 0.9M, two options installed is sold at Kshs. 1.2M and all the three options installed sold at Kshs. 1.8M, find the total cost if all the 25 cars are sold. Set Theory contd... Solution (i): Total =25, |A| = 15, |R| = 12, |A ∩ W | = 5, |A ∩ R| = 9, |R ∩ W | = 4, |A ∩ R ∩ W | = 3, |A ∪ R ∪ W | = 25 − 2 = 23 Set Theory contd... Solution contd...(i): A&W excluding R = 5 − 3 = 2 A&R excluding W = 9 − 3 = 6 R&W excluding A = 4 − 3 = 1 A excluding R&W = 15 − (6 + 3 + 2) = 4 R excluding A&W = 12 − (6 + 3 + 1) = 2 W excluding R&A = 23 − (4 + 6 + 2 + 2 + 3 + 1) = 5 Only one of the 3 = 4 + 2 + 5 = 11 Solution (ii): Total sales = (2 × 0.7) + (11 × 0.9) + (9 × 1.2) + (3 × 1.8) = 1.4 + 9.9 + 10.8 + 5.4 = 27.5M Set Theory contd... Exercises Exercise 1: In a survey of 260 college students, the following data was obtained: 64 are doing a Mathematics course, 94 are pursuing Computer Science course, 58 are doing Bachelor of Education course, 28 both Mathematics and Bachelor of Education, 26 both Mathematics and Computer Science course, 22 both Computer Science and Bachelor of Education while 14 are doing all the three courses. (a) How many students were surveyed who had taken none of the three types of courses. (106) (b) Of the students surveyed, how many had taken only one type of course. (106) (c) Represent the information in a Venn diagram. Set Theory contd... Exercises Exercise 2: An IT department hires 25 programmers to handle system programming jobs and 40 programmers for applications programming. Of those hired, 10 will be expected to perform jobs on both types. How many programmers must be hired? Exercise 3: A survey of 500 internet users produced the following information: 285 visit soccer sites, 195 visit hockey sites, and 115 visit national geographic sites (natgeo), 45 visit both soccer and natgeo, 70 visit both soccer and hockey sites, 50 visit botj hockey and natgeo sites while 50 do not visit any of the three sites. (a) How many people in the survey visit all the three sites? (20) (b) How many visit exactly one site? (330) (c) Represent the information on a Venn diagram Set Theory contd... Exercises Exercise 4: In a survey of 60 people, it was found that 25 read Daily Nation online, 26 read Standard online and 26 read Parents Magazine online, 9 read both Daily Nation and Parents Magazine, 11 read both Daily Nation and Standard online, 8 read both Standard online and Parents Magazine, and 8 do not read any of the three. (a) Find the number of people who read all the three newspapers online. (3) (b) Represent the information on a Venn diagram (c) Find the number of people who read exactly two of the three papers. (19) (d) Determine the number of people who read exactly one of the three papers. (30) Set Theory contd... Exercises Exercise 5: There are 35 students in an art class and 57 in a science class. Find the number of students who are either in the art class or science class when: (i) the two classes meet at different hours and 12 students are enrolled in both classes. (ii) The two classes meet at the same hour. Set Theory contd... Solutions to Exercises Exercise 1 |M| = 64, |C | = 94, |B| = 58, |M ∩ B| = 26, |M ∩ C | = 26, |C ∩ B| = 22, |M ∩ C ∩ B| = 14 M ∪ C ∪ B = 64 + 94 + 58 − 26 − 26 − 22 + 14 = 154 =⇒ 260 − 154 = 106 Set Theory contd... Solutions to Exercises Exercise 2 S → Systems programmer A → Applications programmer |S| = 25, |A| = 40, |S ∩ A| = 10 |S ∪ A| = |S| + |A| − |S ∩ A| =⇒ 25 + 40 − 10 = 55 Set Theory contd... Solutions to Exercises Exercise 3 |S| = 285, |H| = 195, |N| = 115, |S ∩ N| = 45, |S ∩ H| = 70, |H ∩ N| = 50, |S ∪H ∪N| = |S|+|H|+|N|−|S ∩N|−|S ∩H|−|H ∩N|+|S ∩H ∩N| 500 = 285 + 195 + 115 − 45 − 70 − 50 + x ∗ =⇒ x ∗ = 70 ∴ x = x ∗ − 50 =⇒ x = 20 Set Theory contd... Solutions to Exercises Exercise 4 |D| = 25, |S| = 26, |P| = 26, |D ∩ P| = 9, |D ∩ S| = 11, |S ∩ P| = 8, |D ∪S ∪P| = |D|+|S|+|P|−|D ∩P|−|D ∩S|−|S ∩P|+|D ∩S ∩P| 60 = 25 + 26 + 26 − 9 − 11 − 8 + x ∗ =⇒ x ∗ = 60 − 49 = 11 ∴ x = x ∗ − 8 =⇒ x = 3 Set Theory contd... Exercise 5: Solution (i): |A ∪ B|?, |A ∩ B| = 12, |A| = 35, |B| = 57, |A ∪ B| = |A| + |B| − |A ∩ B| |A ∪ B| = 35 + 57 − 12 ∴ |A ∪ B| = 80 Solution (ii): |A ∪ B| = |A| + |B| =⇒ |A ∪ B| = 35 + 57 = 92 Note: When the students meet at the same hour, A ∩ B = ∅ i.e. |A ∩ B| = 0 2: Real Numbers  Real Numbers The following are the classifications of subsets of real numbers: ▶ Natural Numbers (N): They are known as counting numbers. N = {1, 2, 3, · · · , ∞}. ▶ Whole Numbers (W): W = {0, 1, 2, 3, · · · , ∞}. ▶ Integers (Z): These are whole numbers together with the negatives of natural numbers i.e. Z = {−∞, · · · , −2, −1, 0, 1, 2, 3, · · · , ∞}. Real Numbers contd... ▶ Rational Numbers (Q): Refers to any number which can be expressed in the form pq where p, q ∈ Z and q ̸= 0. ▶ They can be expressed as fractions ▶ Integers are rational numbers e.g. −3 = −3 2 0 1 , 2 = 1, 0 = 1. ▶ Terminating decimals can be expressed as rational numbers 125 e.g. 1.5 = 32 , 0.125 = 1000 = 18 , 211386 105693 2.11386 = 100,000 = 50,000 Real Numbers contd... ▶ Rational Numbers (Q) contd...: ▶ Repeating / Recurring decimals e.g. (a) 0.6. Let x = 0.6 = 0.666 · · · =⇒ 10x = 6.666 6 2 =⇒ 10x − x = 6.666 − 0.666 =⇒ 9x = 6 =⇒ x = 9 = 3 (b) 0.47. Let x = 0.47 = 0.4777 · · · =⇒ 10x = 4.777 =⇒ 100x = 47.777 =⇒ 100x − 10x = 47.777 − 4.77 =⇒ x = 43 90 (c) 0.2 3. Let x = 0.232323 · · · =⇒ 10x = 2.32323 =⇒ 100x = 23.2323 =⇒ 100x − x = 23.2323 − 0.2323 =⇒ x = 23 99 Real Numbers contd... Exercise A businessman rounds off his increase in sales of 0.3 to 0.3. Calculate the percentage error in this rounding off. Solution: 0.3 = 0.333 =⇒ x = 0.333 =⇒ 10x = 3.33 =⇒ x = 13 3 0.3 = 10 , 1 3 1 Error = 3 − 30 = 30 , 1 1 % Error = 30 ÷ 3 × 100 = 10% Real Numbers contd... ▶ Irrational Numbers (II): A number which cannot be expressed as a rational number i.e. in the form pq where p, q ∈ √ Z and q ̸= 0 e.g. π, 2 ▶ Include decimals which neither terminate nor recur e.g. √ e 1 = 2.718 · · · , π = 3.14157 · · · , 2 = √ 1.414 · · · i.e. any root of a number which is not rational i.e. n r ̸= pq for n, p, q, r ∈ Z. Real Numbers contd... ▶ Real Numbers (R): Set of rational numbers + irrational numbers i.e. ▶ R = Q ∪ II ▶ N⊆R ▶ W⊆R ▶ Z⊆R ▶ Q⊆R ▶ II ⊆ R ▶ Q ⊈ II ▶ N⊆W⊆Z⊆Q⊆R ▶ Intersections: ▶ N∩W=N ▶ Z∩Q=Z ▶ Q∩R=Q 3: Fundamentals of Logic  Fundamentals of Logic ▶ Mathematical logic is a kind of language where everything is designed to have a precise meaning i.e. the language of unambiguous reasoning. ▶ Logics come into computer science in many different ways: (i) Digital circuit logic (ii) Proofs of correctness of programs, verification (iii) Automated reasoning in artificial intelligence (iv) Database query languages Logics ▶ Mathematics is about statements which are either True or False. Propositions ▶ A mathematical statement that is either True or False is called a proposition. Consider: 1. Nairobi is the capital of Kenya 2. 5 + 9 = 26 3. What time is it? ▶ The first statement is True, the second statement is False while the third one is neither True nor False. Fundamentals of Logic contd... ▶ A proposition is expressed as a declarative sentence (as opposed to a question or a command). ▶ Propositions are the basic building blocks of any theory of logic. ▶ True or False are referred to as the truth values of a proposition. Logical Connectives (a) Conjunction: ▶ Let p and q be propositions. ▶ The conjunction of p and q denoted by p ∧ q is a proposition p and q that is true when both p and q are true and false otherwise. ▶ This can be represented using a truth table: p q p∧q T T T T F F F T F F F F Logical Connectives contd... (b) Disjunction: ▶ The disjunction of any two propositions p and q is the proposition denoted by p ∨ q that is false when both p and q are false and true otherwise. ▶ On a truth table, this is given by: p q p∨q T T T T F T F T T F F F Logical Connectives contd... (c) Negation: ▶ Let p be a proposition. ▶ Negation of p denoted by ¬p or ∼ p is the proposition ‘not p’. ▶ The truth value for ‘not p’ is defined by: p ¬p T F F T Logical Connectives contd... (d) Exclusive or ⊕: ▶ Let p and q be propositions. ▶ The ‘exclusive or’ of p and q denoted p ⊕ q is the proposition that is true when exactly one of p and q is true and is false otherwise. ▶ The truth values for these are given by: p q p⊕q T T F T F T F T T F F F Logical Connectives contd... (e) Conditional (a.k.a implication i.e. p implies q): ▶ Let p and q be propositions. ▶ The conditional statement denoted by p → q is the proposition “if p then q”, that is false when p is true and q is false and true otherwise. ▶ This can be represented in a truth table as follows: p q p→q T T T T F F F T T F F T Logical Connectives contd... Example of a Conditional (Implication) Statement: John will pass Discrete Maths if he revises. ▶ p : John revises ▶ q : John passes ▶ p → q i.e. ▶ If John revises, then he will pass: T ▶ If John revises, he will fail: F. ▶ If John doesn’t revise, he will pass: F. ▶ If John doesn’t revise, he will fail: T. ▶ The statement p → q is a conditional statement because p → q asserts that q is True on the condition that p holds i.e. p is defined. Logical Connectives contd... Remarks: Converse, Contrapositive and Inverse Statements: ▶ Some new conditional statements can be formed starting with a conditional statement, p → q. ▶ In particular, there are three related conditional statements that occur so often and are defined as follows: If p → q, then ▶ The proposition q → p is called the converse of p → q. ▶ The contrapositive of p → q is the proposition ¬q → ¬p. ▶ The proposition ¬p → ¬q is called the inverse of p → q. Logical Connectives contd... (f) Bi-conditional Statements: ▶ Let p and q be propositions. ▶ The bi-conditional statement denoted by p ↔ q is a proposition “p if and only if (iff) q”, that is true when both p and q have the same truth values and false otherwise. ▶ Bi-conditional statements are also called bi-implications. ▶ This can be represented in a truth table as follows: p q p↔q T T T T F F F T F F F T Truth Tables for Compound Propositions Example 1: Construct a truth table for the following compound proposition: (p ∨ ¬q) → (p ∧ q) Solution: p q ¬q (p ∨ ¬q) (p ∧ q) (p ∨ ¬q) → (p ∧ q) T T F T T T T F T T F F F T F F F T F F T T F F Truth Tables for Compound Propositions contd... Example 2: Construct a truth table for the following compound proposition: (p ∨ q) ⊕ (p ∧ q) Solution: p q (p ∨ q) (p ∧ q) (p ∨ q) ⊕ (p ∧ q) T T T T F T F T F T F T T F T F F F F F Truth Tables for Compound Propositions contd... Example 3: Construct a truth table for the following compound proposition: (p ↔ q) ⊕ (¬p → ¬r ) Solution: Let (∗) = (p ↔ q) ⊕ (¬p → ¬r ) p q r (p ↔ q) ¬p ¬r (¬p → ¬r ) (∗) T T T T F F T F T T F T F T T F T F T F F F T T F T T F T F F F T F F F F T T T F T F F T T T T F F T T T F F T F F F T T T T F Compound Propositions contd... Tautology: ▶ Is a compound proposition that is always true no matter what the truth values of the propositions occur in it. ▶ A compound proposition that is always false is called a contradiction. ▶ A compound proposition that is neither a tautology nor a contradiction is called a contingency. Tautology contd... Example 1: Show that the following compound proposition is a tautology using a truth table. [p ∧ (p → q)] → q Solution: p q (p → q) p ∧ (p → q) [p ∧ (p → q)] → q T T T T T T F F F T F T T F T F F T F T ∴ [p ∧ (p → q)] → q is a tautology Exercises Show that the following compound propositions form a tautology. 1. [¬p ∧ (p ∨ q)] → q 2. [(p → q) ∧ (q → r )] → (p → r ) 3. [(p ∨ q) ∧ (p → r ) ∧ (q → r )] → r Solutions Solution (1): [¬p ∧ (p ∨ q)] → q p q ¬p (p ∨ q) [¬p ∧ (p ∨ q)] [¬p ∧ (p ∨ q)] → q T T F T F T T F F T F T F T T T T T FT F T F F T Solutions contd... Solution (2): [(p → q) ∧ (q → r )] → (p → r ) Let (∗) = [(p → q) ∧ (q → r )] (6th column) Let (∗∗) = [(p → q) ∧ (q → r )] → (p → r ) (last column) p q r (p → q) (q → r ) (∗) (p → r ) (∗∗) T T T T T T T T T T F T F F F T T F T F T F T T F T T T T T T T T F F F T F T T F T F T F F T T F F T T T T T T F F F T T T F T Solutions contd... Solution (3): [(p ∨ q) ∧ (p → r ) ∧ (q → r )] → r Let ∗ = (p ∨ q) ∧ (p → r ) (6th column) Let (∗∗) = [(p ∨ q) ∧ (p → r )] ∧ (q → r ) (8th column) Let (∗ ∗ ∗) = [(p ∨ q) ∧ (p → r ) ∧ (q → r )] → r (last column) p q r (p ∨ q) (p → r ) (∗) (q → r ) (∗∗) (∗ ∗ ∗) T T T T T T T T T T T F T F F F F T T F T T T T T T T F T T T T T T T T T F F T F F T F T F T F T T T F F T F F T F T F T F T F F F F T F T F T Logical Equivalence Definitions: 1. Compound propositions that have the same truth values in all possible cases are called logically equivalent. 2. The compound proposition p and q are logically equivalent if the bi-conditional p ↔ q is a tautology. 3. The notations p ≡ q or (⇐⇒) denotes that p and q are logically equivalent. Logical Equivalence... Examples Example 1: Show that ¬(p ∨ q) and ¬p ∧ ¬q are logically equivalent. Solution: p q (p ∨ q) ¬(p ∨ q) ¬p ¬q ¬p ∧ ¬q T T T F F F F T F T F F T F F T T F T F F F F F T T T T ▶ ∴ ¬(p ∨ q) and ¬p ∧ ¬q are logically equivalent. ▶ Or ¬(p ∨ q) ≡ ¬p ∨ ¬q ▶ Or ¬(p ∨ q) ⇐⇒ ¬p ∨ ¬q Examples contd... Show that the following compound propositions are logically equivalent. (a): (p → q) ∧ (p → r ) ≡ p → (q ∧ r ) Let (∗) = (p → q) ∧ (p → r ) (6th column) Let (∗∗) = p → (q ∧ r ) (last column) p q r (p → q) (p → r ) (∗) (q → r ) (∗∗) T T T T T T T T T T F T F F F F T F T F T F F F F T T T T T T T T F F F F F F F F T F T T T F T F F T T T T F T F F F T T T F T ▶ ∴ (p → q) ∧ (p → r ) ≡ p → (q ∧ r ) Examples contd... (b): p ∨ (q ∧ r ) ≡ (p ∨ q) ∧ (p ∨ r ) Let (∗) = (p ∨ q) ∧ (p ∨ r ) (last column) p q r (q ∧ r ) p ∨ (q ∧ r ) (p ∨ q) (p ∨ r ) (∗) T T T T T T T T T T F F T T T T T F T F T T T T F T T T T T T T T F F F T T T T F T F F F T F F F F T F F F T F F F F F F F F F ▶ ∴ p ∨ (q ∧ r ) ≡ (p ∨ q) ∧ (p ∨ r ) Logically Equivalent Laws 1. Identity Law. ▶ For any proposition p: p∧T ≡p p∨F ≡p 2. Domination Laws: p∨T ≡T p∧F ≡F 3. Idempotent Laws: p∨p ≡p p∧p ≡p 4. Double Negation Laws: (¬p) ≡ p Logically Equivalent Laws contd... 5. Commutative Laws. p∧q ≡q∧p p∨q ≡q∨p 6. Associative Laws. p ∨ (q ∨ r ) ≡ (p ∨ q) ∨ r p ∧ (q ∧ r ) ≡ (p ∧ q) ∧ r 7. Distributive Laws. p ∨ (q ∧ r ) ≡ (p ∨ q) ∧ (p ∨ r ) p ∧ (q ∨ r ) ≡ (p ∧ q) ∨ (p ∧ r ) 8. De Morgan’s Laws. ¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q Logically Equivalent Laws contd... 9. Absorption Laws. p ∨ (p ∧ q) ≡ p p ∧ (p ∨ q) ≡ p 10. Negation Laws. p ∨ ¬p ≡ T p ∧ ¬p ≡ F Exercise: Show the laws using truth tables Logic and Bit Operations ▶ Computers represent information using bits. ▶ A bit is a symbol with two possible values i.e. 0 (zero) and 1 (one). ▶ A bit can be used to represent a truth value i.e. 1 represents true (T) and 0 represents false (F). ▶ The variable is called a Boolean variable if its value is either T or F and consequently it can be represented using bits. ▶ Computer bit operations correspond to the logical connectives: ∧, ∨ and ⊕ which are notations for AND, OR and XOR respectively. Logic and Bit Operations contd... Bit String: ▶ Is a sequence of 0 or more bits. ▶ The length of this string is the number of bits in the string. ▶ Example: 101011001 is a bit string of length 9. Bit Operations: bitwise OR bitwise AND bitwise XOR x y x ∨y x ∧y x ⊕y 1 1 1 1 0 1 0 1 0 1 0 1 1 0 1 0 0 0 0 0 Logic and Bit Operations contd... Operations on a bit string Consider the following bit strings: 1. 0110110110 and 1100011101. Then, 0110110110 1100011101 1110111111 bitwise OR 0100010100 bitwise AND 1010101011 bitwise XOR Logic and Bit Operations contd... 2. Find the bitwise OR, bitwise AND and bitwise XOR in each of the following cases: (a) 101 1110; 010 0001 (b) 11 1111 1111; 00 0000 0000 Solution (a): 101 1110 010 0001 111 1111 bitwise OR 000 0000 bitwise AND 111 1111 bitwise XOR Solution (b): 11 1111 1111 00 0000 0000 11 1111 1111 bitwise OR 00 0000 0000 bitwise AND 11 1111 1111 bitwise XOR Logic and Bit Operations contd...Exercises 1. Find the bitwise OR, bitwise XOR and bitwise AND in: (a) 1111 0000; 1010 1010 (b) 00 01 11 0001; 10 0100 1000 2. Evaluate each of the following: (a) 11000 ∧ (01011 ∨ 11011) (b) (01111 ∧ 10101) ∨ 01000 (c) (01010 ⊕ 11011) ⊕ 01000 (d) (11011 ∨ 01010) ∧ (10001 ∨ 11011) Logic and Bit Operations contd...Solutions Exercise 1: Solution (a): 1111 0000 1010 1010 1111 1010 bitwise OR 1010 0000 bitwise AND 0101 1010 bitwise XOR Solution (b): 00 01 11 0001 10 01 00 1000 10 01 11 1001 bitwise OR 00 01 00 0000 bitwise AND 10 00 11 1001 bitwise XOR Logic and Bit Operations contd...Solutions Exercise 2: Solution (a): 01011 11011 11011 bitwise OR 11000 11000 bitwise AND Solution (b): 01111 10101 00101 bitwise AND 01000 01101 bitwise OR Logic and Bit Operations contd...Solutions Exercise 2: Solution (c): 01010 11011 10001 bitwise XOR 01000 11001 bitwise XOR Solution (d): 11011 01010 11011 · · · ∗ 10001 11011 11011 · · · ∗ ∗ bitwise OR 11011 · · · ∗ 11011 · · · ∗ ∗ 11011 bitwise AND Predicates and Quantifiers Predicates: ▶ Statements involving variables such as: x > 3, x = y + 3, x + y = z are often found in mathematical assertions and computer programs. ▶ These statements are neither true nor false when the values of the variables are not specified. ▶ Consider the statement “x greater than 3”. It has two parts: ▶ First part: the variable x, called the subject of the statement ▶ Second part: greater than 3, called the predicate and it refers to the property that the subject of the statement can have. Predicates contd... ▶ We denote the statement “x greater than 3” by P(x) where P denotes the predicate “greater than 3” and x is the variable. ▶ The statement P(x) is said to be the value of the propositional function P at x. Once a value has been assigned to the variable, the statement P(x) becomes a proposition and hence has a truth value. Predicates contd... Example 1: Consider P(x) : x > 3 What are the truth values for P(4) and P(2). Solution: P(x) : x > 3 P(4) : 4 > 3 which is True (T) P(2) : 2 > 3 which is False (F) Example 2: Let Q(x, y ) be the statement x = y + 3. Find the truth values for: (a) Q(5, 2) =⇒ 5 = 2 + 3 → T (b) Q(3, −3) =⇒ 3 = −3 + 3 → F (c) Q(0, −3) =⇒ 0 = −3 + 3 → T Predicates contd...Exercise Exercise: Let R(x, y , z) : x + y = z Find the truth values for: (a) R(1, 2, 3) (b) R(0, 0, 1) Predicates contd... ▶ In general, a statement involving n variables x1 , x2 , x3 , · · · , xn can be checked by P(x1 , x2 , x3 , · · · , xn ). ▶ A statement of the form P(x1 , x2 , x3 , · · · , xn ) is the value of the proposition function P at the n − tuple (x1 , x2 , x3 , · · · , xn ) and P is called a predicate. ▶ Propositional functions occur in computer programs as demonstrated by the following examples: Predicates contd... Consider the statement if x > 0, then x := x + 1 ▶ When this statement is encountered in a program, the value of the variable x at that point of execution of the program is inserted into P(x) which is “x > 0” ▶ If P(x) is true for this value of x the assignment statement x := x + 1 is executed so that the value of x is increased by 1. ▶ If P(x) is false for a given value of x, the assignment statement is not executed ∴ the value of x is not changed. Quantifiers contd... ▶ When all variables in a propositional function are assigned values, the resulting statement has a truth value. ▶ However, there is another way i.e. quantification to create a proposition from a propositional function. ▶ This can be done in two ways i.e. 1. Universal quantification 2. Existential quantification Quantifiers contd... ▶ Mathematical statements assert that a property is true for all values of a variable in a particular domain called the universe of discourse. ▶ Such a statement is expressed using a universal quantification i.e. the universal quantification of a propositional function is the proposition that asserts that P(x) is T for all values of x in the universe of discourse. ▶ The universe of discourse specifies the possible values of the variable. Quantifiers contd...Definition Universal Quantification: ▶ The universal quantification of P(x) is the proposition P(x) T for all values of x in the universe of discourse. ▶ The notation ∀x P(x) denotes the universal quantification of P(x) where ∀ is a universal quantifier. ▶ ∀x P(x) is expressed as: “for all x P(x)” or “for every x P(x)” Universal Quantification contd...Examples Example 1: Express the statement “every student in this class has studied computer programming” as a universal quantification. Solution: ▶ Let P(x) denote the statement “ x has studied computer programming”. ▶ ∴ the statement “every student in this class has studied computer programming” can be written as ∀x P(x). ▶ Alternatively, the statement can be expressed as ∀x(s(x)) → P(x), where ▶ s(x) refers to x in this class. ▶ P(x) refers to x has studied computer programming. Universal Quantification contd...Examples Example 2: Let P(x) be the statement “x + 1 > x”. What is the truth value of the quantification ∀x P(x)? where the universe of discourse is the set of real numbers. Solution: - Since P(x) is T for all real numbers, x, the quantification ∀x P(x) is T. Remark: When all the elements in the universe of discourse can be listed as x1 , x2 , x3 , · · · , xn , then it follows that the universal quantification ∀x P(x) is the same as the conjunction P(x1 ) ∧ P(x2 ) ∧ · · · ∧ P(xn ) since this conjunction is true if and only if P(x1 ), P(x2 ), P(x3 ), · · · , P(xn ) are all true. Universal Quantification contd... Example: What is the truth value of ∀x P(x) where P(x) is the statement “x 2 < 10” and the universe of discourse consists of positive integers not exceeding 4? Solution: ▶ The statement ∀x P(x) is the same as the conjunction P(1) ∧ P(2) ∧ P(3) ∧ P(3) ∧ P(4) since the universe of discourse is {1, 2, 3, 4}. ▶ Since P(4) which is 42 < 10 is false (F), it follows that ∀x P(x) is False. Quantifiers contd... Existential Quantification: ▶ Some mathematical statements assert that there is an element with a certain property. ▶ Such statements are expressed using the existential quantification. In this case, we form a proposition that is true if and only if P(x) is true for at least 1 value of x in the universe of discourse. Definition: The existential quantification of P(x) is the proposition “there exists an element x in the universe of discourse such that P(x) is true” ▶ Notation: ∃ x P(x), where ∃ is the existential quantifier. Existential Quantification contd...Examples Example 1: Let P(x) denote the statement “x > 3′′. What is the truth value of the quantification ∃ x P(x) where the universe of discourse is a set of real numbers? Solution: ▶ Let x = 4, then 4 > 3 which is true, T. ▶ ∴ ∃ x P(x) is true, T. Existential Quantification contd...Examples Example 2: Let Q(x) denote the statement “x = x + 1′′. What is the truth value of the quantification ∃ x Q(x) where the universe of discourse is a set of real numbers? Solution: ▶ Let x ∈ R ∀x, ▶ Q(x) is False ∀x ∈ R ▶ ∴ ∃ x Q(x) is False. Existential Quantification contd... Remark: When all the elements in the universe of discourse can be listed as, say, x1 , x2 , x3 , · · · , xn , the existential quantification ∃ x P(x) is the same as the disjunction P(x1 ) ∨ P(x2 ) ∨ · · · ∨ P(xn ) since this disjunction is true if and only if at least one of P(x1 ), P(x2 ), P(x3 ), · · · , P(xn ) is true. Existential Quantification contd... Example: What is the truth value of ∃ x P(x) where P(x) is the statement “x 2 > 10” and the universe of discourse consists of positive integers not exceeding 4? Solution: ▶ Universe of discourse is {1, 2, 3, 4}. ▶ ∃ x P(x) is the same as: P(1) ∨ P(2) ∨ P(3) ∨ P(4). ▶ P(4) = 16 > 10 which is true, T. ▶ ∴ ∃ x P(x) is true, T. Quantifiers contd... Translation of Statements: Example 1:   Translate the statement ∀ x c(x) ∨ ∃ y [c(y ) ∧ F (x, y )]) into English where c(x) is “ x has a computer”, F (x, y ) is “ x and y are friends” and the universe of discourse for both x and y is a set of students in your class. Solution: ▶ Alternative 1 : For every student x in your class, x has a computer OR there exists another student y such that y has a computer AND x and y are friends. ▶ Alternative 2 : Every student in your class has a computer OR has a friend who has a computer. Translation of Statements contd...Examples Example 2: Translate the h statement i ∃ x∀y ∀z : F (x, y ) ∧ F (x, z) ∧ y ̸= z → ¬F (y , z)]) into English, where F (a, b) means a and b are friends and the universe of discourse for x, y and z is a set of students in your class. Solution: ▶ There is a student x such that for all students y and all students z, x and y are friends and x and z are friends, then y and z are not friends. Translation of Statements contd...Exercises Exercise 1: Express the statements “some student in this class has visited Mexico” and “ every student in this class has visited either Canada or Mexico” using quantifiers. Exercise 2: Use quantifiers to express the statement “ there is a businessman who has a flight on every airline in the world” Translation of Statements contd...Solutions Exercise 1 (solution): ▶ Let x be the variable (set of students in this class) ▶ Let M(x) be the statement “x has visited Mexico ” ▶ Let C (x) be the statement “x has visited Canada ”. ∃xM(x)   ∀x C (x) ∨ M(x) Exercise 2 (solution): ▶ Let P(m, f ) be “ M has taken off ” and ▶ Q(f , a) be “ f is a flight on a ” ▶ ∃M∀a∃f [P(m, f )] ∧ Q(f , a)) where the universe of discourse for m, f and a consists of businessmen in the world, all air plane flights and all airlines respectively. 4: Relations Relations ▶ A relation is a set of ordered pairs. Example 1: Suppose A = {1, 2, 3, 4} is a set and R is a relation from A to A; then 1R2, 1R3, 1R4, 2R3, 2R4, 3R4. ▶ We have the relation R defined as the less than ( 200 (iv) 190 ≤ Cost ≤ 220 Relations contd... From/To C1 C2 C3 C4 C5 C1 - 140 100 150 200 C2 190 - 200 160 220 C3 110 180 - 190 250 C4 190 200 120 - 150 C5 200 100 200 150 - Solution: n (i) R = (C1 , C2 ), (C1 , C3 ), (C1 , C4 ), (C2 , C4 ), o (C3 , C1 ), (C3 , C2 ), (C4 , C3 ), (C4 , C5 ), (C5 , C2 ), (C5 , C4 ) Relations contd... Domain and Range of a Relation: ▶ Let R ⊆ A × B be a relation from A to B. (i) The domain of R denoted by Dom(R) is a set of the elements in A that are related to some elements in B, Or Dom(R) is a set of all first elements in each pairs that make up R. (ii) The range of R denoted by Ran(R) is a set of the elements in B that are the second elements of pairs in R i.e. all elements in B that are related to some elements in A. Domain and Range of a Relation contd... Example 1: Consider the relation defined by the diagram: Then ▶ Dom(R) = {1, 3, 4} ▶ Ran(R) = {x, y , w } Domain and Range of a Relation contd... Example 2: Let A = {1, 2, 3, 4, 5} and B = {q, r , s}. If R is a relation from A to B defined by R = {(1, r ), (2, s), (3, r )}, find: (a) Dom(R) Solution: Dom(R) = {1, 2, 3} (b) Ran(R) Solution: Ran(R) = {r , s} Relations contd... Inverse of a Relation: ▶ The inverse of a relation R from A to B denoted by R −1 is the relation from B to A which consists of those ordered pairs that when reversed belong to R i.e. n o R −1 = (b, a) : (a, b) ∈ R for a ∈ A and b ∈ B. Note: ▶ If aRb then bR −1 a for a ∈ A and b ∈ B if R is a relation from A to B. Relations contd... Example: Let R be the relation n from A = {1, 2, 3, 4} to B = o {x, y , z} defined by R = (1, y ), (1, z), (3, y ), (4, x), (4, z) (a) Determine: (i) Dom(R) (ii) Ran(R) (b) Find the relation R −1 of R. Solutions: (a) (i) Dom(R) = {1, 3, 4} (ii) Ran(R) = {y , z, x} n o (b) R −1 = (y , 1), (z, 1), (y , 3), (x, 4), (z, 4). Representation of Relations (i) Matrix of a Relation: ▶ A relation between two sets A and B can be represented in matrix form as follows: If A = {a1 , a2 , · · · , an } and B = {b1 , b2 , · · · , bn } are finite sets containing m and n elements respectively and R is a relation from A to B then we represent R as an m × n matrix denoted by: MR = [mij ] for the i th row and j th column where n o mij = 1 if (ai , bj ) ∈ R and 0 if (ai , bj ) ∈ /R Representation of Relations contd... Example: Let A = {1, 2, 3} and B = {r , s}. If R is a relation from A to B defined by R = {(1, r ), (2, s), (3, r )}, find MR , the matrix of R. Solution: A/B r s 1 1 0 2 0 1 3 1 0   1 0 ∴ MR = 0 1 1 0 Representation of Relations contd... Note: R −1 for the above relation is defined from B to A and R −1 = {(r , 1), (s, 2), (r , 3)} so that B/A 1 2 3 r 1 0 1 s 0 1 0   1 0 1 ∴ MR −1 = 0 1 0 Remark: ▶ The first, second and third rows of MR respectively form the first, second and third columns of MR −1 , hence MR −1 is a transpose of MR. Representation of Relations contd... Example:   1 0 0 1 Consider the matrix MR = 0 1  1 0 of the relation R from 1 0 1 0 the set A = {a1 , a2 , a3 } to the set B = {b1 , b2 , b3 , b4 }. Write R as a set of ordered pairs. Solution: A/B b1 b2 b3 b4 a1 1 0 0 1 a2 0 1 1 0 a3 1 0 1 0 n o ∴ R = (a1 , b1 ), (a1 , b4 ), (a2 , b2 ), (a2 , b3 ), (a3 , b1 ), (a3 , b3 ) Representation of Relations contd... (ii) Directed Graphs of a Relation: ▶ Also known as digraphs. ▶ If A is a finite set and R is a relation on A, then we can represent R pictorially as defined below: ▶ Draw a small circle and each element of A labelling each circle with the corresponding element. ▶ Draw an arrow called the edge from the vertex ai to vertex aj iff (ai Raj ) by R. ▶ The resulting pictorial representation is called the digraph of R. Representation of Relations contd... Example 1: Let A = {1, 2, 3, 4} be a set and R be a relation defined by n o R = (1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (2, 4), (3, 4), (4, 1) Draw the digraph of R. Solution: Representation of Relations contd... Example 2: Write R as a set of ordered pairs if its digraph is as shown below: Solution: n o ∴ R = (1, 1), (1, 3), (2, 3), (3, 2), (4, 3) Exercises 1. Find the domain, range, matrix and digraph of R in each of the following cases if R is defined from A to B. (a) A = {a, n b, c, d}, B = {1, 2, 3} and o R = (a, 1), (a, 2), (b, 1), (c, 2), (d, 1) (b) A = {IBM, Compaq, Dell, Hp, Zerith}, B = {750c, pc60, 450v , 4133v , 466v , 486Ω} and R = {(IBM, 750c), (Dell, 466v ), (Compaq, 450v ), (Hp, pc60)} (c) A = {1, 2, 3, 4} = B : aRb iff a = b (d) A = {1, 2, 3, 4, 8}, B = {1, 4, 6, 9} : aRb iff a|b (e) A = {1, 2, 3, 4, 5} = B : aRb iff a ≤ b Exercises contd... 2. Let A = {a, b, c, d} and R be a relation of A defined by n o R = (a, a), (b, b), (c, a), (c, b), (c, c), (d, b), (d, d) Find: (i) Matrix of R. (ii) Digraph of R. Exercises contd... 3. Find the relation R defined on A by the following matrices:   1 1 0 1 0 1 1 0 (a) MR =   for A = {1, 2, 3, 4} 0 0 1 1 1 0 0 0   1 1 0 0 0 0 0 1 1 0   (b) MR =  0 0 0 1 1  for A = {a, b, c, d, e} 0 1 1 0 0 1 0 0 0 0 Exercises contd... 4. Find R as a set of ordered pairs from the digraphs below: (a) (b) Relations contd... Composition of Relations: ▶ Let A and B be sets and let R be a relation from A to B and S be a relation from B to C i.e. R ⊆ A × B and S ⊆ B × C. ▶ Then, Q = R ◦ S (R composition S) is a relation from A to C i.e. a(R ◦ S)c for a ∈ A, b ∈ B and c ∈ C. Relations contd... Example 1: Let A = {1, 2, 3}, B = {a, b, c} and n C = {x, y , z}. Consider o the relation R from A to B i.e. R = (1, b), (2, a), (2, c) and S from n o B to C i.e. S = (a, y ), (b, x), (c, y ), (c, z). Find R ◦ S. Solution: n o ∴ R ◦ S = (1, x), (2, y ), (2, z) Relations contd... Example 2: Let A = {a, b, c, d}, B = {1, 2, 3} and C = {w , x, y , z}. Consider the relations n aRb and bSc defined by o R = (a, 3), (b, 3), (c, 1), (c, 3), (d, 2) and n o S = (1, x), (2, y ), (2, z). Find R ◦ S. Solution: n o ∴ R ◦ S = (c, x), (d, y ), (d, z) Relations contd... Example 3: Consider n the relation R whose o ordered n pairs are o R = (1, b), (2, a), (2, c) and S = (a, y ), (b, x), (c, y ), (c, z) on the sets A to B and B to C respectively where A = {1, 2, 3}, B = {a, b, c} and C = {x, y , z}. Find: (a) (i) MR (ii) MS (iii) MR◦S (b) Multiply MR by MS and compare the product MR ∗ MS with MR◦S. Relations contd... Solution 3(a) (i): A/B a b c 1 0 1 0 2 1 0 1 3 0 0 0   0 1 0 ∴ MR = 1 0 1 0 0 0 Relations contd... Solution 3(a) (ii): B/C x y z a 0 1 0 b 1 0 0 c 0 1 1   0 1 0 ∴ MS = 1 0 0 0 1 1 Relations contd... Solution 3(a) (iii): n o ∴ R ◦ S = (1, x), (2, y ), (2, z) A/C x y z 1 1 0 0 2 0 1 1 3 0 0 0   1 0 0 ∴ MR◦S = 0 1 1 0 0 0 Relations contd... Solution 3(b):       0 1 0 0 1 0 1 0 0 MR × MS = 1 0 1 × 1 0 0 = 0 2 1 0 0 0 0 1 1 0 0 0 Note: 0-entries and non-0 entries are in the same positions for the matrices MR ∗ MS and MR◦S. Relations contd... Exercise: Let A = {1, 2, 3, 4}, B = {a, b, c, d} and C = {x, y , z}. Consider the relation n aRb and bSc defined by o R = (1, a), (2, b), (3, a), (3, b), (3, d) n o R = (b, x), (b, z), (c, y ), (d, z) Find: (a) MR , MS and MR◦S. (b) Multiply MR by MS and compare the product MR ∗ MS with MR◦S. Relations contd... Equivalence Relations: (a) Reflexive Relation ▶ A relation R is reflexive if aRa for every a in the set A. Example 1: n A = {a, b, c} and Consider o R = (a, a), (a, b), (b, b), (b, c), (c, c) since for a ∈ A ∃ (a, a) ∈ R b ∈ A ∃ (b, b) ∈ R c ∈ A ∃ (c, c) ∈ R ∴ R is reflexive. Example n 2: o Is R = (0, 1), (2, 1), (1, 1), (0, 0), (1, 2) defined on A = {0, 1, 2} reflexive? Solution: ▶ 2 ∈ A but (2, 2) ∈/R ∴ R is not reflexive. Equivalence Relations contd... (b) Symmetric Relation: ▶ A relation R on a set X is symmetric if for all x, y ∈ X , if (x, y ) ∈ R, then (y , x) ∈ R. Example 1: The relation n R given by o R = (1, 0), (2, 1), (1, 1), (1, 2), (0, 1) is symmetric since for every (x, y ) there is a corresponding (y , x). Example n 2: o Is R = (a, b), (b, b), (b, c), (c, b) defined on A = {a, b, c} symmetric? Solution: ▶ (a, b) ∈ R but (b, a) ∈ /R ∴ R is not symmetric. Equivalence Relations contd... (c) Antisymmetric Relation: ▶ A relation R on a set X is an antisymmetric if for all x, y ∈ X , if (x, y ) ∈ R and (y , x) ∈ R, then x = y. Example: n o Let A = {a, b, c}, R = (a, a), (b, b), (c, c) ; then R is antisymmetric. Equivalence Relations contd... (d) Transitive Relation: ▶ A relation R on a set X is transitive if for all x, y , z ∈ X , if (x, y ) ∈ R and (y , z) ∈ R, then (x, z) ∈ R i.e. consider: (x, y ) (y , z) (x, z) (1, 1) (1, 1) (1, 1) (1, 1) (1, 2) (1, 2) (1, 1) (1, 3) (1, 3) (1, 2) (2, 3) (1, 3) (2, 3) (3, 4) (2, 4) Transitive Relation contd... Example n 1: o Is R = (a, a), (b, b), (c, b), (d, d) defined on X = {a, b, c, d} transitive? Solution: ▶ Since (c, b) ∈ R and (b, b) ∈ R and (c, b) ∈ R ∴ R is transitive. Example 2: n o Let A = {a, b, c, d} and R = (a, a), (b, c), (c, b), (d, d). Is transitive? Solution: ▶ Since (b, c) ∈ R, (c, b) ∈ R but (b, b) ∈/ R ∴ R is not transitive. Equivalence Relations contd... Remarks: 1. A relation which is reflexive, symmetric and transitive is called an equivalence relation. 2. A relation which is reflexive, antisymmetric and transitive is called a partial order i.e. a relation R on a set X is a partial order if R is reflexive, antisymmetric and transitive. Equivalence Relations contd...Exercises 1. Give examples of relations of a set A = {1, 2, 3, 4} having the properties specified below: (a) Reflexive, symmetric and not transitive. (b) Reflexive, not symmetric and not transitive. (c) Reflexive, antisymmetric and not transitive. 2. Write the relations described by the digraphs below as a set of ordered pairs and determine whether they are reflexive, symmetric, antisymmetric or transitive: Equivalence Relations contd...Exercises (i) (ii) (iii) Equivalence Relations contd...More Examples Example 1: [Task Scheduling] Consider the set T of tasks that must be completed in order to take an indoor flash picture with a particular camera. 1. Remove the lens cap 2. Focus camera 3. Turn off safely lock 4. Turn on flash unit 5. Push the photo button. ▶ Some of these tasks must be done before others e.g. Task 1 must be done before Task 2. On the other hand, other tasks can be done in either order. e.g. Task 2 and Task 3 can be done in either order. More examples... Example 1 contd... ▶ The relation R defined on T by iRj if i = j or task i must be done before Task j orders the tasks and we obtain: n R = (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 2), (1, 5), o (2, 5), (3, 5), (4, 5) Remarks: R above is defined on T = {1, 2, 3, 4, 5} (a) For all x ∈ T , (x, x) ∈ R, hence R is reflexive (b) R is not symmetric since (1, 2) ∈ R but (2, 1) ∈ / R, (1, 5) ∈ R but (5, 1) ∈ /R (c) R is antisymmetric since (x, x) ∈ R More examples... Example 1 contd... Remarks contd...: (d) R is transitive since for all x, y , z ∈ T : (x, y ) (y , z) (x, z) (1, 1) (1, 2) (1, 2) (4, 4) (4, 5) (4, 5) → R is reflexive, antisymmetric and transitive ∴ it is a partial order. Exercise: Find R using T in the example above if iRj if i = j or if task i or j can be done before the other. Determine if R is reflexive, symmetric, antisymmetric or transitive. 5: Functions Functions Function as a Relation: ▶ A function is a relation in which each value from the set of the first components of the ordered pairs is associated with one and only one value from the set of the second components of the ordered pairs. ▶ Considern the relations R1 and R2obelow: R1 = (a, 1), (b, 3), (1, 1), (d, 4) n o R2 = (1, w ), (2, y ), (3, x), (3, 2), (4, 2) Functions contd... ▶ → R1 is a relation since each element of the set A is mapped to one and only one element of the set B. ▶ → R2 is not a relation since 3 ∈ X is mapped to both x, y ∈ Y. Functions contd... Exercise: Determine whether or not each of the following relations is a function. n o (a) R1 = (2, 4), (3, −7), (6, 10) n o (b) R2 = (−1, 8), (4, −7), (−1, 6), (0, 0) n o (c) R3 = (6, 10), (−7, 3), (0, 4), (6, −4) n o (d) R4 = (2, 1), (9, 10), (−8, 1), (−4, 10) Functions contd... Function as an Equation: ▶ A function f is a rule which assigns to each value of a variable x called the argument of the function, one and only one value f (x) called the value of the function. Example: f and g below are functions since each value of x results to a single corresponding value of f (x) and g (x). 1. f (x) = x 2 + 1: (i) f (1) = 12 + 1 = 2 (ii) f (4) = 42 + 1 = 17 2. g (x) = x 3 + 2x 2 + 3x − 4: (i) g (1) = 13 + 2(12 ) + 3(1) − 4 = 2 (ii) g (4) = 43 + 2(42 ) + 3(4) − 4 = 104 Function as an Equation contd... ▶ h(x) is not a function since each value of x is mapped to two values of h(x) (+ and −). i.e. √ h(x) = x √ h(1) = 1 = ±1 √ h(4) = 4 = ±4 Functions contd... Composition of Functions: ▶ Let f (x) and g (x) be functions of x. ▶ The composition of f and g denoted (f ◦ g )(x) is defined by: (f ◦ g )(x) = f [g (x)]. ▶ Similarly, (g ◦ f )(x) = g [f (x)] where (f ◦ g )(x) and (g ◦ f )(x) are not necessarily equal. Example 1: Let f (x) = 31 x + 2 3 and g (x) = x 2 + 1. Find: (a) (f ◦ g )(x) (b) (g ◦ f )(x) Functions contd... Solution 1 (a): (f ◦ g )(x) = f [g (x)] 1 2 = (x 2 + 1) + 3 3 1 2 1 2 = x + + 3 3 3 1 2 = x +1 3 Functions contd... Solution 1 (b): (g ◦ f )(x) = g [f (x)] 1 2 2 = x+ +1 3 3 1 2 1  2 = x+ x+ +1 3 3 3 3 1 1 2 21 2 = x x+ + x+ +1 3 3 3 3 3 3 1 2 2 4 = x2 + x + x + + 1 9 9 9 9 1 2 4 4 = x + x +1 9 9 9 Functions contd... Example 2: Let f (x) = x + 2 and h(x) = x 2 + 3x + 1. Find: (a) (f ◦ h)(x) (b) (h ◦ f )(x) Functions contd... Solution 2 (a): (f ◦ h)(x) = f [h(x)] = (x 2 + 3x + 1) + 2 = x 2 + 3x + 1 + 2 = x 2 + 3x + 3 Solution 2 (b): (h ◦ f )(x) = h[f (x)] = (x + 2)2 + 3(x + 2) + 1 = (x + 2)(x + 2) + 3x + 6 + 1 = x(x + 2) + 2(x + 2) + 3x + 7 = x 2 + 2x + 2x + 4 + 3x + 7 = x 2 + 7x + 11 Functions contd... Exercise: Let f (x) = x 3 , g (x) = 3x 2 + 7 and h(x) = 2x 3 + 3x + 5. Find: (a) (f ◦ g )(x) (b) (g ◦ h)(x) (c) (f ◦ h)(x) (d) (g ◦ f )(x) (e) (h ◦ g )(x) (g) (h ◦ f )(x) Functions contd... Inverse of a Function: ▶ Inverse of a function represents a one-to-one mapping from the range of one function to its domain. ▶ The inverse of a function is also a relation in which the roles of the independent and dependent variables are reversed. ▶ The inverse of f is denoted by f −1. Example: Find the inverse of each of the following: (a) f (x) = 3x + 1 (b) g (x) = 2x − 3 √ (c) h(x) = x + 7 Functions contd... Solution 1(a): f (x) = 3x + 1 Let y = f (x) =⇒ y = 3x + 1 y −1 3x =⇒ = 3 3 y −1 =⇒ x = 3 x −1 ∴ f −1 (x) = 3 Functions contd... Solution 1(b): g (x) = 2x − 3 Let g (x) = y ∴ y = 2x − 3 y +3 2x = 2 2 y +3 x= 2 x +3 ∴ g −1 (x) = 2 Functions contd... Solution 1(c): √ h(x) = x +7 √ h(x) − 7 = x  2 √ 2 h(x) − 7 = x  2 h(x) − 7 = x  2 h−1 (x) = x − 7 Functions contd... Exercise: Find the inverse of: (a) f (x) = x 3 + 1 2x (b) g (x) = x−3 2 (c) h(x) = x+1 Functions contd... Surjective, Injective and Bijective Functions (a) Surjective Functions: ▶ Let f : A → B made to be an arbitrary function with the domain A and co-domain B. ▶ Recall that every member of A has an image under f such that the set of all the images is called the range of the function f. i.e. R = f (A) and note that R ⊆ B. Example 1: Consider the following mapping: Functions contd... ▶ Clearly f (x) = c, f (y ) = b, f (z) = e, f (w ) = d and ▶ A = {x, y , z, w } is the domain of f ▶ B = {a, b, c, d, e} is the co-domain of f ▶ But range, R = f (a) = {b, c, d, e} ▶ Note that a ∈ B and a ∈ / R ∴ R ̸= B and R ⊂ B (R is a proper subset of the co-domain B). Functions contd... Example 2: Let A = {a, b, c, d} and B = {IBM, Compaq, Hp, Dell} such that ▶ Domain is A = {a, b, c, d} ▶ Co-domain is B = {IBM, Compaq, Hp, Dell}. Functions contd... ▶ Images: f (a) = Hp, f (b) = IBM, f (c) = Dell, f (d) = Compaq such that: ▶ Range of f , R = {Hp, IBM, Dell, Compaq} = B. Remarks: ▶ If the range coincides with the co-domain, then the function is called a surjective function Or ▶ A function f : A → B is surjective (onto) function if the range of f = the co-domain of f. ▶ To show that a function is surjective, pick an arbitrary element in the co-domain and show that it has a pre-image in the domain. Functions contd... Example: Let f : R → {x|x > 0} where f (x) = e x. In this case, the co-domain is {x|x > 0} and the domain is R. ▶ Let x = 3, then f (3) = e 3 = 20.08 · · · x = 100, then f (100) = e 100 = 2.6 × 1043 ▶ In general, ∀x > 0, f (x) = e x ∈ R hence f : R → {x|x > 0} is surjective. Exercise: Check if the following are surjective functions: (1). f : R → R, f (x) = x 3 (2). f : R → R, f (x) = x 2 Functions contd... (b) Injective Functions: ▶ A function f : A → B is an injective (or one-to-one) function if no member of B is the image under f of two distinct elements of A i.e. to show that a function is injective, for any elements a1 and a2 of A with f (a1 ) = f (a2 ) then a1 = a2. Example: Test the following functions to see if they are injective: (a) f : R → R, f (x) = x 3 (b) f : R → R, f (x) = x 2 (c) f : [0, ∞) → R, f (x) = x 2 Functions contd... Solution (a): ▶ Let x = −2, then f (−2) = (−2)3 = −8 x = 5, then f (5) = (5)3 = 125 ▶ In general, ∀x ∈ R, f (x) = x 3 ∈ R such that no distinct x1 , x2 ∈ R has f (x1 ) = f (x2 ). ▶ ∴ f (x) = x 3 is injective. Solution (b): ▶ Let x = −2, then f (−2) = (−2)2 = 4 x = 2, then f (2) = (2)2 = 4 ▶ For any −x, x ∈ R, f (−x) = f (x) = x 2 hence f is not injective. Solution (c): ▶ Let x = 4, then f (4) = (4)2 = 16 x = 25, then f (25) = (25)2 = 625 ▶ In general, ∀{x|x ≥ 0} ∈ R, no distinct x1 , x2 ∈ R has f (x1 ) = f (x2 ). ∴ f (x) = x 2 is injective. Functions contd... Bijective Functions: ▶ A function f : A → B is bijective (a bijection) if it is both sujective and injective. Example: Which of the following functions are surjective, injective and bijective?. (a) f : R → R, f (x) = x 3 (b) f : R → R, f (x) = 2x (c) f : R → R, f (x) = x 3 − 2x 2 − 5x + 6 6: Mathematical Induction Mathematical Induction ▶ Mathematical theorems which state that P(n) is true for all positive integers where P(n) is a propositional function are verified by the technique of mathematical induction. ▶ Mathematical Induction is used to prove propositions of the form ∀P(n) where the universe of discourse is the set of positive integers. ▶ Proof by mathematical induction that P(n) is true for every positive integer n consists of two steps: 1. Basis Step: The proposition P(1) is shown to be true 2. Inductive Step: Assume that P(n) is true for all n and show that it will be true for P(n + 1). Mathematical Induction contd... Example 1: n(n+1) Show that 1 + 2 + 3 + · · · + n = 2 Proof: Basis Step: Show P(1) is true. ▶ L.H.S P(1) = 1 ▶ R.H.S P(1) = 1(1+1) 2 = 1×2 2 =1 ▶ ∴ P(1) is true. Inductive Step: k(k+1) ▶ Assume P(n) is true ∀k ∈ Z+ i.e. 1 + 2 + 3 + · · · + k = 2 ▶ Show that it is true for k + 1. Mathematical Induction contd... k(k + 1) 1 + 2 + 3 + · · · + k + (k + 1) = + (k + 1) 2 k(k + 1) + 2(k + 1) = 2 (k + 1)(k + 2) = 2 (k + 1)[(k + 1) + 1] = 2 which is true for k + 1 ▶ ∴ P(n) is true for all Z+ Mathematical Induction contd... Example of 2: Show that 1 + 3 + 5 + · · · + (2n − 1) = n2. Proof: Basis Step: ▶ Show that P(1) is true. ▶ L.H.S: P(1) = 1 ▶ L.H.S: P(1) = P(12 ) = 1 ∴ P(1) is true. Inductive Step: ▶ Show that P(n + 1) is true. ▶ Assume P(n) is true ∀k ∈ Z+ 1 + 3 + 5 + · · · + (2k − 1) = k 2 ▶ We show that it is true for k + 1. Mathematical Induction contd... 1 + 3 + 5 + · · · + (2k − 1) + [2(k + 1) − 1] = k 2 + [2(k + 1) − 1] 1 + 3 + 5 + · · · + (2k − 1) + (2k + 1) = k 2 + 2k + 1 = (k + 1)2 which is true for k + 1 ▶ ∴ P(n) is true for all positive integers. Mathematical Induction contd... Example 3: Use mathematical induction to show that 1 + 2 + 22 + · · · + 2n = 2n+1 − 1 for all non-negative integers n. Proof: Basis Step: ▶ (n = 0), show P(0) is true. ▶ L.H.S = 20 = 1 ▶ R.H.S = 20+1 − 1 = 21 − 1 = 1 ▶ ∴ P(0) is true. Inductive Step: ▶ Assume P(n) is true for all k ∈ Z+. ▶ 1 + 2 + 22 + · · · + 2k = 2k+1 − 1 ▶ We show that it is true for k + 1. Mathematical Induction contd... 1 + 2 + 22 + · · · + 2k + 2k+1 = 2k+1 − 1 + 2k+1 = 2k+1 + 2k+1 − 1 = 21 ∗ 2k+1 − 1 = 2[(k+1)+1] − 1 which is true for k + 1; ▶ ∴ P(n) is true for all non-negative integers. Mathematical Induction contd... Exercise: Prove the following using mathematical induction: n(n+1)(2n+1) 1. 12 + 22 + · · · + n2 = 6 h i2 n(n+1) 2. 13 + 23 + · · · + n3 = 2 (n+1)(2n+1)(2n+3) 3. 12 + 32 + 52 + · · · + (2n + 1)2 = 3 n(n+1)(n+2) 4. 1 ∗ 2 + 2 ∗ 3 + · · · + (n)(n + 1) = 3 Mathematical Induction contd... Strong Form of Mathematical Induction: ▶ Suppose we have a propositional function S(n) whose domain of discourse is the set of integers greater than or equal to n0. ▶ Suppose that S(n0 ) is true for all n > n0 , if S(k) is true for all k, where n0 ≤ k < n, then S(n) is true for all integers that are greater than or equal to n0 (n ≥ n0 ). Example: Use mathematical induction to show that postage of four cents or more can be achieved by using only two-cent and five-cent stamps. Mathematical Induction contd... Proof: Basis Step: ▶ When n = 4 (postage of 4-cent stamp), two 2-cent stamps are needed. ▶ When n = 5, one 5-cent stamp is needed. Inductive Step: ▶ Assume n ≥ 6 and that postage of k cents or more can be achieved using only 2-cent and 5-cent stamps for 4 ≤ k < n. ▶ By inductive assumptions, we can make a postage of (n − 2) cents. ▶ By adding a 2-cent stamp to (n − 2), we get n. This completes the proof. Mathematical Induction contd... Exercise: 1. Show that postage of Kshs 6 or more can be achieved by using only 2-Kshs and 7-Kshs stamps. 2. Show that postage of 24-Kshs or more can be achieved using only 5-Kshs and 7-Kshs stamps. 7: Graph Theory Graph Theory Definition: 1. A graph (or undirected graph) G consists of a set V of vertices and a set E of edges such that each edge e ∈ E is associated with an unordered pair of vertices. 2. A directed graph (digraph) G consists of a set V of vertices and a set E of edges such that each edge a ∈ E is associated with an ordered pair of vertices. Graph Theory contd... Note: (a) An edge in a graph (directed or undirected ) that is associated with a pair of vertices say v and w is said to be incident on v and w ; and v and w are said to be incident on e and to be adjacent vertices (b) If G is a graph (directed or undirected) with vertices V and E , we write G = (V , E ). Graph Theory contd... Graphs and Matrices: ▶ Let G be a graph with vertices v1 , v2 , · · · , vm and edges e1 , e2 , · · · , en , we define: (a) The Adjacency Matrix of G ▶ Let A = (aij ), be the m × n matrix defined by  1, if {vi , vj }is an edge i.e vi is adjacent to vj aij = 0, otherwise (b) The Incidence Matrix of G ▶ Let M = (mij ), be the m × n matrix defined by  1, if vertex i is incident on the edge ej mij = 0, otherwise ▶ Then M is the incidence matrix of G. Graph Theory contd...Examples Example 1: Find the adjacency matrix and the incidence matrix for the graph shown below. Graph Theory contd...Examples Solution: (i) Adjacency Matrix Since G has 5 vertices, the adjacency matrix A is a 5 × 5 matrix. Solution: (ii) Incidence Matrix Graph Theory contd...Examples Example 2: Find the adjacency matrix and the incidence matrix for the following graphs. (a) Graph Theory contd...Examples Solution: (a) Adjacency and Incidence Matrices Graph Theory contd...Examples Example 2 (b): Graph Theory contd...Examples Solution: (b) Adjacency and Incidence Matrices Graph Theory contd...Exercise Exercise: (a) Draw a graph with the following incidence matrix. (b) Find the adjacency matrix for the graph in (a) above. 8. Recurrence Relations Recurrence Relation Definition: ▶ A recurrence relation for the sequence {an } is an equation that expresses an in terms of one or more of the previous terms of the sequence i.e. a0 , a1 , a2 , · · · , an−1 for all integers n such that n ≥ n0 where n0 is a non-negative integer. ▶ A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation. ▶ The start-up values for a sequence or a recurrence relation are called the initial conditions. Recurrence Relation contd... Example 1: Let {an } be a sequence that satisfies the recurrence relation an = an−1 − an−2 for n = 2, 3, 4, · · ·. Suppose that a0 = 3 and a1 = 5, find a2 and a3. Solution: ▶ From an = an−1 − an−2 ▶ If n = 2; a2 = a(2−1) − a(2−2) =⇒ a2 = a1 − a0 ▶ a1 = 5, a0 = 3 ∴ a2 = 5 − 3 = 2 ▶ Similarly, a3 = a(3−1) − a(3−2) =⇒ a3 = a2 − a1 ▶ a2 = 2, a1 = 5 ∴ a3 = 2 − 5 = −3 Recurrence Relation contd... Example 2: (a) Determine whether the sequence {an } is a solution of the recurrence relation an = 2an−1 − an−2 for n = 2, 3, 4, · · · where an = 3n for every non-negative integer n. (b) Answer the same question where an = 2n and (c) where an = 5. Solution (2a): ▶ Suppose an = 3 − n for n > 0 ▶ Since n ≥ 2, note that an = 2an−1 − an−2 = 2[3(n−1) ] − 3(n−2) = 2[3n − 3] − 3n + 6 = 6n − 6 − 3n + 6 = 3n ▶ ∴ an = 3n is a solution to the recurrence relation. Recurrence Relation contd... Solution (2b): ▶ an = 2n , if n = 0 → a0 = 20 = 1 ▶ n = 1 → a1 = 21 = 2, n = 2 → a2 = 22 = 4 ▶ From an = 2an−1 − an−2 ▶ Let n = 2; a2 = 2a2−1 − a2−2 = 2a1 − a0 =⇒ a2 = 2(2) − 1 = 3 ▶ a2 = 3 ̸= a2 = 4; ▶ 3 ̸= a2 (since a2 = 4) ▶ ∴ an = 2n is not a solution to the recurrence relation. Recurrence Relation contd... Solution (2c): ▶ an = 5, 2an − 1 − an − 2 = 2[5 − 1] − (5 − 2) = (10 − 2) − 3 = 8 − 3 = 5 =⇒ an = 5 ▶ ∴ each and every term = 5 2an−1 − an−2 = 2(5) − 5 = 5 = an ▶ ∴ an = 5 is a solution to the recurrence relation. Recurrence Relation contd... Example 3: Suppose that a person invests $ 10, 000 in a savings account at a bank yielding 11% p.a with interest compounded annually. How much will be in the account after 30 years? Solution: ▶ Let Pn = the amount in the account after n years ▶ Amount at the start of the nth year is the principal amount plus interest accumulated for (n − 1) years i.e. Pn = Pn−1 + 0.11Pn−1 = (1 + 0.11)Pn−1 = 1.11Pn−1 Recurrence Relation contd... Solution contd...: Simplifying: If ▶ n = 1; P1 = 1.11P1−1 = 1.11P0 ▶ n = 2; P2 = 1.11P2−1 = 1.11P1 = 1.11(1.11P0 ) ▶ n = 3; P3 = 1.11P3−1 = 1.11P2 = 1.11(1.112 P0 ) = (1.11)3 P0 ▶ In general, Pn = (1.11)n P0 , where P0 = $ 10,000 (Principal amount) ▶ ∴ P30 = (1.11)30 × 10, 000 = $228, 922.97 Exercise 1. Find if each of the following sequences form a solution to the recurrence relation an = 8an−1 − 16an−2 : (a) an = 0 (b) an = 1 (c) an = 2 (d) an = 4 n (e) an = n.4 n (f) an = n2.4n 2. A person deposits $ 1000 in an account that yields 9% interest compounded annually. Set up a recurrence relation for the amount in the account at the end of n years. How much will be in the account after 100 years? 3. Assume that the population in the world in 2021 is 6 billion and is growing at the rate of 1.3% a year. What will be the population in the world in 2050? Linear Homogeneous Recurrence Relation ▶ A linear homogeneous recurrence relation of order k with constant coefficients is a recurrence relation of the form an = c1 an−1 + c2 an−2 + · · · + ck an−k for any ck ̸= 0. ▶ Suppose: n = 0; a0 = c0 n = 1; a1 = c1 a0 n = 2; a2 = c1 a1 + c2 a0 n = 3; a3 = c1 a2 + c2 a1 + c3 a0 Example: Assume that the deeper population of the country is 1000 at a time n = 0 and that the increase from time n − 1 to time n is 10% of the size at time n − 1. Write a recurrence relation and initial conditions that define the deeper population at time n and hence solve the recurrence relation. Linear Homogeneous Recurrence Relation Solution: ▶ Let dn = deeper population at time n; at n = 0, d0 = 1000 ▶ The increase from time (n − 1) to time (n) is given by dn − dn−1 and since this increase is 10% of the size at time n − 1, we obtain: dn − dn−1 = 10% of dn−1 dn − dn−1 = 0.1dn−1 dn = 0.1dn−1 + dn−1 dn = 1.1dn−1 ▶ If n = 1; d1 = 1.1d0 n = 2; d2 = 1.1d1 = (1.1)(1.1d0 ) = (1.1)2 d0 n = 3; d3 = 1.1d2 = (1.1)(1.1)2 d0 = (1.1)3 d0 ▶ In general, dn = (1.1)n d0 =⇒ dn = (1.1)n (1000)