CS 191 Exam One Terms and Concepts

Hein Section 1.1 Proofs

• Be familiar with truth tables and know how to use them to show the truth value of statements.
• In particular, be familiar with the truth table for conditional statements.
• Understand what the contrapositive of a statement is and be able to use it in a proof.
• Be able to use proof techniques such as:
  • proof by exhaustive checking
  • direct proof of a conditional statement
  • proof by contradiction
  • iff proofs
• Some (not necessarily all) possible topics for proofs include:
  • divisibility
  • even and odd integers
  • sets (from Section 1.2)

Hein Section 1.2 Sets

• Know ways to describe sets.
• Be able to show that two sets are equal, including using subsets.
• Be able to calculate the power set of a finite set.
• Know how to draw and use Venn diagrams.
• Be familiar with the standard operations on sets including union, intersection, difference, symmetric difference and complement.
• Be able to calculate the cardinality of finite sets both abstractly and for particular sets.

Hein Section 1.3 Ordered Structures

• Know the definitions of tuple, list, and string.
• Be able to calculate the Cartesian Product of sets.
• Know about string operations including concatenation, what a language is and what the products of languages are.
• Be able to count tuples using the product rule and to use tuples to count strings with restrictions.