Chapter Review
83
Distributive Law for Intersection
Distributive Law for Meet
Distributive Law for Join
Distributive Law for Union
TEMPLATES
Template 1.8 Proof by Cases
Template 1.10 Proof by Contradiction
Template 1.9 Disproof by Counterexample Template 1.11 Indirect Proof
1.5 Summary
TERMS
cardinality
number of divisors
even intersection
odd intersection
hat check problem
THEOREMS
Basic Counting Theorem
Principle of Inclusion-Exclusion for
Principle of Inclusion-Exclusion
Three Sets
Principle of Inclusion-Exclusion for
Principle of Inclusion-Exclusion for Two
Finitely Many Sets
Sets
1.7 and 1.8 Summary
TERMS
algorithm
inductive step
base step
infinite loop
condition
lemma
correctness
mathematical induction
Fibonacci numbers
perfect square
finite geometric series
pseudocode
first form
recursive definition
for loop
recursively defined sequence
geometric series
selection sort
inductive assumption
while loop
inductive hypothesis
THEOREMS
Principle of Mathematical Induction
Size of a Power Set
ALGORITHMS
Perfect Squares
Square Root I
Square Root II
TEMPLATES
Template 1.12 Using the Principle of
Mathematical Induction