Makalah Aljabar Boleean [PDF]

Citation preview

“Aljabar Boolean” Disusun Oleh : -Alya Fahira Berutu (201114014) - Sarah Nabillah (201114015) - Siti Khadijah (201114005) - Biaz Tiwi Harahap (201114009) Untuk Memenuhi Tugas Mata Kuliah : Himpunan dan Logika Dosen Pengampu: Amanda Syahri Nasution, S.Pd., M.Pd.



SEMESTER 3A FAKULTAS KEGURUAN ILMU PENDIDIKAN PROGRAM STUDI PENDIDIKAN MATEMATIKA



KATA PENGANTAR



Puji syukur kehadirat Allah SWT karena telah memberikan kesempatan pada penulis untuk menyelesaikan makalah ini. Atas rahmat dan hidayah-Nya lah penulis dapat menyelesaikan makalah yang berjudul “Aljabar Boolean” tepat waktu. Makalah ini disusun guna memenuhi tugas Dosen Amanda Syahri Nasution, S.Pd.,M.Pd. pada mata kuliah Himpunan dan Logika di Universitas Muslim Nusantara (UMN). Selain itu, penulis juga berharap agar makalah ini dapat menambah wawasan bagi pembaca. Penulis mengucapkan terima kasih sebesar-besarnya kepada Ibu selaku Dosen mata kuliah Himpunan dan Logika. Tugas yang telah diberikan ini dapat menambah pengetahuan dan wawasan terkait bidang yang ditekuni penulis. Penulis menyadari makalah ini masih jauh dari kata sempurna. Oleh karena itu, kritik dan saran yang membangun akan penulis terima demi kesempurnaan makalah ini.



Medan, 05 November 2021



Penulis



DAFTAR ISI



Kata Pengantar…..…………………………………......………………….….   Daftar isi………...…………………………………………..…………………     BAB I PENDAHULUAN 1.1   Latar Belakang.................................................…………………………...   1.2   Rumusan Masalah........…….....……………...........................…………...   1.3   Tujuan ..………………………………………...........................................   BAB II PEMBAHASAN 2.1  Definisi Aljabar Boolean............................................................................. 2.2 Hukum-hukum aljabar boleean..................................................................... 2.3 Fungsi Boolean dan Ekspresi Boolean.......................................................... 2.4 Bentuk Kanonik............................................................................................. BAB II PENUTUP Kesimpulan….....…………………………......................................................... Saran………………………..................………………....................................... Daftar Pustaka .……………………..........……………...................................... 



3



BAB I PENDAHULUAN



1.1.



Latar Belakang Masalah Perkembangan informasi khususnya ilmu komputer sangat cepat dewasa



ini perlu diimbangi dengan pengetahuan tentang teorinya. Salah satu teori yang mendukung ilmu komputer adalah Matematika diskrit. Selain itu matematika diskrit banyak diaplikasikan dalam berbagai bidang, antara lain: bisnis, kimia, geografi, dan botani. Matematika diskrit merupakan ilmu dasar dalam pendidikan informatika atau ilmu komputer. Dalam kenyataannya komputer digital bekerja secara diskrit. Informasi yang disimpan dan dimanipulasi oleh komputer adalah dalam bentuk diskrit. Selain itu mata kuliah matematika diskrit ini juga sebagai dasar/penunjang bagi mata kuliah Basis data, struktur data, algoritma dan pemrograman, jaringan komputer, sistem operasi, dan lainnya. Sebagian besar mata kuliah dibidang informatika dilandasi secara matematis oleh matematika diskrit, sehingga matematika diskrit dianggap sebagai matematika-nya orang informatika. Untuk kemajuan teknologi dan ilmu komputer peranan Aljabar Boolean sebagai salah satu subbab dalam Matematika diskrit sangat penting untuk diterapkan. Terutama dalam teknologi digital. Dengan demikian penulis akan memaparkan materi terkait Aljabar dan Fungsi Boolean.



1.2.



Rumusan Masalah



1.



Bagaimanakah definisi Aljabar Boolean?



2.



Bagaimana bentuk dan pengertian fungsi Boolean?



