REPRSENTASI FUNGSI BOOLE PADA GRAF KUBUS

Prosiding Seminar Nasional Matematika dan Terapannya 2016 p-ISSN : 2550-0384; e-ISSN : 2550-0392

REPRSENTASI FUNGSI BOOLE PADA GRAF KUBUS Wulan Cahyani Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Jenderal Soedirman [email protected] Siti Rahmah Nurshiami Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Jenderal Soedirman Ari Wardayani Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Jenderal Soedirman ABSTRACT. This research discussed about range of simplification Boole functions with 2, 3, 4 and 5 variables in a graph Cube. Two vertices of the cube graph is connected if and only if their binary representations differ in a single digit.

Representation of Boolean function with two variable are lines with two vertices adjacent have one bits in the same position. Representation of Boolean functions with 3 variable are line and square, with two vertices adjacent have two bits in the same position and square with four vertices adjacent have a 1 bit in the same position, respectively. Representation of Boolean function with 4 variable are line, square, and cube, with two vertices adjacent have 3 bits at the same position, four vertices adjacent have two bits in the same position, 8 vertices adjacent have one bit in the same position, respectively. Representation of Boolean function with 5 variable are line, square, cube, tesseract, with two vertices adjacent having 4 bits in the same position, four vertices adjacent have 3 bits at the same position, 8 vertices adjacent have two bits in the same position and 16 vertices adjacent have one bit in the same position. Keywords: Boole function, graph Cube, Gray code, K-Map

ABSTRAK. Penelitian ini mengkaji representasi fungsi Boole dengan 2, 3, 4 dan 5 variabel pada graf Kubus. Dua simpul pada graf kubus terhubung jika dan hanya jika bit pada string yang direpresentasikan berbeda tepat satu bit. Representasi fungsi Boole dengan 2 variabel berbentuk garis apabila 2 simpul bertetangga memiliki 2 bit dengan posisi yang sama. Representasi fungsi Boole dengan 3 variabel berbentuk garis apabila 2 simpul yang bertetangga memiliki 2 bit dengan posisi yang sama, berbentuk persegi apabila 4 simpul bertetangga memiliki 1 bit

Representasi Fungsi Boole pada Graf Kubus

25

dengan posisi yang sama. Representasi fungsi Boole dengan 4 variabel masingmasing berbentuk garis, atau persegi, atau, kubus dengan 2 simpul bertetangga memiliki 3 bit dengan posisi yang sama, atau 4 simpul bertetangga memiliki 2 bit dengan posisi yang sama, atau kubus dengan 8 simpul bertetangga memiliki 1 bit dengan posisi yang sama. Representasi fungsi Boole dengan 5 variabel masingmasing berbentuk garis, atau persegi, atau kubus, atau bangun 4 dimensi dengan 2 simpul bertetangga memiliki 4 bit dengan posisi yang sama, 4 simpul bertetangga memiliki 3 bit dengan posisi yang sama, 8 simpul bertetangga memiliki 2 bit dengan posisi yang sama, 16 simpul bertetangga memiliki 1 bit dengan posisi yang sama. Kata Kunci: fungsi Boole, graf kubus, K-Map, Kode gray

1. PENDAHULUAN Aljabar Boole pertama kali dikemukakan oleh seorang matematikawan Inggris, George Boole pada tahun 1854. Dalam buku The Laws of Thought, Boole memaparkan aturan-aturan dasar logika yang kemudian dikenal sebagai logika Boole. Aturan dasar logika ini membentuk sistem matematika yang disebut Aljabar Boole. Pada tahun 1938, Claude Shannon memperlihatkan penggunaan Aljabar Boole untuk merancang rangkaian sirkuit yaitu rangkaian pengalihan telepon. Rangkaian pengalihan telepon bekerja dengan mode operasi biner. Aljabar Boole telah menjadi dasar teknologi komputer digital karena rangkaian elektronik didalam komputer juga bekerja dengan mode operasi biner. Saat ini Aljabar Boole digunakan secara luas dalam perancangan rangkaian pensaklaran, rangkaian digital. Pada Aljabar Boole terdapat variabel-variabel yang membentuk fungsi Boole. Fungsi Boole dapat disajikan dalam bentuk Sum of Product (SOP) dan Product of Sum (POS). Fungsi-fungsi Boole tersebut dapat diimplementasikan menjadi rangkaian digital. Penyederhanaan fungsi Boole bertujuan untuk mendapatkan rangkaian yang lebih sederhana, karena jumlah gerbang yang terbentuk lebih sedikit. Beberapa metode untuk menyederhanakan fungsi Boole, yaitu secara aljabar menggunakan aksioma Aljabar Boole, metode Peta Karnaugh (K-Map), metode Tabulasi (Quine-McCluskey) dan metode Map Entered Variables (MEV). Purwokerto, 3 Desember 2016

