Boolean Algebra

Definisi Aljabar Boolean

Aljabar  Boolean merupakan salah satu cabang ilmu matematika yang pertama kali dikemukanan oleh seorang matematikawan Inggris yang bernama  George Boole pada tahun 1854. Aljabar  Boolean  dapat didefinisikan secara  abstrak dalam beberapa cara. Cara yang paling umum adalah  dengan menspesifikasikan unsur–unsur  pembentuknya dan operasi–operasi yang menyertainya [Rinaldi Munir, 2005, p282].

Misalkan B adalah himpunan yang didefinisikan pada dua operator biner, + dan ., dan sebuah operator uner,’. Misalkan 0 dan 1 adalah dua elemen yang berbeda dari B. Maka, tupel <B, +, ., ‘, 0, 1> disebut aljabar  Boolean jika untuk setiap  a,  b,  c 0 B berlaku aksioma (sering dinamakan juga postulat Huntington) berikut :

1. Identitas       

(i) a + 0 = a

(ii) a . 1 = a

2. Komutatif

(i) a + b = b + a

(ii) a . b = b . a

3. Distributif

(i) a . (b + c) = (a . b) + (a . c)

(ii) a + (b . c) = (a + b) . (a + c)

4. Komplemen

     Untuk setiap a € B terdapat elemen unik a’ € B sehingga

(i) a + a’ = 1

(ii) a . a’ = 0

Aljabar Boolean Dua-Nilai

Aljabar  Boolean yang terkenal dan memiliki terapan yang luas adalah aljabar Boolean dua-nilai (two-valued Boolean algebra). Aljabar  Boolean dua-nilai didefinisikan pada sebuah himpunan  B dengan dua buah elemen 0 dan 1 (sering dinamakan bit – singkatan dari binary digit), yaitu B = {0, 1}, operator biner, + dan . operator uner, ‘ [Rinaldi Munir, 2005, p285].

Kaidah untuk operator biner dan operator uner ditunjukkan pada Tabel 2.1, 2.2, dan 2.3 di bawah ini.

Harus diperhatikan bahwa keempat aksioma di dalam definisi 2.1 terpenuhi pada himpunan  B = {0, 1} dengan dua operator biner dan satu operator uner yang didefinisikan di atas.

1. Identitas:   jelas berlaku karena dari tabel:

(i) 0 + 1 = 1 + 0 = 1

(ii) 1 . 0 = 0 . 1 = 0

yang memenuhi elemen identitas 0 dan  1 seperti yang didefinisikan pada postulat Huntington.

2. Komutatif :   jelas berlaku dengan melihat simetri tabel operator biner.

3. Distributif :

(i) a . (b + c) = (a . b) + (a . c) dapat ditunjukkan benar dari tabel operator biner di atas, dengan membentuk tabel kebenaran untuk semua nilai yang mungkin dari a, b, dan c (Tabel 7.4). Oleh karena nilai–nilai pada kolom a. (b +  c) sama dengan nilai – nilai pada kolom (a .  b) + (a .  c), maka kesamaan a . (b + c) = (a . b) + (a . c) adalah benar.

(ii) Hukum distributif a + (b . c) = (a + b) . (a + c) dapat ditunjukkan benar dengan membuat tabel kebenaran dengan cara yang sama seperti (i).

4. Komplemen : jelas berlaku karena Tabel 2.4 memperlihatkan bahwa :

(i) a + a’ = 1, karena 0 + 0’ = 0 + 1 = 1 dan 1 + 1’ = 1 + 0 = 1

(ii) a . a = 0, karena 0 . 0’ = 0 . 1 dan 1 . 1’ = 1 . 0 = 0

Karena keempat aksioma terpenuhi, maka terbukti bahwa B = {0 , 1} bersama– sama dengan operator biner + dan ., operator komplemen ‘ merupakan aljabar Boolean. Untuk selanjutnya, jika disebut aljabar  Boolean, maka aljabar  Boolean yang dimaksudkan di sini adalah aljabar Boolean dua-nilai.

Ekspresi Boolean