3.



Apa saja aplikasi dalam aljabar Boolean?



4



1.3.



Tujuan Penulisan



Tujuan penulisan makalah ini adalah sebagai berikut: 1.



Untuk mengetahui definisi Aljabar Boolean



2.



Untuk mendeskripsikan tentang bentuk dan pengertian fungsi Boolean.



3.



Untuk mengetahui aplikasi dari Aljabar Boolean dalam cabang ilmu lain, seperti dalam ilmu Fisika dan Teknologi Komputer.



BAB II



5



PEMBAHASAN



2.1.



Definisi Aljabar Boolean Aljabar Boolean merupakan dasar teknologi digital seperti pada rangkaian



pensaklaran, rangkaian digital, dan integrated circuit computer, karena rangkaian elektronik di dalam komputer bekerja dengan mode bit. Definisi dasar Baik himpunan-himpunan maupun pernyataan-pernyataan, keduanya mempunyai sifatsifat yang mirip, yang disebut hukum-hukum identikal. Hukum-hukum ini digunakan untuk mendefinisikan struktur matematika yang abstrak yang disebut aljabar Boolean.Nama tersebut diambil dari matematikawan Inggris Geoge Boole (1815-1864). Definisi 2.1. Aljabar Boolean Misalkan B himpunan yang didefinisikan pada operasi “∨”, “∧”, dan “~” . Misalkan 0 dan 1 adalah dua elemen yang berbeda dari B maka 𝐵,∨,∧,~,0,1 disebut aljabar boolean jika memenuhi aksioma (Postulat Huntington) berikut: dengan 𝑥,𝑦,𝑧 ∈ 𝐵 1. Hukum komutatif



4. Hukum identitas



a. 𝑥 ∨ 𝑦 = 𝑦 ∨ 𝑥



a. 𝑥 ∨ 0 = 𝑥



b. 𝑥 ∧ 𝑦 = 𝑦 ∧ 𝑥



b. 𝑥 ∧ 1 = 𝑥



2. Hukum asosiatif



5. Hukum negasi (komplemen)



a. 𝑥 ∨ 𝑦 ∨ 𝑧 = 𝑥 ∨ 𝑦 ∨ 𝑧



a. 𝑥 ∨ ~𝑥 = 1



b. 𝑥 ∧ 𝑦 ∧ 𝑧 = 𝑥 ∧ (𝑦 ∧ 𝑧)



b. 𝑥 ∧ ~𝑥 = 0



3. Hukum distributif a. 𝑥 ∨ 𝑦 ∧ 𝑧 = 𝑥 ∨ 𝑦 ∧ (𝑥 ∨ 𝑧) b. 𝑥 ∧ 𝑦 ∨ 𝑧 = 𝑥 ∧ 𝑦 ∨ (𝑥 ∧ 𝑧)



6



Dalam buku tertentu agar menyerupai dengan aritmatika, operasi ∨ diganti +, operasi ∧ diganti * atau . , dan operasi ~ diganti (’). Aljabar proposisi dan aljabar himpunan merupakan aljabar boole, sehingga sifat-sifatnya mirip.



Menurut (Rinaldi Munir, 2010:282) elemen 0 dan 1 adalah elemen unik yang di dalam B. 0 disebut elemen terkecil dan 1 disebut elemen terbesar. Kedua elemen unik dalam aljabar Boolean (misalnya ∅ dan U pada himpunan, nilai kebenaran B dan S pada proposisi), namun secara umum kita menggunakan ) 0 dan 1 dalam aljabar Boolean.



2.2.



Hukum-Hukum Aljabar Boolean



Dalam subbab 7.1 sudah disampaikan bahwa hukum-hukum pada aljabar boole mirip dengan hukum pada himpunan atau proposisi. Hukum pada aljabar boole dapat dilihat pada tabel 2.1. 1. Hukum identitas:



5. Hukum komutatif:



a. 𝑥 ∨ 0 = 𝑥



a. 𝑥 ∨ 𝑦 = 𝑦 ∨ 𝑥



