ALJABAR BOOLEAN

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’

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

1 1 0

Atau

A ( A + 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.

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 6. HK. IDENTITAS

A+B=B+A A+A=A

A. B=B .A A .A=A
2. HK. ASSOSIATIF 7.

(A+B)+C = A+(B+C) 0 + A = A ----- 1. A = A

(A.B) . C = A . (B.C) 1 + A = 1 ----- 0 . A = 0

3. HK. DISTRIBUTIF 8.

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

A + (B.C) = (A+B) . (A+C) A’ . A =0

4. HK. NEGASI 9.

( A’ ) = A’ A + A’ . B = A + B

(A’)’ = A A . (A + B)= A . B
5. HK. ABRSORPSI 10. DE MORGAN’S

A+ A.B = A ( A+ B )’ = A’ . B’

A.(A+B) = A ( 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

2. A

X = (A.B)’ . B = (A’ + B’) . B

= ( A.B )’ + B’.B

= ( A.B )’ + 0
 = A’.B

X = A’.B

ATAU

A X = A’.B
B

Aljabar 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:

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. Komplemen1: (i) a + a’ = 1
(ii) a  a’ = 0

1
  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)

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

Hukum-hukum Aljabar Boolean

1. Hukum identitas: 2. Hukum idempoten:
(i) a+0=a (i) a + a = a
(ii) a  1 = a (ii) a  a = a
3. Hukum komplemen: 4. Hukum dominansi:
(i) a + a’ = 1 (i) a0 =0
(ii) aa’ = 0 (ii) a + 1 = 1
5. Hukum involusi: 6. Hukum penyerapan:
(i) (a’)’ = a (i) a + ab = a
(ii) a(a + b) = a
7. Hukum komutatif: 8. Hukum asosiatif:
(i) a+b=b+a (i) a + (b + c) = (a + b) + c
(ii) ab = ba (ii) a (b c) = (a b) c
9. Hukum distributif: 10. Hukum De Morgan:
(i) a + (b c) = (a + b) (a + c) (i) (a + b)’ = a’b’
(ii) a (b + c) = a b + a c (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}.

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
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 1
1 1 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’)

Aplikasi Aljabar Boolean

2. Rangkaian Digital Elektronik

x x
xy x+ y x x'
y y

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

x
xy
y

xy+x'y
x'
x
x'y
y

(b) Cara kedua

x xy
y

x y+x 'y

x'

x 'y

(b) Cara ketiga

x y

xy

xy+x'y

x'
x'y
Gerbang turunan

x x
( xy )' x + y
y y

Gerbang NAND Gerbang XOR

x x
( x+y )' ( x + y )'
y y

Gerbang NOR Gerbang XNOR

x x x+ y
( x + y )' ekivalen dengan ( x + y )'
y y

x' x
x 'y ' ekivalen dengan ( x+y )'
y' y

Penyederhanaan Fungsi Boolean

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

x' x
x '+ y ' ekivalen dengan ( xy )'
y' 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)

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

Teori De Morgan

Teori de morgan dapat dituliskan sebagai berikut:

Untuk mentransformasikan situasi AND menjadi OR ( atau situasi OR ke AND ) diperlukan empat langkah

yang berdsarkan teori de morgan sebagai berikut :

1. Ubah semua OR ke AND dan semua AND ke OR.

2. Lengkapi setiap variable individual ( tambahkan tanda strip diatas pada setiap variable)

3. Lengkapi semua fungsi (tambahkan tanda strip diatasnya).

4. Hilangkan semua kelompok dari tanda strip diatas yang berjumlah genap.

C. Penyederhanaan Persamaan Logika Dengan Aljabar Boolean Dan Teori De Morgan

Untuk membuat persamaan logika dari suatu permasalahan logika dapat dikerjakan dengan dua cara:

1. Sum Of Product (SOP).

Sum of product atau Minterm atau jumlah dari kali adalah persamaan logika yang menjumlahkan

( OR ) kondisi 1 dari setiap hasil kali ( AND).

Contoh:

Masukan Keluaran

A B Y

0 0 0

0 1 1

1 0 1

1 1 1

Dari table kebenaran diatas dapat disusun persamaan logika minterm sebagai berikut;

A.B + A.B + A.B=Y

2. Product of Sum ( POS)

Product of Sum atau Maxterm atau perkalian dari jumlah adalah persamaan logika yang mengalikan ( AND )

kondisi 0 dari setiap Penjumlahan ( OR ).

Contoh:

Masukan Keluaran

A B Y

0 0 0

0 1 0

1 0 0

1 1 1

Dari table kebenaran diatas dapat disusun persamaan logika maxterm sebagai berikut;

A+B . A+B . A+B=Y

Dengan menerapkan hukum – hukum Boolean dan teori de morgan persamaan diatas dapat disederhanakan.

KARNAUGH MAP (K-MAP)

Karnaugh Map atau yang biasanya disebut dengan K-Map adalah suatu teknik penyederhanaan fungsi logika

dengan cara pemetaan. K-Map terdiri dari kotak-kotak yang jumlahnya terdiri dari jumlah variable dan fungsi

logika atau jumlah inputan dari rangkaian logika yang sedang kita hitung.

Rumus untuk menentukan jumlah kotak pada K-Map adalah 2n n adalah banyaknya variabel / inputan.
Langkah – langkah pemetaan K-Map secara umum :

· Menyusun aljabar Boolean terlebih dahulu

· Menggambar rangkaian digital

· Membuat Table Kebenarannya

· Merumuskan Tabel Kebenarannya

