Introduction to Discrete Structures

Sets

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 of S

Partitions

Partitions and Proof by Case Enumeration

Partitions and Code for Solving Problems

Finite State Machines Partition Inputs

Operations on Sets

Venn Diagrams

Union

Intersection

Subtraction (Set Difference)

Complement

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

Relations

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

Soundex

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

Reflexivity

Symmetry

Transitivity

Reviewing the Properties

Patterns of Pattern Combinations

Proving Claims about Properties of Relations

Equivalence Relations

What Is an Equivalence Relation?

Examples of Equivalence Relations

Partitions

Equivalence Classes

Proving that a Relation is an Equivalence Relation

Soundex (Again)

Finite State Machines (Again)

Functions

Introduction

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