Important Announcement
PubHTML5 Scheduled Server Maintenance on (GMT) Sunday, June 26th, 2:00 am - 8:00 am.
PubHTML5 site will be inoperative during the times indicated!

Home Explore Lecture Notes & Study Guide Discrete Mathematics

Lecture Notes & Study Guide Discrete Mathematics

Published by Fairuz Shohaimay, 2019-07-28 05:50:17

Description: Lecture notes for Discrete Mathematics
Intended for use by CS110 UiTM Kampus Raub only

Search

Read the Text Version

LECTURE NOTES & STUDY GUIDE DISCRETE MATHEMATICS Prepared by Fairuz Shohaimay



Lecture Notes & Study Guide Discrete Mathematics 2019 Edition Prepared by Fairuz Shohaimay This book is intended for use by CS110 students in UiTM Kampus Raub only.



CONTENT Notes iii Chapter 1 Set Theory 1 1.1 Sets and Subsets 5 1.2 Set Operations 7 1.3 Counting and Venn Diagram 14 1.4 Laws of Set Theory 17 Chapter 2 Fundamental Principles of Counting 21 2.1 The Rules of Sum and Product 27 2.2 Permutations 33 2.3 Combinations 2.4 Binomial Theorem 35 38 Chapter 3 Relations and Functions 46 3.1 Cartesian Products 50 3.2 Relations and Properties of Relations 3.3 Equivalence Relations and Partitions 59 3.4 Functions 62 69 Chapter 4 Directed Graphs 74 4.1 Graphs 4.2 Relations, Functions and Directed Graphs 79 4.3 Path and Cycles 85 4.4 Trees 95 Chapter 5 Fundamentals of Logic 102 5.1 Basic Connectives and Truth Tables 107 5.2 Logical Equivalence and The Laws of Logic 115 5.3 Logical Implication and Rules of Inference Chapter 6 Induction and Recursion 6.1 Sequences and Summations 6.2 The Principle of Mathematical Induction 6.3 Recursion i

ii

NOTES iii

NOTES iv

CHAPTER 1: SET THEORY 1.0 Introduction When we talk about sets, we will usually think about a group of things or objects or people having something in common. The set of students who like to take photographs or the set of positive integers, and so on. This chapter presents some of the essential terms, symbols and operations of sets. Finally, we give the fundamental laws of set theory. 1.1 Sets and Subsets Definition 1.1 A set is a collection of things, objects, items, etc. Definition 1.2 If ������ is one of the objects of the set ������ , then ������ is an element of ������ (denoted by ������ ∈ ������). If it is not true that ������ is an element of ������, we write ������ ∉ ������. We use capital letters to denote a set (e.g., A, B, C). Lower case letters (e.g., a, b, c, x) represent elements of the set. Elements of a set are placed within curly brackets “{ }” and separated by commas “,”. Example 1.1: If A is the set consisting of the first five positive integers, then we write ������ = {1, 2, 3, 4, 5} Here 2 ∈ ������ but 6 ∉ ������. Another standard notation for this set is, ������ = {������ |������ is an integer and 1 ≤ ������ ≤ 5}. Here the vertical line “|” within the set braces is read “such that.” The properties following | describes the properties of being a member of the set. 1

Example 1.2: If the members of a set are well known or follow by a particular pattern, we can define the set by listing a few elements followed by three dots: ������ = {… , −3, −2, −1, 0, 1, 2, 3, … } ������ = {2, 3, 5, 7, 9, … ,47} ������ = B21 , 1 , 1 , … C ������ = {������|������H + 2������ + 1 = 0} 3 4 The sets C and S are called finite sets. The sets I and F are called infinite sets. Below are some of the common number sets and their standard notations. 1. Whole numbers, ������ = {0, 1, 2, 3, … } = Nonnegative integers 2. Natural numbers, ℕ = {1, 2, 3, 4, … } = Positive integers 3. Integers, ℤ = {… , −3, −2, −1, 0, 1, 2, 3, … } 4. Rational numbers, ℚ = N������O������ = P , where ������, ������ ∈ ℤ, ������ ≠ 0W Q 5. Irrational numbers, ℚX = Y√2, ������, ������, √5, ]√4, … ^ = Numbers that cannot be expressed as a fraction. 6. Real numbers, ℝ Definition 1.3 The cardinality of a set ������, ������(������) (also can be written as |������|) is the number of different (distinct) elements in a set. Example 1.3: Given ������ = {������, ������, ������, ������, ������, ������} and ������ = Y2, 3, {5, 6}^ Then, ������(������) = 5, and ������(������) = 3. Definition 1.4 A set ������ is a subset of a set ������ (denoted by ������ ⊂ ������) if every element of ������ is an element of ������; that is, if ������ ∈ ������, then ������ ∈ ������. If it is not true that ������ is a subset of ������, we write ������ ⊄ ������. Example 1.4: {1, 2, 3} ⊂ {1, 2, 3, 4} but {1, 2, 5} ⊄ {1, 2, 3, 4}. Also, every set is a subset of itself, so {1, 2, 3} ⊂ {1, 2, 3}. 2

Example 1.5: If ������ = {������|������ is football player in UiTM}, ������ = {������|������ is an athlete in UiTM}, and ������ = {������|������ is a computer science student in UiTM}, then ������ ⊂ ������ but ������ ⊄ ������. Definition 1.5 If ������ and ������ are sets, then ������ equals ������, (A = B), whenever, ������ ∈ ������ if and only if ������ ∈ ������, for any x. An alternative definition is that ������ = ������ if and only if ������ ⊂ ������ and ������ ⊂ ������. Example 1.6: {1, 2, 4, 6} = {2, 6, 4, 1} Since a set is defined their elements, there is no order implied in the listing of the elements. Definition 1.6 The empty set, denoted by ∅ or by { }, is the set which contains no elements. Definition 1.7 The universal set ������ (or ������) is a set of all elements under discussion for possible membership in a set. Example 1.7: In number theory, ������ is usually the set of all integers of the positive integers. In calculus, ������ may be the set of all real numbers. By definition, every set is a set of the universal set. Since every element of the empty set contained in ������. Then, the empty set is a subset of any given set ������. Definition 1.8 The power set of ������, Ƥ(������) is the collection (or set) of all subsets of ������. For any finite set ������ with |������| = ������ ≥ 0, |Ƥ(������)| = 2|. 3

