Toán Rời Rạc 1

Discrete Mathematics 1

Mathematics from high school to university

S1. Introduction to the course
You will learn: about this course: its content and the optimal way of studying it together with the book.

S2. Preliminaries: "paintbrushes and easels"
You will learn: some basics needed for understanding the new topics discussed in this course.

S3. A very soft start: "painting happy little trees"
You will learn: you will get the first glimpse into various types of problems and tricks that are specific to Discrete Mathematics: proving formulas, motivating formulas, deriving formulas, generalising formulas, a promise of Mathematical Induction, divisibility of numbers (by factoring, by analysing remainders / cases), various ways of dealing with problem solving (mathematical modelling, using graphs, using charts, using Pigeonhole Principle, using the Minimum Principle, [always] using logical thinking; strategies); you will also see some problems that we are not able to solve (yet) but which will be solved in Section 12 where we will learn more about counting; nothing here is based on big theories, just logical thinking; treat it as a "smörgåsbord" (Swedish buffet) of Discrete Mathematics.

S4. Logic
You will learn: the meaning of the symbols used in logic; conjunction, disjunction, implication, equivalence, negation; basic rules of logic (tautologies) and how to prove them; two kinds of quantifiers: existential and universal; necessary and sufficient conditions. This section is almost identical to Section 7 in "Precalculus 1: Basic notions"; I have only removed the material covering the epsilon-delta definition of limit, because it is irrelevant for Discrete Mathematics. I have also added several new problems (Videos 87-93) that were not present in the Precalculus course.

S5. Sets
You will learn: the basic terms and formulas from the Set Theory and the link to Logic; union, intersection, set difference, subset, complement; cardinality of a set; Inclusion-exclusion principle. This section is almost identical to Section 8 in "Precalculus 1: Basic notions".

S6. Functions
You will learn: about functions: various ways of defining functions; domain, codomain, range, graph; surjections, injections, bijections, inverse functions, inverse images; bijections and cardinality of sets; compositions of functions; some examples of monotone and periodic functions. You will get an information about other topics relevant for examining functions (in Calculus) and where to find them (in the Precalculus and Calculus series).

S7. Relations
You will learn: about binary relations generally, and specifically about RST (Reflexive-Symmetric-Transitive) relations, equivalence classes, and about order (partial order) relations. This section is almost identical to Section 9 in "Precalculus 1: Basic notions".

S8. Functions as relations
You will learn: definition of a function as relation between sets: domain and co-domain; injections, surjections, bijections, inverse functions. This section is almost identical to Section 10 in "Precalculus 1: Basic notions".

S9. A very brief introduction to sequences
You will learn: you will get an extremely brief introduction to the topic of sequences: just enough for the next sections in this course (proofs and combinatorics; for the latter we only need finite sequences) and to complete the discussion of functions defined on the set of natural numbers (adding and scaling sequences, monotone sequences); the topic of sequences will be covered very thoroughly and from scratch in DM2.

S10. Various proof techniques
You will learn: the meaning of words axiom, definition, theorem, lemma, proposition, corollary, proof; various types of proofs with some examples: direct proof, indirect proof (proof by contradiction, proof by contrapositive), proof by induction, proof by cases; proving or disproving statements (finding counterexamples).

S11. Factorial, n choose k, and Binomial Theorem
You will learn: some important properties of the sigma symbol; the factorial function, binomial coefficients, Pascal's Triangle; the Binomial Theorem (theorem telling you how to raise a sum of two terms to any positive natural power) with a motivation and a formal proof; I will show you (mostly without proving, as this is moved to DM2, where you will see plenty of proofs, both "regular" and combinatorial) several binomial identities and where you can find even more of them; all this will be really important for the next section (Combinatorics).

S12. Combinatorics: the art of counting, an introduction (TBC in DM2)
You will learn: some basic combinatorial concepts like permutation, variation, and combination; an explanation of the name of binomial coefficients ("n choose k"); counting subsets of a finite set; counting paths on a grid; some examples of combinatorial proofs. Much more follows in DM2, I promise.

Note: This is the first part of our trilogy in Discrete Mathematics. The following subjects will be covered in the next courses: an introduction to Number Theory with modular arithmetic, an introduction to algebraic structures (groups, rings, fields, etc), with groups of permutations and really cool geometrical applications (DM2); sequences (recurrences, generating functions, etc), an introduction to Graph Theory (DM3). The topic of Combinatorics will be further (after the introduction done in DM1) discussed in DM2, followed by a very brief introduction to (discrete) probability.

Make sure that you check with your professor what parts of the course you will need for your final exam. Such things vary from country to country, from university to university, and they can even vary from year to year at the same university.

A detailed description of the content of the course, with all the 272 videos and their titles, and with the texts of all the 395 problems solved during this course, is presented in the resource file

“001 List_of_all_Videos_and_Problems_Discrete_Mathematics_1.pdf”

under Video 1 ("Introduction to the course"). This content is also presented in Video 1.