· Lalu memasukkan rumus Tabel Kebenaran ke K-Map (Kotak-kotak

Penyederhanaan Dua Variabel

Catatan : Bar = ‘

Tabel dari K-Map 2 variabel adalah seperti dibawah ini

Contoh

H = AB + A’B+AB’

Maka cara pengerjaanya seperti dibawah ini

Bar / ‘ biasanya ditulis kedalam angka 0 sedangkan angka 1 adalah tanpa Bar / ‘

Dan dapat dipermudah lagi menjadi dibawah ini

Yang dapat disederhanakan dalam K-Map hanya 2 / kelipatan 2 dari kotak yang berdempetan dan sedangkan

jika seperti kotak diatas maka penyderhanaannya

Yaitu terletak pada kotak 01 + 11 dan 10 + 11 yaitu cara penyederhanaan dengan cara menulis angka yang sama

(1 lingkaran) dan menerjemahkannya kedalam bentuk huruf seperti A dan B.

Caranya :

01

11

1 yang sama adalah angka 1 yang dibelakang jadi jika letaknya dibelakang (kedua) adalah B (B diambil

dari tabel K-Map Diatas ) jika yang sama angka 0 pada urutan kedua adalah B’ diatas sudah disebutkan bahwa

angka 0 = Bar/’

10

11

1 yang sama adalah angka 1 yang didepan jadi jika letaknya didepan (pertama) adalah A (A diambil dari

tabel K-Map Diatas) jika yang sama angka 0 pada urutan kedua adalah A’ diatas sudah disebutkan bahwa

angka 0 = Bar/’

Jadi kesimpulan dari contoh diatas adalah dari rumus :

H = AB + A’B + AB’ dapat disederhanakan menggunakan K-Map menjadi

BA / AB (boleh dibalik menurut abjad tetapi harus 1 teman atau tidak dapat dibalik dengan huruf yang

dipisahkan dengan penjumlahan atau pengurangan)

Penyederhanaan Tiga Variabel

Catatan : Bar = ‘

Tabel dari K-Map 3 variabel adalah seperti dibawah ini

Contoh

H = ABC + A’BC+A’B’C+AB’C

Maka cara pengerjaanya seperti dibawah ini

Bar / ‘ biasanya ditulis kedalam angka 0 sedangkan angka 1 adalah tanpa Bar / ‘

Dan dapat dipermudah lagi menjadi dibawah ini

Yang dapat disederhanakan dalam K-Map hanya 2 / kelipatan 2 dari kotak yang berdempetan dan sedangkan

jika seperti kotak diatas maka penyderhanaannya

Cara diatas adalah langsung mesederhanakan 4 kotak, sebenarnya dapat disederhanakan menjadi 2 kotak 2

kotak tetapi terlalu lama dan kita hanya menyingkat waktu saja menjadi 4 kotak langsung, terletak pada kotak

001 + 011+101 +111 yaitu cara penyederhanaan dengan cara menulis angka yang sama (1 lingkaran) dan

menerjemahkannya kedalam bentuk huruf seperti A, B, C.

Caranya :

011

011

101

111

1 yang sama adalah angka 1 yang dibelakang jadi jika letaknya dibelakang (keempat) adalah C (C diambil

dari tabel K-Map Diatas ). Jika yang sama angka 0 pada urutan keempat adalah C’ diatas sudah disebutkan

bahwa angka 0 = Bar/’

Jadi kesimpulan dari contoh diatas adalah dari rumus :

H = ABC + A’BC+A’B’C+AB’C dapat disederhanakan menggunakan K-Map menjadi C.

Penyederhanaan 4 variabel

Catatan : Bar = ‘

Tabel dari K-Map 4 variabel adalah seperti dibawah ini

Contoh

H = ABCD + ABCD’+AB’CD+ABC’D’
Maka cara pengerjaanya seperti dibawah ini

Bar / ‘ biasanya ditulis kedalam angka 0 sedangkan angka 1 adalah tanpa Bar / ‘

Dan dapat dipermudah lagi menjadi dibawah ini

Yang dapat disederhanakan dalam K-Map hanya 2 / kelipatan 2 dari kotak yang berdempetan dan sedangkan

jika seperti kotak diatas maka penyderhanaannya

Yaitu terletak pada kotak 1111 + 1011 dan 1111 + 1110 dan 1110 + 1100. Cara diatas menyederhanakannya dapat

dari sisi paling kanan dengan sisi paling kiri dalam 1 baris.

Cara penyederhanaan dengan cara menulis angka yang sama (1 lingkaran) dan menerjemahkannya kedalam

bentuk huruf seperti A, B, C, D.

Caranya :
1111

1011

1 11 yang sama adalah angka 1 yang pertama, ketiga, dan keempat adalah A, C, dan D (A, C, dan D diambil

dari tabel K-Map Diatas ) jika yang sama angka 0 pada urutan kedua adalah A’ dst diatas sudah disebutkan

bahwa angka 0 = Bar/’

1111

1110

111 yang sama adalah angka 1 yang pertama, kedua, dan ketiga adalah A, B, C (A, B, C diambil dari tabel K-

Map Diatas) jika yang sama angka 0 pada urutan kedua adalah A’ dst diatas sudah disebutkan bahwa angka 0 =

Bar/’

1110

1100

11 yang sama adalah angka 1 yang pertama dan kedua adalah A dan B (A dan B diambil dari tabel K-Map

Diatas) jika yang sama angka 0 pada urutan kedua adalah A’ dst diatas sudah disebutkan bahwa angka 0 =

Bar/’

Jadi kesimpulan dari contoh diatas adalah dari rumus :

H = AB + A’B + AB’ dapat disederhanakan menggunakan K-Map menjadi

ACD + ABC + AB (boleh dibalik menurut abjad tetapi harus 1 teman atau tidak dapat dibalik dengan huruf

yang dipisahkan dengan penjumlahan atau pengurangan).