Sejarah Algebra Boolean, Teorema dan Postulat, Contohnya

Dia Algebra Boolean Algebra Boole adalah notasi algebra yang digunakan untuk rawatan pembolehubah binari. Meliputi kajian mengenai pembolehubah yang hanya mempunyai 2 hasil yang mungkin, pelengkap dan eksklusif antara satu sama lain. Sebagai contoh, pembolehubah yang satu -satunya kemungkinan adalah benar atau palsu, betul atau tidak betul, hidup atau mati adalah asas kajian algebra Boolean.

Algebra Boolean merupakan asas elektronik digital, yang menjadikannya cukup dalam kontemporari. Ia ditadbir oleh konsep pintu logik, di mana operasi yang diketahui dalam aljabar tradisional sangat terjejas.

Sumber: Pexels.com

[TOC]

Sejarah

Algebra Boolean diperkenalkan pada tahun 1854 oleh ahli matematik Inggeris George Boole (1815 - 1864), yang merupakan seorang sarjana yang diajar sendiri pada masa itu. Kebimbangannya timbul dari pertikaian yang ada antara Augustus Morgan dan William Hamilton, mengenai parameter yang menentukan sistem logik ini.

George Boole berpendapat bahawa definisi nilai berangka 0 dan 1 sepadan, dalam bidang logik, untuk tafsiran Tiada dan alam semesta masing -masing.

Hasrat George Boole adalah untuk menentukan, melalui sifat algebra, ungkapan logik cadangan yang diperlukan untuk menangani pembolehubah binari.

Pada tahun 1854 bahagian paling penting dalam algebra Boolean diterbitkan dalam buku "Penyiasatan undang -undang pemikiran di mana teori matematik logik dan kebarangkalian didasarkan ".

Tajuk yang ingin tahu ini akan diringkaskan kemudian sebagai "Undang -undang pemikiran "(" undang -undang pemikiran "). Tajuk itu melonjak ke kemasyhuran kerana perhatian segera dari komuniti matematik pada masa itu.

Pada tahun 1948 Claude Shannon memohonnya dalam reka bentuk litar penukaran elektrik biestable. Ini berfungsi sebagai pengenalan kepada penggunaan algebra Boolean dalam keseluruhan skim elektronik-digital.

Struktur

Nilai asas dalam jenis algebra ini adalah 0 dan 1, yang sesuai dengan palsu dan benar. Operasi asas dalam algebra Boolean adalah 3:

- Dan operasi konjungsi. Diwakili oleh satu titik ( . ). Sinonim produk.

- Atau atau operasi disjungsi. Diwakili oleh salib ( +) .Sinonim Jumlah.

- Tiada operasi atau denation. Diwakili oleh awalan tidak (bukan a). Ia juga dikenali sebagai pelengkap.

Sekiranya dalam set 2 undang -undang komposisi dalaman dilambangkan sebagai produk dan jumlahnya ditakrifkan ( .  + ), dikatakan bahawa senarai (a . + ) Ini adalah aljabar boolean jika dan hanya jika senarai tersebut memenuhi syarat menjadi retikulum distributif.

Ia boleh melayani anda: Nombor rasional: sifat, contoh dan operasi

Untuk menentukan retikulum pengedaran, keadaan pengedaran antara operasi yang diberikan mesti dipenuhi:

. adalah pengedaran berkenaan dengan jumlah +                   ke . (b + c) = (a . b) + (a . c)

+ adalah pengedaran berkenaan dengan produk.                  A + (b . c) = (a +b) . (A + C)

Unsur -unsur yang membentuk set A mestilah binari, sehingga mempunyai nilai Alam semesta atau kekosongan.

Aplikasi

Senario aplikasi terbesarnya adalah cawangan digital, di mana ia berfungsi untuk menyusun litar yang membentuk operasi logik yang terlibat. Art of Circuits Kesederhanaan untuk mengoptimumkan proses, adalah hasil dari aplikasi dan amalan Algebra Boolean yang betul.

Dari penjelasan papan elektrik, melalui penghantaran data, sehingga mencapai pengaturcaraan dalam bahasa yang berbeza, kita sering dapat mencari algebra Boole dalam semua jenis aplikasi digital.

Pembolehubah boolean sangat biasa dalam struktur pengaturcaraan. Bergantung pada bahasa pengaturcaraan yang digunakan, akan ada operasi struktur kod yang menggunakan pembolehubah ini. Bersyarat dan argumen setiap bahasa mengakui pembolehubah boolean untuk menentukan proses.

Postulates

