Prinsip Aljabar Boolean
·
Misalkan terdapat
-
Dua operator biner: + dan ×
-
Sebuah operator uner: ’.
-
B : himpunan yang didefinisikan pada opeartor +, ×, 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.
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.
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
c
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:
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
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)
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.
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
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)
Saklar adalah objek yang mempunyai dua
buah keadaan: buka dan tutup.
Tiga bentuk
gerbang paling sederhana:
1. a
x b
Output
b hanya ada jika dan hanya jika x dibuka Þ x
2. a
x
y b
Output
b hanya ada jika dan hanya jika x dan y dibuka Þ xy
3. a x
c b y
Output c hanya ada jika dan hanya jika x atau y dibuka Þ x + y
Contoh rangkaian pensaklaran pada rangkaian listrik:
1. Saklar dalam hubungan SERI: logika AND
Lampu |
|||||
 |
 |
||||
A
B  |
¥
Sumber tegangan  |
2. Saklar
dalam hubungan PARALEL: logika OR
A
Lampu |
|||||
 |
|
||||
B  |
¥
Sumber Tegangan  |
Contoh. Nyatakan rangkaian
pensaklaran pada gambar di bawah ini dalam ekspresi Boolean.
 |
 |
x’ y |
x’
x |
 |
x y |
|||||
|
|||||
 |
|||||
x y’
z |
z
Jawab: x’y + (x’
+ xy)z + x(y + y’z + z)
2. Rangkaian Digital Elektronik
 |
 |
 |
|||
Gerbang AND Gerbang
OR Gerbang NOT
(inverter)
Contoh. Nyatakan fungsi f(x,
y, z) = xy + x’y
ke dalam rangkaian logika.
Jawab: (a) Cara pertama
 |
(b) Cara kedua
 |
 |
(b) Cara ketiga
Gerbang
turunan
 |
 |
||
Gerbang NAND Gerbang XOR
 |
 |
||
Gerbang NOR Gerbang XNOR
 |
 |
 |
 |
||
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 + xz’
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
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
|
Teknik
Minimisasi Fungsi Boolean dengan Peta Karnaugh
1. Pasangan: dua buah 1 yang bertetangga
yz
00
|
01
|
11
|
10
|
|
wx 00
|
0
|
0
|
0
|
0
|
01
|
0
|
0
|
0
|
0
|
11
|
0
|
0
|
1
|
1
|
10
|
0
|
0
|
0
|
0
|
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
yz
00
|
01
|
11
|
10
|
|
wx 00
|
0
|
0
|
0
|
0
|
01
|
0
|
0
|
0
|
0
|
 11 |
1
|
1
|
1
|
1
|
10
|
0
|
0
|
0
|
0
|
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
yz
00
|
01
|
11
|
10
|
|
wx 00
|
0
|
0
|
0
|
0
|
01
|
0
|
0
|
0
|
0
|
  11 |
1
|
1
|
1
|
1
|
10
|
0
|
0
|
0
|
0
|
Contoh lain:
yz
00
|
01
|
11
|
10
|
|
wx 00
|
0
|
0
|
0
|
0
|
01
|
0
|
0
|
0
|
0
|
 11 |
1
|
1
|
0
|
0
|
10
|
1
|
1
|
0
|
0
|
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
yz
00
|
01
|
11
|
10
|
|
wx 00
|
0
|
0
|
0
|
0
|
01
|
0
|
0
|
0
|
0
|
 11 |
1
|
1
|
1
|
1
|
10
|
1
|
1
|
1
|
1
|
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
yz
00
|
01
|
11
|
10
|
|
wx
00
|
0
|
0
|
0
|
0
|
01
|
0
|
0
|
0
|
0
|
  11 |
1
|
1
|
1
|
1
|
10
|
1
|
1
|
1
|
1
|
Contoh
5.11. Sederhanakan fungsi Boolean f(x, y,
z)
= x’yz + xy’z’ + xyz
+ xyz’.
Jawab:
Peta Karnaugh untuk fungsi tersebut adalah:
yz
00
|
01
|
11
|
10
|
|
 x 0 |
1
|
|||
  1 |
1
|
1
|
1
|
Hasil penyederhanaan: f(x,
y, z) = yz
+ xz’
Contoh
5.12. Andaikan suatu tabel kebenaran telah diterjemahkan ke dalam Peta
Karnaugh. Sederhanakan fungsi Boolean yang bersesuaian sesederhana mungkin.
yz
00
|
01
|
11
|
10
|
|
  wx 00 |
0
|
1
|
1
|
1
|
01
|
0
|
0
|
0
|
1
|
 11 |
