BAB X FUNGSI BOOLEAN, BENTUK KANONIK, DAN BENTUK BAKU

Buku Panduan Belajar Matematika Diskrit

STMIK TRIGUNA DHARMA

BAB X FUNGSI BOOLEAN, BENTUK KANONIK, DAN BENTUK BAKU 9.1 Fungsi Boolean Pada aljabar Boolean dua-nilai B = {0,1}. Peubah (variabel) x disebut peubah boolean atau peubah biner jika nilainya hanya dari B. Fungsi Boolean (disebut juga fungsi biner) adalah ekspresi yang dibentuk dari peubah biner, dua buah operator + dan g , operator uner, tanda kurung ”()” dan tanda sama ”=”. Setiap peubah boolean, termasuk komplemennya disebut literal. Contoh-contoh fungsi Boolean: 1. f ( x) = x 2. f ( x, y ) = x ' y + xy '+ y ' 3. f ( x, y ) = x ' y ' 4. f ( x, y ) = ( x + y ) ' 5. f ( x, y, z ) = xyz ' Pada contoh 5 terdiri dari 3 literal yaitu x, y, dan z ' . Fungsi tersebut akan bernilai 1 jika x =1, y =1, dan z = 0 sebab f(1,1,0) = 1.1.0’ = (1.1).1 = 1.1 = 1 Dan bernilai 0 untuk yang lainnya. Selain secara aljabar fungsi Bolean bisa dinyatakan dengan tabel kebenaran (truth table). Contoh 9.1 Dari contoh 5 f ( x, y, z ) = xyz ' nyatakan f dalam tabel kebenaran. Penyelesaian:

Langkah Pasti Menuju Sukses

x

y

z

z'

f ( x, y , z )

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

84

Buku Panduan Belajar Matematika Diskrit

STMIK TRIGUNA DHARMA

9.2 Fungsi Komplemen Fungsi komplemen dari suatu fungsi f yaitu f ' dapat dicari dengan menukarkan nilai 0 menjadi 1 dan nilai 1 menjadi 0. Ada dua cara yang dapat digunakan untuk membentuk fungsi komplemen: 1. Menggunakan hukum De Morgan ( x1 + x2 + K + xn ) ' = x1 ' x2 'K xn '

dan dualnya: ( x1 gx2 gK gxn ) ' = x1 ' + x2 ' + K + xn '

Contoh: misal f ( x, y, z ) = x( y ' z '+ yz ) maka f '( x, y, z ) = x ' + ( y ' z ' + yz ) ' = x ' + ( y ' z ') ' ( yz ) ' = x ' + ( y + z )( y ' + z ' )

