TASK 3

exciting math indeed. alot of reading and understandings accompanied with patience are required.
These are the assignment:


 TASK 3

 1. Explain how to represents sets using a computer. Give 1 example of representing sets by using computer and 1 example for representing each operation (union, intersection and complement), sets in computer respectively.
2. RELATION: a) Describe the concept of relations between 2 sets. b) Use the appropriate methods for representing relation(Reflexive, Symmetric, Antisymmetric and Transitive) c) Explain some of the properties of relations.
 3. FUNCTIONS
 a) Definition or concept of function on general sets.
 b) Explain the concept of Boolean Functions.
 c) Explain each types of function(Injective, Surjective and Bijective)
 d) Give the definition and examples of Inverse Function.
 e) Give the definition and examples of Composition Function

_________________________________________________________________________________

 1. Sets reprisented via computer

 There are two methods to represent sets using a computer :
 Unordered fashion
 a. Store the elements of the set in an unordered fashion: -Computing operation are union, intersection and differ entence of two set. -Each operation require large amount of searching elements.

Arbitrary ordering.
 b. Store the elements using an arbitrary ordering of the elements of the universal set.
Easy to make compute set.

1.  Let's assume that set U is a finite and of reasonable size.
2.  First, we'll specify an arbitrary ordering of elements of U, for instance a1, a2, a3, ..., an.
3. Then, we'll represent a subset A of U with the bit string of length n, where the i th bit in this string is:                                                       if ai ∈ A, and 0, if ai ∉ A.

A. Store the elements of the set in an unordered fashion: -Computing operation are union, intersection and differ entence of two set. -Each operation require large amount of searching elements.

 Example 1:     Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, and the ordering of elements of U has the elements in increasing order; that is, ai = i . What bit strings represent the subset of all odd integers in U, the subset of all even integers in U, and the subset of integers not exceeding 5 in U?    


Solution:    The bit string that represents the set of odd integers in U, namely, {1, 3, 5, 7, 9}, has a one bit in the first, third, fifth, seventh, and ninth positions, and a zero elsewhere. It is 10 1010 1010.   Similarly, we represent the subset of all even integers in U, namely, {2, 4, 6, 8, 10}, by the string   01 0101 0101.   The set of all integers in U that do not exceed 5, namely, {1, 2, 3, 4, 5}, is represented by the string   11 1110 0000. 1) 
Ā (Complement) Solution: Bit string for A: 0101 0111,
Then Ā = 1010 1000 (Therefore, Ā = {0,1,2,4})

2)       A ∩ B (Intersection) Solution: Bit string for A: 0101 0111 Bit string for B: 1111 1100
Then, A ∩ B =0101 0111 ˄  1111 1100 = 0101 0100        
         (A ∩ B = {1,3,5} )

3)      A U B (Union) Solution: Bit string for A: 0101 0111 Bit string for B: 1111 1100   Then A U B = 0101 0111 ˅  1111 1100 = 1111 1111
(A U B = U = {0,1,2,3,4,5,6,7})



 2.Relation 

 Relation Between 2 Sets:
 A relation is a set of ordered pairs(x,y) ,
 -the first component are the input values(Domain).
 - second component are the output values(Range).

A relation R defined by ( , {(x,y):x  }), is the set of ordered pairs of all Input Values (x) and all Output Values(y) such that each element x is related to the corresponding element y. Here, x=Domain of the Relation y=Range of the Relation x & y no values, it will repeated x is called Independent variable and y is called Dependent variable because its value depends on the x-value chosen.







 3.FUNCTION

Function DEFINITION OR CONCEPT OF FUNTION ON GENERAL SETS
Function is a relation between a set of inputs and a set of permissible outputs with the property that each input is related to exactly one output. As an example:-

The function f maps to A to B 


Boolean function
A Boolean function describes the ways to gain the value of boolean output via logical calculation from Boolean inputs. 
The functions play a basic role in questions of complexity theory also the design of circuits and chips for digital computers.



