FUNGSI BOOLEAN- Logika Informatika

DEFINISI

Misalkan x₁,x₂.......x_n  merupakan variabel-variabel aljabar Boolean. Boolean dengan n variabel adalah fungsi yang dapat dibentuk dari aturan-aturan berikut :

1.       Fungsi konstan :
f(x₁,x₂,x₃,x₄......x) =

2.       Fungsi proyeksi

F(x₁,x₂,x₃,....x_n) =x   I= 1,2,... n

3.       Fungsi komplemen

g(x₁,x₂,x₃,....x_n)  = (f(x₁,x₂,x₃,....x_n))

fungsi gabungan

h(x₁,x₂,x₃,....x_n) = f(x₁,x₂,x₃,....x_n)+g(x₁,x₂,x₃,....x_n)

h(x₁,x₂,x₃,....x_n) = f(x₁,x₂,x₃,....x_n)●g(x₁,x₂,x₃,....x_n)

catatan :

fungsi identitas ; fungsi proyeksi satu variabel, dimana f(x)=x

contoh

berikuat adalah fungsi-fungsi boolean dengan variabel x,y, dan z dan a yang merupakan elemen dalam aljabar:

f(x)                 = x + x’a
g(x,y)            = x’y+xy’+y

h(x,y,z)         = axy’z=yz’+a+xy

Teorema

jika f adalah Boolean dengan satu variabel maka untuk semua nilai x adalah

f(x) = f(1)x+f(0)x’
untuk kemungkinan bentuk f :

kasus 1 :

f adalah fungsi konstan , f(x) = a
f(1)x+f(0)x’ = ax+ax’ = a(x+x’) = a1 = f(x)

kasus 2:

f adalah fungsi identitas
f(1)x+f(0)x’ = 1’+0x’ = x+0 = x = f(x)

kasus 3

h(x) = f(x)+g(x)

h()x = f(x)+g(x) = f(1)x+f(0)x’+g(1)x+g(0)x
                                                = (f(1)+g(1))x+(f(0)+ g(0))
                                                = h(1)x+h(0)x’

kasus 4

k()x        = f(x)g(x)
k()x        = f(x)g(x) = (f(1)x+f(0)x’)(g(1)x+g(0)x’)
                = f(1)g(1)xx+f(1)g(0)xx’+f(0)g(1)x’x+f(0)g(0)x’x’
                = f(1)g(1)x+f(0)g(0)x’
                = k(1)x+k(0)x’

bentuk diatas adalah bentuk kanonik fungsi boolean satu variabel, dengan cara yang sama jika f adalah fungsi boolena dengan dua variabel, maka untuk nilai x dan y bentuk kanoniknya adalah sebagai berikut :

f(x,y) = f(1,1)xy + f(1,0)xy’+f(0,1)x’y+ f(0,0)x’y’

Rumus Umum Bentuk Kanonik

Rumus pembentukan bentuk kanonik f fungsi boolean dengan n variabel adalah sebagai berikut:
f(x₁.....x_n)= f(e₁......e₂)x₁^e ₁x₂^e₂.....x_n ^e_n

Dimana e₁ bernilai 0 dan  x₁^e ₁ diartikan sebagai x₁  atau x₁^e’ sesuai dengan e₁ (bernilai 1 atau 0)

BENTUK FUNGSI

Suatu fungsi dapat dinyatakan dalam berbagai bentuk berbeda tapi mempunyai arti yang sama.

Contoh fungsi – fungsi boolean berikut :

f(x)         = x+ x’a

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

h(x,y)    = x’y’

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

f1(x,y)   = x’.y’

f2(x,y)   = (x+y)

dengan menggunakan hukum de morgan dapat dinyatakan bawa h dan k adalah fungdi yang sama, juga untuk fungsi f1 dan f2. Dapat disimpulkan bahwa berapa fungsi boolean mungkin mempunyai bentuk berbeda tetapi nilainnnya sama. Olelh karena itu, diperlukan cara untuk menentukan apakah dua ekspresi boolean ynag mempresentasikan mempunyai nilai sama. Cara tersebut adalah menggunakan bentuk standar atau bentuk kanonik.

