CS 173, Fall 2014: Skills list for twelfth examlet
- Logic and proofs
- Recap from the past: give the negation of a statement or the contrapositive
(if/then statements only), simplifying it
so that all negations are on individual propositions/predicates.
- Write a proof by contradiction.
- Collections of sets
- Manipulate sets containing other sets using standard set operations.
(Be careful of getting
the right number of brackets in examples involving the empty set and
sets with only one element.)
- Define the power set P(A) for a set A.
- Given a specific set A, list the elements of its power set.
- Correctly interpret set-builder definitions of sets containing other sets.
- Correctly interpret definitions for functions whose input and/or output values are sets.
- Write simple proofs involving collections of sets, functions whose input and/or output values are sets.
- Define a partition of a set A.
- Determine whether a specific set is a
partition of some specific set A.
- Know that the equivalence classes of an
equivalence relation form a partition.
- Know the shorthand notation for binomial coefficients (number of combinations)
and its definition in terms of factorials.
- Know the formula for computing the number of combinations of k objects from
n types, with repetition.
- Know the Binomial Theorem and Pascal's Identity
- Be able to solve practical counting
problems involving combinations,
combinations with repetition, and applications of the Binomial Theorem.