ALJABAR BOOLEAN
v Aljabar Boolean
Aljabar Boolean
merupakan operasi aritmatiks pada bilangan Boolean. Bilangan Boolean
adalah bilangan hanya mengenal 2 keadaan (False/True), (Yes/No), (1 atau
0).--- > bilangan biner.
Ø Misalkan terdapat :
1. Dua operator biner : + dan ×
2. Sebuah operator uner : ’.
3. B : himpunan yang didefinisikan pada opeartor
+, ×, dan ’
4.
0 dan 1 adalah
dua elemen yang berbeda dari B.
v 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][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.
v Aljabar Boolean Dua-Nilai
1. Aljabar Boolean du B = {0, 1 operator biner, +
dan ×}
2.
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 :
a)
0 + 1 = 1 + 0 =
1
b)
1 × 0
= 0 × 1 = 0
3.
Komutatif:
jelas berlaku dengan melihat simetri tabel operator biner.
4.
Distributif:
a) 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
|
1
|
|||||
|
0
|
1
|
0
|
|||||
|
0
|
1
|
1
|
|||||
|
1
|
0
|
0
|
|||||
|
1
|
0
|
1
|
|||||
|
1
|
1
|
0
|
|||||
|
1
|
1
|
1
|
b) Hukum distributif a + (b × c)
= (a + b) × (a + c)
dapat ditunjukkan benar dengan membuat tabel kebenaran dengan cara yang sama
seperti (a).
5. Komplemen: jelas berlaku karena memperlihatkan bahwa:
(a) a + a‘ = 1, karena 0 +
0’= 0 + 1 = 1 dan 1 + 1’= 1 + 0 = 1
(b) 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.
o
Misalkan (B, +, ×, ’) adalah sebuah
aljabar Boolean.
o Suatu ekspresi Boolean dalam (B, +, ×, ’)
dapat berbentuk:
a) elemen di dalam B, ex : 0 dan 1
b) peubah/ literal/ variable, ex : a, b, c
c) 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’,
dan sebagainya
v 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
Buktikan :
(a) a + a’b = a + b
dan
(b) a(a’ + b) = ab
Penyelesaian:
(a)
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)
(b)
adalah dual dari (a)
v Fungsi Boolean
o
Fungsi Boolean (disebut juga fungsi biner) adalah pemetaan dari Bnke 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.
o
Setiap ekspresi Boolean tidak lain merupakan fungsi
Boolean.
o
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 yang termasuk fungsi Boolean yang lain adalah:
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’
o
Setiap peubah di dalam fungsi Boolean, termasuk dalam
bentuk komplemennya, disebut literal
·
Contoh 1 :
Fungsi f
(x, y, z)
= xyz’ pada contoh di atas terdiri dari 3 buah literal,
yaitu x, y, dan z’.
·
Contoh 2 :
Diketahui fungsi
Booelan f (x, y, z) = xy z’,
nyatakan f dalam tabel kebenaran.
Penyelesaian:
|
x
|
y
|
z
|
F (x, y, z) = xy z’
|
f= x’+yz
|
|
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
Contohnya :
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’)
v 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 1 Selanjutnya
:
Nyatakan tabel kebenaran di bawah ini dalam bentuk kanonik SOP dan POS.
ü Tabel
|
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 2 :
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)
Komentar
Posting Komentar