BILANGAN BOOLEAN SOP POS & k-map
BILANGAN BOOLEAN SOP POS
Aljabar Boolean dapat
didefinisikan dalam beberapa cara. Cara yang paling umum adalah dengan
menspesifikasikan unsur – unsur pembentuknya dan operasi – operasi yang
menyertainya.
Misalkan B adalah himpunan
yang didefinisikan pada dua operator biner, + dan ., dan sebuah operator
uner,’. Misalkan 0 dan 1 adalah dua elemen yang berbeda dari B. Maka,
tupel <B, +, ., ‘, 0, 1> disebut aljabar Boolean jika untuk setiap
a, b, c 0 B berlaku aksioma berikut :
1. Identitas
(i) a + 0 = a
(ii) a . 1 = a
2. Komutatif
(i) a + b = b +
a
(ii) a . b = b .
a
3. Distributif
(i) a . (b + c)
= (a . b) + (a . c)
(ii) a + (b . c)
= (a + b) . (a + c)
4. Komplemen
Untuk setiap a 0 B terdapat
elemen unik a’ 0 B sehingga
(i) a + a’ = 1
(ii) a . a’ = 0
5. Closure: (i) a +
b E
B (ii) a ×
b E
B
Angka 0 dan 1 adalah dua elemen
yang berada di dalam B. 0 disebut
elemen terkecil dan 1 disebut
elemen terbesar. Tanda (+) disebut operator penjumlahan,( .) disebut operator
perkalian, dan ( ‘) disebut operator komplemen.
Ada perbedaan antara aljabar
Boolean dengan aljabar biasa untuk aritmetika bilangan riil :
1. Hukum distributif yang
pertama, a . (b + c) = (a . b) + (a .
c) sudah dikenal di dalam aljabar biasa, tetapi hukum distributif yang
kedua, a + (b . c) = (a + b) . (a + c)
2. Aljabar Boolean tidak memiliki
kebalikan perkalian dan kebalikan penjumlahan; karena itu, tidak ada operasi
pembagian dan pengurangan di dalam aljabar Boolean.
3.
Aljabar biasa memperlakukan himpunan bilangan riil dengan elemen yang tidak
berhingga banyaknya.
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
|
Buktikan apakah memenuhi postulat
Huntington:
1.
Closure
: berlaku
2.
Identitas:
berlaku karena dari tabel dapat di lihat bahwa:
(i) 0 + 1 = 1 + 0 = 1
(ii) 1 × 0 = 0 ×
1 = 0
3.
Komutatif:
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
5.
Komplemen:
jelas berlaku karena 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
Kesimpulannya: Karena kelima postulat Huntington
dipenuhi, maka terbukti bahwa B = {0, 1}
Ekspresi
Boolean
- Semisal (B, +, ×, ’) sebuah aljabar Boolean.
- Suatu
ekspresi Boolean dalam (B, +, ×,
’) dapat berbentuk:
(1) elemen di dalam B, ex : 0 dan 1
(2) peubah/ literal/ variable, ex : a, b, c
(3) jika e1
dan e2 adalah ekspresi Boolean, maka e1 + e2,
e1 × e2, e1’
adalah ekspresi Boolean
Prinsip
Dualitas
Semisal S kesamaan di dalam aljabar Boolean yang
menggunakan operator +, ×, dan komplemen, maka jika
pernyataan S* diperoleh dengan cara
mengganti
×
dengan +
+ dengan
×
0 dengan
1
1 dengan
0
dan biarkan operator komplemen tetap apa adanya, maka kesamaan S* juga benar.
Contoh.
(1) (a × 1)(0 + a’) = 0
dualnya (a
+ 0) + (1 × a’) = 1
(2) a(a‘
+ b) = ab dualnya a + a‘b = a
+ b
1.
Cara
pertama: menggunakan hukum De Morgan
Hukum
De Morgan untuk dua buah peubah, x1
dan x2, adalah
Contoh. Semisal 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.
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
|
|
Contoh.
buatlah
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
|
Jwab:
(a)
SOP
Perpaduan nilai-nilai peubah yang menghasilkan nilai fungsi
sama dengan 1 adalah 001, 100, dan 111, maka fungsi Booleannya dalam bentuk
kanonik SOP:
f(x,
y, z) = x’y’z + xy’z’ + xyz
atau bisa (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)
PETA KARNAUGH
(K-MAP)
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 akan tetap, jika
peubahnya lebih dari 6, akan lebih sulit.
Definisi Peta Karnaugh
yaitu:
Setiap peta karnaugh
boleh mengubah wujud dalam suatu rangkap Boolean
atau jadual benar
Setiap petak
menunjukkan nilai ‘minterm’ (bagi SOP) atau ‘maxterm’ (bagi POS)
setiap pembolehubah. Kemudian hanya merangkumi 2 atau 3 atau 4
pembolehubah/input saja. Pemudahan bagi rangkap Boolean lebih besar daripada 4.
Bilangan petak (2ⁿ) akan
ditentukan oleh bilangan input
a. Peta
Karnaugh 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’
|
c. 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’
|
|
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
2. Kuad: empat buah 1 yang bertetangga
|
|
yz
00
|
01
|
11
|
10
|
|
ab 00
|
0
|
0
|
0
|
0
|
|
01
|
0
|
0
|
0
|
0
|
|
11
|
1
|
1
|
1
|
1
|
|
10
|
0
|
0
|
0
|
0
|
Sebelum disederhanakan: f(b,a, y, z)
= bay’z’
+ bay’z
+ bayz + bayz’
Hasil penyederhanaan: f(b, a, y, z)
= ba
3. Oktet:
delapan buah 1 yang bertetangga
|
|
yz
00
|
01
|
11
|
10
|
|
ws 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) = wsy’z’ + wsy’z
+ wsyz + wsyz’ +
ws’y’z’
+ ws’y’z + ws’yz + ws’yz’
Hasil penyederhanaan: f(w,
s, y, z)
= w
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
Keadaan Don’t
Care
|
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
|
0 comments:
Post a Comment