Aljabar Boolean Adri Priadana
Pengantar Aljabar Boolean ditemukan oleh George Boole, pada tahun 1854. Boole melihat bahwa himpunan dan logika proposisi mempunyai sifat-sifat yang serupa (kemiripan hukum-hukum aljabar logika dan hukum-hukum aljabar himpunan).
Dalam buku The Laws of Thought, Boole memaparkan aturan-aturan dasar logika. Aturan dasar logika ini membentuk struktur matematika yang disebut aljabar Boolean. Aplikasi: perancangan rangkaian pensaklaran, rangkaian digital, dan rangkaian IC (integrated circuit) komputer
Definisi Aljabar Boolean DEFINISI. Misalkan B adalah himpunan yang didefinisikan pada dua operator biner, + dan , dan sebuah operator uner, ’. Misalkan 0 dan 1 adalah dua elemen yang berbeda dari B. Maka, tupel
disebut aljabar Boolean jika untuk setiap a, b, c B berlaku aksioma 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 Untuk setiap a B terdapat elemen unik a‘ B sehingga (i) a + a’ = 1 (ii) a a’ = 0
Berhubung elemen-elemen B tidak didefinisikan nilainya (kita bebas menentukan anggota-anggota B), maka terdapat banyak sekali aljabar boolean. Untuk mempunyai sebuah aljabar Boolean, orang harus memperlihatkan: 1. elemen-elemen himpunan B, 2. kaidah/aturan operasi untuk dua operator biner dan operator uner, 3. himpunan B, bersama-sama dengan dua operator tersebut, memenuhi keempat aksioma di atas
Aljabar himpunan dan aljabar logika proposisi juga merupakan aljabar Boolean karena memenuhi empat aksioma di atas. Dengan kata lain, aljabar himpunan dan aljabar proposisi adalah himpunan bagian (subset) dari aljabar Boolean.
Pada aljabar proposisi misalnya: B berisi semua proposisi dengan n peubah.
dua elemen unik berbeda dari B adalah T dan F, operator biner: dan , operator uner: ~ semua aksioma pada definisi di atas dipenuhi
Dengan kata lain adalah aljabar Booelan
Aljabar Boolean 2-Nilai Merupakan aljabar Boolean yang paling popular, karena aplikasinya luas. Pada aljabar 2-nilai (i) B = {0, 1}, (ii) operator biner: + dan , operator uner: ’ (iii) Kaidah untuk operator biner dan operator uner: a 0 0 1 1
b 0 1 0 1
ab 0 0 0 1
a 0 0 1 1
b 0 1 0 1
a+b 0 1 1 1
(iv) Keempat aksioma di atas dipenuhi
a 0 1
a’ 1 0
Ekspresi Boolean Ekspresi Boolean dibentuk dari elemen-elemen B dan/atau peubah-peubah yang dapat dikombinasikan satu sama lain dengan operator +, , dan ’. Contoh 1: 0 1 a b a+b ab a’ (b + c) a b’ + a b c’ + b’, dan sebagainya
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 Buktikan bahwa untuk sembarang elemen a dan b dari aljabar boolean maka kesamaaan berikut:
a(a’ + b) = ab adalah benar. Penyelesaian:
a(a’ + b) = a a’ + ab (Hukum Distributif) = 0 + ab (Hukum Komplemen) = ab (Hukum Identitas)
Fungsi Boolean Contoh-contoh fungsi Boolean:
1. 2. 3. 4. 5.
f(x) = x f(x, y) = x’y + xy’+ y’ f(x, y) = x’ y’ f(x, y) = (x + y)’ f(x, y, z) = xyz’
Setiap peubah di dalam fungsi Boolean, termasuk dalam bentuk komplemennya, disebut literal. Fungsi h(x, y, z) = xyz’ terdiri dari 3 buah literal, yaitu x, y, dan z’.
Bentuk Kanonik Ekspresi Boolean yang menspesifikasikan suatu fungsi dapat disajikan dalam dua bentuk berbeda. Pertama, sebagai penjumlahan dari hasil kali dan kedua sebagai perkalian dari hasil jumlah.
Contoh: f(x, y, z) = x’y’z + xy’z’ + xyz dan g(x, y, z) = (x + y + z)(x + y’ + z)(x + y’ + z’)(x’ + y + z’)(x’ + y’ + z) adalah dua buah fungsi yang sama.
Minterm: suku (term) di dalam ekspresi boolean mengandung literal yang lengkap dalam bentuk hasil kali Maxterm: suku (term) di dalam ekspresi boolean mengandung literal yang lengkap dalam bentuk hasil jumlah.
Contoh: f(x, y, z) = x’y’z + xy’z’ + xyz 3 buah minterm: x’y’z, xy’z’, xyz g(x, y, z) = (x + y + z)(x + y’ + z)(x + y’ + z’)(x’ + y + z’)(x’ + y’ + z) 5 buah maxterm: (x + y + z), (x + y’ + z), (x + y’ + z’), (x’ + y + z’), dan (x’ + y’ + z)
Misalkan peubah (variable) fungsi Boolean adalah x, y, dan z Maka: x’y bukan minterm karena literal tidak lengkap y’z’ bukan minterm karena literal tidak lengkap xy’z, xyz’, x’y’z minterm karena literal lengkap
(x + z) bukan maxterm karena literal tidak lengkap (x’ + y + z’) maxterm karena literal lengkap (xy’ + y’ + z) bukan maxterm Ekspresi Boolean yang dinyatakan sebagai penjumlahan dari satu atau lebih minterm atau perkalian dari satu atau lebih maxterm disebut dalam bentuk kanonik.
Jadi, ada dua macam bentuk kanonik: 1. Penjumlahan dari hasil kali (sum-of-product atau SOP) 2. Perkalian dari hasil jumlah (product-of-sum atau POS) Fungsi f(x, y, z) = x’y’z + xy’z’ + xyz dikatakan dalam bentuk SOP Fungsi g(x, y, z) = (x + y + z)(x + y’ + z)(x + y’ + z’)(x’ + y + z’) (x’ + y’ + z) dikatakan dalam bentuk POS
Cara membentuk minterm dan maxterm: Untuk minterm, setiap peubah yang bernilai 0 dinyatakan dalam bentuk komplemen, sedangkan peubah yang bernilai 1 dinyatakan tanpa komplemen.
Sebaliknya, untuk maxterm, setiap peubah yang bernilai 0 dinyatakan tanpa komplemen, sedangkan peubah yang bernilai 1 dinyatakan dalam bentuk komplemen.
Cara membentuk minterm dan maxterm dari tabel kebenaran untuk dua peubah:
x 0 0 1 1
y 0 1 0 1
Minterm Suku Lambang x’y’ m0 x’y m1 xy’ m2 xy m3
Maxterm Suku Lambang x+y M0 x + y’ M1 x’ + y M2 x’ + y’ M3
Cara membentuk minterm dan maxterm dari tabel kebenaran untuk tiga peubah:
x 0 0 0 0 1 1 1 1
y 0 0 1 1 0 0 1 1
z 0 1 0 1 0 1 0 1
Minterm Suku Lambang x’y’z’ m0 x’y’z m1 x‘y z’ m2 x’y z m3 x y’z’ m4 x y’z m5 x y z’ m6 xyz m7
Maxterm Suku Lambang x+y+z M0 x + y + z’ M1 x + y’+z M2 x + y’+z’ M3 x’+ y + z M4 x’+ y + z’ M5 x’+ y’+ z M6 x’+ y’+ z’ M7
Jika diberikan sebuah tabel kebenaran, kita dapat membentuk fungsi Boolean dalam bentuk kanonik (SOP atau POS) dari tabel tersebut dengan cara: mengambil minterm dari setiap nilai fungsi yang bernilai 1 (untuk SOP)
atau mengambil maxterm dari setiap nilai fungsi yang bernilai 0 (untuk POS).
Contoh Tinjau fungsi Boolean yang dinyatakan oleh Tabel di bawah ini. Nyatakan fungsi tersebut dalam bentuk kanonik SOP dan POS x 0 0 0 0 1 1 1 1
y 0 0 1 1 0 0 1 1
z 0 1 0 1 0 1 0 1
f(x, y, z) 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)
Contoh
POS
x 0 0 0 0 1 1 1 1
y 0 0 1 1 0 0 1 1
z 0 1 0 1 0 1 0 1
f(x, y, z) 0 1 0 0 1 0 0 1
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 Nyatakan fungsi Boolean f(x, y, z) = x + y’z dalam bentuk kanonik SOP dan POS. Penyelesaian: (a) SOP Lengkapi terlebih dahulu literal untuk setiap suku agar jumlahnya sama. x = x(y + y’) = xy + xy’ = xy (z + z’) + xy’(z + z’) = xyz + xyz’ + xy’z + xy’z’ dan 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)
Contoh (b) POS
f(x, y, z) = x + y’z = (x + y’)(x + z) Lengkapi terlebih dahulu literal pada setiap suku agar jumlahnya sama: 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)
Contoh Contoh 7: Nyatakan fungsi Boolean f(x, y, z) = xy + x’z dalam bentuk kanonik POS. Penyelesaian: f(x, y, z) = = = =
xy + x’z (xy + x’) (xy + z) (x + x’) (y + x’) (x + z) (y + z) (x’ + y) (x + z) (y + z)
Lengkapi literal untuk setiap suku agar jumlahnya sama: x’ + y = x’ + y + zz’ = (x’ + y + z) (x’ + y + z’) x + z = x + z + yy’ = (x + y + z) (x + y’+ z) y + z = y + z + xx’ = (x + y + z) (x’ + y + z) Jadi, f(x, y, z) = (x + y + z) (x + y’+ z) (x’+ y + z) (x’ + y + z’) atau f(x, y, z) = M0 M2M4 M5 = (0,2,4,5)
Konversi Antar Bentuk Kanonik Misalkan f adalah fungsi Boolean dalam bentuk SOP dengan tiga peubah: f(x, y, z) = (1, 4, 5, 6, 7) dan f ’adalah fungsi komplemen dari f, f ’(x, y, z) = (0, 2, 3) = m0+ m2 + m3 Dengan menggunakan hukum De Morgan, kita dapat memperoleh fungsi f dalam bentuk POS: f (x, y, z) = (f ’(x, y, z))’ = (m0 + m2 + m3)’ = m0’ . m2’ . m3’ = (x’y’z’)’ (x’y z’)’ (x’y z)’ = (x + y + z) (x + y’ + z) (x + y’ + z’) = M0 M2 M3 = (0,2,3) Jadi, f(x, y, z) = (1, 4, 5, 6, 7) = (0,2,3). Kesimpulan: mj’ = Mj
Rangkaian Logika Fungsi Boolean dapat juag direpresentasikan dalam bentuk rangkaian logika. Ada tiga gerbang logika dasar: gerbang AND, gerbang OR, dan gerbang NOT
x y
xy
Gerbang AND dua-masukan
x y
x+ y
Gerbang OR dua-masukan
x
x'
Gerbang NOT (inverter)
Contoh Nyatakan fungsi f(x, y, z) = xy + x’y ke dalam rangkaian logika. Penyelesaian: Ada beberapa cara penggambaran x xy
y
xy+x'y
Cara pertama:
x'
x
x'y
y
x y
xy
Cara kedua:
xy+x'y x' x'y
x
y xy
Cara ketiga:
xy+x'y x' x'y
Gerbang Logika Turunan Gerbang logika turunan: NAND, NOR, XOR, dan XNOR x y
(xy)'
Gerbang NAND
x y
(x+y)'
Gerbang NOR
x y
x y
Gerbang XOR
x y
( x y )'
Gerbang XNOR
Keempat gerbang di atas merupakan kombinasi dari gerbang-gerbang dasar, misalnya gerbang NOR disusun oleh kombinasi gerbang OR dan gerbang NOT: x
(x + y)'
y
ekivalen dengan
x
x+y
(x + y)'
y
Selain itu, dengan menggunakan hukum De Morgan, kita juga dapat membuat gerbang logika yang ekivalen dengan gerbang NOR dan NAND di atas: x' y'
x'y'
ekivalen dengan
x y
(x+y)'
Penyederhanaan Fungsi Boolean Menyederhanakan fungsi Boolean artinya mencari bentuk fungsi lain yang ekivalen tetapi dengan jumlah literal atau operasi yang lebih sedikit.
Contoh: f(x, y) = x + x’y
disederhanakan menjadi
f(x, y) = (x + x’)(x + y)
(Hukum distributif)
= 1 (x + y)
(Hukum komplemen)
=x+y
(Hukum identitas)
Dipandang dari segi aplikasi aljabar Boolean, fungsi Boolean yang lebih sederhana berarti rangkaian logikanya juga lebih sederhana (menggunakan jumlah gerbang logika lebih sedikit).
Penyederhanaan Fungsi Boolean • Tiga metode yang dapat digunakan untuk menyederhanakan fungsi Boolean: 1. Secara aljabar, menggunakan hukum-hukum aljabar Boolean. 2. Metode Peta Karnaugh. 3. Metode Quine-McCluskey (metode tabulasi) • Yang dibahas hanyalah Metode Peta Karnaugh
Peta Karnaugh • Peta Karnaugh (atau K-map) merupakan metode grafis untuk menyederhanakan fungsi Boolean. • Metode ini ditemukan oleh Maurice Karnaugh pada tahun 1953. Peta Karnaugh adalah sebuah diagram/peta yang terbentuk dari kotak-kotak (berbentuk bujursangkar) yang bersisian.
• Tiap kotak merepresentasikan sebuah minterm. • Tiap kotak dikatakan bertetangga jika minterm-minterm yang merepresentasikannya berbeda hanya 1 buah literal.
Peta Karnaugh Peta Karnaugh dengan dua peubah
y 0
1
y’
y
m0
m1
x 0
x’y’
x’y
x’
x’y’
x’y
m2
m3
1
xy’
xy
x
xy’
xy
Penyajian 1
Penyajian 2
Penyajian 3
Peta Karnaugh Peta Karnaugh dengan tiga peubah
00
yz 01
11
10
m0
m1
m3
m2
x 0
x’y’z’
x’y’z
x’yz
x’yz’
m4
m5
m7
m6
1
xy’z’
xy’z
xyz
xyz’
Peta Karnaugh Peta Karnaugh dengan empat peubah yz 00
01
11
10
m0
m1
m3
m2
wx 00
w’x’y’z’
w’x’y’z
w’x’yz
w’x’yz’
m4
m5
m7
m6
01
w’xy’z’
w’xy’z
w’xyz
w’xyz’
m12
m13
m15
m14
11
wxy’z’
wxy’z
wxyz
wxyz’
m8
m9
m11
m10
10
wx’y’z’
wx’y’z
wx’yz
wx’yz’
Peta Karnaugh Cara mengisi peta Karnaugh • Kotak yang menyatakan minterm diisi “1” • Sisanya diisi “0” • Contoh: f(x, y, z) = x’yz’ + xyz’ + xyz
Peta Karnaugh Contoh: f(x, y, z) = xz’ + y xz’: Irisan antara: x semua kotak pada baris ke-2 z’ semua kotak pada kolom ke-1 dan kolom ke-4 y: y semua kotak pada kolom ke-3 dan kolom ke-4
x 0 1
yz 00
01
11
10
0
0
1
1
1
0
1
1
xz’ + y
Peta Karnaugh Pengisian peta Karnaugh dari tabel kebenaran Tinjau hanya nilai fungsi yang memberikan 1. Fungsi Boolean yang merepresentasikan tabel kebenaran adalah f(x, y) = x’y’z + xy’z’ + xy’z+ xyz.
Peta Karnaugh Teknik Minimisasi Fungsi Boolean dengan Peta Karnaugh Penggunaan Peta Karnaugh dalam penyederhanaan fungsi Boolean dilakukan dengan cara menggabungkan kotak-kotak yang bernilai 1 dan saling bersisian.
Kelompok kotak yang bernilai 1 dapat membentuk: pasangan (dua), kuad (empat), oktet (delapan).
Peta Karnaugh Pasangan
Sebelum disederhanakan: f(w, x, y, z) = wxyz + wxyz’ Sesudah disederhanakan: f(w, x, y, z) = wxy
Peta Karnaugh Kuad (1)
Sebelum: f(w, x, y, z) = wxy’z’ + wxy’z + wxyz + wxyz’ Sesudah: f(w, x, y, z) = wx
Peta Karnaugh Kuad (2)
Sebelum: f(w, x, y, z) = wxy’z’ + wxy’z + wx’y’z’ + wx’y’z Sesudah: f(w, x, y, z) = wy’
Peta Karnaugh Oktet
Sebelum: f(w, x, y, z) = wxy’z’ + wxy’z + wxyz + wxyz’ + wx’y’z’ + wx’y’z + wx’yz + wx’yz’ Sesudah: f(w, x, y, z) = w
Peta Karnaugh Penggulungan (1)
Peta Karnaugh Penggulungan (2) Contoh: Sederhanakan f(x, y, z) = x’yz + xy’z’ + xyz + xyz’.
Sebelum: f(x, y, z) = x’yz + xy’z’ + xyz + xyz’ Sesudah: f(x, y, z) = yz + xz’
Peta Karnaugh Ketidakunikan Hasil Penyederhanaan • •
Hasil penyederhanaan dengan peta Karnaugh tidak selalu unik. Artinya, mungkin terdapat beberapa bentuk fungsi minimasi yang berbeda meskipun jumlah literal dan jumlah term-nya sama f(w,x,y,z) = w’x’y + w’xy’z + wxz’ + wyz + wx’y’
f(w,x,y,z) = w’x’y + w’xy’z + wxy + wy’z’ + wx’z
Peta Karnaugh Tips menyederhanakan dengan Peta Karnaugh Kelompokkan 1 yang bertetangga sebanyak mungkin Dimulai dengan mencari oktet sebanyak-banyaknya terlebih dahulu, kemudian kuad, dan terakhir pasangan.
Peta Karnaugh Contoh minimisasi 1:
Hasil penyederhanaan: f(w, x, y, z) = wy’ + yz’ + w’x’z
Peta Karnaugh Contoh minimisasi 2:
Hasil penyederhanaan: f(w, x, y, z) = z + xy + wx’y’
Peta Karnaugh Contoh minimisasi 3:
Hasil penyederhanaan: f(w, x, y, z) = wx + wz + wy + xyz
Peta Karnaugh Contoh minimisasi 4:
Peta Karnaugh
Peta Karnaugh Contoh minimisasi 5: Sederhanakan fungsi f(x, y, z, t) = xy’ + xyz + x’y’z’ + x’yzt’ Penyelesaian: Pengelompokan yang berlebihan zt
00
01
11
10
00
1
1
0
0
01
0
0
0
1
11
0
0
1
1
10
1
1
1
1
xy
Pengelompokan yang benar zt
00
01
11
10
00
1
1
0
0
01
0
0
0
1
11
0
0
1
1
10
1
1
1
1
xy
Fungsi minimasi: f(x, y, z, t) = y’z’ + xz + yzt’
Peta Karnaugh Contoh minimisasi 6: Sederhanakan rangkaian logika berikuit:
Peta Karnaugh Penyelesaian: Fungsi yang berkoresponden dengan rangkaian logika tsb: f(x, y, z) = x’yz + x’yz’ + xy’z’ + xy’z yz
00
01
0
10
1
1
x
11
10
0
1
1
1
0
0
Fungsi Boolean hasil minimisasi: f(x, y, z) = x’y + xy’
x
y x'y
Rangkaian logika hasil penyederhanaan:
x'y+xy'
xy'
Matur Nuwun
Adri Priadana
@adrxtwit AdriPriadana
