×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

by: Lamont Block

36

0

31

# Honors Introduction to Discrete Structures COT 3100H

Marketplace > University of Central Florida > Engineering and Tech > COT 3100H > Honors Introduction to Discrete Structures
Lamont Block
University of Central Florida
GPA 3.74

Staff

These notes were just uploaded, and will be ready to view shortly.

Either way, we'll remind you when they're ready :)

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

COURSE
PROF.
Staff
TYPE
Class Notes
PAGES
31
WORDS
KARMA
25 ?

## Popular in Engineering and Tech

This 31 page Class Notes was uploaded by Lamont Block on Thursday October 22, 2015. The Class Notes belongs to COT 3100H at University of Central Florida taught by Staff in Fall. Since its upload, it has received 36 views. For similar materials see /class/227697/cot-3100h-university-of-central-florida in Engineering and Tech at University of Central Florida.

×

## Reviews for Honors Introduction to Discrete Structures

×

×

### What is Karma?

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/22/15
Set Theory repetition Set theory starts with some unde ned but intuitively clear terms then formal logic is used to prove properties about sets and their relationships Set theory has been used as the foundation for all mathematical theories lntuitively a set means a collection of things objects The relationship between the objects contained in the set called the elements and the set is the belongs to relationship Formally letA denote a set an element x belongs to A is denoted x e A otherwise x e A if x doesn t belong to A There are two ways to describe a set by an enumeration of its elements or by stating the properties that the elements must satisfy Example The set of all even nonnegative integers can be described as E 0 2 4 or E x x 2 0 andx 2 n where n is an integer After the unde ned terms are understood we can make formal definitions and prove theorems Definition LetA B denote two sets a A is a subset ofB denotedA g B if for all x e A x e B is true A g B can also be written wBQA b A B if bothA g B and B g A that is for all x x e A ltgt x e B where the symbolltgt means implication in both directions gt and lt and is called if and only if abbreviated as i c The union of sets A and B denotedA u B is de ned as x x e A or x e B d The intersection of setsA and B denotedA m B is de ned as x x e A and x e B e The difference of sets A and B denotedA B is de ned as x x e A and x e B Note that in generalA B B A f The set containing no elements is the empty set denoted 0 Typically the sets under consideration are subsets of a universe U The difference between U and a setA U A is called the complement of A denoted A Sets and their relationships are typically depicted by the Venn diagrams B A v U A B AmB B A AuB U ACA Many properties of the sets can be proved by the de nitions and the use of propositional logic Theorem Let A B C denote arbitrary sets The following properties hold a Commutative Law A u B B u A A m B B m A b Associative Law A u B u CA u B u C A m B m CA m B m c DistributiveLawAuBm CAuBmAuCAmBuCAmBUAmC d Idempotent Property A u A A A m A A e De Morgan s Law A u B A m B A m B A u B f Double Negation A A g Complementary Property A m A Q A u A U where U denotes the universe Proof We will only prove a few of these properties to demonstrate the ideas To prove a notice thatA u B x x e A or x e B by de nition x x e B or x e A by the commutative law for logical or B u A by de nition SimilarlyA m B x x e A andx e B x x e B andx e A B mA using the de nition of set intersection and the commutative property of logical and To prove d notice thatA u A x x e A or x e A by de nition of u x x e A A because for any propositionpp orp 2p Let us prove a few more theorems about sets The main techniques used are the de nitions other theorems and logical reasoning Theorem LetA and B denote arbitrary sets The following properties hold a A m B Q A Proof By the de nition of g we need to prove that if x e A m B then x e A By the de nition ofA m B x e A m B implies x e A and x e B In particular x e A is true b A g A u B Proof By the de nition of g we need to prove that if x e A then x e A u B that is prove x e A or x e B But this is true by the de nition of or since x e A is true c A m Q Q Proof By part a A m Q g Q On the other hand we proved on page 11 that Q is a subset of any set in particular Q g A m Q is true Thus A m Q Q by the de nition of set equality d A u Q A Proof By part b A gA u Q Thus to prove the two setsA andA u Q are equal it suf ces to prove thatA u Q g A that is to prove that if x e A u Q then x e A When x e A u Q we have x e A orx e Q Since x e Q is always false x e A must be true e A g B iff B g A Proof A g B iff for all x x e A gt x e B by de nition of g iff for all x x ez B gt x ez A by the contrapositive law iff B g A because x ez B means x e B and x g A means x e A and by the de nition of g fA gB iffA m B Q Proof By de nitionA gB ifffor all x x e A gt x e B is true By the contrapositive law page 113 for all x x e A gt x e B iff for all x x ez A or x e B which is equivalent to for all x x e A and x ez B by De Morgan s law and it is equivalent to there eXists x x e A and x ez B by the De Morgan s law This last statement is equivalent to saying there is no x which is in setA and in set B thus A m B Q is true Let us introduce a few more de nitions in set theory Definition LetA be a set The power set of A denoted PowerA or 2 4 is the set of all subsets of A Example LetA 1 2 Then PowerA Q 1 2 1 2 a set ofthe 4 subsets ofA Definition LetA and B denote two sets De ne the Cartesian product of A and B as A x B a b a e A and b e B where the notation a 7 denotes an ordered pair or a 2tuple Note that the ordering of the elements in an ordered pair is signi cant that is two ordered pairs are equal a b c 0 iff a c and b d More generally the Cartesian product of n sets A1 A2 A is de ned as Ai a1 an a e A for 1 S i S n where all an de nes an ordered ntuple il Example LetA 1 2 andB a b ThenA x B 1 a 1 b 2 a 2 19 One application of the set theory concerns the counting problems There are two basic counting principles dealing with set union and set product The Sum Principle LetA and B denote two nite sets andA m B 0 Then A u Bl A B More generally letAl A2 A denote n nite sets n 2 1 and these sets are nmutually disjoint that isAlmAj Q foriij Then A1 UAZU uAn A1 A2 Anl zlAll n 11 n The Product Principle LetAl A2 An denote n nite sets Then IllLl Ill1 l Example LetA 1 2 3 andB 4 5 denote two sets Then A u Bl 5 lAl lBl because1 m B Q IA gtlt B 14 15 24 25 34 35l 6 2 3 W lBl When the sets A and B are not disjoint the following result tells how to count IA u Bl Theorem LetA and B denote two nite sets Then A u Bl lAl lBl A m Bl Proof Since each element of A u B belongs to eitherA or B the sum lAl lBl includes a count for each of the elements of A u B but those elements of A m B are counted twice Thus lAl lB l l A m B l counts each element of A u B exactly once that is it is equal to l A u Bl More precisely we rst claim that the following is a disjoint union AA BuAmB 1 Thus by the de nition of set equality we want to prove that AgA BuAmB 2 A BuAmBgA 3 and A B m A m B Q 4 To prove 2 let x e A Since either x e B or x ez B is true in the former case x e A m B by de nition and in the latter case we have x e A and x ez B which means x e A B by de nition To proved 3 note thatA B g A because each x e A B must also have x e A by the de nition of set difference Also A m B g A because each x e A m B must also have x e A by the de nition of intersection Thus A B u A m B g A by the de nition of set union and the subset relationship To prove 4 note that each x e A B must satisfy x ez B by the de nition of set difference Also each x e A m B must satisfy x e B by the definition of set intersection Thus it is impossible to have x e A B m A m B which proves 4 by the definition of the empty set Similar to l we also have the following disjoint set union BB AuBmA 5 Applying the Sum Principle on p 119 to l and 5 we have the following AABlA Bl 6 and B B A BmA 7 Combining l and 5 yields the following disjoint union the sets A B and B A are disjoint because x e A B implies x ez B which means x ez B A AuBA BuB AuBmA 8 which implies the following equation using the Sum Principle p 119 AuBlA BlB ABmA 9 Combining 6 7 and 9 gives the equation A u Bl lAl lBl A m B Venn Diagram for A u B Theorem Let A B and Cdenote three nite sets Then A u B u C A B C i MmmiBinMmqMmqu Proof Applying the previous theorem to sets A and B u C we have A u B u C A u B u C associative law ABuClelA BuCl 1 Note that BuC B CVleCl 2 And note that A m B u C A m B u A m C by distributive law MOHMmqiMmBmAmq AmB Am Cl 7 AmBmCbecauseA AA Thus substituting the above equation and 2 into 1 proves MuBuCF MHMWMMmH7BinMmQMmBmQ AmC AmB B m C Venn Diagram forAuBuC AmBmC Set Theory Concept of Set Special Set The founder of set theory is Georg Cantor 18451918 The importance of the notion introduced by him became well known only Set theory has a decisive role in all branches of mathematics and today it is an essential tool of mathematics and its applications Membership relation Sets and their Elements The fundamental notion of set theory is the membership relation A set A is a collection of certain things a objects ideas etc that we think belong together for certain reasons These objects are called the elements of the set We write aEA or aE EA to denote a is an element of A and a is not an element of A respectively Set can be given by enumerating their elements in braces for example MLabc or UI173757 or by a de ning property possessed exactly by the elements of the set For instance the set U of odd natural numbers is de ned and denoted by Ux x is an odd number For number domains the following notation is generally used IN I 012 set of natural numbers ZOl l2 2 set ofthe integers Q p qEZAin set ofthe rational numbers IR set of the real number C set of the complex number Principle of Extensionality for Sets Two sets A and B are identical if and only if they have the same elements that is ABltgtVxx AltgtxEB The set 31372 and l237 are the same A set contains every element only once even if it enumerate several times Subsets Definition If A and B are sets and Vxx AgtxEB holds then A is called a subset ofB and this is denoted by A E B In words A is a subset of B if all elements of A also belong to B If for A E B there are some elements in B such that they are not in A then we call A a proper subset of B and denote it by AC B Obviously every set is a subset of itself AEA Example Suppose A246810 is a set of even numbers and B l2345678910 SinceA does not contain odd numbers A is a proper subset of B Definition It is important and useful to introduce the notion of empty set or void set H which has no element Because of the principle of extensionality there exists only one empty set Examples The set xxERx22x20 is empty EM for every setM that is the empty subset H is subset of setM For a setA the empty set and A itself are called the trivial subsets of A Definition Equality of sets Two sets are equal if and only if both are subsets of each other ABltgtAEBABEA This fact is often used to prove that two sets are identical Definition The number of elements of a nite setM is called the cardinal number or cardinality of M and it is denoted by lMl Note that the cardinal number of set with in nitely elements can also be de ned Definition The set of all subsets A of M is called the power set of M and is denoted by PM that is PMA AEM Example For the setMabc the power set is PM 3 a b c Cab 6L0 bcabc It is true that 1 If a setM has m elements its power set PM has 2 quot elements 2 For every setM we have H M EP M that isM itself and the empty set are elements of the power set Operations with Sets Definition The graphical representation of sets and set operations are the socalled Venndiagrams when we represent set by plane gures So in the gure on the left we represent the subset relation A B Definition By set operations we form new sets from the given sets in different ways by Union LetA and B be two sets The union set or union denoted by AUB is de ned by AUBLxxEAVxEBJ1 We say A union B or A cup B If A and B are given by properties p and q respectively the union set AUB has the elements possessing at least one of the properties AUB Example 123Ul2356f1235 6 Intersection LetA and B be two sets The intersection set intersection cut or cut set denoted by A m B is de ned by A BLxxEAxEBJ1 We say A intersected by B or A cap B If A and B are given by properties p and q respectively the intersection A B has elements possessing both properties p and q Example 123 2 3 5 6I23 7 7 7 Definition Two set A and B are called disjoint if they have no common element for them AnB holds that is their intersection is the empty set Example The set of odd numbers and the set of even numbers are disjoint their intersection is is the empty set that is odd numbers 0 even number Complement If we consider only the subsets of a given setM then the complementary set or the complement C M A of A with respect to M contains all elements of M not belonging to A CMAxxEMxE EA We say complement of A with respect to M and M is called the fundamental set or the universal set If the fundamental setM is obvious from the considered problem the notation A is also used for the complementary set Fundamental Laws of Set Algebra These set operations have analogous properties to the operations in propositional logic The fundamental laws of set algebra are 1 Double Complement ZA 2 De Morgan Laws WZUF mZ F 3 Commutative Laws 14033014 AUBBUA 4 Associative Laws AnBnCAmBnC AUBUCAUBUC 5 Distributive Laws AUB CAUB AUC AnBUCAnBUAnC 6 Idempotent Laws A AA AUBBUA 7 Identity Laws A UA AU A 8 Inverse Laws A02 AUX U 9 Domination Laws A AU U U 10Abs0rpti0n Laws A AUBA AUA BA Remark This table can also be obtained from the fundamental laws of propositional calculus if we make the following substitutions by 3 U HOJltgt C This is not a coincidence it can be shown that the algebra of propositional logic is isomorphic to the set algebra we won39t pursue this any further Properties of Integers Divisibility Primes Euclid s Division Algorithm Greatest Common Divisor GCD and Least Common Multiple LCM Recall the following de nition of divisibility of integers Definition An integer a is divisible by integer b where b i 0 if a bc for some integer c In this case b is called a divisor of a the notation is b a We often restricted the divisors to positive integers since if b a where b 2 0 then b a For example since 12 3 4 we can say 3 12 and 4 12 Also 1 n and n n for any non zero integer n Definition An integer p is called a prime if p 2 2 and the only positive divisors of p are l and 19 itself that is ifp is a prime and a lp where a gt 0 then a l or a 19 Thus some primes are 2 3 5 7 ll 13 It is well known that there exist in nitely many primes proved by Euclid However it is still unknown whether there are infinitely many prime pairs such as 3 and 5 5 and 7 11 and 13 etc where two primes of the form 19 and 92 known as twin primes Any integer n gt 1 can be factored into a product of primes in essentially a unique way which is known as the fundamental theorem of arithmetic It turns out that factorization is not a trivial problem that is given a large integer finding its factors may take many steps given the stateofart algorithms However finding common factors between two integers can be done very efficiently something known to Euclid Definition Given two positive integers a and b An integer m is a common divisor of a and b if m a and m b The greatest common divisor of a and b denoted GCDa b is the largest of the common divisors of a and Z Note that the GCD always exists since 1 is always a common divisor so GCDa b 2 1 Two integers a and b are relatively prime if GCDa b l We now develop Euclid s algorithm which computes the GCD of two positive integers The basic idea is based on the following theorem Theorem If a bq r where 1 0 then GCDa b GCDb r Proof We rst note that if m l a and m b that is if m is a common divisor of a and b then m r This is true because m l a implies a mc m l 1 implies b md for some integers c and 61 Thus r a bq mc mdq mc dq which proves m r Thus m is a common divisor of b and r Therefore m S GCDb r by the de nition of GCDb r In particular GCDa b S GCDb r Similarly we can prove that any common divisor of b and r divides 61 Thus GCDb r S GCDa b Combining the two inequalities proves the theorem Example We now illustrate Euclid s GCD algorithm by computing GCD228 95 228 95 2 38 so GCD228 95 GCD95 38 Repeating the division process using the previous divisor and remainder as the dividend and divisor respectively of the next step we nd 95 38 2 19 so GCD95 38 GCD3819 and since 38 19 2 0 so GCD3819 GCD19 0 19 Combining we nd GCD228 95 19 the divisor of the last division step Note that the above process always terminates since each remainder is strictly smaller than the divisor of that step thus strictly smaller than the remainder of the previous step so the remainder eventually becomes zero When that occurs the last GCD between the divisor and zero is the divisor itself which gives the GCD of the original pair of integers Euclid s algorithm written in C that computes the GCD is given below int gcd int a int b assume a b gt 0 int r while 1 repeat until remainder 0 r a b r is the remainder if r 0 return b otherwise a b b r Theorem Suppose a and b are two positive integers There exist integers rand u may not be positive such that at bu GCDa b That is the GCD can be written as a linear combination of the two integers We will demonstrate this theorem by the extended Euclid s GCD algorithm Basically the GCD is equal to the remainder of the secondtothelast division step of Euclid s algorithm Thus the GCD can be written as a linear combination of the dividend and the divisor of that division step We can then use the division step above it to substitute out its remainder resulting in a linear combination of the dividend and divisor from this previous step Repeating the substitutions using the division steps toward the beginning of Euclid s algorithm eventually leads to a linear combination in terms of the original pairs of the integers Example Find integers I and u such that GCD228 95 228 t 95 u that is write GCD228 95 as a linear combination of 228 and 95 Recall the following division steps in computing GCD228 95 using Euclid s algorithm 228 95 2 1 95 382 2 and 38 19 2 0 3 Thus GCD228 95 19 and E 95 2 4 by rewriting the remainder in Step 2 We now substitute out the remainderrom Step 1 thus rewriting 4 as 1995 228 952 2 228 2 95 4 1 by combining the like terms writing as a linear combination of the previous dividend and divisor 228 2 95 5 Thus I 2 and u 5 Theorem If p is a prime and p ab then 19 a or p b where a and b are two positive integers Proof Consider the value of GCDp a Since this is a divisor of p but 19 is a prime by assumption so GCDp a l or p by the de nition primes We now have two cases Case one Suppose GCDp a 1 Write 1 19 au using the Extended Euclid s algorithm Multiplying both sides by 17 yields 17 ptb abu ptb mu assuming ab pm since 9 ab by assumption Thus we proved p b in this case Case two Suppose GCDp a 19 In this case p is the GCD of p and a sop a We can now state the following theorem which says any integer greater than 1 can be factored into a product of primes in essentially a unique way The proof is given on pages 36 and 37 Theorem Fundamental Theorem of Arithmetic Let n 2 2 denote an integer Then there eXists prime numbers 191 p2 pk not necessarily distinct such that n 191192 pk that is any integer n 2 2 can be factored as a product of prime numbers Furthermore the product is unique except for possible rearrangement of the prime factors Example Consider the following prime factorizations 10296 2332111312675 3 52 132 and25168 24 112 13 Note that the GCD can be calculated quickly once the prime factorizations are given That is if integers a and b have a common prime factor 19 eg p a and p b then 19mm 39539 is a prime power factor in GCDa b Thus GCD10296 12675 3 13 39 and GCD10296 25168 23 11 13 1144 Definition The least common multiple of two integers a and b denoted LCMa b is the smallest positive multiple of a and b For example LCM10296 12675 23 32 52 ll l32 and LCM10296 25168 24 32 112 13 Theorem GCDa b LCMa b ab for any two positive integers a and b Proof It can be seen that if p a and p b then pmaXW I is a primepower factor in LCMa b Thus the primepower factor using prime p in GCDa b LCMa b is 19mm 395 19mm 395 which equals p I exactly the same as the primepower factor using prime p in ab Since this is true for all primepower factors of a and b the theorem is proved

×

×

### BOOM! Enjoy Your Free Notes!

×

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

Steve Martinelli UC Los Angeles

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Janice Dongeun University of Washington

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

Steve Martinelli UC Los Angeles

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Parker Thompson 500 Startups

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!
×

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com