Discrete Mathematics — Final Reviewer

Reviewer

Study Notes Click each topic to expand. Use this as your main reading guide.

📌 Study Tip: Focus on the formal notation for each relation property, and practice checking sets step-by-step. For set operations, always draw a Venn diagram mentally first.

Topic 1 Basic Set Theory — Definitions & Types ⌄

What is a Set?

A set is a well-defined collection of distinct objects called elements or members.
Sets are denoted by capital letters (A, B, C) and elements are listed inside curly braces {}.
Well-defined means there is a clear rule — you can always tell if something belongs or not.
Elements are unique (no duplicates) and order does not matter — {1,2,3} = {3,2,1}
∈ means "is an element of"; ∉ means "is NOT an element of"
Example: A = {2, 4, 6, 8} is well-defined. B = {x | x is beautiful} is NOT well-defined.

Types of Sets

Empty Set (∅) — Contains no elements at all. Also called the null set. Notation: ∅ or {}
Finite Set — Has a limited, countable number of elements. Ex: A = {1,2,3,4,5}
Infinite Set — Has unlimited elements, indicated by ellipsis. Ex: N = {1,2,3,…}
Universal Set (U) — Contains all elements under consideration in a given context.
Real-life: Universal set = all students in a school; Subset = students in the IT department

Cardinality

Cardinality |A| or n(A) = the number of elements in a set (its "size")
Example: If A = {2,4,6}, then |A| = 3
Empty set cardinality: |∅| = 0
Infinite sets have infinite cardinality.

Topic 2 Set Operations — Union, Intersection, Difference, Complement ⌄

The Four Basic Operations

Union (A ∪ B) — All elements in A or B or both. Combines both sets, no duplicates.
- A = {1,2}, B = {2,3} → A ∪ B = {1,2,3}
Intersection (A ∩ B) — Only elements common to BOTH A and B.
- A = {1,2}, B = {2,3} → A ∩ B = {2}
Difference (A − B) — Elements in A but NOT in B.
- A = {1,2,3}, B = {2,3,4} → A − B = {1}
Complement (A' or Aᶜ) — All elements in U that are NOT in A.
- U = {1,2,3,4,5}, A = {1,2} → A' = {3,4,5}

Key Laws of Sets

Commutative Law — Order doesn't matter: A ∪ B = B ∪ A and A ∩ B = B ∩ A
Associative Law — Grouping doesn't matter: (A ∪ B) ∪ C = A ∪ (B ∪ C)
Distributive Law — A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) and A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
De Morgan's Laws — (A ∪ B)' = A' ∩ B' and (A ∩ B)' = A' ∪ B'

Topic 3 Venn Diagrams ⌄

What Are Venn Diagrams?

