Bilangan Biner

Sebelumnya sudah dibahas algoritma konversi bilangan desimal dan biner. Kemudian dibahas bahasa pemrograman pascal. Nah, apa hubungan nya kedua materi ini? Mari kita lihat pengertian algoritma yang diambil dari Wikipedia.

Dalam matematika dan komputasi, algoritma atau algoritme merupakan kumpulan perintah untuk menyelesaikan suatu masalah. Perintah-perintah ini dapat diterjemahkan secara bertahap dari awal hingga akhir. Masalah tersebut dapat berupa apa saja, dengan catatan untuk setiap masalah, ada kriteria kondisi awal yang harus dipenuhi sebelum menjalankan algoritma. Algoritma akan dapat selalu berakhir untuk semua kondisi awal yang memenuhi kriteria, dalam hal ini berbeda dengan heuristik. Algoritma sering mempunyai langkah pengulangan (iterasi) atau memerlukan keputusan (logika Boolean dan perbandingan) sampai tugasnya selesai.

Sudah paham apa hubungan algoritma dengan bahasa pemrograman pascal? Jika belum, mari kita bandingkan program konversi bilangan desimal ke biner yang ditulis dengan bahasa pascal, dengan algoritma nya.

Program Konversi Bilangan Desimal ke Biner dengan Pascal

Program Konversi Bilangan Biner ke Desimal dengan Pascal

Sudah ketemu apa hubungan nya algoritma dengan program pascal? Jadi, algoritma itu langkah-langkah membuat program nya. Nanti nya langkah-langkah itu yang diterjemahkan dengan bahasa pascal sehingga menjadi bahasa pascal yang bisa dijalankan.

Jika mau lancar membuat program pascal sebaiknya harus paham bagaimana cara menyusun algoritma yang tepat, sehingga akan lebih lancar dalam menyusun program pascal.

SISTEM BILANGAN BINER

Sistem bilangan biner atau sistem bilangan basis dua adalah sebuah sistem penulisan angka dengan menggunakan dua simbol yaitu 0 dan 1. Sistem bilangan biner modern ditemukan oleh Gottfried Wilhelm Leibniz pada abad ke-17. Sistem bilangan ini merupakan dasar dari semua sistem bilangan berbasis digital. Dari sistem biner, kita dapat mengkonversinya ke sistem bilangan Oktal atau Hexadesimal. Sistem ini juga dapat kita sebut dengan istilah bit, atau Binary Digit. Pengelompokan biner dalam komputer selalu berjumlah 8, dengan istilah 1 Byte/bita. Dalam istilah komputer, 1 Byte = 8 bit. Kode-kode rancang bangun komputer, seperti ASCII, American Standard Code for Information Interchange menggunakan sistem peng-kode-an 1 Byte.

2⁰=1

2¹=2

2²=4

2³=8

2⁴=16

2⁵=32

2⁶=64

dst

Perhitungan

Desimal	Biner (8 bit )
0	0000 0000
1	0000 0001
2	0000 0010
3	0000 0011
4	0000 0100
5	0000 0101
6	0000 0110
7	0000 0111
8	0000 1000
9	0000 1001
10	0000 1010
11	0000 1011
12	0000 1100
13	0000 1101
14	0000 1110
15	0000 1111
16	0001 0000

Perhitungan dalam biner mirip dengan menghitung dalam sistem bilangan lain. Dimulai dengan angka pertama, dan angka selanjutnya. Dalam sistem bilangan desimal, perhitungan mnggunakan angka 0 hingga 9, sedangkan dalam biner hanya menggunakan angka 0 dan 1.

contoh: mengubah bilangan desimal menjadi biner

desimal = 10.

berdasarkan referensi diatas yang mendekati bilangan 10 adalah 8 (2³), selanjutnya hasil pengurangan 10-8 = 2 (2¹). sehingga dapat dijabarkan seperti berikut

10 = (1 x 2³) + (0 x 2²) + (1 x 2¹) + (0 x 2⁰).

dari perhitungan di atas bilangan biner dari 10 adalah 1010

