materi aljabar boolean
ALJABAR BOOLEAN
Aljabar boolean adalah cabang ilmu
matematika yang diperlukan untuk mempelajari desain logika dari suatu sistem
digital yang merupakan operasi aritmatik pada bilangan boolean (bilangan yang
hanya mengenal 2 keadaan yaitu False/True, Yes/No, 1/0) atau bisa disebut
bilangan biner.
Aksioma Aksioma yang berlaku dalam
aljabar boolean:
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
Ekspresi
Boolean
· Misalkan (B , + , ∙ , ‘) adalah
sebuah aljabar boolean.
· Suatu ekspresi Boolean dalam (B, + , ∙ , ‘) dapat berbentuk :
(i) Elemen di dalam B, ex : 0 dan 1
(ii) Peubah / literal / variabel, ex
: a , b, c
(iii) Jika e1 dan e2 adalah ekspresi Boolean, maka e1 + e2 , e1 ∙ e2 , e1’ adalah ekspresi
Boolean
Contoh :
a + b
a ∙ b
a’ ∙ (b + c)
a ∙ b’
+ a ∙ b ∙ c’ + b’
dsb.
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 (di lambangkan
dengan ‘=’) jika keduanya bernilai sama untuk setiap nilai-nilai pada n peubah.
Contoh : a ∙ (b + c) = (a ∙ b) + (a ∙ c)
- Catatan : tanda titik (∙) dapat hilang dari
penulisan ekpresi Boolean, kecuali :
(i) a(b + c) = ab + ac
(ii) a + bc = (a + b) (a + c)
(iii) a ∙ 0 , bukan a0
Prinsip
Dualitas
Missal S adalah kesamaan (identity) di dalam aljabar Boolean
yang melibatkan operator +, ∙ , dan
komplemen, maka jika pertanyaan 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 : (a ∙ 1)(0 + a’) = 0 dualnya (a + 0 ) + (1 ∙ a’) = 1
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
|
Fungsi Boolean
Fungsi Boolean (fungsi biner) adalah pemetaan dari Bn ke B melalui ekspresi Boolean, :
f : Bn → B
B adalah himpunan yang beranggotakan
pasangan terurut ganda –n (odered n-tuple) di dalam daerah asal B.
Setiap ekspresi Boolean merupakan
fungsi Boolean
Contoh :
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}
penyelesaian
: (1,0,1) yang berarti x=1, y=0, z=1
sehingga
f(1,0,1) = 1 ∙ 0 ∙ 1 + 1’ ∙ 0 + 0’ ∙ 1 = 0 + 0 + 1 = 1
Bentuk
Kanonik
1. Penjumlahan
dari hasil kali (Sum Of Product / SOP)
Contoh : f(x,y,z)
= x’y’z + xy’z’ + xyz
Setiap
suku (term) disebut minterm
2. Perkalian
dari hasil jumlah (Produck Of Sum / POS)
Contoh : g(x, y, z)
= (x + y + z)(x + y’
+ z)(x + y’ + z’)
(x’
+ y + z’)(x’ + y’ + z)
Setiap suku (term)
disebut maxterm
Minterm
|
Maxterm
|
|||||
x
|
y
|
Suku
|
Lambang
|
Suku
|
Lambang
|
|
0
0
1
1
|
0
1
0
1
|
x’y’
x’y
xy’
x y
|
m0
m1
m2
m3
|
x + y
x + y’
x’ + y
x’ + y’
|
M0
M1
M2
M3
|
|
Minterm
|
Maxterm
|
|||||
x
|
y
|
z
|
Suku
|
Lambang
|
Suku
|
Lambang
|
0
0
0
0
1
1
1
1
|
0
0
1
1
0
0
1
1
|
0
1
0
1
0
1
0
1
|
x’y’z’
x’y’z
x‘y z’
x’y z
x y’z’
x y’z
x y z’
x y z
|
m0
m1
m2
m3
m4
m5
m6
m7
|
x + y + z
x + y + z’
x + y’+z
x + y’+z’
x’+ y + z
x’+ y + z’
x’+ y’+ z
x’+ y’+ z’
|
M0
M1
M2
M3
M4
M5
M6
M7
|
Konversi
Antar Bentuk Kanonik
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
Aplikasi
Aljabar Boolean
1. Jaringan
Pensaklaran (Switching Network)
Saklar
adalah objek yang mempunyai dua keadaan yaitu buka dan tutup.
Tiga
bentuk gerbang sederhana :
Output b hanya ada jika dan hanya jika x dibuka
=> x
Output b hanya ada jika dan hanya jika xdan y dibuka
=> xy
Output c hanya ada
jika dan hanya jika x atau ydibuka => x + y
2. Rangkaina
Digital Elektronik
Penyederhanaan Fungsi Boolean
Contoh :
f(x,y) = x’y + xy’ + y’ di
sederhanakan → f(x,y) = x’ + y’
* Penyederhanaan fungsi Boolean
dapat dilakukan dengan 3 Cara : *
1. Secara Aljabar
Contoh :
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
2. Peta Karnaugh
Cara untuk menyederhanakan
ekspresi atau pernyataan dari Aljabar Boole. Caranya dengan menggambarkan
kotak-kotak yang berisi “Minterm” (Minimum-Terms).
*
Peta Karnaugh dengan 2 Peubah
*
Peta Karnaugh dengan 3 Peubah
* Peta Karnaugh dengan 4 Peubah
3. Metode Quine Mc Cluskey
(Metode Tabulasi)
* Pasangan :
dua buah 1 yang bertetangga
Hasil : f(w, x, y, z) = wxyz + wxyz’
f(w, x, y, z) = wxyz + wxyz’
= wxy(z + z’)
= wxy(1)
= wxy
* Kuad: empat buah 1 yang bertetangga
Hasil : f(w, x, y, z) = wxy’z’ + wxy’z + wxyz + wxyz’
f(w, x, y, z)
= wxy’ + wxy
= wx(z’ + z)
= wx(1)
= wx
Keadaan
Don’t Care
Kondisi ini terjadi misalnya
pada rangkaian “Flip-flop” dimana beberapa kombinasi variabel input akan
menghasilkan output yang tidak tentu (dapat “1”, dapat “0”) sehingga kombinasi
tesebut dapat diabaikan (Don’t Care).
Tabel
w
|
x
|
y
|
Z
|
desimal
|
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
|
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
|
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
|
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
|
0
1
2
3
4
5
6
7
8
9
don’t care
don’t care
don’t care
don’t care
don’t care
don’t care
|
Contoh : Diberikan Tabel
Minimisasi fungsi f sesederhana mungkin.
a
|
b
|
C
|
d
|
f(a, b, c, d)
|
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
|
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
|
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
|
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
|
1
0
0
1
1
1
0
1
X
X X X X X X X |
Jawab: Peta Karnaugh dari fungsi tersebut adalah:
Hasil penyederhanaan: f(a, b, c, d)
= bd + c’d’ + cd
Komentar
Posting Komentar