CMSI 2820: Discrete Mathematics Cheat Sheet
Quick reference guide for course material. Sections unlock when homework is assigned.
Useful Terminal Commands
Git Commands
| Command | Description | Example | ||
|---|---|---|---|---|
| git add [file/directory/path] | Add a file/directory to the staging area. Use "." to add all changes currently in the working directory. | git add . | git add farm.py | git add src/ |
| git commit -m "[commit message]" | Commit changes to the repository. The -m flag is used to add a commit message to the commit and avoid the custom terminal interface. | git commit -m "Completed HW1! 🎉" | git commit -m "Fixed bug in farm.py" | |
| git push | Push changes to the remote repository. This will update GitHub's cloud copy of the repository with the changes you have made locally. | git push | ||
| git pull | Pull changes from the remote repository. This will update your local copy of the repository with the changes that have been made to the cloud repository. | git pull |
Python Commands
| Command | Description | Example | |
|---|---|---|---|
| python -m pytest | Run the unit tests for the current project. | python -m pytest | |
| python [file.py] | Run the file.py file. On MacOS, you may need to use `python3` instead of `python`. | python proceedings.py | python3 test_farm.py |
| python -m pip install [package] | Install a package using Python's Package Manager. | python -m pip install pytest | python -m pip install numpy |
Logic
Logical Operators
| Operator | Symbol | Meaning | Example |
|---|---|---|---|
| Negation | ¬p or ~p | NOT p | If p is true, ¬p is false |
| Conjunction | p ∧ q | p AND q | True only if both are true |
| Disjunction | p ∨ q | p OR q | True if at least one is true |
| Implication | p → q | If p then q | False only if p is true and q is false |
| Biconditional | p ↔ q | p if and only if q | True if both have same truth value |
Key Logical Equivalences
- ¬(¬p) ≡ p (Double Negation)
- p ∧ q ≡ q ∧ p (Commutative)
- ¬(p ∧ q) ≡ ¬p ∨ ¬q (De Morgan's Laws)
- p → q ≡ ¬p ∨ q (Implication)
Numbers
Divisibility Rules
- 2: Last digit is even
- 3: Sum of digits divisible by 3
- 5: Last digit is 0 or 5
- 9: Sum of digits divisible by 9
- 10: Last digit is 0
Modular Arithmetic
- a ≡ b (mod m) means m | (a - b)
- (a + b) mod m = ((a mod m) + (b mod m)) mod m
- (a × b) mod m = ((a mod m) × (b mod m)) mod m
Collections
Set Operations
| Operation | Symbol | Definition |
|---|---|---|
| Union | A ∪ B | Elements in A or B (or both) |
| Intersection | A ∩ B | Elements in both A and B |
| Difference | A - B | Elements in A but not in B |
| Complement | A' | Elements not in A |
| Cartesian Product | A × B | All ordered pairs (a, b) |
Functions
Injective (One-to-One)
f(a) = f(b) implies a = b
Each output has at most one input
Surjective (Onto)
Every element in codomain is mapped
Range equals codomain
Bijective
Both injective and surjective
One-to-one correspondence
Combinatorics
Key Formulas
- P(n,r) = n!/(n-r)! - Permutations (order matters)
- C(n,r) = n!/(r!(n-r)!) - Combinations (order doesn't matter)
- Sum Rule: If A and B are disjoint, |A ∪ B| = |A| + |B|
- Product Rule: |A × B| = |A| × |B|
Common Patterns
- Permutations with repetition: n^r
- Combinations with repetition: C(n+r-1, r)
- Pigeonhole Principle: If n+1 objects in n holes, at least one hole has 2+ objects
Graph Theory
Graph Properties
- Handshaking Lemma: Sum of all vertex degrees = 2|E|
- Complete Graph K_n: Has n(n-1)/2 edges
- Tree: Connected acyclic graph with n-1 edges (n vertices)
- Euler Path: Visits every edge exactly once
- Hamiltonian Path: Visits every vertex exactly once
Graph Types
- Bipartite: Vertices divided into 2 sets, edges only between sets
- Complete Bipartite K(m,n): All possible edges between two sets
- Planar: Can be drawn without edge crossings