MATH208: DISCRETE MATHEMATICS

1 U N D M AT H E M AT I C SM AT H 2 0 8 :D I S C R E T EM AT H E M AT I C SD E PA R T M E N T O F M AT H E M AT I C ST H E U N I V E R S I T Y O F N O R T H DA KOTAC opyright 2017 UND Mathematicspublished by department of mathematicsthe university of north 2005,2006,2007,2008,2009,2014,2015,2016, 2017 University of North Dakota MathematicsDepartmentPermission is granted to copy, distribute and/or modify this document under the terms of the GNU FreeDocumentation License, any later version published by the Free Software Foundation; withno Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included inthe section entitled "GNU Free Documentation License".Second corrected edition, Second printing: December2017 Contents1 Logical Connectives and Compound Implication and :If .. , then .. :.. if and only if .. table to propositional and .. , then .. normal and and to symbolic and basic laws of quantified of propositional with : Basic standard and universal and equality of set set string of by by a counterexample to disprove a a ordered digraph: domain= operations with relation using relation of a of with matrices.

2 Boolean of class of a of an equivalence representation of an equivalence and Their of with DISCRETE domain and by0-1matrix or bipartite (injective) (surjective) of DISCRETE and ceiling of and a Sequence With a a Sequence by for arithmetic and geometric Defined form Fibonacci Sequence of sequences by Defined definitions of of principle of mathematical by principle of mathematical of an search search Growth of efficiency and division algorithm for s and the Euclidean of the Euclidean Euclidean algorithm in quotient/remainder s (a,b)as a linear combination of a and to expressgcd(a,b)as a linear Euclidean Linear Combinations forgcd(a,b) Fundamental Theorem of the Fundamental of positive divisors of Diophantine andgcd(a,b) all modulo m equivalence classes modulo congruence in Other to and from between non-decimal science bases:2,8, Two Fundamental Counting sum two independent sum rule and the logical product two sequential tasks: logical product by subtraction: Good=Total both the sum and product form solution and Binomial Theorem and Pascal s combinatorial s Binomial inclusion-exclustion with the Good=Total-Bad Pigeonhole pigeonhole Counting Basic Donut Shop More Realistic Donut Shop Real Donut Shop with order and some six fundamental counting Using Recurrence counting rules for finding recursive to Recurrence a recursion by a recursion by Method of Characteristic , constant coefficient example of the steps.

3 The characteristic equation and its characteristic method of characteristic roots more method for repeated general Nonhomogeneous to solve nonhomogeneous recurrence Graph a graph in a Historical Interlude: The origin of graph First Theorem of Graph Brief Catalog of Special trails and facts about eulerian and hamiltonian Free Documentation License3211. APPLICABILITY AND DEFINITIONS3222. VERBATIM COPYING3243. COPYING IN QUANTITY3244. MODIFICATIONS3255. COMBINING DOCUMENTS3286. COLLECTIONS OF DOCUMENTS3287. AGGREGATION WITH INDEPENDENT WORKS3298. TRANSLATION3299. TERMINATION33010. FUTURE REVISIONS OF THIS LICENSE33011. RELICENSING331 ADDENDUM: How to use this License for your documents331 List of logical diagram forA diagram forA diagram forA diagram forA diagram forA=U bipartite relations:R ofy= function in 0-1 matrix part part log2(x) 5 23 23board with s s Triangle (numeric) B=(A B) grades with the same degree Isomorphic , trails, and for 318 List of or and table for(p q) q p rules of of an of Set simple size vs.

4 CPU time efficiency functions for small values functions wheren= : 6567(si) +987(ti) =ri,qi (107653, 22869) counting counting solution patterns288 List of search (repeat/until). (ABindicates a comment follows.) search (for loop) (again) list value162 IntroductionDiscrete math has become increasingly important in recentyears,for a number of reasons:11 The Art of Problem math is essential to college-level MATHEMATICS and math together with calculus and abstract algebra is oneof the core components of MATHEMATICS at the undergraduate level. Stu-dents who learn a significant quantity of DISCRETE math before enteringcollege will be at a significant advantage when taking undergraduate-level math math is the MATHEMATICS of MATHEMATICS of modern computer science is built almost entirelyon DISCRETE math, in particular combinatorics and graph theory. Thismeans that in order to learn the fundamental algorithms used bycomputer programmers, students will need a solid background in thesesubjects.

5 Indeed, at most universities, a undergraduate-level course indiscrete MATHEMATICS is a required part of pursuing a computer math is very much real world students complaints about traditional high school math al-gebra, geometry, trigonometry, and the like is "What is this goodfor?" The somewhat abstract nature of these subjects often turn offstudents. By contrast, DISCRETE math, in particular counting and prob-ability, allows students even at the middle school level to veryquickly explore non-trivial "real world" problems that are challengingand math208: DISCRETE mathematicsDiscrete math shows up on most middle and high schoolmath math competitions such as MATHCOUNTS (at the middleschool level) and the American MATHEMATICS Competitions (at the highschool level) feature DISCRETE math questions as a significant portionof their contests. On harder high school contests, such as the AIME,the quantity of DISCRETE math is even larger. Students that do not havea DISCRETE math background will be at a significant disadvantage inthese contests.

