Chap 2: Set Theory (Part 4)

COMPUTER REPRESENTATION OF SETS:
 There are many ways to represent sets using a computer.
 One of the method is to store elements using an arbitrary ordering of elements of the universal set.
◦ Ordered set (less time-consuming)
◦ Unordered set (time consuming)
 An arbitrary ordering of the elements of U (universal set), for instance, a1, a2, …, an, then representing a subset of A of U with bit string of length n, where the ith bit in this string is 1 if a1 belongs to A and is 0 if a does not belong to A.

EXAMPLE:
Let U={0,1,2,3,4,5,6} represent set with bit strings (binary form)
a) A= {2,4,5,6}
      bit string is 0010111
 b) B is the set of all odd integer, BÍ U.
      B= {1,3,5} the bit string is 0101010
 c) C is a subset of U, containing all integers greater than 4.
      C={5,6} the bit string is 0000011




COMPLEMENT, UNION, INTERSECTION AND DIFFERENCES OF SETS

 Using bit strings to represent sets, it is easy to find complement of sets, unions, intersection and differences of sets.

EXAMPLE:
Let U= {0,1,2,3,4,5,6,7} , A= {1,3,5,6,7} , B= {1,2,3,4,5}. Use bit strings to find
a) ¬A (complement of A)
   A : 01010111
  ¬A : 10101000
Therefore ¬A  is {0,2,4}

b) A ʌ B (Intersection @ bitwise AND)
    A : 01010111
    B : 01111100
 A ʌ B : 01010100
 Therefore A ʌ B={1,3,5}

c) A ᴠ B  (Union @ bitwise OR)
    A : 01010111
    B : 01111100
A ᴠ B : 01111111
Therefore A ᴠ B={1,2,3,4,5,6,7}

p/s: you can download the note at this link --> Chap 2: Set Theory (Part 4)