Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Law of Algebra of sets
2.1.
Commutative laws
2.2.
Distributive Laws
2.3.
Idempotent Laws
2.4.
Associative Laws
2.5.
De Morgan's Law
2.6.
Identity Law
2.7.
Complement Law
2.7.1.
More laws of the algebra of sets:
3.
The Principle of Duality
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024
Easy

Algebra of Sets

Author Soumya Agrawal
2 upvotes
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

The algebra of sets is for developing the fundamental properties of set operations.

The algebra of sets is the analog of the algebra of numbers. The algebra of union, intersection and complement operations satisfies various laws (identities), which we will see further in this article.

For the basic introduction of sets, see The Theory of set.

Law of Algebra of sets

Here we will see different laws of the algebra of sets under the various set operations.

Commutative laws

Commutative means that if the operands' order is changed, it doesn't make any difference in the result. 

For any of the two finite sets, A and B,

  • A U B = B U A
  • A ∩ B = B ∩ A

Let’s prove the above identities to get a clear picture of the law.

To Prove: A ∪ B = B ∪ A

 

  A ∪ B = B ∪ A
      A ∪ B = {x: x ∈ A or x ∈ B}
            = {x: x ∈ B or x ∈ A} 
      A ∪ B = B ∪ A
Hence Proved.

 

To Prove: A ∩ B = B ∩ A     

  A ∩ B = B ∩ A
      A ∩ B = {x: x ∈ A and x ∈ B}
            = {x: x ∈ B and x ∈ A}   
      A ∩ B = B ∩ A
 Hence Proved.

 

Distributive Laws

The distributive law asserts that equality is always true in algebra.

  • A ∪ (B ∩ C ) = (A ∪ B ) ∩ (A ∪ C )
  • A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C )

To Prove: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

Let x ∈ A ∪ (B ∩ C) ⇒ x ∈ A or x ∈ B ∩ C 
      ⇒ (x ∈ A or x ∈ A) or (x ∈ B and x ∈ C)
      ⇒ (x ∈ A or x ∈ B) and (x ∈ A or x ∈ C)
      ⇒ x ∈ A ∪ B and x ∈ A ∪ C
      ⇒ x ∈ (A ∪ B) ∩ (A ∪ C)
  
Therefore-> A ∪ (B ∩ C) ⊂ (A ∪ B) ∩ (A ∪ C)............(i)
Again, Let y ∈ (A ∪ B) ∩ (A ∪ C) ⇒ y ∈ A ∪ B and y ∈ A ∪ C
      ⇒ (y ∈ A or y ∈ B) and (y ∈ A or y ∈ C)
      ⇒ (y ∈ A and y ∈ A) or (y ∈ B and y ∈ C)
      ⇒ y ∈ A or y ∈ B ∩ C
      ⇒ y ∈ A ∪ (B ∩ C)
Therefore, (A ∪ B) ∩ (A ∪ C) ⊂ A ∪ (B ∩ C)............(ii)

Combining (i) and (ii), we get A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
Hence Proved.

 

To Prove: A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C )   

Let x ∈ A ∩ (B ∪ C) ⇒ x ∈ A and x ∈ B ∪ C
⇒ (x ∈ A and x ∈ A) and (x ∈ B or x ∈ C)
         ⇒ (x ∈ A and x ∈ B) or (x ∈ A and x ∈ C)
         ⇒ x ∈ A ∩ B or x ∈ A ∩ C
         ⇒ x ∈ (A ∩ B) ∪ (A ∪ C)
 
Therefore-> A ∩ (B ∪ C) ⊂ (A ∩ B) ∪ (A ∪ C).... (1)
Again, Let y ∈ (A ∩ B) ∪ (A ∪ C) ⇒ y ∈ A ∩ B or y ∈ A ∩ C
⇒ (y ∈ A and y ∈ B) or (y ∈ A and y ∈ C)
⇒ (y ∈ A or y ∈ A) and (y ∈ B or y ∈ C)
⇒ y ∈ A and y ∈ B ∪ C
           ⇒ y ∈ A ∩ (B ∪ C)
Therefore, (A ∩ B) ∪ (A ∪ C) ⊂ A ∩ (B ∪ C).... (2)

Combining (1) and (2), we get A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∪ C)
Hence Proved.

 

Idempotent Laws

To prove: A ∪ A = A 

As, B ⊂ A ∪ B, therefore A ⊂ A ∪ A
Let x ∈ A ∪ A ⇒ x ∈ A or x ∈ A ⇒ x ∈ A
∴ A ∪ A ⊂ A
As A ∪ A ⊂ A and A ⊂ A ∪ A ⇒ A =A ∪ A
Hence Proved.

To prove: A ∩ A = A

As, A ∩ B ⊂ B, therefore A ∩ A ⊂ A
Let x ∈ A ⇒ x ∈ A and x ∈ A  
⇒ x ∈ A ∩ A ∴ A ⊂ A ∩ A
As A ∩ A ⊂ A and A ⊂ A ∩ A ⇒ A = A ∩ A
Hence Proved.

 

Associative Laws

Associativity is a valid rule for replacing the expressions in logical proofs. For any of the three finite sets A, B, and C;

(i) (A U B) U C = A U (B U C)

(ii) (A ∩ B) ∩ C = A ∩ (B ∩ C)

Thus, union and intersection are associative.

To prove : (A U B) U C = A U (B U C)

