Group Members

  • Pang Kok An 032195
  • Muhd. Faiz Fahimi B. Razali 033225
  • Hasyazid B. Osman 033147
  • Nurul Nabilah Bt. Azman 032236
  • Nurul Fasihah Bt. Che Azmi 032220
  • Siti Aminah Bt. Ahmad Sahrel 032806
  • Roshatul Hidaya Bt. Rosdin 032558
  • Nusaibah Bt. Yahaya 032357

Monday, 11 March 2013



Representation of sets in computers

All the numbers in our daily are represented in the decimal form, which are numbers with 0 to 9 digits. However, computers recognize numbers in binary form which consists of 0 and 1 only. Computers can recognize binary numbers very quick but not for decimal numbers because conversion is needed to convert decimal numbers into binary. This conversion may slows down the time needed for the CPU to recognize numbers in decimal.

We usually write our sets like this:

S = { 4, 3, 5 }

You’re asked to recognise the number 4 in a set. Well, I guess it doesn’t take you a long time on this, right? What if we let a computer to recognize the number 4 in set. 

 

The computer gets used to binary numbers. Therefore, it have to convert decimals into binaries in order to recognize it. This is rather a slow process. If it encounters a set with 100 elements or even 1000 elements, the downside of this method is more obvious.

Rather than converting numbers into decimals, sets are preferred to be presented in the form of bit string, in which computers recognize certain types of elements in a set by determining the digit 0 and 1 only. There is no need to force the computers into reading decimals. I’ll show you a few examples how it works.


Example 1:

S = { a, b, e, g, h, i, n, o, r, t, u, z }

Recognise the subset of set S consists of only vowel elements and turn the subset into a bit string.

Solution:

We’ll turn all the vowel elements to 1 and all the non-vowel elements into 0. Therefore, the bit string for the subset with vowel elements is

101001010010

From the above bit string, the computer can recognize the vowel elements by looking at the bits 1. So the elements of vowel are in the the 1st, 3rd, 6th, 8th and 11th position respectively.


Example 2:

Refer to Example 1, what is the bit string of the subset of set S which consists of only consonant elements?

Solution:

The subset of set S with consonant elements is exactly the complement of the subset with vowel elements.

bit string of vowel subset = 101001010010

When dealing with complements, just change all 1’s into 0’s. Therefore we get:

bit string of consonant subset = 010110101101


Example 3:

Refer to Example 1,

S = { a, b, e, g, h, i, n, o, r, t, u, z }

V = { a, e, i, o, u }

E = { a, b, o, r, t }

Set V has all of their elements vowels while set E represents the alphabets in the word “abort”. Please write the bit string and the set of V E.

Solution:

From example 1, we have concluded that the bit string for set V is 101001010010. The bit string for set E is 110000011100. We can find the bit string of V E by comparing the two sets like this:

1  0  1  0  0  1  0  1  0  0  1  0
1  1  0  0  0  0  0  1  1  1  0  0

Remember when we learn about propositional logic. The logical operator yields true results if at least one of the propositions that we put into comparison is true. We’ll apply the same concept in this section. Unity is the set that includes all the elements present in at least one of the sets. Therefore, the “or” operator is very suitable to be used in this situation to find the bit string. If two binary values, at least one of them is 1, the binary value yielded is 1. Otherwise, the result is 0. 

1  0  1  0  0  1  0  1  0  0  1  0
1  1  0  0  0  0  0  1  1  1  0  0
                                           
1  1  1  0  0  1  0  1  1  1  1  0

The bit string we get is 111001011110. Therefore, from the above working, we can conclude that V E = { a, b, e, i, o, r, t, u }


Example 4:

Refer to Example 1 and Example 3, please write the bit string and the set of V E.

Solution:

We will be solving this question almost like what we did in Example 3.

1  0  1  0  0  1  0  1  0  0  1  0
1  1  0  0  0  0  0  1  1  1  0  0

But this time we’re finding the bit string of set V E. In this case, we use the logical operator “and” in this situation, where the binary value yielded is 1 if every binary values we put into comparison is 1.

1  0  1  0  0  1  0  1  0  0  1  0
1  1  0  0  0  0  0  1  1  1  0  0
                                           
1  0  0  0  0  0  0  1  0  0  0  0

The bit string we get is 100000010000. Therefore, from the above working, we can conclude that V E = { a, o }


Relations

Binary relation

A binary relation is a set R which consists all the relations of ordered pairs of elements from two different sets.


Example 5:

Set A contains all the name of students in the course of Computer Science, whereas set B consists of different religions among students. Represent R in matrix form.

Which of the sets below are not exist in set R?
1.     { Minah, Islam }
2.     { Pang, Christian }
3.     { Lo Chii Toh, Christian }
4.     { Karshan, Buddhist }

