Aljabar Boolean dan Gerbang Logika

           Teori dasar Aljabar Boolean terdiri dari: Elemen Identitas (x + 0 = x dan x . 1 = x), Komplemen (x + x’ = 1 dan x . x’ = 0), Tertutup (x + x =x; x + 1 = 1 dan x . x = x; x .0 = 0), Involusi ((x’)’ = x), Komutatif (x + y = y + x dan xy = yx), Asosiatif (x + (y + z) = (x + y) + z dan x(yz) = (xy)z), Distributif (x (y + z) = xy + xz dan x + (yz) = (x + y)(x + z)), De Morgan ( ( x + y)’ =x’y’ dan (xy)’ = x’ + y’), Absorpsi ( x + xy = x dan x ( x + y) = x ).

            Komplemen fungís merupakan statu fungsi yang memberikan nilai keluaran berkebalikan dengan fungsi awalnya. Sebagai conti suatu fungsi ( 0 menjadi 1 dan 1 menjadi 0). Sebagai contoh suatu fungsi K = (yz + x’y), Maka komplemennya adalah K’ = (y’ + z’)(x + y’).

            Fungsi Boolean-Bentuk Kanonikal terdiri dari dua terms, yaitu minterms dan maxterms, dimana setiap terms terdiri atas semua variabel yang ada.

Contoh:

K (x, y, z) = x’y’z + xy’z’

L (o, p, q) = (o + p’ + q)(o’ + p + q’)

            x’y’z , xy’z’ disebut minterms

            (o + p’ + q), (o’ + p + q’) disebut maxterms

            Funsi boolean bentuk standar terdiri dari 2 yaitu SOP (Sum of Product) dan POS (Product of Sum). SOP terdiri dari beberapa gerbang AND dan satu gerbang OR. Sebaliknya POS terdiri dari beberapa gerbang OR dan satu buah gerbang AND.

Penyederhanaan Fungsi Boolean

            Penyederhanaan sangat perlu dilakukan untuk membuat suatu fungsi menjadi lebih efisien dan mudah dipahami. Ada tiga cara penyederhanaan fungsi, yaitu: Menggunakan aturan Aljabar Boolean (secara matematis), Menggunakan Karnaugh map (K-map), dan menggunakan tabulasi (Quine McCluskey).

            Contoh dalam menggunakan aturan aljabar Boolean:

K   = ABC’ +A’BC + ABC + A’BC’

      = AB(C + C’) + A’B(C + C’)

      = AB(1) + A’B(1)

      = A(B + B’)

      = A(1)

      = A

L    = (B + C’) C

      = BC + CC’

      = BC + 0

      = BC

Cara kedua adalah menggunakan K-map. Dengan ketentuan sebagai berikut: Setiap kombinasi variabel (minterms) dipetakan ke kotak yang unik, setiap 2ⁿ kotak bernilai 1 yang berdekatan (mempunyai beda nomor kotak 1 bit) digabungkan, hasil yang didapatkan dalam bentuk sum of product (SOP), bisa digunakan untuk menyederhanakan fungsi boolean dengan jumlah variabel 2, 3, 4, dst.