Aljabar boolean merupakan aljabar yang berhubungan dengan variabel-variabel biner dan operasi-operasi logik. Variabel-variabel diperlihatkan dengan huruf-huruf alfabet, dan tiga operasi dasar dengan AND, OR dan NOT (komplemen). Fungsi boolean terdiri dari variabel-variabel biner yang menunjukkan fungsi, suatu tanda sama dengan, dan suatu ekspresi aljabar yang dibentuk dengan menggunakan variabel-variabel biner, konstanta-konstanta 0 dan 1, simbol-simbol operasi logik, dan tanda kurung.
Suatu fungsi boolean bisa dinyatakan dalam tabel kebenaran. Suatu tabel kebenaran untuk fungsi boolean merupakan daftar semua kombinasi angka-angka biner 0 dan 1 yang diberikan ke variabel-variabel biner dan daftar yang memperlihatkan nilai fungsi untuk masing-masing kombinasi biner.
Aljabar boolean mempunyai 2 fungsi berbeda yang saling berhubungan. Dalam arti luas, aljabar boolean berarti suatu jenis simbol-simbol yang ditemukan oleh George Boole untuk memanipulasi nilai-nilai kebenaran logika secara aljabar. Dalam hal ini aljabar boolean cocok untuk diaplikasikan dalam komputer. Disisi lain, aljabar boolean juga merupakan suatu struktur aljabar yang operasi-operasinya memenuhi aturan tertentu.
DASAR OPERASI LOGIKA
LOGIKA :
Memberikan batasan yang pasti dari suatu keadaan, sehingga suatu keadaan tidak dapat berada dalam dua ketentuan sekaligus.
Dalam logika dikenal aturan sbb :
¨ Suatu keadaan tidak dapat dalam keduanya benar dan salah sekaligus
¨ Masing-masing adalah benar / salah.
¨ Suatu keadaan disebut benar bila tidak salah.
Dalam ajabar boolean keadaan ini ditunjukkan dengan dua konstanta : LOGIKA ‘1’ dan ‘0’
Operasi-operasi dasar logika dan gerbang logika :
Pengertian GERBANG (GATE) :
¨ Rangkaian satu atau lebih sinyal masukan tetapi hanya menghasilkan satu sinyal keluaran.
¨ Rangkaian digital (dua keadaan), karena sinyal masukan atau keluaran hanya berupa tegangan tinggi atau low ( 1 atau 0 ).
¨ Setiap keluarannya tergantung sepenuhnya pada sinyal yang diberikan pada masukan-masukannya.
Operasi logika NOT ( Invers )
Operasi merubah logika 1 ke 0 dan sebaliknya à x = x’
12
Tabel Operasi NOT Simbol
  X | X’ |
    0 | 1 |
| 1 | 0 |
Operasi logika AND
¨ Operasi antara dua variabel (A,B)
¨ Operasi ini akan menghasilkan logika 1, jika kedua variabel tersebut berlogika 1
Simbol Tabel operasi AND 
A B A . B
A A . B 0 0 0
0 1 0 1 0 0 B 1 1 1
Operasi logika OR
Operasi antara 2 variabel (A,B)
Operasi ini akan menghasilkan logika 0, jika kedua variabel tersebut berlogika 0.
Simbol Tabel Operasi OR
 |