Example 1.8: For the set ������ = {1, 2, 3}, Ƥ(������) = Y{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1, 2, 3}, ∅^ Since |������| = 3 then the number of elements in Ƥ(������) is |Ƥ(������)| = 2} = 8. Exercise 1.1 1. List down the members of the sets below. a) A = The set of alphabets from the word “SESQUIPEDALIAN”. b) B = The set of months in the Hijrah calendar, which starts with Z. c) C = {������ ∈ ℤ|������H + 5������ − 6 = 0} d) D = The set of all prime numbers greater than 12 and less than 50. e) E = The set of all single-digit integers. f) F = {������ ∈ ℤ|������ is divisible by 2} g) G = {������|������ is a factor of 36 } 2. Given that ������ = {3, 4, 6, 7}, state whether the statements below are true or false. a) 7 ∈ ������ b) {1, 3} ∈ ������ c) {7} ∈ ������ d) ������ ⊂ ������ e) ∅ ⊂ ������ f) ������(������) = 4 3. List down all the subsets of ������ = {6, ∆, 8, ������}. 4. Consider the universal set ������ = {������ ∈ ℤ|10 ≤ ������ ≤ 20} and the following subsets. ������ = {������| ������ is a prime} ������ = {������| ������ is a composite} ������ = {������| 3 divides ������} a) List down all of the elements in the sets ������, ������, and ������. b) Determine the number of elements in the sets ������, ������, and ������. c) Is ������ = ������? Why or why not? 5. Let ������ = {1, 2} and ������ = {1, 2, 3}. Which of the following is true? a) {1} ∈ ������ b) ������ ⊂ ������ c) ∅ ⊂ ∅ d) {1} ⊂ ������ e) ������ = ������ f) ∅ ∈ {∅, ������ } g) ∅ ⊂ ������ h) ������ ≠ ������ i) ∅ ⊂ {∅, A} 6. Given the universal set, ������ = {������| 1 ≤ ������ ≤ 10; ������ is an integer} and ������ = {������|������ is even}. Which of the following is correct? a) 3 ∈ ������ b) { } ⊂ ������ c) 0.5 ∈ ������X d) ������ ∈ ������ e) ������ ⊂ ������ f) 4 ∉ ������X 4

1.2 Set Operations Definition 1.9 The intersection (“and”) of sets ������ and ������ (������ ∩ ������ ) is the set of all elements that are in both ������ and ������. ������ ∩ ������ = {������ | ������ ∈ ������ and ������ ∈ ������} Example 1.9: If ������ = {1, 2, 3, 4, 5} and ������ = {1, 3, 5, 7, 9}, then ������ ∩ ������ = {1, 3, 5} Definition 1.10 The union (“or”) of sets ������ and ������ (������ ∪ ������) is the set of all elements that are either in ������ or ������. ������ ∪ ������ = {������|������ ∈ ������ or ������ ∈ ������} Example 1.10: If ������ = {1, 2, 6, 7} and ������ = {2, 3, 5, 6}, then ������ ∪ ������ = {1, 2, 3, 4, 5, 6, 7} Definition 1.11 Assume that ������ and ������ are sets. The set difference ������ − ������ (or ������\\������) is the set of all elements which are in ������ but are not in ������ or in ������ only. ������ − ������ = {������|������ ∈ ������ and ������ ∉ ������} Example 1.11: If ������ = {1, 2, 4, 6, 7} and ������ = {2, 3, 4, 5, 6}, then ������ − ������ = {1, 7} and ������ − ������ = {3, 5} Definition of set difference: ������ − ������ = ������\\������ = ������ ∩ ������X 5

Definition 1.12 The complement of set ������, denoted ������’, is the set of all elements of the universe which are not in ������. ������X = ������ − ������ = {������|������ ∈ ������ and ������ ∉ ������} Example 1.12: ������’ If U is the set of positive integers and ������ = {2, 4, 6, 8, … } is the set of all even integers, then ������’ = {1, 3, 5, 7, … } is the set of all odd integers. Exercise 1.2 1. State whether the statements below are true or false. a) An empty set is a subset of a universal set. b) The intersection of a set with its complement is a universal set. c) Two sets are equal if their numbers of elements are equal. d) A set A is a subset of a set B if and only if elements in A are also elements in B. 2. Given that ������ = {������ ∈ ℤ|0 ≤ ������ < 13} , ������ = {0, 2, 4, 5, 8} and ������ = {������|������ is odd} . List all the elements of the following sets. a) ������X b) ������X c) ������ ∩ ������ e) (������ ∩ ������)X f) (������ ∪ ������)X d) ������ ∪ ������ i) (������\\������)X h) ������\\������ l) ������\\������X g) ������\\������ k) ������X\\������ j) (������\\������)X 3. Let ������, ������ and ������ are subsets of the universal set ������ = {������ ∈ ℤ| 1 ≤ ������ ≤ 30}, where ������ = {������|������ is a multiple of 3} ������ = {������|������ is a factor of 56} ������ = {������|������ is a two-digit number such that the sum of digits is odd } a) List down the elements of ������, ������ and ������. b) Find |������X ∩ ������|. c) Find |(������ ∩ ������)X|. 6

