MATEMATIKA DISKRIT

MACAM-MACAM RELASI dan SIFAT-SIFAT RELASI

I.         Relasi Biner

Adalah hasil kali 2 himpunan atau relasi yang menghubungkan 2 himpunan yang himpunan bagianya tidak kosong.

Sifat-sifat relasi Biner

a.       Reflektif

Suatu relasi bersifat reflektif , jika setiap x є A, maka (A,A) є R

Contoh :

1.      B = {1,2,3} dan R = {(x,y)│x,y є B, xy > 0}

Periksa apakah R reflektif atau tidak

Peny :

B x B = {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,3) dari hasil kali Cartesian kita memperoleh R = {(1,1),(2,2),(3,3)}. Karena semua hasil xy > 0 dan x є B, maka R adalah relasi yang reflektif.

2.      A = {-1,0,1} dan R = {(x,y)│x,y є A, xy > 0}

Periksa apakah R reflektif atau tidak

b.      Simetris

Suatu relasi bersifat simetrik, jika untuk setiap x,y є A dengan xRy dan yRx

Contoh

1.      M = {-2,-1,0,1,2} dan R = {(x,y) │x,y є M,  xy > 0}

Periksa apakah R simetris atau tidak

Peny :

M x M = {(-2,-2), (-2,-1), (-2,0), (-2,1), (-2,2), (-1,-2),(-1,-1),(-1,0),(-1,1),(-1,2)

                 (0,-2), (0,-1), (0,0), (0,1), (0,2), (1,-2), (1,-1), (1,0), (1,1), (1,2),(2,-2)

                 (2,-1), (2,0), (2,1), (2,2)}, dari hasil kali Cartesian kita memperoleh

R = {(-2,-2), (-2,-1), (-1,-2), (-1,-1), (1,1), (1,2), (2,2)}

Dari sini jelas terlihat bahwa untuk setiap (x,y) є R berlaku (y,x) є R dengan x,y є M. Jadi R adalah sebuah relasi yang simetris.

2.      B = {-2,-1,0,1,2} dan R = {(x,y) │x,y є B,  x ≤ y }

Periksa apakah R simetris atau tidak

c.       Antisimetris

Suatu Relasi bersifat antisimetris, jika untuk setiap x,y є A dengan xRy dan yRx maka x = y.

Contoh :

1.      A  = {-2,-1,0,1,2} dan R = {(x,y) │x,y є A,  y = │x }

Periksa apakah R antisimetris atau tidak

Peny :

M x M = {(-2,-2), (-2,-1), (-2,0), (-2,1), (-2,2), (-1,-2),(-1,-1),(-1,0),(-1,1),(-1,2)

                 (0,-2), (0,-1), (0,0), (0,1), (0,2), (1,-2), (1,-1), (1,0), (1,1), (1,2),(2,-2)

                 (2,-1), (2,0), (2,1), (2,2)}, dari hasil kali Cartesian kita memperoleh

R = {(-2,2),(-1,1),(1,1),(0,0),(2,2)}

Dari sini jelas terlihat bahwa untuk setiap (x,y) є R berlaku (y,x) є R dengan x,y є A. Jadi R adalah sebuah relasi yang antisimetris.

2.      G = {B,A,M} dan R = {(B,A), (A,B), (B,M), (M,B), (A,M)}

Periksa apakah R antisimetris atau tidak

d.      Transitif

Suatu Relasi bersifat transitif, jika setiap x,y,z є A dengan xRy, yRz, dan xRz

Contoh :

1.      A = {-1,0,1} dan R = {(x,y) │x,y є A, x ≥ y}

Periksa apakah R transitif atau tidak

Peny :

A x A = {(-1,-1), (-1,0), (-1,1), (0,-1), (0,0), (0,1), (1,-1), (1,0), (1,1)} dari hasil kali Cartesian kita memperoleh,

R = {(-1,-1), (-1,0), (-1,1), (0,0), (0,1), (1,1)}

Dari sini jelas terlihat bahwa untuk setiap (x,y,z є A) dengan xRy dan yRz, berlaku xRz

2.      N = {G,U,T} dan R = {(G,U), (T,U), (U,G), (G,T)

Periksa apakah R transitif atau tidak

II.      Relasi Ekivalen

Adalah relasi yang memenuhi 3sifat relasi yaitu reflektif, simetris dan transitif.

Contoh :

1.      B = {a,b,c,d} dan R = {(a,a),(a,b),(b,a),(b,b),(c,c),(c,d),(d,c),(d,d)}

Periksa apakah R ekivalen atau tidak

Peny :

·         Reflektif    : {(a,a),(b,b),(c,c),(d,d)}, ya reflektif karena x є B berlaku (x,x) є R

·         Simetris     :  Karena untuk setiap x,y є B dengan xRy berlaku yRx, maka R simetris.

   Contoh : {(a,b),(b,a)}

·          Transitif    : {(a,b),(b,a),(a,a)}, karena x,y,z є B dengan xRy dan yRz berlaku xRz,

   Maka R adalah relasi yang transitif.

Karena tiga sifat diatas yaitu reflektif, simetrik dan transitif dipenuhi maka kita dapat simpulkan bahwa R adalah relasi ekivalen.

III.   Relasi tolak parsial (poset)

Adalah relasi yang memenuhi 3 sifat relasi yaitu reflektif, transitif dan antisimetris.

Contoh :

A = {1,2,3,4} dan R = {(x,y) │x,y є A dan x ≤ y}

Periksa apakah R poset atau tidak