A A + B A B A + B
0 0 0 
0 1 1 B 1 0 1
1 1 1
Operasi logika NOR
Operasi ini merupakan operasi OR dan NOT, keluarannya merupakan keluaran operasi OR yang di inverter.
Simbol Tabel Operasi NOR
|
A A + B ( A + B )’ A B ( A + B)’
0 0 1 0 1 0 B
1 0 0
13 1 1 0
Atau
A ( A + B )’
B
Operasi logika NAND
Operasi logika ini merupakan gabungan operasi AND dan NOT, Keluarannya merupakan keluaran gerbang AND yang di inverter.
Simbol Tabel Operasi NAND
|
A A . B ( A . B )’ A B ( A . B)’
0 0 1 0 1 1 B 1 0 1
1 1 0
Atau
A ( A . B )’
B
Operasi logika EXOR
akan menghasilkan keluaran ‘1’ jika jumlah masukan yang bernilai ‘1’ berjumlah ganjil.
Simbol Tabel Operasi EXOR
|
A Y A B A + B
0 0 0 0 1 1 B 1 0 1
1 1 0
Operasi logika EXNOR
Operasi ini akan menghasilkan keluaran ‘1’ jika jumlah masukan yang bernilai ‘1’ berjumlah genap atau tidak ada sama sekali.
14
Simbol Tabel Operasi EXNOR
|
A Y A B A + B 0 0 1 0 1 0 B 1 0 0
1 1 1
DALIL BOOLEAN ;
1. X=0 ATAU X=1
2. 0 . 0 = 0
3. 1 + 1 = 1
4. 0 + 0 = 0
5. 1 . 1 = 1
6. 1 . 0 = 0 . 1 = 0
7. 1 + 0 = 0 + 1 = 0
TEOREMA BOOLEAN
| 1. HK. KOMUTATIF A + B = B + A A . B = B . A | 6. HK. IDENTITAS A + A = A A . A = A |
| 2. HK. ASSOSIATIF (A+B)+C = A+(B+C) (A.B) . C = A . (B.C) | 7. 0 + A = A ----- 1. A = A 1 + A = 1 ----- 0 . A = 0 |
| 3. HK. DISTRIBUTIF A . (B+C) = A.B + A.C A + (B.C) = (A+B) . (A+C) | 8. A’ + A = 1 A’ . A =0 |
| 4. HK. NEGASI ( A’ ) = A’ (A’)’ = A | 9. A + A’ . B = A + B A . (A + B)= A . B |
| 5. HK. ABRSORPSI A+ A.B = A A.(A+B) = A | 10. DE MORGAN’S ( A+ B )’ = A’ . B’ ( A . B )’ = A’ + B’ |
CONTOH :
1. A + A . B’ + A’ . B = A . ( 1 + B’ ) + A’ . B
= A . 1 + A’ . B
= A + A’ . B
= A + B
15
2. A
B |
X X = (A.B)’ . B = (A’ + B’) . B
= ( A.B )’ + B’.B
= ( A.B )’ + 0
= A’.B
A | |||
 | |||
