This is a course on elementary discrete mathematics. See the syllabus, which includes the following sections.
Office hours will take place remotely at the following times.
| TTh 10:00–11:30am |
| TTh 2:00–3:00pm |
| or by appointment |
To attend office hours during the listed times, log into https://ecu.webex.com/meet/abrahamsonk (using Cisco Webex Meetings). You should be allowed to join the meeting automatically. If you have trouble, please send me an email.
You can find whiteboard controls at the left-hand side of the screen. To type text, click on Tt, then click on a position on the whiteboard and type. To draw, click on the pencil tool and draw using a mouse. You might need to select a color using the lower square in the tool bar. You might need to change from the pen tool to the pencil tool by clicking on the tool and selecting pencil.
Anyone can join at any time during the listed office-hour times. If you join while someone else is talking to me, please remain quiet until the previous student is done. If you need to discuss something private, please set up a meeting with me by email.
There are two textbooks.
Discrete Mathematics, ZyBooks, offers an introduction to discrete mathematics through solving simple problems. It is an excellent way to learn, and is a useful introduction. But it does not cover all of the material that this course is required to cover, and does not offer sufficient depth in what it does cover, for it to be the only textbook.
Start each topic with this book. Read the assigned chapters and work the problems.
Discrete Mathematics and Its Applications Kenneth H. Rosen, 8th Edition McGraw Hill, is a book that offers thorough coverage of discrete mathematics. It is more difficult to follow than the ZyBooks book, but if you read it after the lecture, you should be able to make sense of it.
Additionally, there are lecture notes on some of the topics, including logic, proofs and sets. Use that for supplemental material. Proofs are shown in a detailed, step by step fashion. (These notes were created for CSCI 4602 as review, but you might find them useful.)
There will be five quizzes. They will be administered in Canvas.
See the lecture schedule for material that each quiz will cover.
| Quiz 1 | Friday, October 16 | |
| Quiz 2 | Friday, October 23 | |
| Quiz 3 | Friday, October 30 | |
| Quiz 4 | Friday, November 6 | |
| Quiz 5 | Friday, November 13 |
Each lecture has practice questions that are due by 11:59pm on the date of the next lecture. Submit the assignments through Canvas.
Friday 10/2
| Read before class and do exercises: | Zybook1.1–1.3 |
| Read after class: | Rosen 1.1 |
propositions
logical operators
conditionals
truth tables
validity
examples of valid formulas
precedence and associativity
conversion from English to propositional logic
Monday 10/5
| Read before class and do exercises: | Zybook1.4, 1.5 |
| Read after class: | Rosen 1.2.6, 1.3.1–1.3.4 |
Wednesday 10/7
| Read before class and do exercises: | Zybook 1.6, 1.7 |
| Read after class: | Rosen 1.4.1–1.4.8, 1.4.10 |
Friday 10/9
| Read before class and do exercises: | Zybook 1.8–1.10 |
| Read after class: | Rosen 1.4.9, 1.4.13, 1.5 |
Monday 10/12
| Read before class and do exercises: | Zybook 1.11 1.13 |
| Read after class: | Rosen 1.6.1–1.6.6 |
proofs
premises, conclusions
rules of inference
premises, conclusions
rules of inference for propositional logic
logical proofs in propositional logic
logical fallacies
Wednesday 10/14
| Read before class and do exercises: | Zybook 2.1, 2.2 |
| Read after class: | Rosen 1.6.4–1.6.7, 1.7.1-1.7.4 |
rules of inference for FOL
logical proofs in FOL mathematical proof and proof techniques
how theorems are stated
finding proofs vs. presenting proofs
finding proofs
try to understand why the theorem is true
using definitions
presenting proofs
Friday 10/16
| Quiz 1 | Material covered on 10/2, 10/5, 10/7 and 10/9 |
| Read before class and do exercises: | Zybook 2.3–2.4 |
| Read after class: | Rosen 1.7.5 |
proving A → B by direct proof
Monday 10/19
| Read before class and do exercises: | Zybook 2.5 |
| Read after class: | Rosen 1.7.6, 1.8.1, 1.8.3 |
proving A → B using the contrapositive
proving ∃x P(x)
constructive proofs
nonconstructive proofs (see Chomp, Rosen p. 102)
using existential information
proving ∀x P(x)
Wednesday 10/21
| Read before class and do exercises: | Zybook 2.6, 2.7 |
| Read after class: | Rosen 1.7.7, 1.7.8, 1.8.2, 1.8.5-1.8.6 |
proof by contradiction
proving ∀x∃y P(x,y)
proving (A or B)
proof by cases
Friday 10/23
| Quiz 2 | material covered on 10/12, 10/14 and 10/16 |
| Read before class and do exercises: | |
| Read after class: | Rosen 1.8.7, 1.8.8 |
proving not(A)
clever proof ideas: checkerboards
forward and backwards proofs
common errors
Monday 10/26
| Read before class and do exercises: | Zybook 3.1, 3.3–3.6 |
| Read after class: | Rosen 2.1.1–2.1.6, 2.2.1, 2.2.2 |
What is a set?
set membership
subsets
set equality
universal set
Venn diagrams
finite sets
the empty set
set enumerations
cardinality
infinite sets
set comprehensions
operations on sets
union
intersection
difference
complement
cartesian product
set identities
proving identities equationally
Wednesday 10/28
| Read before class and do exercises: | Zybook 3.2, 4.1, 4.3 |
| Read after class: | Rosen 2.2.4, 2.3.1, 2,3,2 |
proving identities using membership tables
sets of sets
{{}}
cardinality of sets of sets
powersets
computer representation of sets
functions
f(x)
domain, codomain, range
image, preimage
properties of functions
one-to-one (injective)
onto (surjective)
bijective
increasing
Friday 10/30
| Quiz 3 | Material covered on 10/19, 10/21 and 10/23 |
| Read before class and do exercises: | Zybook 4.2, 4.4, 4.5 |
| Read after class: | Rosen 2.3.3–2.3.5 |
operations on functions
f + g
composition
inverse functions
floor, ceiling
bijections and cardinality
there are more real numbers than integers
there are the same number of rational numbers as integers
Monday 11/2
| Read before class and do exercises: | Zybook 6.1, 6.2, 6.4 |
| Read after class: | Rosen 9.1, 9.4.1–9.4.4 |
binary relations
a relation as a set
notation x R y
functions as relations
properties of binary relations
reflexive
symmetric
antisymmetric
transitive
composite relation
R^n
paths in directed graphs
closures of relations
definition of a closure
reflexive closure
symmetric closure
transitive closure
Wednesday 11/4
| Read before class and do exercises: | Zybook 6.3, 6.5, 6.7, 3.7, 6.8 |
| Read after class: | Rosen 9.5, 9.6.1–9.6.6 |
paths in directed graphs
reflexive transitive closure
equivalence relations
definition of an equivalence relation
equivalence classes
partitions
partial and total orderings
partial orderings
total orderings
lexicographic ordering
Hasse diagrams
order relations
maximal and minimal elements
upper and lower bounds
lattices
topological sorting
Friday 11/6
| Quiz 4 | Material covered on 10/26, 10/28 and 10/30 |
| Read before class and do exercises: | Zybook 9.1, 9.2, 9.6, 9.7 |
| Read after class: | Rosen 4.1, 4.2.1, 4.2.2, 4.2.4 |
elementary number theory
the division theorem
modular arithmetic
efficient modular arithmetic
modular exponentiation
congruences
representation of integers
radix notation
conversion from decimal to base b
conversion from base b to decimal
Monday 11/9
| Read before class and do exercises: | Zybook 9.3, 9.6 |
| Read after class: | Rosen 4.3.1–4.3.3, 4.3.6, 4,3,7, 4.4.1, 4,4,2 |
greatest common divisors
least common multiples
relatively prime integers
Euclid's algorithm
prime and composite numbers
there are infinitely many primes
the prime number theorem
solving congruences
multiplicative inverses
(extended Euclidean algorithm)
Wednesday 11/11
| Read before class and do exercises: | Zybook 9.8 |
| Read after class: | Rosen , 4,4.5, 4.4.6, 4.6.1–4.6.3 |
determining primality
trial division
fast randomized primality checking
Fermat's Little Theorem
pseudo-primes
Carmichael numbers
cryptograpy
classical cryptography
public-key cryptograpy
the RSA public key cryptosystem
Friday 11/13
| Quiz 5 | Material covered on 11/2, 11/4 and 11/6 |
| Read before class and do exercises: | Zybook 9.9 |
| Read after class: | Rosen 4.6.4–4.6.7 |
Monday 11/16
Review