12, Lekce 4

Binární relace doc. RNDr. Josef Kolář, CSc. Katedra teoretické informatiky FIT České vysoké učení technické v Praze c

Josef Kolar, 2011

Základy diskrétní matematiky, BI-ZDM ZS 2011/12, Lekce 4

Evropský sociální fond. Praha & EU: Investujeme do vaší budoucnosti

doc. Josef Kolář (FIT ČVUT)

Binární relace

ZDM, ZS 2011/12, Lekce 4

1 / 26

Relace

Binární relace Co je to relace? Relace (neformálně) je vzájemný vztah mezi nějakými objekty. Svět je plný relací a matematika se zabývá studiem jejich vlastností.

Příklad 1 V následujících sděleních najdeme několik různorodých příkladů relací: 1

Slečna Irma miluje kapitána Armána.

2

Číslo 123456789 je dělitelné číslem 643.

3

Trojice přirozených čísel 3,4,5 představuje tzv. Pythagorejská čísla (platí pro ně 32 + 42 = 52 ).

4

Paní Nováková je manžekou pana Nováka a miluje pana Vonáska.

5

Přednáška z předmětu BI-ZDM se koná v pondělí od 7:30 v NTK.

6

Jan a Jiří jsou sourozenci.


Binární relace


2 / 26

Relace

Binární relace - definice Definice 2 ( binární relace) Nechť X, Y jsou množiny a R ⊆ X × Y . Trojice hR, X, Y i se nazývá binární relace z X do Y . Množinu X nazýváme levým oborem a množinu Y pravým oborem relace hR, X, Y i. Je-li (a, b) ∈ R, píšeme aRb a říkáme, že prvek a je v relaci R s prvkem b. Je-li (a, b) ∈ / R, říkáme, že a není v relaci R s prvkem b. Binární relaci hR, X, Xi nazýváme binární relací na X.

Definice 3 ( n-ární relace) Nechť X1 , X2 , . . . , Xn pro n ≥ 2 jsou množiny a R ⊆ X1 × X2 × · · · × Xn . Potom se (n + 1)-tice hR, X1 , X2 , . . . , Xn i nazývá n-ární relace. Je-li R ⊆ X n , pak hR, X, X, . . . , Xi se nazývá n-ární relací na X. doc. Josef Kolář (FIT ČVUT)

Binární relace


3 / 26

Relace

Reprezentace konečných relací Úmluva: Je-li levý a pravý obor (binární) relace hR, X, Y i jasný z kontextu, pak k označení relace používáme jen R. Někdy vynecháváme přívlastek binární a mluvíme jen o relaci. Pro reprezentaci (binárních) relací máme několik možností: množinová reprezentace, tj. výčet uspořádaných dvojic (příp. n-tic) diagram relace kartézské vyjádření tabulka / matice atd.


Binární relace


4 / 26

Relace

Příklad reprezentace relací Příklad 4 Nechť X = {2, 3, 4}, Y = {3, 4, 5, 6, 7} a relaci R z X do Y definujeme takto: (x, y) ∈ R ⇔df x dělí (beze zbytku) y V množinové reprezentaci bude R = {(2, 4), (2, 6), (3, 3), (3, 6), (4, 4)}. Kontrolní otázka: Proč není v R dvojice (2, 2) podobně jako (3, 3) a (4, 4)? Diagram této relace a další formy její reprezentace viz OBRÁZEK 4.1 a) až d). Jak by vypadal diagram stejně definované relace na množině X = Y = {2, 3, 4, 5, 6, 7}? OBRÁZEK 4.2


Binární relace


5 / 26

Relace

Definiční obor a obor hodnot relace Definice 5 ( definiční obor, obor hodnot) Nechť hR, X, Y i je binární relace. Definiční obor D(R), resp. obor hodnot H(R) relace R definujeme vztahy: D(R) = {x ∈ X; (∃y ∈ Y ) xRy}, resp. H(R) = {y ∈ Y ; (∃x ∈ X) xRy}.

Příklad 6 Pro relaci z minulého příkladu máme X = {2, 3, 4}, Y = {3, 4, 5, 6, 7} a R = {(2, 4), (2, 6), (3, 3), (3, 6), (4, 4)}. Pro tuto relaci tedy platí D(R) = {2, 3, 4} = X, H(R) = {3, 4, 6}.


Binární relace


6 / 26

Relace

Definiční obor a obor hodnot relace Příklad 7 1

Mějme binární relaci R definovanou na následující množině lichých čísel X = {3, 5, 7, . . . , 49} takto: mRn ⇔df m 6= n a m dělí n beze zbytku. Určete definiční obor a obor hodnot této relace. D(R) = {3, 5, 7, 9, 11, 13, 15}, H(R) = {9, 15, 21, 25, 27, 33, 35, 39, 45}

2

Mějme binární relaci S definovanou na množině čtyřbitových nezáporných čísel X = {0, 1, 2, . . . , 15} takto: mSn ⇔df dvojkový zápis m obsahuje o dvě číslice 1 méně než dvojkový zápis n. Určete definiční obor a obor hodnot této relace. D(S) = {0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12} H(S) = {3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15}


