Aljabar Boolean

Eki Ahmad Zaki Hamidi, ST.,MT.

Kita dapat menjadi berpengetahuan dengan pengetahuan orang lain

Tetapi kita tidak dapat menjadi bijaksana dengan
Menggunakan kearifan orang lain.
(Michael de Montaigne)

Chapter 7
 Pendahuluan

• Aljabar Boolean, sebagai salah satu cabang matematika,

pertama kali dikemukakan seorang matematikawan Inggris,
George Boole, pada tahun 1854.
• Dalam buku The Laws of Thought, Boole memaparkan
aturan-aturan dasar logika (yang kemudian dikenal sebagai
logika Boolean).
• Tahun 1938, Claude Shannon memperlihatkan penggunaan
aljabar Boolean untuk merancang rangkaian sirkuit yang
menerima masukan 0 dan 1 dan menghasilkan keluaran 0 dan
1.
• Aljabar Boolean telah menjadi dasar teknologi komputer
digital karena bekerja dengan mode operasi bit, 0 dan 1.

Ch07_Aljabar Boolean 2
 Definisi Aljabar Boolean

• Jika untuk setiap a, b, c ϵ B berlaku aksioma (sering

dinamakan Postulat Huntington) sebagai 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
Ch07_Aljabar Boolean 3
 Aljabar Boolean Dua-Nilai

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

1. Identitas
(i) 0 + 1 = 1 + 0 = 1
(ii) 1.0=0.1=0
2. Komutatif
Sudah jelas berlaku melihat simetri tabel operator
biner.
Ch07_Aljabar Boolean 4
 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

3. Distributif
(i) a . (b + c) = (a . b) + (a . c)
(ii) a + ( b . c) = ( a + b) . (a + c)
4. Komplemen
(i) a + a’ = 1 → 0 + 0’ = 0 + 1 = 1 dan 1 + 1’ = 1 + 0 = 1
(ii) a . a’ = 0 → 0 . 0’ = 0 . 1 = 0 dan 1 . 1’ = 1 . 0 = 0
Ch07_Aljabar Boolean 5
 Hukum-hukum Aljabar Boolean
1. Teorema Variabel Tunggal
Teorema variabel tunggal aljabar Boole diturunkan dari operasi logika dasar
OR, AND, dan NOT. Penurunan teorema variabel tunggal ditunjukkan
pada gambar berikut:

Teorema Ekspresi Sifat Rangkap

Satu dan Nol Teorema (1): A + 1 = 1 Teorema (2) : A.0 = 0

Identitas Teorema (3): A + 0 = A Teorema (4) : A.1 = A

Idempoten Teorema (5): A + A = A Teorema (6) : A.A = A

Komplemen Teorema (7): A + A' = 1 Teorema (8) : A.A' = 0

Involusi Teorema (9): A" = A -

Ch07_Aljabar Boolean 6
2. Teorema Variabel Jamak
Teorema-teorema variabel jamak aljabar Boole umumnya sama dengan
teorema-teorema pada aljabar biasa seperti ditunjukkan pada tabel berikut
ini:
Teorema Ekspresi Sifat Rangkap
Teorema (10) : Teorema (11):
Komutatif
A+B=B+A A.B = B. A

Teorema (12) : Teorema (13):

Asosiatif
A + (B + C) = (A + B) + C A (B.C) = (A.B) C

Teorema (14) : Teorema (15):

Distributif
A + B.C = (A + B)(A + C) A (B + C) = A.B + A.C

Teorema (16) : Teorema (17):

A + A.B = A A(A + B) = A
Absorpsi
Teorema (18) : Teorema (19):

A + A'.B = A + B A(A' + B) = A.B

Teorema (20) : Teorema (21):

De Morgan
A' + B' + ...' = A'.B' A'.B' ...' = A' + B' + ....'
Ch07_Aljabar Boolean 7
 Bentuk-bentuk Persamaan Logika
1. Bentuk Sum of Product (SOP)
SOP merupakan persamaan logika yang berbentuk operasi OR
dari suku-suku berbentuk operasi AND.
Contoh:
X = A’ B’ C+ A B’C’ + A B C’ + A B C .....persamaan (1)
Y = A B’ + A’ B .....persamaan (2)
P = A B’ C + A’ B + B C’ + A’ .....persamaan (3)
Q = A’ B + B’ C + A’ C’ .....persamaan (4)

Persamaan (1) dan (2) merupakan SOP bentuk standar karena

