Computer Representation of Sets

Computer Representation of Sets

    Method for storing elements using an arbitrary ordering of the elements of the universal
    set.Specify an arbitrary ordering of the elements of U, for instance a1, a2, . . . , an. Represent a 
    subset A of U with the bit string of length n, where the ith bit in this string is 1 if ai belongs to A
    and is 0 if ai does not belong to A.

Example1: Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.

i)What bit strings represent the subset of all odd integers in U?

  The bit string that represents the set of odd integers in U, {1, 3, 5, 7, 9}, has a one bit in the

  first, third, fifth, seventh, and ninth positions. It is 10 1010 1010.

ii)What bit strings represent the subset of all even integers in U?

   The bit string that  represent the subset of  even integers in U,{2, 4, 6, 8, 10}.

   It is 01 0101 0101.

iii)What bit strings represent the subset of integers not exceeding 5 in U? 

    The set of all integers in U that do not exceed 5, {1, 2, 3, 4, 5}, is represented by the

    string 11 1110 0000.

To find the bit string for the complement of a set from the bit string for that set, change each 1 to 0 and each 0 to 1.

Example 2:The bit string for the set {1, 3, 5, 7, 9} (with universal set {1, 2, 3, 4,

5, 6, 7, 8, 9, 10}) is 10 1010 1010.

What is the bit string for the complement of this set?

The bit string for the complement of this set is obtained by replacing 0s with 1s.

This yields the string 01 0101 0101,which corresponds to the set {2, 4, 6, 8, 10}.

To obtain the bit string for the union and intersection of two sets we perform bitwise Boolean

operations on the bit strings representing the two sets.

Example 3:The bit strings for the sets {1, 2, 3, 4, 5} and {1, 3, 5, 7, 9} are 11 1110 0000 and 10 1010 1010.

The bit string for the union of these sets is 11 1110 0000 ∨ 10 1010 1010 = 11 1110 1010,

which corresponds to the set {1, 2, 3, 4, 5, 7, 9}.

If either of the bits in the ith position in the two strings is 1 (or both are 1),the bit in the ith position of the bit string of the union is 1. When both bits are 0, is 0. Hence, the bit string for union is the bitwise OR of the bit strings for the two sets.

The bit string for the intersection of these sets is

11 1110 0000 ∧ 10 1010 1010 = 10 1010 0000, which corresponds to the set {1, 3, 5}.

When the bits in the corresponding position in the two strings are both 1,the bit in the ith position of the bit string of the intersection is 1. When either of the two bits is 0 (or both are 0) ,is 0. Hence, the bit string for the intersection is the bitwise AND of the bit strings for the two sets.

Properties of Relations

• Reflexive
• Irreflexive
• Symmetric
• Antisymmetric
• Transitive

[1] Reflexive

     A reflexive relation is a binary relation on a set for which every element is related to itself.

Example

A={1,2,3}

R={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}

R is reflexive because they contains all pairs of the form (a,a), namely (1,1),(2,2)&(3,3)

       

[2] Irreflexive

     A irreflexive relation is a binary relation on a set for which is false for every element.

" a Î A,(a,a) Ï R

Example

These 4 irreflexive relations are :

1. Empty
2. {(1,2)}
3. {(2,1)}
4. {(1,2),(2,1)}

[3] Symmetric

     A symmetric relation is a binary relation on a set  A if  (a,b) Î R = (b,a) Î R  

R={(1,1),(1,2),(2,1),(2,2)}

R is symmetric because both (1,2) and (2,1) are in the relation.

[4] Antisymmetric

     A binary relation a on a set A is antisymmetric whenever (a, b) Î R and (b, a) Î R , then a=b

Example

R={(2, 1), (3, 1), (4, 1), (3, 2), (4, 2), (4, 3)}

R is antisymmetric because there is no pair of element a and b.

a ≠ b (a,b) & (b,a).

[5] Transitive

A binary relation a on a set A is transitive (a,b) Î R and (b,c) Î R = (a,c) Î R     

Example

A={1,2,3,4}

answer:

R={(1,1),(1,2),(2,2),(2,3),(1,3),(3,3)}