26

W. Cahyani d.k.k.

Dalam penelitian ini akan digunakan metode Peta Karnaugh, yaitu metode grafis untuk menyederhanakan fungsi Boole. Banyaknya variabel pada fungsi Boole berpengaruh pada banyaknya kotak yang terbentuk pada K-Map. Semakin banyak variabel yang digunakan maka semakin banyak pula kotak yang terbentuk pada K-Map. Pada K-Map kotak-kotak bernilai 1 dapat dikelompokan sehingga memudahkan untuk penyederhanaan fungsi Boole. Kode gray pada K-Map dapat diinterpretasikan kedalam graf kubus ( Qn ), yaitu graf yang simpulnya merepresentasikan string sebanyak 2n bit. Penulis tertarik untuk menentukan hasil penyederhanaan fungsi Boole pada graf kubus. Adapun tujuan dari penelitian ini yaitu mengkaji bentuk graf kubus untuk fungsi Boole dengan 2, 3, 4 dan 5 variabel dan representasi fungsi boole pada graf kubus.

2. HASIL PENELITIAN Bagian ini membahas mengenai penyederhanaan fungsi Boole, bentuk graf kubus serta representasi fungsi Boole dengan 2, 3, 4 dan 5 variabel pada graf kubus.

2.1 Representasi Fungsi Boole dengan 2 Variabel pada Graf Kubus Kode gray pada K-Map 2 variabel yaitu 00, 01, 11 dan 10 dapat direpresentasikan ke dalam graf kubus. Berikut representasi fungsi Boole pada graf kubus untuk fungsi Boole dengan 2 variabel yang dinotasikan Q2 .

10

11

00

01

Gambar 1 Representasi fungsi Boole pada graf Q2

Diberikan fungsi Boole

f (a, b)  a ' b  ab . Dengan menggunakan

K-Map

diperoleh hasil penyederhanaan fungsi Boole f (a, b)  a ' b  ab adalah b. Berikut representasi fungsi Boole f (a, b)  a ' b  ab pada Q2 .

Purwokerto, 3 Desember 2016


10

27

11 b

00

01

Gambar 2 Representasi fungsi Boole f (a, b)  a ' b  ab pada Q2

Diperoleh representasi fungsi Boole f (a, b)  a ' b  ab berbentuk garis. Dengan cara yang sama diperoleh representasi 3 fungsi Boole dengan 2 variabel yang memiliki 2 minterm juga berbentuk garis.

2.2 Representasi Fungsi Boole dengan 3 Variabel pada Graf Kubus Kode gray pada K-Map 3 variabel, yaitu 000, 001, 011, 010, 110, 111, 101, dan 100 dapat direpresentasikan ke dalam graf kubus. Berikut representasi fungsi Boole pada graf kubus untuk fungsi Boole dengan 3 variabel

yang

dinotasikan Q3 .

00 10 0 0 01 11 0

00 10 1 1 01 11 1 1

0

Gambar 3 Representasi fungsi pada graf Q3

Diberikan

fungsi

menggunakan

Boole

K-Map

f (a, b, c)  a ' b ' c  a ' bc  abc  ab ' c .

diperoleh

hasil

penyederhanaan

fungsi

Dengan Boole

f (a, b, c)  a ' b ' c  a ' bc abc  ab ' c adalah c . Berikut representasi fungsi Boole f (a, b, c)  a ' b ' c  a ' bc abc  ab ' c pada graf kubus Q3 .


