ALJABAR BOOLEAN DAN GERBANG LOGIKA
Pendahuluan
Konsep dasar aljabar Boole (Boolean Algebra) telah diletakkan oleh seorang matematisi Inggeris George Boole, pada tahun 1854. Konsep dasar itu membutuhkan waktu yang cukup lama untuk disadari kegunaannya, baik dalam bidang matematika maupun dalam bidang teknik.
Pada tahun 1938 Claude Shannon, seorang ahli komunikasi, memanfaatkan dan menyempurnakan konsep Boole tersebut. Sekarang ini, aljabar Boole memegang peranan yang sangat penting, tidak saja dalam logika, tetapi juga di bidang lain seperti teori peluang/kemungkinan, teori informasi/komunikasi, teori himpunan dan lain-lain. Teori ini juga dipakai dalam merancang computer elektronik dengan menerjemahkannya ke dalam rangkaian saklar (switching circuits) yang pada dasarnya adalah logika, tertutup atau terbuka, mengalirkan arus listrik atau tidak.
Ekspresi Boolean adalah pernyataan logika dalam bentuk aljabar Boolean.

Fungsi Boolean
Fungsi Boolean (disebut juga fungsi biner) adalah pemetaan dari Bn ke B melalui ekspresi Boolean, kita menuliskannya sebagai
f : Bn  B
yang dalam hal ini Bn 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 .

Setiap peubah di dalam fungsi Boolean, termasuk dalam bentuk komplemennya, disebut literal.

Table 2.1 rumus-rumus pada aljabar Boolean
No. AND OR Keterangan
1
2
3
4
5
6
7
8


9 (A.B).C = A.(B.C)
A .B = B .A
(A+B).(A+C)=A+(B.C)
A.O = O
A.A = A
A.A= O
A = A
A.O= O
A .1 = A

A.(A + B ) = A (A+B)+C=A+(B+C)
A+B=B+A
(A.B)+(A.C)=A(B+C)
A+1= 1
A+A=A
A+ A=1
A = A
A + O = A
A + 1 = 1

A + (A.B) = A Hk.Asosiatif
Hk.Komutatif
Hk.Distributif
Hk.Identitas
Hk.Idempoten
Hk.Inversi/Negasi
Hk.Negasi Ganda
Hk.Hubungan Dgn Suatu Konstanta
Hk.Absorbsi

Kanonikal dan Bentuk Standar
Adalah menyatakan suatu persamaan dalam hubungan operasi AND atau OR antar variabel secara lengkap pada setiap suku. Dan antar suku dihubungkan dengan operasi OR atau AND.

Jadi, ada dua macam bentuk kanonikal:
Penjumlahan dari hasil kali (sum-of-product atau SOP)
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
Tabel 2.2 Bentuk Minterm dan Maxterm untuk 2 variabel biner
Minterm Maxterm
x y Suku Lambang Suku Lambang
0
0
1
1 0
1
0
1 x’y’
x’y
xy’
x y m0
m1
m2
m3 x + y
x + y’
x’ + y
x’ + y’ M0
M1
M2
M3

Tabel 2.3 Bentuk Minterm dan Maxterm untuk 3 variabel biner
Minterm Maxterm
x y z Suku Lambang Suku Lambang
0
0
0
0
1
1
1
1 0
0
1
1
0
0
1
1 0
1
0
1
0
1
0
1 x’y’z’
x’y’z
x‘y z’
x’y z
x y’z’
x y’z
x y z’
x y z m0
m1
m2
m3
m4
m5
m6
m7 x + y + z
x + y + z’
x + y’+z
x + y’+z’
x’+ y + z
x’+ y + z’
x’+ y’+ z
x’+ y’+ z’ M0
M1
M2
M3
M4
M5
M6
M7



Contoh 2.1. Nyatakan tabel kebenaran di bawah ini dalam bentuk kanonikal SOP dan POS.
Tabel 2.4
x y z f(x, y, z)
0
0
0
0
1
1
1
1 0
0
1
1
0
0
1
1 0
1
0
1
0
1
0
1 0
1
0
0
1
0
0
1
Penyelesaian:
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) = m1 + m4 + m7 =  (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) = M0 M2 M3 M5 M6 = (0, 2, 3, 5, 6)
Contoh 2.2. Nyatakan fungsi Boolean f(x, y, z) = x + y’z dalam bentuk kanonik SOP dan POS.
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) = m1 + m4 + m5 + m6 + m7 =  (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) = M0M2M3 = (0, 2, 3)
Gerbang Logika
Gerbang AND

Gambar 2.1
Tabel 2.5
A B Y
0 0 0
0 1 0
1 0 0
1 1 1



Gerbang OR




Gambar 2.2
Tabel 2.6
A B Y
0 0 0
0 1 1
1 0 1
1 1 1



diumpamakan sebagai sebuah rangkaian dengan dua buah saklar yang terpasang secara paralel.
Apabila salah satu saklar memutuskan hubungan (bernilai 0), maka output-nya tetaplah bernilai 1 karena input yang lain tidak akan terputus hubungannya dengan output. Apabila kedua input bernilai 0, maka output barulah benar-benar terputus atau bernilai 0. Jika keduanya bernilai 1, maka output juga akan bernilai 1.

Gerbang NOT

Gambar 2.3
Tabel 2.7
A Y
0 1
1 0

Gerbang NAND


Gambar 2.4
Tabel 2.8
A B Y
0 0 1
0 1 1
1 0 1
1 1 0


Gerbang NOR

Gambar 2.5
Tabel 2.9
A B Y
0 0 1
0 1 0
1 0 0
1 1 0

Gerbang XOR

Gambar 2.6
Tabel 2.10
A B Y
0 0 0
0 1 1
1 0 1
1 1 0




Gerbang XNOR

Gambar 2.7


salah satunya saja yang berbeda, maka nilai output pastilah bernilai 0.
Tabel 2.11
A B Y
0 0 1
0 1 0
1 0 0
1 1 1

Hukum De Morgan
(A + B)’ = A’ . B’ "⟺" A + B = (A’ . B’)’
(A . B)’ = A’ + B’ ⟺ A . B = (A’ + B’)’