BAB
4
Aljabar Boolean
4.1
Pendahuluan
Aljabar
boole pertama kali dikemukakan oleh
seseorang matematikawan inggris, geogre boole pada tahun 1854. Aljabar boolean adalah cabang ilmu matematika yang
diperlukan untuk mempelajari desain logika dari suatu sistem digital yang
merupakan operasi aritmatik pada bilangan boolean (bilangan yang hanya mengenal
2 keadaan yaitu False/True, Yes/No, 1/0) atau bisa disebut bilangan biner. Pada tahun 1938 clamde
shanmon memperlihatkan penggunaan aljabar boole untuk merancang rangkaian
sirkuit yang menerima masukan 0 dan 1 dan menghasilkan keluaran juga 0 dan 1
aljabar boole telah menjadi dasar teknologi komputer digital.
Definisi :
Aljabar boole
merupakanaljabaryng terdiri atas suatu hmpunan B dengan dua operator biner yang
didefinisikan pada himpunan tersebut, yaitu * (infimum) dan + (supremum).
Atau
Aljabar boole
adalah suatu letisdistribusi berkomplimen.
Notasi
aljabarboole adalah (B, + , 1 , 0 , 1 ). Dalam aljabar boole
terdapat :
- Letis (B, * , + ) dengan dua operasi biner infimum (*) dan supremum (+)
- Poset (B, ≤) yaitu himpunan terurut bagian.
- Batas-batas letis yang dinotasikan dengan 0 dan 1. 0adalah elemen terkecil dan 1 adalah elemen terbesr dari relasi (B, ≤).
Karena (B, * , +) merupakan letis distribusi berkomplemen maka tiap elemen
dari B merupakan komplemen yang unik. Komplemen dan ( a Î B )
Untuk setiap
a, b, c Î B berlaku sifat-sifat atau postulat-postulat
berikut:
1. Closure (tertutup) : (i)
a + b Î B
(ii) a * b Î B
2. Identitas : (i)
ada
elemen untuk 0 Î B sebgai bentuk
a
+ 0 = 0 + a = a
(ii) ada elemen untuk 1 Î B sebgai bentuk
a
* 1 = 1 * a = 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)
(iii) (a
* b) + c = (a + c) * (b + c)
(i) a +
a1 = 1
(ii) a * a1 = 0
6.
Terdapat paling sedikit dua buah elemen
a dan Î B sedemikian hingga a ≠ b.
7. Idempoteni :
a * a = a ; + a = a
8.
Assosiatif : a + (b + c)
= (a + b) +c ; a * (b *c) = (a * b) * c
Kecuali postulat nomor
7 dan 8, postulat pertama diformulasikan secara formal oleh E.V Humtingtonn
pada tahun 1904 sebagai keenan aksioma/ postulat tersebut. Adapun postulat
assosiatif dan idempoten dapat diturunkan dari postulat yang lain.
4.2 Aljabar Boole Dua Nilai
Aljabar Boolean dua-nilai didefinisikan pada sebuah
himpunan dua buah elemen, B = {0, 1}. Akan diselidiki apakah (B, + , 1 , 0 , 1 ) aljabar boole atau
bukan.
operator biner, + dan ×
operator uner, ’
Kaidah untuk operator biner dan operator uner:
a
|
b
|
a * b
|
|
a
|
B
|
a + b
|
|
a
|
a1
|
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
Yang
memenuhi elemen identitas 0 dan 1 seperti yang didefinisikan pada postulat huntington.
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 di atas memperlihatkan bahwa:
(i) a + a1 = 1, karena 0 + 01= 0 + 1 = 1 dan 1 + 11= 1 + 0 = 1
(ii) a * a = 0, karena 0 * 01= 0 × 1 = 0 dan 1 * 11 = 1 * 0 = 0
Karena kelima postulat Huntington
dipenuhi, maka terbukti bahwa B = {0, 1} bersama-sama dengan operator
biner + dan * operator komplemen1 merupakan
aljabar Boolean.
Contoh :
Buktikan
sifat aljbar boole : a + (a1 * b) = a + b
Bukti :
a + ( a1
* b) = ( a + a1 ) * (a + b)
= 1 * ( a + b )
= a + b
4.3 Prinsip
Dualitas
Definisi : Misalkan S adalah kesamaan (identity) di
dalam aljabar Boolean yang melibatkan
operasi ( *, +, dan komplemen1) , maka
jika pernyataan S* diperoleh dengan
cara mengganti
* dengan +
+
dengan *
0 dengan
1
1
dengan 0
maka kesamaan S*
juga benar. S* disebut sebagai dual dari S.
Contoh.
1.
Tentukan dual dari a
+(b *c) = (a + b)*(a + c)
Jawab :
a *(b + c)
= (a * b)+(a * c)
2.
a * 1 = 0
Jawab :
a + 0 = 1
4.4 Sifat-sifat
atau 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 + a1
= 1
(ii) aa1 = 0
|
4. Hukum
dominansi:
(i) a * 0 =
0
(ii) a
+ 1 = 1
|
5. Hukum
involusi:
(i) (a1)1= 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)1 = a1 b1
(ii)
(ab)1 = a1 + b1
|
11.
Hukum
0/1
(i) 01 = 1
(ii) 11 = 0
|
|
Contoh. Buktikan (i) a
+ ab = a dan (ii) a(a + b)
= a
Penyelesaian:
(i) a + ab = a * 1 + a*b (hukum identitas)
= a ( 1 + b) (distributif)
= a * 1 (dominasi)
= a (Identitas)
(ii) a(a + b) = ( a + 0)
(a +b) (hukum identitas)
= a + (0*b) (distributif)
= a+ 0 (dominasi)
= a (Identitas)
Contoh :
Buktikan bahwa untuk sembarang
elemen a dan b dari aljabar Boolean maka kesamaan berikut :
a + a1b=a+b
dan a(a1+b)=ab adalah benar.
Jawab:
(i)
a + a1b = (a + ab) + a1b (hukum penyerapan)
= a +
(ab + a1b) (asosiatif)
= a +
(a + a1) b (distributif)
= a + 1
. b (komplemen)
= a + b (identitas)
(ii)
a(a1 +
b) = a a1 + ab (hukum
distributif)
= 0 + ab (komplemen)
= ab (identitas)
Atau, dapat juga dibuktikan
melalui dualitas dari (i) sebagai berikut:
a(a1
+ b) = a(a + b)(a1 + b)
= a{(a + b)(a1 + b)}
= a {(a a1) + b}
= a (0 + b)
= ab
4.5 Fungsi
Boolean
Fungsi
Boolean (disebut juga fungsi biner)
adalah pemetaan dari Bn ke B melalui ekspresi Boolean,
kita menuliskannya sebagai
f : Bn
® B
Bn adalah himpunan yang
beranggotakan pasangan terurut ganda-n (ordered n-tuple) di dalam
daerah asal B.
Setiap
ekspresi Boolean 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}.
Penyelesaian
: (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
|
4.6 Fungsi Komplemen
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’)
4.7 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 . 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 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)
4.8 Aplikasi Aljabar Boolean
a. 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)
3.
Rangkaian Digital Elektronik
Contoh.
Nyatakan fungsi f(x, y,
z) = xy + x’y ke dalam rangkaian logika.
Jawab: (a) Cara
pertama
(b) Cara kedua
(b) Cara ketiga
4.9 Penyederhanaan
fungsi Boolean
Dari segi penerapannya,fungsi
boole yang lebih sederhana berarti rangkaan logika nya juga sederhana.
Penyederhanaan fungsi boole dapat dilakukan dengan 3 cara:
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
Cara untuk
menyederhanakan ekspresi atau pernyataan dari Aljabar Boole. Caranya dengan
menggambarkan kotak-kotak yang berisi “Minterm” (Minimum-Terms)
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 . 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 .
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 . 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 . (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 : (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 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 . 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 \. (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
lorecQlen-pi Tom Proulx Here
BalasHapuskingtasfaestan
minoOquad-dzu-Billings Paul Overturf Movavi Video Editor
BalasHapusScreaming Frog SEO Spider 17.1
VMware Player
Burp Suite Professional 2022.8.2
ulranchaouladb