CS 173: Skills list for second CBTF test

The CBTF test will have 5 multiple choice questions on topics related to predicate logic, sets, functions, and relations. The specific skills it will test are

• Predicate Logic
  • Know the meaning of exists and for all quantifiers.
  • Know how to translate between English and predicate logic, statements involving quantifiers
  • Know to read and interpret formulas with nested quantifiers
  • Know how to negate expressions with quantifiers
• Set Theory
  • Notation
    • set builder notation for defining sets
    • set membership and inclusion notation: ⊆, ∈
    • special symbol for the empty set: ∅
    • an ordered pair, triple, n-tuple
  • Define formally, be familiar with standard notation, compute the values for concrete input sets
    • A is a subset of B
    • The cartesian product of two sets A and B, of three or more sets
    • The cardinality of a set
    • The complement of a set (given some specified universe).
    • The union, intersection, and difference of two sets.
  • Know the meaning of the term disjoint.
  • Know what happens if one of the inputs to these operations is the empty set.
  • Given a simple set relationship, recognize whether it's correct or not. If not, show a counter-example.
  • Cardinality
    • Given the cardinality of two sets A and B, compute the cardinality of their Cartesian product.
    • Given the cardinality of a set A, compute the cardinality of the power set of A.
• Functions
  • Know the basic notation f:A→B. Know the meaning of the terms domain, co-domain, image (of the function), pre-image (of a value in B).
  • Define the composition of two functions. Compute the composition of two specific functions.
  • One-to-one and Onto
    • Define what it means for a function function to be one-to-one, onto, bijective, increasing, strictly increasing.
    • Be able to identify whether a function has one of these properties.
• Relations
  • Define a relation R from A to B, using the notation xRy.
  • Know the relationship between functions, relations, and Cartesian products.