ALJABAR BOOLEAN

1. Pengantar.

• Jika B adalah himp. dengan 2 operasi biner (+ dan *) dan operasi [’], elemen 0 dan 1 merupakan 2 elemen berbeda dalam B, maka [B, +, *, ’, 0, 1] disebut aljabar Boolean jika aksioma-aksioma berlaku untuk setiap elemen a, b, c dalam B, sbb :

Hukum komutatif.

a+b=b+a                          a*b=b*a

Hukum distributif.

a*(b+c)=(a*b)+(a*c).

a+(b*c)=(a+b)*(a+c).

Hukum identitas.

a+0=a.                              a*1=a

Hukum komplemen.

a+a’=1.                            a*a’=0.

• Dlm Aljabar Boolean, elemen 0 disebut elemen zero, elemen 1 disebut elemen unit, a’ disebut komplemen a.
• Hukum-hukum lain yang berlaku dalam aljabar Boolean :

1.Hukum idempotent.

a+a=a.                                   a*a=a.

2.Hukum keterbatasan (boundedness).

a+1=1                                    a*0=0.

3.Hukum penyerapan (absorbsi).

a+(a*b)=a.                           a*(a+b)=a.

4.Hukum asosiatif.

(a+b)+c=a+(b+c).               (a*b)*c=a*(b*c)

5.Hukum De Morgan.

(a+b)’ = a’ * b’                   (a*b)’=a’+b’

• Aljabar Boolean 2 nilai (0 dan 1).

• +	0	1
  0	0	1
  1	1	1

• a	a’
  1	0
  0	1

• *	0	1
  0	0	0
  1	0	1

• Contoh :

Jika a=1101, b=1011, maka :

1.a+b   = 1111.

2.a*b  = 1001.

3.a’  = 0010.

Catatan :

• 1. a+b = KPK(a,b).
• 2. a*b = FPB(a,b).

Contoh :

• 2+2=2               2*2=2                 3+7   =                   6*8     =
• 2+4=4               2*4=2                4+9   =                   12*18 =
• 4+6=12            4*6=2                4+10 =                    5*10   =
• 3+5=15            3*5=1                6+8   =                    6*9     =

Contoh :

• D70={1,2,5,7,10,14,35,70} pembagi 70, maka :
• 1. 10+14=70. 4. 2+5=10.
• 2. 10*14=2. 5. 10*35=5.
• 3. 10’=70/10=7. 6. 5’=70/5=14.

Tentukan :

• X=35*(2+7’) =
• Y=(35*10)+14’ =
• Z=(2+7)*(14+10)’   =
• Buktikan hukum penyerapan.
• Buktikan hukum distributif.
• Buktikan hukum De Morgan.

Prinsip Dualitas

• Prinsip dualitas dari S adalah pernyataan yang diper-oleh dengan mengubah oprasi + menjadi * (atau seba-liknya) dan elemen 0 menjadi 1 (atau sebaliknya).

Contoh :

(a*1)*(0+a’)=0 dualnya : (a+0)+(1*a’)=1.

a+a’b = a+b  dualnya :   a(a’+b) = ab

Tentukan dual dari :

1.a(a’+b)=ab.

2.(a+1) (a+0)=a

3.(a+b) (b+c) =ac+b

  Pembuktian rumus dualitas dilakukan berdasarkan ak-sioma dan sifat aljabar Boolean, yaitu:

• Buktikan bahwa :

a+a = a

Pembuktian :

  a+a  = (a+a) (1)               identitas

           = (a+a) (a+a’)         komplemen

           = a+(a.a’)                distributif.

           = a+0                        identitas.

          = a.

a.a = a

Pembuktian :

  a.a  = (a.a) + 0               identitas

         = (a.a) + (a.a’)         komplemen

         = a (a+a’)                 distributif.

         = a.1                         identitas.

         = a.

a+1 = 1

Pembuktian :

  a+1  = a+(a+a’)         komplemen

          = (a+a) +a’         asosiatif

          = a+a’                 distributif.

          = 1                       komplemen.

Fungsi Boole.

• Aljabar Boole 2 nilai, B={0,1}. Peubah (variabel) x di-sebut peubah Boole (peubah linier) jika nilainya hanya dari B. Fungsi Boole adalah ekspresi yang dibentuk dari peubah biner, 2 operator biner [+] dan [*], operator uner komplemen [‘]. Setiap peubah Boole, termasuk komplemen disebut literal.

Contoh :

1.f(x)   = x

2.f(x,y)  = x’y + xy’ + y’

3.f(x,y)  = x’ y’

4.f(x,y,z)   = xyz’

5.f(x,y,z)   = xy’z + yz’ + xyz’

• Fungsi : h(x,y,z) = xyz’
• Untuk : h(1,1,0) = 1.1.0’

                             = 1.1.1

                            = 1.

Contoh :