Pada aljabar  Boolean dua-nilai,  B = {0, 1}. Kedua elemen  B ini seringkali disebut elemen biner atau bit (singkatan binary bit). Peubah (variable) x disebut peubah Boolean atau peubah biner jika nilainya hanya dari B. Ekspresi Boolean dibentuk dari elemen–elemen B dan/atau peubah–peubah yang dapat dikombinasikan satu sama lain dengan operator +, ., dan ‘ [Rinaldi Munir, 2005, p286]. Secara formal, ekspresi Boolean dapat didefinisikan secara rekursif sebagai berikut.

        Misalkan (B, +, ., ‘, 0, 1) adalah sebuah aljabar Boolean. Suatu ekspresi Booleandalam (B, +, ., ‘) adalah:

(i) Setiap elemen di dalam B,

(ii) setiap peubah,

(iii) jika e1 dan e2 adalah ekspresi Boolean, maka e1 + e2, e1 . e2, e1’ adalah ekspresi Boolean.

Jadi menurut definisi di atas, setiap ekspresi di bawah ini,

 0

1

a

b

c

a + b

a . b

a’ . (b + c)

a . b’ + a . b . c + b’, dan sebagainya

adalah ekspresi  Boolean. Ekspresi  Boolean yang mengandung  n peubah dinamakan ekspresi Boolean bagi n peubah [Rinaldi Munir, 2005, p287].

        Dalam penulisan ekspresi  Boolean selanjutnya, digunakan  perjanjian berikut: tanda kurung ‘()’ mempunyai prioritas pengerjaan paling tinggi, kemudian diikuti dengan operator ‘, + dan ·. Sebagai contoh, ekspresi a + b . c berarti a + (b . c), bukan  (a+ b) . c dan ekspresi a . b’ berarti a . (b’), bukan (a . b)’.

Prinsip Dualitas

Di dalam aljabar  Boolean, banyak ditemukan kesamaan (identity) yang dapat diperoleh dari kesamaan lainnya, misalnya pada dua aksioma distributif yang sudah disebutkan pada definisi aljabar Boolean sebelumnya:

(i) a . (b + c) = (a . b) + (a . c)

(ii) a + (b . c) = (a + b) . (a + c)

Aksioma yang kedua diperoleh dari aksioma pertama dengan cara mengganti · dengan + dan mengganti + dengan ·. Prinsip ini dikenal dengan prinsip dualitas, prinsip yang juga kita temukan di dalam teori himpunan maupun logika [Rinaldi Munir, 2005, p289]. Definisi prinsip dualitas di dalam aljabar Boolean adalah sebagai berikut.

            Misalkan  S adalah kesamaan (identity) di dalam aljabar  Boolean yang melibatkan operator +, ·, dan ‘, maka jika pernyataan S* diperoleh dari S dengan cara mengganti · dengan +, + dengan ·, 0 dengan 1, 1 dengan 0 dan membiarkan operator komplemen tetap apa adanya, maka kesamaan  S* juga benar.  S* disebut sebagai  dual dari S.

Hukum–Hukum Aljabar Boolean

            Ada banyak hukum di dalam aljabar  Boolean. Beberapa literatur bervariasi dalam mengungkapkan jumlah hukum pada aljabar Boolean, tetapi hukum–hukum yang paling penting ditampilkan pada tabel berikut. 

            Selanjutnya dapat memperoleh hukum–hukum aljabar  Boolean dari hukum–hukum aljabar dengan cara mempertukarkan

∪ dengan +, atau ­ dengan +

∩ dengan ·, atau ­ dengan ·

U dengan 1, atau T dengan 1

dengan 0, atau F dengan 0.

        Perhatikanlah bahwa hukum yang ke-(ii) dari setiap hukum di atas merupakan dual dari hukum yang ke-(i). Sebagai contoh,

Hukum komutatif:  a + b = b + a

    dualnya:  a . b = b . a

Hukum asosiatif:  a + (b + c) = (a + b) + c

    dualnya:  a . (b . c) = (a . b) . c

Hukum distributif:  a + (b . c) = (a + b) . (a + c)

    dualnya:  a . (b + c) = (a . b) + (a . c)

Fungsi Boolean

            Fungsi Boolean (disebut juga fungsi biner) adalah pemetaan dari Bⁿ ke B melalui ekspresi Boolean, dapat dituliskan sebagai 

f : Bⁿ B

