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:
R = {(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 A and B be nonempty sets.
•A function f from A to B is an assignment of exactly one element of B to each element of A.
•We write f (a) = b if b is the unique element of B assigned by the function f to the element a of A.
•If f is a function from A to B, we write f : A → B
•If f is a function from A to B, we say that A is the domain of f and B is the codomain of f.
•If f (a) = b, we say that b is the image of a and a is a preimage of b.
•The range, or image, of f is the set of all images of elements of A.,
• if f is a function from A to B, we say that f maps A to B.
Concept of Boolean Function
Definition 1 : A literal is a Boolean variable or its complement. A minterm of Boolean variables x1, x2, . . . , xn is Boolean product y1 y2. . .yn where yi = xi or
Example1:
Find the minterm F such that F = 1 if x1 = x3 = 0 and F = 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