b. 𝑥 ∧ 1 = 𝑥



b. 𝑥 ∧ 𝑦 = 𝑦 ∧ 𝑥



2. Hukum negasi (komplemen)



6. Hukum involusi:



a. 𝑥 ∨ ~𝑥 = 1 b. 𝑥 ∧ ~𝑥 = 0



~ ~𝑥 = 𝑥 7. Hukum dominansi/ikatan: a. 𝑥 ∧ 0 = 0 b. 𝑥 ∨ 1 = 1



7



3. Hukum distributif:



8. Hukum absorbsi (penyerapan):



a. 𝑥 ∨ 𝑦 ∧ 𝑧 = 𝑥 ∨ 𝑦 ∧ (𝑥 ∨ 𝑧)



a. 𝑥 ∧ 𝑦 ∨ 𝑥 = 𝑥



b. 𝑥 ∧ 𝑦 ∨ 𝑧 = 𝑥 ∧ 𝑦 ∨ (𝑥 ∧ 𝑧)



b. 𝑥 ∨ 𝑦 ∧ 𝑥 = 𝑥



4. Hukum asosiatif: a. 𝑥 ∨ 𝑦 ∨ 𝑧 = 𝑥 ∨ 𝑦 ∨ 𝑧 b. 𝑥 ∧ 𝑦 ∧ 𝑧 = 𝑥 ∧ (𝑦 ∧ 𝑧) 9. Hukum idempotent: a. 𝑥 ∧ 𝑥 = 𝑥 b. 𝑥 ∨ 𝑥 = 𝑥 10. Hukum De Morgan: a. ~( 𝑥 ∨ 𝑦 )= ~𝑥 ∧ ~𝑦 b. ~ (𝑥 ∧ 𝑦) = ~𝑥 ∨ ~𝑦 11. Hukum 0/1: a. ~0 = 1 b. ~1 = 0



Tabel 2.1. Hukum-hukum pada Aljabar Boolean



2.3.



Fungsi Boolean dan Ekspresi Boolean



Definisi 2.2 Fungsi Boolean Misalnya 𝐵 = ⟨ B , ∨, ∧, , 0,1 ⟩ adalah aljabar boolean. Fungsi boolean adalah pemetaan dari Bn ke B melalui ekspresi boole, yang ditulis n



f : B →B



yang dalam hal ini Bn adalah himpunan yang beranggotakan pasangan terurut ganda-n di dalam daerah asal B.



8



Definisi 2.2 Ekspresi Boolean Ekspresi boole dalam n buah peubah 𝑥1,𝑥2,…,𝑥𝑛 adalah 1. 0 dan 1 adalah ekspresi Boolean. 2. x 1 , x 2 , x 3 ,… x n masing-masing adalah ekspresi Boolean. 3. Jika E1 dan E2 adalah ekspresi Boolean, maka E1 ∧ E2, E1∨ E2 ,~ E1 adalah ekspresi boole. Secara aljabar, fungsi boole dapat dinyatakan dalam tabel kebenaran dan rangkaian logika. Jika fungsi boole dinyatakan dalam tabel kebenaran, maka untuk fungsi boolean dengan n peubah, kombinasi dari nilai peubahnya sebanyak n 2 . Kedua fungsi boole dikatakan sama jika kedua ekspresi boole-nya ekivalen.



Maksudnya ekivalen adalah kedua ekspresi boole tersebut tidak sama tetapi mempunyai nilai yang sama (menyatakan fungsi yang sama). Hal ini bisa dibuktikan dengan menggunakan tabel kebenaran atau dengan menurunkan ekspresi boole sampai mendapatkan ekspresi yang lain dengan menggunakan hukum-hukum yang terdapat pada aljabar boole. Contoh 2.1: Nyatakan fungsi boole 𝑓 𝑥,𝑦,𝑧 = 𝑥 ∧ 𝑦 ∨ ~𝑧 dalam tabel kebenaran. Penyelesaian: Nilai-nilai dari fungsi boole dapat dilihat pada tabel 2.2. x Y z 𝒙∧𝒚 𝒙 ∧ 𝒚 ∨ ~𝒛 1 1 1 1 1 1 1 0 1 1 1 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1 Tabel 2.2: Tabel kebenaran 𝑓 𝑥,𝑦,𝑧 = 𝑥 ∧ 𝑦 ∨ ~𝑧