1.3 Counting and Venn Diagram A Venn diagram is used to represent finite elements of sets, sometimes overlapping with each other. We write the number of elements in each region. There is no formal rule for constructing a Venn diagram. However, the following formula might be useful. If ������ and ������ are finite sets, then |������ ∪ ������| = |������| + |������| − |������ ∩ ������| If also, ������ is a finite set, then |������ ∪ ������ ∪ ������| = |������| + |������| + |������| − |������ ∩ ������| − |������ ∩ ������| − |������ ∩ ������| + |������ ∩ ������ ∩ ������| From the formula for |������ ∪ ������ ∪ ������|and De Morgan’s Law, we find that if ������, ������, and ������ are sets from a finite universe ������, then |(������ ∪ ������ ∪ ������)X| = |������| − |������ ∪ ������ ∪ ������|. Example 1.13: In a class of 70 students, 42 likes sundae cone, 34 likes fruit smoothie, and ten likes both. How many students like neither? Let ������ = the class of 65 students ������ = students who like a sundae cone ������ = students who like a fruit smoothie ������ ������ ������ 10 24 4 7

Example 1.14: During a computer exhibition, a survey was conducted on 60 salespeople on their sales of computers. The following information was obtained: 19 salesmen sold Sony n(S) = 19 24 salesmen sold Acer n(A) = 24 25 salesmen sold Lenovo n(L) = 25 6 salesmen sold both Sony and Acer n(S Ç A) = 6 10 salesmen sold both Acer and Lenovo n(A Ç L) = 10 8 salesmen sold both Sony and Lenovo n(S Ç L) = 8 2 salesmen sold all three brands n(S Ç A Ç L) = 2 Draw and label a Venn diagram that represents the information above. Hence, find the number of salespeople who: a) did not sell any computers b) sold at least one computer c) sold at most two computers d) sold only Sony e) sold either Acer or Lenovo but not Sony f) sold Sony and Lenovo but not Acer Answers: (a) 14, (b) 46, (c) 58, (d) 7, (e) 27, (f) 6 8

Example 1.15: A lecturer has twenty-four introductory textbooks on computer science and is concerned about their coverage on the topics (A) compiler, (B) data structure and (C) operating systems. The following are the number of books that contain material on those topics: |������| = 8, |������| = 13, |������| = 13 |������ ∩ ������| = 5, |������ ∩ ������| = 3, |������ ∩ ������| = 6 and |������ ∩ ������ ∩ ������| = 2 a) Draw a single Venn diagram that represents that information. b) How many have no material on compilers? c) How many have material on compilers or operating systems but not data structure? d) How many have material on at least two of the topics? Answers: (b) 16, (c) 9, (d) 10 9

Example 1.16: From a survey done on 210 First Grade SPM students who have sent their applications to further studies oversea, it was found that: 70 students choose the United States of America 65 students choose Australia 35 students choose the United Kingdom and the United States of America 45 students choose the United Kingdom and Australia 30 students choose the United States of America and Australia 25 students choose all the three countries 50 students choose none for the three countries. a) Draw a Venn diagram to represent all the information given above. b) Find the number of students who choose only the United Kingdom. c) Find the number of students who choose the United Kingdom and Australia, but not the United States of America. Answers: (b) 55, (c) 20 10

Example 1.17: A TV station surveyed 115 respondents. They found that: 39 respondents like to watch Majalah 3, 43 respondents like to watch Jalan-Jalan Cari Makan, 56 respondents like to watch Nona, 7 respondents like to watch Majalah 3 and Jalan-Jalan Cari Makan 10 respondents like to watch Majalah 3 and Nona, and 6 respondents do not like to watch any of the programs. The number of respondents who like to watch Jalan-Jalan Cari Makan and Nona only is three times the number of respondents who like to watch all the three programs. a) Draw a Venn diagram which represents the above information. b) Find the number of respondents who like to watch those three programs. c) Find the number of respondents who like to watch at least one program. d) Find the number of respondents who like to watch exactly one program. e) Find the number of respondents who like to watch Jalan-Jalan Cari Makan and Nona but not Majalah 3. Answers: (b) 4, (c) 109, (d) 84, (e) 12 11

Example 1.18: A survey was conducted on several students. The following information was obtained: 41 owned an MP3 player 50 owned a digital camera 37 owned a laptop 25 owned both an MP3 player and a digital camera 33 owned both a digital camera and a laptop 13 owned an MP3 player only 2 owned a digital camera only a) Draw a Venn diagram to illustrate the above information. b) State the number of students who owned at least two types of gadgets. c) State the number of students who owned all three gadgets. d) Find the number of students who owned a laptop only. Answers: (b) 51, (c) 10, (d) 1 12

Exercise 1.3 1. Given the Venn diagram below, shade the region representing the following sets. ������ ������ ������ ������ a) (������ ∪ ������) ∩ ������ b) ������\\(������\\������) c) ������ ∩ (������ ∪ ������) d) ������′ ∪ (������\\������) e) (������ ∩ ������)X ∪ ������ f) ������′ ∩ ������ 2. The following information was obtained from 305 students. 125 students enrolled in Mathematics 115 students enrolled in Accounting 110 students enrolled in Science 35 students enrolled in Mathematics and Accounting 30 students enrolled in Mathematics and Science 10 students enrolled in all three of the above subjects 50 students did not enrol in any of the above subjects a) Sketch a Venn diagram that represents the above data. b) How many students enrolled in Mathematics only? c) How many students enrolled in Accounting but not Science? d) Calculate the number of students enrolled in Science and Accounting. e) How many students enrolled for exactly two subjects? f) How many students did not enrol for Accounting and Mathematics? 3. The following data were obtained from 74 car owners of Proton, Toyota and Honda. 42 owned Proton 20 owned Toyota and Proton 16 owned Honda and Proton 26 owned Honda and Toyota 10 owned only Honda 4 owned only Toyota a) Sketch a Venn diagram that represents the above data. b) How many own only Proton? c) How many own Proton or Honda? d) How many do Toyota owners not own Honda? e) How many owned at least 2 types of cars? f) How many owned at most 2 types of cars? 13

