Honors Discrete Mathematics
Honors Discrete Mathematics MAD 2104
Popular in Course
Popular in Mathematics Discrete
This 7 page Class Notes was uploaded by Dino Corwin on Monday October 12, 2015. The Class Notes belongs to MAD 2104 at Florida Atlantic University taught by Jorge Viola-Prioli in Fall. Since its upload, it has received 55 views. For similar materials see /class/221637/mad-2104-florida-atlantic-university in Mathematics Discrete at Florida Atlantic University.
Reviews for Honors Discrete Mathematics
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/12/15
10QUANTIFIERS This is a short but nevertheless important section in which we introduce two special symbols frequently used in the construction of mathematical statements In many cases we need to assert the existence of some elements with a particular property In those instances we use the symbol El In fact El is read 39II II in many equivalent ways quotthere exist quotthere IS exists j quotthere are For instance there exists an integer whose square is 9 is simply written as quotEleZx29 As to quotthere is a prime greater than 1000 we write it as El x E Z x prime x gt 1000 J Viola Prioli For obvious reasons El is called the existential quanti er Its negation is naturally E Another useful quanti er is the so called universal quanti er V which asserts that a certain property holds for all elements of a well designated set The symbol V means therefore quotfor every quotfor all quotfor each As a consequence quotO is divisible by every integer is written as quotV x E Z xO Also quotevery set contains the empty set is presented as QA V set A The negation of V is V For simplicity expressions like quotVx and Vy are written as quotV xy There are many statements that combine both quanti ers For instance J Viola Prioli aVxEZ EIyEZsuchthatxyO bVxEZ EIyEZsuchthatygtx2 c V xy E Z El n such that xyn x2 2xy y2 REMARK The order of the quanti ers matters For instance let us consider these two statements 1VaEZ El b EZabO This statement is true because it asserts that every integer has an opposite J Viola Prioli 2ElaEZ v bEZabO This statement obtained by interchanging the positions of the two quanti ers turns out to be false because it claims that there is an integer a that is the opposite of every other integer So a is at the same time equal to 1 and 2 a contradiction As observed in previous sections we need to know how to negate a statement in particular when trying to build a counterexample or to formulate a proof by contradiction and to be seen later a proof by contrapositive We notice at once that Vx assertion P about x means that P is not true for every x Hence there is an x for which the statement P is false In other words 39 P happens Therefore Vx assertion P about x El x assertion P about x Equivalently Vx P Elx P J Viola Prioli Observe that as the negation symbol is pushed to the right V turns into El and goes in front of the statement P Likewise with the same type of reasoning we see that Elx assertion P about x V x assertion P about x Equivalently Elx P Vx P Observe that as is pushed to the right El turns into V and goes in front of the statement P Conclusion when we negate a statement involving the quanti ers we pushed all the way to the right toggling the two quanti ers in the process J Viola Prioli For instance consider the negation oszl XEZ V y 62 x gt y3 NOTICE This statement is read quotthere exists an integer x such that for every integer y we have x is greater than y cubed Observe that the rst comma stands for quotsuch that but the second comma does not Also notice that the nal assertion P is quotx gt y3 Let us negate it step by step El XEZ V y 62 x gty3V XEZ V y 62 x gt y3 V XEZ El y 62 x gt y3 Finally the negation of x gt y3 isx s y3 Inconclusion El XEZ V y 62 x gt y3V XEZ El y 62 x s y3 In plain English the negation turns out to be for every integer x there exists an integer y such that x is less than or equal to y cubed J Viola Prioli EXERCISE a Negate quotV x E N and V yE N El n E N such that either x gt yn or x ny0 by pushing the symbol all the way to the right Tip you will need to use here the De Morgan s Laws b Afterwards decide whether the resulting statement is true and so whether the original statement is false J Viola Prioli
Are you sure you want to buy this material for
You're already Subscribed!
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'