dapat juga dengan cara lain yaitu 10 : 2 = 5 sisa 0 (0 akan menjadi angka terakhir dalam bilangan biner), 5(hasil pembagian pertama) : 2 = 2 sisa 1 (1 akan menjadi angka kedua terakhir dalam bilangan biner), 2(hasil pembagian kedua): 2 = 1 sisa 0(0 akan menjadi angka ketiga terakhir dalam bilangan biner), 1 (hasil pembagian ketiga): 2 = 0 sisa 1 (1 akan menjadi angka pertama dalam bilangan biner) karena hasil bagi sudah 0 atau habis, sehingga bilangan biner dari 10 = 1010

atau dengan cara yang singkat

10:2=5(0),

5:2=2(1),

2:2=1(0),

1:2=0(1) sisa hasil bagi dibaca dari belakang menjadi 1010

POHON BINER

Definisi untuk pohon berakar

Jenis pohon biner

Definisi dalam teori graf

Sebuah pohon biner adalah grafik asiklis yang terhubung dimana setiap tingkatan dari sudut tidak lebih dari 3. Ini dapat ditunjukan bahwa dalam pohon biner manapun, terdapat persis dua atau lebih simpul dengan tingkat satu daripada yang terdapat dengan tingkat tiga, tetapi bisa terdapat angka apa saja dari simpul dengan tingkat dua. Sebuah pohon biner berakar merupakan sebuah grafik yang mempunyai satu dari sudutnya dengan tingkat tidak lebih dari dua sebagai akar.

Dengan akar yang dipilih, setiap sudut akan memiliki ayah khusus, dan diatas dua anak; bagaimanapun juga, sejauh ini terdapat keterbatasan informasi untuk membedakan antara anak kiri atau kanan. Jika kita membuang keperluan yg tak terkoneksi, membolehkan bermacam koneksi dalam komponen di gafik, kita memanggil struktur sebuah hutan .

Sebuah jalan lain untuk mendefinisikan pohon biner melalui definisi rekursif pada grafik langsung. Sebuah pohon biner dapat berarti:

Ini juga tidak menentujan susunan anak, tetapi memperbaiki akar tertentu.

Kombinatorik

Kelompok dari sepasang simpul dalam sebuah pohon dapat digambarkan sebagai pasangan dari aksara dalam tanda kurung. Oleh sebab itu, (a,b) menunjukan pohon biner dimana sub pohon kirinya adalah a sedangkan sub pohon kanannya adalah b. Benang dari tanda kurung yang seimbang mungkin dapat digunakan untuk menunjukan pohon biner pada umumnya. Himpunan dari semua benang yang mungkin yang terdiri dari keseluruhan tanda kurung yang seimbang dikenal sebagal bahasa Dyck.

Diketahui n+1 simpul, jumlah seluruh jalan dimana simpul tersebut dapat disusun kedalam sebuah pohon biner dengan sebuah bilangan Catalan $C_n$ . Sebagai contoh, $C_2=2$ adalah pernyataan bahwa (ab)c dan a(bc) merupakan dua pohon biner yang mungkin, yang memiliki 3 simpul.

Kemampuan untuk menggambarkan pohon biner sebagai benang dari simbol-simbol dan tanda kurung secara tidak langsung menyatakan bahwa pohon biner dapat mewakili elemen dari magma . Sebaliknya, himpunan dari semua pohon biner yang mungkin, bersama-sama dengan operasi natural memasangkan pohon dari satu ke yang lain, dari sebuah magma, magma bebas.

Memberikan benang yang menggambarkan sebuah pohon biner, operator untuk mendapatkan sub pohon kiri dan kanan kadang-kadang mengacu sebagai CAR dan CDR .

Metode untuk menyimpan pohon biner

Pohon biner dapat dikonstruksi dari bahasa pemrograman primitif dalam berbagai cara. Dalam bahasa yang menggunakan records dan referensi, pohon biner secara khas dikonstruksi dengan mengambil sebuah struktur simpul pohon yang memuat beberapa data dan referensi ke anak kiri dan anak kanan. Kadang-kadang itu juga memuat sebuah referensi ke ayahnya yang khas. Jika sebuah simpul mempunyai kurang dari dua anak, beberapa penunjuk anak dapat diatur kedalam nilai nol khusus, atau ke sebuah simpul sentinel.