28

W. Cahyani d.k.k.

000

001

010

101 c 011 111

100

110

Gambar 4 Representasi fungsi Boole f (a, b, c)  a ' b ' c  a ' bc  abc  ab ' c pada Q3

Diperoleh

representasi

fungsi

Boole

f (a, b, c)  a ' b ' c  a ' bc  abc  ab ' c

berbentuk bidang. Dengan cara yang sama diperoleh representasi 5 fungsi Boole dengan tiga variabel yang memiliki 4 minterm juga berbentuk bidang. Kemudian diberikan fungsi Boole menggunakan

K-Map

f (a, b, c)  a ' b ' c  a ' bc

diperoleh adalah

hasil

f (a, b, c)  a ' b ' c  a ' bc . Dengan

penyederhanaan

fungsi

Boole

a ' c . Berikut representasi fungsi Boole

f (a, b, c)  a ' b ' c  a ' bc pada graf Q3 .

001

000 100

101 010

011 111

110

Gambar 5 Representasi fungsi Boole f (a, b, c)  a ' b ' c  a ' bc pada Q3

Diperoleh representasi fungsi Boole f (a, b, c)  a ' b ' c  a ' bc berbentuk garis. Dengan cara yang sama diperoleh representasi 11 fungsi Boole dengan tiga variabel yang memiliki 2 minterm juga berbentuk garis.



29

2.3 Representasi Fungsi Boole dengan 4 Variabel pada Graf Kubus Kode gray pada K-Map 4 variabel, yaitu 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, dan 1000 dapat direpresentasikan ke dalam graf kubus. Berikut representasi fungsi Boole pada graf Q4 . 0110

1110

0111 1111 1010 1011 0011 0101 1101 1001 0100 0001 1100

0010

0000

1000


Diberikan fungsi Boole f (a, b, c, d )  (0,1, 4,5,8,9,12,13) . Dengan mengguna kan K-Map diperoleh hasil penyederhanaan fungsi Boole f (a, b, c, d )  (0,1, 4,5, 8,9,12,13) adalah c '. Berikut representasi fungsi Boole f (a, b, c, d )  (0,1, 4,5, 8,9,12,13) pada graf Q4 .

Gambar 7 Representasi fungsi Boole

f (a, b, c, d )  (0,1, 4,5,8,9,12,13) pada graf Q4

Berdasarkan Gambar representasi fungsi Boole

f (a, b, c, d )  (0,1, 4,5,8,9,

12,13) berbentuk ruang. Dengan cara yang sama diperoleh representasi 7 fungsi

Boole dengan 4 variabel yang memiliki 8 minterm juga berbentuk ruang.


30

W. Cahyani d.k.k.

Kemudian

diberikan

fungsi

Boole

f (a, b, c, d )  a ' b ' c ' d ' a ' bc ' d '

abc ' d ' ab ' c ' d ' . Dengan menggunakan K-Map diperoleh hasil penyederhanaan fungsi Boole f (a, b, c, d )  a ' b ' c ' d ' a ' bc ' d ' abc ' d ' ab ' c ' d ' adalah c ' d '. Berikut representasi fungsi Boole

f (a, b, c, d )  a ' b ' c ' d ' a ' bc ' d ' abc ' d '

ab ' c ' d ' pada graf Q4 .


f (a, b, c, d )  a ' b ' c ' d ' a ' bc ' d ' abc ' d ' ab ' c ' d ' pada graf Q4

Berdasarkan

Gambar

representasi

fungsi

Boole

f (a, b, c, d )  a ' b ' c ' d '

a ' bc ' d ' abc ' d ' ab ' c ' d ' berbentuk bidang. Dengan cara yang sama diperoleh 26 representasi fungsi Boole dengan 4 variabel yang memiliki 4 minterm juga berbentuk bidang . Selanjutnya, diberikan fungsi Boole

f (a, b, c, d )  a ' b ' c ' d ' a ' bc ' d ' .

Dengan menggunakan K-Map diperoleh hasil penyederhanaan fungsi Boole f (a, b, c, d )  a ' b ' c ' d ' a ' bc ' d ' adalah a ' c ' d ' . Berikut representasi fungsi

