FMCS 101- Fundamentals of Mathematics for Computer Science “This is property of PRESIDENT RAMON MAGSAYSAY STATE UNIVERSITY NOT FOR SALEFMCS101 - Fundamentals of Mathematics for Computer Science First Edition, 2022 Copyright. Republic Act 8293 Section 176 provides that “No copyright shall subsist in any work of the Government of the Philippines. However, prior approval of the government agency or office wherein the work is created shall be necessary for exploitation of such work for profit. Such agency or office may, among other things, impose as a condition the payment of royalties. Borrowed materials included in this module are owned by their respective copyright holders. Every effort has been exerted to reach and seck permission to use these materials from their respective copyright owners. The University and authors do not claim ownership over them.Course Overview Introduction ‘Computer science is the art of solving problems with computers. This is a broad definition that encompasses an equally broad field. Within computer science, we find software engineering, bioinformatics, cryptography, machine learning, human-computer interaction, graphics, and a host of other fields. Mathematics underpins all of these endeavors in computer science. We use graphs to model complex problems, and exploit their mathematical properties to solve them, ‘We use recursion to break down seemingly insurmountable problems into smaller and more ‘manageable problems. We use topology, linear algebra, and geometry in 3D graphics. We study computation itself in computability and complexity theory, with results that have profound impacts on compiler design, machine learning, cryptography, computer graphics, and data processing. This set of course notes serves as a first course in the mathematical foundations of computing. It will teach you how to model problems mathematically, reason about them abstractly, and then apply a battery of techniques to explore their properties. It will teach you to prove mathematical truths beyond a shadow of a doubt. It will give you insight into the fundamental nature of computation and what can and cannot be solved by computers. It will introduce you to complexity theory and some of the most important problems in all computer science. This set of course notes is intended to give a broad and deep introduction to the mathematics that lie at the heart of computer science. It begins with a survey of discrete ‘mathematics ~ basic set theory and proof techniques, mathematic induction, graphs, relations, functions, and logic — then explores computability and complexity theory. This subject discusses a range of mathematies topics to provide a foundation for concepts and analysis used in computer science. It can be used by the students in computer science as introduction to the underlying ideas of mathematics for computer science. Starting with the fundamentals of logic, and finishing with Matrices. ‘Course General Objectives At the end of the semester, the students will be able to: Leam basic concepts of mathematical logic and proof, 2. Use different set notations; 3, Demonstrate knowledge on the key concepts on functions, coordinate system and sequences4. Apply different methods on solving problems; 5. Use matrices to describe suitable situations Course Details: Course Code: FMCS 101 Course Title: Fundamentals of Mathematics for Computer Science No. of Units :3 Classification: Lecture-based Pre-requisite / Co-Requisite: None Semester and Academic Year: 2" Semester, AY 2021-2022 Schedule: 9:00 am — 10:30 am (BSCS 1C), 2:00 pm — 3:30 pm (BSCS 1A), 3:30 pm - 5:00 pm (BSCS 1B) Name of Faculty: May Ann A. Acera Contact Details Email: mayannaacera@gmail.com Mobile Number: 0956-598-1813 FB Account: May Ann A. Acera © Consultation Day: MW Time: 1:00 PM-2:00 PM Learning Management System Edmodo, Google Meet Assessment with Rubries Students will be assessed in a regular basis thru chapter tests using asynchronous modalities or submission of exercises. Rubrics ate also provided for evaluation of individual outputs. ‘Major examinations will be given as scheduled. The scope and coverage of the examination will be based on the lessons/topics as plotted in the course syllabus.Module Overview Introduction Computer science is the art of solving problems with computers. This is a broad definition that encompasses an equally broad field. Within computer seience, we find software engineering, bioinformatics, cryptography, machine learning, human-computer interaction, graphics, and a host of other fields. Mathematics underpins all of these endeavors in computer science. We use graphs to model complex problems, and exploit their mathematical properties to solve them. We use recursion to break down seemingly insurmountable problems into smaller and more manageable problems. We use topology, linear algebra, and geometry in 3D graphics. We study computation itself in computability and complexity theory, with results that have profound impacts on compiler design, machine learning, cryptography, computer graphics, and data processing. This set of course notes serves as a first course in the mathematical foundations of computing. It will teach you how to model problems mathematically, reason about them abstractly, and then apply a battery of techniques to explore their properties. It will teach you to prove mathematical truths beyond a shadow of a doubt. It will give you insight into the fundamental nature of computation and what can and cannot be solved by computers. It will introduce you to complexity theory and some of the most important problems in all computer science. This set of course notes is intended to give a broad and deep introduction to the mathematics that lie at the heart of computer science. It begins with a survey of discrete mathematics — basic set theory and proof techniques, mathematic induction, graphs, relations, functions, and logic — then explores computability and complexity theory. This subject discusses a range of mathematios topics to provide a foundation for concepts and. analysis used in computer science. It can be used by the students in computer science as introduction to the underlying ideas of mathematics for computer science. Starting with the fundamentals of logic, and finishing with Matrices. Table of Contents Chapter 1: Logic Chapter 2: Sets Chapter 3: Functions Chapter 4: Sequences Chapter 5: Coordinate Plane Chapter 6: Probability and Counting Chapter 7: Number TheoryChapter 8: Proofs Chapter 9: Recurrences Chapter 10: MatricesFundamentals of Mathematics for Computer Science Chapter 1 LogicChapter 1 Logic Introduction A propositional logic, also known as statement logic, is the branch of mathematical logic that, studies the truth and falsity of propositions. In propositional logic, the simplest statements are considered as indivisible units, and hence, propositional logic does not study those logical properties and relations that depend upon parts of statements that are not themselves statements on their own, such as the subject and predicate of a statement. Specific Objectives At the end of the lesson, the students should be able to: Define basic terms in probability and statistics. Define a propositional logic; Explain logical connectives and transform logical statements into symbolic form (or vice versa); Exemplify truth values status of a proposition and construct combined truth table; Transform conditional statements into its inverse, converse, and contrapositive; Define and use the terms: tautology, and contradiction; and Define and use the different bit operations Duration Chapter 1 Logic =6 hours (45° hours discussion; 1.5 hours assessment)Lesson Proper > A PROPOSITION is a complete declarative sentence (a sentence that declares a fact) that is either true or false, but not both, Examples: 1) Manila is the capital of the Philippines. 2) 11-2 3) 1>5 4) 242=3 Propositions (1) and (2) are true while propositions (3) and (4) are false. Consider the following sentences: 1. Isittime? 2. Pay attention to this! 3. xtl=2 4. xty Sentences (1) and (2) are not propositions because they are not declarative sentences or statements. Likewise, sentences (3) and (4) are not propositions because they are neither true or false, since the variables in these sentences have no assigned values yet. PROPOSITIONAL VARIABLES > variables that represent propositions: p, q,r, 8 TRUTH VALUES > T (True), F (False) > The truth value of a SIMPLE STATEMENT is T or F. » The truth value of a COMPOUND STATEMENT/PROPOSITION depends on the values of its simple statement and its connectives. LOGICAL OPERATORS/ PROPOSITIONAL CONNECTIVES/ CONNECTIVE > Logical connectives are words or symbols used to connect two or more sentences in a logical and grammatically valid way to produce one compound statement that takes its meaning from the original sentences as well as the logical connective used. They can be used as a means to connect two or more ideas, to compare and contrast different ideas, or to state certain conditions.Statement | Connective [ Symbol | Type of Logical Statement Not p not ap Negation. pand g ‘And pag ‘Conjunction porg Or pv Disjunction Ifp, then g If-then | p>q Conditional pif and only ifg [Ifand onlyif| po g Biconditional COMPOUND PROPOSITION > propositions built up by combining propositions using propositional connectives are called compound proposition. Examples: To understand the use of symbols in logic, consider the following simple statements. Let p: The Earth is round, 4: The Sun is cold r: Itrains in Spain The following compound statements can be written in symbolic form. 1, The Earth is round and the sun is cold. Symbolic Form: p A q 2. Bither the Earth is round or the Sun is not cold. Symbolic Form: pV (q) 3. The Earth is round, and either the Sun is not cold or it rains in the Spain. Symbolic Form: pA (>qV 1) 4, If the Earth is round, then it rains in Spain. Symbolic Form: p> r 5. The Earth is round if and only if it rains in Spain Symbolic Form: pr ‘The following symbolic forms can be written in compound statement. L sreCpAg Compound Statement: It docs not rain in Spain if and only if the earth is not round and the sun is cold, 2(Ap)or Compound Statement: If the sun is cold and the earth is round, then it rains in Spain. 3.Cavn-p Compound Statement: If either the Sun is not cold or it rains in Spain, then the Earth is not round.4.rv(Cahp) Compound Statement: Either it rains in Spain , or the Sun is not cold and the Earth is not round S.Cpynea ‘Compound Statement: Either the Earth is not round or it rains in Spain if and only if the Sun is not cold. TRUTH TABLE > It is a table that shows the truth value of a compound statement for all possible truth values of its simple statement. > Truth tables can also be used to display various combinations of the values of two propositions p and q. The rows of the table will correspond to each truth combination of p and q so there will be 252-4 rows. T 2'=2 (1 True & 1 False) E <4 (2 True & 2 False) T4144 wy AM a2'=8 (4 True & 4 False) add tea a a tam Fatt aa tama am ada NEGATION =p ~ Ifp is T then its negation is F . - Ip is F then its negation is T. fF CONJUCTION p Aq =p Aq is T (True) if and only if p and q are both true, otherwise itis F (False). ed ae ee Se ate T F E FDISJUNCTION p V q =pVq is T (True) if and only if p or q (or both of them) are true. mo) aa444/= pe | aa4a74 CONDITIONAL STATEMENT/IMPLICATION p — q = p—q is only F (False) when p is true and q is false, otherwise it is T (True). iste Jab Ri eee en mt) Tea 4404 BICONDITIONAL p+ q orp 4 =p q is T (True) if and only if p and q are both true or both false. iy I Gal eu a a T F i eee F Examples : Write each sentence in symbolic form and state whether the statement formed is T or F. Use p,q, and ras defined below.p: It is raining. (T) 4g: Itis cold. (F) 1 Today is Friday. (T) 1 Itis raining and it is cold. Symbolic form : p Aq Truth Value : F 2. Itis raining or Symbolic form : pV q cold. Truth Value : T 3. If today is Friday, then it is raining. Symbolie form : r— p Truth Value: T 4, It is raining if and only if today is Fridav. Symbolic form : p +r Truth Value: T 5. If today is Friday, then itis not raining ‘Symbolie form : r—~p Truth Value: F Write the given statement in symbolic form and construct the truth table. p: Stephen Curry is a football player. 4: Stephen Curry is a basketball player. : Stephen Curry is a rock star. Stephen Curry is a football player or a basketball player, and he is not a rock star. P 4 r SOLUTION: SYMBOLIC FORM: (pV q)A-rA Sy ek tee | | } el aL mn I i F f af iE - 7 1 T iE Tr aE 1 F 7 F iE T 1 T B E AW a. iB F E TL 1 Tr Fr a Ip Up ot Ip F F Hi E Ei 1 Tt F STATEMENTS RELATED TO THE CONDITIONAL STATEMENT > Converse- The converse of pq is formed by interchanging p with q. q—>p > Inverse: The inverse of pq is formed by negating both p and q. “p—>"q > Contrapositive: The contrapositive of pq is formed by negating both p and q and interchanging these negated statements. “q—>"p Truth Table for related statements. Examples: Write the converse, inverse, and contrapositive of a) If mZA is35, then 2A is an acute angle.b) Ifyou are an Olympian, then you are an athlete. Solution (a.) q-p: If ZA is an acute angle, then mzA is 35. “pq: If mZA is not 35, then 2A is not an acute angle. “q-’p: If 2A is not an acute angle, then mZA is not 35. Solution (b.) q~p: If you are an athlete, then you are an Olympian. pq: If you are not an Olympian, then you are not an athlete. “q-> p: If you are not an athlete, then you are not an Olympian. TAUTOLOGY, CONTRADICTION and CONTINGENCY TAUTOLOGY. > A compound proposition that is always true no matter what the truth values of the propositions that occur in it, is called TAUTOLOGY. Example: PY~p CONTRADICTION, > A compound proposition that is always false is called CONTRADICTION. Example: pA~p[cee ieee eevee ie F F F T F CONTINGENCY » A compound proposition that is neither a tautology nor a contradiction is called CONTINGENCY. Example: @>4)> (Aq) fa aecne Po a oT tt a7 714 Na AS Example State whether the given proposition is a TAUTOLOGY, CONTRADICTION, Or a CONTINGENCY by constructing the truth table. e-go(4>~) Solution Bod Too Se F F 7 T ae F oF: F < Fe - F ik tT a F; av T fog 7 1 T eBIT OPERATION Computers represent information using bits. A bit (short for binary digit) is a symbol with two possible values, 0 and 1. By convention, 1 represents T (true) and 0 represents F (false). replace true by 1 and false by 0 in logical operations. BITWISE AND -if both of the bits are 1, the result on that position is 1. vvvyv BITWISE OR -if any one of the bit is 1, the result on that position is 1. iy | C Ma o 1 1 i 0 1 os 1 1 0 0 0 BITWISE XOR the bits are different, the result on that position is 1.A BIT STRING is a sequence of zero ot more bits. The length of this string is the number of bits in the string. Example: 1010 , the length is 4. The bitwise AND, bitwise OR, and bitwise XOR of two strings of the same length are defined as the strings that have as their bits the connectives OR, AND, XOR of the corresponding bits in the two strings, respectively. Example: Consider two bit strings 01101 10110 and 11000 11101. Find (a) bitwise AND, (b) bitwise OR, and (c) bitwise XOR Solution: Osea (0 0) ee 0) Ostet e0 BitwiseAND: 0 1 0 Oe ae oe BitwiseOR: 1 1 ccooc o BitwisexoR: 1 0 1Fundamentals of Mathematics for Computer Science Chapter 2 SetsChapter 2 Sets Introduction The concept of a set underlies most of modem mathematics and much of computer science. To use sets as a foundation for all the other structures in this text, we first need to understand both. the language used to describe sets and the operations normally associated with sets, The language of sets is very precise. When we use this language carefully, we gain precision in expressing problems and describing solutions to problems, Understanding basic operations on sets and the properties of these operations is a model for the approach that is used to introduce most other discrete structures in this text. Specific Objectives Atthe end of the lesson, the students should be able to: - Define and represent Sets; - Use set notation, including the notations for subsets, unions, intersections, differences, complements, cross (Cartesian) products, and power sets; and ~ Identify and use the different set operations. Duration Chapter 1: Sets =5 hours (3.5 hours discussion; 1.5 hours assessment)‘Lesson Proper Set ‘A set Collection of well-defined distinct object. A set is well-defined if we can tell whether ‘a particular object is an element of that set. The word ‘distinct’ means that the objects of a set must be all different. This means that {1, 2, 3} is a set but {1, 1, 3} is not because 1 appears twice in the second collection. It is often specified with curly braces { }. Normally sets are denoted by capital letters of English alphabet like A.B,C\D,...X,YZ Examples: 1. S= {1,2,3,4,5} 2. V={a,e,i,0.u} 3. The set of even integers between 2 and 10. Element > members of the set > the objects used to form a set. > written in any order and are not repeated. > written inside a pair of curly braces separated by commas. > If the elements of the sets are alphabets then these elements are written in small letters. Examples: In the given set : V={a,e,i,0,u} , the elements are a.e,,o,u - written inside a pair of curly braces separated by commas. Some of the different notations used in sets are:Representation of Sets > Descriptive form well-defined description of the elements of the set is given and the same are enclosed in curly brackets > Set Builder form = arule, or the formula or the statement is written within the pair of brackets so that the set is well defined. In the set builder form, all the elements of the set, must possess a single property to become the member of that set. - In this form of representation of a set, the element of the set is described by using a symbol ‘x’ or any other variable followed by a colon The symbol *:' or ‘|" is used to denote such that and then we write the property possessed by the elements of the set and enclose the whole description in braces. In this, the colon stands for ‘such that” and braces stand for ‘set of all’. > Roster form = elements of the set are listed within the pair of brackets { } and are separated by commas Examples: 1. Descriptive form: {V is set of all vowels of the English alphabet} Set Builder form: V= {x: x isa vowel of the English alphabet} Roster form: V= {a,¢, i, 0, u} 2. Descriptive form: {Tis a set of integers lying between -2 and 3} Set builder form: [= {x : x € I, -2 The number of distinct elements in a finite set is called its cardinal number. > Itis denoted as n(A) and read as ‘the number of elements of the set’. Examples: 1. Set A= {2, 4, 5, 9, 15} has 5 elements. ‘Therefore, the cardinal number of set A = 5. So, it is denoted as n(A) = 5. 2. X= fletters in the word MALAYALAM} Then, X= (M, A, L, Y} Therefore, cardinal number of set X= 4. So, n(X)=43. P= {x|x €Nand x? <30} Then, P= {1, 2, 3, 4, 5} Therefore, cardinal number of set P= 5. So, n(P)=5 Types of Set Empty Set/Null set/Void Set > set which does not contain any clement > denoted by 6 and is read as “phi” > Inroster form, 0 is denoted by { } Examples: 1, A= (x: xis amonth containing 32 days} A= ()orA=0 2. The set of whole numbers less than 0. S-{} orS=0 Note: O# (OF {0} is a set which has one element 0. The cardinal number of an empty set, ie., n(@)=0Singleton Set > Asset which contains only one element is called a singleton set. Examples: 1.A= (x: x Nand x*=4} A=(Q} 2. B= (x: x is a whole number, x <1) B=(0} Finite Set > A set which contains a definite number of elements is called a finite set. > Empty set is also called a finite set. Examples: 1. The set of even numbers between 2 and 10. 2. V=fa,ei,o,u} 3, A={ Monday, Tuesday, Wednesday, Thursday, Friday} Infinite Set > The set whose elements cannot be listed. > Set containing never-ending elements is called an infinite set Examples: 1. Set of even integers. 2. A= (x: x€N,x>1} 3. Set of all points in a plane. Note: Alll infinite sets cannot be expressed in roster form. Equivalent Set > Two sets A and B are said to be equivalent if their cardinal number is same, ie., n(A) = n(B). > The symbol for denoting an equivalent set is “+" or Examples: 1. A=(a,¢,i,0,u) BR(1,2,3,4,5} n(A=5,n(B)=5 Therefore, AB. 2.A=(1,2,3} B= {par} n(A)=3 n(B) = 3 Therefore, A> B Equal Set > Two sets A and B are said to be equal if they contain the same elements. > Every clement of A is an element of B and every element of B is an element of A. Examples: LA={p.ans} B= {p,s,1,q} Therefore, A= B 2, B={4,2,1,3} A is set whose members are the first four positive whole numbers. = 1,2,3,4 ‘Therefore B=A Subset > — If and B are two sets, and every element of set A is also an element of set B, then A is called a subset of B and we write it as A ¢ B. Exampl 1, Let A= (2, 4, 6} B= (6,4,8,2) Here A is a subset of B; ASB Since, all the elements of set A are contained in set B. 2. X= (7,8,9} and Y=(7,8,9,10) ‘Therefore X is a subset of Y; X ¢ Y. Note: (i) Every set is a subset of itself ie, X © X for any set X. (ii) ‘The empty set is a subset of any set (ii) If X¢ Y and Y¢ X, Then X=Y.(iv) Every set (except {} ) has at least two subsets , {} and the set itself Super Set > — Whenever a set A is a subset of set B, we say the B is a superset of A and we write, B 2A Examples: A= {a,¢, i, 0, u} {A,B,C scsnssny 2) Here A CB, A is a subset of B but B 2 A, B isa super set of A. Proper Subset > If A and B are two sets, then A is called the proper subset of B if A ¢ B but B 2 A(A #B). > The symbol °c" is used to denote proper subset. Symbolically, we write A cB. Examples: B2A Therefore, Ac B 2, X={5,7,8} Y=(5,6.7,8} xXcY Y2x Therefore X is a proper subset of Y. Power Set > The set of all subsets of A is said to be the power set of A. & It is denoted by P(A). > — Number of elements of P(A)=n[P(A)]=2" .m=n(A) Examples: 3,4} n[P(A)]-2°=4 The subsets of A are { }, {-3}, {4}, (3,4) 1. LetPA (8, £3}, (4), £3,4)} 2.A= {p,q} n[P(A)]=2?=4 P(A) = (6, fp}, {a}, (Pa) 3, A={5,6,7) n[P(A)]=2°=8 P(A)= (, {5}, (6), {7}, {5,6}, {5,7}, (6, 7 {5.6.73 Universal Set > — Asset which contains all the elements of other given sets is called a universal set. > The symbol for denoting a universal set is U. Examples: IfA= (1, 2, 3}, B= (2, 3, 4}, C= (3, 5,7} then U={1,2, 3,4, 5,7} Complement Of Sets > — The complement of set A, is the set of all elements in the universal set that are not in A. > It is denoted by A’ Examples: 1. LetU= (1, 2, 3,4, 5,6, 7} A= (1,3,7} find A’ A'=(2, 4,5, 6} 2. Let U= {2, 4, 6, 8, 10, 12, 14, 16} A= (6,10, 4, 16} find A’. A'= (2, 8, 12, 14}OPERATIONS ON SET eel Cin Union » — Union of two given sets is the smallest set which contains all the elements of both the sets, » — To find the union of two given sets A and B is a set which consists of all the elements of A and all the elements of B such that no element is repeated. > The symbol for denoting union of sets is “U’. Examples: A=(1,2,3} B={1,3,5} C-2,3.4,5} a) AUB={1,2,3,5} b) AUC={1,2,3,4,5} ©) BUC= {1,2,3,4,5} Intersection of Sets > Intersection of two given sets is the largest set which contains all the elements that are common to both the sets. > The symbol for denoting intersection of sets isExamples: A=(1.23) B{13,5} C=(2,3,4,5} a) ANB= {1,3} b) ANC= 2,3) c) BNC=3,5} Difference of Sets > If Aand B are two sets, then their difference is given by A - B or B- A. Examples: A=(2,3,5,7,11} and B= (5,7,9,11,13} a) A-B= {2,3} b) B-A=(9,13} Symmetric Difference of Sets > The symmetric difference of two sets A and B is the union of their differences and is denoted by AAB AAB=(A-B)U(B-A) Examples: A~{2,3,5,7,11} and B= (5,7,9,11,13} 2,3} B-A=(9,13} AA B= (2,3, 9, 13} Cartesian Product > — The Cartesian product of two sets A and B (also called the product set, set direct product, or cross product) is defined to be the set of all points (a,b) where a € A and b € B. > — Itis denoted Ax B. Examples: ‘A= {a,b,c} and B=(1,2}, n(A)=3 and n(B)= 2, n(A x B) = 6 ordered pairs Ax B= ((al), (2.2), (51), (0,2),(6,1)(62)}For3 sets AxBxC Example: A= {abc}, B={1,2}, and C= (3,4} n(A x Bx C)=12 AXxB= {(a,1), (2.2), (b,1), (0.2).(61),(6,2)} (AxB) x C= ((a,1,3), (a,1,4), (2,2,3), (a,2,4), (bs1,3), (b,1,4), (b,2,3), (b,2,4), (C13), (61,4), (2,3), (€,2,4)}Fundamentals of Mathematics for Computer Science Chapter 3 FunctionsChapter 3 Functions Introduetion In our daily living, we often encounter quantities that do come in pair. For example, the number of kilograms of rice and the amount of money needed to purchase. Furthermore, the number of miles a car travelled and the liters of gasoline consumed. Likewise, the plant growth in centimeters and the amount of rainfall it received. When one quantity changed, the other also changed. These pairings are best represented as ordered pairs. Tin the study of mathematics, functions provide an important unifying concept. Functions are also familiar in computer science as components of programs that formalize the relationship between the input and the output for a computation. Since functions are special kinds of sets or relations, we will study them here using the ideas introduced in Chapters 2. First, we define both functions and several fundamental properties of functions. Next, we deal with operations on functions, and basic properties of functions resulting from the operations introduced are explored, Specific Objectives ‘At the end of the lesson, the students should be able to’ - Define function and identify the types and its properties; = Define the term and find the inverse of a given function; and Find the composition of two functions. Duration Chapter 3: Functions =5 hours 8.5 hours discussion; 1.5 hours assessment)Lesson Proper FUNCTIONS In mathematics, a function is a relation between a set of inputs and a set permissible outputs. Functions have the property that each input is related to exactly one output. Let A and B be two sets. A function from A to B, denoted f: A — B , is an assignment of exactly one element of B to each element of A. We write fla) = b to denote the assignment of b to an element a of A by the function f- ‘A function is sometimes called a map or mapping ‘A function f: A > B is effectively a special kind of relation between A and B, which relates every a € A to exactly one clement of B. That element is denoted by fx) Domain and Codomain > If fis a function from A to B, then set A is called the domain and set B is called the codomain. A B LH Domain = }1,2,3} Codomain a, b,c, d} Image > The elements in Set B that are mapped to the elements in Set A. A B a B b 2 c : d Image: image of | is a, 2 isd, and 3 is bPre-Image > The elements in Set A that are mapped to the elements in Set B. A aoe Pre-image: pre-image of a is 1. b is 3, and d is 2 Range > The set of all images of Set A is called range of a function, A B Range: {a, b, d} > Function has to be single valued = an input “a” cannot produce two different results, Example of Funetion: {2.4), G.5), (7.3)} “2 is related to 4, “3 is related to 5”, and “7 is related to 3”. Not Function: {(2,4), (2.5), (7.3)} Tt is not a function because (2,4) and (2,5) means “2” could be related to 4 and 5. Classification Of Set Mapping (Function) 1. Qne-one Function (or Injective Function)> A function fA — B is said to be a one-one (or Injective) function, if for each element of A, there is a different element of B. Example: A B a 1 b mle? 3 a 2. Many-One Function > A function f, A — B is called a many to one funetion if two associated to the same element of set B. or more elements of A are Example: A B -a 1 Tb - c 3. Onto Function (or Surjective Function) > A function f. A — B is called an onto funetion if each element in the co-domain has at least one pre — image in the domain. > All elements in Set B are covered.4. Qne-One Onto Function (Bijective Function) » Iff A — Bis both one-one and onto then it is called a one-one onto (bijective) function. A B a 1 j—a — _——b 3a— J oe To evaluate a function, substitute the input for function’s variable. Replace x with the given number or expression. Evaluating of Funetion Examples: 1. f(x) =3x-5, find (4) Solutio £4) =3(4)- 5 =12-5 (4) = 2. f(x) =x? -2xH1 , find f(2x) Soluti f(x) = (2x)? -2(2x)+1 f(x) = 4x? 4x H1 3. f(x) = 3x3 +1, find £2) Solution: £2) =3Q)3 +1 aInverse of a Function If f A — B is a one-one onto (or bijective) function and if f(x) = y, where x € A, y €B then £!: B— A defined by f! (y) =x, is known as inverse function of f For example: If A= (2, 4, 6} and B= (5,7, 9} and £ A — B is given by f(2) = 5, (4) = 7 and £(6) = 9. Find f! Solution: Given that (2) = 5, f(4) = 7 and f(6) = 9, Hence f= {(2,5), (4, 7), (6,9)} Hence f) = {(5, 2), (7, 4), 9, 6) > function f(x) is one-one if f(x1)= f(x2), then x1 = Xo ‘Example: Prove that f(x) = 3x-2 is one-one, flx)= fixe) 3xi-2=3m-2 3m-2+2=3m 3x1=3x2 xI=X Example: Find the inverse of : 1. f(x) =3x-2. Solution f(x) =3x-2 oy eke Rewrite f (x) as y———+ v = 3x —2 swap xandy ——+ x= 3y—2 Solvefory ——+ 3y x By =x42 PO=Z2 oS Solution 2x 3 xy+2x=2y-3 (@= 347 20-3, y@—2)=-2x-3 ~2x-3 f@)= x2 x(y +2) = 2y-3 Composition of Function Given 2 functions f and g, the composite function denoted by fo g (read as “fof g”, “E composition g”, or “f circle g”) is defined by (fo g)(x) = fig(x)) Let A = {1,2,3} and B= {a,b,c,d} gAGA 133 21 32 £ASB I>b doa Bod Find (fo g): ASB Answer lod 2b BoaExample: 1. {x)= 2x and g(x) = x’, find (Fo g(x). Solution: (£0 gx) = f (x) =2(24) (f.0 g(x) = 2x? 2. f(x)= 2x+1 and g(x) = 6x + 4, find (g o f(x). Solution: (go N(X)= f @x+1) (2x +1) +4 12x +644 (fo g(x) =12x + 10 3. f(x) = 2x~1, find (Fo )0x) Solution: flx)=2x-1 2x-1 res op eo-F (FH) -2(82)—1 =xt1-1 (For ey=x > Two functions f and g are inverses of each other if: * (fo g)(x)=x and * (gof(x)=x. Example: Prove if the following functions are inverses of each other.1. f(x) =3x and g(x) =F Solution: (foao=F (2) -3() (fo g\xy=x (0 \x)=f Gx) = 3 @of)ax 2.) = 2x-2 and g(x) = Solution: oa =F () -2(22)-2 =x+2-2 (fo gyx)=xFundamentals of Mathematics for Computer Science Chapter 4 SequencesChapter 4 Sequences Introduction We will discuss in this module the definition and elements of sequence, distinguish geometric and arithmetic sequence, and identify and use the terms in finding the missing value in arithmetic and geometric sequence. Specific Objectives ‘At the end of the lesson, the students should be able to: - Define sequence and its elements; - Distinguish between geometric and arithmetic sequence; and ~ Identify and use the terms in finding the missing value in arithmetic and geometric sequence; Dura Chapter 1: Sequences =4 hours (2.5 hours discussion; 1.5 hours assessment)Lesson Proper ‘A sequence is an ordered list of numbers, called terms, that may have repeated values. The arrangement of these terms is set by a definite rule. There are many types of sequence but this chapter will only discuss two sequences, the Arithmetic and Geometric Sequence. Arithmetic Sequence > Itisa sequence in which each term is obtained by adding a constant d to preceding term. The constant number d is called the common difference. > The nth term of the arithmetic sequence is defined as On, = + (n= 1)d Where a, the nth term in the sequence y= the first term in the sequence n= the number of term d= the common difference Examples: 1. Find the 5th term of the arithmetic sequence 5, 8, 11, 14,, Solution: a,=5 d=3 n=5 a, =a, + (n— 1d as = 5+ (5-193) as =5 + (4)(3) as =5+12 as =17 2, In the arithmetic sequence where a; = 10 and d= 6 , which term is 1247 n=? Solution: a, =a, + (n= 1)d 124 = 10+ (n- 1)(6) 124 = 10+ 6n-6124 =4+46n 124-4 = 6n 120 = 6n 206 6 6 n= 20 3, Find the 15" term of the arithmetic sequence whose 1* term is 7 and 5" term is 19. a, =a, +(n—1d 19=74(5-1)d 19=7+(4)d 19=7+4d 19-7=4d 12=4d sd 4 4 d=3 a, =a, + (n= 1d a5 =7 + (15-198) ays = 7 + (14)(3) ays =7 +42 a5 = 49 4, Find the 1* term of the arithmetic sequence whose 33" term is 80 and common difference which is equal to 2 Solution: yg = 80a,=? ay = a; + (n= 1)d 80 = a, + (33—1)(2) 80 = a, + (32)(2) 80 = a, + 64 80-64=a, 80-64=a, a, =16 > To find the sum of the ist nth term of the arithmetic sequence is given by: Su = (@y + ay) 5 if dn is given Sn =F [2a, + (n— 1d] ; ify is not given Where Sq = the sum of the fist nth term = the nth term in the sequence ,= the first term in the sequence n= the number of term, d= the common difference Examples: 1. Find the sum of the first 100 positive integers. Solution: Syn? n Sn = 5 (ai + an) 100 Stoo = FG + 100) Sto9 = 5,0502. Find the sum of the first 12 terms of the arithmetic sequence 50, 47, 44, 41, 38, Solution: a, =50 3 n= 12 Sy? Su= Flea, +(n-1d] Sn = F260) + (12—1)(-3)] Sn = 6[100 + (11)(-3)] Sp = 6(100 — 33) Sy, = 6(67) Sy = 402 Arithmetic Mean > Itis the terms between any two terms Examples: Insert 3 arithmetic means between 18 and 30. Solution: a, =18 a, 30 n=5 a a, =a; + (n—1)d 30=18+(S—1)d 30=18+ (4)d 1943-21 30 = 18+ 4d Ziman 2443=27 30-18 =4d 27+3=30 12=4d 12_ 4d ae d=318, 21,24, 27, 30 2. Insert 4 arithmetic means between 7 and 37. Solution: a, =a, + (n-1)d 37=7+(6-1)d 37=7+(S)d 1+6 B+ 19+ 37=7+5d 25+6=31 eee 31+6=37 30 =Sd 30 5d 5. 5 d=6 7, 13,19, 25, 31, 37 Geometric Sequence > Itis.a sequence in which the ratio of each term to the preceding term is the same throughout. Geometric Sequence ‘Common Ratio (r ) 1,2,4, 8, 2 3,9, 27, 81, ... 3 5, 10, -20, 40, ... 2 > The nth term of the geometric sequence is defined as a, = ay rt Wherea,= the nth term in the sequence a,= the first term in the sequence n= the number of term r= the common ratio } To find the sum of the 1st nth term of the geometric sequence is given by: _ad-r) Sy Where Sy = the sum of the first nth term a,= the first term in the sequence n= the number of term r= the common ratio Other Formulas wok dn a Where r= the common ratio n= position of dy in the sequence a, = a given term in the sequence k = position of ay in the sequence a, = a given term in the sequence Where a, the nth term in the sequence y= the first term in the sequence n= the number of term r= the common ratio_SxA=7) a4 Where a= the Ist term in the sequence Sq= sum of the sequence r= the common ratio n= the number of term. Examples: 1, Find the 8th term of the geometric sequence 5, 15, 45, 135, Solution: a,=5 1-3 n=8 a, =a,- 7" ag=5 + 3° ag=5° 37 ay = 5 +2187 ag = 10935 2. Find the 6th term of the geometric sequence 4, 2, 1, 0.5, 0.25, Solution: a=4 r 1 2 n=6dg = 0.125 3. Given a geometric sequence with a, = —4 and a, = 32. Determine the value ofr. Solution: a,=~-4 a, = 32 “E ae ay + [32 r =4 r=V-8 r=-2 4, Given a geometric sequence with a, = 15 and ag = 10 935. Determine the value of r. Solution: a, =15 a, = 10935 r= 475 r=3 5. Determine the sum of the geometric sequence 3, 6, 12, ... 1563. Solution: a,=3 y= ay rt 1563 =3 - 2"-+3(1— 1024) 1 3(—1023) Sy = 3069 6, Determine the sum of the geometric sequence 5, 15, 45,...405 Solution: a=5 r=3 n=? Sy=?_a(i=r*) =o, 51-35) 1-3 243) is 5¢ 5 5, = 507242) =2 1210 -2 Sy = 605 7. Find the 1* term of the geometric sequence when the 5" term is 405 and has a common ratio of Solution: a,,= 405 m5 3 8. Find the 1* term of the geometric sequence when the sum of the 5 terms is 605 and has a common ratio of 3. Solution: Sy = 605 m3 m5 a=?T= 605(1—3) a= Ts 605(—2) 1 TT 748 -1210 a> a a,=5Fundamentals of Mathematics for Computer Science Chapter 5 Coordinate PlaneChapter 6 Coordinate Plane Introduction Historically, maps played a vital role for travelers and explorers. This map contains vertical and horizontal lines called longitude and latitude, respectively. In this modern day, map applications and the Global Positioning System (GPS) in your mobile phone still utilize the use of horizontal and vertical lines to give you the exact location or coordinate of the place you are looking for. In this lesson, you will leam the concept of Rectangular Coordinate System, plotting points, and locating coordinates which may help you in understanding maps, distance, economics, research and other daily activity. Specific Objectives ‘At the end of the lesson, the students should be able to: Identify and describe the Cartesian coordinate system; Use Cartesian coordinate system to plot points; Find the slope of the given points using Cartesian coordinate plane; Identify and use the formula on finding the distance of the given points in the plane, and Identify and use the formula on finding the midpoint of the given points in the plane. Duration Chapter 5: Coordinate Plane =4 hours (2.5 hours discussion; 1.5 hours assessment)Lesson Proper Cartesian Mathematics was invented by (and is named after) French Philosopher, Physiologist, and Mathematician Rene Descartes. “The Cartesian Plane is composed of two perpendicular lines that meet at the point of origin (0,0) and divides the plane into four regions called Quadrants. It is composed of infinitely many points. Bach point in the coordinate system is defined by an ordered pair of the form (X.Y). ‘The first coordinate of a point is called the x-coordinate or abscissa and the second coordinate is called the y-coordinate or ordinate. Also called: x-y plane Rectangular Coordinate System trac co I usdeantiv cI ong (0.0) Plotting Points in the Cartesian Plane 1, Always start at (0,0) 2. Remember the directions of both x and y-axis. 3, x-axis goes left and right 4, y-axis goes up and down Examples: 1. Plot the point (4,3) in the Cartesian plane.cols) where x; 4x2 Definition: In a coordinate plane, the slope of a line is the ratio of its vertical rise over its horizontal run, m =" Formula: The slope m of a line containing two points with coordinate (x,, ys)and (¢2,¥2) is given by the formula m =Describing lines: + Lines that have a positive slope rise from left to right, ~ Lines that have a negative slope fall from left to right. es “ Lines that have no slope (the slope is undefined) are vertical. + Lines that have a slope equal to zero are horizontal. §—§ <> ‘Examples: 1. Find the slope between two points (0,3) and (-4, 0) Solution: rise Ay -3_ 3 nee ee run ax 4 4 YerIn aH,_3 maa 2. Find the slope between two points (1,2) and (3, -2). Solution: 3. Find the slope between two points (3,5) and (4, -5). Solution: rise Ay mom heo m=0 4. Find the slope between two points (3,4) and (3, -2). Solution: m = undefined Distance Formula The distance d between any two points (23,7) and (x2, Ya) is given by the formula 2-91)? + G2 —x1)?. Examples: What is the distance between (2, -6) and (-3, 6) ?m=2 n=-6 m=-8 n=6 Solution: 2-1)? + 2-1)? = RCO CSAS = SCPC = V2) + 5)? = VI44425 =v169 d=13 2. Find EF and GH. Then determine if EF = GH. Solution: E(21) F(5,5) G (1, -2) HG,1) For EF: xy =-2 net m=-5 ye =5 FF = (G-0? +-5-COP = VG=1 4 SHRP= VOC =viet9 =v25 EF=5 For GH: my =-1 wW=n2 x2 =3 y=1 GA = J Car + B- COP =VG+2 + B+? =VGP+ OF =V9+16 =Vv25 GH=5 Since EF = GH, EF = GH. Midpoint Formula The midpoint formula is used to find the coordinate that is the exact midpoint between two other coordinates. + The x-coordinate of the midpoint is found by ==** + The y-coordinate of the midpoint is found by == 4 So, the coordinate of the midpoint is (2 ,£2*) Examples: 1, What is the coordinate of the midpoint between (1, 2) and (-5, 6)? Solution: w=6 Fatt, 14-5) x-coordinate: “7 vatys _ 612 8 y-coordinate: aE 5 4 So, the midpoint is located at the coordinate (2,4)2. M is the midpoint of XY. X has coordinates (2,7) and M has coordinates (6,1). Find the coordinates of Y. Solution: Step 1: Let the coordinates of Y equal to (x, y) Step 2: Use the Midpoint Formula: (6,1) = (, 7%) x-coordinate: 6 = = (2) =24x 12=2+x 12-2=x x=10 y-coordinate: 1= 4% @aQ=7+y 2=7+y 2-7=y y=-5 the coordinates of Y are (10, -5) Y Checking: sates 2410 ¥ — x-coordinate: == = Y _y-coordinate: *C2 ¥ — Midpoint: (6,1) 3, S is the midpoint of RT. R has coordinates (-6, -1) and § has coordinates (-1,1). Find the coordinates of T. Solution: Step 1: Let the coordinates of T equal to (x,y) sete, =n) rae aa Step 2: Use the Midpoint Formula: (-1,1)= (- x-coordinate: — (Q)(-D=-6+x -2=-6+x -2+6=xx=4 y-coordinate: 1 = 2 Qa)=-1+y 2=-1+y 2+1=y ve3. the coordinates of T are (4, 3)Fundamentals of Mathematics for Computer Science Chapter 6 Probability and CountingChapter 6 Probabi ity and Counting Introduction Counting techniques are also used in the study of probability to determine the number of events in a sample space and the number of successfl outcomes for an experiment. Probability theory commonly uses these counts to assess the likelihood of a particular event. In computer science, elementary counting ‘methods provide useful tools and techniques for dealing with problems such as the enumeration of all possible states that must be considered in proving that a program is correct. More generally, counting ‘methods are used at several stages in the development of a correct and efficient program. For example, a first decision about which algorithm to use in a particular application is often based on knowing how the various alternative algorithms compare with respect to running time or storage use. A step in the process of determining the running time or the storage use of a program often includes one or more counting arguments. In this chapter, we discuss four major topics. First, we introduce the two fandamental counting principles: the Multiplication Principle and the Addition Principle. Second, we introduce permutations and combinations, which deal with the ways of selecting subsets of a set in which the order of selection of the elements may-or may not-be important. With these preliminaries, wwe introduce the final two major topics: The first involves counting the number of selections possible fiom collections with repeated elements; the second involves combinatorial identities, such as the binomial theorem. Specific Objectives At the end of the lesson, the students should be able to: - Define and use probability concepts to solve problems, - Demonstrate knowledge and understanding of the probability of events; ~ Apply the fundamental principle of counting; ~ Differentiate permutations from combinations, and - Perform operations on problems involving permutations and combinations Duration Chapter 6: Probability and Counting =6 hours (45° hours discussion; 1.5 hours assessment)Lesson Proper Probability Probability is a word related to chance or likelihood. It measures the likelihood that a particular event will or will not happen. It is number which ranges from 0 to 1. An event having a probability of 1 indicates that the event will happen with absolute certainty while probability of 0 indicates the impossibility of the events to happen that there is no chance or that the event is impossible to happen. Experiment » It isan activity which can be done repeatedly under similar conditions and which can result in an outcome. Examples: O Tossing a coin O Casting/ Rolling a die Outcome > The result of an experiment. Examples: An experiment of tossing a coin has two possible outcomes = Head (H) and Tail (T) O Ifasingle die is cast, there are six possible outcomes. =1,23,4,5,6 Sample Space > A set of all possible outcomes of a random phenomenon/ an experiment, Examples: O s={HT) O $= {1,2,3,4,5,6} Event > A set of happenings or outcome Examples: Q Casting a Head or a Tail Event = {(H.T), (T,H)} Q Rolling a sum of 5Event= {(1,4), (2,3), (3,2), (4,} > If there is only one outcome, the event is called a simple event, ‘The Probability that an event will happen is denoted by P(E) and the Probability that it will not happen is denoted by P(E’). The sum of the probabilities of the different outcomes is equal to 1, That is, PE) + PE 1 For instance, in a single toss of a balanced coin, the probability that a head occurs P(H) and the probability that a tail is up P(T) is P(H)=%, PCT) =% P(H) + P(T)=1 Ath=1 Similarly, if the probability that it will rain is 0.4, then the equation implies that the probability that it will not rain is 1-04=06 P(R) + PR’ 0.4+PR?)=1 P(R’)=1-0.4 PR’)=06 Probability of an Event > The Probability of an Event , P(E) is defined as the proportion of times a favorable event will occur in a long series of repeated trials. number of favorable outcomes number of possible outcomes P(E) = Examples: 1. A fair dice is cast. What is the probability of rolling a sum of 5? Solution: Sample Space= { 1,2,3,4,5,6}, N-6 Sample Space={(1,1), (1,2), (1,3),..-s(5,6), (6,6)}; N=36 Event= (1,4), (2.3), (3.2), 4,1}, n(E)=4 number of favorable outcomes P©) = Sumber of possible outcomesP(sum of 5) = Zor 2 2. Two coins are cast. Find the probability of obtaining a head or a tail? Solution: The two coins can result in 4 ways. The event has two sample points namely: (H.T), (TH) ‘Sample Space={H,T), N=2 Sample Space= {(H,H), (H,T), (T,T), (1,H)}; N=4 Event = ((H,T), (T,H)}, n()=2 number of favorable outcomes number of possible outcomes P(E) = P(head and tail) =? or i 3. A box contains 10 white and 5 red balls. What is the probability that a, Itisred? b. Itis not red? Solution: a. P(red) = 573 = 7g 10. 2 1 10+5 b. 1 P(not red) = P(white) = This can also be solved by b.2 P(not red) = 1— P(red) Mutually Exclusive and Non-Mutually Exclusive Events > Twoevents are mutually exclusive if they have no point in common. These are the events that cannot happen simultaneously. For example, drawing an ace and a face card from an ordinary deck of cards are mutually exclusive because it is not possible to draw an ace which is a face card. > Non-mutually exclusive events are events that can happen at the same time. They are events with common points . For example, drawing a red card and drawing a king are non- mutually because there are two red cards that are kings. > The concept underlying mutually exclusive and non-mutually exclusive events is depicted in the Venn Diagram below.A B a B “Mutually Exclusive Events ‘Non-Mutually Exclusive Events Figure 1 Figure 2 Figure 1 shows two disjoint or nonintersecting circles representing two mutually exclusive events. Figure 2 shows overlapping circles indicating that the events being represented are non- mutually exclusive events The Addition Rule > If Aand B are any two events, then P(A +B) = P(A) + P(B) — P(A and B) > If events A and B are mutually exclusive events or P( A and B) is equal to zero, the above formula is reduced to P(A or B) = P(A) + P(B) Examples 1. Ifa card is drawn from an ordinary deck, find the probability of drawing a, A queen Q ora heart H b. A jack J oran ace A Solution: a. P(Q or H) = P(Q) + P(H) — P (@ and H) 4.13 1 “52 t52 52 16 4 “aD b. Recall that whenever two events are mutually exclusive, the probability of both events occurring is equal to zero. You cannot get a jack and an ace with one draw of card, So the addition rule is simplified when two events are mutually exclusive. PU or A) = PU) + PCA) oo 4 “5252om 2 52 2. A student was told that his probability of passing Statistics is 0.50; the probability that he will pass English is 0.55; and the probability of passing both subjects is 0.45. What is the probability that he will pass at least one of the two subjects? Solution: P(at least 1) = P (S or E) = P(S) + P(E) — P(S and E) =0.50+0.55 — 0.45 = 0.60 Conditional Probability > The probability that an event A occurs when it is known that some event B has occurred is called conditional probability. > This is denoted by P(A|B) which is read as “the probability that A occurs given that B occurs” or simply “the probability of A, given B. rape 5) Where: Note: P(A or B= PB or A) and P(A and B)=P(B and A), P(AIB) #P(BIA) Example 1. Consider the previous example about determining the probability that if the student passed Statistics 1, he will also pass English, Solution: P(A and B) PB) P(E and S) POS) P(AIB)=: PE|S)= Independence of Events ca Two events are said to be independence if the occurrence of one does not affect the occurrence of the other. When the occurrence of one event does affect the occurrence of the other, the two are said to be not independent on each other. > The outcomes associated with drawing a card and choosing a letter from the alphabet are considered independent events because the outcome on the card does not in any way affect the probability of choosing a letter from the alphabet, and vice versa. ThusP(Card) ==, Also P(Letter, L) = = regardless of what card is drawn no matter what the outcome on obtaining a letter from the alphabet. > The illustration clearly implies that if events A and B are independent, P(AIB) = P(A) P(B|A) = P(B) ‘The Multiplication Rule > To determine the probability of occurrence of two independent events, A and B, we employ the multiplication rule. For events A and B that are not independent, the multiplication rule is P(A and B) = P(A) - P(A|B) > When A and B are independent events, P(A|B)=P(B); hence, for independent events P(A and B) = P(A) - P(B) Examples: 1. A balanced coin is flipped twice. What is the probability that it will come up head twice? Solution: ol oh 4) P(@heads)=5 - 5= 7 0r0.25 2. A quality control expert inspects a box containing 50 cellphones and found out that 5 are defective. If two cellphones are randomly chosen, what is the probability that a. Both are defective? b. Neither is defective? c. The first cellphone is defective and second is not? Let D, = the first cellphone is defective Dz = the second cellphone is defective N, = the first cellphone is not defective Ny = the second cellphone is not defectivea P(D,and D2) = P(D;) - P(D2|D;) _ 5 4 “50 49 20 ~ 2450 2 = 3qg 07 0.0082 b. P(Nyand Nz) = P(N,) + P(N,IN,) “50 49 _ 1980 ~ 2450 = 28 or0.8082 = 7g 070. ¢. P(Dyand Nz) = P(D,) - P(N,|D,) 5 45 50°49 _ 225 ~ 2450 = 2 oro.os18 = 5g Or. Fundamental Principles of Counting Consider a lady with 3 skirts with colors namely red, blue and yellow. She has 3 pair of shoes; black, white and brown. Let us list down the possible ways of wearing her skirt with her shoes. ‘The outcomes are as follows: Red Black Red White Red Brown Therefore, there are 9 possible ways for a lady to wear her skirt and Blue Black Blue White "°° Blue Brown Yellow Black Yellow White Yellow Brown If.an event A can occur in n; distinet ways and if for each outcome of event A event B can occur in nz ways, then both can occur in (71;)(%2) ways.In the example , the lady has 3 ways of wearing her skirt and 3 ways of wearing her shoes, Therefore, she can wear her skirt and her shoes (3)(3)-9 ways, Examples: 1. In how many ways can three coins fall? Solution: A coin can fall in two ways; therefore three coins can fall in (2)(2)(2) or 8 ways 2. Trina has to choose one dessert and one viand. There are 6 choices for viands, The choices for dessert are cake and pie. In how many ways can she choose her dessert and viand Solution: ‘There are 6 ways in choosing the viands and 2 ways in choosing the dessert, therefore, Trina ccan choose her dessert and viands in (6)(2) = 12 ways. Permutation > A permutation is an arrangement of n different objects in definite order. > Consider the set A = {c, a, t}. We have the following arrangements for the elements of Set A. cat, cta, act, atc, tac, toa Therefore , there are 6 permutations. Linear Permutation > In general, the number of permutations ~P for n different object is P =n(n-1)(n— 2)... (3)(2)(1) orn! (read as ‘nfactorial’) Thus, 4!=4x3x2x1=24 By definition 0! > If n objects are to be arranged r objects at a time, then the number of distinct arrangements is given by: Examples: 1. Inhow many ways can 6 people be lined up to get in a bus? Solution: The 6 people can be arranged in 6 positions to get in the bus. There are 6 ways on filling the first position, 5 ways of filling the second position, and so on.Therefore there are 6! Or 6 x 5x 4x3 x 2.x 1= 720 ways for the 6 people to be lined up to get in a bus. 2. In how many ways can the prizes for the first and second place be awarded to 15 candidates? Solution: P= 15! poem 1s —-2)I 15 x14x 13! 13! =210 ways Circular Permutation > The number of permutations of n distinct objects arranged in a circle is (n-1)! Example: In how many ways can 6 people be arranged in a round table? Solution: @-D!=(6- =5! =Sx4x3x2x1 = 120 ways Permutations of Things Not All Different > The number of distinct permutations of n things of which n, are of one kind, nz of a second kind, ... my of the ke" kind is nt P mylngl Example: How many distinct permutations can be made from the letters of the word “SATISFACTORY”? Solution: my = 2's" mg = 2A" ng = 2"T"ny = 11" ig = 1"F” Tg =1"C" ny =1"0" ng = 1"R" nye 12! Dix 2x Qhx Ux Ux Ux 1x Ux! = 59, 875, 200 permutations Combination > A combination is also an arrangement of a set of objects but without regard to order. > The number of combinations of n distinct objects taken r at a time is Examp 1. In how many ways can 5 people be chosen from 15 people? Solution: nC; ri@—r)! = SGS— sy Six 10! = 3, 003 ways 2. Inhhow many combinations of 3 letters can be made from the letters ¢, a, and t? Solution:= 1 combinationFundamentals of Mathematics for Computer Science Chapter 7 Number TheoryChapter 7 Number Theory Introduction ‘This module will introduce you to the key concepts of modular arithmetic wo be able to perform different arithmetic operations, to find the additive and multiplicative inverses, and to apply modular arithmetic in real life problem situation, Specific Objectives At the end of the lesson, the students should be able to: Understand the key concepts on modular arithmetic; Perform arithmetic operations on modulo n; Find the additive and multiplicative inverses in modular arithmetic; and Apply modular arithmetic in solving problems and in cryptology. Duration Chapter 7: Number Theory =5S hours (35° hours discussion; 1.5 hours assessment)Lesson Proper 4 Modular Arithmetic Modulo n - Two integers a and 5 are said to be congruent modulo n, where n is a natural number, if * is an integer. In this case, we write a= b mod n. The number » is called the modulus. The statement a = b mod n is called a congruence. Examples: Determine whether a congruence is TRUE. a 29 mod 3 b. 15=4mod6 Solution: a.29=8 mod 3 Find Because 7 is an integer, 29 = 8 mod 3 is a true congruence, b. 15=4 mod 6 Find Because is not an integer, 15 = 4 mod 6 is not true. For 29 = 8 mod 3 given in example a, note that 29 + 3 (modulus) = 9 remainder 2 and that 8 +3 (modulus) = 2 remainder 2. Both 29 and 8 have the same remainder when divided by the modulus. This lead to an important alternate method to determine a true congruence. If a=b mod n and a and b are whole numbers, then a and b have the same remainder when divided by n. Examples: Using the alternate method, determine whether the following given a true congruence or not. a, 33=49mod4 b. 15=4 mod 6 Solution: a. 33=49 mod 4 33 +4=8 remainder | 49+ 4= 12 remainder 1 Both 33 and 49 have the same remainder 1 when divided by the 4 (modulus). 33 = 49 mod 4 isa true congruence.b. 15=4 mod 6 15 + 6 =2 remainder 3 4+6=O remainder 4 ‘The remainder of 15 and 4 when divided by the 6 (modulus) are different. 15= 4 mod 6 is not a true congruence, + Arithmetic Operations Modulo n Arithmetic modulo n (where n is a natural number) requires us to evaluate a modular expression after using a standard rules of arithmetic. Thus we perform the arithmetic operation and then divide by the modulus, The answer is the remainder. The result of an arithmetic operation mod n is always a whole number less than 7. Examples: Addition Modulo n 1, Evaluate (23 + 38) mod 12 Solution: Add 23 and 38 to produce 61. To evaluate 61 mod 12, divide 61 by modulus, 12. The answer is the remainder. 61 + 12=5 remainder 1 (23+ 38) mod 12=1 The answer is 1. 2, Evaluate (51 +72) mod 3 Solution: Add 51 and 72 to produce 123. To evaluate 123 mod 3, divide 123 by modulus, 3, The answer is the remainder. 123 +3=41 remainder 0 (51 +72) mod 3=0 ‘The answer is 0. Examples: Subtraction Modulo 7 1. Evaluate (33 -16) mod 6 Solution: Subtract 33 — 16 = 17. The result is positive. Divide the difference by the modulus, 6. The answer is the remainder, 17+ 6=2 remainder 5 (33-16) mod 6=5The answer is 5. 2. Evaluate (14 - 27) mod 5 Solution: Subtract 14 - 27 =-13. Because the result is negative, we must find x so that -13 = x mod 5. a13-x _ ats) ‘Thus we must find x so that the values of is an integer . Trying the whole 70312) __y number values of x less than 5, the modulus, we find that when x = : (14-27) mod 5=2 Additional Information Modulus 5 2 4 1 3 2 0 mod 5=0 Tmod 5=2 -3mod5=2 1mod5=1 8 mod 5=3 -4mod5=1 2mod5=2 9 mod 5=4 -5mod5=0 3 mod 5=3 10 mod 5=0 ~6 mod 5=4 4mod5=4 5 mod 5 -1 mod 5=4 13 mod 5=2 6 mod 5=1 -2mod 5=3 Modulus 6 0 5 1 40 mod 6 =0 7mod6=1 14 mod 6 =2 1 mod 6= 1 8 mod 6 =2 15 mod 6 =3 2 mod 6 =2 9 mod 6=3 16 mod 6=4 3 mod 6=3 10 mod 6=4 17 mod 6 =5 4 mod 6=4 11 mod 6=5 5 mod 6=5 12 mod 6 =0 -1mod 6=5 6 mod 6=0 13 mod 6=1 -2mod 6=4 Examples: Multiplication Modulo n 1, Evaluate (15 + 23) mod 11 Solution: Find the product of 15 and 23 and then divide by modulus, 11. The answer is the remainder. 15 +23 = 345 345 +11 =31 remainder 4 (15 + 32) mod 11=4 ‘The answer is 4. 2. Evaluate (33 © 41) mod 17 Solution: Find the product of 33 and 41 and then divide by modulus, 17. The answer is the remainder. 33 +41 = 1353 1353 + 17=79 remainder 10 (33 + 41) mod 17= 10 ‘The answer is 10. + Additive and Multiplicative Inverses in Modular Arithmetic Additive Inverse Recall that if the sum of two numbers is 0, then the numbers are inverses of each other. For instance, 8 + (-8) = 0, so 8 is the additive inverse of -8, and -8 is the additive inverse of 8. ‘The same concept applies in modular arithmetic, For example, (3+5) = 0 mod 8. thus, in mod 8 arithmetic, 3 is the additive inverse of 5, and 5 is the additive inverse of 3. Here we consider only those whole numbers smaller than the modulus. Note that 3 + 5 = 8; that is, the sum of a number and its additive inverse equals the modulus. Using this fact, we can easily find the additive inverse of a number. For instance, in mod 11 arithmetic, the additive inverse of 5 is 6because 5 + 6 = 11 ‘Two numbers a and b are additive inverse of each other if a + b = 0 mod n. Examples: 1. Find the additive inverse of 7 in modulo 16 arithmetic Solution: at+b=0modn 7+b=0 mod 16 16-7=9 7+9= 16, so the additive inverse of 7 is 9. ‘Check: 7+9=0mod 16 16+ 16 = I remainder 0 2. Find the additive inverse of 6 in modulo 12 arithmetic Solution: 6 + 6 = 12, so the additive inverse of 6 is 6. Check: 6+ 6= 0 mod 12 12+ 12= I remainder 0 3. Find the additive inverse of 4 in modulo 5 arithmetic Solution: at+b=Omodn 4+b=0mod5 5-41 4+1=5, so the additive inverse of 4 is 1. Check: a mod 55+5= I remainder 0 Multiplicative Inverse If the product of two numbers is 1, then the numbers are multiplicative inverses of each other. For instance, 2 + = 1, so 2 is the multiplicative inverse of 3, and 3 is the multiplicative inverse of 2. The same concept applies to modular arithmetic (although the multiplicative inverse will always be natural numbers). For example, in mod 7 arithmetic, 5 is the multiplicative inverse 3 (and 3 is the multiplicative inverse of 5) because 5 + 3 = 1 mod 7. (Here we will concern ourselves only with natural numbers less than the modulus.) To find the multiplicative inverse ofa mod n, solve the modular equation ax = I mod n for x. Examples: 1. Find the multiplicative inverse of 2 in modulo 7 arithmetic Solution: To find the multiplicative inverse of 2, solve the equation 2x = 1 mod 7 by trying different natural number values of x less than the modulus. =1,2,3,4,5,6 2() #1 mod7;2mod7=2:2(1) #1 mod7 2@) =1 mod 7:4 mod7=4:2(2) 21 mod7 2) S1 mod 7:6 mod7=6:2(3) #1 mod7 2(4) =1 mod 7; 8 mod7=1:2(4) £1 mod? 2(5) #1 mod7; 10 mod 7=3:2(5) #1 mod 7 2(6) =1mod 7:12 mod 7 =5:2(6) #1 mod 7 In modulo 7, the multiplicative inverse of 2is 4 2. Find the multiplicative inverse of 4 in modulo 5 arithmetic Solution: To find the multiplicative inverse of 4, solve the equation 4x = 1 mod 5 by trying different natural number values of x less than the modulus. x=1,2,3,4