MAKALAH SISTEM DIGITAL

“Konsep Dasar Teorema Boole & De Morgan”

Disusun Oleh :

Anin Rodahad (12131307)

Abdurrahman Ar-Rohim (12131299)

Bayu Ari Utomo ()

TEKNIK INFORMATIKA

STMIK EL RAHMA YOGYAKARTA

Jl. Sisingamangaraja no. 76 Karangkajen Yogyakarta

2014

KATA PENGANTAR

Puji syukur kami ucapkan kehadapan Tuhan Yang Maha Esa karena atas berkat

rahmatnyalah kami dapat menyelesaikan makalah yang berkaitan dengan Mata Kuliah Sistem

Digital. Makalah ini memberikan gambaran materi teorema bolle dan de Morgan, dari dasar hukum

penyajian fungsi boole, serta contoh soal

Makalah ini tentunya masih sangat jauh dari sempurna, kami berharap semoga makalah ini

dapat berguna bagi semua pihak sesuai dengan tujuan pembuatan makalah ini. Selain itu juga

kami mengharapkan kritik dan saran untuk menyempurnakan makalah kami ini. Kami juga

berterima kasih kepada semua pihak dan sumber-sumber referensi yang telah membantu dalam

penulisan makalah ini.

Yogyakarta, 5 Oktober 2014

Penulis

1

DAFTAR ISI

KATA PENGANTAR 2

DAFTAR ISI 3

BAB I PENDAHULUAN

A. Latar Belakang 4

B. Rumusan Masalah 5

C. Tujuan Dan Manfaat 5

BAB II PEMBAHASAN

A.Teorema dasar Bolee 6

Hukum Distributif 6

Hukum Asosiatif 6

Hukum Komutatif 7

Hukum Komplemen 8

Hukum Operasi 0 dan 1 8

Hukum Idempoten 9

Hukum Involusi 10

B.Penyajian Fungsi Boole 11

A.bentuk kanomik

Penjumlahan dari hasil kali (sum-of-product atau SOP) 12

Perkalian dari hasil jumlah (product-of-sum atau POS) 12

D.Penyederhanaan fungsi Boole 13

A. Penyederhanaan secara Teorema

13

B.Penyederhanaan dengan peta karnaugh 13

E.Teorema dasar De morgan 18

BAB III PENUTUP

KESIMPULAN................................................................................. 21

SARAN 21

DAFTAR PUSTAKA 222

BAB I

PENDAHULUAN

A. Latar Belakang

Teorema boole dan de Morgan merupakan teorema yang berhubungan dengan variabel-variabel

biner dan operasi-operasi logik. Variabel-variabel diperlihatkan dengan huruf-huruf alfabet, dan

tiga operasi dasar dengan AND, OR dan NOT (komplemen).

Fungsi boole terdiri dari variabel-variabel biner yang menunjukkan fungsi, suatu tanda sama

dengan, dan suatu ekspresi teorema yang dibentuk dengan menggunakan variabel-variabel biner,

konstanta-konstanta 0 dan 1, simbol-simbol operasi logik, dan tanda kurung. Suatu fungsi boole

bisa dinyatakan dalam tabel kebenaran. Suatu tabel kebenaran untuk fungsi boole merupakan

daftar semua kombinasi angka-angka biner 0 dan 1 yang diberikan ke variabel-variabel biner dan

daftar yang memperlihatkan nilai fungsi untuk masing-masing kombinasi biner.

Oleh karena itulah si penulis berharap si pembaca dapat mengetahui fungsi dan menambah

wawasan tentang teorema Boole & De Morgan.

B. Rumusan Masalah

a. Pengertian Teorema dasar boole & Hukum hukumnya?

b. Cara penyajian Fungsi Boole?

c. Penyederhanaan Fungsi Boole?

d. Pengertian Teorema dasar De Morgan?

C. Tujuan Penulisan

Selain permasalahan yang ditemuai dalam pembuatan makalah ini si penulis juga mempunyai

beberapa tujuan dalam menulis makalah ini yaitu sebagai berikut:

1. Si pembaca dapat mengetahui apa yang dimaksud dengan Teorema Boole & De Morgan

