Definisi
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.
(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.
Aljabar Boolean Dua-Nilai
Aljabar Boolean dua-nilai:
-
B = {0, 1}
-
operator biner, + dan ×
-
operator uner, ’
-
Kaidah untuk operator biner dan operator uner :
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
Contoh:
0
1
a
b
a + b
a
× b
a’× (b + c)
a
× b’ + a × b × c’ + b’, dan
sebagainya
Mengevaluasi Ekspresi
Boolean
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:
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
Hukum-hukum Aljabar Boolean
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’
- 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 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
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. 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
Contoh:
Nyatakan tabel kebenaran di
bawah ini dalam bentuk kanonik SOP dan POS.
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 :
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)
Konversi Antar Bentuk Kanonik
Misalkan
f(x, y,
z) = S (1, 4, 5, 6, 7)
dan f
’adalah fungsi komplemen dari f,
f
’(x, y, z) = S (0, 2, 3)
= m0+ m2 + m3
Dengan menggunakan hukum De Morgan, kita dapat
memperoleh fungsi f dalam bentuk POS:
f ’(x, y, z)
= (f ’(x, y, z))’ = (m0 + m2 +
m3)’
= m0’
. m2’ . m3’
= (x’y’z’)’ (x’y z’)’ (x’y z)’
= (x + y + z) (x
+ y’ + z) (x + y’ + z’)
= M0 M2 M3
= Õ (0,2,3)
Jadi, f(x,
y, z) = S (1, 4, 5, 6, 7) = Õ (0,2,3).
Kesimpulan: mj’
= Mj
Contoh.
Nyatakan
f(x, y,
z)= Õ (0, 2, 4, 5) dan
g(w, x,
y, z) = S(1, 2, 5, 6, 10, 15)
dalam bentuk SOP dan POS
Penyelesaian:
f(x, y, z) = S (1, 3, 6, 7)
g(w,
x, y, z)= Õ (0, 3, 4, 7, 8, 9, 11, 12, 13, 14)
Contoh.
Carilah bentuk kanonik SOP
dan POS dari f(x, y, z) = y’
+ xy + x’yz’
Penyelesaian:
(a) SOP
f(x, y,
z) = y’ + xy + x’yz’
= y’ (x + x’) (z
+ z’) + xy (z + z’) + x’yz’
= (xy’ + x’y’) (z
+ z’) + xyz + xyz’ + x’yz’
= xy’z + xy’z’ + x’y’z
+ x’y’z’ + xyz + xyz’ + x’yz’
atau f(x, y, z) = m0+ m1 + m2+ m4+
m5+ m6+ m7
(b) POS
f(x, y,
z) = M3
= x + y’ + z’
Bentuk Baku
- Tidak harus mengandung literal yang lengkap.
Contohnya,
f(x, y, z) = y’ + xy + x’yz (bentuk baku SOP)
f(x, y, z) = x(y’ + z)(x’ + y + z’) (bentuk baku POS)
Aplikasi Aljabar Boolean
1. Jaringan Pensaklaran (Switching Network)
Tiga bentuk gerbang paling
sederhana:
Contoh
rangkaian pensaklaran pada rangkaian listrik:
1. Saklar dalam
hubungan SERI: logika AND
2. Saklar dalam hubungan PARALEL: logika OR
2. Rangkaian Logika
Penyederhanaan 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:
1. Secara aljabar
2. Menggunakan Peta Karnaugh
3. Menggunakan metode Quine Mc Cluskey (metode
Tabulasi)
1. Penyederhanaan Secara Aljabar
Contoh:
1. f(x, y)
= x + x’y
= (x
+ x’)(x + y)
= 1 × (x + y )
= x
+ y
2. f(x, y,
z) = x’y’z + x’yz + xy’
= x’z(y’
+ y) + xy’
= x’z + xy’
3. f(x, y,
z) = xy + x’z + yz = xy
+ x’z + yz(x + x’)
= xy
+ x’z + xyz + x’yz
= xy(1
+ z) + x’z(1 + y) = xy
+ x’z
2. Peta Karnaugh
a. Peta Karnaugh dengan dua peubah
b. Peta dengan
tiga peubah
Contoh. Diberikan tabel kebenaran, gambarkan Peta Karnaugh.
c. Peta dengan empat peubah
Contoh. Diberikan tabel kebenaran, gambarkan Peta
Karnaugh.
Teknik Minimisasi Fungsi Boolean dengan Peta Karnaugh
1. Pasangan:
dua buah 1 yang bertetangga
Sebelum
disederhanakan:
f(w,
x, y, z) = wxyz + wxyz’
Hasil
Penyederhanaan: f(w, x, y, z)
= wxy
Bukti
secara aljabar:
f(w,
x, y, z) = wxyz + wxyz’
= wxy(z + z’)
= wxy(1)
= wxy
2. Kuad:
empat buah 1 yang bertetangga
Sebelum
disederhanakan:
f(w,
x, y, z) = wxy’z’
+ wxy’z + wxyz + wxyz’
Hasil
penyederhanaan: f(w, x,
y, z) = wx
Bukti secara aljabar:
f(w,
x, y, z) = wxy’ + wxy
= wx(z’ + z)
= wx(1)
= wx
Contoh
lain:
Sebelum disederhanakan: f(w, x, y, z) = wxy’z’ + wxy’z + wx’y’z’
+ wx’y’z
Hasil
penyederhanaan: f(w, x,
y, z) = wy’
3. Oktet: delapan buah 1 yang bertetangga
Sebelum
disederhanakan:
f(a,
b, c, d) = wxy’z’
+ wxy’z + wxyz + wxyz’ +
wx’y’z’ + wx’y’z
+ wx’yz + wx’yz’
Hasil penyederhanaan: f(w, x, y, z) = w
Bukti
secara aljabar:
f(w, x,
y, z) = wy’ + wy
= w(y’ + y)
= w
Peta Karnaugh untuk lima peubah
Contoh:
(Contoh penggunaan Peta 5
peubah) Carilah fungsi sederhana dari f(v,
w, x, y, z) = S (0, 2, 4, 6, 9, 11, 13, 15,
17, 21, 25, 27, 29, 31)
Jawab:
Peta
Karnaugh dari fungsi tersebut adalah:
OctaviantiNurwiningtyas
A11.2011.06411
MatematikaDiskrit(A11.4310)
TeknikInformatika-S1
UDINUS
