Binarne relacije: razlika između inačica
Nema sažetka uređivanja |
Nema sažetka uređivanja |
||
Redak 3: | Redak 3: | ||
Primjer: |
Primjer: |
||
Neka je S neprazan skup, <math>S</math> = {1,2,3,4}, Kartezijev produkt |
Neka je S neprazan skup, <math>S</math> = {1,2,3,4}, Kartezijev produkt čskupa S sa samim sobom je: |
||
<math>SxS</math> = {{1,1},{1,2},{1,3},{1,4},{2,1},{2,2},{2,3},{2,4},{3,1},{3,2},{3,3},{3,4},{4,1},{4,2},{4,3},{4,4}} |
<math>SxS</math> = {{1,1},{1,2},{1,3},{1,4},{2,1},{2,2},{2,3},{2,4},{3,1},{3,2},{3,3},{3,4},{4,1},{4,2},{4,3},{4,4}} |
||
Binarna relacija <math><</math> (manji od) na skupu SxS je onaj podskup skupa SxS za kojeg vrijedi da je <math>x \mathcal{R} y</math>, tj. u ovom primjeru x<y: |
Binarna relacija <math><</math> (manji od) na skupu SxS je onaj podskup skupa SxS za kojeg vrijedi da je <math>x \mathcal{R} y</math>, tj. u ovom primjeru x<y: |
Inačica od 18. travnja 2017. u 19:47
Binarna relacija na skupu je svaki podskup (podskup Kartezijevog produkta skupa sa samim sobom). Ako je uređeni par onda kažemo da je u relaciji s , i pišemo ili .
Primjer:
Neka je S neprazan skup, = {1,2,3,4}, Kartezijev produkt čskupa S sa samim sobom je:
= {{1,1},{1,2},{1,3},{1,4},{2,1},{2,2},{2,3},{2,4},{3,1},{3,2},{3,3},{3,4},{4,1},{4,2},{4,3},{4,4}}
Binarna relacija (manji od) na skupu SxS je onaj podskup skupa SxS za kojeg vrijedi da je , tj. u ovom primjeru x<y:
= {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}
Ova relacija nije refleksivna jer za niti jedan uređeni par ne vrijedi da je x<x (x manji od samog sebe), npr. da bi relacija bila refleksivna za (1,2) trebao bi postojati element skupa oblika (1,1).
Također nije simetrična jer za niti jedan uređeni par ne vrijedi da je y<x, ako vrijedi da je x<y npr. ne postoji element za (2,3) oblika (3,2)
Ova relacija je tranzitivna jer za x<y i y<z vrijedi da je x<z npr. za (1,2) i (2,3) postoji element (1,3)
Nije antisimetrična jer ne vrijedi x<y i y<x iz čega bi slijedilo da je x=y.
Binarna relacija može biti:
- refleksivna: ako je (svaki element je u relaciji sam sa sobom);
- simetrična: ako (ako je u relaciji sa onda i mora biti u relaciji sa );
- tranzitivna: ako (ako je u relaciji sa , i u relaciji sa onda je i u relaciji sa );
- antisimetrična: ako (ako je u relaciji sa i u relaciji sa , onda je ;
Relacija ekvivalencije
Binarna relacija je relacije ekvivalencije, ako je refleksivna, simetrična i tranzitivna.
Parcijalni uređaj i totalni uređaj
Binarna relacija je parcijalni uređaj, ako je refleksivna, antisimetrična i tranzitivna.
Ako dodatno vrijedi i , , za relaciju kažemo da je totalni uređaj.