Contoh

Fungsi boolean

F(x) = x+x’a

Dimana f mempunyai elemen aljabar boolean yaitu 0,a,a’, 1.  tentukan bentuk kanoniknya  !

Maka kita harus melakukan pemeriksaan untuk semua elemen fungsi, yaitu :

X	f(x)
0 a a’ 1	0 + 1.a = a a + a’.a =a = 0 + a a’=a.aa = a’ +a =1 1 + 0.1 = 1 + 0 = 1

 Kita dapat memperoleh bentuk kanoniknya sebagai berikut :

f(x)         = f(1)x+f (0)x’
                =1.x + a.x’
                = x+ax’
                = (x+a).(x+x’)
                = (x+a).1
                = x+a

kegunakan bentuk kanonik

bentuk kanonik digunakan untuk menentukan apakah dua ekspresi merupakan fungsi yang sama.

Seringkali fungsi Boolean dinyatakan dengan operasi yang berlebihan. Kita dapat mengkorversi bentuk fungsi Boolean menjadi bentuk minimum, yaitu fungsi yang masih menghasilkan nilai sama tapi dengan jumlah operasi yang minimum,

Cara representasi fungsi Boolean dapat dinyatakan secara :

1.       Aljabar

2.       Dengan tabel kebenaran

Contoh : Fungsi F = xyz’

Refresentasi  secara aljabar adalah F = xyz’

Refresentasi dengan tabel kebenarannya adalah sebagai berikut

X   Y   Z	F
0   0   0 0   0   1 0   1   0 0   1   1 1   0   0 1   0   1 1   1   0 1   1   1	0 0 0 0 0 0 1 0

Jumlah elemen dalam tabel kebenaran adalah jumlah kombinasi dari nilai variabel-variabelnya, yaitu sejumlah 2ⁿ dimana n adalah banyaknya variabel biner.

Konversi dari tabel kebenaran

Fungsi boolean yang diinyatakan tabel kebenaran dapat dikorversi menjadi bentuk aljabar.

Contoh fungsi boolean dengan tabel kebeanran sebagai berikut :

X   Y   Z	F
0   0   0 0   0   1 0   1   0 0   1   1 1   0   0 1   0   1 1   1   0 1   1   1	0 1 0 0 1 0 0 1

Dari tabel kebenaran:

(1)    F₁                  = x’y’z +xy’z’ +xyz

= m11 +m4 +m7

F1           = x’y’z’ + x’yz’ +x’yz + xy’z + xyz’

Atau

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

= (F1’)’
= M0 M2 M3 M5 M6

Bentuk (1) dan (2) merupakan fungsi/bentuk standar, yaitu fugsi yang literalnya ditulis lengkap pada tiap suku

1.       Bentuk pertama (1) disebut SOP (Sum Of Product)/ Mintrem

2.       Bentuk kedua (2) disebut POS (Product of Sum)/ Maxtrem

Fungso Boolean yang diekspresikan dalam bentuk SOP atau POS disebut fungsi/bentuk Kanonik.

BENTUK STANDAR DAN BENTUK KANONIK

Bentuk Standar Dan Bentuk Kanonik 2 Variabel

x y	Sum Of Product (SOP)		Product Of Sum (POS)
	Term	Nilai	Term	nilai
1 1 1 0 0 1 0 0	xy xy’ x’y’ x’y	M3 M2 M1 M0	X’ + y’ X’ + y X  + y X  + y	M3 M2 M1 M0

Bentuk Standar Dan Bentuk Kanonik 3 Variabel

x y	Sum Of Product (SOP)		Product Of Sum (POS)
	Term	Nilai	Term	nilai
1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0	xyz xyz’ xy’z xy’z’ x’yz x’yz’ x’y’z x’y’z’	m7 m6 m5 m4 m3 m2 m1 m0	x’ + y’+z’ x’ + y’ +z x‘ + y +z’ x’ + y +z x  + y’ +z’ x  + y’ +z x  + y +z’ x  + y +z	m7 m6 m5 m4 m3 m2 m1 m0

Sumber : Logika Matematika ( Retno Hendrowati, Ir.,MT)