Sejarah Aljabar Boolean, Teorema dan Deposulat, Contoh

Dia aljabar Boolean o Aljabar Boole adalah notasi aljabar yang digunakan untuk pengobatan variabel biner. Mencakup studi dari variabel apa pun yang hanya memiliki 2 hasil yang mungkin, komplementer dan eksklusif satu sama lain. Misalnya, variabel yang hanya kemungkinannya benar atau salah, benar atau salah, hidup atau mati adalah dasar dari studi aljabar boolean.

Aljabar Boolean merupakan dasar elektronik digital, yang membuatnya cukup hadir dalam kontemporer. Ini diatur oleh konsep gerbang logis, di mana operasi yang dikenal dalam aljabar tradisional sangat terpengaruh.

Sumber: Pexels.com

[TOC]

Sejarah

Aljabar Boolean diperkenalkan pada tahun 1854 oleh ahli matematika bahasa Inggris George Boole (1815 - 1864), yang merupakan sarjana yang dijalankan sendiri saat itu. Kekhawatirannya muncul dari perselisihan yang ada antara Augustus dari Morgan dan William Hamilton, tentang parameter yang menentukan sistem logis ini.

George Boole berpendapat bahwa definisi nilai numerik 0 dan 1 sesuai, di bidang logika, dengan interpretasi Tidak ada dan alam semesta masing -masing.

Niat George Boole adalah untuk mendefinisikan, melalui sifat -sifat aljabar, ekspresi logika proposisional yang diperlukan untuk menangani variabel biner.

Pada tahun 1854 bagian paling signifikan dari aljabar Boolean diterbitkan dalam buku ini "Investigasi Hukum Pemikiran tentang Teori Matematika Logika dan Probabilitas Berdasarkan ”.

Judul yang aneh ini akan dirangkum nanti sebagai "Hukum Pemikiran "(" Hukum Pikiran "). Judul melonjak menjadi terkenal karena perhatian segera dari komunitas matematika saat itu.

Pada tahun 1948 Claude Shannon menerapkannya dalam desain sirkuit switching listrik. Ini berfungsi sebagai pengantar penerapan aljabar boolean dalam seluruh skema elektronik-digital.

Struktur

Nilai dasar dalam jenis aljabar ini adalah 0 dan 1, yang masing -masing sesuai dengan salah dan benar. Operasi mendasar di aljabar Boolean adalah 3:

- Dan operasi konjungsi. Diwakili oleh suatu titik ( . ). Sinonim dari produk tersebut.

- Atau atau operasi disjungsi. Diwakili oleh salib ( +) .Sinonim dari jumlah tersebut.

- Tidak ada operasi atau denation. Diwakili oleh awalan bukan (bukan a). Itu juga dikenal sebagai komplemen.

Jika dalam satu set 2 hukum komposisi internal yang dilambangkan sebagai produk dan jumlah didefinisikan ( .  + ), dikatakan bahwa daftar (a . + ) Ini adalah aljabar boolean jika dan hanya jika daftar tersebut memenuhi syarat menjadi retikulum distributif.

Itu dapat melayani Anda: bilangan rasional: properti, contoh dan operasi

Untuk mendefinisikan retikulum distributif, kondisi distribusi antara operasi yang diberikan harus dipenuhi:

. distributif sehubungan dengan jumlahnya +                   ke . (b + c) = (a . b) + (a . C)

+ distributif sehubungan dengan produk.                  A + (b . c) = (a +b) . (A + C)

Elemen -elemen yang membentuk himpunan A harus biner, sehingga memiliki nilai Alam semesta atau kekosongan.

Aplikasi

Skenario aplikasi terbesarnya adalah cabang digital, di mana ia berfungsi untuk menyusun sirkuit yang membentuk operasi logis yang terlibat. Seni kesederhanaan sirkuit untuk mengoptimalkan proses, adalah hasil dari aplikasi dan praktik aljabar boolean yang benar.

Dari elaborasi papan listrik, melalui transmisi data, hingga mencapai pemrograman dalam berbagai bahasa, kita dapat sering menemukan aljabar Boole di semua jenis aplikasi digital.

Variabel boolean sangat umum dalam struktur pemrograman. Bergantung pada bahasa pemrograman yang digunakan, akan ada operasi struktural kode yang menggunakan variabel -variabel ini. Bersyarat dan argumen dari setiap bahasa mengakui variabel boolean untuk mendefinisikan proses.

