Discrete Mathematics MATH 150
Popular in Course
Popular in Mathematics (M)
verified elite notetaker
This 33 page Class Notes was uploaded by Lisa Wisoky on Monday October 12, 2015. The Class Notes belongs to MATH 150 at Fayetteville State University taught by Staff in Fall. Since its upload, it has received 8 views. For similar materials see /class/221586/math-150-fayetteville-state-university in Mathematics (M) at Fayetteville State University.
Reviews for Discrete Mathematics
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/12/15
Sec 17 Mathematical Induction Principle of Mathematical Induction Suppose that we have a propositional function Sn whose domain of discourse is the set of positive integers Further suppose that St is true basis step and for all n 2 1 if Sn is true then Sn1 is true inductive step Then Sn is true for every positive integer n Example induction proof letSn12n proveSn nI12 1for alln 2 1 proof basis step SI 12 1 inductive step Sn w assuming that Sn is true we must show that n1n2 2 Sn1 is true by de nition Sn1 l2 n n1 Sn n1 M 01 nnl 2nl 2 2 2 nnl 2nl nln2 2 2 the factorial function is defined as follows 39 lifn0 n nn ln 2l if n 2 l prove n 2 2 1 for alln 2 l proof basis step let nl then 1 l 2 l 21 1 20 inductive step assume n 2 2 quot1 is true then we need to prove that n1 2 2 n1 nln 2 nl2quot 1 2 2x2quot1 since n1 2 2 2quot If we want to verify that the statements Sno Sn01 where n0 i 1 are true we must change the basis step to Sno is true The inductive step then becomes for all n 2 no if Sn is true then Sn1 is true Prove ifr 1 21arar2 a1rt1 11D fornZO Proof basis step settingn0 a 2101 1 whichisttue r l inductive step we want to prove n2 a r 1 a ar ar2 arquot arquot1 r 1 Assuming that the formula is true for n we have n1 a r 1 a ar ar2 arquot arquot1 g arn1 r 1 n1 n1 n1 n2 n1 ar 1ar r l ar aar ar r 1 r 1 r 1 a1n2 a arn2 1 r 1 r 1 Sec 14 Nested Quantifiers ex For every integer m there exists an integer n such that mltn ie there is no A formula contains nested quantifiers greatest Integer when It contaIns at least one quantIerr within the scope of another quantifier Vm n m lt n39 D 39 39megers ex The sum of any two positive real numbers is positive VxVy xgt0 ygt0 a xygt0 D reals ex There exists a positive integer m such ex There exists two integers m and n such that for every positive integer n m is less that m n than or equal to n ie there is a least positive integer HmVn m g n D positive integers While this is true ofthe positive integers m1 it is not true ofthe integers 3min m n D integers While this is true ofthe integers m1 and 1 it is not true ofthe positive integers Problemsolving tips Problemsolving example 1 1 To prove VxVy Pxy is true must show prove VXVY Xgt0 A ygt0 XYgt0 Pxy is true for every combination ofx D reals and y in the domain Use x and y to stand for arbitrary elements of the domain in the argument proof if xgo or ygo then vacuously true Let x be an arbitrary real such that xgt0 and let y be an arbitrary real such that ygt0 If we add y to each side ofxgt0 we get xygt0y But since 0y is equal to y which is greaterthan 0 we have xy gt 0y gt 0 so xy gt 0 Problemsolving tips 2 To prove Vx y Pxy is true must show that for each x in the domain there is a y in the domain such that Pxy is true Use x as an arbitrary element and then find a y for that x that makes Pxy true Problemsolving example 2 prove Vm n m lt n D integers proof let m be an arbitrary integer then there exists an least one integer n namely n m1 such that mltn Problemsolving tips 3 To prove HXVy Pxy is true must show that for some x in the domain Pxy is true for every y in the domain Having chosen an x let y stand for an arbitrary element and show that Pxy is true Problemsolving example 3 prove HmVn m g n D positive integers proof let m1 Then for every positive integer n n has the property that m g n Problemsolving tips 4 To prove Hx y Pxy is true must find some x and some y in the domain which make Pxy true Problemsolving example 4 positive In e proof let x 2 and y 3 prove Hx y xgt1 ygt1 xy6 D t gers inclass exercises prove Vx y xy 0 D reals Disproof To disprove VxVy Pxy is to show that VxVy Pxy is false Sometimes this can be done directly but at other times it is easier to prove that VxVy Pxy is true But VxVy Pxy 2 3x Vy Pxy by DeMorgan s law 2 Hx y Pxy by DeMorgan s law Therefore one way to disprove VxVy Pxy is to prove that Hx y Pxy is true Disproof equivalences summary 1 to disprove VxVy Pxy can prove Hx y Pxy 2 to disprove Vx y Pxy can prove HXVy Pxy 3 to disprove HXVy Pxy can prove Vx y Pxy 4 to disprove Hx y Pxy can prove VxVy Pxy inclass exercises disprove Vx y xgty D positive integers disprove Hx y xgt1 ygt1 xy7 D positive integers Sec 15 Proofs A mathematical system consists of axioms definitions and undefined terms axioms statements assumed to be true definitions used to create new termsconcepts from old ones undefined terms defined implicitly by the axnoms Euclidean geometry is a mathematical system The real numbers form a mathematical system 17 theorems propositions proven to be true theorems are often of the form for all x1 x2 xn if px1 x2 xn then qx1 x2 xn universally quantified conditional lemma a not very interesting theorem useful for proving other theorems corollary a theorem that follows quickly from another theorem proof an argument that establishes the truth of a theorem Types of proofs for conditionals 1 directproof assume that px1 x2 xquot is true and then show that it follows that qx1 x2 xquot is true prove for any integers m and n if m is odd and n is even then mn is odd proof Since m is odd there is an integer k1 such that m 2k11 Also since n is even there is an integer k2 such that n 2k2 Therefore mn 2k11 2k2 2k1 k2 1 Thus there is an integer k namely k k1 k2 such that mn 2k 1 Therefore mn is odd 2 proof by contradiction indirect proof prove p a q by assuming p and sq and deriving a contradiction a proposition of the form rA r prove For all real numbers x and y if xy 22then eitherx21ory21 proof Let x and y be arbitrary real numbers and suppose x 21 v y 21 But x21vy212 x21A y21 E x lt 1 y lt 1 Therefore xy lt11 2 But this is a contradiction xy lt 2 xy 2 2 Therefore x 21 v y 21 is true 3 proof by contrapositive we prove p a q by assuming sq and deriving p In other words we prove sq a p by direct proof prove for all integers m if m2 is odd then m is odd proof The contrapositive is if m is not odd then m2 is not odd or equivalently if m is even then m2 is even So suppose m is even then m2k for some integer k Now m2 2k2 22k2 22k2 Therefore m2 is even Therefore we have proven the original conditional 4 proony cases used when the hypothesis naturally divides itself into various cases Suppose we want to prove p1 v p2 v v pquot a q we can instead prove p1 a q p2 a q prove for every real number x x x proof For every x x 2 0 v x lt 0 Case 1 ifx 20then x x by definition Thus x 2x Case 2 ifx lt 0 then x x by A pquot a 0039 definition Since x x gt 0 and 0 gt x x 2x In either case x 2 x 5 to prove theorems ofthe form prove for all integers n n is odd iff n1 is p ifand only ifq 9V9 We use the equivalence proof 1 if n is odd then n 2k1 for some integer k Now n1 2k1 1 p 9 q 7 p a q A q a p39 2k Therefore n1 is even 2 if n1 is even then n1 2k for some integer k Now n 2k1 Therefore n is odd Deducnve reasomng Deductive arguments are also written as deductive reasoning the process of p1 drawing a conclusion from a set of p2 propositions the hypotheses A deductive argument has the form Pr if p1 and p2 and and pquot then q quotquot 39 andas p1p2p39q An argument is valid provided that ifthe hypotheses are all true then the conclusion must also be true Otherwise the argument is invalid or a fallacy mles of inference brief valid arguments used within larger arguments such as proofs Rules of inference for propositions modus ponens p a q p q modus toens p a q q p addition p p vq simplification pA q p conjunction p q pA q hypothetical syllogism paqqar par disjunctive syllogism p v q p q given hypotheses p a q q a r q a S p prove r s 1 p a q hypothesis 2 q a r hypothesis 3 par hypsyll12 4 p hypothesis 5 r modus ponens 3 4 6 q a s hypothesis 7 p a s hyp syll 1 6 8 s modus ponens 7 4 9 rA s conjunction 58 Rules of inference for quantified statements 1 universal instantiation Vx Px Pd if d is in the domain D 2 universal generalization Pd for every d in D Vx Px Pd for an arbitrary d in D Vx Px Rules of inference for quantified statements 3 existential instantiation 3x Px Pd for some d in D 4 existential generalization Pd for some d in D 3x Px given the hypotheses Vx Px v Qx Plynn prove Qlynn 1 Vx Px v Qx hypothesis 2 Plynn v Qlynn Ul 1 3 Plynn hypothesis 4 Qlynn disj syll 2 3 Ch 3 Relations Sec 31 Relations A binary relation R from a set X to a set Y is a subset of the Cartesian product X x Y If x y e R we write ny and saythat x is related to y If XY R is a binary relation on X The setx e X x y e Rforsomeye Y is the domain of R The setye Y x y e Rforsomex e X is the range of R A function f from X to Y is a relation from X to Y having the properties The domain off is equal to X and For each X e X there is exactly one y e Y such that X y e f ex let X 2 3 4 and Y 3 4 5 6 7 Defining R X Y by X y e R ifx divides y we obtain R 24 26 33 36 44 Rewriting R as a table we have X Y WWMM meow 4 4 The domain of R 234 and the range 346 ex let R be the relation on X 1 234 defined by x y e R ifx yforx y e X Then R 11 12 13 14 22 23 24 33 34 44 The domain of R the range of R X We can picture a relation on a set with a digraph Steps a draw dots or vertices to represent the elements of X b if x y e R then draw an arrow directed edge from x to y A relation R on a set X is reflexive if x x e Rforeveryx e X ex R 11 12 13 14 22 23 24 33 34 44 on X 1 2 3 4 is reflexive ex R 12 13 14 23 24 33 34 44 on X 1 2 3 4 is not reflexive A relation R on a set X is symmetric if for every x y e X if x y e Rthen y x e R ex R ab ac and bya bc byd cya cb cyd dya dyb dyc on X a b c d is symmetric ex R aa bc cb dd on X a b c d is symmetric ex R aa bc dd on X a b c d is not symmetric A relation R on a set X is antisymmetric if for everyx y e X if x y e R and x i y then y x e R ex R 11 12 13 14 22 23 24 33 34 44 on X 1 2 3 4 is antisymmetric but not symmetric ex R aa bc cb dd on X a b c d is symmetric but not antisymmetric ex R aa bb cc dd on X a b c d is symmetric and antisymmetric ex R aa ab bc cb dd on X a b c d is not symmetric and not antisymmetric A relation R on a set X is transitive if for every x y z e X if x y e R and y z e R then x z e R ex R 11 12 13 14 22 23 24 33 34 44 on X 1 2 3 4 is transitive ex R aa bc cb dd on X a b c d is not transitive ex R aa bb bc cb cc dd on X a b c d is transitive Orders on Sets Relations can be used to order the elements of a set A relation R on a set X is called a partial order if R is reflexive antisymmetric and transitive If R is a partial order on a set X we sometimes write x lt y to indicate that x y e R ex Prove g is a partial order on the real numbers Proof 1 X g X for all real numbers X g is reflexive 2 ifxgyandx ythenxlty 4ygx g is antisymmetric 3 ifx g y and y g 2 then X g z g is transitive Since g is reflexive antisymmetric and transitive g is a partial order on the set of real numbers ex Prove lt is not a partial order on the real num ers Proof 11X lt X for any real number x lt is not reflexive 2 ifx lt ythen x y and y lt X lt is antisymmetric 3 ifx lt y and y lt 2 then X lt z lt is transitive Since lt is not reflexive lt is not a partial order on the set of real numbers ex R defined on the positive integers by x y e R ifx divides y is a partial order because 1 x x e R because every integer divides itself reflexive 2 if x divides ythen x g y y does not divide x unless x y antisymmetric 3 If x divides y then y k1x for some integer k1 and if y divides 2 then 2 k2y for some integer k2 z k2y k2k1x k2k1x for some integer k2k1 x divides z and so R is transitive Since R is reflexive antisymmetric and transitive R is a partial order on the set of positive integers ex Prove R 11 12 13 14 22 23 24 33 34 44 on X 1 2 3 4 is a partial order Proof 1 1R1 2R2 3R3 and 4R4 XRX for all x e X R is reflexive 2 1R2 but not 2R1 1R3 but not 3R1 1R4 but not 4R1 2R3 but not 3R2 2R4 but not 4R2 3R4 but not 4R3 if ny and x i y then ny R is antisymmetric 31R2A 2R3A1R31R2A 2R4A1R4 1R3 A 3R4 A 1R4 2R3 A 3R4 A 2R4 if ny and sz then sz R is transitive Since R is reflexive antisymmetric and transitive R is a partial order on X 1 2 Let R be a partial order on set X For x y e X if either ny or ny then x and y are said to be comparable If x y e X and ny and ny then x and y are incomparable ex given R based on divides 2 and 4 are comparable because 24 6 R ie 2 divides 4 ex given R based on divides 2 and 3 are incomparable because 23 e R and 32 e R ie 2 doesn t divide 3 and 3 doesn t divide 2 Let R be a partial order on X If every pair of elements in X is comparable then R is a total order ex on the positive integers is a total order because for all positive integers x and y either x g y or y g x ex the divides relation on the positive integers is not a total order because for some positive integers x and y x doesn t divide y and y doesn t divide x ex Prove R 11 12 13 14 22 23 24 33 34 44 on X 1 2 3 4 is a total order Proof 1 R is a partial order shown earlier 2 1R1 1R2 1R3 1R4 2R2 2R3 2R4 3R3 3R4 and 4R4 for every xy e X either ny or ny Since R is a partial order and for every xy e X x and y are comparable R is a total order Let R be a relation from X to Y The inverse of R R4 is the relation from Y to X defined by R391 y X x Y 6 R ex 2 is the inverse relation of eX R4 11 21 22 31 32 33 41 42 43 44 is the inverse of R 11 12 13 14 22 23 24 33 34 44 Composition of Relations Let R1 be a relation from X to Y and R2 be a relation from Y to Z The composition of R1 and R2 denoted R2 R1 is the relation from X to Z defined by R2 R1XZXy R1 and V Z 6 R2 for some y e Y ex The composition of the relations R1 a1 2 16 24 34 36 38 an R2 2yu 48 4t 6t 8U is R2 R1 141 11 28 2t 3 s 3i 3u Sec 32 Equivalence Relations A partition of a set X is a collection 8 of nonempty subsets of X such that every element of X belongs to exactly one member of S Thm 321 Let S be a partition of a set X Define ny to mean that for some set s e 8 both x and y belong to s Le x and y belong to the same member of the partition 8 Then R is reflexive symmetric and transitive Proof of Thm 321 1 Let X e X By the definition ofa partition X belongs to some s e 8 Thus XRX and so R is reflexive 2 Suppose XRy then both X and y belong to some s e 8 Therefore yRX and so R is symmetric 3 Suppose XRy and sz Then both X and y belong to some s e S and both y and z belong to some t e 8 But since y only belongs to one set in S s t both X and z belong to s and so XRz R is transitive A relation that is re exive symmetric and transitive on a set X is an equivalence relation on X ex Prove R 11 13 15 22 24 31 33 35 42 44 51 53 55 on the set X 1 2 3 4 5 is an equivalence relation on X Proof 1 1R1 2R2 3R3 4R4 5R5 R is reflexive 2 1R3 and 3R1 1R5 and 5R1 2R4 and 4R2 3R5 and 5R3 R is symmetric 3 1R3 and 3R5 and 1R5 R is transitive R is an equivalence relation on X Thm 328 Let R be an equivalence relation on a set X For each a e X let a xeXlxRathenSaanisa partition of X The sets a are called the equivalence classes of X given by the relation R ex There are two equivalence classes on X 1 2 3 4 5 defined by R 11 13 15 22 24 31 33 35 42 44 51 53 55 namely 1 3 5 1 3 5 and 2 4 2 4 These two classes partition X ex let X 1 2 3 10 and define ny to mean that 3 divides x y 1 3 divides x x O R is reflexive 2 if 3 divides x y then 3 divides y x x y R is symmetric 3 if 3 divides x y and 3 divides y 2 then 3 divides x y y z x z R is transitive R is an equivalence relation on X The equivalence classes defined by R are 1 x e X 3 divides x 1 1 4 7 10 2 x e X 3 divides x 2 2 5 8 3 x e X 3 divides x 3 3 6 9 These three sets partition X Thm 3215 Let R be an equivalence relation on a finite set X If each equivalence class has r elements then there are Xr equivalence classes Proof Let X1 X2 Xk denote the distinct equivalence classes Since these sets partition X X X1 le Xk r r r kr k Xr is the number of equivalence classes Ch 2 The Language of Mathematics Sec 21 Sets A set is a collection of objectselements ex A 1 2 3 4 A set has only one occurrence of each of its elements and the order of the elements is not significant Sets can be described by listing their elements or by giving a property necessary and sufficient for membership Sets can be described by listing their elements or by giving a property necessary and sufficient for membership ex B x x is a positive even integer This is read as B is the set of all x such that x is a positive even integerquot or B is the set of positive even integersquot X the number of elements in set X ifX is finite x e X a member of x e X not a member of The emptynull set is the set with no elements and is denoted by Q Thus 9 Set Relations Two sets are equal X Y iff they have the same elements XYEVXX X X YAXEY XEX X is a subset of Y X g Y iff every element in X is also in Y XQYEVXXEXgtXEY X is a proper subset of Y X C Y iff X is a subset of Y but does not equal Y ProvethatifAxx2x 6Oand B 2 3 then A B Proof 1 Show that ifx e A then x e B Suppose that x e A Then x2 x 6 0 Solving for x we get x 2 or x 3 In either case x e B 2 Show that ifx e B then x e A Suppose that x e B Thenx20rx3 lfx2thenx2x 642 6O Thereforex e A lfx3 then x2 x 6 9 3 6 0 Therefore x e A Therefore A B ProvethatifXxx2x 2O andY the set of integers then X g Y Proofle e X then x2x 2 0 Solving for x we getx 1 orx 2 In either case x is an integer Therefore Vx x e X a x e Y Therefore X g Y To show that X is not a subset of Y we must show that Vx x e X a x e Y is false which is the same thing as showing that Vx x e X a x e Y is true But we have that Vx x e X a x e Y 2 3xIxeX xeY23xquotXervxe Y23xxeXAxeY In other words we need to find an element of X which is not an element of Y for every set X X g X for every set X 9 g X Proof need to show that Vx x e 9 a x e X But this is always true since x e 9 is always false The powerset of X PX is the set of all subsets of X ex let A a b c then PA 9 a b C a b a c by c a b c Thm 216 If X n then PX 2quot Proof in class ex If A 3 then PX 23 8 Set OperationsFunctions The union of X and Y X U Y equals x x e X v X e Y The intersection of X and Y X m Y equals XlXEXAXEY The difference of X and Y X Y equals x x e X X e Y also called the relative complement X and Y are disjoint ifX m Y Q A collection of sets 8 is pairwise disjoint if X m Y Q for each pair of distinct sets in S The universeset is a set which contains all the elements of all the sets in some domain Given a universal set U and a subsetX of U the set U X is the complement of X written X39 or Xbar letU 1 2 3 4 5and etA 1 3 5 then A39U A24 Thm 2112 Let U be a universal set and let A B and C be subsets of U then the following properties hold associative laws AUBUCAUBUC AmBmCArBrC commutative laws AUBBUA AmBBmA distributive laws AmBUC AmBUAmC AUBmC AUBmAUC identitylawsAU AAm UA complement laws A U A39 U A m A39 Q idempotent laws A U A A A m A A bound IaWSIAUUUA absorption laws A U A m B A A m A U B A involution law Aquot A 01 laws 939 U U39 Q DeMorgan s laws for sets A U B A39 m B39 AmB39A39UB39 Generalized Union amp Intersection Let S be a family of sets Then US xleXforsomeXES HS xleXforallXES IfS A1 A2 An then we write UsUA and ns A 11 11 IfS A1 A2 then we write USLjAand s A 11 11 eX fori 21 de neAi i i1 i2 and S A1 A2 Then DA Us 1 2 3 Partitions A collection 8 of nonempty subsets of X is a partition of X if every element of X belongs to exactly one member of S If S is a partition of X then S is pairwise disjoint and US X LetX1 2 34 5 6 7 8thenS1 4 5 2 6 3 7 8 is a partition of X Ordered Pairs An ordered pair a b is distinct from b a unless a abcdiffacandbd If X and Y are sets then the Cartesian product of X and Y X x Y is the set of all ordered pairs x y where x e X and y e Y IX X Y IXIIYI letX123andYa bthenXxY 1 a 1 b 2 a 2 b 3 a 3 b An ntuple a1 a2 an also takes order into account Therefore a1 a2 an b1 b2 bn when a1 b1 and a2 b2 and and an n The Cartesian product of sets X1 X2 Xn is the set of all ntuples where xi 6 Xi for i 1 n letX 1 2 3 Y a b 2 1 2 then x x Y x z 1a1 1 a2 1b1 1b2 2a1 2a2 2b1 2b2 3a1 3a2 3b1 3b2 In general X1x X2 x x Xn X1X2 Xn Sec 22 Functions A function assigns to each member of a set X exactly one member of a set Y ex d 55t where t is time and d is distance This function assigns to each nonnegative real numbert a value for d which is 55t A function f from set X to set Y is a subset of the Cartesian product X x Y having the propertythat for each x e X there is exactly one y e Y with x y e f written as f X a Y set X is the domain off y x y e f is the range of f The range off is a subset of Y ex let X 1 2 3 and Y a b c Then f 1 a 2 b 3 a is a function from X to Y with domainf X and rangef a b ex let X 1 2 3 4 and Y a b c Then f 1 a 2 a 3 b is not a function from X to Y because element 4 is not assigned an element in Y ex let X 1 2 3 and Y a b c Then f 1 a 2 b 3 c 1 b is not a function from X to Y because the element 1 of X is not assigned a unique element of Y Given f X a Y fx y is another way to write x y e f ex Let f be the function defined bythe rule fx x2 with domain reas Then we have f x x2 x is a real number The range off is the set of nonnegative reas In a graph a set S of points in the plane defines a function precisely when each vertical line intersects at most one point of S QuotientRemainder Theorem if d and n are integers d gt O amp n 2 0 then there exist integers q the quotient and r the remainder satisfying n dq r 0 g r lt d ex letn7andd3Then73qr whereq2andr1 If x is a nonnegative integer and y is a positive integer we define X modyto be the remainder when x is divided by y modulus function ex 6 mod 2 O 6mod30 6mod42 6mod51 6mod76 The floor of x LXJ is the greatest integer less than or equal to x The ceiling of x lxl is the least integer greater than or equal to x ex le T51 5 L83l 8 i831 9 Lsal 9 i sal 8 A function f X a Y is onetoone injective if for each y e Y there is at most one x e X with fx y In other words f X a Y is onetoone if VX1VX2 fX1 gt9 9 X1 X2 ex f 1 b 2 a 3 c is onetoone ex f 1 a 2 b 3 a is not oneto one Prove fn 2n 1 is onetoone where domainf positive integers Proof Want to show that if fn1 fn2 then n1 n2 Suppose fn1 fn2 Then 2n1 1 2n21 2n1 2n2 n1 n2 f is onetoone A function f X a Y is not onetoone if 3x1 3x2 fx1 fx2 x1 i x2 ex fn n2 is not onetoone because f2 f2 A function f X a Y is onto Y surjective if the range off is Y In other words f X a Y is onto Y if Vy e Y 3x 6 X fx y ex let X 1 2 3 and Y a b Then f 1 a 2 b 3 a is onto Y ex let X 1 2 3 and Y a b c Then f 1 a 2 c 3 b is onetoone and onto Y Prove fx 1x2 from the set X of nonzero real numbers to the set Y of positive real numbers is onto Y Proof want to show that for every y e Y there exists an x e X such that fx y 1x2 fx y x2 1y x i1y 2 note y is positive In either case positive or negative x e X f is onto Y fX Yis notontoYif 3y 6 Y Vx e X fx i y Prove fn 2n 1 from the set X of positive integers to the set Y of positive integers is not onto Y Proof want to find a y e Y such that there is no x e X where fx y Since fn is always an odd number for any even y e Y there is no n such that fn y f X a Y is a bijection iff is both oneto one and onto letf Xw Y1 X2 Y2 Xn 341 the f inVerse f4 Y1v X1 Y2 X2 1 an Xn let f X a Y be a bijection then f391 Y a X is also a bijection ex fx 2X the exponential function is a bijection from the set R of all real numbers onto the set R of positive real numbers Then f391 y x log2y the logarithmic function is also a bijection note if f3 23 8 y then f3918 Iog28 3 x Let g X a Y and f Y a Z then the composition offWith g f g is the function f gx fgx from X to Z ex given g 1 a 2 a 3 c where X 1 2 3 and Y a b c and f a y b x c 2 where Z x y 2 then f g 1 y 2 y 3 2 ex let fx log3x and gx x4 then f 9X fgx 39093X4 and 9 fX 9fX l093X4 A function from X a X is a unary operator on X A function from X x X a X is a binary operatoron X ex letX 1 2 3 lffx y x y where x y e X then f is a binary operator on X ex let U a universal set Then fX X where X e PU is a unary operator on PU Sec 23 Sequences and Strings A sequence is a function whose domain is a set of consecutive integers A sequence s can be denoted by sn where sn is the nth term in the sequence and n is the index of the sequence ex let s be the sequence 2 4 6 2n where s1 2 s2 4 s3 6 sn 2n 39the domain of s positive integers A sequence is infinite if its domain is infinite otherwise a sequence is finite ex the sequence un defined by uquot n2 1 n 2 0 is infinite and can be denoted by M ex the sequence t Whose domain is 1 0 1 2 3 can be denoted by 23 and is finite ex define sequence s as sn 2n 43 n 2 O as02 43 145 b bs12143121214 c s 2i 43i d sn1 2n1 43n1 e s2 2n2 43n2 f prove that sn 5sn1 6sn2 n 2 2 5sn1 6sn2 52 391 43quot391 62 392 43n392 5quot2quot2quot392 5quot4quot3quot3quot392 6quot2quot392 6quot4quot3quot392 52 6quot2 392 543 64 quot3 2 4quot2 2 36 3quot2 222n2 4323n2 2n 4quot3n sn A sequence is increasing if sn lt sn1 A sequence is decreasing if sn gt sn1 A sequence is nondecreasing if sn sn1 A sequence is nonincreasing if sn 2 sn1 If a sequence is increasing then it is also nondecreasing If a sequence is decreasing then it is also nonincreasing ex the sequence ai 1i for i 2 1 is decreasing and therefore nonincreasing ex the sequence 100 90 90 74 74 7430 is nonincreasing ex the sequence 100 is increasing and decreasing and therefore nonincreasing and nondecreasing Let sn be a sequence defined for n m m1 and let n1 n2 be an increasing sequence Whose values are in the set m m1 We call the sequence Snk a subsequence of sn ex b c is a subsequence ofthe sequence tfa t2a t3b t4c t5q Where n3 and n24 39 the subsequence can also be written as 4 t3 t4 or tnl tn2 or tn 3 Sum amp Product of a sequence If ai n is a sequence we de ne n Za am amH an surnorsigma m 11 Ha am 0 amH o 0 an product orpi m i is the index In is the lower limit and n is the upper limit ex let an 2n n 21 be a sequence Then 3 2aaaa24612 H 3 Ha a a a24648 H ex The geometric sum a ar ar2 ar3 ar can be Written as 2 ar Pu The sum and product notations can be modified to denote sums and products indexed over an arbitrary set of integers S as follows 2 al the sum ofthe elements a l i5 S 2 H a the product ofthe elements a l i5 S 2 ex if S is the set of prime number less than 20 then 1 1 1 E39 2 3 1 777i 17 L1455 5 7 11 13 17 19 Strings A string is a finite sequence of characters A string overX where X is a finite set is a finite sequence of elements from X ex let X a b c then the sequence 31 b 32 a 33 a 34 c is a string over X The string is usually written baac Repetitions in a string can be specified by superscripts ex bbaaac can be written as b2a3c The null string 7L is the string with no elements X denotes the set of all strings over X X denotes the set of all nonnull strings over X The length of a string on Iocl is the number of elements in on If on and 3 are strings the concatenation of on and 3 043 is the string consisting of on followed by 3 ex if y aab and e cabd then yo aabcabd ey cabdaab y y aab Ayyaab Let X be a finite set If we define foc 3 043 where on and 3 are strings over X then f is a binary operator on X A substring of a string on is obtained by selecting some or all consecutive elements of 0c A string 3 is a substring of the string on if there are strings y and 8 with x VBS ex 3 add is a substring of x aaaddad since if we take y aa and 8 ad we have x VBS Ch 5 Introduction to Number Theory Introduction Numbertheory is the branch of mathematics concerned with the integers Sec 51 Divisors Let n and d be integers d i 0 Then ddivides n d n if there exists an integer q satisfying n dq d is the divisor q is the quotient Thm 185 QuotientRemainder Theorem There exist unique integers q quotient and r remainder satisfying n dq r 0 g r lt d r 0 iff d n Thm 513 Let m n and d be integers a if dm and dn then dmn b if dm and dn then dmn c ifdm then dmn An integer greaterthan 1 whose only positive divisors are 1 and itself is called prime An integer greaterthan 1 that is not prime is called composite Thm 517 A positive integer n greaterthan 1 isltomposite iff n has a divisor d satisfying 2 g d g n proof 1 if n is composite then n has a divisor d satisfying 2 g d g n Suppose n is composite Then n has a divisor d39 satisfying 2 g d39 lt n Case 1 if d39 g n then done Case 2 d39 gt n then since d39n there exists an integer q satisfying n d39q Thus q is also a divisor of n Suppose q gt n then n d39q gt nn n Contradiction Thus q s n So n has a divisor d q satisfying 2 g d g n 2 if n has a divisor d satisfying 2 g d ln then n is composite True by definition Algorithm 518 Testing Whether an integer is prime Input n Output d 0 if n is prime OW smallest divisor isprimen for d 2 to Lxnl if n mod d 0 return d return 0 ex input 43 check whether 2 3 4 5 6 H431 divides 43 Since none of them do 43 is prime In the worst case when n is prime Alg 518 takes time n If n is composite the divisor returned by Alg 518 is prime ex If n 1274 the algorithm returns 2 because 1274 2637 If we input n 637 we get 637 791 If we input n 91 we get 91 713 13 is prime we have 1274 27713 as a product of primes Thm 5111 Fundamental Theorem of Arithmetic Any integer gt 1 can be written as a product of primes lfthe primes are written in nondecreasing order the factorization is unique Thm 5112 The number of primes is infinite Proof Let p1 p2 pn be all the distinct primes less than or equal to prime p Considerthe integer m p1p2 p 1 For all i 1 to n pi does not divide m Let p39 be a prime factor of m then p39 i pi i 1 to n Since p1 p2 pn are all the primes less than or equal to p we must have p39 gt p Let m and n be integers with not both zero A common divisor of m and n is an integer that divides both m and n The greatest common divisor gcdmn is the largest common divisor of m and n Can find gcdmn by looking at their prime factorizations ex 30 235 and 105 3 57 3 and 5 are common divisors so 35 15 is the gcd30105 Thm 5117 Let m and n be integers with not both zero and with prime factorizations m turbidquotprquot and n p1b1p2b2pnb Then the gcdmn p1mina1b1p2mina2b2 pnminanbn In other words the gcdmn equals the product of all the primes which are common divisors of m and n ex 82320 243 573 and 950796 22327411 Therefore gcd82320 950796 2min423min125min107min341 1min01 22315073110 4116 Let m and n be positive integers A common multiple of m and n is an integer that is divisible by both m and n The least common multiple lcmmn is the smallest positive common multiple of m and n Thm 5122 Let mgt1 and ngt1 be integers with prime factorizations m plalpzazpnaquot and n p1b1pzb2pnb Then the lcmmn p1maxa1b1p2maxa2b2 pnmaxanbn ex 82320 243quot573 and 950796 2232741 1 Therefore Icm82320 950796 2max423max125max107max341 1max01 2432quot5174111 19015920 5 25 For any positive integers m and n mn Thm 1 gcdmnlcmmn Proof if m1 then gcdmn 1 and lcmmn n Similarly for n1 Thus we may assume mgt1 nd ngt1 Write the prime factorizations of m and n as m p a1p 32p aquot and n p1b1p2b2pnbquot by Thm 51 7 am Thm 5122 godr 1nglcm39rn 2nb2 39 b 1b1 mina mina mll39l an I39I maxa max ELEM BmB anbn quot39pquot p1 p2 mina1 maxa1b mina2b2maxa2b2 minanbn Biaxanbn a1b1 pza2b2 anbn mpquot 1 n pia pzazm pnaquotpig p2b2 mm mn By Thm 5125 Icmmn mngcdmn Therefore if we have an efficient algorithm to compute the gcd we can also efficiently compute the lcm Sec 52 Representations of Integers the positional representation of an integer using base b anb an1b 391a1b1a0b where Ogailtb In the decimal number system the base is 10 and Ogailt10 ex 385410 31O3810251O4 A bit is a binary digit that is O or 1 In the binary number system the base is 2 and ai is a bit ex 1011012 1quot250quot241quot231quot220quot21120 32 8 4 1 4510 Some powers of 2 2 1 212 224 238 2416 2532 2664 27128 Algorithm 523 Converting an integerfrom base b to decimal Input c n b output decva the decimal value of the base b integer cncn1c1c0 basebtodeccnb decva 0 power 1 for i 0 to n decva decva cipower power powerb retu rn decva ex n3b2c31c21c10c01 c02 c121c222c323 11O21418 148 13 ex B4F16 11quot162 416 15 11256 416 15 289510 Common bases which are powers of 2 base 2 binary digits are 0 and 1 base 4 digits are 0 3 base 8 octal digits are 0 7 base 16 hexadecimal digits are 0 9 and A F where A10 B11 C12 D13 E14 F15 Converting between these bases and base 2 is relatively easy base 4 a binary starting with the least significant digit convert each base 4 digit into a group of 2 binary digits which has the same value ex 12110204 11OO1O1OO10002 binary base 4 starting with the least significant digit collect the binary digits into groups of two and write each group as a single base 4 digit ex 1 1001 O1 001000212110204 octal binary starting with the least significant digit convert each octal digit into a group of 3 binary digits which has the same value ex 145108 1 100101 001 0002 binary octal starting with the least significant digit collect the binary digits into groups of three and write each group as a single octal digit ex 1 100101 001 0002 145108 hexadecimal binary starting with the least significant digit convert each hexadecimal digit into a group of 4 binary digits which has the same value ex 194816 1 1001 0100 10002 ex A7F916 1010 0111 1111 10012 binary hexadecimal starting with the least significant digit collect the binary digits into groups of four and write each group as a single hexadecimal digit ex 1 1001 0100 10002 194816 ex 1010 0111 1111 10012 A7F916 Algorithm 527 Converting a decimal integer into base b Input m a decimal number b the base to be converted to Output 0 n dectobasebmbcn n 1 While mgt0 n n 1 on m mod b m Lmbl ex 14710 to binary 1 least significant digit 732 362 182 92 42 22 1 2 0 Answer100100112 OO OO most significant digit ex 10410 to base 3 104 3 2 least significant digit 34 3 1 11 3 2 3 3 O 1 3 1 most significant digit 0 Answer 102123 ex 14710 to base 16 hexidecimal 147 16 3 least significant digit 9 16 9 most significant digit 0 Answer 9316 BinaryAddition Binary addition table O 1 O O 1 1 1 1O ex 10011011 155 1011011 91 11110110 246