Introduction to Discrete Structures
Introduction to Discrete Structures COT 3100
University of Central Florida
Popular in Course
verified elite notetaker
Popular in Engineering and Tech
This 5 page Class Notes was uploaded by Lamont Block on Thursday October 22, 2015. The Class Notes belongs to COT 3100 at University of Central Florida taught by Arup Guha in Fall. Since its upload, it has received 19 views. For similar materials see /class/227689/cot-3100-university-of-central-florida in Engineering and Tech at University of Central Florida.
Reviews for Introduction to Discrete Structures
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/22/15
COT 3100 Topics Covered Logic Use of truth tables logical connectives implications logic and implication laws use of quantifiers Sets Definition Union Intersection Minus Some Counting Set Laws Set Table Venn Diagrams InclusionExclusion Principle Relations amp Functions Definition of a relation reflexive irreflexive symmetric antisymmetric transitive injection surjection and bijection Number Theory Induction Definition of divisibility Use of mod and mod rules Euclid s Algorithm Strings and Languages Regular expressions DFAs languages are sets of strings Relevant parts in the book Logic 21 24 Sets 31 33 Number Theory 41 44 Relations amp Functions 515256717374 Strings amp Languages 61 remember 6263 talks about FSMs but I have dealt only With DFA s Since we have not had an exam With induction number theory and strings and languages that Will be the stress of the exam No need to memorize the logic or set laws I Will attach the necessary tables Logic problem Show that the following is a tautology PVFV qAFVPV IPODP pvrv qArvpV uupODpltgt pvrv qArvpv pAqv p lt2 DeMorgans pvrv qArvpvpAqv pltgtDoubleNegation p v p v p v r v q A r v p A q ltgt ComAssoc over or T v p v r v q A r v p A q lt2 Inverse Law T C Domination Law Set Problem Prove or disprove A c C A B c C gt A U B C Q PROVE if A c C A B c C that means we can assume if XEA then XEC and if XEB then XEC Now we need to show that A U B C Q Consider to the contrary that there is an element xeA U B C That would mean by definition of set difference that xe A U B but XE C If XE A U B we must have either xeA or XEB In the first case we nd XE C by the assumption And we find the same thing in the second case But this contradicts that Xe C Thus the set A U B C must be empty Function Problem Let f A B and g B C denote two functions If g f is an injection prove that f must be an injection Also show that it is not necessary for g to be an injection That is show that there is a case where g is not an injection but g f is an injection We must show that f is an injection We are given the fact that g f is an injection We will prove the statement using contradiction Assume that f is not an injection In this situation we can find two distinct elements of the set A a and a such that fa fa Let each of these be inputs to the function g Then we have the following gfa gfa where a a since we assumed the two to be distinct BUT this contradicts the assumption that g f is an injection Thus we can conclude that f must be injective Here is a small example that satisfies the restrictions of the question but where g is not injective A 1 Bab Cz f1 a ga z gb z gf1 2 Here we have that g f is not only injective but also bijective But g is not injective since gagb Induction Problem n1 Show that for all n 2 0 and x gt 2 x lt X Use induction on 11 Base case n0 LHS X0 1 RHS x With given information we find LHS lt RHS as desired Inductive hypothesis Assume for an arbitrary value of nk that x lt xk Inductive Step Under this assumption we must prove our formula for nk1 That is we must show Ex lt X061 10 Ex 3614 Xk1 10 lt Xkl xk by the inductive hypothesis 2Xk1 ltxxk1 using given information about X Xk11 proving the inductive step Thus we can conclude that x lt Xn1 for all n 2 0 and x gt 2 10 Number Theory Problem Given that 5 2X 5y where X and y are integers show that 5 X Using our given information we find that 2X 5y 5c for some integer c 2X 5c 5y X 5c y2 We are given that X is an integer Thus we must have that 2 5c y But if c y is odd this will be false So we must have that 2 c y In this case we can let c y 2d for some integer d Substituting we have X 52d2 X 5d so we can conclude that 5 X StringLanguage problem Let T W and X be languages over the alphabet ab Show that ifT C W then T n X C W m T First we will show that T n X C W n T Let y ET m X We must show that y e W m T If we have that y ET 0 X we can conclude that y ET and y EX But we also know that T C W Thus given that y e T we also know that yeW Since both of these are true we have y e W m T as desired Now that we have established that T n X C W n T we can star both sides to yield T n X C W n T