cont...chapter 2

1) COMPUTER REPRESENTATION OF SETS

>  Using method is to store elements of the sets in the unordered fashion. 

>  However, if this is done, the operations of computing, union, intersection, or difference of two sets would    

    be time consuming which each operations will required a large amount of searching of elements.

>  We will present a method for storing elements using orbitrary ordering of the elements of the universal   

    sets which make it more easier.

>  Assume that the universal set U is finite(size that less than the memory of our computer).

>  First,specify an arbitrary ordering of the elements of U,for instance a1,a2,...,an.

>  Subset A of U represent with the bit string of length n, where the ith bit in this string is 1
     if ai is belong to A and is 0 if ai d'nt belong to A.

>  Look for the example below to be more clear :

    

example 1 :

   how to present sets using computer...

      

    Let U = {1,2,3,4,5,6,7,8,9,10} and the ordering elements of U has the elements in increasing order,

    i.e.,ai = i.What bit string represent the subset of all odd integers in U, the subset of all even integers in U,

    and the subset of integers not exceed than 5 in U?

solution :

    The bit string that represent the set of odd integers in U, namely, {1,3,5,7,9}, has 1 bit in the 1st,3rd,5th,

    7th ad 9th positions and a zero elsewhere,It is...

                       10 1010 1010 

    same with how to represent the subsets of all even integers in U,namely, {2,4,6,8,10},by the string

                       01 0101 0101 

example 2:

    find complements of sets...

    To find the bit string for the complement of a set from the bit string for that sets , we simply change each      

    1 to 0 and 0 to 1, since x ∈ A if and only if x 

    We have seen that the bit string for the bit 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 is obtained by replace 0s with 1s and vice versa.
     This yields the string 

      01 0101 0101

    which correspond to the set {2,4,6,8,10}.

example 3: 
     find union and intersection...

         the bit string for the sets {1,2,3,4,5} and {6,7,8,9,10} are 11 1110 0000 and
         10 1010 1010,respectively.Use bit strings to find the union and intersection of these sets.

solution:

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

          which correspond to the set {1,2,3,4,5,7,9}.
         The bit string for the intersection of these sets is
                11 1110 0000 ^ 10 1010 1010 = 10 1010 0000,

          which correspond to the set {1,3,5}.

2) RELATION

            Relation:  A relation is simply a set of ordered pairs.

The first elements in the ordered pairs (the x-values) form the domain.
The second elements in the ordered pairs (the y-values), form the range.
Only the elements "used" by the relation constitute the range

This mapping shows a relation from set A into set B.

This relation consists of the ordered pairs

(1,2), (3,2), (5,7), and (9,8).

 The domain is the set {1, 3, 5, 9}.

 The range is the set {2, 7, 8}.(Notice that 3, 5 and 6 are not part of the range.)

 The range is the dependent variable.

Reflexive relation R on A, if ∀a ∈ A, (a, a) ∈ R.

Symmetric relation R on A, if ∀a∀b ∈ A, (a, b) ∈ R → (b, a) ∈ R.

Antisymmetric relation R on A, if ∀a∀b ∈ A, (a, b) ∈ R ^ (b, a) ∈ R →  a=b.

Transitive relation R on A, if ∀a∀b∀c ∈ A, (a, b) ∈ R ^ (b, c) ∈ R → (a, c) ∈ R.

Relations on the set A = {1, 2, 3}

reflexive symmetric antisymmetric transitive R0 = {(1,1), (2,2), (3,3)} Yes Yes Yes Yes R1 = {(2,2), (2,3), (3,2)} No Yes No (2,3) (3,2) No (3,3) R2 = {(1,1), (1,2), (2,1), (2,2), (3,3)} Yes Yes No (1,2) (2,1) Yes R3 = {(2,3), (3,2)} No Yes No (2,3) (3,2) No (2,2) (3,3) R4 = {(1,2), (2,3), (1,3)} No No Yes Yes

3)function

Concept of function on general sets

o   Let A and B be sets. A function f from A to B is an assignment of exactly one element of B to each element of A.

o   We write f(a) = b if b is the unique element of B assigned by the function f to the element of A.

o   If f is a function from A to B, we write

                       f : A --> B

o   If f : A --> B, we say that A is the domain of f and B is the co domain of f.

o   If f(a) = b, we say that b is the image of a.

o   The range of f is the set of all images of elements of A.

Boolean Function

An expression that  is formed with binary variables. The binary operators are OR and AND .The unary operator NOT, parentheses and equal sign.  The Boolean function can be represented as an algebraic expression or in truth table.

Example: Display value of Q :

Q = A AND NOT B

Example:

Simplify the following Boolean function to minimum number of variables (literals).

F(X,Y) = X + X’Y

X + X’Y = (X+X’)(X+Y)

=1. (X+Y)

=X+Y

Injective, Surjective and Bijective

Injective is every A has its own unique matching in B.
There is no two A’s pointing to the same B.
In injective we can have a B without a matching A.

Injective is also called "One-to-One"

Surjective means that every B has at least one matching A .
There won't be a B left out.

Bijective means both Injective and Surjective together.
So there is a perfect "one-to-one correspondence" between the members of the sets.
(But don't get that confused with the term "One-to-One" used to mean injective).

Inverse function
Is a function that undoes the action of another function.
Example:

f(x) = 5x + 1. Find the inverse function f  ¯¹ (x).
Let y = 5x + 1 and solve for x.

 y = 5x + 1
y – 1 = 5x
 (y-1) / 5 = x

So we can write f  ¯¹ (x) =x/5-1/5


Composition function

The process of combining two functions. One function is performed first and the result of which is substituted in place of each x in the other function.

Example:

f(x) = x – 4 and g(x) = 5 – x²
Find f ◦ g
Solution:
(f ◦ g) = f [g(x)]
           = f (5 – x²)
           = (5 – x²) – 4
           = 1 – x²