setiap sukunya mengandung semua variabel input yang ada,
sedangkan persamaan (3) dan (4) contoh SOP bentuk tak standar
karena tidak setiap sukunya mengandung semua variabel input.
Pada bentuk SOP standar, setiap sukunya dinamakan minterm,
disingkat dengan m (huruf kecil).

Ch07_Aljabar Boolean 8
 X = A’ B’ C + A B’ C’ + A B C’ + A B C

I II III IV

minterm
Minterm bersifat unik, yakni untuk semua kombinasi input yang ada hanya terdapat satu
kombinasi saja yang menyebabkan suatu minterm bernilai 1. Misal jika terdapat input A=0, B=0,
dan C=1 maka hanya terdapat sebuah miniterm yang bernilai 1 yakni:
A’ B ‘C = 0 0 1 = 1 . 1 . 1 = 1
Dengan demikian untuk suatu input yang memberikan nilai 1 pada salah satu minterm yang ada,
fungsi SOP standar selalu bernilai 1.
Karena pasangan input yang menyebabkan output bernilai 1 adalah 001 maka minterm tersebut
suku I dinamakan minterm (mɪ).
Jadi fungsi X dapat ditulis:
X = A’ B’ C + A B’ C’ + A B C’ + A B C Cara penulisan I ..Persamaan (5)
m₁ m₄ m₆ m₇
X = m₁ + m₄ + m₆ + m₇
X (A, B, C) = ∑ m (1,4,6,7) Cara penulisan II ...Persamaan (6)
Perhatikan bahwa fungsi X akan bernilai 1 untuk input-input yang bernilai desimal 1, 4, 6 dan 7
sesuai dengan nama-nama minterm penyusunnya.

Ch07_Aljabar Boolean 9
 Tabel Kebenaran Fungsi
X = A’ B’ C + A B’ C’ + A B C’ + A B C

INPUT OUTPUT
A B C X
0 0 0 0
0 0 1 1 m₁ = A B C
0 1 0 0
0 1 1 0
1 0 0 1 m₄ = A B C
1 0 1 0
1 1 0 1 m₆ = A B C
1 1 1 1 m₇ = A B C

Ch07_Aljabar Boolean 10
2. Bentuk Product of Sum (POS)
POS merupakan persamaan logika berbentuk AND dari
suku-suku berbentuk operasi OR.
Contoh:
R = (A’ + B’ + C)(A + B + C’)(A + B’ + C)(A’ + B + C) ..........persamaan (5)
S = (A’ + B’)(A + B) ...........persamaan (6)
T = (A’ + B’ + C)(A’ + B + C)(A + C’) ...........persamaan (7)
U = (A + B)(B + C’)(A’ + C’) ...........persamaan (8)
Persamaan (5) dan (6) merupakan POS standar karena
setiap sukunya mengandung semua varibel input yang ada,
sedangkan persamaan (7) dan (8) adalah POS tak standar
karena setiap sukunya mengandung semua variabel input.
Pada bentuk POS standar, setiap sukunya dinamakan
maxterm, disingkat dengan M (huruf besar).

Ch07_Aljabar Boolean 11
 R = (A’ + B’ + C)(A + B + C’)(A + B’ + C)(A’ + B + C)

I II III IV

Maxterm
Seperti halnya minterm, maxterm juga bersifat unik dalam hal ini, untuk semua kombinasi
input hanya terdapat satu kombinasi saja yang menyebabkan suatu maxterm bernilai 0. Misal
jika terdapat input A=1, B=1, dan C=0 maka hanya terdapat sebuah maxterm yang bernilai 0
yaitu :
A’ + B’ + C = 1 + 1 + 0 = 0 + 0 + 0 = 0
Jadi, untuk suatu input yang memberikan nilai 0 pada salah satu maxterm yang ada, fungsi
POS standar selalu bernilai 0. karena pasangan input yang menyebabkan output bernilai 0
salah satunya adalah 110 maka maxterm tersebut yakni suku I dinamakan maxterm 6 (M₆).
Jadi R dapat ditulis:
R = ( A’ + B’ + C)(A + B + C’)(A + B’ + C)(A’ + B + C) .....cara penulisan I

M₆ M₁ M₂ M₄
R = M₆ . M₁ . M₂ . M₄
R (A, B, C) = ∏ M ( 1, 2, 4, 6) .......cara penulisan II

Ch07_Aljabar Boolean 12
 Tabel Kebenaran Fungsi
R = ( A’ + B’ + C)(A + B + C’)(A + B’ + C)(A’ + B + C)

