# 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