CS 173: Skills list for Examlet 1

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 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.