UNIT 2 PART 2

Question 1

RELATIONS+example?

Answer 1

<a>, a and b from any sets, relationship bw a and b</a>

greater than, circle to radius, mother to son</a>

Question 2

binary relation?

Answer 2

definite rlation between obj in ordered pairs
same as relation
xRy
x,y belongs in R
special symbols >

Question 3

Domain and Range

Answer 3

in D(S)
x such that for some y, (x,y) belongs to S

Question 4

Relation properties

Answer 4

RATS

Question 5

REFLEXIVE

Answer 5

R(reln) reflexive in X(set) if for x such that x belongs to X, xRx
<=
DIAAG IN RELATION MATRIX

Question 6

SYMMETRIC

Answer 6

R(reln) symmetric in X(set) if for x,y such that x and y belongs to X and xRy -> yRx
=,brother

Question 7

transative

Answer 7

R(reln) symmetric in X(set) if for x,y,z such that x and y and z belongs to X and xRy and yRz, xRz
<=

Question 8

IRREFLEXIVE

Answer 8

opp of reflexive

Question 9

antisym

Answer 9

opp of sym
if both there equal
% div by

Question 10

Relation matrix

Answer 10

reln R from finite X to finite Y
xiRyj -> 1 in ith row, jth col
m(X)* n(Y) matrix

Question 11

Graph of relation

Answer 11

elements in X as circles
xiRyj -> arrow to it
row to col

Question 12

equivalence reln

Answer 12

RST

Question 13

Partition and covering of set

Answer 13

set of sets given S
one set given A
partition + covering -> union of S = A and sets in S disjoint
covering-> union of S = A and sets in S not disjoint
one set -> both

Question 14

composition of relation

Answer 14

.
matching ele
multiply reln matrices

Question 15

converse of reln

Answer 15

flip all pairs
~
transpose
double transpose -> original

Question 16

compatibility relation

Answer 16

RS

~~

Question 17

COMPAT matrix

Answer 17

nodes from graph
except last -> col
except first-> rows
1 -> compat

Question 18

TRANSITIVE CLOSURE

Answer 18

R+

RURUR^2UR^3…

Question 19

POSET

Answer 19

RAT
<= -> PO
(P,<=) -> POSET (set,partial ordering reln)

Question 20

DUAL OF POSET

Answer 20

(P,<=) -> (P,>=)

Question 21

Hasse diagram

Answer 21

aka ordering diag
graphical poset
lower to upper
no arrows
no self loops
ele -> dot
edge -> a->b b->c then no a -> c

Question 22

max compat blocks

Answer 22

all connected with other

include rest

Question 23

compat graph

Answer 23

relation ->
no self loops
no arrows
one edge bw nodes

Question 24

compat steps

Answer 24

1. prove compat
2. reln graph
3. compat graph
4. compat graph
5. compat matrix
6. compat blocks