Boole f (a, b, c, d )  a ' b ' c ' d ' a ' bc ' d ' pada Q4 .

Gambar 9 Representasi fungsi Boole f (a, b, c, d )  a ' b ' c ' d ' a ' bc ' d '



31

Berdasarkan Gambar representasi fungsi Boole f (a, b, c, d )  a ' b ' c ' d ' a ' bc ' d ' berbentuk garis. Dengan cara yang sama diperoleh representasi 32 fungsi Boole dengan 4 variabel yang memiliki 2 minterm juga berbentuk garis.

2.4 Representasi Fungsi Boole dengan 5 Variabel pada Graf Kubus Kode gray pada K-Map 5 variabel yaitu 00000, 00001, 00010, 00011, 00100, 00101, 00110, 00111, 01000, 01001, 01010, 01011, 01100, 01101, 01110, 01111, 10000, 10001, 10010, 10011, 10100, 10101, 10110, 10111, 11000, 11001, 11010, 11011, 11100, 11101, 11110, 11111 dapat di representasikan ke dalam graf kubus. Berikut representasi fungsi Boole pada graf kubus untuk fungsi Boole dengan 5 variabel yang dinotasikan dengan Q5 .


Diberikan fungsi Boole dengan 5 variabel yaitu, f (a, b, c, d , e)   (8,9,10,11,12, 13,14,15, 24, 25, 26, 27, 28, 29,30,31) . Dengan menggunakan K-Map diperoleh

penyederhanaan fungsi Boole f (a, b, c, d , e)  (8,9,10,11,12,13,14,15, 24, 25, 26, 27, 28, 29,30,31) adalah b . Berikut representasi fungsi Boole f (a, b, c, d , e)   (8,9,10,11,12,13,14,15, 2425, 26, 27, 28, 29,30,31) pada graf Q5 .


32

W. Cahyani d.k.k.


f (a, b, c, d , e)   (8,9,10,11,12,13,14,15, 24, 25, 26, 27, 28, 29,30,31) pada Q5 f (a, b, c, d , e)   (8,9,10,11,


12,13,14,15, 24, 25, 26, 27, 28, 29,30,31) berbentuk ruang 4 dimensi. Dengan cara

yang sama diperoleh representasi 9 fungsi Boole

dengan 5 variabel yang

memiliki 16 minterm juga berbentuk ruang 4 dimensi. Kemudian

diberikan

fungsi

Boole

dengan

5

variabel

yaitu,

f (a, b, c, d , e)  (8,9,10, 25, 26, 27) . Dengan menggunakan K-Map diperoleh

hasil penyederhanaan fungsi Boole

f (a, b, c, d , e)  (8,9,10,11, 24, 25, 26, 27)

adalah bc '. Berikut representasi fungsi Boole f (a, b, c, d , e)  (8,9,10,11, 24, 25, 26, 27) pada Q5 .


f (a, b, c, d , e)  (8,9,10,11, 24, 25, 26, 27) pada Q5

Berdasarkan Gambar representasi fungsi Boole f (a, b, c, d , e)  (8,9,10,11, 24, 25, 26, 27) berbentuk ruang. Dengan cara yang sama diperoleh representasi 36

fungsi Boole dengan 5 variabel yang memiliki 8 minterm juga berbentuk ruang.



Selanjutnya

diberikan

fungsi

33

Boole

dengan

5

variabel

yaitu,

f (a, b, c, d , e)  a ' b ' c ' d ' e ' a ' b ' c ' d ' e  ab ' c ' d ' e ' ab ' c ' d ' e . Dengan menggu

nakan

K-Map

diperoleh

hasil

penyederhanaan

f (a, b, c, d , e)  a ' b ' c ' d ' e ' a ' b ' c ' d ' e  ab ' c ' d ' e ' ab ' c ' d ' e

Berikut representasi fungsi Boole

fungsi

Boole

adalah

b 'c 'd '

f (a, b, c, d , e)  a ' b ' c ' d ' e ' a ' b ' c ' d ' e 

ab ' c ' d ' e ' ab ' c ' d ' e pada Q5 .

