CS 173, Fall 2014: Skills list for first examlet

• Math prerequisites
  • Algebraic manipulations with
    • equations
    • inequalities
    • fractions
    • absolute value
    • squares and square roots
    • i (square root of -1)
  • 2nd order polynomials: solving, factoring, finding roots. Easy cases only: don't worry if you don't remember the quadratic formula.
  • Basic rules for manipulating exponents and logs
  • Defining and composing numerical functions. E.g. if f(x) = x-6 and g(x) = 7x, then g(f(x)) = 7(x-6).
• Numbers and sets
  • Know what sets these symbols represent: R, N, Z, Z⁺, Q, C.
  • Notation for set membership, e.g. x ∈ Z
  • Know that 0 belongs to N but not Z⁺. (There's two conventions about what's in N. This is the one we are using this term.)
  • Know the notation and definition of n factorial (n!).
  • Know the notations [a,b] and (a,b) for closed and open intervals of the real line.
  • Know the definitions of the floor and ceiling functions, i.e. ⌈ x ⌉ and ⌊ x ⌋
• Propositional and predicate logic
  • Know the truth tables for basic logical operators, especially implies. Know that, unless there is specific indication otherwise, "or" means inclusive or.
  • Know the meaning of the universal and existential quantifier, shorthand notation, and basic terminology such as "scope" of a quantifier.
  • Translate between English and logical shorthand. But we realize that it's hard to pin down the exact meaning of some English sentences.
  • Know the distributive, commutative, and associative laws and that "p implies q" is equivalent to "(not p) or q".
  • Given a new, fairly simple, logical equivalence, figure out whether it's correct or not and explain why using a truth table or counter-example.
  • Identify non-statements (e.g. questions) and statements which are neither true not false, because they contain variables not bound by a quantifier.
  • Decide whether a complex statement is true, given information about the truth of the basic statements it's made out of.
  • Identify the hypothesis and the conclusion of an if/then statement.
  • Given a statement, give its negation.
  • Given an if/then statement, give its converse, and contrapositive. Know that the contrapositive is equivalent to the original statement, but the converse is not.
  • Simplify a negation or contrapositive by moving all negations onto individual propositions. This requires knowing certain key logical equivalences: double negation, DeMorgan's laws, and the rules for negating if/then statements and quantifiers.