2. Si pembaca dapat mengetahui cara penyajian & penyederhanaan fungsi Boole.

3. Si pembaca dapat mengetahui apa saja hukum-hukum dari teorema dasar Boole.

D.Manfaat Penulisan

Dengan menulis makalah ini si penulis mengharapkan si pembaca dapat menambah wawasan,

memperdalami teorema Boole dan Teorema De Morgan.

3

BAB II

PEMBAHASAN

A. Teorema Dasar Boole

Konsep dasar teorema Boole (Boole Algebra) telah diletakkan oleh seorang matematisi

Inggris George Boole, pada tahun 1854. Konsep dasar itu membutuhkan waktu yang cukup

lama untuk disadari kegunaannya, baik dalam bidang matematika maupun dalam bidang

teknik.

Pada tahun 1938 Claude Shannon, seorang ahli komunikasi, memanfaatkan dan

menyempurnakan konsep Boole tersebut. Sekarang ini, teorema Boole memegang peranan

yang sangat penting, tidak saja dalam logika, tetapi juga di bidang lain seperti teori

peluang/kemungkinan, teori informasi/komunikasi, teori himpunan dan lain-lain. Teori ini juga

dipakai dalam merancang komputer elektronik dengan menerjemahkannya ke dalam

rangkaian saklar (switching circuits) yang pada dasarnya adalah logika, tertutup atau terbuka,

mengalirkan arus listrik atau tidak.

Seperti telah diterangkan di bagian depan, setiap peubah Boole hanya dapat

berkeadaan satu dari dua keadaan, 0 atau 1. Jadi, kalau satu peubah di-OR-kan dengan 0

maka hasilnya akan tidak berubah sedangkan bila satu peubah di-OR-kan dengan 1, maka

apapun keadaan peubah itu sebelumnya akan menjadi 1. Tetapi, bila satu peubah di-AND-

kan dengan 1, maka hasilnya tidak akan berubah sedangkan bila di-AND-kan dengan 0,

apapun keadaan peubah itu sebelumnya akan berubah menjadi 0.

Ini dapat disimpulkan dalam bentuk teorema dasar:

X + 0 = X

X.0 = 0

X + 1 = 1

X.1 = X

Kalau suatu peubah di-OR-kan dengan dirinya sendiri, maka hasilnya akan 0 bila keadaan

variabel itu adalah 0 dan hasilnya akan 1 bila keadaan variabel itu adalah 1.

Jadi, peng-OR-an satu variabel dengan dirinya sendiri menghasilkan keadaan yang sama

dengan keadaan variabel itu. Keadaan serupa berlaku untuk operasi AND. Ini disebut

hukum idempoten:

X + X = X X.X = X

4

Sesuai dengan logika, maka kalau tidak benar disangkal (di-NOT-kan), hasilnya menjadi

benar dan kalau tidak-salah di-NOT-kan, hasilnya menjadi salah.

Dengan kata lain, penidakan/penyangkalan (komplementasi) dua kali akan menghasilkan

keadaan aslinya. Ini dikenal dengan nama hukum involusi yang dituliskan sebagai:

¿X= X

Hasil dari keadaan benar ATAU tidak benar pasti selalu benar dan keadaan salah

ATAU tidak salah juga akan selalu benar (terpenuhi). Tetapi keadaan salah DAN tidak

salah dan benar DAN tidak benar akan selalu salah. Jadi, dalam teorema Boole dapat

dinyatakan dengan hukum komplemen sebagai berikut:

X + X = 1 (selalu benar)

X . X = 0 (selalu salah)

Untuk fungsi-fungsi Boole dengan dua peubah atau lebih, dikenal juga hukum-hukum kumulatif,

assosiatif dan distributif yang berlaku dalam teorema biasa, yaitu:

Hukum Kumutatif : XY = YX

X + Y = Y + X

Hukum Assosiatif: (X Y) Z = X (Y Z) = XYZ

(X+Y) + Z = X + (Y+Z) = X + Y + Z

Hukum Distributif: X (Y + Z) = X Y + X Z

X + Y Z = (X + Y)(X + Z)

5

B.Teorema dasar Boole

Hukum Distributif