9



Contoh 2.2: Jelaskan apakah kedua ekspresi boole ini ekivalen. E1 : (𝑥 ∧ 𝑦 )∨ (𝑥 ∧ 𝑦 ∧ 𝑧 )∨ 𝑧 ; E2: (𝑥 ∧ 𝑦) ∨ 𝑧



Penyelesaian: Untuk menunjukka ekivalen atau tidak ada dua cara, yaitu: a.



Merurunkan salah satu ekspresi boole sampai memndapatkan ekspresi boole lainnya dengan menggunakan hukum aljabar. (𝑥 ∧ 𝑦 )∨ (𝑥 ∧ 𝑦 ∧ 𝑧 )



= (𝑥 ∧ 𝑦) ∧ (1 ∨ 𝑧 )∨ 𝑧



Hukum distributif



= (𝑥 ∧ 𝑦 )∧ (1 ∨ 𝑧)



Hukum ikatan



= (𝑥 ∧ 𝑦) ∨ 𝑧



Hukum identitas



Karena E1 = E2 maka kedua ekspresi boole ini ekivalen. b. Tabel kebenaran x y z 𝑥 ∧ 𝑦 𝑥 ∧ 𝑦 ∧ 𝑧 𝐸1 𝐸2 x



y



z



𝒙∧𝒚



𝒙∧𝒚∧z



E1



E2



1



1



1



1



1



1



1



1



1



0



1



0



1



1



1



0



1



0



0



1



1



1



0



0



0



0



0



0



0



1



1



0



0



1



1



0



1



0



0



0



0



0



0



0



1



0



0



1



1



0



0



0



0



0



0



0



Tabel 2.3: Tabel kebenaran E1 : (𝑥 ∧ 𝑦 )∨ (𝑥 ∧ 𝑦 ∧ 𝑧 )∨ 𝑧 dan E2: (𝑥 ∧ 𝑦) ∨ 𝑧 Dari Tabel 2.3 juga menunjukkan bahwa nilai E1 ≡ E2. Jadi E1ekivalen dengan E2.



2.4.



Bentuk Kanonik



10



MenurutRinaldi



Munir



(2010:298),



Ekspresi



Boolean



yang



menspesifikasikan suatu fungsi dapat disajikan dalam dua bentuk berbeda. Pertama, sebagai penjumlahan dari hasil kali dan kedua sebagai perkalian dari hasil jumlah. Misalnya, f ( x , y , z )=¿ ∧ y ) ∧ z ∨ (x∧ y ) z + (𝒙 ∧ 𝒚 ∧ z)



Dan g ( x , y , z ) =¿ ∨ y ∨ z) ∧ ( x ∨ ~y ∨ z) ∧ ( x ∨ y ∨ ~z) ∧ (~ x ∨ ~y ∨ z)



adalah dua buah fungsi yang sama (dapat ditunjukkan dari tabel kebenarannya). Fungsi yang pertama, f



muncul dalam bentuk penjumlahan dari hasil



kali,sedangkan fungsi yang kedua, g, muncul dalam bentuk penjumlahan dari hasil kali. Perhatikan juga bahwa setiap suku (term) di dalam ekspresi mengandung literal yang lengkap dalam peubah x, y , dan z, baik peubahnya tanpa komplemen maupun dengan komplemen. Ada dua macam bentuk term, yaitu minterm (hasil kali) dan maxterm (hasil jumlah). Suku-suku di dalam ekspresi Boolean dengan n peubah x 1 , x 2 , x 3 ,… x n x ∧~ x ∧~ x ∧ …~ x . Dan dikatakan dikatakan mintern jika ia muncul dalam bentuk ~ 1



2



3



n



x 1 ∨~ x 2 ∨~ x 3 ∨ …~ x n . Literal adalah ekspresi Boolean yang maxterm jika berbentuk ~