Let some x ∈ (A'∪ B) ∪ C
   ⇒ (x ∈ A or x ∈ B) or x ∈ C
   ⇒ x ∈ A or x ∈ B or x ∈ C
  ⇒ x ∈ A or (x ∈ B or x ∈ C)
  ⇒ x ∈ A or x ∈ B ∪ C 
  ⇒ x ∈ A ∪ (B ∪ C).
Similarly, if some x ∈ A ∪ (B ∪ C), then x ∈ (A ∪ B) ∪ C.
Thus, any x ∈ A ∪ (B ∪ C) ⇔ x ∈ (A ∪ B) ∪ C
 Hence Proved.

To prove : (A ∩ B) ∩ C = A ∩ (B ∩ C)

Let some x ∈ A ∩ (B ∩ C) ⇒ x ∈ A and x ∈ B ∩ C 
   ⇒ x ∈ A and (x ∈ B and x ∈ C) ⇒ x ∈ A and x ∈ B and x ∈ C
  ⇒ (x ∈ A and x ∈ B) and x ∈ C) ⇒ x ∈ A ∩ B and x ∈ C
  ⇒ x ∈ (A ∩ B) ∩ C.
Similarly if some x ∈ A ∩ (B ∩ C), then x ∈ (A ∩ B) ∩ C
Thus, any x ∈ (A ∩ B) ∩ C ⇔ x ∈ A ∩ (B ∩ C)
 Hence Proved.

 

De Morgan's Law

De Morgan's Law in mathematics consists of a pair of transformation rules in boolean algebra that relates the intersection and union of sets through complements.

For any of the two finite sets A and B;

(i) A – (B U C) = (A – B) ∩ (A – C)

(ii) A - (B ∩ C) = (A – B) U (A – C)

De Morgan's Laws can also be written or modified as:

(i) (A U B)’ = A' ∩ B'

(ii) (A ∩ B)’ = A' U B'

To prove : (A U B)' = A' ∩ B'

 

Let x ∈ (A ∪B)c ⇒ x ∉ A ∪ B (∵ a ∈ A ⇔ a ∉ Ac)
           ⇒ x ∉ A and x ∉ B
           ⇒ x ∉ Ac and x ∉ Bc
           ⇒ x ∉ Ac∩ Bc
Therefore, (A ∪B)c ⊂ Ac∩ Bc............. (i)
Again, let x ∈ Ac∩ Bc ⇒ x ∈ Ac and x ∈ Bc
            ⇒ x ∉ A and x ∉ B
            ⇒ x ∉ A ∪ B
            ⇒ x ∈ (A ∪B)c
Therefore, Ac∩ Bc ⊂ (A ∪B)c............. (ii)
Combining (i) and (ii), we get Ac∩ Bc =(A ∪B)c
Hence Proved.

 

To prove : (A ∩ B)' = A' U B'

Let x ∈ (A ∩B)c ⇒ x ∉ A ∩ B (∵ a ∈ A ⇔ a ∉ Ac)
           ⇒ x ∉ A or x ∉ B
           ⇒ x ∈ Ac and x ∈ Bc
           ⇒ x ∈ Ac∪ Bc
∴ (A ∩B)c⊂ (A ∪B)c... (i)
Again, Let x ∈ Ac∪ Bc ⇒ x ∈ Ac or x ∈ Bc
            ⇒ x ∉ A or x ∉ B
            ⇒ x ∉ A ∩ B
            ⇒ x ∈ (A ∩B)c
∴ Ac∪ Bc⊂ (A ∩B)c... (ii)
Combining (i) and (ii), we get(A ∩B)c=Ac∪ Bc
Hence Proved.

 

Identity Law

For any subset A of universal set U, the following identities hold:

  • A ∪ ∅ = A
  • A ∩ U = A

Complement Law

For any subset A of universal set U, the following identities hold:

  • A ∪ A′ = U
  • A ∩ A′ = ∅

More laws of the algebra of sets:

For any of the two finite sets A and B;

(i) A – B = A ∩ B'

(ii) B – A = B ∩ A'

(iii) A – B = A ⇔ A ∩ B = ∅

(iv) (A – B) U B = A U B

(v) (A – B) ∩ B = ∅

(vi) A ⊆ B ⇔ B' ⊆ A'

(vii) (A – B) U (B – A) = (A U B) – (A ∩ B)

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

The Principle of Duality

The dual E∗ of E is the equation obtained by replacing every occurrence of ∪, ∩, U and ∅ in E by ∩, ∪, ∅, and U, respectively. For example, the dual of

 (U ∩ A) ∪ (B ∩ A) = A is (∅ ∪ A) ∩ (B ∪ A) = A  

It is noted as the principle of duality that if any equation E is an identity, then its dual E∗ is also an identity.

FAQs

 

1. List the various laws of the algebra of sets.

  • Commutative Law
  • Distributive Law
  • Associative Law
  • Idempotent Law
  • De Morgan’s Law
  • Identity Law
  • Complement Law

 

2. State De Morgan’s Law.

De Morgan's Law in mathematics consists of a pair of transformation rules in boolean algebra that is used to relate the intersection and union of sets through complements.

For any two finite sets A and B;

(i) A – (B U C) = (A – B) ∩ (A – C)

(ii) A - (B ∩ C) = (A – B) U (A – C)

 

3. What do you mean by Principal of Extension?

According to the Principle of Extension two sets, A and B are the same if and only if they have the same members. We denote equal sets by A=B.

 

Key Takeaways

In this blog, we have extensively covered the use of the laws of algebra for the set operations. We saw the proof of the various identities of the laws. 

For understanding this article clearly you must go through this article to understand the set operations.

Check out this link if you want to explore more about sets.

If you are preparing for the upcoming Campus Placements, don't worry. Coding Ninjas has your back. Visit this data structure link for cracking the best product companies.

Happy Learning!!!

Previous article
Multisets
Next article
Inclusion-Exclusion Principle
Live masterclass