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)
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
|
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’)
Bentuk Kanonik
· Jadi, 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
|
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
|
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)
