Introduction to Discrete Structures


The Key Ideas

What Is a Set?

Some Important Sets

Sets, Multisets and Lists†††††††††

Defining a Set

Using Sets in Logical Expressions†††††††

How Large is a Set?††††

Subsets, Supersets, Powersets and Partitions††††††††††††† ††

Subsets and Supersets††††††††††††

Sets of Sets†††††

The Powerset ofS†††††


Partitions and Proof by Case Enumeration††

Partitions and Code for Solving Problems

Finite State Machines Partition Inputs†††††††††††††

Operations on Sets††††

Venn Diagrams††††††††††††



Subtraction (Set Difference)††


Insertion and Deletion††††††††††††

Summary of Set Operations††

Venn Diagrams for Larger Expressions†††††††††††††

Operator Precedence

The Natural Analogy between Sets and Logic†††††††††††††

The Big Idea

Set Operations / Logical Operations††

Making Sure That We Donít Write Nonsense

Proving Claims about Sets††† ††

Convert the Set Problem to a Logic Problem†††††††††††

Set Identities††

Generalized Union and Intersection††

Law of the Excluded Middle†††

Computing Set Values

Inference Rules†††††††††††

Proving that Two Sets Are Equal

Proving the Correctness of the Identities and the Inference Rules†††††

Proving Claims about Sets by Converting to Logical Claims

Working Directly with Set Expressions

Proving Claims about Subsets

Proving that Two Sets are Equal Using Two Subset Relationships

Proving Claims about Powersets††††††††

Proof by Counterexample††††††

The Inclusion/Exclusion Principle†††††††

Computer Representation of Sets

Concrete Representations of Sets†††††

Bit Vector Representations of Sets††††

Set Operations Using Bit Vector Representations††††††††††

Multisets††††††† ††

The Key Idea†††

The Fundamental Theorem of Arithmetic††††††† ††


Ordered Tuples and Cartesian Products

Relating Elements of Sets†††††††

Ordered Pairs

Ordered N-Tuples†††††††

Cartesian Products†††††

Generalizing to More Sets††††††

Relations††††††† ††

Binary Relations††††††††††

n-ary Relations††††††††††††

The Inverse of a Binary Relation†††††††††

Composing Binary Relations††††

Composition Describes a Path

Composing a Binary Relation with Itself

Composing a Binary Relation with Its Inverse


Making Sure That We Donít Write Nonsense

Representing Binary Relations††††

Approaches to Representation†††††††††††

Undirected Graphs

Directed Graphs††††††††††

Using a Directed Graph to Represent a Relation†††††††††††

Using an Adjacency Matrix††††

Properties of Binary Relations on a Set

The Special Nature of Binary Relations on a Set†††††††††††

Modular Arithmetic




Reviewing the Properties

Patterns of Pattern Combinations

Proving Claims about Properties of Relations†††††††††

Equivalence Relations††††

What Is an Equivalence Relation?

Examples of Equivalence Relations


Equivalence Classes

Proving that a Relation is an Equivalence Relation

Soundex (Again)

Finite State Machines (Again)



What Is a Function?

Not All Relations Are Functions

Unary Functions, Binary Functions

The Function Distinction Matters for Programmers

Properties of Functions

One-to-One and Many-to-One Functions

Onto Functions

One-to-One and Onto Functions

When Are These Properties Important

Pigeonhole Principle††

Counting Arguments and the Pigeonhole Principle

Extended Pigeonhole Principle

Hash Functions

Composition, Inverses and the Identity

Function Composition

Why Function Composition is a Big Deal for Programmers

The Inverse of a Function

The Inverse Isnít Always a Function

When is f-1 a Function?

The Identity Function