yang dalam hal ini  Bⁿ adalah himpunan yang beranggotakan pasangan terurut ganda-n (ordered n-tuple) di dalam daerah asal B [Rinaldi Munir, 2005, p293].

            Misalkan ekspresi  Boolean dengan  n peubah adalah  E(x₁,  x₂, ...,  x_n). Menurut definisi di atas, setiap pemberian nilai–nilai kepada peubah x₁, x₂, ..., x_n merupakan suatu pasangan terurut ganda-n di dalam daerah asal  Bⁿ dan nilai ekspresi tersebut adalah bayangannya di dalam daerah hasil B. Dengan kata lain, setiap ekspresi Boolean tidak lain merupakan fungsi Boolean. Misalkan sebuah fungsi Boolean adalah  f(x, y, z) = xyz +  x’y +  y’z. Fungsi  f memetakan nilai–nilai pasangan terurut ganda-3 (x,  y,  z) ke himpunan {0, 1}. Contoh pasangan terurut ganda-3 misalnya (1, 0, 1) yang berarti x = 1, y = 0, dan z = 1 sehingga  f(1, 0, 1) = 1 . 0 . 1 + 1’ . 0 + 0’ . 1 = 0 + 0 + 1 = 1.

Komplemen Fungsi Boolean

            Bila sebuah fungsi  Boolean dikomplemenkan, kita memperoleh fungsi komplemen. Fungsi komplemen berguna pada saat kita melakukan penyederhanaan fungsi Boolean [Rinaldi Munir, 2005, p296]. 

            Fungsi komplemen dari suatu fungsi  f, yaitu  f ’ dapat dicari dengan dua cara berikut.

1. Cara pertama: menggunakan hukum De Morgan

Hukum De Morgan untuk dua buah peubah, x₁ dan x₂ adalah

(i) (x₁ + x₂)’ = x₁’x₂’

(ii) dan dualnya: (x₁ . x₂)’ = x₁’ + x₂’

Hukum De Morgan untuk tiga buah peubah, x₁, x₂ dan x₃ adalah

(i)                 (x₁ + x₂ + x₃)’ = (x₁ + y’) , yang dalam hal ini y = x₂ + x₃

                                     = x₁’y’

                                     = x₁’(x₂ + x₃)’

                                     = x₁’x₂’x₃’

(ii)  dan dualnya : (x₁ . x₂ . x₃)’ = x₁’ + x₂’ + x₃’

(iii) (x₁ + x₂ + ... + x_n)’ = x₁’ x₂’ ... xn’ 

(iv) dan dualnya : (x₁ . x₂ . ... . x_n)’ = x₁’ + x₂’ + ... + x_n’

2. Cara kedua: menggunakan prinsip dualitas.

Tentukan dual dari ekspresi  Boolean yang merepresentasikan   f, lalu komplemenkan setiap literal di dalam dual tersebut. Bentuk akhir yang diperoleh menyatakan fungsi komplemen. 

Misalkan  f(x, y, z) = x(y’z’ + yz), maka dual dari ekspresi Boolean nya adalah  

x + (y’ + z’) (y + z)

Komplemenkan tiap literal dari dual di atas menjadi

x’ + (y + z) (y’ + z’) = f ’

Jadi,  f‘(x, y, z) = x’ + (y + z) (y’ + z’)

Penyederhanaan Fungsi Boolean

Fungsi Boolean seringkali mengandung operasi–operasi yang tidak perlu, literal atau suku–suku yang berlebihan. Oleh karena itu, fungsi Boolean dapat disederhanakan lebih lanjut. Menyederhanakan fungsi Boolean artinya mencari bentuk fungsi lain yang ekivalen tetapi dengan jumlah literal atau operasi yang lebih sedikit. Penyederhanaan fungsi Boolean disebut juga minimisasi fungsi [Rinaldi Munir, 2005, p308].

Dipandang dari segi aplikasi aljabar  Boolean, fungsi  Boolean yang lebih sederhana berarti rangkaian logikanya juga lebih sederhana (menggunakan jumlah gerbang logika lebih sedikit). Ada  tiga metode yang dapat digunakan untuk menyederhanakan fungsi Boolean:

1. Secara aljabar, menggunakan hukum–hukum aljabar Boolean.

2. Metode Peta Karnaugh.

3. Metode Quine-McCluskey (metode tabulasi).

Penyederhanaan Fungsi Boolean Secara Aljabar

