CS 173, Spring 2009
Skills list for first quiz

The first quiz will cover the material presented in lectures 1-8. Since you have not yet had time to do homework problems on the material from lectures 6-8, 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:

• Administrative issues
  • Know the day and time that your assigned discussion section meets.
• 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 and perhaps quantifiers.
  • Know DeMorgan's laws and the distributive laws.
  • Given another simple logical equivalence (e.g. one the ones in the tables on Rosen pp. 24-25) recognize whether it's correct or not. Explain why using a truth table or 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.
• 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 odd, x is even
    • 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
  • Special cases for divides: zero is even, zero divides itself but not any other integer, and every integer divides zero.
  • Special cases for prime: 0 and 1 are not prime (primes must be greater than or equal to 2).
  • Know the definitions of the following functions, compute output values given specific input values:
    • a mod m
    • gcd(a,b) and lcm(a,b) NOTE: GCD and LCD WILL NOT BE ON THE FIRST QUIZ
    • ⌈ x ⌉ and ⌊ x ⌋
  • Write any (small) positive integer as a product of primes.
  • Know that there are infinite many primes.
  • Be able to state the Fundamental Theorem of Arithmetic (any positive integer can be written as the product of primes).
• Numbers and sets
  • Know what sets these symbols represent: R, N, Z, Z+, Q, C.
  • Kotation for set membership, e.g. x ∈ Z
  • Know that 0 belongs to N but not Z+. (For this class.)
  • Know that sqrt(2) is not rational.
  • Remember key equations for manipulating logs and exponentials (see notes for lecture 2).
• Summations
  • Know how to read summation notation, i.e. convert between it and a list of terms with ellipsis (...). Same for product notation.
  • Extract the first or last term in a sum or product.
  • Rewrite a sum or product with different bounds on the index variable.
  • Know the closed forms for special summations: sum of all integers from 1 to n, sum of (1/2)ⁱ from 0 to n.