CS 173: Skills list for first CBTF test

The CBTF test will have 5 multiple choice questions on topics related to propositional and predicate logic. The specific skills it will test are

• 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 distributive, commutative, and associative laws and that "p implies q" is equivalent to "(not p) or q".
  • Know the meaning of the universal and existential quantifier, shorthand notation, and basic terminology.
  • Translate between English and logical shorthand. But we realize that it's hard to pin down the exact meaning of some English sentences.
  • 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.
  • Know the definitions of satisfiability and validity. Given an expression, figure out whether it is satisfiable/valid.
  • 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.