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