1.4 Laws of Set Theory For any sets ������, ������ and ������ taken from a universe ������, and ∅ represents the empty set. a) Double Complement Law (������X)X = ������ b) De Morgan’s Law c) Commutative Law (������ ∪ ������)X = (������X ∩ ������X) d) Associative Law (������ ∩ ������)X = (������X ∪ ������X) e) Distributive Law f) Idempotent Law ������ ∪ ������ = ������ ∪ ������ g) Identity Law ������ ∩ ������ = ������ ∩ ������ h) Dominance Law i) Inverse Law ������ ∪ (������ ∪ ������) = (������ ∪ ������) ∪ ������ j) Absorption Law ������ ∩ (������ ∩ ������) = (������ ∩ ������) ∩ ������ ������ ∪ (������ ∩ ������) = (������ ∪ ������) ∩ (������ ∪ ������) ������ ∩ (������ ∪ ������) = (������ ∩ ������) ∪ (������ ∩ ������) ������ ∪ ������ = ������ ������ ∩ ������ = ������ ������ ∪ ∅ = ������ ������ ∩ ������ = ������ ������ ∩ ∅ = ∅ ������ ∪ ������ = ������ ������ ∪ ������X = ������ ������ ∩ ������X = ∅ ������ ∪ (������ ∩ ������) = ������ ������ ∩ (������ ∪ ������) = ������ Example 1.19: Simplify ������ ∩ (������\\������). ������ ∩ (������\\������) Reasons = ������ ∩ (������ ∩ ������X) = ������ ∩ (������X ∩ ������) = (������ ∩ ������X) ∩ ������ = ∅ ∩ ������ =∅ 14

Example 1.20: Reasons Simplify (������\\������)X. Definition of set difference De Morgan’s Law (������\\������)X Double Complement Law = = Reasons = Reasons Example 1.21: Simplify ������ ∩ [(������ ∪ ������) ∪ ������′]. ������ ∩ [(������ ∪ ������) ∪ ������′] = ������ ∩ [������ ∪ (������ ∪ ������X)] = ������ ∩ (������ ∪ ������) = ������ ∩ ������ = ������ Example 1.22: Simplify ‘’(������ ∪ ������) ∩ ������“X ∪ ������X”X. ‘’(������ ∪ ������) ∩ ������“X ∪ ������X X ” = ‘’(������ ∪ ������) ∩ ������“X”X ∩ (������X)X = ’(������ ∪ ������) ∩ ������“ ∩ ������ = ������ ∩ ’(������ ∪ ������) ∩ ������“ = ’������ ∩ (������ ∪ ������)“ ∩ ������ = ������ ∩ ������ 15

Example 1.23: Reasons Simplify (������ ∪ ������) ∩ (������X ∩ ������)X. = = = = = Example 1.24: Simplify (������ ∪ ������)X ∩ (������ ∩ ������X)X. Reasons = = = = = = Exercise 1.4 1. Simplify the following set expression using the Laws of Set Theory. DO NOT skip any steps and state the laws used. a) (������ ∪ ������) ∩ ������ b) (������ ∩ ������)′ ∩ ������X c) (������\\������X) ∪ (������\\������) d) (������ ∩ ������) ∪ (������′ ∩ ������) e) (������ ∩ ������) ∪ (������X ∪ ������)X f) ((������ ∪ ������X)X ∪ ������) ∩ ������ 2. Prove the following set expression using the Laws of Set Theory. DO NOT skip any steps and state the laws used. a) ������X ∩ (������ ∪ ������) = ������\\������ b) ������\\(������ ∩ ������) = ������ ∩ ������′ c) ’������ ∩ (������′ ∪ ������)“X ∪ ������ = ������ d) (������\\������) ∩ (������\\������) = ∅ e) (������ ∩ ������) ∪ (������ ∩ ������′) = ������ f) (������ ∪ ������′) ∩ (������′\\������)X = ������ 16

CHAPTER 2: FUNDAMENTAL PRINCIPLES OF COUNTING 2.0 Introduction In this chapter, counting is more than just ‘1 2 3 4 5 …’. Consider the possibilities of creating passwords. If server can generate unique passwords with certain conditions, how many passwords would exist? The number of possible passwords is an example of a permutation problem. We want to find the number of ways to arrange symbols, or to select different options. Much of these problems use certain formulas, but we do not rely too heavily on them. Most of the time, you have to use some common sense and logical thinking. 2.1 The Rules of Sum and Product The Rule of Sum Suppose a first task can be performed in m ways. While a second task can be performed in n ways. If the two tasks cannot be performed simultaneously, then performing either task can be accomplished in m + n ways. The Rule of Product Suppose a task can be done in m ways for the first stage. Then for each of these outcomes, a task can be done in n ways for the second stage. Therefore, the total number of procedures to carry out these tasks can be done in m´ n ways. The above rules can be extended to three or more events. If an event ������\" can be performed in ������\" ways, a second event ������$ can be performed in ������$ ways, and a third event ������% can be performed in ������% ways and so on. Then Sum Rule: If two or more events cannot be performed at the same time, then one of the events can be performed in ������\" + ������$ + ������% + ⋯ ways. Product Rule: If the events can be performed one after the other, then all the events can be performed in the order indicated in ������\" × ������$ × ������% × … ways. 17

