MATEMATIKA DISKRIT
"ALJABAR BOOLEAN"
Dalam blog kali ini akan menmbahas tentang Aljabar Boolean, yang sebelumnya lupa di sampaikan oleh bapak dosen. Dan Disini saya akan menjelaskan definisi tentang Aljabar Boolean yang berisikan SOP, POS & Peta Karnaugh. Berikut materinya.
Definisi 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 elemen B
berlaku aksioma-aksioma atau postulat Huntington berikut:
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.
ALJABAR BOOLEAN DUA NILAI
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:
(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.
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
Mengevaluasi Ekspresi
Boolean
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
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
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
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
|
Konversi Antar Bentuk Kanonik
PETA KARNAUGH
Peta Karnaugh adalah suatu cara lain untuk mempermudah penyederhanaan fungsi Boolean.
Cara ini lebih mudah dari pada cara penyederhanaan aljabar terutama dengan 3 atau 4 Variabel (peubah) akan tetap, jika peubahnya lebih dari 6, akan lebih sulit. Peta Karnaugh di rumuskan dengan menggunakan kotak segi empat.
Cara ini lebih mudah dari pada cara penyederhanaan aljabar terutama dengan 3 atau 4 Variabel (peubah) akan tetap, jika peubahnya lebih dari 6, akan lebih sulit. Peta Karnaugh di rumuskan dengan menggunakan kotak segi empat.
Terima kasih, semoga bermanfaat.
0 komentar:
Posting Komentar