BAB 4
Aljabar Boolean
1. PENDAHULUAN
Aljabar Boolean merupakan lanjutan dari matakuliah logika matematika. Definisi aljabar boolean adalah suatu jenis manipulasi nilai-nilai logika secara aljabar. Contoh pengaplikasian aljabar boolean adalah pemikiran logika pada saat anda ingin membuat suatu aplikasi komputer. 2. HUKUM-HUKUM OPERASIONAL
Secara umum aljabar boolean didefinisikan sebagai himpunan yang terdiri dari himpunan boolean (0,1) dan mengandung operasi OR,AND dan NOT. Yang harus anda ketahui sebelum memulai materi ini adalah : NO 1 2 3
OPERASI OR AND NOT
TANDA + . ‚ atau -
CONTOH x+y x.y x‘ atau x
Hukum-hukum operasional : 1. Hukum Identitas : a. x + 0 = x b. x . 1 = x 3. Hukum Involusi : (x‘)‘ = x 5. Hukum De Morgan : a. (x +y)‘ = x‘.y‘ b. (x . y)‘ = x‘+y‘ 7. Hukum Komplemen : a. x + x‘ = 1 b. x . x‘ = 0 9. Hukum Idempoten : a. x + x = x b. x . x = x
2. Hukum Penyerapan : a. x+(x.y) = x b. x.(x+y) = x 4. Hukum Assosiatif : a. x+(y+z) = (x+y)+z b. x.(y.z) = (x.y).z 6. Hukum Komutatif : a. x+y = y+x b. x.y = y.x 8. Hukum Distributuf : a. x+(y.z) = (x+y).(x+z) b. x.(y+z) = (x.y)+(x.z) 10. Hukum Dominasi : a. x.0 = 0 b. x+1=1 Matematika Diskrit Oleh . Dwi Nurul Huda, ST
1
3. FUNGSI BOOLEAN
Pada Aljabar Boolean nilai variabel boolean adalah 0 dan 1, B = {0,1}. Dimana dalam aljabar boolean terdapat beberapa operator didalamnya yaitu : (1)
Operator biner ( OR dan AND)
(2)
Operator uner ( komplemen/NOT)
Setiap peubah Boolean termasuk komplemennya disebut sebagai literal. Contoh fungsi Boolean : f(x,y) = x’y’ 4. FUNGSI KOMPLEMEN
Fungsi komplemen dari suatu fungsi f, yaitu f’. Fungsi komplemen dapat dicari dengan cara : (1) Menggunakan Hukum De Morgan (lihat pada hukum-hukum operasional) Ex. f(x,y,z) = xyz+x’yz‘ f’(x,y,z) = (xyz+x’yz‘)’ f’(x,y,z) = (x’+y+z’).(x+y’+z) (2) Menggunakan prinsip dualitas, dengan mendualitaskan f terlebih dahulu kemudian komplemenkan tiap literalnya. Ex. f(x,y,z) = xyz+x’yz‘ Mendualitaskan nilai f f’(x,y,z) = (x+y+z).(x’+y+z‘) mengkomplemenkan seluruh literalnya f’(x,y,z) = (x’+y’+z’).(x+y’+z)
5. BENTUK KANONIK
Bentuk kanonik digunakan untuk menyederhanakan suatu fungsi boolean. Bentuk Kanonik dapat juga di gunakan untuk menentukan apakah dua ekspresi merupakan fungsi yang sama. Suatu fungsi Boolean yang dinyatakan tabel kebenaran dapat dikonversi menjadi bentuk aljabar.
Matematika Diskrit Oleh . Dwi Nurul Huda, ST
2
Bentuk kanonik terbagi menjadi dua macam, yaitu : 1. SOP (Sum Of Product – Penjumlahan dari hasil kali), dibentuk dari dua atau lebih fungsi AND yang di OR kan di dalam tanda kurung, dan di dalam tanda kurung tersebut bisa terdiri dari dua atau lebih variable. Tiap suku dalam SOP disebut sebagai minterm. Contoh : f (x, y, z) = (x’y’z) + (x’y’z’) + (xyz) 2. POS (Product Of Sum – perkalian dari hasil jumlah), dibentuk dari dua atau lebih fungsi OR yang di AND kan di dalam tanda kurung, dan di dalam tanda kurung tersebut bisa terdiri dari dua atau lebih variable. Tiap suku dalam SOP disebut sebagai maxterm. Contoh : f (x, y, z) = (x’+y’+z)( x’+y’+z’)(x+y+z) Berikut contoh table SOP (Sum Of Product – Penjumlahan dari hasil kali) dan POS ((Product Of Sum – perkalian dari hasil jumlah) untuk dua buah variable: Minterm
Maxterm
X
Y
Suku
Lambang
Suku
Lambang
0
0
x’y’
mo
xy
Mo
0
1
x’y
m1
x y’
M1
1
0
xy’
m2
x’y
M2
1
1
xy
m3
x’y’
M3
Berikut contoh table SOP (Sum Of Product – Penjumlahan dari hasil kali) dan POS ((Product Of Sum – perkalian dari hasil jumlah) untuk tiga buah variable:
Matematika Diskrit Oleh . Dwi Nurul Huda, ST
3
Minterm
Maxterm
X
y
z
Suku
Lambang
Suku
Lambang
0
0
0
x’y’z’
mo
x+y+z
Mo
0
0
1
x’y’z
m1
x+y+z’
M1
0
1
0
x’yz’
m2
x+y’+z
M2
0
1
1
x’yz
m3
x+y’+z’
M3
1
0
0
xy’z’
m4
x’+y+z
M4
1
0
1
xy’z
m5
x’+y+z’
M5
1
1
0
xyz’
m6
x’+y’+z
M6
1
1
1
xyz
m7
x’+y’+z’
M7
CONTOH SOAL :
1. Diberikan sebuah fungsi boolean berikut : f(x,y,z) = (x’y’z‘) + xy‘z buat kedalam bentuk kanonik fungsi diatas tersebut. Penyelesaian : Langkah 1 : buat tabel kebenarannya x
y
z
x’y’z’
xy‘z
f(x,y,z) = (x’y’z‘) + xy‘z
0
0
0
1
0
1
0
0
1
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
1
0
0
0
0
0
1
0
1
0
1
1
1
1
0
0
0
0
1
1
1
0
0
0 Matematika Diskrit Oleh . Dwi Nurul Huda, ST
4
Langkah 2 : tentukan SOP dan POS nya x
y
z
x’y’z’
xy‘z
f(x,y,z) = (x’y’z‘) + xy‘z
0
0
0
1
0
1
SOP
mo
0
0
1
0
0
0
POS
M1
0
1
0
0
0
0
POS
M2
0
1
1
0
0
0
POS
M3
1
0
0
0
0
0
POS
M4
1
0
1
0
1
1
SOP
m5
1
1
0
0
0
0
POS
M6
1
1
1
0
0
0
POS
M7
CARA MENCARI SOP : Kombinasi nilai-nilai peubah yang menghasilkan nilai fungsi sama dengan 1. Contoh pada table tersebut ada pada : x
y
z
f(x,y,z) = (x’y’z‘) + xy‘z
0
0
0
1
0
1
1
1
Lihat yang hasilnya bernilai 1
000 dan 011, maka : f(x, y, z) = (x’y’z’) + (x’yz) atau (dengan menggunakan lambang minterm) : f(x, y, z) = m0 + m5 = (0,5)
Matematika Diskrit Oleh . Dwi Nurul Huda, ST
5
CARA MENCARI POS : Kombinasi nilai-nilai peubah yang menghasilkan nilai fungsi sama dengan 0. Contoh pada table tersebut ada pada : x
y
z
f(x,y,z) = (x’y’z‘) + xy‘z
0
0
1
0
0
1
0
0
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
0
Lihat yang hasilnya bernilai 0
001, 010, 100, 101, 110 dan 111, maka : f(x, y, z) = (x+y+z’) + (x+y’+z) + (x’+y+z) + (x’+y+z’) + (x’+y’+z) + (x’+y’+z’) atau (dengan menggunakan lambang minterm) : f(x, y, z) = M1 M2 M3 M4 M6 M7 = π (1,2,3,4,6,7)
MENYATAKAN SOP & POS DARI FUNGSI BOOLEAN Untuk menyatakan fungsi boolean SOP atupun POS dapat dilakukan dengan cara melengkapi literalnya. Terdapat beberapa hukum aljabar boolean yang digunakan dalam melengkapi literalnya. 1. Hukum Identitas :
2. Hukum Distributif :
(i) a + 0 = a
(i) a + (b . c) = (a+b) . (a+c)
(ii) a . 1=a
(ii) a . (b + c) = a . b + a. C
3. Hukum Komplemen :
4. Hukum De Morgan :
(i) a + a‘ = 1
(i) (a + b)‘ = a‘. c‘
(ii) a . a = 0
(i) (a . b)‘ = a‘ + b‘
Matematika Diskrit Oleh . Dwi Nurul Huda, ST
6
CONTOH SOAL : CONTOH
2. Nyatakan fungsi boolean f(a,b,c) = a + b’c dalam bentuk kanonik SOP dan POS ! PENYELESAIAN : a. SOP (Sum Of Product) Lengkapi literal fungsi booleannya dahulu :
f(a,b,c) = a + b’c a = = = =
a .1 a . (b + b’) (a . b) + ( a . b’) ab+ ab’
Hukum Identitas Hukum Komplemen Hukum Distributif
f(a,b,c) = ab + ab’+ b’c ab = = = =
ab .1 ab . (c + c’) (a . b. c) + ( a . b . c‘) abc + abc‘
Hukum Identitas Hukum Komplemen Hukum Distributif
f(a,b,c) = abc + abc’ + ab’+ b’c ab‘ = = = =
ab‘ .1 ab‘ . (c + c’) (a . b‘. c) + ( a . b‘ . c‘) ab‘c + ab‘c‘
Hukum Identitas Hukum Komplemen Hukum Distributif
f(a,b,c) = abc + abc’ + ab’c + ab’c’+ b’c b‘c = b‘c .1 = b‘c . (a + a’) = (a . b‘. c) + ( a‘ . b‘ . c) = ab‘c + a‘b‘c
Hukum Identitas Hukum Komplemen Hukum Distributif
Matematika Diskrit Oleh . Dwi Nurul Huda, ST
7
berdasarkan pengerjaan melengkapi literal diatas , maka diperoleh :
f(a,b,c) = abc + abc’ + ab’c + ab’c’+ ab’c + a’b’c NB . Jika terdapat satu suku yang bentuk literalnya sama, maka cukup dituliskan satu kali saja
Sehingga diperoleh SOP : f(a,b,c) = a + b’c = abc + abc’ + ab’c + ab’c’+ a’b’c = m7+m6+m5+m4+m1 = Σ (1,4,5,6,7) b. POS (Product Of Sum) Lengkapi literal fungsi booleannya dahulu :
f(a,b,c) = a + b’c a + b’c = a + (b’c) = (a+b’)(a+c)
Hukum Distributif
f(a,b,c) = (a+b’)(a+c) a+ b’ = a + b’ + 0 = a + b‘ + (c .c’) = (a+b’+c) (a+b’+c’)
Hukum Identitas Hukum Komplemen Hukum Distributif
f(a,b,c) = (a+b’+c)(a+b’+c’)(a+c) a+ c = a +c + 0 = a + c + (b .b’) = (a+b+c) (a+b’+c)
Hukum Identitas Hukum Komplemen Hukum Distributif
Matematika Diskrit Oleh . Dwi Nurul Huda, ST
8
berdasarkan pengerjaan melengkapi literal diatas , maka diperoleh :
f(a,b,c) = (a+b’+c)+ (a+b’+c’)+ (a+b+c) + (a+b’+c) NB . Jika terdapat satu suku yang bentuk literalnya sama, maka cukup dituliskan satu kali saja
Sehingga diperoleh POS : f(a,b,c) = a + b’c = (a+b’+c) + (a+b’+c’) + (a+b+c) = M2.M3.M0 = π (0,2,3) 6. PENYEDERHANAAN FUNGSI BOOLEAN
Suatu fungsi Boolean seringkali mengandung operasi biner yang tidak perlu ataupun mengandung literal yang berlebihan, maka dapat dilakukan penyederhanaan dengan menggunakan : (1) Secara aljabar, dengan menggunakan aksioma-aksioma/hukum yang berlaku pada boolean. Penyederhanaan secara aljabar dapat mengurangi penggunaan literal yang berlebihan. Contoh (1): f(x,y) = x‘+xy --------> gunakan hukum distributif = (x‘+x).(x’+y) ----------> gunakan hukum komplemen = (1).(x‘+y) = x‘+y Contoh (2): f(x,y,z) = x‘yz+xyz+xy --------> gunakan hukum distributif = yz(x‘+x)+ xy ----------> gunakan hukum komplemen = yz+xy
Matematika Diskrit Oleh . Dwi Nurul Huda, ST
9
(2) Menggunakan Peta Karnaugh, direpresentasikan menggunakan kmetode pemetaan dapat meminimisasi fungsi yang kompleks. Karnaugh memperkenalkan Peta Karnaugh sebagai metode pemetaan untuk meminimasisasi fungsi yang kompleks seperti suatu rangkaian logika digital yang kompleks. Peta Karnaugh digambarkan dengan kotak bujur sangkar. Setiap kotak merepresentasikan minterm. Jumlah kotak bujur sangkar tergantung pada jumlah variabel dari suatu fungsi boolean. Rumus untuk menentukan jumlah kotak bujur sangkar dapat diketahui dengan menggunakan rumus :
2𝑛
, dimana n merupakan jumlah variabel
Peta karnaugh dapat digunakan untuk menyederhanakan fungsi boolean hingga lebih dari empat variabel,hanya pada modul ini saya hanya akan membahas penyederhanaan menggunakan peta karnaugh hingga empat variabel saja. A. PETA KARNAUGH DUA VARIABEL
Peta Karnaugh dua variabel digunakan untuk menyederhanakan fungsi boolean yang terdiri dari dua buah variabel. Berikut tabel peta karnaugh untuk dua buah variabel : Apabila : Suatu variabel bernilai 0 maka variable tersebut diberikan tanda aksen
Terdiri dari 4 buah kotak bujur sangkar. Jumlah kotak di peroleh dari rumus 2𝑛 , dimana n merupakan jumlah variabel. B. PETA KARNAUGH TIGA VARIABEL Peta Karnaugh tiga variabel digunakan untuk menyederhanakan fungsi boolean yang terdiri dari tiga buah variabel. Berikut tabel peta karnaugh untuk tiga buah variabel : Matematika Diskrit Oleh . Dwi Nurul Huda, ST
10
Terdiri dari 8 buah kotak bujur sangkar. Jumlah kotak di peroleh dari rumus 2𝑛 , dimana n merupakan jumlah variabel. Perhatikan tabel bujur sangkar diatas, aturannya berbeda dengan yang dua buah variabel, sehingga setelah m1 langsung m3 baru kemudian m2. Begitu pula baris selanjutnya m5-m7-m6. Pengaturan tempat tersebut jangan sampai tertukar. C. PETA KARNAUGH EMPAT VARIABEL
Peta Karnaugh empat variabel digunakan untuk menyederhanakan fungsi boolean yang terdiri dari empat buah variabel. Berikut tabel peta karnaugh untuk empat buah variabel :
Terdiri dari 16 buah kotak bujur sangkar. Jumlah kotak di peroleh dari rumus 2𝑛 , dimana n merupakan jumlah variabel. Perhatikan tabel bujur sangkar diatas, aturannya berbeda dengan yang dua buah tetapi hampir sama dengan tiga buah variabel.
Matematika Diskrit Oleh . Dwi Nurul Huda, ST
11
D. PETA KARNAUGH LIMA VARIABEL
Peta Karnaugh lima variabel digunakan untuk menyederhanakan fungsi boolean yang terdiri dari lima buah variabel. Peta karnaugh untuk lima buah variabel dibuat dengan anggapan terdapat dua buah peta karnaugh empat variabel yang disambungkan. Setiap sub-peta ditandai dengan garis tebal/ganda ditengahnya. Dua buah kotak dianggap bersisian jika secara fisik berdekatan dan merupakan pencerminan terhadap garis ganda. Berikut tabel peta karnaugh untuk lima buah variabel : 000
001
011
010
110
111
101 100
00
m0
m1
m3
m2
m6
m7
m5
01
m8
m9
m11 m10
m14 m15 m13 m12
11 m24 m25 m27 m26
m30 m31 m29 m28
10 m16 m17 m19 m18
m22 m23 m21 m20
m4
Garis pencerminan
CONTOH SOAL
Sederhanakan fungsi boolean berikut menggunakan peta karnaugh : (study kasus 3 buah variabel) f(x,y,z) = x’y’z‘ + x’yz‘
Matematika Diskrit Oleh . Dwi Nurul Huda, ST
12
Penyelesaian. 1. Buat Tabel kebenaran dari fungsi boolean tersebut x
y
z
x’y’z‘
x’yz‘
f(x,y,z) = x’y’z‘ + x’yz‘
0
0
0
1
0
1
0
0
1
0
0
0
0
1
0
0
1
1
0
1
1
0
0
0
1
0
0
0
0
0
1
0
1
0
0
0
1
1
0
0
0
0
1
1
1
0
0
0
m0
m2
2. Lihat hasil yang bernilai 1, kemudian konversikan menggunakan tabel bujur sangkar peta karnaugh 3 buah varaibel 1
0
0
1
0
0
0
0
Konversikan menggunakan table 3 buah variable yang sebelah kanan
3. Sederhanakan, dengan melihat tabel 3 buah variabel yang sebelah kanan (konversi ke tabel tersebut ). Untuk jenis variabel yang bentuknya (a‘ + a), (b+b‘) ataupun jenis variabel lainnya dapat dihilangkan. f(x,y,x) = x’y’z‘ + x’yz‘ f’(x,y,x) = x’z‘ + (y+y’) f’(x,y,x) = x’z‘ (Hasil penyederhanaannya ) (3) Menggunakan Metode Quine-McCluskey, penggunaan peta karnaugh memang dapat dilakukan hingga untuk penyederhanaan variable sampai dengan 5. Untuk variable lebih dari 5 akan menjadi sulit untuk diterapkan. Oleh sebab itu dibutuhkan metode lain yaitu metode Quine McCluskey/ metode tabulasi Matematika Diskrit Oleh . Dwi Nurul Huda, ST
13
Langkah-langkah metode Quine-Mc cluskey adalah : 1. Tuliskan tiap minterm fungsi Boolean menjadi string bit. Bila ada n variable maka panjang bit adalah n. missal untuk empat buah variable (w,x,y,z) maka angka 11 dituliskan dalam string bit : 1011. Dalam hal ini variable komplemen dinyatakan dengan ‘0’, variable yang bukan komplemen dinyatakan dengan ‘1’ 2. Kelompokan tiap minterm berdasarkan jumlah ‘1‘ yang dimiliki. Tujuannya untuk proses kombinasi antara kelompok minterm pada langkah selanjutnya 3. Kombinasikan minterm dalam n variabel dengan kelompok lain yang jumlah ‘1‘ nya berbeda 1, sehingga diperoleh bentuk prima yang terdiri dari n-1 variabel. Minterm yang dikombinasikan diberi tanda “√“. Sebagai contoh untuk 4 buah variabel, bila yang dikombinasikan adalah kelompok minterm 0(dengan string bit 0000) dan 1(dengan string bit 0001), maka kombinasinya adalah (0,1):000-, dimana pada bit terakhir dibuat tanda “-“ karena itulah bit yang berbedanya 4. Ikuti langkah (3) untuk kelompok kombinasi minterm dalam n-1 variabel dengan kelompok lain yang jumlah ‘1‘ nya berbeda satu, sehingga diperoleh bentuk prima yang terdiri dari n-2 variabel. Teruskan hingga tidak dimungkinkan lagi proses kombinasi 5. Ambil semua bentuk prima yang tidak bertanda “√“. Bentuk prima yang tidak bertanda “√“ merupakan hasil penyederhanaan fungsi Boolean tersebut. Contoh : Sederhanakan fungsi Boolean f(w,x,y,z) = Σ (1,3,5,7,9,11,13,15) Penyelesaian : 1. Minterm dalam bentuk SOP dituliskan dalam string bit dengan panjang 4, karena jumlah variabel adalah 4.hasilnya ditulis pada kolom(a). Pemisahan kelompok minterm berdasarkan jumlah angka“1“ yang dimiliki string bit ditandai dengan garis
0 1 3 5 9 7 11 13 15
(a) wxyz 0001 0011 0101 1001 0111 1011 1101 1111
√ √ √ √ √ √ √ √
Matematika Diskrit Oleh . Dwi Nurul Huda, ST
14
2. Pada kolom(b) dimasukan hasil kombinasi antara kelompok minterm. Semua minterm pada kolom(a) ditandai dengan “√“ karena semuanya masuk dalam kombinasi pada kolom(b) (b) Term w x y z 1,3 0 0 - 1 √ 1,5 0 - 0 1 √ 1,9 - 0 0 1 √ 3,7 0 - 1 1 √ 3,11 - 0 1 1 √ 5,7 0 1 - 1 √ 5,13 - 1 0 1 √ 9,11 1 0 - 1 √ 9,13 1 - 0 1 √ 7,15 - 1 1 1 √ 11,15 1 - 1 1 √ 13,15 1 1 - 1 √ 3. Pada kolom(c) dimasukan kombinasi dari kelompok minterm pada kolom(b). Semua minter pada kolom(b) ditandai dengan “√“ karena semuanya masuk dalam kombinasi pada kolom (c) (c) Term 1,3,9,11 1,5,3,7 1,9,3,11 1,9,5,13 3,7,11,15 5,13,7,15 9,11,13,15 9,13,11,15
w x y - 0 0 - - 0 - - 0 - - 1 - 1 1 - 1 - -
z 1 1 1 1 1 1 1 1
√ √ √ √ √ √ √ √
Matematika Diskrit Oleh . Dwi Nurul Huda, ST
15
4. Pada kolom(d) diberikan hasil kombinasi dari kolom(c) karena semuanya satu jenis yaitu hanya ada angka “1“ yang dimiliki karena kelompok mintermnya sama, maka tidak mungkin lagi disederhanakan/dikombinasikan. (d) term 1,3,9,11,5,13,7,15 1,5,3,7,9,11,13,15 1,5,3,7,9,13,11,15 1,9,2,11,5,3,7,15
w -
x y z - - 1 - - 1 - - 1 - - 1
Inilah hasil metode Quine –McCluskey. String bit “---1“ berarti hanya bit terakhir yang sisa dengan nilai“1“ yang artinya hanya variable z, sehingga solusi akhir dari f(w,x,y,z) = Σ (1,3,5,7,9,11,13,15) = z
Matematika Diskrit Oleh . Dwi Nurul Huda, ST
16