Pohon biner dapat juga disimpan sebagai struktur data implisit dalam array, dan jika pohon tersebut merupakan sebuah pohon biner lengkap, metode ini tidak boros tempat. Dalam penyusunan yang rapat ini, jika sebuah simpul memiliki indeks i, anaknya dapat ditemukan pada indeks ke-2i+1 dan 2i+2, meskipun ayahnya (jika ada) ditemukan pada indeks lantai((i-1)/2) (asumsikan akarnya memiliki indeks kosong). Metode ini menguntungkan dari banyak penyimpanan yang rapat dan memiliki referensi lokal yang lebih baik, tersitimewa selama sebuah preorder traversal. Bagaimanapun juga, ini terlalu mahal untuk perkembangannya dan boros tempat sebanding dengan 2^h - n untuk sebuah pohon dengan tinggi h dengan nsimpul.

Dalam bahasa dengan tagged union seperti ML, sebuah simpul pohon seringkali sebuah tagged union dari dua jenis simpul, dimana yang satu merupakan data dari 3-tupel, anak kiri, dan anak kanan, dan yang lain dimana sebuah daun, yang tidak memuat data dan fungsi seperti nilai nol dalam bahasa dengan penunjuk (pointers)

Metode iterasi pohon biner

Seringkali, seseorang berkeinginan untuk mengunjungi simpul dalam pohon dan menjalankan perintahnya disana. Terdapat beberapa penyusunan umum dimana simpul-simpuk tersebut dapat dikunjungi, dan setiap simpul memiliki sifat-sifat yang berguna yang dimanfaatkan dalam algoritma yang berdasarkan pada pohon biner.

Penyandian

Penyandian ringkas

Sebuah struktur data ringkas adalah sesuatu yang mengambil tempat minimum mutlak yang mungkin, yang berdiri sebagai teori informasi bawah. Jumlah dari pohon biner yang berbeda pada $n$ simpul adalah $\mathrm{C}_{n}$ , Bilangan Catalan ke- $n$ (asumsikan kita melihat pohon dengan struktur yang identik sebagai sebuah kesamaan). Untuk besarnya $n$ , ini berkisar kira-kira $4^{n}$ ; sehingga kita membutuhkan setidaknya kira-kira $\log_{2}4^{n} = 2n$ bit untuk menyalinnya. Oleh sebab itu sebuah pohon biner ringkas hanya membutuhkan 2 bit setiap simpul.

Salah satu penggambaran sederhana yang masih berhubungan dengan ini adalah mengunjungi simpul dari pohon dengan preoder, meletakkan "1" untuk sebuah simpul dalan dan "0" untuk sebuah daun. [1] Jika pohon ini memuat data, kita dapat menyimpanya secara serempak dalam sebuah array yang berurutan dengan preoder. Fungsi ini memenuhi:

function EncodeSuccinct(node n, bitstring structure, array data) {
    if n = nil then
        append 0 to structure;
    else
        append 1 to structure;
        append n.data to data;
        EncodeSuccinct(n.left, structure, data);
        EncodeSuccinct(n.right, structure, data);
}

String structure hanya memiliki $2n + 1$ bit pada bagian akhir, dimana $n$ adalah angka dari simpul dalam; kita bahkan tidak memerlukan untuk menyimpan panjangnya. Untuk menunjukkan bahwa tidak ada informasi yang hilang, kita dapat mengubah hasilnya kembali seperti pohon aslinya seperti ini:

function DecodeSuccinct(bitstring structure, array data) {
    remove first bit of structure and put it in b
    if b = 1 then
        create a new node n
        remove first element of data and put it in n.data
        n.left = DecodeSuccinct(structure, data)
        n.right = DecodeSuccinct(structure, data)
        return n
    else
        return nil
}

Penggambaran secara ringkas dan rumit memungkinkan tidak hanya penyimpanan yang rapi pada pohon tetapi bahkan operasi yang berguna secara langsung pada pohon tersebut, meskipun mereka masih dalam bentuk yang ringkas.

Penyandian pohon n-er sebagai pohon biner

Terdapat sebuah pemetaan satu-satu antara pohon terurut general dan pohon biner, yang biasanya digunakan oleh Lisp untuk menggambarkan pohon terurut general sebagai pohon biner. Setiap simpul N dalam pohon terurut terhubung ke sebuah simpul N dalam pohon biner; anak kiri dari N merupakan simpul yang terhubung ke anak pertama dari N, dan anak kanan dari N merupakan simpul yang terhubung ke saudara selanjutnya dari N yang merupakan simpul selanjutnya dalam urutan di antara anak-anaknya dari ayahnya N