a) A food truck offers three main dishes, which are chicken burgers, fried rice, and spaghetti. How many ways can a customer buy one meal for his lunch? b) TEH’O Café offers 12 different tea flavours, eight different toppings and comes in regular or large sizes. If Sunny wishes to buy a drink, how many different drinks can she order? A shoe store wishes to display a new brand of shoes. The shoes come in three different colours, two different designs and four different patterns. How many ways can two different shoes be displayed? 18

a) How many different ways can we arrange the letters a, b and c? ´´= 1. You can put 2. Suppose you 3. Suppose you have the letters a have chosen b, you chosen b and c, you or b or c. can put a or c. can only put a. There are ______ possible arrangements: a b c , a c b , b a c , b c a , c b a , c a b b) From (a), how many ways can we arrange the elements if the repetition of the elements is allowed? ´´= 1. You can put Suppose you’ve chosen c the letters a since repetition is allowed or b or c. you can still put a or b or c. List down all the possible arrangements. Consider the manufacture of license plates consisting of two letters, followed by four digits. Find the number of arrangements a) if no letter or digit can be repeated. ´ ´ ´ ´ ´= 19

b) with repetitions of letters and digits allowed, ´ = ´´´´ c) if repetitions are allowed as in part (b), how many of plates have only vowels (A, E, I, O, U) and even digits? (0 is an even integer.) ´ ´ ´ ´ ´= Exercise 2.1 1. A university would like to determine how many different four-digit telephone extensions can be made using the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Find the number of extensions if: a) The four digits must be different. b) The four digits can be repeated. 2. Terra automobiles come in four models, 12 colours, three engine sizes, and two transmission types. a) How many distinct Terras can be manufactured? b) If one of the available colours is blue, how many different blue Terras can be manufactured? 3. A new brand of bags comes in five different designs. Each design is available in three different colours and three different sizes. How many distinct bags can be purchased? 4. McGee’s restaurant has a large selection of food and drinks. It offers ten different main dishes, five different side dishes, two types of desserts and three different drinks. Each drink is available in two different sizes. If Adi wants to buy a combo meal consisting one of each main dish, side dish, dessert and a drink, how many different meals can he order? 20

2.2 Permutations Definition 2.1 For an integer ������ ≥ 0, ������ factorial (������!) is defined by 0! = 1 ������! = ������ × (������ − 1) × (������ − 2) × … × 3 × 2 × 1, for ������ ≥ 1 a) 2! = b) 3! = c) 9! = d) (������ + 1)! = (������ + 1) × ������! e) \":! = 10 × 9 × 8 × 7 × 6 × ;×?×%×$×\" = 10 × 9 × 8 × 7 × 6 ;! ;×?×%×$×\" Definition 2.2 Given a collection of ������ distinct objects, any (linear) arrangement of these objects is called a permutation of the collection. If there are ������ distinct objects and ������ is an integer, with 1 ≤ ������ ≤ ������ , then by the rule of product, the number of permutations of size ������ for ������ objects is ������(������, ������) = F ������E = (������ ������! − ������)! Suppose we are interested in arranging only two of the four letters p, q, r, and s, there are ____ ways to do so. ������ =_____, ������ = _____. F ������E = =_____ ways. a) How many ways can the letters in the word COMPUTER can be arranged? F ������E = G ������G = 8! =_____ ways. b) If only five of the letters are used, the number of permutations (of size 5) is ������ =_____, ������ = _____. F ������E = =_____ ways. 21

Definition 2.3 If there are ������ objects with ������\" indistinguishable objects of a first type, ������$indistinguishable objects of a second type, ..., and ������E indistinguishable objects of an ������-th type, where ������\" + ������$ + ⋯ + ������E = ������, then the (linear) arrangements of the given ������ objects is ������! ������\"! × ������$! × … × ������E! Consider the word SESPQUIPEDALIAN. Arranging all of the letters, we have ������(������) = ___, ������(������) = ___, ������(������) = ___, ������(������) = ___, ������(������) = ___, ������(������) = ___, ������(������) = ___, ������(������) =___, ������(������) =___, ������(������) =___, ������(������������������������������) = 15 2! × 2! 15! 2! × 2! = possible arrangements. × 2! × Find the number of arrangements that can be formed using all the alphabets from the words: a) COMMUTATIVE Answer: 9979200 b) TALLAHASSEE Answer: 831600 c) ARRANGEMENTS Answer: 29937600 d) UNIVERSITY Answer: 1814400 22

Conditional Permutation For a conditional permutation, we do not only use formula but also logical thinking. Permutation in a circular arrangement There are (������ – 1)! ways that ������ person can be seated around a circular table. Determine the number of arrangements of three female students and four male students, such that it satisfies the following condition. a) in a row with no restriction b) in a row, if three female students must be together c) in a row, if three female students must not be together d) around a circular table 23

Three couples go to a movie together. Determine the number of ways they can sit if a) they can sit in any order. b) all three couples must sit together. Consider the word MASSASAUGA. How many possible arrangements such that all four A’s are together? AAAA (one symbol), S, S, S, M, U, G a) How many different arrangements of the letters in the word DIRGAHAYU can be formed if all the vowels are arranged on the right and all the consonants are on the left? 24

b) Find the number of arrangements of all the letters in the word PLAGIARISM in which all the vowels must not be together. The number of ways = (no restriction) – (arrangement such that vowels are together) Find the number of ways to form four-digit numbers using the digits 4, 5, 6, 7, 8, 9 if a) no repetition is allowed. b) repetition of digits is allowed. c) the numbers from (a) are odd. d) the numbers from (b) are even numbers. 25