Dalil

Ada teorema yang mengatur hukum logika struktural aljabar boolean. Dengan cara yang sama, mereka dipostulatkan untuk mengetahui hasil yang mungkin dalam kombinasi variabel biner yang berbeda, menurut operasi yang dilakukan.

Jumlah (+)

Operator Atau Elemen logisnya adalah Union (U) didefinisikan untuk variabel biner sebagai berikut:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 1

Produk (.)

Operator Dan yang elemen logisnya adalah persimpangan (∩) didefinisikan untuk variabel biner sebagai berikut:

0 . 0 = 0

0 . 1 = 0

1 . 0 = 0

1 . 1 = 1

Berlawanan (tidak)

Operator Bukan yang elemen logisnya adalah komplemen (x) 'didefinisikan untuk variabel biner sebagai berikut:

Bukan 0 = 1

Bukan 1 = 0

Banyak postulat berbeda dari padanannya dalam aljabar konvensional. Ini karena domain variabel. Misalnya, penambahan elemen alam semesta dalam aljabar boolean (1 + 1) tidak dapat menghasilkan hasil konvensional 2, karena itu bukan milik unsur -unsur kompleks biner.

Teorema

Nol aturan dan unit

Operasi sederhana apa pun yang melibatkan elemen dengan variabel biner didefinisikan:

0 + a = a

1 + a = 1

0 . A = 0

1 . A = a

Kekuatan yang sama atau idemplight

Operasi antara variabel yang sama didefinisikan sebagai:

Dapat melayani Anda: kongruensi: angka kongruen, kriteria, contoh, latihan

A + a = a

KE . A = a

Komplemen

Operasi apa pun antara variabel dan pelengkapnya didefinisikan sebagai:

A + bukan a = 1

KE . Bukan A = 0

Involusi atau penolakan ganda

Semua penolakan ganda akan dianggap sebagai variabel alami.

Bukan (bukan a) = a

Komutatif

A + b = b + a; Musim panas jumlahnya.

KE . B = b . KE ; Komutasi produk.

Asosiatif

A + (b + c) = (a + b) + c = a + b + c; Jumlah asosiasi.

KE . (B . C) = (a . B) . C = a . B . C; Asosiasi Produk.

Distributif

A + (b . C) = (a + b) . (A + c); Mendistribusikan jumlah sehubungan dengan produk.

KE . (B + c) = (a . B) + (a + c); Distributivitas produk sehubungan dengan jumlah.

Hukum penyerapan

Ada banyak hukum penyerapan antara beberapa referensi, beberapa yang paling terkenal adalah:

KE . (A + b) = a

KE . (Bukan A + B) = a . B

Bukan a (a + b) = bukan a . B

(A + B) . (A + tidak b) = a

A + a . B = a

A + bukan a . B = a + b

Bukan + a . B = bukan A + B

KE . B + a . Bukan b = a

Teorema Morgan

Mereka adalah undang -undang transformasi, yang mengelola pasangan variabel yang berinteraksi antara operasi aljabar boolean ( + . ).

CATATAN . B) = bukan A + bukan b

Tidak (a +b) = bukan a . Tidak b

A + b = tidak (bukan a + bukan b)

KE . B = tidak (bukan a . Tidak b)

Dualitas

Semua dalil dan teorema memiliki kekuatan dualitas. Ini menyiratkan bahwa dengan menukar variabel dan operasi, proposisi yang dihasilkan diverifikasi. Yaitu, saat bertukar 0 untuk 1 dan dan dan 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 sangat 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 logika proposisional. Data tabel nyata dapat secara langsung diwujudkan di peta Karnaugh.

Peta Karnaugh dapat menampung proses hingga 6 variabel. Untuk fungsi dengan jumlah variabel yang lebih besar, penggunaan perangkat lunak untuk menyederhanakan proses disarankan.

Diusulkan pada tahun 1953 oleh Maurice Karnaugh, didirikan sebagai alat tetap di bidang Boole.

Contoh

Aljabar boolean berfungsi untuk mengurangi pintu logis di sirkuit, di mana prioritasnya adalah untuk membawa kompleksitas atau tingkat sirkuit ke ekspresi minimum yang mungkin terjadi. Ini karena keterlambatan komputasi yang menurut masing -masing pintu.

Dalam contoh berikut kita akan mengamati penyederhanaan ekspresi logis sampai ekspresi minimumnya, menggunakan teorema dan postulat aljabar boolean.