Suatu cara untuk menyelesaikan ini adalah bahwa setiap anak simpul berada dalam sebuah linked list , dihubungkan bersama dengan bidang kanan mereka, dan simpul yang hanya memiliki sebuah petunjuk ke awalnya atau kepala dari daftar ini, melalui bidang kiri nya.

Sebagai contoh, dalam sebuah pohon bagian kirinya, A memiliki 6 anak {B,C,D,E,F,G}. Ini dapat diubah manjadi sebuah pohon biner bagian kanan.

Sebuah contoh mengubah sebuah pohon n-er menjadi sebuah pohon biner

Pohon biner dapat dianggap sebagai pohon asli yang membujur kesamping, dengan tepi kirinya yang berwarna hitam menggambarkan anak pertama dan tepi kanannya yang berwarna biru menggambarkan saudara selanjutnya. Daun dari bagian kiri pohon ini dapat dituliskan dalam Lips sebagai:

(((M N) H I) C D ((O) (P)) F (L))

yang akan diimplementasikan ke memori sebagai pohon biner kanan, tanpa huruf apapun pada simpul itu yang telah memiliki anak.

PENCARIAN BINER

Algoritma

Penerapan terbanyak dari pencarian biner adalah untuk mencari sebuah nilai tertentu dalam sebuah list terurut . Jika dibayangkan, pencarian biner dapat dilihat sebagai sebuah permainan tebak-tebakan, kita menebak sebuah bilangan, atau nomor tempat, dari daftar (list) nilai.

Pencarian diawali dengan memeriksa nilai yang ada pada posisi tengah list; oleh karena nilai-nilainya terurut, kita mengetahui apakah nilai terletak sebelum atau sesudah nilai yang di tengah tersebut, dan pencarian selanjutnya dilakukan terhadap setengah bagian dengan cara yang sama. Berikut ini adalah pseudocode sederhana yang menentukan indeks (posisi) dari nilai yang diberikan dalam sebuah list berurut, a berada antara left dan right :

function binarySearch(a, value, left, right)
    if right < left
        return not found
    mid := floor((right-left)/2)+left
    if a[mid] = value
        return mid
    if value < a[mid]
        return binarySearch(a, value, left, mid-1)
    else
        return binarySearch(a, value, mid+1, right)

Karena pemanggilan fungsi di atas adalah rekursif ekor , fungsi tersebut dapat dituliskan sebagai sebuah pengulangan (loop), hasilnya adalah algoritma in-place:

function binarySearch(a, value, left, right)
    while left ≤ right
        mid := floor((right-left)/2)+left
        if a[mid] = value
            return mid
        if value < a[mid]
            right := mid-1
        else
            left  := mid+1
    return not found

Pada kedua kasus, algoritma akan berakhir karena paa setiap pemanggilan rekursif atau pengulangan, jangkauan indeks right dikurang left akan selalu mengecil, dan akhirnya pasti akan menjadi negatif.

Pencarian biner adalah sebuah algoritma logaritmik dan bekerja dalam waktu O(log n). Secara khusus, $1 + log_2N$ pengulangan yang diperlukan untuk menghasilkan jawaban. Hal ini dianggap lebih cepat dibandingkan sebuah pencarian linear. Pencarian biner dapat diimplementasikan dengan rekursi atau iterasi, seperti yang terlihat di atas, walaupun pada kebanyakan bahasa pemrograman akan lebih elegan bila dinyatakan secara rekursif.

Contoh

Sebuah contoh aksi pencarian biner adalah sebuah permainan tebak-tebakan dimana seorang pemain harus menebak sebuah bilangan bulat positif yang dipilih oleh pemain lain di antara 1 dan N, dengan memanfaatkan jawaban pertanyaan berupa ya dan tidak. Misalnya N adalah 16 dan angka yang dipilih adalah 11, permainan dapat berjalan sebagai berikut.

