Matematika informatika 1 ALJABAR BOOLEAN
ALJABAR BOOLEAN Matematika yang digunakan untuk menganalisis dan menyederhanakan Gerbang Logika pada Rangkaian-rangkaian Digital Elektronika. Boolean pada dasarnya merupakan Tipe data yang hanya terdiri dari dua nilai yaitu “True” dan “False” atau “Tinggi” dan “Rendah” yang biasanya dilambangkan dengan angka “1” dan “0” pada Gerbang Logika ataupun bahasa pemrograman komputer.
Aljabar Boolean memiliki aplikasi yang luas dalam bidang keteknikan, antara lain dalam bidang jaringan pensaklaran dan rangkaian digital.
Contoh rangkaian pensaklaran pada rangkaian listrik: 1. Saklar dalam hubungan SERI: logika AND Lampu A
B
Sumber tegangan
2. Saklar dalam hubungan PARALEL: logika OR A Lampu B Sumber Tegangan
4
Contoh rangkaian seri
A
B
Lampu hanya Dalam menyala jika ekspresi A dan B Boolean ditutup hubungan seri (Closed) ini dinyatakan sebagai A.B
Contoh rangkaian paralel A
B
Lampu hanya Dalam menyala jika ekspresi salah satu dari Boolean A atau B dihubungan seri tutup (Closed) ini dinyatakan
sebagai A + B
Definisi Aljabar Boolean Misalkan terdapat - Dua operator biner: + dan
- Sebuah operator uner: ’
- B : himpunan yang didefinisikan pada operator +, , dan ’ - 0 dan 1 adalah dua elemen yang berbeda dari B.
(B, +, , ’) disebut aljabar Boolean jika untuk setiap a, b, c B berlaku aksioma-aksioma atau postulat Huntington berikut:
Postulat Huntington 1. Closure:
(i) a + b B (ii) a b B
2. Identitas:
(i) a + 0 = 0 + a = a (ii) a 1 = 1 . a = 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) (iii) (a . b) + c = (a + c) . (b + c)
5. Komplemen1:
(i) a + a’ = 1 (ii) a a’ = 0
8
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.
DALIL BOOLEAN X=0 ATAU X=1 0 . 0 = 0 1 + 1 = 1 0 + 0 = 0 1 . 1 = 1 1 . 0 = 0 . 1 = 0 1 + 0 = 0 + 1 = 1
Aljabar Boolean Dua-Nilai Aljabar Boolean dua-nilai: - B = {0, 1} - operator biner, + dan - operator uner, ’ - 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
a 0 1
a’ 1 0
LATIHAN
x
xy
y Gerbang AND
x
x+ y
y Gerbang OR
x'
Gerbang NOT (inverter)
x x 0 0
y y 0 0
x.y x.y
x x
y y
x+y x+y
0
0 0 1 1
1 1 0 0
0
0 0
0 0
0 0
0
1
1
1 1
1 1
1
1
0
1
1
1
1
0
x
x x 0 0
x’ x’ 1 1
1
0
Prinsip Dualitas Misalkan S adalah kesamaan (identity) di dalam aljabar Boolean yang melibatkan operator +, , dan komplemen, maka jika pernyataan S* diperoleh dengan cara mengganti + 0 1
dengan dengan dengan dengan
+ 1 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: (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
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+1b (Komplemen) =a+b (Identitas) (ii) adalah dual dari (i)
Latihan (A, +,*) Aljabar Boolean dimana A= {a,b} a + a = a; a + b = b + a; b + b = b; a * a = a; a * b = b * a; b*b=b Maka 1. a + (a * b) =..... Jawab: a + (a * b) = a ............. Hukum penyerapan
2. a * (a + b) =.... Jawab: a * (a + b) = a ............. Hukum penyerapan
Metode Konsensus Misal P1, P2 adalah perkalian dasar sedemikian sehingga tepat satu variabel sebut xk muncul sebagai komplemennya pada salah satu dari P1 dan P2. Maka yang dikatakan konsensus Q dari P1 dan P2 adalah perkalian (tanpa pengulangan) dari literal P1 dan literal P2, sesudah xk dan xk’ dihilangkan. Contoh : xyz’s dan xy’t mempunyai konsensus xz’st xy’ dan y mempunyai konsensus x
LATIHAN
Tentukan konsesus dari Aljabar Boolean berikut.. 1. xyz’s dan xy’t Jawab :
xz’st
2. x’yz dan x’yt Jawab:
tidak mempunyai konsensus
Penyederhanaan Fungsi Boolean Penyederhanaan fungsi Boolean dapat dilakukan dengan 2 cara: 1. Secara aljabar 1. Menggunakan Peta Karnaugh
1. Penyederhanaan Secara Aljabar Contoh: 1. f(x, y) = x + x’y = (x + x’)(x + y) --- aksioma distributif = 1 (x + y ) --- aksioma komplemen =x+y 2) f(x, y, z) = xy + x’z + yz = xy + x’z + yz(x + x’) --- aksioma komplemen = xy + x’z + xyz + x’yz = xy + xyz + x’z + x’yz = xy(1 + z) + x’z(1 + y) --- hukum dominasi = xy + x’z 20
LATIHAN
1) f(x, y, z) = x’y’z + x’yz + xy’ = x’z(y’ + y) + xy’ --- aksioma distributif = x’z . 1 + xz’ --- aksioma komplemen = x’z + xz’
2. Penyederhanaan dengan Peta Karnaugh a. Tabel Kebenaran dengan Dua Peubah No. Map
x
y
f (x, y)
0
0
0
x’y’
1
0
1
x’y
2
1
0
xy’
3
1
1
xy
22
Peta Karnaugh dengan dua peubah y 0
23
1
m0
m1
x 0
x’y’
x’y
m2
m3
1
xy’
xy
x 0
1
m0
m2
y 0
x’y’
xy’
m1
m3
1
x’y
xy
b. Tabel Kebenaran dengan Tiga Peubah
No. Map
x
y
z
f (x, y, z)
0
0
0
0
x’y’z’
1
0
0
1
x’y’z
2
0
1
0
x’yz’
3
0
1
1
x’yz
4
1
0
0
xy’z’
5
1
0
1
xy’z
6
1
1
0
xyz’
7
1
1
1
xyz
24
Peta Karnaugh dengan tiga peubah yz 00 m0 m1
m3
m2
m4 m5
m7
m6
m0 m2
m6
m4
m1 m3
m7
m5
25
01
x 0 x’y’z’ x’y’z 1
11
10
x’yz
x’yz’
xy’z’
xy’z
xyz
xyz’
xy 00
01
11
10
xyz’
xy’z’
xyz
xy’z
z 0 x’y’z’ x’yz’ 1 x’y’z
x’yz
LATIHAN
Diketahui (B, +, *, ‘) Aljabar Boolean, x,y, z, x’, y’, z’ Yang bukan merupakan perkalian dasar adalah.. 1. xyz’ 2. x’yzy’ 3. x’yz’ 4. x’y’z’
Contoh. Diberikan tabel kebenaran, gambarkan Peta Karnaugh. y 0 0 1 1 0 0 1 1
z 0 1 0 1 0 1 0 1
f(x, y, z) 0 0 1 0 0 0 1 1
yz 00
01
11
10
x 0
0
0
0
1
1
0
0
1
1
x 0 0 0 0 1 1 1 1
27
c. Tabel Kebenaran dengan Empat Peubah No. Map
w
x
y
z
f (w, x, y, z)
0
0
0
0
0
w’x’y’z’
1
0
0
0
1
w’x’y’z
2
0
0
1
0
w’x’yz’
3
0
0
1
1
w’x’yz
4
0
1
0
0
w’xy’z’
5
0
1
0
1
w’xy’z
6
0
1
1
0
w’xyz’
7
0
1
1
1
w’xyz
8
1
0
0
0
wx’y’z’
9
1
0
0
1
wx’y’z
10
1
0
1
0
wx’yz’
11
1
0
1
1
wx’yz
12
1
1
0
0
wxy’z’
13
1
1
0
1
wxy’z
1
1
1
0
wxyz’
1
1
1
1
wxyz
14 15
28
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’
wx 00
01
11
10
w’x’y’z’
w’xy’z’
wxy’z’
wx’y’z’
01 w’x’y’z
w’xy’z
wxy’z
wx’y’z
m0
m4
m12
m8
m1
m5
m13
m9
m3
m7
m15 m11
11
w’x’yz
w’xyz
wxyz
wx’yz
m2
m6
m14 m10
10
w’x’yz’
w’xyz’
wxyz’
wx’yz’
29
yz 00
Contoh. Diberikan tabel kebenaran, gambarkan Peta Karnaugh. w 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
wx
x 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
y 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
z 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
f(w, x, y, z) 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0
yz 00
01
11
10
00
0
1
0
0
01
0
0
1
1
11
0
0
0
1
10
0
0
0
0
30
Teknik Minimisasi Karnaugh
Fungsi
Boolean
1. Pasangan: dua buah 1 yang bertetangga yz 00
01
11
10
wx 00
0
0
0
0
01
0
0
0
0
11
0
0
1
1
10
0
0
0
0
Sebelum disederhanakan: f(w, x, y, z) = wxyz + wxyz’ Hasil Penyederhanaan: f(w, x, y, z) = wxy Bukti secara aljabar: f(w, x, y, z) = wxyz + wxyz’ = wxy(z + z’) = wxy(1) 31 = wxy
dengan
Peta
2. Kuad: empat buah 1 yang bertetangga yz 00
01
11
10
wx 00
0
0
0
0
01
0
0
0
0
11
1
1
1
1
10
0
0
0
0
Sebelum disederhanakan: f(w, x, y, z) = wxy’z’ + wxy’z + wxyz + wxyz’ Hasil penyederhanaan: f(w, x, y, z) = wx
32
Bukti secara aljabar: f(w, x, y, z) = wxy’ + wxy = wx(z’ + z) = wx(1) = wx yz 00
01
11
10
wx 00
0
0
0
0
01
0
0
0
0
11
1
1
1
1
10
0
0
0
0
33
Latihan yz 00
01
11
10
wx 00
0
0
0
0
01
0
0
0
0
11
1
1
0
0
10
1
1
0
0
Sebelum disederhanakan ? Hasil penyederhanaan ?
34
3. Oktet: delapan buah 1 yang bertetangga yz 00
01
11
10
0
0
0
0
0
0
0
0
11
1
1
1
1
10
1
1
1
1
wx 00 01
Sebelum disederhanakan: f(a, b, c, d) = wxy’z’ + wxy’z + wxyz + wxyz’ + wx’y’z’ + wx’y’z + wx’yz + wx’yz’ Hasil penyederhanaan: f(w, x, y, z) = w
35
Bukti secara aljabar: f(w, x, y, z) = wy’ + wy = w(y’ + y) =w yz 00
01
11
10
wx 00
0
0
0
0
01
0
0
0
0
11
1
1
1
1
10
1
1
1
1
36
Latihan Andaikan suatu tabel kebenaran telah diterjemahkan ke dalam Peta Karnaugh. Sederhanakan fungsi Boolean yang bersesuaian sesederhana mungkin. yz 00
01
11
10
wx 00
0
1
1
1
01
0
0
0
1
11
1
1
0
1
10
1
1
0
1
37
Latihan Minimisasi fungsi Boolean yang bersesuaian dengan Peta Karnaugh di bawah ini. yz 00
01
11
10
wx 00
0
0
0
0
01
0
1
0
0
11
1
1
1
1
10
1
1
1
1
38
Contoh. (Penggulungan/rolling) Sederhanakan fungsi Boolean yang bersesuaian dengan Peta Karnaugh di bawah ini. yz 00
01
11
10
wx 00
0
0
0
0
01
1
0
0
1
11
1
0
0
1
10
0
0
0
0
Jawab: f(w, x, y, z) = xy’z’ + xyz’ ==> belum sederhana
39
Penyelesaian yang lebih minimal: yz 00
01
11
10
wx 00
0
0
0
0
01
1
0
0
1
11
1
0
0
1
10
0
0
0
0
f(w, x, y, z) = xz’
40
===> lebih sederhana
Contoh. Sederhanakan fungsi Boolean f(x, y, z) = x’yz + xy’z’ + xyz + xyz’. Jawab: Peta Karnaugh untuk fungsi tersebut adalah: yz 00 x
0
01
11
10
1
1
1
1
1
Hasil penyederhanaan: f(x, y, z) = yz + xz’
41
Latihan Sederhanakan fungsi Boolean f(x, y, z) = x’yz + xy’z’ + xyz + xyz’. Buatlah Peta Karnaugh!
42
Contoh: (Kelompok berlebihan) Sederhanakan fungsi Boolean yang bersesuaian dengan Peta Karnaugh di bawah ini. yz 00
01
11
10
wx 00
0
0
0
0
01
0
1
0
0
11
0
1
1
0
10
0
0
1
0
Jawab:
f(w, x, y, z) = xy’z + wxz + wyz masih belum sederhana.
43
Penyelesaian yang lebih minimal: yz 00
01
11
10
wx 00
0
0
0
0
01
0
1
0
0
11
0
1
1
0
10
0
0
1
0
f(w, x, y, z) = xy’z + wyz
44
===> lebih sederhana