Gambar 13 Representasi fungsi Boole f (a, b, c, d , e)  a ' b ' c ' d ' e ' a ' b ' c ' d ' e  ab ' c ' d ' e ' ab ' c ' d ' e pada graf Q5


f (a, b, c, d , e)  a ' b ' c ' d ' e '

a ' b ' c ' d ' e  ab ' c ' d ' e ' ab ' c ' d ' e berbentuk bidang. Dengan cara yang sama diperoleh representasi 80 fungsi Boole dengan 5 variabel yang memiliki 4 minterm juga berbentuk bidang. Diberikan fungsi Boole dengan 5 variabel yaitu, f (a, b, c, d , e)  ab ' c ' de 

ab ' c ' de ' . Dengan menggunakan K-Map diperoleh hasil penyederhanaan fungsi Boole f (a, b, c, d , e)  ab ' c ' de  ab ' c ' de ' adalah ab ' c ' d . Berikut representasi fungsi Boole f (a, b, c, d , e)  ab ' c ' de  ab ' c ' de ' pada Q5 .

.


f (a, b, c, d , e)  ab ' c ' de  ab ' c ' de ' pada Q5 .


34

W. Cahyani d.k.k.


f (a, b, c, d , e)  ab ' c ' de 

ab ' c ' de ' berbentuk garis. Dengan cara yang sama diperoleh representasi 80 fungsi Boole dengan 5 variabel yang memiliki 2 minterm juga berbentuk garis.

3. KESIMPULAN DAN SARAN 3.1 Kesimpulan Berdasarkan pada bagian Hasil dan Pembahasan, diperoleh bahwa : 1.

Graf Q2 terdiri atas 4 simpul. Representasi fungsi Boole pada graf Q2 berbentuk garis dengan 2 simpul yang memiliki 1 bit dengan posisi yang sama.

2.

Graf Q3 terdiri atas 8 simpul. Representasi fungsi Boole pada graf Q3 berbentuk garis dengan 2 simpul yang memiliki 2 bit dengan posisi yang sama dan berbentuk bidang dengan 4 simpul yang memiliki 1 bit dengan posisi yang sama.

3.

Graf Q4 terdiri atas 16 simpul. Representasi fungsi Boole pada graf Q4 berbentuk garis dengan 2 simpul yang memiliki 3 bit dengan posisi yang sama, berbentuk bidang dengan 4 simpul yang memiliki 2 bit dengan posisi yang sama dan berbentuk ruang dengan 8 simpul yang memiliki 1 bit dengan posisi yang sama.

4.

Graf Q5 terdiri atas 32 simpul. Representasi fungsi Boole pada graf Q5 berbentuk garis dengan 2 simpul yang memiliki 4 bit dengan posisi yang sama, berbentuk bidang dengan 4 simpul yang memiliki 3 bit dengan posisi yang sama, berbentuk ruang dengan 8 simpul yang memiliki 2 bit dengan posisi yang sama dan berbentuk ruang 4 dimensi dengan 16 simpul yang memiliki 1 bit dengan posisi yang sama

3.2 Saran Dalam skripsi ini, penulis membatasi masalah penyederhanaan fungsi Boole yaitu sampai dengan 5 variabel, dalam bentuk Sum of Product (SOP). Penulis menyarankan agar dilakukan pengkajian lebih lanjut untuk melakukan penentuan Purwokerto, 3 Desember 2016


35

daerah hasil penyederhanaan fungsi Boole untuk 6 atau lebih variabel, baik dalam bentuk Sum of Product (SOP) maupun Product of Sum (POS).

DAFTAR PUSTAKA Arifin, A., Aljabar Linier, ITB, Bandung, 2000. Berge, C., Graphs, Elsevier Science, North Holland, 1991. Munir, R., Matematika Diskrit, Informatika, Bandung, 2012. Sukirman, Pengantar Aljabar Abstrak, FMIPA UNY, Yogyakarta, 2000. Whitesitt, J. E., Boolean Algebra and its Application, Addison-Wesley, London, 1961.


REPRSENTASI FUNGSI BOOLE PADA GRAF KUBUS

Recommend Documents