1. A (B + C) = A B + A C (BENAR)

Pembuktian:

2. A+(B+C)=(A+B)+C=A+B+C  (BENAR)

3. Pembuktian:

6

Hukum Asosiatif

1.  (A + B) + C = A + (B + C)(BENAR)

Pembuktian:

A B C A+B B+C (A+B)+C A+(B+C)

0 0 0 0 0 0 0

0 0 1 0 1 1 1

0 1 0 1 1 1 1

0 1 1 1 1 1 1

1 0 0 1 0 1 1

1 0 1 1 1 1 1

1 1 0 1 1 1 1

1 1 1 1 1 1 1

   2.  (A B) C = A (B C) (BENAR)

Pembuktian:

A B C AB BC (A B) C A (B C)

0 0 0 0 0 0 0

0 0 1 0 0 0 0

0 0 1 0 0 0 0

0 1 1 0 1 0 0

1 0 0 0 0 0 0

1 0 1 0 0 0 0

1 1 0 1 0 0 0

7

1 1 1 1 1 1 1

Hukum Komutatif 

(a) A + B = B + A(BENAR)

Pembuktian:

A B A+B B+A

0 0 0 0

0 1 1 1

1 0 1 1

1 1 1 1

(b) A B = B A(BENAR)

Pembuktian:

A B AB BA

0 0 0 0

0 1 0 0

1 0 0 0

1 1 1 1

Teorema kompelement 

(a) A + Ā=1) (BENAR)

Pembuktian:

A Ā 1 (A + Ā=1)

0 1 1 1

0 1 1 1

1 0 1 1

8

1 0 1 1

(b) A Ā = 0 (BENAR)

Pembuktian:

A Ā 0 (A Ā= 0)

0 1 0 0

0 1 0 0

1 0 0 0

1 0 0 0

Hukum Operasi 0 dan 1

(a) 1 + A = 1(BENAR) 

Pembuktian:

A 1 1+A

0 1 1

0 1 1

1 1 1

1 1 1

(b) 1 A = A (BENAR) 

Pembuktian:

A 1 1.A=A

0 1 0

9

0 1 0

1 1 1

1 1 1

(a) 0 + A = A (BENAR)

Pembuktian:

A 0 0+A=A

0 0 0

0 0 0

1 0 1

1 0 1

(b) 0 A = 0 (BENAR)

Pembuktian:

A 0 0 A = 0

0 0 0

0 0 0

1 0 0

1 0 0

Hukum Idempoten

(a) A + A = A (BENAR)

Pembuktian:

A A A + A = A 

0 0 0

0 0 0

1 1 1

1 1 1

10

(b) A A = A (BENAR)

Pembuktian:

A A A . A = A 

0 0 0

0 0 0

1 1 1

1 1 1

Hukum Involusi

¿A= A

Ā.Ā= A (BENAR)

Pembuktian:

Ā Ā Ā.Ā= A

0 0 0

0 0 0

1 1 1

1 1 1

C.Penyajian Fungsi Boole

A.bentuk kanomik

• Ada dua macam bentuk kanonik:

11

1) Penjumlahan dari hasil kali (sum-of-product atau SOP)

2) Perkalian dari hasil jumlah (product-of-sum atau POS)

Contoh:

1. f(x, y, z) = x’y’z + xy’z’ + xyz à SOP

Setiap suku (term) disebut minterm 

2. g(x, y, z) = (x + y + z)(x + y’ + z)(x + y’ + z’)

(x’ + y + z’)(x’ + y’ + z) à POS

Setiap suku (term) disebut maxterm

•  Setiap minterm/maxterm mengandung literal lengkap

• Suatu fungsi Booelan dapat dibentuk secara teorema dari tabel kebenaran yang

diketahui dengan membentuk minterm/maxterm dari setiap kombinasinya.

Untuk membentuk SOP, tinjau kombinasi peubah-peubah yang menghasilkan nilai 1.

Untuk membentuk POS, tinjau kombinasi peubah-peubah yang menghasilkan nilai 0.

• Contoh:

Nyatakan fungsi Boole f(x, y, z) = x + y’z dalam

bentuk kanonik SOP dan POS!

• Cara 1

12

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