2. Menggunakan Prinsip Dualitas Cari dual dari f , lalu komplemenkan setiap literalnya. Contoh: Misal f ( x, y, z ) = x( y ' z '+ yz ) maka Dual dari f : x + ( y '+ z ')( y + z ) Komplemenkan tiap literalnya: x '+ ( y + z )( y '+ z ') = f ' Jadi, f '( x, y, z ) = x '+ ( y + z )( y '+ z ') Contoh 9.2 Carilah komplemen dari f ( x, y, z ) = x ' ( yz ' + y ' z ) Penyelesaian: Dengan hukum De Morgan: f '( x, y, z ) = ( x ') ' + ( yz ') ' ( y ' z ) ' = x + ( y '+ z )( y + z ')

Dengan prinsip dualitas: Dual dari f = x ' + ( y + z ') ( y '+ z ) f '( x, y, z ) = ( x ') ' + ( y '+ ( z ') ') (( y ') '+ z ') f '( x, y, z ) = x + ( y '+ z )( y + z ')

Langkah Pasti Menuju Sukses

85

Buku Panduan Belajar Matematika Diskrit

STMIK TRIGUNA DHARMA

Bentuk fungsi Boolean mungkin mempunyai ekspresi aljabar yang berbeda akan tetapi sebenarnya nilai fungsinya sama. Contoh: f ( x, y ) = x ' y ' dan h( x, y ) = ( x + y ) ' f ( x, y, z ) = x ' y ' z + xy ' z '+ xyz dan g ( x, y, z ) = ( x + y + z )( x + y '+ z )( x + y '+ z ')( x '+ y + z ')( x '+ y '+ z ) Adalah dua buah fungsi yang sama. Fungsi yang pertama f muncul dalam bentuk penjumlah dari perkalian, sedangkan fungsi yang kedua g muncul dalam bentuk perkalian dari hasil jumlah. Perhatikan juga bahwa setiap suku (term) mengandung literal yang lengkap x, y, dan z. 9.3 Bentuk Kanonik Adalah fungsi Boolean yang dinyatakan sebagai jumlah dari hasil kali, hasil kali dari jumlah dengan setiap suku mengandung literal yang lengkap. Ada dua macam bentuk kanonik: 1. Minterm atau sum-of-product (SOP): Jumlah dari Perkalian 2. Maxterm atau product-of-sum (POS): Perkalian dari Jumlah Tabel 9.1 Tabel Kebenaran untuk Minterm dan Maxterm Minterm Suku Lambang x' y' m0

Maxterm Suku Lambang x+ y M0

x

y

0

0

0

1

x' y

m1

x+ y'

M1

1

0

m2

x '+ y

M2

1

1

xy ' xy

m3

x '+ y '

M3

x

y

z

0

0

0

Minterm Suku Lambang x' y'z' m0

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

m6

x '+ y '+ z

M6

1

1

1

xyz ' xyz

m7

x '+ y '+ z '

M7

Langkah Pasti Menuju Sukses

Maxterm Suku Lambang x+ y+ z M0

86

Buku Panduan Belajar Matematika Diskrit

STMIK TRIGUNA DHARMA

Perbedaan minterm dan maxterm adalah: Untuk membentuk minterm (SOP) perhatikan kombinasi peubah yang menghasilkan nilai 1. Jika bernilai 1 maka bentuknya tidak komplemen, dan dikomplemenkan jika 0. Contoh: Kombinasi 001, 100 dan 111 dituliskan x ' y ' z , xy ' z ' dan xyz . Untuk membentuk maxterm (POS) perhatikan kombinasi peubah yang menghasilkan nilai 0. Jika bernilai 0 maka tidak komplemen. Contoh: Kombinasi 000, 010, 011, 101 dan 110 dituliskan ( x + y + z ), ( x + y '+ z ), ( x + y '+ z ' ), ( x '+ y + z ' ) dan ( x '+ y '+ z ) Notasi  dan  berguna untuk mempersingkat penulisan ekspresi dalam bentuk SOP dan POS. Contoh 9.3

x

y

z

x' y'z

xy ' z '

xyz

f ( x, y , z )

0

0

0

0

0

0

0

0

0

1

1

0

0

1

0

1

0

0

0

0

0

0

1

1

0

0

0

0

1

0

0

0

1

0

1

1

0

1

0

0

0

0

1

1

0

0

0

0

0

1

1

1

0

0

1

1

Dari tabel kebenaran di atas nyatakan fungsi f ( x, y, z ) = x ' y ' z + xy ' z '+ xyz dalam bentuk kanonik SOP dan POS! Penyelesaian: 1. SOP Perhatikan kombinasi peubah yang mengasilkan nilai 1. Bentuk kanonik SOP dari fungsi f ( x, y, z ) = x ' y ' z + xy ' z '+ xyz Dalam bentuk lain adalah: f ( x, y, z ) = x ' y ' z + xy ' z '+ xyz

= m1 + m4 + m7 = S (1, 4, 7)

Langkah Pasti Menuju Sukses

87

Buku Panduan Belajar Matematika Diskrit

STMIK TRIGUNA DHARMA

2. POS Perhatikan kombinasi peubah yang mengasilkan nilai 0. f ( x, y, z ) = ( x + y + z )( x + y '+ z )( x + y '+ z ')( x '+ y + z ')( x '+ y '+ z ) Dalam bentuk lain f ( x, y, z ) = M 0 M 2 M 3 M 5 M 6 = P (0, 2,3,5, 6)

Bentuk Baku Dua bentuk kanonik adalah bentuk dasar yang diperoleh dengan membaca fungsi dari tabel kebenaran. Bentuk ini umumnya sangat jarang muncul karena setiap suku (term) di dalam bentuk kanonik harus mengandung literal atau peubah yang lengkap baik dalam bentuk normal x atau dalam bentuk komplemennya x. Cara lain untuk mengekspresikan fungsi Boolean adalah bentuk baku (standard). Pada bentuk ini suku-suku yang dibentuk fungsi dapat mengandung satu, dua, atau sejumlah literal. Dua tipe bentuk baku adalah baku SOP dan baku POS. Contoh 9.4 Nyatakan fungsi f ( x, y, z ) = x + y ' z dalam tabel kebenaran, selanjutnya carilah bentuk baku SOP dan POS nya! Penyelesaian: Tabel kebenarannya sebagai berikut:

x

y

z

y'

y'z

f ( x, y , z )

Minterm

Maxterm

0

0

0

1

0

0

m0

M0

0

0

1

1

1

1

m1

M1

0

1

0

0

0

0

m2

M2

0

1

1

0

0

0

m3

M3

1

0

0

1

0

1

m4

M4

1

0

1

1

1

1

m5

M5

1

1

0

0

0

1

m6

M6

1

1

1

0

0

1

m7

M7

Langkah Pasti Menuju Sukses

88

Buku Panduan Belajar Matematika Diskrit

STMIK TRIGUNA DHARMA

Bentuk SOP: Perhatikan kombinasi peubah yang menghasilkan nilai 1. f ( x, y, z ) = x ' y ' z + xy ' z '+ xy ' z + xyz '+ xyz Dalam bentuk lain: f ( x, y, z ) = m1 + m4 + m5 + m6 + m7 = S (1, 4,5, 6, 7)

Bentuk POS: Perhatikan kombinasi peubah yang mengasilkan nilai 0. f ( x, y, z ) = ( x + y + z )( x + y '+ z )( x + y '+ z ') Dalam bentuk lain: f ( x, y, z ) = ( x + y + z )( x + y '+ z )( x + y '+ z ')

= M 0M 2M 3 = P (0, 2,3) Latihan 1. Nyatakan fungsi f ( x, y, z ) = y '+ xy + x ' yz dalam tabel kebenaran 2. Nyatakan fungsi Boolean f(x,y,z) = xy + xz dalam bentuk POS. 3. Nyatakan fungsi f ( x, y, z ) = y '+ xy + x ' yz ' dalam tabel kebenaran. 4. Carilah bentuk kanonik SOP dan POS dari f ( x, y, z ) = y '+ xy + x ' yz ' 5. Carilah bentuk kanonik SOP dari fungsi f(x,y,z) yang ditunjukkan pada tabel kebenaran berikut ini.

Langkah Pasti Menuju Sukses

x

y

z

f ( x, y , z )

0

0

0

1

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

1

1

0

1

0

1

1

0

1

1

1

1

0 89