Discrete Mathematics for Computer Science

82 CHAPTER 1 Sets, Proof Templates, and Induction

1.12.1 Terms, Theorems, Algorithms, and Templates

1.1 Summary

TERMS

algebraic identity is a member of real numbers

empty set is an element of set

equal is contained in set-theoretic notation

factor is in subset

finite set is not an element of universal set

if and only if natural numbers universe

implication not finite sets vacuously

infinite set proper subset Venn diagram

integers rational number

THEOREM

A = B if and only if A C B and B C A

TEMPLATES

Template 1.1 Element Membership in a Set Template 1.5 Set Equality

Template 1.2 Set Inclusion Template 1.6 Set Inequality

Template 1.3 Set Non-Inclusion Template 1.7 Implications and If and Only If

Template 1.4 Proper Set Inclusion

1.3 Summary

TERMS

absolute difference disjoint sets minimum element

analogous distributive lattice power set

bit representation equivalent statements product

boolean algebra inclusive or proof by cases

bottom indirect proof relative difference

complement intersection (n) set difference

complementation inverse statement

complemented lattice join (v) symmetric difference

contrapositive lattice top

converse maximum element union (U)

counterexample meet (A)

THEOREMS

Absorption Law for Join Commutative Law for Intersection

Absorption Law for Meet Commutative Law for Join

An Absorption Law Commutative Law for Meet

Associative Law for Intersection Commutative Law for Union

Associative Law for Join DeMorgan's Law for Intersection

Associative Law for Meet DeMorgan's Law for Union

Associative Law for Union DeMorgan's Laws