Solution:

The first set, { Minah, Islam } is exist in set R because Minah is a muslim, therefore the relation is true and it is a subset of R. We can write a R b to denote this relation. a R b means (a, b) R, or in other words, a is related to b by R.

Pang is a Buddhist, he is not a Christian. Therefore, he has no relation with Christian. Instead of { Pang, Christian }, { Pang, Buddhist } appears in the set R.

Lo is indeed a Christian, Therefore, { Lo Chii Toh, Christian } appears in the set R.

Karshan’s religion is Hindu, he is not a Buddhist. Therefore, { Karshan, Buddhist } is not appeared in the set R.

The relation set, R should looks like this:

R = { { Minah, Islam }, { Pang, Buddhist }, { Lo Chii Toh, Christian } , { Karshan, Hindu }}

We can represent relation, R in another way. Which is, using matrix

 



We denote the matrix form of R as MR. We treat the relations which are true as 1 and 0 for which that are false.


   


Example 6:

Consider R = { { a, b }, { b, c }, { b, a }, { c, c } }

Present set R in digraph form.

Solution:

A digraph is what we used to illustrate the relation set, R in a graphical way. We’ll will illustrate the digraph slowly, one subset by one.

{ a, b }

We draw an arrow from a to b to imply that a is related to b

 


Use the same method for b is related to c

  

 b is related to a



 



c is related to itself
  





Combine these graphics above. We will get the digraph like this:






Properties of Relations

Reflexive

A reflexive relation has all the subsets of elements of A which is related to itself. We can say that (a, a) R for every element a A.

Each element is related to itself, in which is defined mathematically as a ( (a, a) R ).


Example 7:

Set A contains all the elements from integer 1 to 4.

A = {1, 2, 3, 4}

