TASK THREE

#Computer representation of Sets

1. Unordered fashion
2. 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

Boolean Function

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 bB there is an element aA 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