1Definisi
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.
Tupel
(B,
+, ×, ’)
disebut aljabar Boolean jika untuk setiap a, b,
c Î B
berlaku aksioma-aksioma atau postulat Huntington berikut:
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[1]: (i)
a + a’ = 1
(ii) a ×
a’ = 0
-
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
2.
Aljabar
Boolean Dua-Nilai
Aljabar
Boolean dua-nilai:
-
B = {0, 1}
-
operator
biner, + dan ×
-
operator
uner, ’
-
Kaidah
untuk operator biner dan operator uner:
a
|
b
|
a × b
|
A
|
b
|
a
+ b
|
a
|
a’
|
||
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
||
0
|
1
|
0
|
0
|
1
|
1
|
1
|
0
|
||
1
|
0
|
0
|
1
|
0
|
1
|
||||
1
|
1
|
1
|
1
|
1
|
1
|
-
Cek
apakah memenuhi postulat Huntington:
1.
Closure : jelas berlaku
2.
Identitas:
jelas berlaku karena dari tabel dapat kita lihat bahwa:
(i) 0 + 1 = 1 + 0 = 1
(ii)
1 ×
0 = 0 × 1 = 0
3.
Komutatif: jelas berlaku dengan melihat simetri tabel
operator biner.
4.
Distributif:
(i) a ×
(b + c) = (a × b) + (a × c) dapat ditunjukkan benar dari tabel operator biner di atas dengan membentuk tabel kebenaran:
a
|
b
|
c
|
b
+ c
|
a
×
(b + c)
|
a
×
b
|
a
×
c
|
(a × b) + (a × c)
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
(ii)
Hukum distributif a + (b × c) = (a + b) ×
(a + c) dapat ditunjukkan benar dengan membuat tabel kebenaran dengan
cara yang sama seperti (i).
5.
Komplemen:
jelas berlaku karena Tabel 7.3 memperlihatkan bahwa:
(i) a + a‘
= 1, karena 0 + 0’= 0 + 1 = 1 dan 1 + 1’= 1 + 0 = 1
(ii) a
×
a = 0, karena 0 ×
0’= 0 ×
1 = 0 dan 1 ×
1’ = 1 ×
0 = 0
Karena
kelima postulat Huntington dipenuhi, maka terbukti bahwa B = {0, 1}
bersama-sama dengan operator biner + dan × operator
komplemen ‘ merupakan aljabar Boolean.
3.
Ekspresi
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
- 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 (dilambangkan dengan ‘=’) jika keduanya mempunyai nilai yang sama untuk setiap pemberian nilai-nilai kepada n peubah.
Contoh:
a × (b + c)
= (a . b) + (a × c)
Contoh.
Perlihatkan bahwa a + a’b
= a + b .
Penyelesaian:
a
|
b
|
a’
|
a’b
|
a
+ a’b
|
a
+ b
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
0
|
1
|
1
|
- Perjanjian: tanda titik (×) dapat dihilangkan dari penulisan ekspresi Boolean, kecuali jika ada penekanan:
(i) a(b
+ c) = ab + ac
(ii)
a + bc = (a + b) (a + c)
(iii)
a ×
0 , bukan a0
4.
Prinsip
Dualitas
- Misalkan 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
5. 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
|
 |