Venn diagrams visually represent sets and their relationships using overlapping circles inside a rectangle (universal set).
Union (A ∪ B) → Both circles shaded entirely
Intersection (A ∩ B) → Only the overlapping region shaded
Difference (A − B) → Only the part of A not overlapping B is shaded
Complement (A') → Everything outside circle A (but inside U) is shaded

Uses of Venn Diagrams

Visualizing and solving set operations
Understanding overlaps between groups (e.g., students who passed both subjects)
Solving logic and probability problems
Three-circle Venn diagrams (A ∪ B ∪ C) can show all seven distinct regions

Venn Diagram Laws (visual)

Commutative: A ∪ B = B ∪ A — the shaded region looks the same regardless of which set is "first"
Associative: Grouping does not change the final shaded region
Distributive: Breaking apart the operation step-by-step yields the same result

Topic 4 Relations — Definition & Formation ⌄

What is a Relation?

A relation is a connection between elements of two sets (Set A and Set B).
Formal definition: R ⊆ A × B ("R is a subset of A cross B")
A × B = the Cartesian Product = all possible ordered pairs from A and B
A relation R = a selected subset of those pairs — not all pairs need to be included
Example: A = {1,2,3}, B = {a,b} → A×B has 6 pairs; R = {(1,a),(2,b),(3,a)} is a valid relation

How Relations Are Formed

By selection — Randomly pick ordered pairs from A × B
By rule — Apply a condition to determine which pairs are included
- Example rule: "odd numbers relate to a; even numbers relate to b"
- Produces: R = {(1,a), (2,b), (3,a)}

Topic 5 Properties of Relations — Reflexive, Symmetric, Antisymmetric, Transitive ⌄

1. Reflexive Relation

Definition: (a, a) ∈ R for all a ∈ A — every element is related to itself
Every element must have a self-pair (a, a). Missing even ONE self-pair = NOT reflexive.
Extra pairs like (1,2) do NOT affect reflexivity.
✔ Reflexive: A={1,2,3}, R={(1,1),(2,2),(3,3),(1,2)}
✗ Not Reflexive: A={1,2,3}, R={(1,1),(2,2)} — missing (3,3)

2. Symmetric Relation

Definition: (a,b) ∈ R ⇒ (b,a) ∈ R — if a is related to b, then b must also be related to a
The relation must "go both ways." Every pair (a,b) must have its reverse (b,a) also present.
Self-pairs like (a,a) always satisfy symmetry (they are their own reverse).
✔ Symmetric: R = {(1,2),(2,1),(3,3)}
✗ Not Symmetric: R = {(1,2),(3,3)} — missing (2,1)

3. Antisymmetric Relation

Definition: (a,b) ∈ R and (b,a) ∈ R ⇒ a = b
If both directions exist for two different elements, the relation is NOT antisymmetric.
Self-pairs (a,a) do NOT violate antisymmetry since a = a.
✔ Antisymmetric: R = {(1,1),(2,2),(3,3),(1,2)} — (2,1) is absent, so no violation
✗ Not Antisymmetric: R = {(1,2),(2,1)} — both directions exist for 1≠2

4. Transitive Relation

Definition: (a,b) ∈ R and (b,c) ∈ R ⇒ (a,c) ∈ R
If there is a "chain" a → b → c, there must be a direct pair (a,c).
Only check when a chain (a,b) and (b,c) actually exists. No chain = possibly still transitive.
✔ Transitive: R = {(1,2),(2,3),(1,3)} — chain 1→2→3 forces (1,3) ✔
✗ Not Transitive: R = {(1,2),(2,3)} — missing (1,3)

Quick Comparison Table

Reflexive — (a,a) must exist for ALL a ∈ A
Symmetric — (a,b) → must have (b,a) for ALL pairs
Antisymmetric — (a,b) and (b,a) together forces a = b
Transitive — (a,b) + (b,c) → must have (a,c)

Terms

Key Terminology Click any card to reveal its definition.

Set Theory

Set

A well-defined collection of distinct objects called elements. Denoted by capital letters; elements listed in curly braces {}.

Set Theory

Element / Member

An individual object contained in a set. Each element is unique — no duplicates allowed. Order does not matter.

Set Theory

Well-Defined

A set has a clear rule so it is unambiguous whether any object belongs to it or not.

Set Theory

Empty Set (∅)

A set with no elements at all. Also called the null set. Denoted as ∅ or {}. Its cardinality is 0.

Set Theory

Finite Set

A set that has a limited, countable number of elements. Example: A = {1, 2, 3, 4, 5}.

Set Theory

Infinite Set

A set with an unlimited number of elements that cannot be fully counted. An ellipsis (…) shows the pattern continues.

Set Theory

Universal Set (U)

The set containing all elements under consideration in a particular context. All other sets are subsets of U.

Set Theory

Cardinality |A|

The number of elements in a set. Written as |A| or n(A). If A = {2,4,6}, then |A| = 3.

Set Theory

Subset (⊆)

Set A is a subset of B if every element of A is also in B. Written A ⊆ B. Every set is a subset of itself.

Set Theory

Venn Diagram

A visual tool using overlapping circles inside a rectangle to represent sets and their relationships (union, intersection, difference, complement).

Operations

Union (A ∪ B)

All elements in A or B or both. No duplicates. If A={1,2} and B={2,3}, then A∪B={1,2,3}.

Operations

Intersection (A ∩ B)

Elements common to BOTH A and B. If A={1,2} and B={2,3}, then A∩B={2}.

Operations

Difference (A − B)

Elements in A but NOT in B. If A={1,2,3} and B={2,3,4}, then A−B={1}.

Operations

Complement (A')

All elements in the universal set U that are NOT in A. If U={1..5} and A={1,2}, then A'={3,4,5}.

Operations

Cartesian Product (A×B)

The set of all possible ordered pairs (a, b) where a ∈ A and b ∈ B. If |A|=m and |B|=n, then |A×B|=mn.

Operations

Commutative Law

Order of sets does not affect result. A∪B = B∪A and A∩B = B∩A.

Operations

Associative Law

Grouping of sets does not affect result. (A∪B)∪C = A∪(B∪C) and (A∩B)∩C = A∩(B∩C).

Operations

Distributive Law

Connects union and intersection. A∩(B∪C) = (A∩B)∪(A∩C) and A∪(B∩C) = (A∪B)∩(A∪C).

Operations

De Morgan's Laws

(A∪B)' = A'∩B' and (A∩B)' = A'∪B'. The complement distributes and flips the operation symbol.

Relations

Relation (R)

A subset of the Cartesian product A×B. Formally: R ⊆ A×B. It shows how elements of Set A are connected to elements of Set B.

Relations

Ordered Pair

A pair (a, b) where order matters — (a,b) ≠ (b,a) unless a = b. The building block of relations.

Relations

Reflexive Relation

(a,a) ∈ R for all a ∈ A. Every element must be related to itself. Missing even one self-pair means NOT reflexive.

Relations

Symmetric Relation

(a,b) ∈ R ⇒ (b,a) ∈ R. If a relates to b, then b must also relate to a. The relation must "go both ways."

Relations

Antisymmetric Relation

(a,b) ∈ R and (b,a) ∈ R ⇒ a = b. If both directions exist between different elements, the relation is NOT antisymmetric.

Relations

Transitive Relation

(a,b) ∈ R and (b,c) ∈ R ⇒ (a,c) ∈ R. A "chain" a→b→c requires a direct pair (a,c).

Relations

Rule-Based Relation

A relation formed by applying a specific rule or condition to determine which ordered pairs are included, rather than selecting randomly.

Relations

Self-Pair

An ordered pair of the form (a, a) where both elements are the same. Required for reflexive relations; always satisfies symmetry.

Multiple Choice

Multiple Choice Click an option to check your answer. 25 questions total.

SCORE

0 / 25

Which of the following is a well-defined set?

A {x | x is a beautiful number}
B {x | x is an even number less than 10}
C {x | x is a good student}
D {x | x is a tall person}

If A = {1, 2, 3} and B = {2, 3, 4}, what is A ∪ B?

A {2, 3}
B {1, 4}
C {1, 2, 3, 4}
D {1, 2, 3, 4, 5}

What is A ∩ B if A = {1, 2, 3, 4} and B = {3, 4, 5, 6}?

A {1, 2, 5, 6}
B {3, 4}
C {1, 2, 3, 4, 5, 6}
D {1, 2}

If U = {1,2,3,4,5} and A = {2,4}, what is A'?

A {1, 3, 5}
B {2, 4}
C {1, 2, 3, 4, 5}
D {3, 5}

What is A − B if A = {1,2,3,4} and B = {2,4,6}?

A {2, 4}
B {6}
C {1, 3}
D {1, 2, 3, 4, 6}

The cardinality of the set A = {a, b, c, d, e} is:

Which law states that A ∪ B = B ∪ A?

A Commutative Law
B Associative Law
C Distributive Law
D De Morgan's Law

A = {1,2,3} and R = {(1,1),(2,2),(3,3),(1,2)}. Which property does R have?

A Symmetric
B Transitive only
C Neither reflexive nor antisymmetric
D Reflexive and Antisymmetric

For a relation to be symmetric, which condition must hold?

A (a,a) ∈ R for all a ∈ A
B If (a,b) ∈ R, then (b,a) ∈ R
C If (a,b) ∈ R and (b,c) ∈ R, then (a,c) ∈ R
D (a,b) and (b,a) ∈ R implies a = b

Let A = {1,2,3} and R = {(1,2),(2,3)}. Which property does R violate?

A Symmetric
B Reflexive
C Transitive — (1,3) is missing
D Antisymmetric

The Cartesian product A × B where A = {1,2} and B = {x,y} is:

A {(1,x),(1,y),(2,x),(2,y)}
B {(x,1),(y,2)}
C {1,2,x,y}
D {(1,2),(x,y)}

Which of the following sets is an example of an infinite set?

A Days of the week
B Months of the year
C Students in a class
D Set of all natural numbers

According to the Distributive Law, A ∩ (B ∪ C) equals:

A (A ∩ B) ∩ (A ∩ C)
B (A ∩ B) ∪ (A ∩ C)
C (A ∪ B) ∩ (A ∪ C)
D (A ∪ B) ∪ (A ∪ C)

R = {(1,2),(2,1),(3,3)} on A = {1,2,3}. Is R symmetric?

A Yes — every pair has its reverse present
B No — (3,3) violates symmetry
C No — (1,2) has no reverse
D Cannot be determined

What does the notation (A ∪ B)' mean?

A Elements in both A and B
B Elements only in A
C Elements in U but not in A or B (De Morgan: A'∩B')
D Elements in A but not B

In a Venn diagram, the shaded overlapping region of two circles represents:

A Union
B Intersection
C Difference
D Complement

A = {1,2,3} and R = {(1,1),(2,2)}. Is R reflexive?

A Yes — it has self-pairs
B No — (3,3) is missing
C Yes — a relation doesn't need all self-pairs
D It depends on the universal set

Which set law is expressed as (A ∪ B) ∪ C = A ∪ (B ∪ C)?

A Commutative Law
B Associative Law
C Distributive Law
D Identity Law

R = {(1,2),(2,1)} on A = {1,2,3}. Is R antisymmetric?

A Yes — both directions are present
B No — (1,2) and (2,1) exist with 1 ≠ 2
C Yes — antisymmetric allows both directions
D Cannot be determined without more pairs

Which of the following correctly states the formal definition of a relation?

A R ⊆ A × B
B R = A ∪ B
C R ∈ A × B
D R ∩ A × B

De Morgan's Law states that (A ∩ B)' equals:

A A' ∩ B'
B A ∪ B
C A' ∪ B'
D A' ∩ B

If {1,2,2,3} is given as a set, what is its actual set notation?

A {1,2,2,3}
B {1,2,3}
C {1,3}
D {2,3}

For a transitive relation, if (1,2) and (2,3) are in R, what must also be in R?

A (2,1)
B (3,1)
C (2,2)
D (1,3)

Which type of set contains all elements under discussion in a given context?

A Empty Set
B Finite Set
C Universal Set
D Infinite Set

Self-pairs like (a, a) in a relation — which statement is TRUE about them?

A They violate antisymmetry
B They always satisfy symmetry and do not violate antisymmetry
C They are not allowed in any relation
D They are only allowed in reflexive relations

True / False

True or False Click TRUE or FALSE to check each statement. 20 items.

SCORE

0 / 20

A set must be well-defined — its elements must be clearly identifiable.

The set {1, 2, 2, 3} has a cardinality of 4.

The empty set ∅ is a subset of every set.

A ∩ B always contains more elements than A ∪ B.

According to the Commutative Law, A ∪ B = B ∪ A.

A relation R is reflexive if at least one element relates to itself.

The pair (a, a) always satisfies the symmetric property.

A relation can be both symmetric and antisymmetric at the same time — this is always impossible.

R = {(1,2),(2,3),(1,3)} on A = {1,2,3} is transitive.

The Cartesian product is commutative: A × B = B × A in all cases.

A Venn diagram's shaded overlapping region represents the intersection of two sets.

The order of elements in a set matters — {1, 2, 3} is different from {3, 2, 1}.

For antisymmetry: if (a,b) and (b,a) are both in R, then it must be that a = b.

A − B and B − A always produce the same result.

A relation formed by a rule produces a predictable, patterned set of ordered pairs.

Every relation on a set is automatically reflexive.

De Morgan's Law: (A ∪ B)' = A' ∩ B'.

If no chain (a,b)(b,c) exists in a relation, then it is NOT transitive.

The cardinality of the empty set ∅ is 0.

A relation R ⊆ A × B is a subset of the Cartesian product of A and B.

Identification

Identification Read the clue, think of your answer, then click to reveal. 20 items.

📌 Tip: Cover the answer and try to recall it before clicking. These terms come directly from the slides.

The notation used to denote that an object is NOT an element of a set.

⌄

∉

Read as "is not an element of." Example: 5 ∉ {2,4,6,8}.

The set that contains all elements under consideration in a particular context.

⌄

Universal Set (U)

All subsets in a problem are parts of the Universal Set. Represented by the rectangle in a Venn diagram.

The number of elements in a set, written as |A| or n(A).

⌄

Cardinality

Example: A = {a, b, c} → |A| = 3. The empty set has cardinality 0.

The set operation that returns elements in A but NOT in B.

⌄

Set Difference (A − B)

Example: A={1,2,3}, B={2,3,4} → A−B = {1}.

The relation property described by: (a,a) ∈ R for all a ∈ A.

⌄

Reflexive Relation

Every element must relate to itself. Missing even one self-pair disqualifies the relation from being reflexive.

The set of all possible ordered pairs formed from elements of Set A and Set B.

⌄

Cartesian Product (A × B)

If A = {1,2} and B = {a,b}, then A×B = {(1,a),(1,b),(2,a),(2,b)}.

The law stating that A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).

⌄

Distributive Law

This law connects union and intersection operations, allowing one to be "distributed" over the other.

A relation property where if (a,b) ∈ R, then (b,a) must also be ∈ R.

⌄

Symmetric Relation

The relation must "go both ways." Self-pairs (a,a) automatically satisfy this since reversing them gives the same pair.

A diagram using overlapping circles inside a rectangle to visualize set relationships.

⌄

Venn Diagram

Used to visualize union, intersection, difference, and complement. The rectangle represents the universal set U.

The set operation combining all elements in A or B (or both), with no duplicates.

⌄

Union (A ∪ B)

Example: A={1,2}, B={2,3} → A∪B = {1,2,3}. Duplicates are counted once.

The relation property: (a,b)∈R and (b,a)∈R implies a = b.

⌄

Antisymmetric Relation

Different elements cannot relate to each other in both directions. Self-pairs (a,a) do not violate this since a = a.

A set containing no elements, also known as the null set.

⌄

Empty Set (∅)

Written as ∅ or {}. Its cardinality is 0. It is a subset of every set.

The law that says the grouping of sets in union or intersection does not change the result.

⌄

Associative Law

(A∪B)∪C = A∪(B∪C) and (A∩B)∩C = A∩(B∩C). Grouping (parentheses) can be rearranged freely.

The relation property: if (a,b)∈R and (b,c)∈R, then (a,c) must also be ∈ R.

⌄

Transitive Relation

A "chain" a→b→c requires a direct shortcut (a,c). Only needs checking when such a chain exists.

The set of all elements in U that do NOT belong to set A.

⌄

Complement of A (A' or Aᶜ)

If U={1,2,3,4,5} and A={1,2}, then A'={3,4,5}. In a Venn diagram, it is everything outside circle A.

The formal notation for a relation being a subset of the Cartesian product.

⌄

R ⊆ A × B

Read as "R is a subset of A cross B." It means R is a selection of ordered pairs from all possible pairs in A×B.

The two laws that describe how complement distributes over union and intersection.

⌄

De Morgan's Laws

(A∪B)' = A'∩B' and (A∩B)' = A'∪B'. The operation symbol flips when taking the complement of a union or intersection.

The only elements that a relation includes from A × B, based on a rule or selection.

⌄

Ordered Pairs / Selected Pairs

A relation does not need to include ALL pairs from A×B — only the selected ones that satisfy the rule or choice.

The set operation that finds elements common to BOTH A and B.

⌄

Intersection (A ∩ B)

Example: A={1,2,3}, B={2,3,4} → A∩B={2,3}. Represented by the overlapping region in a Venn diagram.

An ordered pair of the form (a, a) — element paired with itself.

⌄

Self-Pair

Required for reflexive relations. Always satisfies the symmetric property. Does not violate antisymmetry since a = a.

Essay

Essay Questions Click each question to expand the guide points for your answer.

Essay 1

Define a set and explain the concept of "well-defined." Give examples of both a well-defined and a non-well-defined set, and explain why the distinction matters in mathematics.

⌄