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.∀a∀b∈
A, (a, b) ∈ R → (b, a) ∈ R.
Antisymmetric
Implies the identity of the respective elements.∀a∀b∈
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
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.
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:
Solution:
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 (f ◦ g)(a).
Example 19:
f(x) = x +
2
g(x) = 3 –
x
Find (f ◦ g)(a)
and the value of (f ◦ g)(2).
Solution:
f(x) = x +
2
g(x) = 3 –
x
f[g(x)] = ( 3 – x ) + 2
(f ◦ g)(a) = 5 – x
(f ◦ g)(2)
= 5 – 2
(f ◦ g)(2) = 3
Therefore, (f ◦ g)(2)
= 3
Example 20:
Refer to
Example 19, find (g ◦ f)(a) and the value of (g ◦ f)(4).
g(x) = 3 –
x
f(x) = x +
2
g[f(x)] = 3 – ( x + 2 )
(g ◦ f)(a) = 1 – x
(g ◦ f)(4)
= 1 – 4
(g ◦ f)(4) = -3
Therefore, (g ◦ f)(2)
= -3
No comments:
Post a Comment
1+1=