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".

2 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: 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)

3 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.

4 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: 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.

5 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.

6 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.

7 Thismeans that in order to learn the fundamental algorithms used bycomputer programmers, students will need a solid background in thesesubjects. 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.

8 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. 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 ).

9 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. Rarely is this thecase with most DISCRETE math topics. When we ask students what theirfavorite topic is, most respond either combinatorics or numbertheory.

10 (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.