CS 173: Skills list for Examlet 1
- 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.
- Logic and Proof techniques.
- Write a simple direct proof, using familiar concepts,
with good mathematical style. Make sure your statements are in logical order,
starting with the given information and ending with what you needed to show.
- Write a proof by cases
- Convert a claim to its contrapositive and prove that using
direct proof.
- Write a proof by contradiction.
- Know how to prove if and only if statements by proving implications in each direction.
- Know the following standard ways to approach parts of a proof:
- prove a universal claim by choosing a representative object
of the appropriate type
- prove an if/then statement by assuming whatever's in the
hypothesis and proving the conclusion,
- disprove a universal claim by giving a concrete counterexample.
- prove an existential claim by giving specific values that make
the claim true