Terdapat teorem yang mengawal undang -undang logik struktur algebra Boolean. Dengan cara yang sama, mereka diulas untuk mengetahui kemungkinan hasil dalam kombinasi pembolehubah binari yang berlainan, menurut operasi yang dijalankan.

Jumlah (+)

Pengendali Atau Elemen logiknya adalah Kesatuan (U) ditakrifkan untuk pembolehubah binari seperti berikut:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 1

Produk (.)

Pengendali Dan Elemen logiknya adalah persimpangan (∩) ditakrifkan untuk pembolehubah binari seperti berikut:

0 . 0 = 0

0 . 1 = 0

1 . 0 = 0

1 . 1 = 1

Bertentangan (tidak)

Pengendali Tidak Elemen logiknya adalah pelengkap (x) 'ditakrifkan untuk pembolehubah binari seperti berikut:

Bukan 0 = 1

Tidak 1 = 0

Banyak postulates berbeza dari kesamaan mereka dalam aljabar konvensional. Ini disebabkan oleh domain pembolehubah. Sebagai contoh, penambahan unsur -unsur alam semesta dalam algebra boolean (1 + 1) tidak dapat menghasilkan hasil konvensional 2, kerana ia tidak tergolong dalam unsur -unsur kompleks binari.

Teorem

Peraturan dan unit sifar

Sebarang operasi mudah yang melibatkan elemen dengan pembolehubah binari ditakrifkan:

0 + a = a

1 + a = 1

0 . A = 0

1 . A = a

Kuasa yang sama atau idemploynce

Operasi antara pembolehubah yang sama ditakrifkan sebagai:

Boleh melayani anda: Congruence: angka kongruen, kriteria, contoh, latihan

A + a = a

Ke . A = a

Pelengkap

Sebarang operasi antara pembolehubah dan pelengkapnya ditakrifkan sebagai:

A + bukan A = 1

Ke . Bukan a = 0

Penyebaran atau penafian berganda

Semua penafian berganda akan dianggap sebagai pemboleh ubah semula jadi.

Tidak (bukan a) = a

Komutatif

A + b = b + a; Summer of the Sum.

Ke . B = b . Kepada; Komutiviti produk.

Bersekutu

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

Ke . (B . C) = (a . B) . C = a . B . C; Persatuan Produk.

Pengagihan

A + (b . C) = (a + b) . (A + c); Mengedarkan jumlah berkenaan dengan produk.

Ke . (B + c) = (a . B) + (a + c); Pengedaran produk berkenaan dengan jumlah.

Undang -undang penyerapan

Terdapat banyak undang -undang penyerapan antara pelbagai rujukan, beberapa yang paling terkenal ialah:

Ke . (A + b) = a

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

Bukan (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

Teorem Morgan

Mereka adalah undang -undang transformasi, yang menguruskan pasangan pembolehubah yang berinteraksi antara operasi yang ditetapkan dari algebra boolean ( + . ).

CATATAN . B) = tidak A + tidak b

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

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

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

Duality

Semua postulat dan teorem mempunyai kekuatan dualitas. Ini menunjukkan bahawa dengan bertukar pembolehubah dan operasi, cadangan yang dihasilkan disahkan. Iaitu, apabila bertukar 0 untuk 1 dan dan atau sebaliknya; Ungkapan dibuat yang juga akan sah.

Contohnya jika anda mengambil postulat

1 . 0 = 0

Dan dualitas digunakan

0 + 1 = 1

Satu lagi postulat yang sah diperolehi.

Peta Karnaugh

Peta Karnaugh adalah gambarajah yang digunakan dalam algebra boolean untuk memudahkan fungsi logik. Ia terdiri daripada susunan dua dimensi yang serupa dengan jadual kebenaran logik proposisi. Data jadual sebenar boleh diwujudkan secara langsung di peta Karnaugh.

Peta Karnaugh boleh menempatkan proses sehingga 6 pembolehubah. Untuk fungsi dengan jumlah pembolehubah yang lebih besar, penggunaan perisian untuk mempermudah proses disyorkan.

Dicadangkan pada tahun 1953 oleh Maurice Karnaugh, ia ditubuhkan sebagai alat tetap dalam bidang Boole.

Contoh

Algebra Boolean berfungsi untuk mengurangkan pintu logik dalam litar, di mana keutamaan adalah untuk membawa kerumitan atau tahap litar ke ungkapan minimum yang mungkin. Ini disebabkan oleh kelewatan pengiraan yang dianggap oleh setiap pintu.

Dalam contoh berikut, kita akan memerhatikan penyederhanaan ekspresi logik sehingga ekspresi minimum, menggunakan teorem dan postulates algebra Boolean.

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

