Discrete Mathematics for Computer Science

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