CS 173, Fall 2014: Skills list for first examlet
- Math prerequisites
- Algebraic manipulations with
- 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
- 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+,
- 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
shorthand notation, and basic terminology such as "scope" of a
- Translate between English and logical shorthand. But we
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
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
Know that the contrapositive is equivalent to the original statement,
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.