(a) SOP

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

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

atau

f(x, y, z) = m1 + m4 + m5 +

m6 + m7

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

(b) POS

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

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

(Hk Distributif)

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)

13

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

(x + y’ + z’)

atau

f(x, y, z) = M0M2M3

= Õ(0, 2, 3)

D. Penyederhanaan fungsi Boole

dapat dilakukan dengan 2 cara:

Secara teorema

Menggunakan Peta Karnaugh

a. Penyederhanaan Secara Teorema

Contoh:

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

= (x + x’)(x + y) hukum distributif

= 1 . (x + y ) hukum komplemen

= x + y

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

= x’z(y’ + y) + xy’ hukum distributif

= x’z + xz’

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

= xy + x’z + xyz + x’yz hukum asosiatif

= xy(1 + z) + x’z(1 + y) = xy + x’z hukum distributif

14

b.Penyederhanaan dengan Peta Karnaugh

Peta Karnaugh adalah sebuah diagram / peta yang terbentuk dari kotak - kotak yang bersisian. Tiap kotakmerepresentasikan sebuah minterm. Peta Karnaugh dengan jumlah kotak lebih dari 4 buah akan memiliki sisi yang berseberangan. Sisi yang berseberangan tersebut sebenarnya merupakan sisi yang bersisian juga. Artinya sebuah peta karnaugh dapat dibayangkan sebagai sebuah kotak kubus atau balok atau silinder yang tersusun atas kotak – kotak itu.

a. Peta Karnaugh dengan dua peubah

Fungsi Boole yang merepresentasikannya adalah f (x, y) = x y

15

Fungsi Boole yang merepresentasikannya adalah f (x, y) = x y‘ + x y

b. Peta Karnaugh dengan tiga peubah

16

Fungsi Boole yang merepresentasikannya adalah f (x, y,z) = x’ y z‘ + x y z’ + x y z

c. Peta Karnaugh dengan empat peubah

Teknik Minimasi Fungsi Boole dengan Peta Karnaugh

1. Pasangan : dua buah 1 yang bertetangga

Fungsi Boole sebelum disederhanakan : f (w, x, y, z) = w x y z + w x y z’Setelah disederhanakan : f (w, x, y, z) = w x yBandingkan dengan cara teoremaf (w, x, y, z) = w x y z + w x y z’= w x y (z + z’ )= w x y (1)= w x y

2. Kuad : empat buah 1 yang bertetangga

Fungsi Boole sebelum disederhanakan : f (w, x, y, z) = w x y’ z’ + w x y’ z + w x y z + w x y z’Setelah disederhanakan : f (w, x, y, z) = w x

3. Oktet : delapan buah 1 yang bertetangga

17

Fungsi Boole sebelum disederhanakan : f (w, x, y, z) = w x y’ z’ + w x y’ z + w x y z + w x y z’ + w x’ y’ z’ + w x’ y’ z + w x’ y z + w x’ y z’Setelah disederhanakan : f (w, x, y, z) = w

E. Teorema Dasar De Morgan

Dua persamaan berikut dikenal dengan nama Hukum De Morgan:

Untuk membuktikan Persamaan (1-1) perlu di perhatikan, bahwa jikalau semua masukan 1,

masing-masing ruas persamaan akan memberikan suatu hasil yang sama dengan 0. Di pihak

lain, kalau satu (atau lebih dari satu) masukan sama dengan 0, maka masing-masing ruas

persamaan akan memberikan suatu hasil yang sama dengan 1. Sehingga, untuk semua

kemungkinan masukan dari ruas sebelah kanan persamaan sama dengan ruas sebelah kiri.

Persamaan (1-2) dibuktikan dengan cara yang sama. Hukum De Morgan memperlengkap

daftar identitas Boole dasar. Untuk masing-masing acuan selanjutnya, semua hubungan-

hubungan tersebut di ringkas dalam tabel 1a.

18

Contoh penggunaan teorema boole hukum-hukum De Morgan pada ekuivalensi rangkaian

EXCLUSIVE OR adalah sebagai berikut:

Diketahui suatu fungsi logika boole EXCLUSIVE OR dan ekuivalen dengan