Sehingga, angka tersebut pasti 11. Pada setiap langkah, kita memilih sebuah angka yang tepat berada di tengah-tengah jangkauan nilai-nilai yang mungkin. Sebagai contoh, saat kita mengetahui angka tersebut lebih besar dari 8, tetapi lebih kecil atau sama dengan 12, kita mengetahui untuk memilih angka di tengah-tengah jangkauan [9, 12] (pada kasus ini 10 adalah yang optimal).

Paling banyak ada $\lceil\log_2 N\rceil$ pertanyaan yang dibutuhkan untuk mendapatkan angka tersebut, karena setiap pertanyaan menghilangkan setengah dari ruang pencarian. Sebagai catatan bahwa dibutuhkan kurang dari satu pertanyaan (iterasi) untuk algoritma umum, karena angka tersebut dibatasi oleh sebuah jangkauan tertentu.

Walaupun angka yang kita tebak sangat banyak, pada kasus tidak ada batas atas N, kita masih dapat menemukan angka paling banyak dalam $2\lceil \log_2 k \rceil$ langkah (dimana k adalah angka yang dipilih (yang tidak diketahui)), caranya adalah dengan pertama-tama menemukan sebuah batas atas dengan melipatduakannya. Sebaai contoh, jika angka tersebut adalah 11, kita dapat menggunakan urutan tebakan sebagai berikut untuk menemukannya:

(Kita mengetahui angka tersebut lebih besar dari 8)

Satu penerapan sederhan, pada sistem kendali revisi , dimungkinkan memanfaatkan sebuah pencarian biner untuk melihat pada revisi mana sebuah cuplikan isi ditambahkan ke sebuah file. Dengan mudah kita lakukan sebuah pencarian biner terhadap seluruh history versi; jika isi tidak ada dalam suatu versi, suatu saat kemudian pasti akan muncul, dan jika ada pasti muncul di versi tersebut atau versi berikutnya. Cara ini lebih cepat dibandingkan dengan memeriksa setiap perbedaan antar versi.

Ada beberapa hal yang tidak terkait dengan komputer dimana sebuah pemilahan biner adalah cara tercepat untuk mengisolasi sebuah solusi yang dicari. Pada pemecahan sebuah permasalah dengan banyak kemungkinan penyebab, kita dapat mengubah setengah sangkaan, kita lihat apakah permasalahan masih terjadi dan tentukan bagian setengah berikutnya; ubah setengah sangkaan sisanya, dan seterusnya.

Contoh nyata lainnya: pada satu revisi di antara 500 revisi terakhir, sebuah paragraf penting terhapus dari sebuah artikel Wikipedia—pertanyaanya di revisi mana? Kita menghadapai paling banyak 500 opersi pembandingan, atau 9 pembandingan dengan pemilahan biner (2 pangkat 9, yaitu 512).

Penerapan pada teori kompleksitas

Seandainya kita tidak mengetahui sebuah jangkauan yang tetap tempat dari bilangan kberada, kita masih dapat menentukan nilainya dengan mengajukan $2\lceil\log_2k\rceil$ pertanyaan ya/tidak dalam bentuk "Apakah k lebih besar dari x?" untuk beberapa bilangan x. Sebagai konsekuensi sederhana dari cara ini, jika kita dapat menjawab pertanyaan "Apakah nilai bilangan bulat k lebih besar dari nilai yang diberikan?" pada suatu waktu kemudian kita dapat menemukan nilai dari bilangan tersebut sama lamanya ditambah dengan faktor log k. Hal ini disebut sebuah reduksi, dan karena disebabkan reduksi ini maka kebanyakan teoris kompleksitas berkonsentrasi pada permasalahan keputusan, algoritma-algoritma yang mengasihlan jawaban sederhana berupa ya/tidak.

Sebagai contoh, anggap kita dapat menjawab "Apakah matriks n x n ini memiliki determinan lebih besar dari k?" dalam waktu O(n²). Kemudian, dengan memanfaatkan pencarian biner, kita dapat menemukan (batas atas) determinan tersebut dalam waktu O(n²log d), dimana d adalah determinan; sebagai catatan, d bukanlah ukuran dari masukan tetapi ukuran dari keluaran.

RELASI BINER

Definisi

Jika terdapat himpunan A dan himpunan B (A bisa sama dengan B), maka relasi R dari A ke B adalah subhimpunan dari A×B.

Relasi dan fungsi proposisi

