R jest zbiorem par uporządkowanych, czyli podzbiorem iloczynu kartezjańskiego dwóch zbiorów



Pobieranie 30.76 Kb.
Data02.05.2016
Rozmiar30.76 Kb.

1.2.Relacje


Określenie relacji:

Relacja R jest zbiorem par uporządkowanych, czyli podzbiorem iloczynu kartezjańskiego dwóch zbiorów: A (dziedzina relacji) i B (przeciwdziedzina relacji)

R  A  B

Zamiast pisać (a, b) R piszemy często aRb. Jeśli dziedzina i przeciwdziedzina relacji są tym samym zbiorem (A=B), to mówimy o relacji określonej na zbiorze A.

R  A  A

Własności relacji:

Mówimy, że relacja R na zbiorze A jest:



  • zwrotna, jeśli (aA) (aRa)

  • przeciwzwrotna, jeśli (aA) ((aRa))

  • przechodnia, jeśli (aRb bRc) aRc

  • symetryczna, jeśli aRb bRa

  • przeciwsymetryczna, jeśli aRb (bRa)

  • antysymetryczna, jeśli (aRb bRa) a=b

Relacje równoważności:

Relację R na zbiorze A nazywamy relacją równoważności, gdy R jest:



  • zwrotna,

  • symetryczna,

  • przechodnia.

Relacja równoważności dzieli zbiór A na klasy równoważności (klasy abstrakcji). Przez [a]R oznaczamy klasę równoważności relacji R o reprezentancie a.

[a]R = { b | bA  aRb }

(a,bA) ( [a]R = [b]R  [a]R  [b]R = Ø )

 [a]R = A

aA

Relacje porządkujące:

Relacją częściowego porządku na zbiorze A nazywamy relację R, która jest:



  • zwrotna,

  • przechodnia,

  • antysymetryczna.

Przykładem relacji częściowego porządku może być relacja zawierania się zbiorów () określona na zbiorze potęgowym.

Relacją liniowego porządku na zbiorze A nazywamy relację R, która posiada następujące własności:



(a,bA) ( aRb  bRa )

Przykładem relacji liniowego porządku jest relacja „mniejszy lub równy” () określona na zbiorze nieujemnych liczb całkowitych.



Domknięcia relacji:

k-ty stopień Rk relacji R na zbiorze A określamy nastepująco:

aRob  a=b

aR1b  aRb

........................

aRkb  (cA) (aRc  cRk-1b)

czyli np.

aR2b  (cA) (aRc  cRb)

aR3b  (c1A) (aRc1  cR2b)  (c1,c2A) (aRc1  c1Rc2  c2Rb)

Przykład:

R  NN

N = {0, 1, 2, ...} – zbiór liczb naturalnych (z zerem)

nRm  n = m+2

nR2m  n = p+2  p = m+2  n = m+4

nR3m  n = p1+2  p1 = p2+2  p2 = m+2  n = m+6

(8, 6)  R

(8, 4)  R2

(8, 2)  R3

Przechodnie domknięcie R+ relacji R na zbiorze A definiujemy następująco:

aR+b  (i1) ( aRib )

Przechodnie i zwrotne domknięcie R* relacji R na zbiorze A definiujemy następująco:

aR*b  (i0) ( aRib )

Inna (rekurencyjna) definicja domknięcia przechodniego R+



  1. aRb  aR+b

  2. (aR+b  bR+c)  aR+c

  3. nic innego nie należy do R+ poza tym, co wynika z punktów (1) i (2).

Niektóre użyteczne zależności:

aR*b  aR+b  a=b

R* = R+  Ro

R+ =  Ri

i1

R* =  Ri



i0

Przechodnie domknięcie R+k relacji R stopnia k na zbiorze A definiujemy następująco:

aR+kb  (  1 i k ) ( aRib )

Przechodnie i zwrotne domknięcie R*k relacji R stopnia k na zbiorze A definiujemy następująco:

aR*kb  (  0ik ) ( aRib )

Niektóre użyteczne zależności:

R+k = R1  R2  ...  Rk =  Ri

1ik


R*k = Ro  R1  ...  Rk =  Ri

0ik


Twierdzenie:

Niech n = #A, n< (zbiór A jest skończony). Wtedy R+  R+n



Macierze boolowskie relacji:

Niech:


A = {a1, a2, ..., an}

R  AA


In = {1, 2, ..., n}

Macierzą boolowską M reprezentującą relację R nazywamy odwzorowanie:

M: InIn → {0, 1}

takie, że:

Przykład:

A = {a1, a2, a3}

R = {(a1, a3), (a2, a3), (a3, a2)}



Niech R i R’’ będą relacjami i niech M reprezentuje R oraz M’’ reprezentuje R’’.

R  AA R’’  AA

Niech R będzie sumą teoriomnogościową R i R’’

R = R  R’’

a1Ra2  a1Ra2  a1R’’a2

Wówczas:

M = M  M’’



Niech teraz R będzie złożeniem R i R’’

R = R R’’

a1Ra2  ( aA ) ( a1Ra  aR’’a2 )

Wówczas:

M = M  M’’



Przykład:

A = {a, b}

R = {(a, a), (a, b), (b, b)}

R’’ = {(a, b), (b, a)}

R1 = R  R’’= {(a, a), (a, b), (b, a), (b, b)}

R2 = R R’’= {(a, a), (a, b), (b, a)}

Obliczanie domknięcia przechodniego dla R AA; n = #A < ∞

Ponieważ R+ R+n , więc wystarczy obliczyć

R+ = R1  R2  ...  Rn

Algorytm:

Wejście: R reprezentowane przez M

Wyjście: R+ reprezentowane przez M+

M+ := 0; (0 – macierz zerowa)

M := M;



for i := 1 to n do

begin

M+ := M+  M;

M := M ∙ M;

end;

Przykład:

A = {a, b,c}

R = {(a, c), (b, c), (c, a)}



Początkowo:



i = 1


i = 2


i = 3


Ostatecznie:



R+ = {(a, a), (a, c), (b, a), (b, c), (c, a), (c, c)}


©absta.pl 2016
wyślij wiadomość

    Strona główna