B |
X = A’.BATAU
A X = A’.B BAljabar Boolean
Ø Misalkan terdapat
- Dua operator biner: + dan ×
- Sebuah operator uner: ’.
- B : himpunan yang didefinisikan pada opeartor +, ×, dan ’
- 0 dan 1 adalah dua elemen yang berbeda dari B.
Tupel
(B, +, ×, ’)
disebut aljabar Boolean jika untuk setiap a, b, c Î B berlaku aksioma-aksioma atau postulat Huntington berikut:
16
1. Closure: (i) a + b Î B
(ii) a × b Î B
2. Identitas: (i) a + 0 = a
(ii) a × 1 = a
3. Komutatif: (i) a + b = b + a
(ii) a × b = b . a
4. Distributif: (i) a × (b + c) = (a × b) + (a × c)
(ii) a + (b × c) = (a + b) × (a + c)
5. Komplemen[1]: (i) a + a’ = 1
(ii) a × a’ = 0
- 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.
Aljabar Boolean Dua-Nilai
Aljabar Boolean dua-nilai:
- B = {0, 1}
- operator biner, + dan ×
- operator uner, ’
- Kaidah untuk operator biner dan operator uner:
| a | B | a × b | | a | b | a + b | | a | a’ |
| 0 | 0 | 0 | | 0 | 0 | 0 | | 0 | 1 |
| 0 | 1 | 0 | | 0 | 1 | 1 | | 1 | 0 |
| 1 | 0 | 0 | | 1 | 0 | 1 | | | |
| 1 | 1 | 1 | | 1 | 1 | 1 | | | |
Cek apakah memenuhi postulat Huntington:
1. Closure : jelas berlaku
2. Identitas: jelas berlaku karena dari tabel dapat kita lihat bahwa:
(i) 0 + 1 = 1 + 0 = 1
(ii) 1 × 0 = 0 × 1 = 0
3. Komutatif: jelas berlaku dengan melihat simetri tabel operator biner.
4. Distributif: (i) a × (b + c) = (a × b) + (a × c) dapat ditunjukkan benar dari tabel operator biner di atas dengan membentuk tabel kebenaran:
| a | b | c | b + c | a × (b + c) | a × b | a × c | (a × b) + (a × c) |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
(ii) Hukum distributif a + (b × c) = (a + b) × (a + c) dapat ditunjukkan benar dengan membuat tabel kebenaran dengan cara yang sama seperti (i).
5. Komplemen: jelas berlaku karena Tabel 7.3 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 = 0 dan 1 × 1’ = 1 × 0 = 0
Karena kelima postulat Huntington dipenuhi, maka terbukti bahwa B = {0, 1} bersama-sama dengan operator biner + dan × operator komplemen ‘ merupakan aljabar Boolean.
Ekspresi Boolean
- Misalkan (B, +, ×, ’) adalah sebuah aljabar Boolean. Suatu ekspresi Boolean dalam (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
Contoh:
0
1
a
b
c
a + b
a × b
a’× (b + c)
a × b’ + a × b × c’ + b’, dan sebagainya
Mengevaluasi Ekspresi Boolean
- Contoh: a’× (b + c)
18
jika a = 0, b = 1, dan c = 0, maka hasil evaluasi ekspresi:
0’× (1 + 0) = 1 × 1 = 1
- Dua ekspresi Boolean dikatakan ekivalen (dilambangkan dengan ‘=’) jika keduanya mempunyai nilai yang sama untuk setiap pemberian nilai-nilai kepada n peubah.
Contoh:
a × (b + c) = (a . b) + (a × c)
Contoh. Perlihatkan bahwa a + a’b = a + b .
Penyelesaian:
| a | b | a’ | a’b | a + a’b | a + b |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 |
- Perjanjian: tanda titik (×) dapat dihilangkan dari penulisan ekspresi Boolean, kecuali jika ada penekanan:
(i) a(b + c) = ab + ac
(ii) a + bc = (a + b) (a + c)
(iii) a × 0 , bukan a0
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.
Contoh.
(i) (a × 1)(0 + a’) = 0 dualnya (a + 0) + (1 × a’) = 1
(ii) a(a‘ + b) = ab dualnya a + a‘b = a + b
19
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 |  |
Contoh 7.3. 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)
(ii) adalah dual dari (i)
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}.
20
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. Diketahui fungsi Booelan f(x, y, z) = xy z’, nyatakan h dalam tabel kebenaran.
Penyelesaian:
| x | y | z | f(x, y, z) = xy 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 0 0 0 0 0 1 0 |
Komplemen Fungsi
1. Cara pertama: menggunakan hukum De Morgan
Hukum De Morgan untuk dua buah peubah, x1 dan x2, adalah
Contoh. Misalkan f(x, y, z) = x(y’z’ + yz), maka
f ’(x, y, z) = (x(y’z’ + yz))’
= x’ + (y’z’ + yz)’
= x’ + (y’z’)’ (yz)’
= x’ + (y + z) (y’ + z’)
21
Aplikasi Aljabar Boolean
2. Rangkaian Digital Elektronik
 |  |  | |||
Gerbang AND Gerbang OR Gerbang NOT (inverter)
Contoh. Nyatakan fungsi f(x, y, z) = xy + x’y ke dalam rangkaian logika.
Jawab: (a) Cara pertama
 |
 |
(b) Cara kedua
 |
(b) Cara ketiga
22
Gerbang turunan
 |  | ||
Gerbang NAND Gerbang XOR
 |  | ||
Gerbang NOR Gerbang XNOR
 |
 |
Penyederhanaan Fungsi Boolean
Contoh. f(x, y) = x’y + xy’ + y’
 |
disederhanakan menjadi
f(x, y) = x’ + y’
Penyederhanaan fungsi Boolean dapat dilakukan dengan 3 cara:
1. Secara aljabar
2. Menggunakan Peta Karnaugh
3. Menggunakan metode Quine Mc Cluskey (metode Tabulasi)
23
1. Penyederhanaan Secara Aljabar
Contoh:
1. f(x, y) = x + x’y
= (x + x’)(x + y)
= 1 × (x + y )
= x + y
2. f(x, y, z) = x’y’z + x’yz + xy’
= x’z(y’ + y) + xy’
= x’z + xz’
3. f(x, y, z) = xy + x’z + yz = xy + x’z + yz(x + x’)
= xy + x’z + xyz + x’yz
= xy(1 + z) + x’z(1 + y) = xy + x’z
sumber;
24