Tidak [a (b + 1) + b] . Tidak (a + tidak b); Pemfaktoran A dengan faktor biasa.

Boleh melayani anda: Pengiraan pendekatan menggunakan perbezaan

Tidak [a (1) + b] . Tidak (a + tidak b); Oleh Teorem A + 1 = 1.

Tidak (a + b) . Tidak (a + tidak b); Oleh Teorem a . 1 = a

( CATATAN . Tidak b) . [ CATATAN . Tidak (tidak b)];

Oleh teorem Morgan tidak (a + b) = bukan a . Bukan b

( CATATAN . Tidak b) .  ( CATATAN . B); Dengan teorem penafian berganda tidak (bukan a) = a

CATATAN . Bukan b . CATATAN . B; Kumpulan Algebra.

CATATAN . CATATAN . Bukan b . B; Komutiviti produk kepada . B = b . Ke

CATATAN . Bukan b . B; Oleh Teorem a . A = a

CATATAN . 0; Oleh Teorem a . Bukan a = 0

0; Oleh Teorem a . 0 = 0

Ke . B . C + bukan a + a . Bukan b . C

Ke . C . (B + tidak b) + bukan A; Pemfaktoran (a . C) dengan faktor biasa.

Ke . C . (1) + bukan A; Oleh teorem a + bukan a = 1

Ke . C + bukan A; Oleh teorem peraturan sifar dan unit 1 . A = a

Bukan A + C ; Oleh undang -undang dari Morgan ke + bukan a . B = a + b

Untuk penyelesaian ini, undang -undang Morgan mesti diperluaskan untuk menentukan:

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

Kerana tidak (bukan a) = a dengan terlibat.

Memudahkan fungsi logik

CATATAN . Bukan b . Bukan c + bukan a . Bukan b . C + bukan a . Tidak c sehingga ungkapan minimumnya

CATATAN . Bukan b . (Bukan c + c) + bukan a . Bukan c; Pemfaktoran (bukan a . Tidak b) dengan faktor biasa

CATATAN . Bukan b . (1) + bukan a . Bukan c; Oleh teorem a + bukan a = 1

(CATATAN . Bukan b) + (bukan a . Bukan c);  Oleh teorem peraturan sifar dan unit 1 . A = a

Bukan (bukan b + tidak c); Pemfaktoran bukan dengan faktor biasa

CATATAN . Tidak (b . C); Oleh undang -undang morgan tidak (a . B) = tidak A + tidak b

Tidak [a + (b . C)] Oleh undang -undang morgan tidak (a . B) = tidak A + tidak b

Mana -mana pilihan 4 berani mewakili penyelesaian yang mungkin untuk mengurangkan tahap litar

Memudahkan fungsi logik sehingga ungkapan minimumnya

(Kepada . Bukan b .  C + a . Bukan b . B . D+ bukan a . Tidak b) . C

(Kepada . Bukan b . C + a . 0 . D + bukan a . Tidak b) . C; Oleh Teorem a . Bukan a = 0

(Kepada . Bukan b . C + 0 + bukan a . Tidak b) . C; Oleh Teorem a . 0 = 0

(Kepada . Bukan b . C + bukan a . Tidak b) . C; Oleh teorem a + 0 = a

Ke . Bukan b . C . C + bukan a . Bukan b . C; Dengan pengedaran produk berkenaan dengan jumlah

Ke . Bukan b . C + bukan a . Bukan b . C; Oleh Teorem a . A = a

Bukan b . C (a + tidak a) ; Pemfaktoran (bukan b . C) dengan faktor biasa

Bukan b . C (1); Oleh teorem a + bukan a = 1

Bukan b . C; Oleh teorem peraturan sifar dan unit 1 . A = a

Rujukan

1. Algebra Boolean dan aplikasi Jnya. Eldon Whitesitt. Syarikat Editorial Continental, 1980.
2. Matematik dan Kejuruteraan dalam Sains Komputer. Christopher J. Van Wyk. Institut Sains dan Teknologi Komputer. Biro Piawaian Kebangsaan. Washington, d. C. 20234
3. Matematik untuk Sains Komputer. Eric Lehman. Google Inc.
   F Thomson Leighton Jabatan Matematik dan Sains Komputer dan Makmal AI, Institut Teknologi Massachussetts; Akamai Technologies.
4. Unsur analisis abstrak. Mícheál O'Searcoid PhD. Jabatan Matematik. Universiti Kolej Dublin, Beldfield, Dublind.
5.  Pengenalan kepada Logik dan Metodologi Sains Deduktif. Alfred Tarski, New York Oxford. Oxford University Press.