Exercise 2.2 1. In how many ways can 6 girls and 2 boys be arranged in a row a) without restriction? b) such that the 2 boys are together? c) such that the 2 boys are not together? 2. In how many ways can the symbols a, b, c, d, e, e, e, e, e be arranged so that no e is adjacent to another e? 3. How many positive integers n can we form using the digits 3, 4, 4, 5, 5, 6, 7 if we want n to exceed 5,000,000? 4. Consider the three-digit number that can be formed from the digits 1, 2, 3, 4, 5 with no repetition of digits allowed. a) How many of these numbers are even numbers? b) How many numbers are greater than 250? c) How many numbers are greater than or equal to 350? 5. How many distinct license plates are there such that a) four uppercase letters, followed by a space and two digits? b) either six uppercase or lowercase letters or two digits followed by four uppercase letters? c) eight alphanumeric characters? 6. Determine the number of six-digit integers (no leading zeros) in which a) no digit may be repeated b) digits may be repeated c) from part (a) and (b) with the extra condition that the six-digit integer is i) even ii) divisible by 5 7. Given the digits: 0, 1, 2, 3, 4, 5. a) Find the number of 4-digit numbers which are greater than 3000 that can be formed if repetition is allowed. b) How many of the numbers formed from (a) are odd numbers? 8. In how many ways can the letters in WONDERING be arranged with all the vowels must be next to each other? 9. Find the number of different possible arrangements of the letters in the word DISCIPLINARY such one of the I’s is placed at the end. 10. In how many ways can you choose four countries to visit in four consecutive months form a list of nine possible countries, including France and Germany, if a) France must be visited? b) France or Germany must be visited but not both? c) France and Germany must be visited, but neither country can be visited during the first of the consecutive months? 26

2.3 Combinations Definition 2.4 If we start with ������ distinct objects, each selection, or combination, of ������ of these objects, with no reference to order, corresponds to ������! permutations of size ������ from the ������ objects. Thus, the number of combinations of size ������ from a collection of samples ������ is ������(������, ������) = F ������E = X������������Y = ������! ������! ������)! , for 0 ≤ ������ ≤ ������ (������ − Determine the number of ways to select three letters from the letters a, b, c. a b c = a c b = b a c = b c a = c b a = c a b = 1 way Order is not important! Important When dealing with any counting problem, we should ask ourselves about the importance of order in the problem. When the order is relevant, we think in terms of permutations and arrangements and the rule of product. When the order is not relevant, combinations could play a key role in solving the problem. Find the value of a) Z ������? = b) ������(5,3) = c) X82Y = d) X110Y = In how many ways can we select three students from seven students? 27

A class of 20 students consists of 12 boys and eight girls. Find the number of ways we can select a) five students. b) three girls and two boys. c) five students, but Adam and Shira must be chosen. An organization has 15 members that consist of six doctors. In how many ways can a committee of five members be selected such that a) any members are included? b) at least three doctors are included? 28

A bridegroom’s party rented five cars from Hetz Rentals. The company has ten Mini Coopers, six BMWs and seven Lancers. Find the number of ways the party could rent those cars if a) there was no condition on the types of vehicles rented. b) they wanted to rent at most three BMWs. Definition 2.5 When we wish to select, with repetition, ������ of ������ distinct objects, the number of combinations of ������ objects taken ������ at a time, with repetition, is ������(������ + ������ − 1, ������) = F[E\\\" ������E The value of ������ can exceed ������ when repetitions are allowed. On their way home from track practice, a group of eight friends stop at a restaurant, where each of them has one of the following: a nasi lemak, a nasi kerabu, a nasi ayam, or a nasi dagang. How many different purchases are possible (from the viewpoint of the restaurant)? 29

In how many ways can three letters be chosen from the letters ������, ������, ������, and ������ if repetition is allowed? Given six digits: 2, 3, 4, 7, 8, 9. a) Find the number of different possible arrangements of three-digit numbers such that repetition is allowed. b) Find the number of ways to select three numbers from the six digits such that repetition is allowed. 30

a) In how many ways can we distribute seven apples among four children? b) In how many ways can we distribute seven apples among four children so that each child receives at least one apple? c) In how many ways can we distribute nine apples and six oranges among four children such that each child receives at least two apples. 31

Exercise 2.3 1. Among 11 students, how many ways are there to select a) five students? b) five students but Ahmad is always included? c) five students so that Aliyah and Ali must be included? 2. How many ways can a committee consisting of two men and three women were selected from five men and five women? 3. A committee of 12 is to be selected from 10 men and 10 women. In how many ways can the selection be carried out if a) there are no restrictions? b) there must be an even number of women? c) there must be more women than men? d) there must be at least eight men? 4. Given a netball club has 20 players and all the players can play equally well. How many ways are there to choose seven players to start a game? 5. Out of five mathematicians and seven engineers, a committee consisting of two mathematicians and three engineers is to be formed. In how many ways can this be done if a) any mathematician and any engineer can be included? b) one particular engineer must be in the committee? c) two particular mathematicians cannot be in the committee? 6. In how many ways 13 balls can be put into three different boxes, such that a) there is no restriction. b) at least three balls must be placed in each of the boxes. 7. A bakery makes five different kinds of cookies: apple, banana, cinnamon, ginger and chocolate. a) Find the number of ways to buy eight cookies. b) Find the number of ways to buy ten cookies if two of the cookies must be chocolate. 8. A basket has 12 balls which are 4 identical blue balls, 4 identical red balls and 4 identical green balls. In how many ways can we select 3 balls from the basket? 9. In how many ways can 15 identical candy bars be distributed among five children so that the youngest gets only one or two of them? 32