mengandung satu peubah atau komplemennya. Jadi bentuk kanonik ada 2, yaitu: 1. Bentuk normal disjungtif (Penjumlahan dari hasil kali/Disjunctive Normal Form=DNF) Suatu ekspresi boole di dalam



⟨ 0,1, ∨ ,∧ , ⟩ disebut DNF



jika merupakan suatu join beberapa minterm. Misalnya: x 1 ∧ x 2 ∧ x 3 ∧ … x n , dan x 1 ∧ x 2 ∧ x 3. 2. Bentuk normal konjungtif (Perkalian dari hasil jumlah / Conjunctive Normal Form=CNF) Suatu ekspresi boole di dalam ⟨ 0,1, ∨ ,∧ , ⟩ disebut CNF jika merupakan suatu meet beberapa maxterm. Misalnya 𝑥1 ∨ 𝑥2 ∨ 𝑥 3 ∧ 𝑥1 ∨ 𝑥 2 ∨ 𝑥 3 adalah suatu ekspresi boole dalam bentuk CNF dengan 2 maxterm.



11



2.4.



12



13



BAB III PENUTUP



KESIMPULAN Definisi 2.1. Aljabar Boolean Misalkan B himpunan yang didefinisikan pada operasi “∨”, “∧”, dan “~” . Misalkan 0 dan 1 adalah dua elemen yang berbeda dari B maka 𝐵,∨,∧,~,0,1 disebut aljabar boolean jika memenuhi aksioma (Postulat Huntington) berikut: dengan 𝑥,𝑦,𝑧 ∈ 𝐵 1. Hukum komutatif



3. Hukum distributif



a. 𝑥 ∨ 𝑦 = 𝑦 ∨ 𝑥



a. 𝑥 ∨ 𝑦 ∧ 𝑧 = 𝑥 ∨ 𝑦 ∧ (𝑥 ∨ 𝑧)



b. 𝑥 ∧ 𝑦 = 𝑦 ∧ 𝑥



b. 𝑥 ∧ 𝑦 ∨ 𝑧 = 𝑥 ∧ 𝑦 ∨ (𝑥 ∧ 𝑧)



2. Hukum asosiatif



4. Hukum identitas



a. 𝑥 ∨ 𝑦 ∨ 𝑧 = 𝑥 ∨ 𝑦 ∨ 𝑧



a. 𝑥 ∨ 0 = 𝑥



b. 𝑥 ∧ 𝑦 ∧ 𝑧 = 𝑥 ∧ (𝑦 ∧ 𝑧)



b. 𝑥 ∧ 1 = 𝑥 5. Hukum negasi (komplemen) a. 𝑥 ∨ ~𝑥 = 1 b. 𝑥 ∧ ~𝑥 = 0



Definisi 2.2 Fungsi Boolean Misalnya 𝐵 = ⟨ B , ∨, ∧, , 0,1 ⟩ adalah aljabar boolean. Fungsi boolean adalah pemetaan dari Bn ke B melalui ekspresi boole, yang ditulis n



f : B →B



yang dalam hal ini Bn adalah himpunan yang beranggotakan pasangan terurut ganda-n di dalam daerah asal B.



14



SARAN Demikian makalah yang saya buat, semoga dapat bermanfaat bagi pembaca. Apabila ada saran dan kitik yang ingin disampaikan, silahkan sampaikan kepada kami. Apabila ada terdapat kesalahan mohon dapat mema’afkan dan memakluminya, karena kami adalah hamba Allah yang tak luput dari salah khilaf, Alfa dan lupa.



15



DAFTAR PUSTAKA



Kurniawati, T Anita. 2010. Diktat Matematika Diskrit. Surabaya: Fakultas Teknik Informasi INSTITUT TEKNOLOGI ADHI TAMA SURABAYA. Munir, Rinaldi.2010. Matematika Diskrit. Bandung : Informatika Bandung. Sirait, Hasanuddin Ir. 2010. Diktat Pendukung Matematika Diskrit. Manado :Displin Ilmu Teknik STMIK PARNA RAYA MANADO MANADO



16