Scribd
Upload
95 views19 pages

Set Operations & Algebra Guide

The document discusses set operations and properties including: 1. The complement of a set A (Ac) contains elements that are in the universal set but not in A. 2. The union of sets A and B (A ∪ B) contains elements that are in A, B, or both. 3. The intersection of sets A and B (A ∩ B) contains elements that are only in both A and B. 4. De Morgan's laws state that the complement of a union is the intersection of complements and the complement of an intersection is the union of complements.

Uploaded by

Roshan Rajith
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
95 views19 pages

Set Operations & Algebra Guide

The document discusses set operations and properties including: 1. The complement of a set A (Ac) contains elements that are in the universal set but not in A. 2. The union of sets A and B (A ∪ B) contains elements that are in A, B, or both. 3. The intersection of sets A and B (A ∩ B) contains elements that are only in both A and B. 4. De Morgan's laws state that the complement of a union is the intersection of complements and the complement of an intersection is the union of complements.

Uploaded by

Roshan Rajith
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 19

Mathematics for Computing - I

Sets (07 hrs.)

Set Operations - Complement


The (absolute) complement of a set A is the set of elements which belong to the universal set but which do not belong to A. This is denoted by Ac or or . In other words we can say: Ac = {x : xU xA}

Venn Diagram for the Complement


A Ac

Set Operations - nion


Union of two sets A and B is the set of all elements which belong to either A or B or both. This is denoted by A B. In other words we can say: A B = {x : xA xB} E.g. A = {3, 5, 7}, B = {2, 3, 5} A B = {3, 5, 7, 2, 3, 5} = {2, 3, 5, 7}
4

Venn Diagram Representation for Union


AB A

35

Set Operations - Itersection


Intersection of two sets A and B is the set of all elements which belong to both A and B. This is denoted by A B. In other words we can say: A B = {x : xA xB} E.g. A = {3, 5, 7}, B = {2, 3, 5} A B = {3, 5}
6

Venn Diagram Representation for Intersection


AB A

35

Set Operations - Difference


The difference or the relative complement of a set B with respect to a set A is the set of elements which belong to A but which do not belong to B. This is denoted by A B. In other words we can say: A B = {x : xA xB} E.g. A = {3, 5, 7}, B = {2, 3, 5} A B = {3, 5, 7} {2, 3, 5} = {7}
8

Venn Diagram Representation for Difference


A B A

35

Some Properties
A AB and B AB AB A and AB B |AB| = |A| + |B| - |AB| AB BcAc A B = ABc If AB = then we say A and B are disjoint.
10

Algebra of Sets
Idempotent laws
AA=A AA=A

Associative laws
(A B) C = A (B C) (A B) C = A (B C)

11

Algebra of Sets ctd


Commutative laws
AB=BA AB=BA

Distributive laws
A (B C) = (A B) (A C) A (B C) = (A B) (A C)

12

Algebra of Sets ctd


Identity laws
A=A AU=A AU=U A=

Involution laws
(Ac)c = A
13

Algebra of Sets ctd


Complement laws
A Ac = U A Ac = Uc = c = U

14

Algebra of Sets ctd


De Morgans laws
(A B)c = Ac Bc (A B)c = Ac Bc

Note: Compare these De Morgans laws with the De Morgans laws that you find in logic and see the similarity.

15

Proofs
Basically there are two approaches in proving above mentioned laws and any other set relationship
Algebraic method Using Venn diagrams

For example lets discuss how to prove


(A B)c = Ac Bc
16

Proofs Using Venn Diagrams


AB A 4 1 2 3 B

Note that these indicated numbers are not the actual members of each set. They are region numbers.

17

Proofs Using Venn Diagrams ctd


U : 1, 2, 3, 4 A : 1, 2 (i.e. The region for A is 1 and 2) B : 2, 3 AB : 1, 2, 3 () (AB)c : 4

18

Proofs Using Venn Diagrams ctd


Ac : 3, 4 Bc : 1, 4 AcBc : 4 () () (AB)c = AcBc

()

19

You might also like