The properties of Boolean functions play a critical role in cryptography, particularly in the design of symmetric key algorithms Boolean functions are often represented by sentences in propositional logic, and sometimes as multivariate(involving 2 or more variables) A literal is a Boolean variable or its complement. A minterm of the Boolean variables x1,x2,...,xn is a Boolean product y1y2 ···yn, where yi = xi or yi = xi. Hence, a minterm is a product of n literals, with one literal for each variable.

Example:
Find the sum-of-products expansion for the function F (x, y, z) = (x + y)z. Solution: We will find the sum-of-products expansion of F (x, y, z) in two ways. First, we will use Boolean identities to expand the product and simplify.
We find that
 F (x, y, z) = (x + y)z =xz+yz =x1z+1yz =x(y+y)z+(x+x)yz 
=xyz+xyz+xyz+xyz =xyz+xyz+xyz.

 Distributive law Identity law Unit property Distributive law Idempotent law Second, we can construct the sum-of-products expansion by determining the values of F for all possible values of the variables x, y, and z. These values are found in Table 2. The sum-of- products expansion of F is the Boolean sum of three minterms corresponding to the three rows of this table that give the value 1 for the function.
This gives F (x, y, z) = xyz + xy z + xyz.
It is also possible to find a Boolean expression that represents a Boolean function by taking a Boolean product of Boolean sums. The resulting expansion is called the conjunctive normal form or product-of-sums expansion of the function.



INJUCTIVE : f (a) = f (b) implies that a = b for all a and b in the domain of f. Involves one to one function.

It can be injective (or one-to-one), where any value in the codomain/range can be produced by at most one value from the domain. The example function f(x) is NOT injective if we define its domain and codomain both as the real numbers (since 4*4 = 16, but (-4)*(-4) = 16). 
Despite, if we define its domain as the positive real numbers, then it is injective.


SURJECTIVE : Onto function every element b ∈ B there is an element a ∈ A with f (a) = b. BIJECTION : one-to-one function AND onto function.

this can be surjective (or onto), which means that every value in the codomain can be produced by the function. If we define both the domain and the codomain of the example f(x) to be all real numbers, then f(x) is NOT surjective, due to unable to produce negative numbers with the given domain.


INVERSE FUNCTION : Definition Let f be the bijection from set A to the set B The inverse function of f is the function that assigns to an element b belonging to B the unique element a in A such that   f (a) = b  The inverse function of f is denoted by  fˉˡ  Hence,  fˉˡ (b) = a  when f(a) = b
Example:

Example
let f : R     
R be the bijection given by the formula: f(x)= 4x + 1
    • Write f(x) = y ,that is  4x + 1 = y
    • Then solve for x
                   4x = y + 1
                    x = y – 1
                            4
Answer:   fˉˡ (y)= = y – 1
                                      4

 DEFINITION OF COMPOSITION OF FUNCTION
Process to combine two functions . One function is to be done first then its result is substitute in place of each x to another function. notation for a composite function : ( ƒº g) (x) = ƒ( g(x))

Given that ƒ (x) =5x and g (x) =x²+2.
Find ( ƒºg )(x) and (gºƒ)(x)
Solution 1:                                      Solution 2: (ƒºg)(x)                                          (gºƒ)(x)
 -ƒ( g (x))                                       - g(ƒ(x))
  ƒ (x²+2)                                       - g(5x)
  5( x²+2)                                        -(5x)²+2
  = 5x²+10                                      -5x²+2

Given that ρ(x)=x+4 and h(x) = x²
get the value of 
 a) (hºρ)(x)                 b) (ρºh)(3)
    -h(ρ(x))                    -ρ(h(x))
    -h(x+4)²                   -ρ(3)²
    -x²+8x+8                 -9+4 =11

here are the slides :) enjoy


  • Digg
  • Del.icio.us
  • StumbleUpon
  • Reddit
  • RSS

0 comments:

Post a Comment