Tidak (ab + a + b) . Tidak (a + bukan b)

Bukan [a (b + 1) + b] . Tidak (a + bukan b); Memperhitungkan A dengan faktor umum.

Dapat melayani Anda: perhitungan pendekatan menggunakan diferensial

Bukan [a (1) + b] . Tidak (a + bukan b); Dengan teorema A + 1 = 1.

Tidak (a + b) . Tidak (a + bukan b); Oleh teorema a . 1 = a

( CATATAN . Tidak b) . [ CATATAN . Bukan (bukan b)];

Oleh teorema Morgan bukan (a + b) = bukan a . Tidak b

( CATATAN . Tidak b) .  ( CATATAN . B); Dengan teorema penolakan ganda bukan (bukan A) = a

CATATAN . Tidak b . CATATAN . B; Grup Aljabar.

CATATAN . CATATAN . Tidak b . B; Komutasi produk ke . B = b . KE

CATATAN . Tidak b . B; Oleh teorema a . A = a

CATATAN . 0; Oleh teorema a . Bukan A = 0

0; Oleh teorema a . 0 = 0

KE . B . C + bukan + a . Tidak b . C

KE . C . (B + tidak b) + bukan A; Faktorisasi (a . C) dengan faktor umum.

KE . C . (1) + bukan A; Dengan teorema a + bukan a = 1

KE . C + bukan A; Oleh nol aturan teorema dan unit 1 . A = a

Bukan A + C ; Secara hukum dari Morgan ke + bukan a . B = a + b

Untuk solusi ini, hukum Morgan harus diperluas untuk mendefinisikan:

Bukan (bukan a) . C + bukan a = bukan a + c

Karena tidak (bukan a) = a secara involution.

Sederhanakan fungsi logis

CATATAN . Tidak b . Bukan c + bukan a . Tidak b . C + bukan a . Tidak c sampai ekspresi minimum

CATATAN . Tidak b . (Bukan c + c) + bukan a . Bukan c; Faktorisasi (bukan a . Bukan b) dengan faktor umum

CATATAN . Tidak b . (1) + bukan a . Bukan c; Dengan teorema a + bukan a = 1

(CATATAN . Bukan b) + (bukan a . Bukan c);  Oleh nol aturan teorema dan unit 1 . A = a

Bukan A (bukan b + bukan c); Memperhitungkan bukan dengan faktor umum

CATATAN . Tidak 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 b

Salah satu dari 4 opsi tebal merupakan solusi yang mungkin untuk mengurangi tingkat sirkuit

Sederhanakan fungsi logis hingga ekspresi minimum

( KE . Tidak b .  C + a . Tidak b . B . D+ bukan a . Tidak b) . C

( KE . Tidak b . C + a . 0 . D + bukan a . Tidak b) . C; Oleh teorema a . Bukan A = 0

( KE . Tidak b . C + 0 + bukan a . Tidak b) . C; Oleh teorema a . 0 = 0

( KE . Tidak b . C + bukan a . Tidak b) . C; Dengan teorema A + 0 = a

KE . Tidak b . C . C + bukan a . Tidak b . C; Dengan distributtivitas produk sehubungan dengan jumlah

KE . Tidak b . C + bukan a . Tidak b . C; Oleh teorema a . A = a

Tidak b . C (A + bukan A) ; Faktorisasi (bukan B . C) dengan faktor umum

Tidak b . C (1); Dengan teorema a + bukan a = 1

Tidak b . C; Oleh nol aturan teorema dan unit 1 . A = a

Referensi

1. Aljabar boolean dan aplikasi j. Eldon Whitesitt. Perusahaan Editorial Kontinental, 1980.
2. Matematika dan Teknik dalam Ilmu Komputer. Christopher J. Van Wyk. Institut Ilmu Komputer dan Teknologi. Biro Standar Nasional. Washington, d. C. 20234
3. Matematika untuk Ilmu Komputer. Eric Lehman. Google Inc.
   F Thomson Leighton Departemen Matematika dan Laboratorium Ilmu Komputer dan AI, Institut Teknologi Massachussetts; Teknologi Akamai.
4. Elemen analisis abstrak. Mícheál O'Searcoid PhD. Departemen Matematika. University College Dublin, Beldfield, Dublind.
5.  Pengantar logika dan metodologi ilmu deduktif. Alfred Tarski, New York Oxford. Oxford University Press.