Rabu, 13 Januari 2010

Relasi A x A

Sebuah relasi A×A, yaitu relasi dari himpunan A kepada A sendiri, dapat memiliki sifat-sifat berikut:

  • Refleksif
  • Irefleksif
  • Simetrik
  • Anti-simetrik
  • Transitif

Kita menyebut relasi R dari A kepada A sebagai relasi R dalam A.

Relasi Refleksif

Sebuah relasi R dalam A disebut memiliki sifat refleksif, jika setiap elemen A berhubungan dengan dengan dirinya sendiri.

\forall_{a \in A}\quad (a,a) \in R

atau

\forall_{a \in A}\quad a R a

Contoh relasi yang memiliki sifat seperti ini adalah relasi “x selalu bersama y.”, dengan x dan y adalah anggota himpunan seluruh manusia. Jelas sekali bahwa setiap orang pasti selalu bersama dengan dirinya sendiri.

Relasi Irefleksif

Relasi R dalam A disebut memiliki sifat irefleksif, jika setiap elemen A tidak berhubungan dengan dirinya sendiri.

\forall_{a \in A}\quad (a,a) \notin R

atau

\forall_{a \in A}\quad \lnot(a R a)

Contoh relasi irefleksif adalah relasi “x mampu mencukur rambut y dengan rapi sempurna.”, dengan x dan y adalah setiap pemotong rambut. Diandaikan bahwa setiap orang hanya dapat mencukur rambut orang lain dengan rapi sempurna, maka relasi ini adalah irefleksif, karena tidak ada seorang tukang cukur a yang mampu mencukur rambutnya sendiri.

Contoh lain dalam himpunan bilangan bulat adalah, relasi <> adalah irefleksif.

Relasi Simetrik

Relasi R dalam A disebut memiliki sifat simetrik, jika setiap pasangan anggota A berhubungan satu sama lain. Dengan kata lain, jika a terhubung dengan b, maka b juga terhubung dengan a. Jadi terdapat hubungan timbal balik.

\forall_{a, b \in A}\quad (a,b) \in R \rightarrow (b,a) \in R

atau

\forall_{a, b \in A}\quad a R b \rightarrow b R a

Sebuah relasi “x + y genap” adalah relasi simetrik, karena untuk sembarang x dan y yang kita pilih, jika memenuhi relasi tersebut, maka dengan menukarkan nilai y dan x, relasi tersebut tetap dipenuhi. Misalnya untuk pasangan (5, 3) relasi tersebut dipenuhi, dan untuk (3, 5) juga.

Relasi Anti-simetrik

Jika setiap a dan b yang terhubung hanya terhubung salah satunya saja (dengan asumsi a dan b berlainan), maka relasi macam ini disebut relasi anti-simetrik.

\forall_{a, b \in A}\quad a \neq b \rightarrow ((a,b) \in R \rightarrow (b,a) \notin R)

atau

\forall_{a, b \in A}\quad a \neq b \rightarrow (a R b \rightarrow \lnot (b R a))

Dalam kebanyakan literatur biasanya ditulis sebagai kontraposisinya seperti di bawah ini. Keuntungan bentuk ini adalah tidak mengandung negasi, dan hanya mengandung satu implikasi.

\forall_{a, b \in A}\quad (a,b) \in R \wedge (b,a) \in R \rightarrow a=b

atau

\forall_{a, b \in A}\quad a R b \wedge b R a \rightarrow a=b

Relasi \leq bersifat anti-simetrik, karena 5 \leq 6 mengakibatkan \lnot (6 \leq 5). Demikian juga jika ada p dan q yang terhadap mereka berlaku p \leq q dan q \leq p berarti p = q.

Relasi Transitif

Sebuah (a,b) \in R \wedge (bin R \rightarrow (a,c) \in R atau

Gagal memparse (fungsi yang tidak diketahui\berhubungan): \forall<>\forall_{a, b, c \in A}\q_{a,relasi d b, dengac \in A}\quad a R''b'', dan b \wedge b R c \rightarrow a R c

Sebagai contoh, relasi dua transitif. Misalnya untuk 5, 6, dan 7, berlaku 5 <>

Relasi khusus

Relasi Ekivalen

Sebuah relasi disebut sebagai relasi ekivalen jika relasi tersebut bersifat:

  • Refleksif
  • Simetrik, dan
  • Transitif

Relasi ekuivalen memiliki hubungan erat dengan partisi, yang merupakan alasan mengapa partisi dari sebuah himpunan disebut kelas ekivalen atau kelas kesetaraan.

Orde Parsial

Orde parsial adalah relasi yang bersifat:

  • Refleksif
  • Anti-simetrik, dan
  • Transitif

Lihat pula

Tidak ada komentar:

Posting Komentar