INPUT OUTPUT
A B C R
0 0 0 1
M₁ = A’+B’+C
0 0 1 0
0 1 0 0 M₂ = A+B+C’
0 1 1 1
1 0 0 0 M₄ = A+B’+C

1 0 1 1
1 1 0 0 M₆ = A’+B+C

1 1 1 1

Ch07_Aljabar Boolean 13
Mengubah Fungsi Bentuk Tak Standar
Menjadi Bentuk Standar
Jika suatu persamaan logika bentuk SOP Tak Standar ingin diubah menjadi bentuk
SOP Standar, maka dapat dilakukan dengan cara seperti contoh berikut:
a. Y = A B’ C’ + B’ C
b. Y = A B + C’
Menjadi bentuk standar!
Jawab:
a. Y = A B’ C’ + B’ C
Y = A B’ C’ + B’ C (A + A’) Ingat : A + A’ = 1
Y = A B’ C’ + A B’ C + A’ B’ C
Y (A, B, C) = ∑ m (1, 4, 5)
b. Y = A B + C’
Y = A B (C + C’) + C’ (B + B’)(A + A’)
Y = A B C + A B C’ + (B C’ + B’ C’)(A + A’)
Y = A B C + A B C’ + A B C’ + A’ B C’ + A B’ C’ + A’ B’ C’

ABC’
Y = A B C + A B C’ + A’ B C’ + A B’ C’ + A’ B’ C
Y (A, B, C) = ∑ m (0, 2, 4, 6, 7)

Ch07_Aljabar Boolean 14
 Memperoleh Persamaan Bentuk
Standar dari Tabel Kebenaran
Contoh: Tuliskan persamaan logika bentuk SOP Standar dan POS Standar
yang diperoleh dari tabel kebenaran berikut ini:

INPUT OUTPUT
A B Y
M₀ = A + B
0 0 0
m₁ = A’ B
0 1 1
m₂ = A B’
1 0 1
M₃ = A’ + B’
1 1 0

a. Bentuk SOP Standar: b. Bentuk POS Standar

Y = m₁ + m₂ Y = M₀ . M₃
Y=AB+AB Y = (A + B)(A + B)
Y (A, B) = ∑ m (1, 2) Y (A, B) = ∏ M (0,3)

Ch07_Aljabar Boolean 15
 Rangkaian untuk persamaan diatas adalah:
a. Y(A, B) = ∑ m(1,2)

b. Y(A, B) = ∏ M(0,3)

Ch07_Aljabar Boolean 16
 Penyederhanaan Secara Aljabar

Untuk mempermudah proses implementasi rangkaian logika, langkah

pertama yang perlu dilakukan adalah mengasumsikan bahwa setiap
rangkaian logika memiliki bentuk yang tidak efisien, selanjutnya dilakukan
pengujian bentuk minimumnya, jika belum minimum diteruskan dengan
penyederhanaan, dan diimplementasikan.
Contoh:
1. Sederhanakan persamaan Y = A B’ D + A B’ D’!
Jawab: Y = A B’ D + A B’ D’
= A B(D + D’)
Jadi Y = A B’  Ingat D + D’ = 1
Rangkaiannya adalah:

Ch07_Aljabar Boolean 17
 Persamaan Y dimanipulasi sedemikian rupa
sehingga sukunya mengandung faktor (D + D’).
Faktor tersebut dapat dieliminasi atau dihilangkan
karena melalui teorema komplemen (teorema 7),
faktor (D + D’) bernilai 1. Hal ini merupakan salah
satu cara meminimalisasi rangkaian dengan Aljabar
Boole yakni dengan mengarahkan persamaan agar
mengandung faktor seperti teorema 7.

Ch07_Aljabar Boolean 18
 Untuk membuktikannya kedua rangkaian tersebut, disusun tabel
kebenarannya:
Tabel Kebenaran Y₁ = A B’ D + A B’ D’ dan Y₂ = A B’

INPUT OUTPUT TIAP GERBANG OUTPUT

A B D B’ D’ AB’D AB’D’ Y₁ Y₂
0 0 0 1 1 0 0 0 0
0 0 1 1 0 0 0 0 0
0 1 0 0 1 0 0 0 0
0 1 1 0 0 0 0 0 0
1 0 0 1 1 0 1 1 1
1 0 1 1 0 1 0 1 1
1 1 0 0 1 0 0 0 0
1 1 1 0 0 0 0 0 0