A x A = {(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(2,4),(3,1),(3,2),(3,3),(3,4),(4,1),(4,2),(4,3),(4,4)}

There are 2 relations regarding to set A.

R1 = {(1, 1)}
R2 = {(2, 3), (1, 1), (2, 2), (3, 3), (4, 4)}

Are R1 and R2 reflevive relations?

Solution:

R2 is reflexive because contain all pairs of the form (a, a), namely, (1, 1), (2, 2), (3, 3), and (4, 4).

Whereas, R1 is not reflexive because it doesn’t have all of the subsets of elements of A which is related to itself.

Symmetric

If the order of the elements is irrelevant.ab A, (a, b) R (b, a) R.

Antisymmetric

Implies the identity of the respective elements.ab A, (a, b) R ^ (b, a) R   a = b

Example 8:

A = {1, 2, 3, 4}
A x A = {(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(2,4),(3,1),(3,2),(3,3),(3,4),(4,1),(4,2),(4,3),(4,4)}

R1 = {(1, 2), (2, 3)}  antisymmetric
R2 = {(1, 1), (2, 2)} symmetric and antisymmetric
R3 = {(1, 2), (2, 1)} symmetric


Transitive

if the middle element of a chain can be removed. a b c A, (a, b) R ^ (b, c) R (a, c) R.

Example 9:

A = {1, 2, 3, 4}

A x A = {(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(2,4),(3,1),(3,2),(3,3),(3,4),(4,1),(4,2),(4,3),(4,4)}


R1 = {(1, 2), (2, 3), (1, 3)}     transitive
R2 = {(1, 2), (2, 3)}    not transitive: (1, 3) R2
R3 = {(1, 1)}    transitive
R5 = {(2, 3), (3, 4), (3, 2)} is not transitive (2,2), (3, 3), (2, 4) R5


Functions

We say a function  f  is from set A to set B, if exactly one element of B is exactly mapped to each element of A.

Example 10:

Set A represents some students’ name and set B represents the laptop brands each of them is using.

A = { Pang, Henry, Jong, Alex, Max }
B = { Asus, Lenovo, HP, Acer, Dell }
 




Is it true for the statement “The function  f  is from A to B” ?

Solution:

Yes. Each element of A is related to exactly one of the elements of B.


Example 11: 

 


Is it true for the statement “The function  f  is from A to B” ?

Solution:

No. One of the elements of A, “Henry” is related to more than 1 element of B.

Example 12:

Refer to Example 10, what is the image for Pang and the preimage for Lenovo?

Solution:

The image of an element in set A is the element of set B which has a relationship between them.

The preimage of an element in set B is the element of set A which has a relationship between them.


Example 13:

Refer to Example 10, find the domain, codomain, and the range of the function.

Solution:

Domain is what we used to refer to set A, and the codomain is what we used to refer to set B, if the function f is from A to B.

Therefore, the domain is equal to set A, which is { Pang, Henry, Jong, Alex, Max }

The codomain is equal to set B, which is { Asus, Lenovo, HP, Acer, Dell }

The range of the function is a set of elements of B which has more than 1 preimage.

Therefore, the range in this condition is { Asus, Lenovo, HP, Dell }. Acer is not included because it has no preimage.


Boolean Function

A boolean function is what we used to determine the truth value of a statement’s, which is represented by a Boolean value, either 0 or 1. We determine the validity of a statement by inserting either 0 or 1 as the variables and use logical operations in determining the truth value of a statement.


Example 14:

Consider a Boolean function F(x, y) = xy. Determine the truth value for F(0, 0), F(1, 0), and F(1, 1).

When F(0, 0), x = 0 and y = 0,

xy = 0 x 0 = 0

The truth value for F(0, 0) is 0. 


When F(1, 0), x = 1 and y = 0,

xy = 1 x 0 = 0

The truth value for F(1, 0) is 0. 


When F(1, 1), x = 1 and y = 1,

xy = 1 x 1 = 1

The truth value for F(1, 1) is 1. 


Example 15:

Consider a Boolean function F(x, y) = x + ¬ y. Determine the truth value for F(0, 0), F(1, 0), and F(1, 1).

When F(0, 0), x = 0 and y = 0,

x + ¬ y = 0 + ¬ 0 = 0 + 1 = 1

The truth value for F(0, 0) is 1. 


When F(1, 0), x = 1 and y = 0,

x + ¬ y = 1 + ¬ 0 = 1 + 1 = 1

The truth value for F(1, 0) is 1. 


When F(0, 1), x = 1 and y = 1,

x + ¬ y = 0 + ¬ 1 = 0 + 0 = 0

The truth value for F(1, 1) is 0. 


Type of functions:

Injective

Definition: a function is said to be one-to-one or an injuction, if and only if f(a)=f(b) implies a=b for all a and b in the domain of f. A function is said to be injective if it is one-to-one.

Examples 16:

Determine whether function f from {a,b,c,d} to {1,2,3,4,5}  with f(a)=4, f(b)=5,f(c)=1 and f(d)=3 is one- to- one.

Solution:

The function f is one-to-one because f takes on different value at the four elements of its domains.







Surjective

Definition: A function f from A to B is called onto, if and only if for every element b  B there is an element a A with f(a)=b. a function is called surjective ifit is onto.

 

Bijective

Definition:  The function f is a one-to-one corresponding or a bijection if it is both one-to-one and onto. We also said that such function is bijective.

 



Examples 17:

Let f be the function from {a,b,c,d} to {1,2,3,4}  with f(a)=4, f(b)=2, f(c)=1 and f(d)=3. Is f a bijection?

Solutions:

The function is one-to-one and onto. It is one-to-one because no two values in the domain are assigned the same function value. It is onto because all four element of the codomain are images of element in the domain. Hence, f is bijection.


Inverse Function

The inverse of a function is the set of ordered pairs obtained by interchanging the first and second elements of each pair in the original function.

Should the inverse of function f (x) also be a function, this inverse function is denoted by f -1(x).
Note: If the original function is a one-to-one function, the inverse will be a function.
[The notation f -1(x) refers to "inverse function". It does not algebraically mean 1/f (x).]
If a function is composed with its inverse function, the result is the starting value. Think of it as the function and the inverse undoing one another when composed.

Consider the simple function f (x) = {(1,2), (3,4), (5,6)}
and its inverse f -1(x) = {(2,1), (4,3), (6,5)}


Examples 18:

Given function f, find the inverse relation. Is the inverse relation also a function?

Solution:

Function f is a one-to-one function since the x and y values are used only once. Since function f is a one-to-one function, the inverse relation is also a function.
Therefore, the inverse function is:






Composition Function

Composition function is about a function which acts as a perimeter of another function. For example, f[g(x)].  f[g(x)] means that the function f takes the g(x) as its perimeter. f[g(x)] We usually states f[g(x)] as (fg)(a).


Example 19:

f(x) = x + 2
g(x) = 3 – x

Find (fg)(a) and the value of (fg)(2).

Solution:

f(x) = x + 2
g(x) = 3 – x

f[g(x)] = ( 3 – x ) + 2
(fg)(a) = 5 – x

(fg)(2) = 5 – 2
(fg)(2) = 3

Therefore, (fg)(2) = 3

Example 20:

Refer to Example 19, find (gf)(a) and the value of (gf)(4).

g(x) = 3 – x
f(x) = x + 2

g[f(x)] = 3 – ( x  + 2 )
(gf)(a) = 1 – x

(gf)(4) = 1 – 4  
(gf)(4) = -3  

Therefore, (gf)(2) = -3



No comments:

Post a Comment

1+1=