6120a Discrete Mathematics And Proof For Computer Science Fix May 2026

| Week | Topic | |------|-------| | 1 | Propositional logic, truth tables | | 2 | Predicate logic, quantifiers | | 3 | Proof strategies (direct, contrapositive, contradiction) | | 4 | Mathematical induction | | 5 | Sets, relations, functions | | 6 | Number theory & modular arithmetic | | 7 | Combinatorics: counting, permutations, combinations | | 8 | Binomial theorem, pigeonhole principle | | 9 | Recurrence relations | | 10 | Graph theory basics, connectivity | | 11 | Trees, spanning trees | | 12 | Finite automata (optional introduction) | | 13 | Review & applications (e.g., RSA, graph coloring) | | 14 | Final exam |

| Concept | Fixed Notation | |-----------------------|------------------------------| | Natural numbers | ℕ = 0, 1, 2, … (specify if 1‑based) | | Empty set | ∅ | | Set difference | A \ B (not A − B) | | Complement (relative) | ∁_U A or ~A when U is clear | | Power set | 𝒫(A) | | Tuple | (a₁, a₂, …, aₙ) | | Relation composition | R ∘ S | | Floor/ceiling | ⌊x⌋, ⌈x⌉ | | Graph G | (V, E) | | Binomial coefficient | (\binomnk) (not C(n,k) unless specified) | | Implication | P → Q (not P ⇒ Q) for object language | | Logical equivalence | P ≡ Q |

All proof exercises must use this fixed notation.

Whenever you see ∀x (P(x) → Q(x)), translate it to ∀x (¬P(x) ∨ Q(x)). Then the negation becomes mechanical using De Morgan’s laws. | Week | Topic | |------|-------| | 1

Negation of an implication (common exam question): ¬(P → Q) ≡ (P ∧ ¬Q). Fix: To disprove "All swans are white," you find one black swan. You do not need to examine all swans.

Memorize this equivalence: (P → Q) ≡ (¬P ∨ Q). If you ever get confused by an implication, rewrite it as an OR.

Example Fix:

6120A: Discrete Mathematics and Proof for Computer Science (Fixed Edition) is not merely a collection of topics but a rigorous, unified, and notationally consistent foundation. By fixing ambiguities, standardizing proof templates, and tightly coupling each concept to a computational motivation, the course prepares students to read research papers, reason about algorithms, and write machine‑checked proofs. The “fix” in the title signals a deliberate correction of common pedagogical flaws — transforming discrete math from a memorization chore into a powerful, reliable tool for computer science.

This write‑up can serve as a syllabus blueprint, a study guide, or a reference for self‑learners seeking a corrected and deepened treatment of the subject.

Since specific syllabi vary by university, this report assumes a standard graduate or advanced undergraduate curriculum for a course with this code (often associated with "fixed" or formalized approaches to mathematical reasoning in CS). This report is designed to be used as a template for departmental review, curriculum planning, or student guidance. Whenever you see ∀x (P(x) → Q(x)) ,

Discrete mathematics forms the logical backbone of computer science. Unlike continuous math (calculus), discrete math deals with distinct, separated values — integers, graphs, statements, sets.
Course 6120A typically emphasizes:

The “fix” part means addressing gaps in problem-solving or proof-writing.

To prove no odd cycle exists (bipartite graphs): Memorize this equivalence: (P → Q) ≡ (¬P ∨ Q)