The material presented in this guide covers the concepts emphasized on Test 1. It is meant to guide students studying and reviewing for Test 1; it is not guaranteed to be comprehensive. Actual test questions will differ from the examples given here. Students should use this guide in addition to other study activities (like re-reading Chapters 1–3, reviewing completed assignments, worksheets, quizzes, etc.)

Things to know:

- Set notation and relations:
- Set roster vs. set builder notation
- Standard sets (natural numbers, integers, etc.)
- Finite vs. infinite sets
- Cardinality
- Set operations: intersection, union, complement
- Cartesian product, power sets
- Summation notation

- Combinatorics:
- Rule of products
- Permutations
- Combinations
- Partitions
- Law of addition
- Principle of inclusion/exclusion

- Mathematical logic:
- Propositions, logical statements
- Truth tables
- Logical connectives: AND, OR, NOT, IMPLIES, IFF
- Tautologies and contradictions
- Equivalences and inference rules (handout provided)
- Valid arguments
- Quantified statements, scope

- Proof techniques:
- direct
- counterexample
- contradiction,
- contrapositive
- mathematical induction

The necessary equivalence rules and inference rules will be provided, so you so not need to memorize them. You need to know how to use the equivalence and inference rules within a proof, though.

You will be asked to write one "assembly language" level proof, one "higher-level" non-inductive proof, and one proof using mathematical induction.