Discrete Mathematics
What is Discrete Mathematics?
A collection of distinct and well-defined objects.
Key formula / rule: Cardinality of Union of Two Sets
Key points
- Define and identify sets and their elements.
- Perform basic set operations.
- Understand the concepts of subsets, power sets, and cardinality.
- Apply set theory principles to solve problems.
Common exam trap
Confusing elements with subsets.
Definitions
- Term
Set
- Meaning
A collection of distinct and well-defined objects.
- Term
Element
- Meaning
An individual object belonging to a set.
- Term
Subset
- Meaning
A set A is a subset of set B if all elements of A are also elements of B (denoted A ⊆ B).
- Term
Union
- Meaning
The set containing all elements that are in set A, or in set B, or in both (denoted A ∪ B).
- Term
Intersection
- Meaning
The set containing all elements that are common to both set A and set B (denoted A ∩ B).
- Term
Complement
- Meaning
The set of all elements in the universal set that are not in set A (denoted A').
- Term
Cardinality
- Meaning
The number of elements in a set (denoted |A|).
Learning objectives
Define and identify sets and their elements.
Perform basic set operations.
Understand the concepts of subsets, power sets, and cardinality.
Apply set theory principles to solve problems.
Formulae
- Name
Cardinality of Union of Two Sets
- Note
Useful for counting problems involving overlapping groups.
- Expression
|A ∪ B| = |A| + |B| - |A ∩ B|
- Name
Cardinality of Union of Three Sets
- Note
Principle of Inclusion-Exclusion for three sets.
- Expression
|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|
- Name
Power Set Size
- Note
Where |S| is the number of elements in set S.
- Expression
|P(S)| = 2^|S|
Prerequisites
Basic understanding of mathematical notation.
Familiarity with logical connectives (AND, OR, NOT).
Common mistakes
Confusing elements with subsets.
Incorrectly applying set operations (e.g., confusing union and intersection).
Assuming order matters in a set (sets are unordered).
Not distinguishing between a set and its elements (e.g., {a} vs. a).
Keywords
Set
Element
Union
Intersection
Difference
Complement
Subset
Power Set
Cardinality
Venn Diagram
Inclusion-Exclusion Principle
Practice preview
Let A = {1, 2, 3, 4, 5} and B = {4, 5, 6, 7}. What is the cardinality of the set A union B?…
easy
Consider a set A = {1, 2, 3, 4, 5}. How many distinct binary relations can be defined on A that are both reflexive and symmetric?…
hard
Let f: Z -> Z be a function defined by f(x) = 2x + 1. Which of the following statements is TRUE about f?…
medium