ALGEBRA BOOLE'A: HISTORIA, TWIERDZENIA I POSTULATY, PRZYKŁADY - MATEMATYKA - 2025

Boole'a lub Boole'a jest oznaczenie algebraiczna stosowane do leczenia zmiennych binarnych. Obejmuje badania dowolnej zmiennej, która ma tylko 2 możliwe wyniki, komplementarne i wzajemnie wykluczające się. Na przykład zmienne, których jedyną możliwością jest prawda lub fałsz, poprawne lub niepoprawne, włączone lub wyłączone, są podstawą badań algebry Boole'a.

Algebra Boole'a stanowi podstawę elektroniki cyfrowej, co czyni ją dość obecną dzisiaj. Kieruje się pojęciem bramek logicznych, w przypadku których znane operacje w tradycyjnej algebrze są szczególnie dotknięte.

Źródło: pexels.com

Historia

Algebra Boole'a została wprowadzona w 1854 roku przez angielskiego matematyka George'a Boole'a (1815-1864), który był ówczesnym samoukiem. Jego obawy wynikały z istniejącego sporu między Augustusem De Morganem a Williamem Hamiltonem o parametry definiujące ten logiczny system.

George Boole argumentował, że definicja wartości liczbowych 0 i 1 odpowiada, w dziedzinie logiki, odpowiednio interpretacji Nic i Wszechświat.

Intencją George'a Boole'a było zdefiniowanie, poprzez właściwości algebry, wyrażeń logiki zdań, niezbędnych do radzenia sobie ze zmiennymi typu binarnego.

W 1854 r. Najważniejsze działy algebry Boole'a zostały opublikowane w książce „Badanie praw myśli, na których opierają się matematyczne teorie logiki i prawdopodobieństwa”.

Ten ciekawy tytuł zostanie później podsumowany jako „Prawa myśli” („Prawa myśli”). Tytuł zyskał sławę dzięki natychmiastowej uwadze społeczności matematycznej tamtych czasów.

W 1948 roku Claude Shannon zastosował ją do projektowania bistabilnych elektrycznych obwodów przełączających. Stanowiło to wprowadzenie do zastosowania algebry Boole'a w całym schemacie elektroniczno-cyfrowym.

Struktura

Elementarnymi wartościami tego typu algebry są 0 i 1, które odpowiadają odpowiednio FALSE i TRUE. Podstawowe operacje algebry Boole'a to 3:

- operacja AND lub koniunkcja. Reprezentowany przez kropkę (.). Synonim produktu.

- operacja LUB rozłączenie. Przedstawiony krzyżykiem (+) Synonim sumy.

- NIE operacja lub negacja. Reprezentowane przez przedrostek NIE (NIE A). Jest również znany jako uzupełnienie.

Jeśli w zbiorze A 2 prawa wewnętrznego składu są zdefiniowane jako iloczyn i suma (. +), Potrójna (A. +) mówi się, że jest algebrą Boole'a wtedy i tylko wtedy, gdy wspomniana trójka spełnia warunek bycia kratą dystrybucyjny.

Aby zdefiniować kratownicę rozdzielczą, muszą być spełnione warunki dystrybucji między podanymi operacjami:

. jest rozdzielny względem sumy + a. (b + c) = (a. b) + (a. c)

+ ma charakter dystrybucyjny w odniesieniu do produktu. a + (b. c) = (a + b). (a + c)

Elementy, które tworzą zbiór A, muszą być binarne, a więc mieć wartości wszechświata lub pustki.

Aplikacje

Jego głównym scenariuszem zastosowania jest gałąź cyfrowa, w której służy do strukturyzowania obwodów tworzących operacje logiczne. Sztuka prostoty obwodów na rzecz optymalizacji procesów jest wynikiem prawidłowego zastosowania i praktyki algebry Boole'a.

Od opracowania paneli elektrycznych, poprzez transmisję danych, aż po programowanie w różnych językach, często możemy znaleźć algebrę Boole'a we wszelkiego rodzaju zastosowaniach cyfrowych.

Zmienne logiczne są bardzo powszechne w strukturze programowania. W zależności od używanego języka programowania w kodzie będą operacje strukturalne korzystające z tych zmiennych. Warunki i argumenty każdego języka dopuszczają zmienne logiczne do definiowania procesów.

Postulaty

Istnieją twierdzenia, które rządzą strukturalnymi prawami logicznymi algebry Boole'a. W ten sam sposób istnieją postulaty znajomości możliwych wyników w różnych kombinacjach zmiennych binarnych, w zależności od wykonywanej operacji.

Suma (+)

