11
•
Relasi
simetrik
Sebuah
relasi
R
pada
A
disebut
simetrik
jika
untuk
setiap
a,
b
?
A, jika
(a, b) ? R, maka (b, a) ? R juga.
•
Relasi
antisimetrik
Sebuah relasi R pada A disebut antisimetrik jika
untuk setiap a, b ? A, jika
(a,
b) ? R,
maka (b,
a)
?
R
hanya berlaku
jika a=b.
Produksi tata bahasa
haruslah
bersifat
antisimetrik
karena
jika
tidak
maka
dapat
terjadi
suatu
nonterminal diuraikan dan direduksi kembali.
•
Relasi
transitif
Sebuah
relasi
R
pada
A
disebut
transitif
jika
untuk setiap
a,
b, c ? A, jika
berlaku
(a,
b)
?
R
dan
(b,
c)
?
R,
maka
haruslah
berlaku
(a,
c)
?
R.
Contoh relasi transitif adalah relasi < dan > pada bilangan bulat, juga relasi
reduksi string oleh sebuah tata bahasa.
•
Relasi
ekivalen
Suatu
relasi
disebut
relasi ekivalen jika
relasi
tersebut
memiliki gabungan
sifat
refleksif,
simetrik, dan
transitif.
Contoh
dari
relasi
ekivalen
adalah
relasi = pada persamaan aljabar.
2.1.5 Penutup (closure)
Misalkan P adalah sebuah himpunan sifat-sifat relasi. Jika R* adalah penutup-P
(P – closure) dari relasi R, maka R* ? R, dan R* memiliki sifat-sifat P.
Sebagai contoh, terdapat relasi # sedemikian hingga:
 |