prosiding seminar nasional matematika dan terapannya … filerepresentation of boolean function with...

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



Ari Wardayani



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

mailto:[email protected]

Representasi Fungsi Boole pada Graf Kubus 25

Purwokerto, 3 Desember 2016

dengan posisi yang sama. Representasi fungsi Boole dengan 4 variabel masing-

masing 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 masing-

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

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 ( nQ ), 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 2Q .

Gambar 1 Representasi fungsi Boole pada graf 2Q

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 2.Q

00

10

01

11



Gambar 2 Representasi fungsi Boole ( , ) 'f a b a b ab pada 2Q

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.


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 3Q .

Gambar 3 Representasi fungsi pada graf 3Q

Diberikan fungsi Boole ( , , ) ' ' ' 'f a b c a b c a bc abc ab c . Dengan

menggunakan K-Map diperoleh hasil penyederhanaan fungsi 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 3.Q

00

10

01

11

b

000

010

001

011

101

111

100

110



Gambar 4 Representasi fungsi Boole

( , , ) ' ' ' 'f a b c a b c a bc abc ab c pada 3Q

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 ( , , ) ' ' 'f a b c a b c a bc . Dengan

menggunakan K-Map diperoleh hasil penyederhanaan fungsi Boole

( , , ) ' ' 'f a b c a b c a bc adalah 'a c . Berikut representasi fungsi Boole

( , , ) ' ' 'f a b c a b c a bc pada graf 3.Q

Gambar 5 Representasi fungsi Boole ( , , ) ' ' 'f a b c a b c a bc pada 3Q

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.

000

010

001

011

101

111

100

110

c

000

010

001

011

101

111

100

110




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 4Q .

0000 1000

11000100

0010 1010

11100110

0111 1111

11011001

0001

00111011

0101


Diberikan fungsi Boole ( , , , ) (0,1,4,5,8,9,12,13)f a b c d . Dengan mengguna

kan K-Map diperoleh hasil penyederhanaan fungsi Boole ( , , , ) (0,1,4,5,f a b c d

8,9,12,13) adalah '.c Berikut representasi fungsi Boole ( , , , ) (0,1,4,5,f a b c d

8,9,12,13) pada graf 4Q .


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

Berdasarkan Gambar representasi fungsi Boole ( , , , ) (0,1,4,5,8,9,f a b c d

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

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



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 4Q .


( , , , ) ' ' ' ' ' ' ' ' ' ' ' 'f a b c d a b c d a bc d abc d ab c d pada graf 4Q

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 4Q .

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



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.


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 5Q .


Diberikan fungsi Boole dengan 5 variabel yaitu, ( , , , , ) (8,9,10,11,12,f a b c d e

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 5Q .




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

Berdasarkan Gambar representasi fungsi Boole ( , , , , ) (8,9,10,11,f a b c d e

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,

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

hasil penyederhanaan fungsi Boole ( , , , , ) (8,9,10,11,24,25,26,27)f a b c d e

adalah '.bc Berikut representasi fungsi Boole ( , , , , ) (8,9,10,11,24,f a b c d e

25,26,27) pada 5.Q


( , , , , ) (8,9,10,11,24,25,26,27)f a b c d e pada 5Q

Berdasarkan Gambar representasi fungsi Boole ( , , , , ) (8,9,10,11,24,f a b c d e

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 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 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 adalah ' ' 'b c d

Berikut 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 5.Q


( , , , , ) ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' '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 5Q

Berdasarkan Gambar 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 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 5.Q

.


( , , , , ) ' ' ' ' 'f a b c d e ab c de ab c de pada 5.Q



Berdasarkan Gambar representasi fungsi Boole ( , , , , ) ' '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 2Q terdiri atas 4 simpul. Representasi fungsi Boole pada graf 2Q

berbentuk garis dengan 2 simpul yang memiliki 1 bit dengan posisi yang

sama.



sama dan berbentuk bidang dengan 4 simpul yang memiliki 1 bit dengan

posisi yang sama.



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.



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



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.

prosiding seminar nasional matematika dan terapannya … filerepresentation of boolean function with...

Documents