Binární relace


7 / 26

Relace

Algoritmy pro relace Vytvoříme několik funkcí realizujících operace s relacemi. Funkce relDomain[R] určí definiční obor relace R. Funkce relRange[R] určí obor hodnot relace R. Funkce relVal[x,R] vrací množinu prvků y, které jsou v relaci R s prvkem x (tj. xRy). Funkce relInv[y,R] vrací množinu prvků x, které jsou v relaci R s prvkem y (tj. xRy). relDomain[R_] := DeleteDuplicates[Map[First, R]]] relRange[R_] := DeleteDuplicates[Map[secnd, R]] secnd[{a_, b_}] := b; relVal[x_, R_] := Map[secnd, Select[R, Function[pair, x === First[pair]]]]; relInv[y_, R_] := Map[First, Select[R, Function[pair, x === secnd[pair]]]];


Binární relace


8 / 26

Relace

Inverzní relace Definice 8 ( inverzní relace) Nechť hR, X, Y i je binární inverzní

relace. Potom relací k této relaci rozumíme binární relaci R−1 , Y, X , kde R−1 = {(y, x); (x, y) ∈ R} Z definice přímo plynou následující vztahy: D(R−1 ) = H(R), H(R−1 ) = D(R), (R−1 )−1 = R

Příklad 9 Jak se od R přejde k reprezentaci inverzní relace R−1 ? výčet překlopených uspořádaných dvojic diagram relace, kartézské vyjádření, tabulka / matice Je inverzní relací k uspořádání podle velikosti ≤ na množině celých čísel Z relace > nebo ≥? doc. Josef Kolář (FIT ČVUT)

Binární relace


9 / 26

Relace

Složení relací Definice 10 ( složení relací) Nechť hR, X, Y i a hS, Y, Zi jsou binární relace. Potom binární relaci hR ◦ S, X, Zi definovanou předpisem x(R ◦ S)z ⇔df ∃y ∈ Y (xRy ∧ ySz) nazýváme složením (součinem) relací R a S. Poznámka: Operátor ◦ při zápisu složení relací často vynecháváme. OBRÁZEK

Složení relací není komutativní (proč?).

Věta 11 Složení binárních relací je asociativní, tzn. jsou-li hR, X, Y i , hS, Y, Zi a hT, Z, V i binární relace, pak platí (R ◦ S) ◦ T = R ◦ (S ◦ T ). doc. Josef Kolář (FIT ČVUT)

Binární relace


10 / 26

Relace

Algoritmus složení relací Při vytvoření funkce relComp[R,S] postupujeme podle definice: probíráme všechny dvojice (x, y) ∈ R a pro každou z nich nalezneme všechny dvojice (y, z) ∈ S a pro každou z nich do složené relace R ◦ S vložíme dvojici (x, z). relComp[R_, S_] := Apply[Union, Map[Function[pair, oneElm[First[pair], secnd[pair], S]], R]]; oneElm[a_, b_, S_] := cartP[{a}, relVal[b, S]]; R2 = {{a, 1}, {a, 3}, {b, 2}, {c, 3}} S2 = {{1, z}, {1, v}, {2, v}, {2, x}, {3, x}, {3, z}} relComp[R2, S2] {{a, v}, {a, x}, {a, z}, {b, v}, {b, x}, {c, x}, {c, z}} doc. Josef Kolář (FIT ČVUT)

Binární relace


11 / 26

Relace

Vlastnosti složení relací Omezíme-li se na binární relace v množině X, pak můžeme skládat.

Věta 12 Nechť R, S, T jsou libovolné relace na množině X. Potom platí (R ∪ S) ◦ T

=

(R ◦ T ) ∪ (S ◦ T ),

(R ∪ S)−1

=

R−1 ∪ S −1 ,

(R ◦ S)−1

=

S −1 ◦ R−1

R⊆S

⇒ (R ◦ T ) ⊆ (S ◦ T )

První dva vztahy lze zobecnit na sjednocení libovolného systému relací. Otázka pro hloubavé: Platí první dva uvedené vztahy, pokud operaci sjednocení nahradíme průnikem? doc. Josef Kolář (FIT ČVUT)

Binární relace


12 / 26

Relace

Speciální relace Definice 13 Identická relace (diagonála) ∆X ⊆ X × X a prázdná relace OX ⊆ X × X na množině X jsou definována vztahy ∆X

= {(x, x); x ∈ X}

OX

= ∅

Identická, resp. prázdná relace hraje na množině relací roli jednotkového, resp. nulového prvku vůči operaci skládání, neboť platí ∆X ◦ R = R ◦ ∆X = R, OX ◦ R = R ◦ OX = OX pro libovolnou relaci R ⊆ X × X. doc. Josef Kolář (FIT ČVUT)

Binární relace


13 / 26

Relace

Mocnina a tranzitivní uzávěr relace Díky asociativnosti a existenci inverze má pro relaci R ⊆ X × X smysl zavést celočíselnou mocninu Rn pomocí vztahů  pro n = 0  ∆X R ◦ R ◦ · · · ◦ R (n-krát) pro n > 0 (1) Rn =  (R−n )−1 pro n < 0

