Foundational Discrete Mathematics

Full Notes Packet

If you find errors in the notes for MAT 141 Foundational Discrete Mathematics, then please fill out the following form: https://forms.office.com/r/y8vLJwZvSS. Each error submitted can earn you an extra 0.5% on your grade up to +3% extra total.
If you are comfortable DOING SO, you can instead create an “issue” on the GitHub repository where the code for the notes is stored: https://github.com/cfroccajr/MAT-141-Foundational-Discrete-Math-Notes/issues

Fall 2025 Final’s Week Schedule:

Exam Times:

MAT 141 Monday 12/8 from 2 to 4:30pm
MAT 304 Monday 12/8 from 5:30 to 8pm
MAT 531 Tuesday 12/9 from 6 to 8:30pm
MAT 133 Friday 12/12 from 2 to 4:30pm

Final’s Week Office Hours:

Monday 12/8: 1-2pm
Tuesday 12/9: 3-6pm
Friday 12/12: 1-2pm

Class Calendar

There is a proposed calendar on the syllabus, but here I will record what we actually get through in each class.

…
11/20 – We finished the chapter 9 material by looking at the pigeonhole principle and then covered some basic graph theory terminology.
11/17 – We looked at an example of using multinomial coefficients \[\binom{n}{i,j,k}=\frac{n!}{i!,j!,k!},\ i+j+k=n\] to rearrange letters in a word when there are repeated letters and then we started looking at examples of making combinations with repetition. For the combination with repetition we can think of it as putting objects into or out of a bucket, or dividing up lines of objects. Either way we emphasized that you should still make a plan before you calculate. Wee ended by abstracting these ideas to solve problems such as “Find the number of solutions to \[x_1+x_2+x_3+x_4+x_5=n\] when for all \(i\), \(n_0\leq x_i\leq n_1\leq n\).” At this point you should be able to take a crack at problems 1-6, 8, & 9 on the practice exam for unit 4.
11/13 – We went over more material on combinatorics. We combined the multiplication principle and combinations in order to answer questions about more complicated combinations. We also looked at Pascal’s Triangle, the Binomial Theorem, and Multinomial Coefficients. At this point you can definitely do problems 1,2,3, & 6 on the practice exam and maybe 4 as well.
11/10 – You got back the exams; remember that the redos are due on Monday 11/17. We went over more material on Combinatorics. At this point we have covered: Multiplication Principle, Addition Principle, Independent Event, Disjoint Events, Inclusion-Exclusion Principle, Factorials, Permutation, and Combinations.
11/6 – Exam on Sets, Relations, and Functions
10/23 & 10/17 – We finished the material on relations in the notes packet and started looking at the material on functions. You should be able to complete problems 1,2,3,7,8, & 9 on the practice exam and probably 5 as well; also look at the challenge problems and additional problems from chapters 6 & 8.
10/16 & 10/20 – Covered additional material from Unit 3, we finished the notes on sets and started looking at Relations
10/13 – Unit 2 Exam
10/19 – Answered questions about the practice exam for Unit 2 and started Unit 3
10/6 – We went over using reindexing and adding a form of 0 to find sums. We then used iteration to find closed formulas for first-order recurrence relations; the emphasis is on the algorithm since the solution is largely the same every time. We will be looking at second order recurrence relatins next time so that we are in step with the syllabus.
10/2 – We went over general formulas for arithmetic and geometric sums \[\sum_{i=1}^nai+b=\frac{n(n+1)}{2}a+n\, b\ \text{and}\ \sum_{i=0}^nar^i=a\frac{(r^{n+1}-1)}{r-1}\] then we looked at how to find a summation that is similar to, but not identical to, formulas we already have by using either re-indexing or adding zero.
9/29 – You got back Exam 1, the redos on the exam are due Monday 10/6/2025, since they are out of class work they need to be written up neatly/professionally in complete sentences and include a sentence or two explaining your error. When you turn in the redos staple the original to the top of your redos. In class we covered more material on sequences and then started discussion summations. In particular we got as far as showing that \[\sum_{i=1}^n i = \frac{n(n+1)}{2}.\] We will pick it up from there on Thursday.
9/25 – Exam 1 on Logic
9/22 – We spent about 30 minutes discussing the practice exam and then covered some more material from Unit 2/Chapter 5.
9/18 – We finished off the Unit 1/Chapter 3 material and moved onto Unit 2. Don’t forget that the practice exam for Unit 1 is due on 9/22/2025. We will spend 20-30 minutes answering questins about the practice exam and then continue looking at Unit 2/Chapter 5.
9/15 – We did an example of constructing a valid argument from section 2.3 (it was #42 on page 75). Then We spent a lot of time on page 19 discussing predicates. We will work through the rest of the material on predicates next class polishing off chapter 3.
9/11 – We worked through page 18 in the notes, this means we have finished content from chapter 2 in the text. We will pick up on page 19 of the notes where we are looking at material form chapter 3 of the text. At this point you should be able to answer questions 1-4 on the Unit 1 practice exam as well as trying the challenge questions from chapter 2.
9/8 We started working through the logical concepts in chapter 2 of your text. We covered through page 12/13 in the notes.
9/4 – Today we covered some terminology so that we would have some common vocabulary and notation that we can use as we move forward. This material is the highlights of Chapter 1, next time we start on Chapter 2 material. If you haven’t already done so bring in a binder to hold your notes packet, either to office hours or class.
8/28 – Today we went over the syllabus and then spent time reviewing some terminology from algebra/precalculus. We will continue in this vein on Thursday 9/4/25 when we talk about chapter 1. Remember that we do not have class on Monday because it is Labor Day.

Unit 1: Logic

Writing Up Mathematics Assignment Due 9/11

Practice Exam for Unit 1 Due 9/22

Unit 2: Sequences and Summations

Practice Exam for Unit 2 Due 10/13

Unit 3: Sets, Functions, Relations

Practice Exam for Unit 3 Due 11/3

Extra Credit Exercise: The code below will build the equivalence classes from #26 in sec. 8.2. Explain how the code works both practically and based on the definition of the relation in 26.

# Written in Python
# Empty collection of equivalence classes
EC={}
# Build equivalence classes
for i in range(3):
    for j in range(3):
        for k in range(3):
            for l in range(3):
                # New element
                temp_lst=[i,j,k,l]
                # Assign to equivalence class based on sum
                EC[sum(temp_lst)]=EC.get(sum(temp_lst),[])+[temp_lst]
# Display equivalence classes
for key in EC: print(key,":\t",EC[key])

Unit 4: Counting, Combinatorics, and Graphs

Practice Exam for Unit 4 Due 12/4.

Extra Credit:

Typesetting Out-of-Class Work (+5% on each typed up piece of work)

If you are doing this extra credit here is a quick reference sheet with symbols and such: Quick Reference

Create an account at Overleaf.com using your WCSU email account
Watch the introductory video here VIDEO LINK, the document created in the video is here: https://www.overleaf.com/read/khbktbvvvkjd
Follow this link to see samples of typed up exercises: https://www.overleaf.com/read/frptnykkgpbt
Follow this link to make a copy of a blank template: https://www.overleaf.com/read/hwdhcvmntrvs
Submit work by downloading a copy of the PDF you generate and printing it.

If you are having problems typing up a document and would like feedback you can share a link to it by following the directions here: https://www.overleaf.com/learn/how-to/Sharing_a_project; send me the link to view but not edit. You can see a full playlist of video lessons here: Technical Typesetting with \(LaTeX\) Playlist

Additional Extra Credit: Complete this Reflection on Quantifiers for upto +2% on your final grade.

Links and Handouts

Vocabulary

\(\mathbb{N}\), \(\mathbb{Z}\), \(\mathbb{Q}\), \(\mathbb{R}\), rational number, irrational number, set notation, set roster notation, modus ponens, modus tollens, De Morgan’s Law, negation, distribution, commutative law, associative law, \(\forall\), \(\exists\), converse, inverse, contrapositive, conjunction, disjunction, set, subset, Cartesian product, relation, function, sequences, series, summation, summation notation \[\sum_{i=0}^n a_i=a_0+a_1+\cdots+a_n,\] product notation \[\prod_{i=0}^n a_i=a_0\times a_1\times \cdots\times a_n,\] geometric sum \[\sum_{i=0}^n a\, r^i=a+ar+ar^2+\cdots+ar^n=a\, \frac{(r^{n+1}-1)}{r-1},\] union, intersection, set difference, set complement, power set – \(\mathscr{P}(x)\), reflexive, symmetric, transitive, anti-symmetric, function, one-to-one, onto, inverses, composition, addition principle, multiplication principle, possibilities tree, combinations, factorial, permutations, binomial coefficients, multinomial coefficients, graph, walk, circuit, Euler circuit, path, tree, trail, binary tree, Hamilton circuit, closed walk, … etc.

Dr. Charles Rocca

Professor of Mathematics