Jumlah literal di dalam sebuah fungsi Boolean dapat diminimumkan dengan trik manipulasi aljabar. Sayangnya, tidak ada aturan khusus yang harus diikuti yang akan menjamin menuju ke jawaban akhir. Metode yang tersedia adalah prosedur yang  cutand-try yang memanfaatkan postulat, hukum–hukum dasar, dan metode manipulasi lain yang sudah dikenal [Rinaldi Munir, 2005, p309]. Sebagai contoh :

f(x, y, z) = xz’ + y’z + xyz’

               = xz’ . 1 + y’z + xyz’                       (Hukum identitas)

               = xz’ (1 + y) + y’z                            (Hukum distributif)

               = xz’ . 1  + y’z                                  (Hukum dominansi)

f(x, y, z)  = xz’ + y’z                                      (Hukum identitas)

Metode Peta Karnaugh

Metode Peta  Karnaugh (atau  K-map) merupakan metode grafis untuk menyederhanakan fungsi Boolean. Metode ini ditemukan oleh Maurice Karnaugh pada tahun 1953. Peta Karnaugh adalah sebuah diagram/peta yang terbentuk dari kotak–kotak (berbentuk bujursangkar) yang bersisian. Tiap kotak merepresentasikan sebuah minterm.

Tiap kotak dikatakan bertetangga jika  minterm–minterm yang merepresentasikannya berbeda hanya 1 buah literal [Kenneth H. Rosen, 2000, p612]. Peta Karnaugh dapat dibentuk dari fungsi Boolean yang dispesifikasikan dengan ekspresi Boolean maupun fungsi yang direpresentasikan dengan tabel kebenaran.

a. Peta Karnaugh dengan Dua Peubah

Misalkan dua peubah di dalam fungsi Boolean adalah x dan y. Baris pada peta Karnaugh untuk peubah x dan kolom untuk peubah y. Baris pertama diidentifikasi nilai 0 (menyatakan  x’), sedangkan baris kedua dengan 1 (menyatakan  x). Kolom pertama diidentifikasi nilai 0 (menyatakan y’), sedangkan kolom kedua dengan 1 (menyatakan y). Setiap kotak merepresentasikan  minterm dari kombinasi baris dan kolom yang bersesuaian. Berikut terdapat tiga cara  yang lazim digunakan sejumlah literatur dalam menggambarkan peta Karnaugh untuk dua peubah.

Perhatikan bahwa dua kotak yang bertetangga pada peta  Karnaugh hanya berbeda satu bit atau satu literal.

b.  Peta Karnaugh dengan Tiga Peubah

Untuk fungsi Boolean dengan tiga peubah (misalkan x, y dan z), jumlah kotak di dalam peta  Karnaugh meningkat menjadi 2³ = 8. Baris pada peta  Karnaugh untuk peubah x dan kolom untuk peubah yz. Baris pertama diidentifikasi nilai  0 (menyatakan x’), sedangkan baris kedua dengan 1 (menyatakan x). Kolom pertama diidentifikasi nilai 00 (menyatakan  x’y’), kolom kedua diidentifikasi nilai 01 (menyatakan  xy’), kolom ketiga diidentifikasi 11 (menyatakan xy). Perhatikanlah bahwa antara satu kolom dengan kolom berikutnya hanya berbeda satu bit. Setiap kotak merepresentasikan minterm dari kombinasi baris dan kolom yang bersesuaian.

c.  Peta Karnaugh dengan Empat Peubah

Misalkan empat peubah di dalam fungsi Boolean adalah w,  x,  y dan z. Jumlah kotak di dalam peta Karnaugh meningkat menjadi 2⁴ = 16. Baris pada peta Karnaugh untuk peubah  wx dan kolom untuk peubah  yz. Baris pertama diidentifikasi nilai 00 (menyatakan w’x’), baris kedua dengan 01 (menyatakan w’x), baris ketiga dengan 11 (menyatakan  wx) dan baris keempat dengan 10 (menyatakan  wx’). Kolom pertama diidentifikasi nilai 00 (menyatakan  y’z’), kolom kedua diidentifikasi nilai 01 (menyatakan  yz’), kolom ketiga diidentifikasi nilai 11 (menyatakan yz), sedangkan kolom keempat diidentifikasi dengan nilai 00 (menyatakan  yz’). Setiap kotak merepresentasikan minterm dari kombinasi baris dan kolom yang bersesuaian.