6 In fact, one prominent MATHCOUNTS coach tells usthat he spends nearly50% of his preparation time with his studentscovering counting and probability topics, because of their importancein MATHCOUNTS math teaches mathematical reasoning and is often taught as a series of formulas and algorithms forstudents to memorize (for example, the quadratic formula, solvingsystems of linear equations by substitution, etc.), and geometry is oftentaught as a series of definition-theorem-proof exercises that are oftendone by rote (for example, the infamous two-column proof ). Whileundoubtedly the subject matter being taught is important, the material(as least at the introductory level) does not lend itself to a great deal ofcreative mathematical thinking. By contrast, with DISCRETE MATHEMATICS ,students will be thinking flexibly and creatively right out of the are relatively few formulas to memorize; rather, there are anumber of fundamental concepts to be mastered and applied in manydifferent math is students, especially bright and motivated students, find algebra,geometry, and even calculus dull and uninspiring.

7 Rarely is this thecase with most DISCRETE math topics. When we ask students what theirfavorite topic is, most respond either combinatorics or numbertheory. (When we ask them what their least favorite topic is, theoverwhelming response is geometry. ) Simply put, most students finddiscrete math more fun than algebra or Connectives and Compound PropositionsLogic is concerned with forms of reasoning. Since reasoningis involved in most intellectual activities, logic is relevant to a broadrange of pursuits. The study of logic is essential for students of com-puter science. It is also very valuable for MATHEMATICS students, andothers who make use of mathematical proofs, for instance, linguisticsstudents. In the process of reasoning one makes inferences. In an in-ference one uses a collection of statements, the premises, in order tojustify another statement, the conclusion. The most reliable types ofinferences are deductive inferences, in which the conclusion must betrue if the premises are.

8 Recall elementary geometry: Assuming thatthe postulates are true, we prove that other statements, such as thePythagorean Theorem, must also be true. Geometric proofs, and othermathematical proofs, typically use many deductive inferences. (RobertL. Causey) ~ basic objects in logic arepropositions. A proposition is a state-ment which is either true (T) or false (F) but not both. For example inthe language of mathematicsp: 3+3=6 is a true proposition whileq: 2+3=6 is a false do you want for lunch?is aquestion, not a proposition. LikewiseGet lost!is a command, not aproposition. The sentenceThere are exactly1087+3stars in the universeis a proposition, despite the fact that no one knows its truth are two, more subtle, examples:26 math208: DISCRETE MATHEMATICS (1)He is more than three feet tallis not a proposition since, until we aretold to whomherefers, the statement cannot be assigned a truthvalue. The mathematical sentencex+3=7 is not a propositionfor the same reason. In general, sentences containing variables arenot propositions unless some information is supplied about thevariables.

9 More about that later a little common sense isrequired. For exampleIt is rainingis aproposition, but its truth value is notconstant, and may be arguable. Thatis, someone might sayIt is not raining,it is just drizzling, orDo you mean onVenus?Feel free to ignore these sorts ofannoyances.(2)This sentence is falseis not a proposition. It seems to be both trueand false. In fact if isTthen it says it isFand if it isFthen it saysit isT. It is a good idea to avoid sentences that refer to propositions, such asIt is raining, andThe streets are wet,can be combined to create more complicated propositions such asItis raining and the streets are not wet. These sorts of involved proposi-tions are calledcompound propositions. Compound propositions arebuilt up from simple propositions using a number ofconnectivestojoin or modify the simple propositions. In the last example, the con-nectives areandwhich joins the two clauses, andnot, which modifiesthe second is important to keep in mind that since a compound propositionis, after all, a proposition, it must be classifiable as either true or is, it must be possible to assign a truth value to any compoundproposition.

10 There are mutually agreed upon rules to allow the deter-mination of exactly when a compound proposition is true and whenit is false. Luckily these rules jive nicely with common sense (withone small exception), so they are easy to remember and :notThe simplest logical connective isnegation. In normal English sen-tences, this connective is indicated by appropriately insertingnotinthe statement, by preceding the statement withit is not the case that, orfor mathematical statements, by using a slanted slash. For example,ifpis the proposition 2+3=4, then the negation ofpis denotedby the symbol pand it is the proposition 2+36=4. In this case,pis false and pis true. IfpisIt is raining, then pisIt is not rain-ingor even the stilted soundingIt is not the case that it is raining. Thelogical connectives and compound propositions 27negation of a propositionpis the proposition whose truth value isthe opposite ofpin all cases. The behavior of pcan be exhibited inatruth table. In each row of the truth table we list a possible truthvalue ofpand the corresponding truth value of : Logical :andThe connective that corresponds to the wordandis calledconjunc-tion.