Qiuz Matematika Diskrit

Quiz Matematika Diskrit ( Aljabar Boolean )

Aljabar Boolean

 

    A.   Definisi Aljabar Boolean

        Definisi 7.1 ( LIP92 )

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, +, ·, ’) disebut Aljabar Boolean jika untuk setiap a, b, c Î B berlaku aksioma-aksioma      atau 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 :(i)  a + a’ = 1

   (ii)  a · a’ = 0

Elemen 0 dan 1 adalah dua elemen unik yang di dalam B. 0 disebut terkucil dan 1 disebut elemen tersebar. Kedua elemen dapat berbeda- beda pada beberapa aljabar Boolean, namun secara umum kita tetap menggunakan 0 dan 1 sebagai dua elem unik yang berbeda. Elemen 0 disebut elem zero, sedangkan elemen 1 disebut elemen unit. Operator + disebut operator penjumlahan, . disebut operator perkalian, dan ‘ disebut operator komplemen

    Untuk mempunyai sebuah aljabar Boolean, harus diperlihatkan:

    1.      Elemen-elemen himpunan B,

    2.      Kaidah operasi untuk operator biner dan operator uner,

    3.      Memenuhi postulat Huntington.

B. Prinsip Dualitas

Misalkan S adalah kesamaan (identity) di dalam aljabar Boolean yang melibatkan operator +, ·, dan komplemen, maka jika pernyataan S* diperoleh 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.

        C.     Hukum-hukum Aljabar Boolean

1.Hukum identitas:             i.  a + 0 = a             ii.a × 1 = a	2. Hukum idempoten:   i.             a + a = a ii.       a × a = a
3. Hukum komplemen:             i.     a + a’ = 1 ii.       aa’ = 0	4. Hukum dominansi: i.      a × 0  = 0 ii.       a + 1 = 1
5. Hukum involusi: i.                     (a’)’ = a	6.  Hukum penyerapan: i.         a + ab = a ii.       a(a + b) = a
7. Hukum komutatif:        i.         a + b = b + a        ii.       ab = ba	8. Hukum asosiatif: i.         a + (b + c) = (a + b) + c ii.       a (b c) = (a b) c
9.  Hukum distributif:             i.         a + (b c) = (a + b) (a + c) ii.       a (b + c) = a b + a c	10. Hukum De Morgan: i.            (a + b)’ = a’b’ ii.       (ab)’ = a’ + b’
11.  Hukum 0/1 i.            0’ = 1 ii.       1’ = 0

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

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

Selain secara aljabar, fungsi Boolean juga dapat dinyatakan dengan table kebenaran dan dengan rangkaian logika. Tabel kebenaran berisi nilai-nilai fungsi untuk semua kombinasi nilai-nilai peubahnya.

Jika fungsi Boolean dinyatakan dengan table kebenaran, maka untuk fungsi Boolean dengan n buah peubah, kombinasi dari nilai peubah-peubahnya adalah sebanyak  .  Ini berarti terdapat  baris yang berbeda di dalam table kebenaran tersebut. misalkan n = 3, maka akan terdapat  = 8 baris tabel. Cara yang praktis membuat semua kombinasi tersebut adalah sebagai berikut:

1.      Untuk peubah pertama, isi 4 baris pertama pada kolom pertama dengan sebuah 0 dan 4 baris selanjutnya dengan sebuah 1 berturut-turut.

2.      Untuk peubah kedua, isi2 baris pertama pada kolom kedua dengan 0 dan 2 baris berikutnya dengan 1, 2 baris berikutnya dengan 0 lagi, dan 2 baris terakhir dengan 1.

3.      Untuk peubah ketiga, isi kolom ketiga secara berselang seling dengan 0 dan 1 mulai baris pertama sampai baris terakhir.

   E. Bentuk Kanonik

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)

Cara membentuk mainterm dan maxtrem dari table kebenaran di bawah. Untuk mainterm, setiap peuba yang bernilai 0 dinyatakan dalam bentuk komplemen, sedangkan peubah yang bernilai 1 dinyatakan tanpa komplemen. Sebaliknya, untuk maxterm, setiap peubah yang bernilai 0 dinyatakan tanpa komplemen, sedangkan peubah yang bernilai 1 dinyatakan dalam bentuk komolemen.

           Kadang – kadang mainterm dilambangkan sebagai huruf m kecil berindeks. Indeks menyatakan nilai decimal dari string biner yang merepresentasikan term. misalnya pada term dengan 2 peubah x dan y, indeks 0 pada  menyatakan nilai decimal dari 00 ( x = 0  dan  y =0), indeks 1 pada  menyatakan nilai decimal dari 01 ( x = 0  dan  y = 1), dan seterusnya. Jadi, untuk mainterm dari 3 peubah ( x, y, dan z ), jika ditulis  maka ini berarti mainterm xyz’ karena 6 ( decimal) = 110 ( biner); disini x = 1, y = 1 dan z = 0. Pada kasus yang terakir, peubah x dan y dinyatakan tanpa komplemen sedangkan peubah z dinyatakan dengan komplemen karena bernilai 0, sehingga ditulis xyz’.

           Maxterm dilambangkan sebagi huruf M besar indeks. Indeks menyatakan nilai decimal dari string biner yang merepresentasikan x + y. Misalnya pada term dengan 2 peubah x dan y, indeks 0 pada  menyatakan nilai decimal dari 00 ( x = 0 dan y = 0 ), indeks 1 pada  menyatakan nilai decimal dari 01 ( x = 0 dan y = 1), dan seterusnya. jadi, untuk maxterm dari 3  peubah ( x, y, dan z ), jika ditulis  maka ini berarti mainterm x’ + y’ + z karena 6 ( decimal) = 110 ( biner); disini x = 1, y = 1, dan z = 0. peubah x dan y dinyatakan dengan komplemen sedangkan peubah z dinyatakan tanpa komplemen karena bernilai 0, sehingga ditulis x’ + y’ +z.