CS 173, Fall 2008: Skills list for first midterm

The first midterm will cover the material presented in lectures 1-14. Since you have not yet had time to do homework problems on the material from lectures 12-14, only more basic aspects of this material will be tested. The corresponding sections of Rosen are listed on the Lectures web page.

Specific skills you should know include:

• 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 how to negate each logical operator (especially implies and the two quantifiers). Use these rules to negate larger expressions containing multiple operators.
  • Know DeMorgan's laws and the distributive laws.
  • Given another simple logical equivalence (e.g. the ones in the tables on Rosen pp. 24-25) recognize whether it's correct or not. If not, show a counter-example.
  • Identify 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.
  • Given a statement, give its negative, converse, and contrapositive. Know that the contrapositive is equivalent to the original statement, but the converse is not.
  • Know that a statement of the form ∀ x, ∃ y P(x,y) is not equivalent to the statement ∃ y, ∀ x, P(x,y). We will not assume you fully understand the meaning of nested combinations of existential and universal quantifiers.
• Number Theory
  • Quote back definitions, decide if simple statements involving them are true, understand the corresponding shorthand notation:
    • a divides b, b is a multiple of a,
    • x is prime, x is composite
    • x is a perfect square
    • x is a rational number
    • x is congruent to y modulo m
    • x and y are relatively prime
  • Know the definitions of the following functions, compute output values given specific input values:
    • a mod m
    • gcd(a,b) and lcm(a,b)
    • ⌈ x ⌉ and ⌊ x ⌋
  • State the division algorithm.
  • Compute the gcd of two larger numbers using the Euclidean algorithm. (We won't make you write out the algorithm itself.)
  • Know that any positive integer can be written as the product of primes. Do this for a specific integer. Know that there are infinite many primes.
  • Prove simple number theory claims using direct proof and the above definitions. For example, if a divides b and a divides c, then a divides b+c.
• Set Theory
  • Notation
    • standard sets: R, N, Z, Q. Know that we're defining N to include 0.
    • 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 power set of A
    • 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.
  • Given a simple set identitie (e.g. the ones in the tables on Rosen pp 124-125) recognize whether it's correct or not. If not, show a counter-example.
  • Know DeMorgan's laws and the distributive laws.
  • Know how to compute the cardinality of a set created using operations such as union, cartesian product, power set.
  • Given a set identity, recognize whether it's true. If not, give a counter-example.
  • Prove a set inclusion relationship of the form A ⊆ B, by picking a representative element from A and show that it's a member of B.
• Functions
  • Know the basic notation f:A→B. Know the meaning of the terms domain and co-domain.
  • Be able to quote back the definition of when a function is one-to-one (injective) and onto (surjective). Given a familiar function (e.g. absolute value on the integers), identify whether it's one-to-one and/or onto.
• Proof techniques.
  • Be able to write a simple direct proof, using familiar concepts, with good mathematical style.
  • Be able to convert a claim to its contrapositive and prove that using direct proof.
  • Given a claim, outline a proof by contradition. Fill in details of the proof if it involves familiar concepts.
  • 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,
    • prove an existential claim by exhibit specific values that make the claim true
  • Disprove a universal claim by exhibiting a counterexample.
  • Identify mistakes in proofs, where the proof is of a type we've said you should know how to write.