1
|
1
|
0
|
1
|
10
|
1
|
1
|
0
|
1
|
Jawab: (lihat Peta
Karnaugh) f(w, x, y, z) = wy’
+ yz’ + w’x’z
Contoh
5.13. Minimisasi fungsi Boolean yang
bersesuaian dengan Peta Karnaugh di bawah ini.
yz
00
|
01
|
11
|
10
|
|
wx 00
|
0
|
0
|
0
|
0
|
 01 |
0
|
1
|
0
|
0
|
 11 |
1
|
1
|
1
|
1
|
10
|
1
|
1
|
1
|
1
|
Jawab: (lihat Peta
Karnaugh) f(w, x, y, z) = w
+ xy’z
Jika penyelesaian Contoh 5.13
adalah seperti di bawah ini:
yz
00
|
01
|
11
|
10
|
|
wx
00
|
0
|
0
|
0
|
0
|
 01 |
0
|
1
|
0
|
0
|
 11 |
1
|
1
|
1
|
1
|
10
|
1
|
1
|
1
|
1
|
maka fungsi Boolean hasil
penyederhanaan adalah
f(w, x,
y, z) = w + w’xy’z
(jumlah
literal = 5)
yang ternyata masih belum
sederhana dibandingkan f(w, x,
y, z) = w + xy’z (jumlah literal = 4).
Contoh
5.14. (Penggulungan/rolling)
Sederhanakan fungsi Boolean yang bersesuaian dengan Peta Karnaugh di bawah ini.
yz
00
|
01
|
11
|
10
|
|
wx 00
|
0
|
0
|
0
|
0
|
  01 |
1
|
0
|
0
|
1
|
11
|
1
|
0
|
0
|
1
|
10
|
0
|
0
|
0
|
0
|
Jawab: f(w, x,
y, z) = xy’z’ + xyz’
==> belum sederhana
Penyelesaian yang lebih minimal:
yz
00
|
01
|
11
|
10
|
|
wx 00
|
0
|
0
|
0
|
0
|
 01 |
1
|
0
|
0
|
1
|
| 11 |
1
|
0
|
0
|
1
|
10
|
0
|
0
|
0
|
0
|
f(w, x,
y, z) = xz’ ===>
lebih sederhana
Contoh
5.15: (Kelompok berlebihan) Sederhanakan fungsi Boolean yang bersesuaian
dengan Peta Karnaugh di bawah ini.
yz
00
|
01
|
11
|
10
|
|
wx 00
|
0
|
0
|
0
|
0
|
 01 |
0
|
1
|
0
|
0
|
   11 |
0
|
1
|
1
|
0
|
10
|
0
|
0
|
1
|
0
|
Jawab: f(w, x,
y, z) = xy’z + wxz
+ wyz
® masih belum
sederhana.
Penyelesaian yang lebih
minimal:
yz
00
|
01
|
11
|
10
|
|
wx 00
|
0
|
0
|
0
|
0
|
 01 |
0
|
1
|
0
|
0
|
 11 |
0
|
1
|
1
|
0
|
10
|
0
|
0
|
1
|
0
|
f(w, x,
y, z) = xy’z + wyz ===> lebih sederhana
Contoh
5.16. Sederhanakan fungsi Boolean
yang bersesuaian dengan Peta Karnaugh di bawah ini.
cd
00
|
01
|
11
|
10
|
|
ab
00
|
0
|
0
|
0
|
0
|
 01 |
0
|
0
|
1
|
0
|
   11 |
1
|
1
|
1
|
1
|
10
|
0
|
1
|
1
|
1
|
Jawab: (lihat Peta
Karnaugh di atas) f(a, b, c, d) = ab
+ ad + ac + bcd
Contoh
5.17. Minimisasi fungsi Boolean f(x,
y, z) = x’z +
x’y + xy’z + yz
Jawab:
x’z = x’z(y
+ y’) = x’yz + x’y’z
x’y = x’y(z + z’)
= x’yz + x’yz’
yz = yz(x + x’)
= xyz + x’yz
f(x, y, z)
= x’z + x’y + xy’z + yz
= x’yz + x’y’z
+ x’yz + x’yz’ + xy’z + xyz + x’yz
= x’yz + x’y’z
+ x’yz’ + xyz + xy’z
Peta Karnaugh untuk fungsi tersebut adalah:
yz
00
|
01
|
11
|
10
|
|
  x 0 |
1
|
1
|
1
|
|
1
|
1
|
1
|
Hasil penyederhanaan: f(x, y,
z) = z + x’yz’
Peta Karnaugh untuk lima peubah
000
001 011 010
110 111 101
100
00
|
m0
|
m1
|
m3
|
m2
|
m6
|
m7
|
m5
|
m4
|
01
|
m8
|
m9
|
m11
|
m10
|
m14
|
m15
|
m13
|
m12
|
11
|
m24
|
m25
|
m27
|
m26
|
m30
|
m31
|
m29
|
m28
|
10
|
m16
|
m17
|
m19
|
m18
|
m22
|
m23
|
m21
|
m20
|
 |