Ch07_Aljabar Boolean 19
2. Sederhanakan persamaan X = (A’ + B)(A + B)!
Jawab:
X = (A’ + B)(A + B)
= A’A + A’B + BA + BB
= 0 + A’B + BA + B ingat A’A = 0 dan BB = B
= A’B + AB + B
= B (A + A’ + 1)
X = B ingat A + A’ + 1 = 1
Rangkaiannya:

Pada contoh 2 ditunjukkan bahwa persamaan dimanipulasi sehingga sukunya

mengandung faktor (A + A + 1). Berdasarkan teorema 1 atau teorema satu
dan nol, faktor tersebut bernilai 1 sehingga dapat dieliminasi.
Ch07_Aljabar Boolean 20
3. Sederhanakan persamaan Z = ACD + A’BCD!
Jawab :
Z = ACD + A’BCD
= CD(A + A’B)
= CD(A + B) ingat A + A’B = A + B
Z = ACD + BCD
Rangkaiannya:

Pada contoh 3, persamaan diarahkan agar sukunya mengandung faktor

berbentuk (A + A’B). Menurut teorema absorpsi atau teorema 18, faktor (A
+ A’B) sama dengan (A + B).

Ch07_Aljabar Boolean 21
4. Sederhanakan Persamaan Y = (A’ + C)(B + D’)!
Jawab :
Y = (A’ + C)(B + D’)
= (A’ + C) + (B + D’) Ingat teorema de Morgan
= (A”.C’) + (B’.D”) Ingat teorema de Morgan
Y = A.C’ + B’.D
Rangkaiannya:

22
5. Sederhanakan persamaan Z = ABC + AB’(A”C”)!
Jawab:
Z = ABC + AB’(A” C”)
Z = ABC + AB’(A” + C”) ingat teorema de Morgan
Z = ABC + AB’(A + C) ingat teorema de Morgan
Z = ABC + AB’A + AB’C
Z = ABC + AB’ + AB’C ingat teorema idempoten AA = A
Z = AB’ + (AB’C + ABC)
Z = AB’ + AC(B’ + B)
Z = AB’ + AC ingat B + B = 1
Z = A(B’ + C)
Rangkaiannya:

Ch07_Aljabar Boolean 23
6. Sederhanakan fungsi Y = ABC + AB C’ + A B’ C!
Jawab:
Cara I : Y = ABC + AB C’ + A B’C
Y = AB(C + C’) + A B’ C
Y = AB (1) + A B’ C ingat teorema komplemen: C + C’ = 1
Y = AB + A B’ C
Y = A(B + B’ C)
Y = A(B + C) ingat teorema distributif: B + B’ C = B + C
Y = AB + AC
Cara II : Y = ABC + A B C’ + A B’ C
Y = ABC + A B C’ + A B’ C + ABC ingat idempoten: ABC + ABC = ABC
Y = (ABC + A B C’) + (A B’ C + ABC)
Y = AB(C + C’) + AC(B + B’)
Y = AB (1) + AC (1) ingat teorema komplemen B + B’ = 1 dan C + C’ = 1
Y = AB + AC atau Y = A(B + C)
Rangkaiannya:

24
 Metode Peta Karnaugh
1. Memperoleh Bentuk Minimum dari Persamaan yang Diketahui.
Langkah pertama cara memperoleh bentuk minimum dari persamaan logika
menggunakan metode Peta Karnaugh (Peta-K) adalah dengan memastikan bahwa
persamaan tersebut bentuk standar.
Contoh: Sederhanakan fungsi Y = A’BC + AB’C + ABC + BC’ dengan menggunakan
Aljabar Boole dan Peta Karnaugh.
Jawab:
Dengan menggunakan Aljabar Boole
Y = A’BC + AB’C + ABC + BC’
Y = A’BC + AB’C + ABC + BC’ + ABC
Y = (A’BC + ABC) + (AB’C + ABC) + BC’
Y = BC(A’ + A) + AC(B’ + B) + BC’
Y = BC (1) + AC (1) + BC’
Y = BC + AC + BC’
Y = AC + (BC + BC’)
Y = AC + B(C + C’)
Y = AC + B (1)
Y = AC + B

Ch07_Aljabar Boolean 25
• Dengan Metode Peta Karnaugh
a. Langkah Pertama:
Y = A’BC + AB’C + ABC + BC’, pastikan bahwa persamaan diatas dalam bentuk SOP
Standar.
Y = A’BC + AB’C + ABC + BC’
Y = A’BC + AB’C + ABC + BC’(A + A’)
Y = A’BC + AB’C + ABC + ABC’ + A’BC’
Y = m₃ + m₅ + m₇ + m₆ + m₂
Y (A,B,C) = ∑ m(2,3,5,6,7)
b. Langkah kedua:
Menyusun petak-petak sebanyak 2ⁿ dimana n adalah jumlah variable input:
Bentuk Peta untuk 3 variabel input:

