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 x dan y dibuka => xy
Output c hanya ada jika dan
hanya jika x atau y dibuka => 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
-OoO-
