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