UNIT 2 PART 2 Flashcards
RELATIONS+example?
<a>, a and b from any sets, relationship bw a and b</a>
greater than, circle to radius, mother to son</a>
binary relation?
definite rlation between obj in ordered pairs same as relation xRy x,y belongs in R special symbols >
Domain and Range
in D(S) x such that for some y, (x,y) belongs to S
Relation properties
RATS
REFLEXIVE
R(reln) reflexive in X(set) if for x such that x belongs to X, xRx
<=
DIAAG IN RELATION MATRIX
SYMMETRIC
R(reln) symmetric in X(set) if for x,y such that x and y belongs to X and xRy -> yRx
=,brother
transative
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
<=
IRREFLEXIVE
opp of reflexive
antisym
opp of sym
if both there equal
% div by
Relation matrix
reln R from finite X to finite Y
xiRyj -> 1 in ith row, jth col
m(X)* n(Y) matrix
Graph of relation
elements in X as circles
xiRyj -> arrow to it
row to col
equivalence reln
RST
Partition and covering of set
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
composition of relation
.
matching ele
multiply reln matrices
converse of reln
flip all pairs
~
transpose
double transpose -> original
compatibility relation
RS
~~
COMPAT matrix
nodes from graph
except last -> col
except first-> rows
1 -> compat
TRANSITIVE CLOSURE
R+
RURUR^2UR^3…
POSET
RAT
<= -> PO
(P,<=) -> POSET (set,partial ordering reln)
DUAL OF POSET
(P,<=) -> (P,>=)
Hasse diagram
aka ordering diag graphical poset lower to upper no arrows no self loops ele -> dot edge -> a->b b->c then no a -> c
max compat blocks
all connected with other
include rest
compat graph
relation ->
no self loops
no arrows
one edge bw nodes
compat steps
- prove compat
- reln graph
- compat graph
- compat graph
- compat matrix
- compat blocks
