Before we get into the details of Theory of Computations. The set is an essential topic which is required to be reviewed. So, let's have a quick review of this topic.
- Set is a group of elements, having a common characteristic or property.
- Example: A = {1,2,3,4,5}
- Another way to specify a set is to give the properties that characterize elements of the sets.
- Example: A = {x | x is a positive integer less than or equal to 5}
- Using this notation we can specify the set {0,1,2,3,4} call it Z by writing
Z = {x | x ∈ N | x <= 5}
Where N = set of natural numbers.
- It is represented by A⊆ B.
- If A is a subset of B and B is a subset of A, then A = B. Also if a is a subset of B but is not equal to B then it is represented as A⊂ B.
A' = {x | x∈ U \land \!\, x ∉ A}
- It is denoted by A'.
- Example:
If U is a set of natural numbers and A = {1,2,3}, then
A' = {x | x∈ U \land \!\, x > 3}
Different operations can be performed on sets;
- Union is denoted by A∪B.
- Example:
If A = {1,2} and B = {3, 4, 5} then A∪B = {1, 2, 3, 4, 5}.
- The difference is denoted by A-B.
- Example:
If A= {1, 2, 3} and B = {3, 4, 5} then A-B = {1,2} also B-A = {4,5}.
- It can be seen that A-B ≠ B-A.
- The intersection is denoted by A∩B.
- Example:
If A= {1, 2, 3} and B = {3, 4, 5} then A∩B = {3}.
- A and B sets are said to be disjoint if they contain no common element, i.e. A∩B = ∅, where ∅ is an empty set.
- Example:
Let A= {1, 2, 3} and B = {4,5,6,7} then A and B are disjoint sets as A∩B = ∅.
Let A, B, C represent arbitrary sets and ∅ be the empty set and U be the Universal set, then
- A∩B = B∩A
- A∩(B∩C) = (A∩B)∩C
- A∪(B∩C) = (A∪B)∩(A∪C)
- A∩A = A
- A∩(A∪B) = A
- (A ∩ B)' = A' U B'
- A ∩ A' = ∅
- A ∪ A' = U
- A ∩ ∅ = ∅
- A ∩ U = A
What is a Set?
- Set is a group of elements, having a common characteristic or property.
- Example: A = {1,2,3,4,5}
- Another way to specify a set is to give the properties that characterize elements of the sets.
- Example: A = {x | x is a positive integer less than or equal to 5}
Set Terminology
1. Belongs To (∈)
- x ∈ A means that x is an element of A.- Using this notation we can specify the set {0,1,2,3,4} call it Z by writing
Z = {x | x ∈ N | x <= 5}
Where N = set of natural numbers.
2. Subset
- Let A and B be two sets. Then A is a subset of B if every element of A is an element of B.- It is represented by A⊆ B.
- If A is a subset of B and B is a subset of A, then A = B. Also if a is a subset of B but is not equal to B then it is represented as A⊂ B.
3. Universal Set
- The set U of all the elements we might ever consider in the discourse is called the universal set.4. Complement
- Let A be a set, then the complement of A is the set consisting of all elements of the universal set that are not in A.A' = {x | x∈ U \land \!\, x ∉ A}
- It is denoted by A'.
- Example:
If U is a set of natural numbers and A = {1,2,3}, then
A' = {x | x∈ U \land \!\, x > 3}
Set Operations
Different operations can be performed on sets;
1. Union:
- If A and B are two sets, then the union of A and B is the set that contains all the elements that are in A and B including the ones in both A and B.- Union is denoted by A∪B.
- Example:
If A = {1,2} and B = {3, 4, 5} then A∪B = {1, 2, 3, 4, 5}.
2. Difference
- If A and B are two sets, then the difference of A from B is the set that contains all the elements that are in A but not in B.- The difference is denoted by A-B.
- Example:
If A= {1, 2, 3} and B = {3, 4, 5} then A-B = {1,2} also B-A = {4,5}.
- It can be seen that A-B ≠ B-A.
3. Intersection
- If A and B are two sets, then the intersection of A and B is the set that contains all the elements that are in both A and B.- The intersection is denoted by A∩B.
- Example:
If A= {1, 2, 3} and B = {3, 4, 5} then A∩B = {3}.
Disjoint Sets
- A and B sets are said to be disjoint if they contain no common element, i.e. A∩B = ∅, where ∅ is an empty set.
- Example:
Let A= {1, 2, 3} and B = {4,5,6,7} then A and B are disjoint sets as A∩B = ∅.
Some Standard Identities of Sets
Let A, B, C represent arbitrary sets and ∅ be the empty set and U be the Universal set, then
1. Commutative Laws:
- A∪B = B∪A- A∩B = B∩A
2. Associative Laws:
- A∪(B∪C) = (A∪B)∪C- A∩(B∩C) = (A∩B)∩C
3. Distributive Laws:
- A∩(B∪C) = (A∩B)∪(A∩C)- A∪(B∩C) = (A∪B)∩(A∪C)
4. Idempotent Laws:
- A∪A = A- A∩A = A
5. Absorption Laws:
- A∪(A∩B) = A- A∩(A∪B) = A
6. De Morgan Laws:
- (A∪B)' = A' ∩ B'- (A ∩ B)' = A' U B'
7. Laws involving Complements:
- (A')' = A- A ∩ A' = ∅
- A ∪ A' = U
8. Laws involving empty set:
- A ∪ ∅ = Λ- A ∩ ∅ = ∅
9. Laws involving Universal set:
- A ∪ U = U- A ∩ U = A
