Post on 30-Dec-2015
description
ALJABAR BOOLE
DEFINISI PRINSIP DUALITAS FUNGSI BOOLEAN KONVERSI FUNGSI BOOLEAN
DEFINISI ALJABAR BOOLE
Sistem aljabar dengan dua operasi penjumlahan (+) dan perkalian (.) yang didefinisikan sehingga memenuhi ketentuan berikut ini :
aturan A1 sampai dengan A5, M1 sampai M3, M5, D1, dan D2,setiap elemen a, b, c dari S mempunyai sifat-sifat atau aksioma-aksioma berikut ini :
2
A1 a + b S closure
M1 a b S closure
A2 a + (b + c) = (a + b) + c asosiatif
M2 a (b c) = (a b) c asosiatif
A3 Jika 0 S, maka untuk setiap a S berlaku 0 + a = a + 0 = a
identitas
M3 Jika 0 S, maka untuk setiap a S berlaku 1 a = a 1 = a
identitas
A5 a + b = b + a komunitatif
M5 a b = b a komunitatif
D1 a (b + c) = a b +a c distributif
D2 (a + b) c = a c + b c distributif
D3 a + (b c) = (a + b) (a + c) distributif
D4 (a b) + c = (a + c) (b + c) distributif
C1 Untuk setiap a S dan a’ S berlaku a + a’ = 1 a a’ = 0
komplemen
a + a = (a + a) (1) identitas a 1 = a M3
(a + a) (a + a’) komplemen a + a’ = 1 C1
a + (a a’) Distributif D3
a + 0 komplemen a a’ = 0 C1
a identitas a + 0 = a A3
a a = a a + 0 identitas a + 0 = a A3
= a a + a a’ komplemen a a’ = 0 C1
= a (a + a’) distributif D1
= a 1 komplemen a + a’ =1 C1
= a identitas a 1 = a M3
PRINSIP DUALITASTeorema 2.1 Untuk setiap elemen a, berlaku
a + a = a dan a a = aBukti :
a + 1 = a + (a + a’) komplemen a + a’= 1 C1
(a + a) + a’ asosiatif A2
a + a’ teorema 2.1 a + a = a
1 komplemen a + a’= 1 C1
a 0 = a (a a’) komplemen a + 0 = a C1
= (a a) a’ asosiatif M2
= a a’ teorema 2.1 a a =a
= 0 komplemen a a’ = 0 C1
Teorema 2.2 Untuk setiap elemen a, berlaku :
a + 1 = 1 dan a 0 = 0
Bukti :
a + ab = a 1 + a.b identitas a 1 = a M3
a (1 + b) distributif D1
a 1 teorema 2.2 1 + a =1
a identitas a 1 = a M3
a .(a+b) = a a + a b distributif a + 0 = a A3
= a + a b teorema 2.1 a a = a
= a 1+ a b identitas a 1=a M3
= a (1+b) distributif D2
= a 1 teorema 2.2 a + 1 = a
= a identitas a 1 = a M3
Teorema 2.3 (Hukum penyerapan)
Untuk setiap elemen a dan b, berlaku
a + a b = a dan a (a+b) = aBukti :
Diketahui : (ab) (ab)’= 0 komplemen C1
ab (a’+b’) = (aa’)b + a(bb’) distributif D1
= 0 b + a 0 komplemen C1
= 0 + 0 Teorema 2.2
= 0 identitas A3
(ab)’ = a’ + b’ kesimpulan
Teorema 2.4 (Hukum de Morgan)
Untuk setiap elemen a dan b, berlaku :
(a b)’ = a’ + b’ dan (a + b)’ = a’ b’
Bukti :
Diketahui : (ab) + (ab)’= 1 komplemen C1
ab+(a’+b’) = (a + a’ + b’)(b + a’ + b’) distributif D4
= (1 + b’) (1 + a’) komplemen C1
= 1 1 teorema 2.2
= 1 teorema 2.2
(ab)’ = a’ + b’ kesimpulan
Bukti :
Latihan Soal 2.1
Buktikan teorema 2.5 :
a+a’b=a+b
a(a’+b)=ab
Latihan Soal 2.2Sederhanakan ekspresi berikut :
'bc'ab
)c'b'ab('ab
z)yx()yx(
a + a b = a dan a (a+b) = a
'''
')''('
)()(
bbcab
abcbabab
yxzyxyx
Latihan Soal 2.3
Buktikan teorema 2.6 :
ab+ab’=a
(a+b)(a+b’)=a
Latihan Soal 2.4Sederhanakan ekspresi berikut :
)z'y'x'w)('z'y'x'w(
))'cb(ad)(cbad(
c'ababc
a + a b = a dan a (a+b) = a
a+a’b=a+b
a(a’+b)=ab
''')''')(''''(
))'()((
'
yxwzyxwzyxw
adcbadcbad
accababc
Latihan Soal 2.5
Buktikan teorema 2. 7
ab+ab’c=ab+ac
(a+b)(a+b’+c)=(a+b)(a+c)
Latihan Soal 2.6Sederhanakan ekspresi berikut :
wwxzwxyzywxwy
bbacbcba
yxwzyxzyxwzyx
zwxxyzwxyxy
'''
')')(')('''(
)'')(''()''')(''(
)''()''('
a + a b = a dan a (a+b) = a
a+a’b=a+b
a(a’+b)=ab
ab+ab’=a
(a+b)(a+b’)=a
T2.7 : (a+b)(a+b’+c)=(a+b)(a+c)
a b + a b’ c = a b + a c
T2.3 : a + a b = a a (a+b) = a
T2.6 : a b + a b’= a (a + b) (a + b’) = a
(a’+b’+c’) (b’+c) (a+b’) = (b’+c) (b’+a’) (a+b’) T2.7
= (b’+c) b’ T2.6
= b’ T2.3
wy’+wx’y+wxyz+wxz’ = wy’+wx’y+wxy+wxz T2.7
= (wy’+wy)+wxz T2.6
= w+wxz T2.6
= w T2.3
16
wwxzwxyzywxwy
bbacbcba
'''
')')(')('''(
C1 a + a’ = 1 a a’ = 0
A2 M2 a + (b + c) = (a + b) + c a (b c) = (a b) c
A3 M3 a + 0 = a a 1 = 1
A2 M2 a + (b + c) = (a + b) + c a (b c) = (a b) c
A5 M5 a + b = b + a a b = b a
D1 D2 a (b + c) = a b +a c (a + b) c = a c + b c
D3 D4 a + (b c) = (a + b) (a + c) (a b) + c = (a + c) (b + c)
T2.1 a+ a = a a a = a
T2.2 a + 1 = 1 a 0 = 0
T2.3 a + a b = a a (a+b) = a
T2.4 (a b)’ = a’ + b’ (a + b)’ = a’ b’
T2.5 a + a’ b = a + b a (a’+ b) = a b
T2.6 a b + a b’= a (a + b) (a + b’) = a
T2.7 a b + a b’ c = a b + a c
(a + b) (a + b’+ c) = (a + b) (a + c)
FUNGSI BOOLEAN Misalkan x1, x2, x3, … , xn merupakan variabel-variabel aljabar
Boolean. Fungsi Boolean dengan n variabel adalah fungsi yang dapat dibentuk dari aturan-aturan berikut :
• fungsi konstanf(x1, x2, x3, … , xn) = a
• fungsi proyeksi f(x1, x2, x3, … , xn) = xi i = 1, 2, 3, … , n
• fungsi komplemen g(x1, x2, x3, … , xn) = (f(x1, x2, x3, … , xn))’
• fungsi gabunganh(x1, x2, x3, … , xn) = f(x1, x2, x3, … , xn) + g(x1, x2, x3, … , xn)
h(x1, x2, x3, … , xn) = f(x1, x2, x3, … , xn) . g(x1, x2, x3, … , xn)
18
BENTUK FUNGSI BOOLEAN
Suatu fungsi Boolean dapat dinyatakan dalam bentuk yang berbeda tetapi memiliki arti yang samaContoh :f1(x,y) = x’ . y’
f2(x,y) = (x + y)’
f1 dan f2 merupakan bentuk fungsi boolean yang sama, yaitu dengan menggunakan Hukum De Morgan.
19
NILAI FUNGSI
Fungsi Boolean dinyatakan nilainya pada setiap variabel yaitu pada setiap kombinasi (0,1).
Contoh : Fungsi Booleanf(x,y) = x’y + xy’ + y’
20
21
MINTERM DAN MAXTERM
Fungsi dua variabel :
Mj = m’j
22
Fungsi tiga variabel :
KONVERSI FUNGSI BOOLEAN23
Contoh Soal 2.1
Dari tabel kebenaran di bawah ini, nyatakan fungsi boolean dalam bentuk SOP (sum of product) dan POS (Product of sum)
No x y z F(x,y,z)
0 0 0 0 0
1 0 0 1 1 m1
2 0 1 0 0
3 0 1 1 0
4 1 0 0 1 m4
5 1 0 1 0
6 1 1 0 0
7 1 1 1 1 m7
SOP
SOP
SOP
f1(x,y,z) = x’y’z + xy’z’ + xyz = m1 + m4 + m7
f1’(x,y,z)= x’y’z’ + x’yz’ + x’yz + xy’z + xyz’
Jawab : Bentuk SOP
No x y z F(x,y,z)
0 0 0 0 0 Mo
1 0 0 1 1
2 0 1 0 0 M2
3 0 1 1 0 M3
4 1 0 0 1
5 1 0 1 0 M5
6 1 1 0 0 M6
7 1 1 1 1
POS
POS
POS
Jawab : Bentuk POS
f2(x,y,z) = (x+y+z)(x+y’+z)(x+y’+z’)(x’+y+z’)(x’+y’+z)
= M0 M2 M3 M5 M6 = (f1’(x,y,z))’
F (x,y,z) = m1 + m4 + m7 = M0 . M2 . M3 . M5 . M6
POS
POS
26Contoh Soal 2.2
Dari tabel kebenaran di bawah ini, nyatakan fungsi boolean dalam bentuk SOP (sum of product) dan POS (Product of sum)
No x y z f(x,y,z)
0 0 0 0 1 m0
1 0 0 1 1 m1
2 0 1 0 1 m2
3 0 1 1 1 m3
4 1 0 0 1 m4
5 1 0 1 0
6 1 1 0 1 m6
7 1 1 1 0
SOP
SOP
SOP
Jawab : Bentuk SOP
f1(x,y,z) = x’y’z’ + x’y’z + x’yz’ + x’yz + xy’z+xyz’
= m0 + m1 + m2 + m3 + m4 + m6
f1’(x,y,z) = xy’z + xyz
SOP
SOP
SOP
Jawab : Bentuk POS
POS
POS
No x y z f(x,y,z)
0 0 0 0 1
1 0 0 1 1
2 0 1 0 1
3 0 1 1 1
4 1 0 0 1
5 1 0 1 0 M5
6 1 1 0 1
7 1 1 1 0 M7
f2(x,y,z)= (x’ + y + z’)(x’ + y’ + z’)
= (f1’(x,y,z))’ = M5. M7
F(x,y,z)= m0 + m1 + m2 + m3 + m4 + m6 = M5. M7
29Contoh Soal 2.3
Dari tabel kebenaran di bawah ini, nyatakan fungsi boolean dalam bentuk SOP (sum of product) dan POS (Product of sum)
No x y z f(x,y,z)
0 0 0 0 0
1 0 0 1 0
2 0 1 0 1 m2
3 0 1 1 1 m3
4 1 0 0 0
5 1 0 1 0
6 1 1 0 1 m6
7 1 1 1 1 m7
SOP
Jawab : Bentuk SOP
SOP
SOP
SOP
f1(x,y,z) = x’yz’ + x’yz + xyz’ + xyz
= m2 + m3 + m6 + m7
f1’(x,y,z)= x’y’z’ + x’y’z + xy’z’ + xy’z
Jawab : Bentuk POS
POS
POS
No x y z f(x,y,z)
0 0 0 0 0 Mo
1 0 0 1 0 M1
2 0 1 0 1
3 0 1 1 1
4 1 0 0 0 M4
5 1 0 1 0 M5
6 1 1 0 1
7 1 1 1 1
f2(x,y,z) = (x + y + z).(x + y + z’).(x’ + y + z).(x’ + y + z’)
= (f1’(x,y,z))’= M0.M1. M4. M5
F(x,y,z) = m2 + m3 + m6 + m7 = M0.M1. M4. M5
POS
POS
BENTUK STANDAR/KANONIK
Jika f adalah fungsi boolean satu variabel maka untuk semua nilai x berlaku :
f (x) = f (1) . x + f (0) . x’
Jika f adalah fungsi boolean dua variabel maka untuk semua nilai x berlaku :
f(x,y) = f(0,0) . x’y’ + f(0,1) . x’y + f(1,0) . xy’ + f(1,1) . xy
Jika f adalah fungsi boolean tiga variabel maka untuk semua nilai x berlaku :
f(x,y,z) = f(0,0,0) . x’y’ z’ + f(0,0,1) . x’y’z + f(0,1,0) . x’yz’ + f(0,1,1) . x’yz + f(1,0,0) . xy’z’ + f(1,0,1) . xy’z’ + f(1,1,0) . xyz’ + f(1,1,1) . xyz
32
No x y z f(x,y,z)
0 0 0 0 0
1 0 0 1 1 m1
2 0 1 0 0
3 0 1 1 0
4 1 0 0 1 m4
5 1 0 1 0
6 1 1 0 0
7 1 1 1 1 m7
SOP
SOP
SOP
f1(x,y,z) = f(0,0,1) x’y’z + f(1,0,0) xy’z’ + f(1,1,1) xyz = x’y’z + xy’z’ + xyz = m1 + m4 + m7
KONVERSI KE BENTUK STANDAR/KANONIK
34
Contoh Soal 2.4
Cari bentuk standar dan kanonik dari f(x,y) = x’
f(x,y) = x’ . 1 identitas
= x’ . (y + y’)
komplemen
= x’y + x’y’ distributif
= m(0,1)
Bentuk standar : x’y + x’ y’
Bentuk kanonik : m(0,1) bentuk SOP
f’(x,y) = x . 1 identitas
= x . (y + y’) komplemen
= xy + xy’ distributif
= m(2,3)
(f’(x,y))’= (x’+y’).(x’+y)
= M(2,3)
Bentuk standar : f(x,y) = (x’+y’).(x’+y)
Bentuk kanonik : M(2,3) bentuk POS
Contoh Soal 2.4
Cari bentuk standar dan kanonik dari f(x,y) = x
Contoh Soal 2.5Cari bentuk standar dari f(x,y,z) = y’ + xy + x’yz’Jawab :f(x,y,z) = y’ + xy + x’yz’ lengkapi literal pada tiap suku
= y’(x+x’)(z+z’) + xy(z+z’) + x’yz’= (xy’ + x’y’)(z+z’) + xyz + xyz’ + x’yz’
f(x,y,z) = xy’z + xy’z’ + x’y’z + x’y’z’ + xyz + xyz’ + x’yz’= m5 + m4 + m1+ m0 + m7 + m6 + m2
SOPBentuk Standar : f(x,y,z)= xy’z + xy’z’ + x’y’z + x’y’z’ + xyz + xyz’ + x’yz’Bentuk Kanonik : f(x,y) = m(0, 1, 2, 4, 5, 6, 7)
atau POSBentuk Standar : f(x,y,z) = x + y’ + z’Bentuk Kanonik : f(x,y) = M(3)
36
37Contoh Soal 2.6
Cari bentuk standar dan kanonik dari f(x,y,z) = y’ + xy + x’yz
f(x,y) = y’ + xy + x’yz’ lengkapi literal pada tiap suku
= 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’
= m5 + m4 + m1+ m0 + m7 + m6 + m2
Bentuk Standar : f(x,y,z)= xy’z + xy’z’ + x’y’z + x’y’z’ + xyz + xyz’ +
x’yz’
Bentuk Kanonik : f(x,y) = m(0, 1, 2, 4, 5, 6, 7) SOP
Bentuk Standar : f(x,y,z) = x + y’ + z’
Bentuk Kanonik : f(x,y) = M(3) POS
Latihan
1. Cari bentuk standar dari : a. f(x,y,z) = x + z,b. f(x,y,z) = z’
2. Cari bentuk Kanonik dari : a. f(x,y) = x’y + xy’ b. f(x,y,z) = x’y’z + xy’z’ + xyz
38
KONVERSI KE BENTUK SOPContoh Soal 2.7Nyatakan Fungsi Boolean f(x,y,z) = x + y’z dalam SOPJawab :Lengkapi literal untuk setiap suku agar samaf(x,y,z) = x . (y+y’).(z+z’) + (x+x’) . y’z
= (xy+xy’)(z+z’) + xy’z + x’y’z= xyz + xyz’ + xy’z + xy’z’ + xy’z + x’y’z= xyz + xyz’ + xy’z + xy’z’ + x’y’z= m7 + m6 + m5 + m4 + m1
= m(1, 4, 5, 6, 7)
39
Contoh Soal 2.8Nyatakan Fungsi Boolean f(x,y,z) = x’y’z + xz + yz
dalam SOPJawab :Lengkapi literal untuk setiap suku agar samaf(x,y,z) = x’y’z + xz + yz
= x’y’z + x. (y+y’) . z + (x+x’) . yz= x’y’z + xyz + xy’z + xyz + x’yz= m1 + m3 + m5 + m7
= m(1, 3, 5, 7)
40
Contoh Soal 2.9Nyatakan Fungsi Boolean f(w,x,y,z) = wxy + yz + xy dalam SOPJawab :Lengkapi literal untuk setiap suku agar samaf(w,x,y,z) = wxy + yz + xy
= wxy . (z+z’) + (w+w’)(x+x’) . yz + (w+w’) . xy . (z+z’)
= wxyz + wxyz’ + (wx+wx’+w’x+w’x’)yz + (wxy+w’xy)(z+z’)
= wxyz + wxyz’ + wxyz + wx’yz + w’xyz + w’x’yz + wxyz + wxyz’ + w’xyz + w’xyz’
= w’x’yz + w’xyz’ + w’xyz + wx’yz + wxyz’ + wxyz = m(3, 6, 7, 10, 14, 15)
41
KONVERSI KE BENTUK POSContoh Soal 2.10Nyatakan Fungsi Boolean f(x,y,z) = x y+ x’z dalam POSJawab :
Bentuk fungsi ke POSf(x,y,z) = xy + x’z
= (xy + x’)(xy + z) distributif= (x + x’)(y + x’)(x + z)(y + z) distributif= (x’ + y)(x + z)(y + z) komplemen,
identitas
Lengkapi literal untuk setiap suku agar samaSuku-1 x’ + y = x’ + y + zz’
= (x’ + y + z)(x’ + y + z’)Suku-2 x + z = x + z + yy’
= (x + y + z)(x + y’ + z)Suku-3 y + z = xx’ + y + z
= (x + y + z)(x’ + y + z)
42
KONVERSI KE BENTUK POSf(x,y,z) = (x’ + y)(x + z)(y + z)Lengkapi literal untuk setiap suku agar samaSuku-1 x’ + y = (x’ + y + z)(x’ + y + z’)Suku-2 x + z = (x + y + z)(x + y’ + z)Suku-3 y + z = (x + y + z)(x’ + y + z)
Semua suku dengan literal lengkap :f(x,y,z) = (x’ + y)(x + z)(y + z)
= (x + x’)(y + x’)(x + z)(y + z) = (x’ + y)(x + z)(y + z) = (x’+y+z)(x’+y+z’)(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 . M2 . M4 . M5
= M(0, 2, 4, 5)
43
Contoh Soal 2.11Nyatakan Fungsi Boolean f(x,y,z) = (x+z)(y’+z’) dalam POSJawab :Fungsi Boolean asumsi sudah dalam bentuk POSf(x,y,z) = (x+z)(y’+z’) lengkapi literal pada tiap suku
= (x+yy’+z)(xx’+y’+z’) identitas, komplemen= (x+y+z)(x+y’+z)(x+y’+z’)(x’+y’+z’) distributif= M0 . M2 . M3 . M7
44