ALJABAR BOOLEAN - MATEMATIKA DISKRIT

ALJABAR BOOLEAN

Jika B adalah himpunan yang didefinisikan pada dua operator biner yaitu + 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

Tiga syarat aljabar dapat dikatan aljabar boolean

1.elemen - elemen himpunan B

2.kaidah/aturan operasi untuk dua operator biner dan operator uner

3.Memenuhi postulat Huntington

ALJABAR BOOLEAN DUA-NILAI

Aljabar Boolean dua-nilai:

 - B = {0, 1}

- operator biner, + dan ×

- operator uner, ’

Kaidah untuk operator biner dan operator uner : 

     

           

Dengan memperhatikan keempat aksioma  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 dapat dilihat bahwa:

(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 pada 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.

EKPSRESI BOOLEAN

Dalam aljabar  Boolean dua-nilai,  B = {0, 1}. Kedua elemen  B ini seringkali disebut elemen biner atau bit (singkatan binary bit). Pengganti (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.

        Misalnya (B, +, ., ‘, 0, 1) merupakan sebuah aljabar Boolean. Suatu ekspresi Boolean dalam (B, +, ., ‘) adalah:

(i) Setiap elemen di dalam B,

(ii) setiap peubah,

(iii      (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 disebut ekspresi Boolean bagi n peubah [Rinaldi Munir, 2005, p287].

      Dalam menuliskan ekspresi Boolean selanjutnya, digunakan perjanjian berikut: tanda kurung {()} memiliki prioritas pengerjaan paling tinggi, kemudian diikuti dengan operator ‘, + dan ·. Sebagai contohnya

1.ekspresi a + b . c berarti a + (b . c), bukan  (a+ b) . c 

2.ekspresi a . b’ berarti a . (b’), bukan (a . b)’.

Prinsip Dualitas

Di dalam aljabar Boolean, banyak ditemukan kesamaan (identity) yang diperoleh dari kesamaan lainnya, misalkan 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 sebaliknya. Prinsip ini disebut prinsip dualitas, prinsip yang juga kita temui di dalam teori himpunan maupun logika. Pengertian prinsip dualitas di dalam aljabar Boolean adalah sebagai berikut.

Dimisalkan 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 maka 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)

Buktikan (i) a + a’b = a + b   dan   (ii) a(a’ + b) = ab

Penyelesaian:

          (i)      a + a’b        = (a + ab) + a’b            (Penyerapan)

                                       = a + (ab + a’b)            (Asosiatif)

                                       = a + (a + a’)b              (Distributif)

                                       = a + 1 · b                    (Komplemen)

                                       = a + b                          (Identitas)

FUNGSI BOOLEAN

Fungsi Boolean (disebut juga fungsi biner) adalah pemetaan dari Bⁿke B  melalui ekspresi Boolean, kita menuliskannya 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.

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}.

Contohnya, (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 .

Contoh.  Contoh-contoh fungsi Boolean yang lain:

1.    f(x) = x

2.    f(x, y) = x’y + xy’+ y’

3.    f(x, y) = x’ y’

4.    f(x, y) = (x + y)’

5.    f(x, y, z) = xyz’                                                                                               

·       Setiap peubah di dalam fungsi Boolean, termasuk dalam bentuk komplemennya, disebut literal.Contoh: Fungsi h(x, y, z) = xyz’ pada contoh di atas terdiri dari 3 buah literal, yaitu x, y, dan z’.

Contoh:

 Fungsi h(x, y, z) = xyz’ pada contoh di atas terdiri dari 3 buah literal, yaitu x, y, dan z’. 

Contoh. Diketahui fungsi Booelan f(x, y, z) = xy z’, nyatakan h dalam tabel kebenaran.

Penyelesaian

BENTUK KATONIK

Ada dua macam bentuk kanonik:

1.    Penjumlahan dari hasil kali (sum-of-product atau SOP)

2.    Perkalian dari hasil jumlah (product-of-sum atau POS)

Contoh: 

1.  f(x, y, z) = x’y’z + xy’z’ + xyz  -->  SOP 

     Setiap suku (term) disebut minterm

2. g(x, y, z) = (x + y + z)(x + y’ + z)(x + y’ + z’) (x’ + y + z’)(x’ + y’ + z)  --> POS

     Setiap suku (term) disebut maxterm

 Setiap minterm/maxterm mengandung literal lengkap     

     

'

Contoh: 

 Nyatakan tabel kebenaran di bawah ini dalam bentuk kanonik SOP dan POS.

 Penyelesaian :

     (a)   SOP

Kombinasi nilai-nilai peubah yang menghasilkan nilai fungsi sama dengan 1 adalah 001, 100, dan 111, maka fungsi Booleannya dalam bentuk kanonik SOP adalah

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

atau (dengan menggunakan lambang minterm),   

        

                                f(x, y, z) =  m₁ + m₄ + m₇ = å (1, 4, 7)

(b) POS

 Kombinasi nilai-nilai peubah yang menghasilkan nilai fungsi sama dengan 0 adalah 000, 010,  011, 101, dan 110, maka fungsi Booleannya dalam bentuk kanonik POS adalah

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

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

                                  

      atau dalam bentuk lain,                

                                 f(x, y, z) =  M₀ M₂ M₃ M₅ M₆ = Õ(0, 2, 3, 5, 6)     

Contoh :

Nyatakan fungsi Boolean f(x, y, z) = x + y’z dalam bentuk kanonik SOP dan POS.

P penyelesaian:

     

  (a) SOP

     x  = x(y + y’)

         = xy + xy’

         = xy (z + z’) + xy’(z + z’)

         = xyz + xyz’ + xy’z + xy’z’

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

           = xy’z + x’y’z

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

                                  = xyz + xyz’ + xy’z + xy’z’ + xy’z + x’y’z

                                  = x’y’z + xy’z’ + xy’z + xyz’ + xyz

                       

       atau  f(x, y, z)   = m₁ + m₄ + m₅ + m₆ + m₇ = S (1,4,5,6,7)   

          (b) POS

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

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

          x + y’ = x + y’ + zz’

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

          x + z = x + z + yy’        

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

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

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

          atau f(x, y, z) = M₀M₂M₃ = Õ(0, 2, 3)