Definisi Aljabar Boolean
Misalkan terdapat
- Dua operator biner: + dan . dan sebuah operator uner: (’).
- B : himpunan yang
didefinisikan pada operator(+, . , dan ’)
- 0 dan 1 adalah dua elemen
yang berbeda dari B.
Tupel (B, +, ×, ’)
disebut aljabar
Boolean jika untuk setiap a, b, c
Î B berlaku
aksioma-aksioma atau Postulat Huntingto
- Postulat Huntingto
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. Komplemen:(i) a + a’ = 1
(ii) a .a’ = 0
Aljabar Boolean Dua Nilai
Aljabar Boolean dua-nilai:
-
B = {0, 1}
-
operator
biner, + dan ×
-
operator
uner, ’
Kaidah untuk operator biner dan operator unerEkpresi Boolean
Misalkan (B, +, ×, ’) adalah sebuah aljabar Boolean. Suatu ekspresi Boolean dalam (B, +, ×, ’) adalah:
(i)
setiap elemen di dalam B,
(ii)
setiap peubah,
(iii) jika e1
dan e2 adalah ekspresi Boolean, maka e1 + e2,
e1 × e2, e1’
adalah ekspresi Boolean
Contoh: 0
1
a
b
a + b
a
× b
a’× (b + c)
a
× b’ + a
× b × c’ + b’, dan sebagainya
Prinsip Dualitas
Misal S adalah kesamaan (identity) di
dalam aljabar Boolean yang melibatkan operator +, ×, dan komplemen, maka jika pernyataan 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.
(i) (a × 1)(0 + a’) = 0 dualnya (a + 0) + (1 × a’) = 1
(ii) a(a‘ + b) = ab dualnya a + a‘b = a
+ b
Hukum Aljabar Boolean
1. Hukum identitas:
(i) a + 0 = a
(ii) a × 1 = a
|
7. Hukum
komutatif:
(i) a + b
= b + a
(ii) ab
= ba
|
|
2. Hukum
idempoten:
(i) a + a
= a
(ii) a × a = a |
8. Hukum
asosiatif:
(i) a + (b
+ c) = (a + b) + c
(ii) a
(b c) = (a b) c
|
|
3. Hukum
komplemen:
(i) a + a’
= 1
(ii) aa’
= 0
|
9. Hukum distributif:
(i) a +
(b c) = (a + b) (a
+ c)
(ii) a (b
+ c) = a b + a c
|
|
4. Hukum
dominansi:
(i) a × 0 =
0
(ii) a
+ 1 = 1
|
10. Hukum
De Morgan:
(i) (a
+ b)’ = a’b’
(ii) (ab)’ = a’ + b’
|
|
5. Hukum
involusi:
(i) (a’)’ = a
|
11. Hukum 0/1
(i) 0’ = 1
(ii) 1’ = 0
|
|
6. Hukum
penyerapan:
(i) a + ab
= a
(ii) a(a + b)
= a
|
Fungsi Boolean
- Fungsi Boolean (fungsi biner) adalah pemetaan dari Bn ke B melalui ekspresi Boolean.
f : Bn → B
Bn adalah himpunan yang beranggota pasangan terurut
ganda-n di dalam daerah asal B.
- Setiap ekspresi Boolean tidak lain merupakan fungsi Boolean.
Misalkan sebuah fungsi Boolean adalah
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}.
Contohnya, (1,
0, 1) yang berarti x = 1, y = 0, dan z = 1
sehingga f(1, 0,
1) = 1 × 0 × 1 + 1’ × 0 + 0’× 1 = 0 + 0 + 1 = 1 .
Komplemen Fungsi
- Cara pertama: menggunakan hukum De Morgan Hukum De Morgan untuk dua buah peubah, x1 dan x2,
- Cara kedua: menggunakan prinsip dualitas. menentukan dual dari ekspresi Boolean yang merepresentasikan f, lalu komplemenkan setiap literal di dalam dual tersebut
Bentuk Konanik
Ada dua macam bentuk kanonik:
- Penjumlahan dari hasil kali (sum-of-product atau SOP) →f(x, y, z) = x’y’z + xy’z’ + xyz Setiap suku (term) disebut minterm
- Perkalian dari hasil jumlah (product-of-sum atau POS) →g(x, y, z) = (x + y + z)(x + y’ + z)(x + y’ + z’)(x’ + y + z’)(x’ + y’ + z) Setiap suku (term) disebut maxterm
Penyederhanan Fungsi Boolean
Contoh. f(x, y) = x’y + xy’
+ y’
disederhanakan menjadi
f(x, y)
= x’ + y’
Penyederhanaan fungsi Boolean dapat dilakukan dengan 3
cara:
- Secara aljabar
- Menggunakan Peta Karnaugh
- Menggunakan metode Quine Mc Cluskey (metode Tabulasi)
Secara Aljabar
f(w, x, y,
z) = wy’ + wy
= w(y’ + y)
=
w
Menggunakan peta Karnaugh
Sebelum
disederhanakan: f(w, x, y, z) = wxy’z’ + wxy’z + wxyz
+ wxyz’ + wx’y’z’ + wx’y’z
+ wx’yz + wx’yz’
Hasil penyederhanaan: f(w, x,
y, z) = w
