Aljabar Boolean: sejarah, teorema dan dalil, contoh
Aljabar Boolean atau aljabar Boolean adalah notasi aljabar yang digunakan untuk pengobatan variabel biner. Ini mencakup studi tentang setiap variabel yang hanya memiliki 2 hasil yang mungkin, saling melengkapi dan saling eksklusif. Misalnya, variabel yang hanya kemungkinan benar atau salah, benar atau salah, hidup atau mati adalah dasar studi aljabar Boolean.
Aljabar Boolean membentuk dasar elektronik digital, yang membuatnya cukup hadir di zaman kontemporer. Hal ini diatur oleh konsep gerbang logika, di mana operasi yang dikenal dalam aljabar tradisional sangat terpengaruh.
Sejarah
Aljabar Boolean diperkenalkan pada tahun 1854 oleh ahli matematika Inggris George Boole (1815 - 1864), yang merupakan sarjana otodidak saat itu. Kekhawatirannya muncul dari perselisihan antara Augustus De Morgan dan William Hamilton, tentang parameter yang mendefinisikan sistem logis ini.
George Boole berpendapat bahwa definisi nilai numerik 0 dan 1 sesuai, dalam bidang logika, dengan interpretasi dari Nothing dan Universe masing-masing.
Niat George Boole adalah untuk mendefinisikan, melalui sifat-sifat aljabar, ekspresi dari logika proposisional yang diperlukan untuk menangani variabel-variabel tipe biner.
Pada 1854 bagian paling signifikan dari aljabar Boolean diterbitkan dalam buku " Sebuah penyelidikan hukum pemikiran yang menjadi dasar teori matematika dan probabilitas".
Judul yang aneh ini akan dirangkum di bawah ini sebagai " Hukum-hukum pemikiran" ("Hukum-hukum pemikiran"). Judul melompat ke ketenaran karena perhatian langsung yang dimilikinya pada bagian dari komunitas matematika saat itu.
Pada tahun 1948 Claude Shannon menerapkannya dalam desain sirkuit switching listrik yang tahan lama. Ini berfungsi sebagai pengantar penerapan aljabar Boolean dalam seluruh skema elektronik-digital.
Struktur
Nilai-nilai dasar dalam jenis aljabar ini adalah 0 dan 1, yang masing-masing sesuai dengan FALSE dan TRUE. Operasi mendasar dalam aljabar Boolean adalah 3:
- Operasi DAN atau hubungannya. Diwakili oleh titik (.). Sinonim untuk produk
- ATAU operasi atau disjungsi. Diwakili oleh tanda silang (+). Sinonim dari jumlah.
- Operasi BUKAN atau negasi. Diwakili oleh awalan BUKAN (BUKAN A). Itu juga dikenal sebagai suplemen.
Jika himpunan A mendefinisikan 2 hukum komposisi internal yang dinyatakan sebagai produk dan jumlah (. +), Dikatakan bahwa triple (A. +) adalah aljabar Boolean jika dan hanya jika kata tripel memenuhi kondisi menjadi reticle distributif
Untuk mendefinisikan jaringan distribusi, kondisi distribusi antara operasi yang diberikan harus dipenuhi:
. bersifat distributif sehubungan dengan jumlah + a. (b + c) = (a. b) + (a. c)
+ bersifat distributif sehubungan dengan produk. a + (b. c) = (a + b). (a + c)
Elemen-elemen yang membentuk himpunan A harus biner, sehingga memiliki nilai semesta atau kosong.
Aplikasi
Skenario aplikasi utamanya adalah cabang digital, di mana ia berfungsi untuk menyusun sirkuit yang membentuk operasi logis yang terlibat. Seni kesederhanaan sirkuit yang mendukung proses optimalisasi adalah hasil dari penerapan dan praktik aljabar Boolean yang benar.
Dari pengembangan panel listrik, melalui transmisi data, hingga pemrograman dalam berbagai bahasa, kita sering dapat menemukan aljabar Boolean di semua jenis aplikasi digital.
Variabel Boolean sangat umum dalam struktur pemrograman. Bergantung pada bahasa pemrograman yang digunakan, akan ada operasi kode struktural yang menggunakan variabel-variabel ini. Persyaratan dan argumen masing-masing bahasa mendukung variabel Boolean untuk mendefinisikan proses.
Postulat
Ada teorema yang mengatur hukum logis struktural aljabar Boolean. Demikian pula, ada postulat untuk mengetahui kemungkinan hasil dalam kombinasi variabel biner yang berbeda, tergantung pada operasi yang dilakukan.
Jumlah (+)
Operator OR yang elemen logiknya adalah gabungan (U) didefinisikan untuk variabel biner sebagai berikut:
0 + 0 = 0
0 +1 = 1
1 + 0 = 1
1 + 1 = 1
Produk (.)
Operator AND yang elemen logiknya adalah persimpangan (∩) didefinisikan untuk variabel biner sebagai berikut:
0 0 = 0
0 1 = 0
1 0 = 0
1 1 = 1
Ditentang (TIDAK)
Operator TIDAK yang elemen logisnya adalah pelengkap (X) 'didefinisikan untuk variabel biner sebagai berikut:
TIDAK 0 = 1
BUKAN 1 = 0
Banyak postulat berbeda dari padanannya dalam aljabar konvensional. Ini karena domain dari variabel. Sebagai contoh, penambahan elemen alam semesta dalam aljabar Boolean (1 +1) tidak dapat menghasilkan hasil konvensional 2, karena itu bukan milik elemen himpunan biner.
Teorema
Aturan nol dan persatuan
Setiap operasi sederhana yang melibatkan elemen dengan variabel biner didefinisikan:
0 + A = A
1 + A = 1
0 A = 0
1 A = A
Kekuatan yang sama atau idempotencia
Operasi antara variabel yang sama didefinisikan sebagai:
A + A = A
A. A = A
Komplementasi
Setiap operasi antara variabel dan komplemennya didefinisikan sebagai:
A + BUKAN A = 1
A. BUKAN A = 0
Keterlibatan atau penolakan ganda
Setiap negasi ganda akan dianggap sebagai variabel alami.
BUKAN (BUKAN A) = A
Komutatif
A + B = B + A; Commutativity of the sum.
A. B = B A; Komutatifitas produk.
Asosiatif
A + (B + C) = (A + B) + C = A + B + C; Asosiasi dari penjumlahan.
A. (B. C) = (A. B). C = A B. C; Asosiasi produk.
Distributif
A + (B. C) = (A + B). (A + C); Distribusi dari jumlah sehubungan dengan produk.
A. (B + C) = (A. B) + (A + C); Distributivitas produk sehubungan dengan jumlah.
Hukum penyerapan
Ada banyak hukum penyerapan di antara banyak
A. (A + B) = A
A. (BUKAN A + B) = A. B
BUKAN A (A + B) = BUKAN A. B
(A + B). (A + NOT B) = A
A + A. B = A
A + TIDAK A. B = A + B
BUKAN A + A. B = BUKAN A + B
A. B + A. BUKAN B = A
Teorema Morgan
Mereka adalah hukum transformasi, yang menangani pasangan variabel yang berinteraksi antara operasi yang didefinisikan dari aljabar Boolean (+.).
TIDAK (A. B) = TIDAK A + TIDAK B
TIDAK (A + B) = TIDAK A. TIDAK B
A + B = TIDAK (TIDAK A + TIDAK B)
A. B = TIDAK (TIDAK A. TIDAK B)
Dualitas
Semua dalil dan teorema memiliki kemampuan dualitas. Ini menyiratkan bahwa ketika bertukar variabel dan operasi, proposisi yang dihasilkan diverifikasi. Artinya, bahwa ketika menukar 0 untuk 1 dan AND untuk OR atau sebaliknya; ekspresi dibuat yang juga akan sepenuhnya valid.
Misalnya, jika Anda mengambil postulat
1 0 = 0
Dan dualitas diterapkan
0 +1 = 1
Postulat lain yang benar-benar valid diperoleh.
Peta Karnaugh
Peta Karnaugh adalah diagram yang digunakan dalam aljabar Boolean untuk menyederhanakan fungsi logis. Ini terdiri dari pengaturan dua dimensi yang mirip dengan tabel kebenaran dari logika proposisional. Data dari tabel kebenaran dapat langsung ditangkap di peta Karnaugh.
Peta Karnaugh dapat mengakomodasi proses hingga 6 variabel. Untuk fungsi dengan jumlah variabel yang lebih banyak, penggunaan perangkat lunak disarankan untuk menyederhanakan proses.
Diusulkan pada tahun 1953 oleh Maurice Karnaugh, itu didirikan sebagai alat tetap di bidang aljabar Boolean, karena implementasinya menyinkronkan potensi manusia dengan kebutuhan untuk menyederhanakan ekspresi Boolean, aspek kunci dalam kelancaran proses digital.
Contohnya
Aljabar Boolean digunakan untuk mengurangi gerbang logika dalam suatu sirkuit, di mana prioritasnya adalah untuk membawa kompleksitas atau tingkat rangkaian ke ekspresi minimum yang mungkin. Hal ini disebabkan oleh penundaan komputasi yang diasumsikan oleh setiap pintu.
Dalam contoh berikut kita akan mengamati penyederhanaan dari ekspresi logis ke ekspresi minimumnya, menggunakan teorema dan postulat aljabar Boolean.
BUKAN (AB + A + B). TIDAK (A + TIDAK B)
BUKAN [A (B + 1) + B]. TIDAK (A + TIDAK B); Anjak faktor A dengan faktor umum.
BUKAN [A (1) + B]. TIDAK (A + TIDAK B); Dengan teorema A +1 = 1.
BUKAN (A + B). TIDAK (A + TIDAK B); oleh Teorema A. 1 = A
(BUKAN A. BUKAN B). [BUKAN A. BUKAN (BUKAN B)];
Dengan teorema Morgan TIDAK (A + B) = TIDAK A. TIDAK B
(BUKAN A. BUKAN B). (BUKAN A. B); Dengan dobel teorema negatif BUKAN (BUKAN A) = A
TIDAK A. TIDAK B. TIDAK A. B; Pengelompokan aljabar
TIDAK A. TIDAK A. TIDAK B. B; Komutatifitas produk A. B = B A
TIDAK A. TIDAK B. B; Dengan teorema A. A = A
TIDAK A. 0; Dengan teorema A. BUKAN A = 0
0; Dengan teorema A. 0 = 0
A. B. C + BUKAN A + A. TIDAK B. C
A. C. (B + TIDAK B) + TIDAK A; Anjak (A. C) dengan faktor umum.
A. C. (1) + BUKAN A; Dengan Teorema A + BUKAN A = 1
A. C + BUKAN A; Secara aturan aturan nol dan unit 1. A = A
BUKAN A + C ; Oleh hukum Morgan A + NOT A. B = A + B
Untuk solusi ini, hukum Morgan harus diperluas untuk mendefinisikan:
BUKAN (BUKAN A). C + BUKAN A = BUKAN A + C
Karena NOT (NOT A) = A oleh involution.
Sederhanakan fungsi logisnya
TIDAK A. TIDAK B. TIDAK C + TIDAK A. TIDAK B. C + TIDAK A. JANGAN C ke ekspresi minimumnya
TIDAK A. TIDAK B. (BUKAN C + C) + BUKAN A. TIDAK C; Anjak (BUKAN A. BUKAN B) dengan faktor umum
TIDAK A. TIDAK B. (1) + TIDAK A. TIDAK C; Dengan Teorema A + BUKAN A = 1
(BUKAN A. BUKAN B) + (BUKAN A. BUKAN C); Secara aturan aturan nol dan unit 1. A = A
BUKAN A (BUKAN B + BUKAN C); Anjak BUKAN dengan faktor umum
TIDAK A. BUKAN (B. C); Menurut hukum Morgan BUKAN (A. B) = BUKAN A + BUKAN B
BUKAN [A + (B. C)] Menurut hukum Morgan BUKAN (A. B) = BUKAN A + BUKAN
Salah satu dari 4 opsi dalam huruf tebal mewakili solusi yang mungkin untuk mengurangi level sirkuit
Sederhanakan fungsi logis ke ekspresi minimumnya
(A) BUKAN B, C + A, B, B, D + B, A B, B). C
(A, BUKAN B, C + A, 0, D + BUKAN, BUKAN B). C; Dengan teorema A. BUKAN A = 0
(A, BUKAN B, C + 0 + BUKAN A, BUKAN B). C; Dengan teorema A. 0 = 0
(A, BUKAN B, C + BUKAN A, BUKAN B). C; Oleh Teorema A + 0 = A
A. TIDAK B. C. C + TIDAK A. TIDAK B. C; Dengan distributivitas produk sehubungan dengan jumlah tersebut
A. TIDAK B. C + TIDAK A. TIDAK B. C; Dengan teorema A. A = A
TIDAK B. C (A + BUKAN A) ; Anjak (BUKAN B. C) dengan faktor umum
TIDAK B. C (1); Dengan Teorema A + BUKAN A = 1
TIDAK B. C; Secara aturan aturan nol dan unit 1. A = A
