Mid-term review outline

Mathematical data types

  1. Sets
    • definitions and representations of set and subset
    • set operations
    • A = B iff (A is a subset of B, and B is a subset of A)
    • finite set, cardinality, and inlusion-exclusion principles
    • power set
    • partition

  2. Relations
    • definition and representations of relation
    • compositions
    • types of relations:
      • reflective
      • symmetric
      • antisymmetric
      • transitive
    • equivalence relations
    • equivalence relation and partition

  3. Functions
    • Definition and representations
    • one-to-one, onto, and invertible function
    • composition
    • frequently used functions:
      • permutation
      • floor and ceiling
      • INT and ABS
      • remainder: k (mod m)
      • exponential
      • logarithm
    • recursively defined functions

Propositional logic and Proof techniques

  1. Propositional logic
    • Proposition
    • Compound propositions and truth tables:
      negation, conjunction, disjunction, and exclusive disjunction
    • Implication, bicondition and truth tables
    • Logical equivalence
    • Propositional functions
    • Universal and existential quantifications

  2. Proof techniques
    • Direct proof
    • Proof by contraposition
    • Proof by contradiction
    • Constructive proof
    • Proof by counterexample
    • Proof by mathematical induction

Homework problem sets and quizzes

  1. Homework problem sets #1 - #4
  2. Quizzes #1-#3