2.4 Binomial Theorem Definition 2.7 The Binomial Theorem. If ������ and ������ are variables and ������ is a positive integer, then (������ + ������)F = XcF���0���YX������������F������Y���������:���F+\\eX������1������eY ������F\\\"������\" + X���2���Y ������F\\$������$ + ⋯ + X������ ������ 1Y ������F������F\\\" + X������������Y ������:������F = − ef: The first term starts at ������ = 0. a) Expand (������ + ������)%. b) Expand (������ − 2������)?. c) Expand (3 + ������)%. 33

d) Expand Xg$ − ; . 3������Y e) Find the coefficient of ������$������h in the expansion of (������$ − ������)G. f) Find the fourth term of the expansion of Xi\" + Z . ������Y Exercise 2.4 1. Find the third term of the expansion of (3������ − ������%)?. 2. Find the coefficient of ������%������h in the expansion of (2������ − ������$)h. 3. Find the middle term in the expansion of Xg% + \": and the coefficient of ������$������?. ������Y 4. Determine the coefficient of ������k������% in the expansions of a) (������ + ������)\"\" b) (������ − ������%)h c) (2������ − 5������)\"$ 34

CHAPTER 3: RELATIONS AND FUNCTIONS 3.0 Introduction Many of us should be familiar with the term ‘relation’, such as Aminah is the daughter of Encik Ali, Gina and Jenny are sisters, and so on, where ‘daughter of’ and ‘sisters’ are relations. In mathematics, relations are more often like ‘less than’, ‘subset of’ or ‘parallel to’. It is a connection between pairs of objects. Certain types of relations have some conditions; relations of these kinds are known as functions. 3.1 Cartesian Products Definition 3.1 Let A and B be sets. The Cartesian product of ������ and ������ (denoted by ������ × ������) is defined as the set of all possible ordered pairs (������, ������), having the first component from set ������ and second component from set ������, that is ������ × ������ = {(������, ������)|������ ∈ ������, ������ ∈ ������} Let ������ = {������, ������, ������} and ������ = {0, 1, 2, 9}, then a) ������ × ������ = The following table shows all the possible ordered pairs in ������ × ������. ������ × ������ ������ 0129 ������ (������, 0) (������, 1) (������, 2) (������, 9) ������ ������ (������, 0) (������, 1) (������, 2) (������, 9) (������, 0) (������, 1) (������, 2) (������, 9) ������ b) ������ × ������ = c) ������3 = ������ × ������ = d) ������3 = ������ × ������ = 35

Important The Cartesian product, ������ × ������ deals with ordered pairs, so ������ × ������ ≠ ������ × ������ ������(������ × ������) = ������(������) × ������(������) Let ������ = {1,3,5} and ������ = {������, ������, ������}, then a) ������ × ������ = b) ������ × ������ = c) |������ × ������| = Theorem Let ������, ������ and ������ be subsets of ������, then • ������ × (������ ∩ ������) = (������ × ������) ∩ (������ × ������) • |������ × ������| = ������(������ × ������) = ������(������) ∙ ������(������) = |������| ∙ |������| • (������ ∩ ������) × ������ = (������ × ������) ∩ (������ × ������) • (������ ∪ ������) × ������ = (������ × ������) ∪ (������ × ������) Given ������ = {1, 3}, ������ = {3, 5}, and ������ = {1, 5}, list down the elements of the following sets. a) (������ × ������) ∪ (������ × ������) = 36

b) (������ × ������) ∩ (������ × ������) = Given ������ = {3, 4, 8} and ������ = {������|������ ∈ ℤD and ������I < 200}, find a) ������(������) b) ������ × ������ c) (������ ∩ ������) × ������ Exercise 3.1 1. If ������ = {1, 2, 3, 4}, ������ = {2, 5}, and ������ = {3, 4, 7}, determine the elements of the sets a) ������ × ������ b) ������ × ������ c) ������ ∪ (������ × ������) d) (������ ∪ ������) × ������ e) (������ × ������) ∪ (������ × ������) 2. If ������ = {Amin, Iman, Aman}, ������ = {tall, petite}, and ������ = {Mathematics, Science, Arts}. List down the elements of the following Cartesian product. a) ������ × ������ b) ������ × ������ c) ������ × ������ × ������ 37

3.2 Relations and Properties of Relations Definition 3.2 Let ������ and ������ be sets. A relation ������ from ������ to ������ is a subset of ������ × ������. Any subset of ������ × ������ is called a relation on ������. (������, ������) ∈ ℛ; ‘a is related to b’, written ������ℛ������. (������, ������) ∉ ℛ; ‘a is not related to b’, written ������ℛ������. Given ������ = {2, 3, 5} and ������ = {2, 5, 6}, the Cartesian product ������ × ������ = a) ������ b) ������ ������ × ������ ������ × ������ 256 256 2 (2, 2) (2, 5) (2, 6) 2 (2, 2) (2, 5) (2, 6) ������ 3 (3, 2) (3, 5) (3, 6) ������ 3 (3, 2) (3, 5) (3, 6) 5 (5, 2) (5, 5) (5, 6) 5 (5, 2) (5, 5) (5, 6) ℛb = {(2, 2), (5, 5)} ℛ3 = {(3, 2), (5, 2)} ������ equals ������ ������ greater than ������ c) ������ d) ������ ������ × ������ ������ × ������ 256 256 2 (2, 2) (2, 5) (2, 6) 2 (2, 2) (2, 5) (2, 6) ������ 3 (3, 2) (3, 5) (3, 6) ������ 3 (3, 2) (3, 5) (3, 6) 5 (5, 2) (5, 5) (5, 6) 5 (5, 2) (5, 5) (5, 6) ℛI = ℛd = ������ ≤ ������ ������ + ������ is even 38