Operator OR , którego elementem logicznym jest unia (U), jest zdefiniowany dla zmiennych binarnych w następujący sposób:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 1

Produkt (.)

Operator AND , którego elementem logicznym jest przecięcie (∩) jest zdefiniowany dla zmiennych binarnych w następujący sposób:

0. 0 = 0

0. 1 = 0

jeden. 0 = 0

jeden. 1 = 1

Naprzeciwko (NIE)

Operator NOT , którego elementem logicznym jest dopełnienie (X) 'jest zdefiniowany dla zmiennych binarnych w następujący sposób:

NIE 0 = 1

NIE 1 = 0

Wiele postulatów różni się od ich odpowiedników w algebrze konwencjonalnej. Wynika to z dziedziny zmiennych. Na przykład dodanie elementów wszechświata w algebrze Boole'a (1 + 1) nie może dać konwencjonalnego wyniku 2, ponieważ nie należy on do elementów zbioru binarnego.

Twierdzenia

Zasada zera i jedności

Każda prosta operacja, która obejmuje element ze zmiennymi binarnymi, jest zdefiniowana:

0 + A = A

1 + A = 1

0. A = 0

jeden. A = A

Równe moce lub idempotencja

Operacje między równymi zmiennymi definiuje się jako:

A + A = A

DO . A = A

Uzupełnienie

Każda operacja między zmienną a jej uzupełnieniem jest definiowana jako:

A + NIE A = 1

DO . NIE A = 0

Inwolucja lub podwójna negacja

Każda podwójna negacja będzie uważana za zmienną naturalną.

NOT (NOT A) = A.

Przemienne

A + B = B + A; Przemienność sumy.

DO . B = B. DO ; Przemienność produktu.

Asocjacyjny

A + (B + C) = (A + B) + C = A + B + C; Łączność sumy.

DO . (B. C) = (A. B). C = A. B. DO; Asocjatywność produktu.

Dystrybucyjny

A + (B. C) = (A + B). (A + C); Dystrybucja sumy w odniesieniu do produktu.

DO . (B + C) = (A. B) + (A + C); Dystrybucja produktu w odniesieniu do sumy.

Prawa absorpcji

Istnieje wiele praw absorpcji wśród wielu odniesień, niektóre z najbardziej znanych to:

DO . (A + B) = A

DO . (NIE A + B) = A. b

NIE A (A + B) = NIE A. b

(A + B). (A + NIE B) = A

A + A. B = A

A + NIE A. B = A + B

NIE A + A. B = NIE A + B

DO . B + A. NIE B = A

Twierdzenie Morgana

Są to prawa transformacji, które obsługują pary zmiennych, które oddziałują między zdefiniowanymi operacjami algebry Boole'a (+.).

NOT (A. B) = NOT A + NOT B

NIE (A + B) = NIE A. NIE B

A + B = NIE (NIE A + NIE B)

DO . B = NIE (NIE A. NIE B)

Dwoistość

Wszystkie postulaty i twierdzenia posiadają zdolność dualizmu. Oznacza to, że poprzez wymianę zmiennych i operacji wynikający z tego wniosek jest weryfikowany. To znaczy przy zamianie 0 na 1 i AND na OR lub odwrotnie; tworzone jest wyrażenie, które będzie również całkowicie poprawne.

Na przykład, jeśli postulat zostanie przyjęty

jeden. 0 = 0

I stosuje się dwoistość

0 + 1 = 1

Otrzymano kolejny, doskonale uzasadniony postulat.

Mapa Karnaugh

Mapa Karnaugha jest diagramem używanym w algebrze Boole'a do uproszczenia funkcji logicznych. Składa się z dwuwymiarowego układu podobnego do tablic prawdy logiki zdań. Dane z tabel prawdy można bezpośrednio przechwycić na mapie Karnaugh.

Mapa Karnaugha może uwzględniać procesy maksymalnie 6 zmiennych. W przypadku funkcji z większą liczbą zmiennych zalecane jest użycie oprogramowania w celu uproszczenia procesu.

Zaproponowany w 1953 roku przez Maurice'a Karnaugha, został uznany za stałe narzędzie w dziedzinie algebry Boole'a, ponieważ jego implementacja synchronizuje ludzki potencjał z potrzebą uproszczenia wyrażeń boolowskich, kluczowego aspektu płynności procesów cyfrowych.

Przykłady

Algebra Boole'a jest używana do redukcji bramek logicznych w obwodzie, gdzie priorytetem jest sprowadzenie złożoności lub poziomu obwodu do możliwie najniższego możliwego wyrażenia. Jest to spowodowane opóźnieniem obliczeniowym, które zakłada każda bramka.

