- Unordered fashion
- Arbitrary ordery
Example:
U =
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
A =
{1, 3, 5, 7, 9} – Odd
A1
|
A2
|
A3
|
A4
|
A5
|
A6
|
A7
|
A8
|
A9
|
A10
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
A1
is element of A
Then,
A1 will have value of 1.
Union
(OR)
1 1 1 1 1 0 0 0 0 0
1 0 1 0 1 0
1 0 1 0
1
1 1 1 1 0 1 0 1 0
So
the answer is 1 2 3 4 5 7 9
Intersect
(AND)
1 1 1 1 1 0 0 0 0 0
1 0 1 0 1 0
1 0 1 0
1
0 1 0 1 0 0 0 0 0
So
the answer is 1 3 5
#Relation
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)}
#Functions
A
Boolean function describes how to determine a Boolean value
output based on some logical calculation
from Boolean inputs.Boolean functions are often represented by
sentences in propositional
logic.
A
function consists of:
- a domain (the set being mapped from),
- a codomain (the set being mapped to),
- a mapping from the domain to the codomain.
Usually,
for each element in the domain, the mapping assigns one element of
the codomain. If this happens, the function is said to be total.
Sometimes,
there are some elements in a domain that are not assigned at all.
Thus, the mapping for these elements are unknown. Such functions are
said to be partial because
not every element in the domain is mapped.
For
finite domains and codomains, we can draw pictures.
Types
of function :
1)
injective function(one-to-one)
- If and only if f(x)=f(y) implies x=y for all x,y in the domain of f.2) Surjective function (onto)
- If and only if for every bB there is an element aA such that f(a)=b
- Alternative way to understand: all codomains elements are covered
3)
Bijective (both one-to-one[injection] and onto[surjection])
Inverse
function:
Let
f be a bijection from set A to set B. The inverse function of f is
the function that assigns to an element b from B the unique element a
in A such that f(a)=b. The inverse function of f is denoted by f-1
(f inverse). Hence, f-1
(b)=a, when f(a)=b . If inverse function of f
exists, f is called invertible.
SLIDE FOR THIS TASK
http://www.scribd.com/doc/131035898/3
No comments:
Post a Comment