atau

Ch07_Aljabar Boolean 26
Bentuk yang lebih sederhana

atau

c. Langkah ketiga
Memasukkan minterm persamaan kedalam petak-petak yang sesuai.

atau

Gambar Peta Karnaugh untuk persamaan

Y(A,B,C) = ∑ m(2,3,5,6,7)
Ch07_Aljabar Boolean 27
d. Langkah Keempat
Memberi tanda lup pada setiap minterm terisolasi
1) Gabungan 2 minterm

Ch07_Aljabar Boolean 28
2) Gabungan 4 minterm (Quad)
Contoh peta Karnaugh yang mengandung Quad

Ch07_Aljabar Boolean 29
3) Gabungan 8 minterm (Octet)
Contoh Peta Karnaugh yang mengandung Octet

Ch07_Aljabar Boolean 30
e. Langkah kelima
memberi tanda lup pada minterm yang hanya dapat bergabung dengan 1
minterm lainnya (gabungan 2 minterm)

atau

f. Langkah keenam
memberi tanda lup pada gabungan empat minterm

atau

Ch07_Aljabar Boolean 31
g. Langkah ke tujuh
memberi tanda lup pada gabungan 8 – minterm. Pada contoh ini tidak
terdapat octet.
h. Langkah ke delapan
membuang variabel-variabel yang berbeda dan menggunakan variabel-
variabel yang sama sebagai suku persamaan dari gabungan minterm yang
diperoleh. Untuk minterm yang terisolasi, suku persamaannya tetap tidak
mengalami reduksi.
i. Langkah Ke sembilan
Membentuk persamaan minimum dengan cara melakukan operasi OR
terhadap suku-suku persamaan yang diperoleh dari gabungan minterm.

atau

Sesuai langkah kesembilan persamaan minimum yang dihasilkan Y = AC + B

Ch07_Aljabar Boolean 32
2. Memperoleh Bentuk Minimum dari Tabel Kebenaran
Susunlah rangkaian yang paling minimum dari tabel kebenaran berikut ini!

Jawab
Dari tabel diatas dapat diperoleh persamaan SOP standar:
Y ( A, B, C) = ∑ m(1,2,3,5,7)
Peta Karnaugh untuk fungsi Y di peroleh dari tabel kebenaran tersebut adalah:

Dari peta-K tersebut terlihat bahwa fungsi Y belum minimum, dan masih dapat disederhanakan
menjadi:
Y = A’B + C
Ch07_Aljabar Boolean 33
3. Kondisi Diabaikan (Don’t Care Condition)
Rangkaian logika hampir semuanya selalu memberikan output 0 dan 1, untuk suatu
kombinasi input yang diberikan. Selain itu, terdapat pula rangkaian logika dengan beberapa
kombinasi input yang dalam kenyataannya tidak pernah ada. Contohnya input kode BCD,
inputnya hanya 10 kombinasi yaitu 0000 – 1001, karena kode BCD mempresentasikan
bilangan desimal dari 0 – 9. Dengan kata lain kombinasi 1010 – 1111 tidak pernah ada,
outputnya diberi tanda X yang berarti diabaikan (don’t care condition). Tabel berikut
menunjukan watak rangkaian detektor bilangan prima dengan input kode BCD.
INPUT OUTPUT
A B C D Y
0 0 0 0 0
0 0 0 1 0
0 0 1 0 1
0 0 1 1 1
0 1 0 0 0
0 1 0 1 1
0 1 1 0 0
0 1 1 1 1
1 0 0 0 0
1 0 0 1 0
1 0 1 0 X
1 0 1 1 X
1 1 0 0 X
1 1 0 1 X
1 1 1 0 X
1 1 1 1 X
Ch07_Aljabar Boolean 34
 Contoh lain tabel kebenaran dengan kondisi diabaikan
INPUT OUTPUT
A B C Y
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 X
1 0 0 X
1 0 1 1
1 1 0 1
1 1 1 1
Peta Karnaugh yang mengandung kondisi diabaikan, X dapat dipilih bernilai 0 atau 1.
Pemilihan nilai X dilakukan sedemikian rupa sehingga dari peta karnaugh tersebut
dapat diperoleh persamaan paling sederhana.

35
36