Garis
pencerminan
Contoh
5.21. (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:
xyz
000
|
001
|
011
|
010
|
110
|
111
|
101
|
100
|
|||
     |
vw 00
|
1
|
1
|
1
|
1
|
|||||
   |
01
|
1
|
1
|
1
|
1
|
|||||
  |
11
|
1
|
1
|
1
|
1
|
|||||
  |
10
|
1
|
1
|
Jadi f(v,
w, x, y, z)
= wz + v’w’z’
+ vy’z
Keadaan
Don’t Care
Tabel 5.16
w
|
x
|
y
|
z
|
desimal
|
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
|
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
|
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
|
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
|
0
1
2
3
4
5
6
7
8
9
don’t care
don’t care
don’t care
don’t care
don’t care
don’t care
|
Contoh
5.25. Diberikan Tabel 5.17. Minimisasi fungsi f sesederhana mungkin.
Tabel
5.17
a
|
b
|
c
|
d
|
f(a,
b, c, d)
|
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
|
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
|
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
|
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
|
1
0
0
1
1
1
0
1
X
X X X X X X X |
Jawab: Peta Karnaugh
dari fungsi tersebut adalah:
cd
00
|
01
|
11
|
10
|
|
  ab
00 |
1
|
0
|
1
|
0
|
 01 |
1
|
1
|
1
|
0
|
11
|
X
|
X
|
X
|
X
|
10
|
X
|
0
|
X
|
X
|
Hasil penyederhanaan: f(a, b,
c, d) = bd + c’d’
+ cd
Contoh
5.26. Minimisasi fungsi Boolean f(x, y,
z)
= x’yz + x’yz’ + xy’z’ + xy’z.
Gambarkan rangkaian logikanya.
Jawab: Rangkaian
logika fungsi f(x, y, z) sebelum diminimisasikan adalah
seperti di bawah ini:
 |
Minimisasi dengan Peta Karnaugh adalah sebagai berikut:
yz
00
|
01
|
11
|
10
|
|
x 0
|
1
|
1
|
||
1
|
1
|
1
|
Hasil minimisasi adalah f(x, y,
z)
= x’y + xy’.
 |
Contoh 5.28. Berbagai sistem digital
menggunakan kode binary coded decimal
(BCD). Diberikan Tabel 5.19 untuk
konversi BCD ke kode Excess-3 sebagai
berikut:
Tabel 5.19
Masukan BCD
|
Keluaran kode Excess-3
|
|||||||
w
|
x
|
y
|
z
|
f1(w, x,
y, z)
|
f2(w, x,
y,z)
|
f3(w, x,
y, z)
|
f4(w, x,
y, z)
|
|
0
1
2
3
4
5
6
7
8
9
|
0
0
0
0
0
0
0
0
1
1
|
0
0
0
0
1
1
1
1
0
0
|
0
0
1
1
0
0
1
1
0
0
|
0
1
0
1
0
1
0
1
0
1
|
0
0
0
0
0
1
1
1
1
1
|
0
1
1
1
1
0
0
0
0
1
|
1
0
0
1
1
0
0
1
1
0
|
1
0
1
0
1
0
1
0
1
0
|
(a) f1(w, x,
y, z)
yz
00
|
01
|
11
|
10
|
|
wx 00
|
||||
  01 |
1
|
1
|
1
|
|
 11 |
X
|
X
|
X
|
X
|
 10 |
1
|
1
|
X
|
X
|
f1(w, x,
y, z) = w + xz + xy
= w + x(y + z)
(b) f2(w, x, y, z)
   |
yz
00
|
01
|
11
|
10
|
  wx 00 |
1
|
1
|
1
|
|
 01 |
1
|
|||
11
|
X
|
X
|
X
|
X
|
     10 |
1
|
X
|
X
|
f2(w, x, y, z)
= xy’z’ + x’z + x’y = xy’z’ + x’(y + z)
(c) f3(w, x, y, z)
yz
00
|
01
|
11
|
10
|
|
wx
00
|
1
|
1
|
||
01
|
1
|
1
|
||
11
|
X
|
X
|
X
|
X
|
10
|
1
|
X
|
X
|
f3(w, x,
y, z) = y’z’ + yz
(d) f4(w, x, y, z)
yz
00
|
01
|
11
|
10
|
|
   wx 00 |
1
|
1
|
||
01
|
1
|
1
|
||
11
|
X
|
X
|
X
|
X
|
| 10 |
1
|
X
|
X
|
f4(w, x,
y, z) = z’
 |
0 komentar:
Post a Comment