fungsi logika boole , buktikan bahwa memang kedua persamaan tersebut

ekuivalen. Maka dua persamaan tersebut dapat dibuktikan dengan penjabaran dengan

pertolongan teorema boole sebagai berikut:

19

Dari hukum De Morgan dapat disimpulkan, bahwa untuk mendapatkan komplemen

(pelengkap) dari suatu fungsi boole adalah dengan mengubah semua operasi OR menjadi

operasi AND, ataupun sebaliknya mengubah semua operasi AND menjadi operasi OR, dan

melakukan penolakan masing-masing simbol binernya. Dan dengan pertolongan hukum De

Morgan dapat kita tunjukkan bahwa suatu rangkaian AND untuk logika positif juga bekerja

seperti halnya suatu gerbang OR untuk logika negatif. Misalkan Y adalah keluaran dan A, B, ...

, N adalah masukan-masukan ke AND positif, sehingga

Kalau keluaran dan semua masukan dari rangkaian dikomplemenkan sedemikian hingga 1

menjadi 0 dan sebaliknya, maka logika positif berubah menjadi logika negatif. Karena Y dan

menggambarkan terminal keluaran yang sama, A dan menggambarkan terminal masukan

yang sama, dan lain sebagainya. Rangkaian yang melaksanakan logika AND positif dalam

persamaan (1-3) juga bekerja sebagai gerbang logika OR negatif pada persamaan (1-4).

Alasan yang sama digunakan untuk membuktikan, bahwa rangkaian yang sama mungkin

berlaku sebagai AND negatif atau OR positif, tergantung kepada bagaimana tingkat biner

didefinisikan. Hal ini telah dibuktikan untuk logika dioda. Untuk lebih jelasnya berikut

ditampilkan aplikasi teorema De Morgan dalam diagram blok fungsi logika boole pada gambar

1-1c. Suatu OR yang diubah ke AND dengan membalikkan semua masukan dan keluarannya,

gambar 1-1d. Suatu AND menjadi OR, kalau semua masukan dan keluaran komplemen.

20

21

BAB III

PENUTUP

A.KESIMPULAN

Teorema boole digunakan untuk menyatakan pengaruh berbagai rangkaian digital pada

masukan-masukan logika, dan untuk memanipulasi variabel logika dalam menentukan cara terbaik

pada pelaksaan fungsi rangkaian tertentu. Oleh karena hanya ada dua niai yang mungkin,

teorema boole lebih cocok digunakan untuk rangkaian digital dibandingkan dengan teorema yang

lain. Kenyataanya alajabar boole hanya mengenal tiga operasi dasar, yaitu: Aturan operasi OR,

AND dan NOT

Teorema De Morgan sebenarnya juga tidak perlu menggunakan semua gerbang logika,

yakni cukup adanya OR dan NOT atau AND dan NOT saja, karena dari hukum De Morgan

persamaan (1-1) AND dapat diperoleh dari OR dan NOT, seperti ditunjukkan dalam gambar 1-1c.

Dan dengan cara yang sama, AND dan NOT dapat dipilih sebagai rangkaian gerbang logika dasar,

dan dari hukum De Morgan persamaan (1-2), OR mungkin dapat dibangun seperti ditunjukkan

dalam gambar 1-1d. Gambar ini akan menjelaskan lagi, bahwa OR (AND) dibalikkan pada

masukan dan keluaran membentuk logika AND (OR)

B.SARAN

Untuk memahami lebih lanjut tentang Teorema Boole saya harap si pembaca dapat mencari

sumber-sumber yang lain di internet dan buku-buku yang terkait dengan Teorema Boole

22

DAFTAR PUSTAKA

http://pandukristiyanto89.wordpress.com/2010/10/19/teorema-boole/

kur2003.if.itb.ac.id/file/Teorema%20Boole.doc

http://rizqiprastowo.blogspot.com/2011/07/teorema-boleab.html

http://habibfreak.blogspot.com/2012/10/bentuk-kanonik-matematika-

diskrit.html

http://www.linksukses.com/2012/11/logika-boolean-karnaugh-map.html

http://eviandrianimosy.blogspot.com/2010/06/hukum-de-morgan.html

23