# Midterm Syllabus – Discrete Math (V63.0120)

**You may see variants on problems:**

- from the homework/quizzes (including bonus problems)
- from the textbook examples
- from the class

## Sequences

- Closed form ↔ recursive (verification or derivation)
- in many cases, easier to go from closed form to recursive: compute {$a_n - a_{n-1}$}

- Derive closed form for arithmetic series as done for Gauss' formula for {$\sum_{i=1}^n i$}

## Propositional logic

- Translate English ↔ propositional logic notation.
- {$\land, \lor, \neg, \rightarrow$}
- truth tables
- implication {$\equiv$} contrapositive, converse {$\equiv$} inverse
- predicates, quantifiers, negation of expressions
- duality: swap ({$\land$} & {$\lor$}) and ({$T$} & {$F$})

## Mathematical writing

- definitions or terms (e.g. divisible, even/odd, primes, relatively prime, rational/irrational)

## Sets

- set builder notation
- {$\cup, \cap, ', \setminus$}
- Venn diagrams
- power sets - set of subsets
- Cartesian product and {$n$}-tuples
- duality: swap ({$\cup$} & {$\cap$}) and ({$U$} & {$\emptyset$})
- size

## Boolean Algebra

- 4 properties: commutative, distributive, identity, negation

## Arguments and Proofs

- Properties on pg 222
- Modus ponens, modus tollens, converse fallacy, inverse fallacy
- Identifying flaws/fallacies in existing proofs
- Proofs of
- Tautologies - truth tables; simplify using equivalences until you get {$T$}
- Argument validity - {$p_1, p_2, p_3, …, p_n, \therefore q$} is valid if {$(p_1 \land p_2 \land p_3 \land … \land p_n) \rightarrow q$}
- Predicate equivalences or Set equalities using the properties on pg 222
- Number properties
- Subset relations {$A \subseteq B$}
- Set equalities {$A = B$} by showing {$A \subseteq B$} and {$B \subseteq A$}

- Strategies/theorems
- Contrapositive - always check if a theorem is easier to prove using the contrapositive
- Cases
- Division theorem - very often used for proof by cases
- Induction - helps to write things recursively. You want to show, for example,
- {$P(1)$} (base step)
- {$P(m-1) \rightarrow P(m)$} (induction step)

- Contradiction
- Pigeonhole principle - state explicitly that you are using pigeonhole principle when applicable