Sebuah relasi dapat dikaitkan dengan sebuah fungsi proposisi atau kalimat terbuka yang himpunan penyelesaiannya tidak lain adalah relasi tersebut.

Sebagai contoh, pandang himpunan B = { apel, jeruk, mangga, pisang } dengan himpunan W = { hijau, kuning, orange}. Suatu relasi R dari A ke B didefinisikan sebagai R = {(apel, hijau), (jeruk, orange), (mangga, hijau), (pisang, kuning)}. Terdapat fungsi proposisi w(x, y) = "x berwarna y", yang himpunan penyelesaiannya adalah {(apel, hijau), (jeruk, orange), (mangga, hijau), (pisang, kuning)}, yang tidak lain adalah relasi R.

Relasi A×A

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

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 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 < dan > 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 relasi disebut transitif jika memiliki sifat, jika a berhubungan dengan b, dan b berhubungan dengan c, maka a berhubungan dengan c secara langsung.

$(a,b) \in R \wedge (b,c) \in R \rightarrow (a,c) \in R$

atau

$\forall_{a, b, c \in A} {a R b \wedge b R c \rightarrow a R c}$

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

Relasi khusus

Relasi Ekivalen

Sebuah relasi disebut sebagai relasi ekivalen jika relasi tersebut bersifat:

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

$R_{AB} \subseteq A \times B$ Orde Parsial

$R_{AB} \subseteq A \times B$ Orde parsial adalah relasi yang bersifat:

$R_{AB} \subseteq A \times B$

KONVERSI BILANGAN BINER

Didalam dunia komputer kita mengenal empat jenis bilangan, yaitu bilang biner , oktal, desimal dan hexadesimal. Bilangan biner atau binary digit (bit) adalah bilangan yang terdiri dari 1 dan 0. Bilangan oktal terdiri dari 0,1,2,3,4,5,6 dan 7. Sedangkan bilangan desimal terdiri dari 0,1,2,3,4,5,6,7,8 dan 9. Dan bilangan hexadesimal terdiri dari 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E dan F.

Biner	Oktal	Desimal	Hexadesimal
0000	0	0	0
0001	1	1	1
0010	2	2	2
0011	3	3	3
0100	4	4	4
0101	5	5	5
0110	6	6	6
0111	7	7	7
1000	10	8	8
1001	11	9	9
1010	12	10	A
1011	13	11	B
1100	14	12	C
1101	15	13	D
1110	16	14	E
1111	17	15	F

Konversi Antar Basis Bilangan
Sudah dikenal, dalam bahasa komputer terdapat empat basis bilangan. Keempat bilangan itu adalah biner, oktal, desimal dan hexadesimal. Keempat bilangan itu saling berkaitan satu sama lain. Rumus atau cara mencarinya cukup mudah untuk dipelajari. Konversi dari desimal ke non-desimal, hanya mencari sisa pembagiannya saja. Dan konversi dari non-desimal ke desimal adalah:
1. Mengalikan bilangan dengan angka basis bilangannya.
2. Setiap angka yang bernilai satuan, dihitung dengan pangkat NOL (0). Digit puluhan, dengan pangkat SATU (1), begitu pula dengan digit ratusan, ribuan, dan seterusnya. Nilai pangkat selalu bertambah satu point.

Konversi Biner ke Oktal

Metode konversinya hampir sama. Cuma, karena pengelompokkannya berdasarkan 3 bit saja, maka hasilnya adalah: 1010 ₍₂₎ = ...... ₍₈₎ Solusi: Ambil tiga digit terbelakang dahulu. 010₍₂₎ = 2₍₈₎ Sedangkan sisa satu digit terakhir, tetap bernilai 1. Hasil akhirnya adalah: 12.

Konversi Biner ke Hexadesimal

Metode konversinya hampir sama dengan Biner ke Oktal. Namun pengelompokkannya sejumlah 4 bit. Empat kelompok bit paling kanan adalah posisi satuan, empat bit kedua dari kanan adalah puluhan, dan seterusnya. Contoh: 11100011₍₂₎ = ...... ₍₁₆₎ Solusi: kelompok bit paling kanan: 0011 = 3 kelompok bit berikutnya: 1110 = E Hasil konversinya adalah: E3₍₁₆₎