COMP9020 Foundations of Computer Science
Foundations of Computer Science
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP9020
Foundations of Computer Science
Outline
Recap of Key Definitions
Set Equality
Laws of Set Operations
Derived Laws
Two Useful Results
Feedback
2
Defining Sets
1 Explicitly list elements
2 Take a subset of an existing set by restricting the elements
3 Build up from existing sets using Set Operations
3
Set Operations
Definition
A ∪ B – union (a or b):
A ∪ B = {x : x ∈ A or x ∈ B}.
A ∩ B – intersection (a and b):
A ∩ B = {x : x ∈ A and x ∈ B}.
Ac – complement (with respect to a universal set U):
Ac = {x : x ∈ U and x /∈ A}.
We say that A,B are disjoint if A ∩ B = ∅
4
Set Operations
Other set operations
Definition
A \ B – set difference, relative complement (a but not b):
A \ B = A ∩ Bc
A⊕B – symmetric difference (a and not b or b and not a; also
known as a or b exclusively; a xor b):
A⊕B = (A \ B) ∪ (B \ A)
5
Venn Diagrams
A Venn Diagram is a simple graphical approach to visualize the
basic set operations.
U
6
Venn Diagrams
A Venn Diagram is a simple graphical approach to visualize the
basic set operations.
U
A
6
Venn Diagrams
A Venn Diagram is a simple graphical approach to visualize the
basic set operations.
U
A B
6
Venn Diagrams
A Venn Diagram is a simple graphical approach to visualize the
basic set operations.
U
A B
A ∪ B
6
Venn Diagrams
A Venn Diagram is a simple graphical approach to visualize the
basic set operations.
U
A B
A ∩ B
6
Venn Diagrams
A Venn Diagram is a simple graphical approach to visualize the
basic set operations.
U
A
Ac
6
Venn Diagrams
A Venn Diagram is a simple graphical approach to visualize the
basic set operations.
U
A B
A \ B
6
Venn Diagrams
A Venn Diagram is a simple graphical approach to visualize the
basic set operations.
U
A B
A⊕B
6
Outline
Recap of Key Definitions
Set Equality
Laws of Set Operations
Derived Laws
Two Useful Results
Feedback
7
Set Equality
Two sets are equal (A = B) if they contain the same elements
To show equality:
Examine all the elements
Show A ⊆ B and B ⊆ A
Use the Laws of Set Operations
Important!
Venn diagrams can help visualize, but are not rigorous.
8
Example
Example
A \ (B \ C ) ?= (A \ B) \ C
A B
C
A \ (B \ C )
A B
C
(A \ B) \ C
9
Example
Example
A \ (B \ C ) ?= (A \ B) \ C
A B
C
A \
(B \ C )
A B
C
(A \ B) \ C
9
Example
Example
A \ (B \ C ) ?= (A \ B) \ C
A B
C
A
\
(B \ C )
A B
C
(A \ B) \ C
9
Example
Example
A \ (B \ C ) ?= (A \ B) \ C
A B
C
A \ (B \ C )
A B
C
(A \ B) \ C
9
Example
Example
A \ (B \ C ) ?= (A \ B) \ C
A B
C
A \ (B \ C )
A B
C
(A \ B)
\ C
9
Example
Example
A \ (B \ C ) ?= (A \ B) \ C
A B
C
A \ (B \ C )
A B
C
(A \ B)
\
C
9
Example
Example
A \ (B \ C ) ?= (A \ B) \ C
A B
C
A \ (B \ C )
A B
C
(A \ B) \ C
9
Example
Example
A \ (B \ C ) ̸= (A \ B) \ C
A B
C
A \ (B \ C )
A B
C
(A \ B) \ C
9
Example
Example
A \ (B \ C ) ̸= (A \ B) \ C
A B
C
A \ (B \ C )
A B
C
(A \ B) \ C
9
Examples
Example
Show {3, 2, 1} = (0, 4).
(0, 4) = {1, 2, 3} = {3, 2, 1}.
10
Examples
Example
Show {3, 2, 1} = (0, 4).
(0, 4) = {1, 2, 3} = {3, 2, 1}.
10
Examples
Example
Show {n : n ∈ Z and n2 < 5} = {n : n ∈ Z and |n| ≤ 2}
{n : n ∈ Z and n2 < 5} = {−2,−1, 0, 1, 2}
= {n : n ∈ Z and |n| ≤ 2}
11
Examples
Example
Show {n : n ∈ Z and n2 < 5} = {n : n ∈ Z and |n| ≤ 2}
{n : n ∈ Z and n2 < 5} = {−2,−1, 0, 1, 2}
= {n : n ∈ Z and |n| ≤ 2}
11
Examples
Example
Show {n : n ∈ Z and n2 > 5} = {n : n ∈ Z and |n| > 2}
Show:
For all n ∈ Z, if n2 > 5 then |n| > 2; and
For all n ∈ Z, if |n| > 2 then n2 > 5.
That is, show:
For all n ∈ Z: n2 > 5 if, and only if |n| > 2
12
Examples
Example
Show {n : n ∈ Z and n2 > 5} = {n : n ∈ Z and |n| > 2}
Show:
For all n ∈ Z, if n2 > 5 then |n| > 2; and
For all n ∈ Z, if |n| > 2 then n2 > 5.
That is, show:
For all n ∈ Z: n2 > 5 if, and only if |n| > 2
12
Outline
Recap of Key Definitions
Set Equality
Laws of Set Operations
Derived Laws
Two Useful Results
Feedback
13
Laws of Set Operations
For all sets A, B, C :
Commutativity A ∪ B = B ∪ A
A ∩ B = B ∩ A
Associativity (A ∪ B) ∪ C = A ∪ (B ∪ C )
(A ∩ B) ∩ C = A ∩ (B ∩ C )
Distribution A ∪ (B ∩ C ) = (A ∪ B) ∩ (A ∪ C )
A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C )
Identity A ∪ ∅ = A
A ∩ U = A
Complementation A ∪ (Ac) = U
A ∩ (Ac) = ∅
14
Substitution
Because the laws hold for all sets, we can substitute complex
expressions for each set symbol.
Example
Commutativity A ∪ B = B ∪ A
Therefore: (C ∩ D) ∪ (D ⊕ E ) = (D ⊕ E ) ∪ (C ∩ D)
15
Substitution
Because the laws hold for all sets, we can substitute complex
expressions for each set symbol.
Example
Commutativity A ∪ B = B ∪ A
Therefore: (C ∩ D) ∪ (D ⊕ E ) = (D ⊕ E ) ∪ (C ∩ D)
15
Example
Example
Show that for all sets A ∩ (B ∩ C ) = C ∩ (B ∩ A):
A ∩ (B ∩ C ) = (A ∩ B) ∩ C [Associativity]
= C ∩ (A ∩ B) [Commutativity]
= C ∩ (B ∩ A) [Commutativity]
Important!
(Aim to) limit each step to a non-overlapping applications of a
single rule
16
Example
Example
Show that for all sets A ∩ (B ∩ C ) = C ∩ (B ∩ A):
A ∩ (B ∩ C ) = (A ∩ B) ∩ C [Associativity]
= C ∩ (A ∩ B) [Commutativity]
= C ∩ (B ∩ A) [Commutativity]
Important!
(Aim to) limit each step to a non-overlapping applications of a
single rule
16
Outline
Recap of Key Definitions
Set Equality
Laws of Set Operations
Derived Laws
Two Useful Results
Feedback
17
Other useful set laws
The following are all derivable from the previous 10 laws.
Idempotence A ∩ A = A
A ∪ A = A
Double complementation (Ac)c = A
Annihilation A ∩ ∅ = ∅
A ∪ U = U
de Morgan’s Laws (A ∩ B)c = Ac ∪ Bc
(A ∪ B)c = Ac ∩ Bc
18
Example (Idempotence of ∪)
A = A ∪ ∅ (Identity)
= A ∪ (A ∩ Ac) (Complementation)
= (A ∪ A) ∩ (A ∪ Ac) (Distributivity)
= (A ∪ A) ∩ U (Complementation)
= (A ∪ A) (Identity)
19
Example (Idempotence of ∪)
A = A ∪ ∅ (Identity)
= A ∪ (A ∩ Ac) (Complementation)
= (A ∪ A) ∩ (A ∪ Ac) (Distributivity)
= (A ∪ A) ∩ U (Complementation)
= (A ∪ A) (Identity)