Contoh
7.3.
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 + 1 · b
(Komplemen)
= a + b (Identitas)
(ii)
adalah dual dari (i)
6. Fungsi Boolean
·
Fungsi Boolean (disebut juga fungsi biner) adalah pemetaan dari Bn
ke B melalui ekspresi Boolean, kita menuliskannya sebagai
f
: Bn ® B
yang dalam hal ini Bn adalah
himpunan yang beranggotakan pasangan terurut ganda-n (ordered n-tuple)
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 .
Contoh. Contoh-contoh fungsi
Boolean yang lain:
1.
f(x) = x
2.
f(x, y)
= x’y + xy’+ y’
3.
f(x, y)
= x’ y’
4.
f(x, y)
= (x + y)’
5.
f(x, y,
z) = xyz’
·
Setiap
peubah di dalam fungsi Boolean, termasuk dalam bentuk komplemennya, disebut literal.
Contoh:
Fungsi h(x, y, z) = xyz’
pada contoh di atas terdiri dari 3 buah literal, yaitu x, y, dan z’.
Contoh. Diketahui
fungsi Booelan f(x, y, z) = xy
z’, nyatakan h dalam tabel
kebenaran.
Penyelesaian:
x
|
y
|
z
|
f(x, y,
z) = xy z’
|
0
0
0
0
1
1
1
1
|
0
0
1
1
0
0
1
1
|
0
1
0
1
0
1
0
1
|
0
0
0
0
0
0
1
0
|
7.
Komplemen
Fungsi
1.
Cara
pertama: menggunakan hukum De Morgan
Hukum
De Morgan untuk dua buah peubah, x1
dan x2, adalah
Contoh.
Misalkan f(x, y, z) = x(y’z’
+ yz), maka
f
’(x, y, z)= (x(y’z’ + yz))’
= x’ + (y’z’ + yz)’
= x’ + (y’z’)’ (yz)’
= x’ + (y + z) (y’ + z’)
2.
Cara
kedua: menggunakan prinsip dualitas.
Tentukan
dual dari ekspresi Boolean yang merepresentasikan f, lalu komplemenkan setiap literal di dalam dual tersebut.
Contoh.
Misalkan f(x, y, z) = x(y’z’
+ yz), maka
dual
dari f: x + (y’
+ z’) (y + z)
komplemenkan
tiap literalnya: x’ + (y + z) (y’ + z’)
= f ’
Jadi, f ‘(x,
y, z) = x’ + (y + z)(y’ + z’)
8.
Bentuk
Kanonik
·
Ada
dua macam bentuk kanonik:
1.
Penjumlahan dari hasil kali (sum-of-product atau SOP)
2.
Perkalian dari hasil jumlah (product-of-sum atau POS)
Contoh: 1. f(x, y,
z) = x’y’z + xy’z’ + xyz à SOP
Setiap suku (term) disebut minterm
2. g(x, y,
z) = (x + y + z)(x
+ y’ + z)(x + y’ + z’)
(x’ + y
+ z’)(x’ + y’ + z)
à
POS Setiap
suku (term) disebut maxterm
·
Setiap
minterm/maxterm mengandung literal lengkap
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
|
Contoh
7.10. Nyatakan tabel kebenaran di bawah ini dalam bentuk
kanonik SOP dan POS.
Tabel
7.10
x
|
y
|
z
|
f(x, y,
z)
|
0
0
0
0
1
1
1
1
|
0
0
1
1
0
0
1
1
|
0
1
0
1
0
1
0
1
|
0
1
0
0
1
0
0
1
|
Penyelesaian:
(a)
SOP
Kombinasi
nilai-nilai peubah yang menghasilkan nilai fungsi sama dengan 1 adalah 001,
100, dan 111, maka fungsi Booleannya dalam bentuk kanonik SOP adalah
f(x, y,
z) =
x’y’z + xy’z’
+ xyz
atau
(dengan menggunakan lambang minterm),
f(x, y,
z) =
m1 + m4 + m7 = å
(1, 4, 7)
(b)
POS
Kombinasi
nilai-nilai peubah yang menghasilkan nilai fungsi sama dengan 0 adalah 000,
010, 011, 101, dan 110, maka fungsi
Booleannya dalam bentuk kanonik POS adalah
f(x, y,
z)
= (x + y + z)(x
+ y’+ z)(x + y’+ z’)
(x’+ y + z’)(x’+
y’+ z)
atau dalam bentuk lain,
f(x, y,
z) =
M0 M2 M3 M5
M6 = Õ(0,
2, 3, 5, 6)
Contoh
7.11. Nyatakan fungsi Boolean f(x, y, z) = x + y’z dalam bentuk kanonik SOP dan POS.
Penyelesaian:
(a) SOP
x = x(y + y’)
= xy + xy’
= xy (z + z’) + xy’(z
+ z’)
= xyz + xyz’ + xy’z + xy’z’
y’z = y’z (x
+ x’)
= xy’z + x’y’z
Jadi
f(x, y, z)
= x + y’z
= xyz
+ xyz’ + xy’z + xy’z’
+ xy’z + x’y’z
= x’y’z + xy’z’ + xy’z + xyz’
+ xyz
atau f(x, y, z) = m1
+ m4 + m5 + m6 + m7
= S
(1,4,5,6,7)
(b)
POS
f(x, y,
z) = x + y’z
= (x + y’)(x + z)
x
+ y’ = x + y’ + zz’
= (x + y’
+ z)(x + y’ + z’)
x + z = x
+ z + yy’
= (x + y
+ z)(x + y’ + z)
Jadi, f(x, y,
z) = (x + y’ + z)(x
+ y’ + z’)(x + y + z)(x + y’
+ z)
= (x + y + z)(x + y’ + z)(x + y’
+ z’)
atau
f(x,
y, z) = M0M2M3 = Õ(0, 2, 3)
-
Peta Karnaugh
a. Peta
Karnaugh dengan dua peubah
y
0 1
m0
|
m1
|
x
0
|
x’y’
|
x’y
|
|
m2
|
m3
|
1
|
xy’
|
xy
|
b.
Peta dengan tiga peubah
yz
00
|
01
|
11
|
10
|
|||||||
m0
|
m1
|
m3
|
m2
|
x 0
|
x’y’z’
|
x’y’z
|
x’yz
|
x’yz’
|
||
m4
|
m5
|
m7
|
m6
|
1
|
xy’z’
|
xy’z
|
xyz
|
xyz’
|
Contoh.
Diberikan tabel kebenaran, gambarkan Peta Karnaugh.
x
|
y
|
z
|
f(x, y,
z)
|
||
0
|
0
|
0
|
0
|
||
0
|
0
|
1
|
0
|
||
0
|
1
|
0
|
1
|
||
0
|
1
|
1
|
0
|
||
1
|
0
|
0
|
0
|
||
1
|
0
|
1
|
0
|
||
1
|
1
|
0
|
1
|
||
1
|
1
|
1
|
1
|
yz
00
|
01
|
11
|
10
|
|
x 0
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
b.
Peta 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’
|
||
Contoh.
Diberikan tabel kebenaran, gambarkan Peta Karnaugh.
w
|
x
|
y
|
z
|
f(w, x,
y, z)
|
||
0
|
0
|
0
|
0
|
0
|
||
0
|
0
|
0
|
1
|
1
|
||
0
|
0
|
1
|
0
|
0
|
||
0
|
0
|
1
|
1
|
0
|
||
0
|
1
|
0
|
0
|
0
|
||
0
|
1
|
0
|
1
|
0
|
||
0
|
1
|
1
|
0
|
1
|
||
0
|
1
|
1
|
1
|
1
|
||
1
|
0
|
0
|
0
|
0
|
||
1
|
0
|
0
|
1
|
0
|
||
1
|
0
|
1
|
0
|
0
|
||
1
|
0
|
1
|
1
|
0
|
||
1
|
1
|
0
|
0
|
0
|
||
1
|
1
|
0
|
1
|
0
|
||
1
|
1
|
1
|
0
|
1
|
||
1
|
1
|
1
|
1
|
0
|
||
yz
00
|
01
|
11
|
10
|
|
wx 00
|
0
|
1
|
0
|
1
|
01
|
0
|
0
|
1
|
1
|
11
|
0
|
0
|
0
|
1
|
10
|
0
|
0
|
0
|
0
|
Tidak ada komentar:
Posting Komentar