Definice 14 Tranzitivní uzávěr R+ , resp. reflexivně-tranzitivní uzávěr R∗ relace R jsou definovány vztahy S S i 2 i 2 R+ = ∞ R∗ = ∞ i=1 R = R ∪ R ∪ · · · i=0 R = ∆X ∪ R ∪ R ∪ · · · R+ je nejmenší tranzitivní relace obsahující R R∗ je nejmenší reflexivní a tranzitivní relace obsahující R doc. Josef Kolář (FIT ČVUT)

Binární relace


14 / 26

Relace

K čemu je tranzitivní uzávěr Intuitivní přiblížení Mějme binární relaci R ⊆ X × X xRy: x je od y na jeden “krok” xR+ y: x je od y na libovolný počet “kroků”

Příklad 15 R ⊆ N × N : xRy ⇔df y = x + 1 (y následuje po x) xR+ y znamená, že y je větší než x xP y znamená, že osoba x je rodičem osoby y xP + y znamená, že osoba x je předkem osoby y xF y znamená, že osoba x je opravdu přítelem (přítelkyní) osoby y xF + y znamená, že osoba x je přítelem (přítelkyní) osoby na y Facebooku doc. Josef Kolář (FIT ČVUT)

Binární relace


15 / 26

Relace

Algoritmus tranzitivního uzávěru relace Při vytvoření funkce relTran[R] postupujeme takto: do tranzitivního uzávěru vložíme relaci R postupně počítáme mocniny relace R a přidáváme je do uzávěru skončíme tehdy, až mocnina do uzávěru nepřidá žádnou novou dvojici. relTran[R_] := relT[R, relComp[R, R], R]; relRec[R_, Rn_, Acc_] := If[subset[Rn, Acc], Acc, relRec[R, relComp[R, Rn], Union[Acc, Rn]]]; subset[{}, _] := True; subset[A_, B_] := If[MemberQ[B, First[A]], subset[Rest[A], B], False] RR = {{a, b}, {b, c}, {c, d}, {d, e}, {e, a}} relTran[RR] {{a,a},{a,b},{a,c},{a,d},{a,e},{b,a},{b,b},{b,c},{b,d},{b,e}, {c,a},{c,b},{c,c},{c,d},{c,e},{d,a},{d,b},{d,c},{d,d},{d,e}, {e,a},{e,b},{e,c},{e,d},{e,e}} doc. Josef Kolář (FIT ČVUT)

Binární relace


16 / 26

Relace

Tranzitivní uzávěr trochu jinak Pro relace na konečné množině by šlo stanovit koncovou počítanou mocninu jiným způsobem. Jak? Tranzitivní, resp. reflexivně-tranzitivní uzávěr je také možné definovat induktivně.

Induktivní definice uzávěrů xR+ y ⇔df xRy ∨ (∃z)(xRz ∧ zR+ y) xR∗ y ⇔df x = y ∨ (∃z)(xRz ∧ zR+ y) Jak tuhle definici převést do fungujícího programu? Je tu problém s neurčeným (hledaným) vhodným z - hodil by se např. Prolog. Analogie s hledáním cesty. doc. Josef Kolář (FIT ČVUT)

Binární relace


17 / 26

Relace

Vlastnosti binárních relací U binárních relací ná zajímají především následující vlastnosti (předpokládáme R ⊆ X × X): (RE) reflexivita:

xRx pro všechna x ∈ X

∆X ⊆ R

(SY) symetrie:

xRy ⇒ yRx

R−1 = R

(TR) tranzitivita:

xRy ∧ yRz ⇒ xRz

(R ◦ R) ⊆ R

(AN) antisymetrie: xRy ∧ yRx ⇒ x = y

(R ∩ R−1 ) ⊆ ∆X

(AS) asymetrie:

xRy ⇒ ¬yRx

R ∩ R−1 = OX

(IR) ireflexivita:

¬(xRx) pro všechna x ∈ X R ∩ ∆X = OX

Věta 16 ( vlastnosti inverzní relace) Má-li relace R na množině X některé z vlastností (RE) až (IR), pak tytéž vlastnosti má také inverzní relace R−1 . doc. Josef Kolář (FIT ČVUT)

Binární relace


18 / 26

Relace

Úpravy relací Jakou minimální úpravou zadané relace můžeme docílit toho, aby měla některou z požadovaných vlastností? Pro (RE), (SY) a (TR) musíme relaci vhodně doplnit, pro (AN), (AS) a (IR) z ní musíme naopak něco odebrat.

Věta 17 Nechť R je binární relace na množině X. Potom R ∪ ∆X je nejmenší reflexivní relace obsahující relaci R R ∪ R−1 je nejmenší symetrická relace obsahující relaci R R+ je nejmenší tranzitivní relace obsahující relaci R R − ∆X je největší ireflexivní relace obsažená v relaci R Jak budeme postupovat, abychom získali co největší antisymetrickou (resp. asymetrickou) relaci obsaženou v zadané relaci R? doc. Josef Kolář (FIT ČVUT)

Binární relace


19 / 26

12, Lekce 4

Recommend Documents