Given ������ = {2, 3, 5, 6}. Define a relation ℛ on ������ if and only if ������ divides evenly into ������ (a divides ������). Given ������ = {5, 8, 10}. Let ℛ be a relation on ������ consisting of ordered pairs (������, ������) such that ������ ≥ ������. Given ������ = {1, 2, 3, 4, 5} and ������ = {2, 4, 6, 8}, ������ℛ������ if and only if ������ + ������ ≤ 10. 39

Definition 3.3 A relation ℛ on a set ������ is reflexive if for all ������ ∈ ������, then (������, ������) ∈ ℛ. In other words, a relation ℛ is reflexive when each element ������ of ������ is related to itself. For ������ = {1, 2, 3, 4}, a relation ℛ on ������ will be reflexive if and only if (1, 1), (2, 2), (3, 3), (4, 4) ∈ ℛ a) ℛb = {(1, 1), (2, 2), (4, 4)} is not a reflexive relation on ������ because 3 ∈ ������ but (3, 3) ∉ ℛb. b) ℛ3 = {(������, ������)|������, ������ ∈ ������; ������ ≤ ������} is reflexive on A. ×1 2 3 4 1 (1, 1) (1, 2) (1, 3) (1, 4) 2 (2, 1) (2, 2) (2, 3) (2, 4) 3 (3, 1) (3, 2) (3, 3) (3, 4) 4 (4, 1) (4, 2) (4, 3) (4, 4) Definition 3.4 A relation ℛ on a set ������ is symmetric if for all ������, ������ ∈ ������, if (������, ������) ∈ ℛ then (������, ������) ∈ ℛ . In other words, a relation ℛ is symmetric when ������ and ������ have the same relation with each other. Consider the set ������ = {1, 2, 3, 4}, then a) ℛb = {(1, 2), (2, 1), (1, 3), (3,1)} is symmetric. b) ℛ3 = {(1, 1), (2, 2), (3, 3), (2,3)} is not symmetric because (2,3) ∈ ℛ3 but (3,2) ∉ ℛ3. c) ℛI = {(1, 1), (2, 2), (3, 3), (2,3), (3,2)} is ________________________________. d) ℛd = {(1, 1), (2, 2), (1, 3)} is ________________________________________. ×1 2 3 4 1 (1, 1) (1, 2) (1, 3) (1, 4) 2 (2, 1) (2, 2) (2, 3) (2, 4) 3 (3, 1) (3, 2) (3, 3) (3, 4) 4 (4, 1) (4, 2) (4, 3) (4, 4) 40

Definition 3.5 A relation ℛ on a set ������ is transitive if for all ������, ������, ������ ∈ ������, if (������, ������) ∈ ℛ and (������, ������) ∈ ℛ then (������, ������) ∈ ℛ. In other words, a relation ℛ is transitive when ������ is related to ������ and ������ is related to ������, while ������ is the intermediary. If ������ = {1, 2, 3, 4}, then a) ℛb = {(1, 1), (2, 3), (3, 4), (2,1)} is transitive. b) ℛ3 = {(1, 1), (1, 3), (3, 3), (3,2)} is not transitive because (1,3) and (3,2) ∈ ℛ3 but (1,2) ∉ ℛ3. c) ℛI = {(1, 1), (2, 2), (3, 3), (2,3), (3,2)} is ________________________________. d) ℛ3 = {(1, 1), (2, 2), (1, 3), (3,1)} is ____________________________________. ×1 2 3 4 1 (1, 1) (1, 2) (1, 3) (1, 4) 2 (2, 1) (2, 2) (2, 3) (2, 4) 3 (3, 1) (3, 2) (3, 3) (3, 4) 4 (4, 1) (4, 2) (4, 3) (4, 4) Definition 3.6 A relation ℛ on a set ������ is antisymmetric if for all ������, ������ ∈ ������, if (������, ������) ∈ ℛ and (������, ������) ∈ ℛ then ������ = ������. In other words, a relation ℛ is antisymmetric when ������ is related to ������ and ������ is related to ������, if ������ and ������ are the same elements. Given ������ = {1, 2, 3, 4}, then a) ℛb = {(1, 1), (1, 2), (2, 3), (1, 3), (4, 4)} is antisymmetric. b) ℛ3 = {(1, 1), (1, 3), (2, 2), (3, 1), (3, 2), (3,3), (3, 4)} is not antisymmetric because (1,3) and (3,1) ∈ ℛ3 but 1 ≠ 3. c) ℛI = {(1, 1), (2, 2), (3, 3), (1,3), (3,4), (4,2)} is ____________________________. d) ℛ3 = {(1, 1), (2, 2), (2, 3), (3,1), (3, 2), (4,3)} is ____________________________. Important The properties of being symmetric and being antisymmetric are not negatives of each other. 41

a) ℛb = {(1, 3), (3, 1), (2, 3)} is not symmetric and not antisymmetric. b) ℛ3 = {(1, 1), (2, 2)} is both symmetric and antisymmetric. Definition 3.7 A relation ℛ on a set ������ is a partial order if ℛ is reflexive, antisymmetric, and transitive. Given ������ = {1, 2, 3}, list the elements of the relation ℛ on ������ given by ℛ = {(������, ������)|������, ������ ∈ ������; ������ ≥ ������} Then, a) ℛ is reflexive because b) ℛ is antisymmetric because c) ℛ is transitive because Therefore, ℛ is a ____________________________________________________. Definition 3.8 A relation ℛ on a set ������ is an equivalence relation if ℛ is reflexive, symmetric, and transitive. Given ������ = {2, 3, 5, 7, 11}, and a relation ℛ on ������ given by ℛ = {(������, ������)|������, ������ ∈ ������; ������ and ������ are odd} Then, a) ℛ is reflexive because b) ℛ is symmetric because c) ℛ is transitive because Therefore, ℛ is a ____________________________________________________. 42


Like this book? You can publish your book online for free in a few minutes!
Create your own flipbook