Monday, 11 March 2013

Task 3 : Set Theory



1. COMPUTER REPRESENTATION of SETS



i) Let A = {1,2,3,5} (from universal set {1,2,3,4,5})


how to represent : 11101
1  2  3  4  5 
                                                            1  1  1  0  1  <---- if the number exist we represent the value      
                                                                                                 by 1, else 0
:- thus, the representation of {1,2,3,5} in computer is 11101 !

ii) Union = OR

   11100 V 10110 = 11110

iii) Intersection

     100111 ʌ 10111 = 100111


iv) Complement

     10101 ---> 01010



2. RELATION


If we want to describe a relationship between elements of two sets A and B, we can use ordered pairs with their first element taken from A and  their second element taken from B.
Since this is a relation between two sets, it is called a binary relation.

Definition:

Let A and B be sets. A binary relation from A to B is a subset of A´B.
In other words, for a binary relation R we have  R Í A´B.
We use the notation aRb to denote that (a, b)ÎR and aRb to denote that (a, b)ÏR.
When (a, b) belongs to R, a is said to be related to b by R.

Example: 

Let P be a set of people, C be a set of cars, and D be the relation describing which person drives which car(s).
P = {Carl, Suzanne, Peter, Carla}
C = {Mercedes, BMW, tricycle}
D = {(Carl, Mercedes), (Suzanne, Mercedes), (Suzanne, BMW), (Peter, tricycle)}
This means that Carl drives a Mercedes, Suzanne drives a Mercedes and a BMW, Peter drives a tricycle, and Carla does not drive any of these vehicles.

Functions as Relations

You might remember that a function f from a set A to a set B assigns a unique element of B to each element of A.
The graph of f is the set of ordered pairs (a, b) such that b = f(a).
Since the graph of f is a subset of A´B, it is a relation from A to B.
Moreover, for each element of A, there is exactly one ordered pair in the graph that has a as its first element.
Conversely, if R is a relation from A to B such that every element in A is the first element of exactly one ordered pair of R, then a function can be defined with R as its graph.
This is done by assigning to an element aÎA the unique element bÎB such that (a, b)ÎR.

Relations on a Set

Definition: A relation on the set A is a relation from A to A.
In other words, a relation on the set A is a subset of A´A.
Example: Let A = {1, 2, 3, 4}. Which ordered pairs are in the relation R = {(a, b) | a < b} ?
Answer: R = {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}

Properties of Relation

(1)Reflexive
A relation R on a set A is called reflexive if (a, a)ÎR for every element aÎA.
Example:
= {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}

Answer: R is reflexive because they both contain all pairs of the form (a, a),namely, (1, 1), (2, 2), (3, 3), and (4, 4).

(2)Irreflexive
A relation on a set A is called irreflexive if (a, a)ÏR for every element aÎA.
Example:
These 4 irreflexive relations are :
1. Empty
2. {(1,2)}
3. {(2,1)}
4. {(1,2), (2,1)}

(3)Symmetric
A relation R on a set A is called symmetric if (b, a)ÎR whenever (a, b)ÎR for all a, bÎA.

Example:

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

Answer: R is symmetric.Both (2, 1) and (1, 2) are in the relation so R is symmetric.

(4) Antisymmetric
A relation R on a set A is called antisymmetric if a = b whenever (a, b)ÎR and (b, a)ÎR.

Example:

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

Answer:R is antisymmetric.There is no pair of elements a and b with a ≠ b such that both (a, b) and (b, a) belong to the relation.


(5)Transitive
A relation R on a set A is called transitive if whenever (a, b)ÎR and (b, c)ÎR, then (a, c)ÎR for a, b, cÎA.

Example: Are the following relations on {1, 2, 3, 4} transitive?

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

3. FUNCTIONS

Definition or concept of function on general sets

In discrete mathematics ,functions are used
in the definition of such discrete structures as sequences and strings.
used to represent how long it takes a computer to solve problems of a given size.

Concept of function:

Let and be nonempty sets.
function f from to is an assignment of exactly one element of to each element of A.
We write f (a) if is the unique element of assigned by the function to the element of A.
If is a function from to B, we write f → B

•If is a function from to B, we say that is the domain of and is the codomain of f.
•If f (a) b, we say that is the image of a and is a preimage of b.
•The range, or image, of is the set of all images of elements of A.,
• if is a function from to B, we say that f maps A to B.

Concept of Boolean Function

Definition 1 : literal is a Boolean variable or its complement. A minterm of Boolean variables x1x2, . . . , xn is Boolean product yy2. . .yn where yi xi or
Example1:
Find the minterm such that = 1 if x1 = x3 = 0 and = 0 if x2 = x4 = x5 = 1.
Solution: The minterm is
The sum of minterms that represents the functions is called the sum-of-products expansion or the disjunctive normal form of the Boolean function.

Injective functions

Injective means that every member of “A” has its own unique matching member in “B”.
A function f is injective if and only if whenever f(x) = f(y), x =y.
It’s also called “one to one”.
Ex: {a, b, c, d} to {1,2,3,4,5} with f(a) =2, f(b) =1, f(c)=3, f(d)=4 is one to one.

Surjective functions (an onto function)

 Surjective means that every “B” has at least one matching “A” (maybe more than one).
A function f (from set A to B) is surjective if and only for every y in B, there at least one x in A such that f(x) = y, in other words f is surjective if and only if f(A) = B.
Ex: f be the function from {a,b,c,d,e} to {1,2,3,4} defined by f(a)=2, f(b)=1, f(c)=3, f(d)=3, f(e)=4. Is f is onto function?
Answer: NO

Bijective functions 

Bijective means both Injective and Surjective together.
Perfect “one-to-one correspondence” between the members of the sets is existed.
A function f (from set A to B) is bijective if, for every y in B, there is exactly one x in A such that f(x) = y.
Ex: f be the function from {a,b,c,d,e} to {1,2,3,4,5} with f(a)=2, f(b)=1,
f (c)=6, f(d)=3, f(e)=5. Is f a bijection?
Answer: YES.

Definition and example of inverse function

An inverse function, which we call f-1  is another function that take y back to x. f(x)= y. So, f-1(y)= x.

Example:
  Let f: Z    Z be such that f(x)=x+1
  f(x)= x+1
  y=x+1
  y-1=x
  f-1(y)= y-1
  
Definition and example of composition function


Let g be a function from the set A to the set B and let f be a function from the set B to the set C. The composition of the functions f and g, denoted  by f ◦ g, is defined by
                              (f ◦ g)(a) = f (g(a)).

Example:
         f (x) = 2x + 3 and g(x) = 3x + 2

Solution:
        (f ◦ g)(x) = f (g(x)) 
        f (3x + 2) = 2(3x + 2) + 3 = 6x + 7
   and
        (g ◦ f )(x) = g(f (x))
         g(2x + 3) = 3(2x + 3) + 2 = 6x + 11.

































No comments:

Post a Comment