• Diketahui fungsi Boole h(x,y,z) = xyz’ nyatakan h dalam bentuk tabel kebenaran.

X	Y	Z	Z’	h=xyz’
0	0	0	1	0
0	0	1	0	0
0	1	0	1	0
0	1	1	0	0
1	0	0	1	0
1	0	1	0	0
1	1	0	1	1
1	1	1	0	0

Prinsip dualitas.

• Dual dari fungsi Boole adalah fungsi lain yang diperoleh dengan mengubah + menjadi * (atau sebaliknya) dan 0 menjadi 1 (atau sebaliknya), komplemen tetap komplemen. 
• Fungsi F dualnya adalah F*
• Contoh :

1. F = (a*1) * (0+a’) = 0, dualnya :

    F* = (a+0) + (1+a’) = 1.

2. F = a+a’b=a+b, dualnya :

    F* = a*(a’+b)=a*b.

Komplemen fungsi : 

• Komplemen dari fungsi f adalah f’. Komplemen fungsi dapat dicari dengan 2 cara :

1. Dengan dual, yaitu :

–Tentukan dual fungsinya.

–Komplemenkan setiap variabelnya.

2. Dengan hukum De Morgan.

–(x+y)’ = x’. y’

–(x.y)’ = x’ + y’

Contoh :

Tentukan komplemen dari :

1. f(x,y) = (x+y), maka :

    f’(x,y) = (x+y)’

               = x’.y’ 

2. f(x,y,z) = x(y’z’+yz).

f’(x,y,z,) = [x (y’z’+yz)]’

            = x’+(y’z’+yz)’

           = x’+(y’z’)’.(yz)’

         = x’+(y+z)+(y’+z’).

Bentuk Kano Hukum-hukum Boole yang banyak digunakan adalah :

1.Hukum distributif.

–x(y+z)=(xy)+(xz).

–x+yz=(x+y) (x+z).

2.Hukum De Morgan.

–(x+y)’ = x’. y’

–(xy)’ = x’+ y’

  Ada dua bentuk kanonik , yaitu :

1. Minterm atau sum–of–product (SOP, notasi S/sigma)

SOP mrpk penjumlahan dari hasil kali.

2. Maxterm atau product–of–sum (POS, notasi Π/phi)

POS mrpk perkalian dari hasil jumlah.

Minterm dan Maxterm 2 peubah biner :

X	Y	Minterm		Maxterm
		Suku	Lambang	suku	Lambang
0	0	x’y’	mo	x+y	Mo
0	1	x’y	m1	x+y’	M1
1	0	xy’	m2	x’+y	M2
1	1	xy	m3	x‘+y’	M3

Minterm dan Maxterm 3 peubah biner :

X	Y	Z	Minterm		Maxterm
			Suku	Lambang	suku	Lambang
0	0	0	x’y’z’	mo	x+y+z	Mo
0	0	1	X’y’z	m1	x+y+z’	M1
0	1	0	X’yz’	m2	x+y’+z	M2
0	1	1	X’yz	m3	x+y’+z’	M3
1	0	0	xy’z’	m4	x’+y+z	M4
1	0	1	xy’z	m5	x’+y+z’	M5
1	1	0	xyz’	m6	x’+y’+z	M6
1	1	1	xyz	m7	x’+y’+z’	M7

SOP : Kombinasi peubah yang menghasilkan nilai 1 dan

POS : Kombinasi peubah yang menghasilkan nilai 0

Contoh (1) :

Tentukan nilai SOP dan POS pada tabel :

SOP :

F(x,y)    = x’y’ + xy

              = m0+m3   

              = S(0,3)

POS :

F(x,y)    = xy’ + x’y

             = M1.M2.   

             = Π(1,2)

x	y	f(x,y)
0	0	1
0	1	0
1	0	0
1	1	1

Contoh (2) :

Tentukan nilai SOP dan POS pada tabel :

x	y	Z	f(x,y,z)
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

SOP :

f(x,y,z) = x’y’z + xy’z’ + xyz

f(x,y,z) = m1 + m 4 + m7   = S(1,4,7) 

POS :

f (x,y,z)=(x+y+z)(x+y’+z)(x+y‘+z’) (x’+y+z’)(x’+y’+z)

f (x,y,z)=Mo.M2.M3.M5.M6= Π(0,2,3,5,6)

Contoh (3) :

Nyatakan fungsi Boole  f(x,y,z)=x+y’z dlm SOP dan POS

Jawab :

1. SOP :

Tiap suku harus memuat literal lengkap, shg :

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

  = m1+m4+m5+m6+m7

  = S (1,4,5,6,7)

2. POS :

f(x,y,z ) = x+y’z

      = (x+y’)(x+z) 

Tiap suku harus memuat literal lengkap, shg :

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).

                 = Mo.M2.M3.

                 = Π(0,2,3).