W poniższym przykładzie będziemy obserwować uproszczenie wyrażenia logicznego do jego minimum, przy użyciu twierdzeń i postulatów algebry Boole'a.

NIE (AB + A + B). NIE (A + NIE B)

NIE. NIE (A + NIE B); Faktoring A ze wspólnym czynnikiem.

NIE. NIE (A + NIE B); Zgodnie z twierdzeniem A + 1 = 1.

NIE (A + B). NIE (A + NIE B); przez twierdzenie A. 1 = A

(NIE A. NIE B). ;

Zgodnie z twierdzeniem Morgana NIE (A + B) = NIE A. NIE B

(NIE A. NIE B). (NIE A. B); Poprzez twierdzenie o podwójnej negacji NOT (NOT A) = A

ANI. NIE B. ANI. B; Grupowanie algebraiczne.

ANI. ANI. NIE B. B; Przemienność produktu A. B = B. DO

ANI. NIE B. B; Według twierdzenia A. A = A

ANI. 0; Według twierdzenia A. NIE A = 0

0; Według twierdzenia A. 0 = 0

DO . B. C + NIE A + A. NIE B. do

DO . DO. (B + NIE B) + NIE A; Faktoring (A. C) ze wspólnym czynnikiem.

DO . DO. (1) + NIE A; Według twierdzenia A + NIE A = 1

DO . C + NIE A; Zgodnie z zasadą zera twierdzenia i jedności 1. A = A

NIE A + C ; Zgodnie z prawem Morgan A + NOT A. B = A + B

W przypadku tego rozwiązania prawo Morgana należy rozszerzyć, aby zdefiniować:

NIE (NIE A). C + NIE A = NIE A + C

Ponieważ NOT (NOT A) = A przez inwolucję.

Uprość funkcję logiczną

ANI. NIE B. NIE C + NIE A. NIE B. C + NIE A. NIE C do minimum

ANI. NIE B. (NIE C + C) + NIE A. NIE C; Faktoring (NIE A. NIE B) ze wspólnym czynnikiem

ANI. NIE B. (1) + NIE A. NIE C; Według twierdzenia A + NIE A = 1

(NIE A. NIE B) + (NIE A. NIE C); Zgodnie z zasadą zera twierdzenia i jedności 1. A = A

NIE A (NIE B + NIE C); Faktoring NIE A ze wspólnym czynnikiem

ANI. NOT (B. C); Zgodnie z prawami Morgana NIE (A.B) = NIE A + NIE B

NIE Według praw Morgana NIE (A. B) = NIE A + NIE B

Każda z 4 opcji zaznaczonych pogrubioną czcionką przedstawia możliwe rozwiązanie obniżenia poziomu obwodu

Uprość funkcję logiczną do jej najprostszej formy

(A. NIE B. C + A. NIE B. B. D + NIE A. NIE B). do

(A. NIE B. C + A. 0. D + NIE A. NIE B). DO; Według twierdzenia A. NIE A = 0

(A. NIE B. C + 0 + NIE A. NIE B). DO; Według twierdzenia A. 0 = 0

(A. NIE B. C + NIE A. NIE B). DO; Z twierdzenia A + 0 = A

DO . NIE B. DO. C + NIE A. NIE B. DO; Przez dystrybucję produktu w odniesieniu do sumy

DO . NIE B. C + NIE A. NIE B. DO; Według twierdzenia A. A = A

NIE B. C (A + NIE A) ; Faktoring (NOT B. C) ze wspólnym czynnikiem

NIE B. C (1); Według twierdzenia A + NIE A = 1

NIE B. DO; Zgodnie z zasadą zera twierdzenia i jedności 1. A = A

Bibliografia

1. Algebra Boole'a i jej zastosowania J. Eldon Whitesitt. Continental Publishing Company, 1980.
2. Matematyka i inżynieria w informatyce. Christopher J. Van Wyk. Instytut Informatyki i Technologii. National Bureau of Standards. Waszyngton, DC 20234
3. Matematyka dla informatyki. Eric Lehman. Google Inc.
   F Thomson Leighton Wydział Matematyki oraz Laboratorium Informatyki i AI, Massachussetts Institute of Technology; Akamai Technologies.
4. Elementy analizy abstrakcyjnej. Dr Mícheál O'Searcoid Katedra Matematyki. University College Dublin, Beldfield, Dublind.
5. Wprowadzenie do logiki i metodologii nauk dedukcyjnych. Alfred Tarski, New York Oxford. Prasa Uniwersytetu Oksfordzkiego.