Set Theory and

Boolean Algebra
1
 Subject Outline

• Set Basics
• How to Describe a Set
• Set Properties
• Set Terminology
• Set Operation and Boolean Algebra
• Venn Diagram
• Set Identities
• Example

2
 Set Basics
Definition
A set is an unordered collection of objects, called elements or members
of the set. A set is said to contain its elements.
• We write a ∈ Ato denote that a is an element of the set A. ( = belongs to)
• The notation a ∈ A denotes that a is not an element of the set A. (
• It is common for SETS to be denoted using uppercase letters.
• Lowercase letters are usually used to denote elements of sets.

• Application: It is used as a foundation for many subfields of mathematics. In

the areas pertaining to statistics, probability, Boolean, ..etc

3
 How to describe a Set?
Three popular methods

1. Word description
Set of even counting numbers less than 10
2. The listing method / Roster method
{2, 4, 6, 8}
3. Set-builder notation
{x | x is an even counting number less than 10}
4
 How to describe a Set?
1. Word description
• Make a word description of the set.

5
 How to describe a Set?
2. Roster Method
• Represented by listing its elements between braces {}
• Example :
• Sometime use ellipses (...) rather than listing all elements.
• The set of positive integers less than 100 can be denoted by
{1,2,3,...,99}.

6
 How to describe a Set?
3. Set-builder notation
• characterize all elements in the set by stating the property or properties they must have to
be members.
• the set O of all odd positive integers less than 10 can be written as
O = { x | x is an odd positive integer less than 10 }
O = { x ∈ Z+ | x is odd and x < 10 }

Example: B = {x | x is an even integer, x > 0}

• Read as- “B is the set of x such that x is an even integer and x is greater than 0”
• | is read as “such that” and comma as “and”.

7
 How to describe a Set?
3. Set-builder notation with interval
• the notation for intervals of real numbers. When a and b are real
numbers with a < b, we write
• [a, b] = {x | a ≤ x ≤ b}
• [a, b) = {x | a ≤ x < b}
• (a, b] = {x | a < x ≤ b}
• (a, b) = {x | a < x < b}

• Note that [a, b] is called the closed interval from a to b and (a, b) is
called the open interval from a to b.
8
 Set - properties

Order does not matter

– {1, 2, 3, 4, 5} is equivalent to {3, 5, 2, 4, 1}

Frequency does not matter

- Consider the list of students in this class
• It does not make sense to list somebody twice

9
 Set Terminology
Definition
U is the universal set – the set of all of elements (or the “universe”)
from which given any set is drawn
Empty (or null) set has zero elements,  = { }
The set A is a sub set of B if and only if every element of A is also an
element of B. A ⊆ B
When a set A is a subset of a set B but that A B, we write A ⊂ B and
say that A is a proper subset of B.

100
 Set Terminology
Definition
Set equality: two sets are equal if and only if they have the same
elements. We write A = B if A and B are equal sets.
Let S be a set. If there are exactly n distinct elements in S where n is a
nonnegative integer, we say that S is a finite set and that n is the
cardinality of S. The cardinality of S is denoted by |S|.
Given a set S, the power set of S is the set of all subsets of the set S.
The power set of S is denoted by P(S).

11
 Set Operation and Boolean Algebra
Operations
• Union () , similar to logical “OR” operator
• Intersection (), similar to logical “AND” operator
• Difference (-)
• Complement (“—”), similar to logical “NOT” operator
• Symmetric Difference () , similar to logical “XOR” operator
Operation into tow sets A and B give us new sets
• AB,
• AB,
• A-B,
• AB, and

122
 Set Operation : Union

Definition
Let A and B be sets. The union of the sets A and B, denoted by A ∪ B, is
the set that contains those elements that are either in A or in B, or in both.

A U B = { x | x A x B }

A = {1, 2, 5, 7}, B = {3, 4, 5, 6} AUB= { 1, 2, 3, 4, 5, 6, 7}

133
 Set Operation : Intersection

Definition
Let A and B be sets. The intersection of the sets A and B, denoted by
A∩B, is the set containing those elements in both A and B.

A B = { x | x A x B }

A = {1, 2, 5, 7}, B = {3, 4, 5, 6} AB= {5}

14
 Venn diagrams
• Represents sets graphically
– The box represents the universal set
– Circles represent the set(s)
• Consider set S, which is the set of all b c d f
U
vowels in the alphabet g h j S
• The individual elements are usually not k l m

written in a Venn diagram n p q a e i

r s t
o u
v w x
y z

15
Union and Intersection in VD

166
Difference and Symmetric Difference in VD

A-B is Shaded A + B is Shaded

FIGURE 3 Venn Diagram FIGURE 4 Venn Diagram

of the Difference of A and B. of the Symmetric Difference
of A and B.

17
 Disjoint Sets
Definition
Two sets are called disjoint if their intersection is the empty set.
i.e. A  B =  .

{a, b} and {3, 4} are disjoint U

A B

188
 Set identities

A = A AU = U
Identity Law Domination law
AU = A A = 
AA = A
Idempotent Law (Ac)c = A Complement Law
AA = A
AB = BA (AB)c = Ac  Bc
Commutative Law De Morgan’s Law
AB = BA (AB)c = Ac  Bc

A(BC) = (AB)C A(BC) = (AB)(AC)

Associative Law Distributive Law
A(BC) = (AB)C A(BC) = (AB)(AC)

A(AB) = A A  Ac = U
Absorption Law Complement Law
A(AB) = A A  Ac = 

19
 Set Identities via Venn
It’s often simpler to understand an identity by drawing a Venn Diagram.
For example DE Morgan's first law

A B  A B
can be visualized as follows.

20
 Visual DE Morgan

A: B:

221
 Visual DE Morgan

A: B:

A B :

22
 Visual DE Morgan

A: B:

L5
23
 Visual DE Morgan

A: B:

A: B:

24
 Visual DeMorgan

A: B:

A: B:

A B :
25
 Visual DE Morgan

A B 

=
A B 
26