Boolean Algebra Historia, twierdzenia i postulaty, przykłady

On Boolean Algebra o algebra Boole'a to notacja algebraiczna stosowana w leczeniu zmiennych binarnych. Obejmuje badania dowolnej zmiennej, które mają tylko 2 możliwe, uzupełniające i wyłączne wyniki. Na przykład zmienne, których jedyną możliwością jest prawdziwa lub fałszywa, poprawna lub niepoprawna, na lub wyłączona, są podstawą badania algebry logicznej.

Boolean Algebra stanowi podstawę cyfrowej elektroniki, co sprawia, że ​​jest dość obecna w współczesności. Rządzi to pojęciem bram logicznych, w której operacje znane w tradycyjnej algebrze są niezwykle dotknięte.

Źródło: Pexels.com

[TOC]

Historia

Boolean Algebra została wprowadzona w 1854 r. Przez angielskiego matematyka George'a Boole'a (1815–1864), który był samozwańczym uczonym tamtych czasów. Jego troska powstała z istniejącego sporu między Augustusem Morgan i Williamem Hamiltonem, o parametry definiujące ten system logiczny.

George Boole argumentował, że definicja wartości numerycznych 0 i 1 odpowiada w dziedzinie logiki, do interpretacji Nic i wszechświata odpowiednio.

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

W 1854 r. Najważniejsze sekcje algebry logicznej są opublikowane w książce ”Badanie praw myślenia, na których oparte są matematyczne teorie logiki i prawdopodobieństwa ”.

Ten ciekawy tytuł zostanie podsumowany później jako "Prawa myślenia ”(„ Prawo myśli ”). Tytuł skoczył na sławę ze względu na natychmiastową uwagę, jaką ze społecznością matematyczną tamtych czasów.

W 1948 r. Służyło to jako wprowadzenie do zastosowania algebry logicznej w ramach całego schematu elektronicznego-cyfrowego.

Struktura

Wartości podstawowe w tego typu algebrze wynoszą 0 i 1, które odpowiadają odpowiednio fałszywemu i prawdziwemu. Podstawowe operacje w algebrze logicznej to 3:

- I operacja koniunkcyjna. Reprezentowane przez punkt ( . ). Synonim produktu.

- Lub operacja rozłączania. Reprezentowane przez krzyż ( +) .Synonim sum.

- Brak operacji lub odniesienia. Reprezentowane przez prefiks nie (nie a). Jest również znany jako uzupełnienie.

Jeśli w zestawie 2 prawa wewnętrznego określone jako produkt i suma są zdefiniowane ( .  + ), mówi się, że lista (a . + ) Jest to algebra logiczna, wtedy.

Może ci służyć: liczby racjonalne: właściwości, przykłady i operacje

Aby zdefiniować retikulum dystrybucji, należy spełnić warunki rozkładu między danymi operacjami:

. jest dystrybucyjny w odniesieniu do sum +                   Do . (b + c) = (a . b) + (a . C)

+ jest dystrybucyjny w odniesieniu do produktu.                  A + (B . c) = (a +b) . (A + C)

Elementy, które składają się na zestaw A, muszą być binarne, a tym samym mieć wartości Wszechświat lub pustka.

Aplikacje

Jego największym scenariuszem aplikacji jest oddział cyfrowy, w którym służy strukturze obwodów, które składają się na operacje logiczne. Art of Circuits Prostota w celu optymalizacji procesów jest wynikiem prawidłowego zastosowania i praktyki algebry boolowskiej.

Od opracowania płyt elektrycznych, poprzez transmisję danych, aż do osiągnięcia programowania w różnych językach, możemy często znaleźć algebrę Boole'a we wszystkich typach aplikacji cyfrowych.

Zmienne logiczne są bardzo powszechne w strukturze programowania. W zależności od używanego języka programowania będą operacje strukturalne kodu, które używają tych zmiennych. Warunkowe i argumenty każdego języka przyznają zmienne logiczne w celu zdefiniowania procesów.

Postuluje

Istnieją twierdzenia, które regulują strukturalne prawa logiczne algebry boolowskiej. W ten sam sposób są one postulowane, aby poznać możliwe wyniki w różnych kombinacjach zmiennych binarnych, zgodnie z przeprowadzoną operacją.

Suma (+)

Operator Lub którego element logiczny jest związek (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 I którego elementem logicznym jest przecięcie (∩) jest zdefiniowane dla zmiennych binarnych w następujący sposób:

0 . 0 = 0

0 . 1 = 0

1 . 0 = 0

1 . 1 = 1

Przeciwnie (nie)

Operator Nie którego element logiczny jest dopełnienie (x) 'jest zdefiniowane dla zmiennych binarnych w następujący sposób:

Nie 0 = 1

Nie 1 = 0

Wiele postulatów różni się od ich równoważników w konwencjonalnej algebrze. Wynika to z domeny zmiennych. Na przykład dodanie elementów wszechświata w algebrze boolowskiej (1 + 1) nie może dawać konwencjonalnego wyniku 2, ponieważ nie należy do elementów kompleksu binarnego.

Twierdzenia

Zero reguły i jednostki

Zdefiniowana jest każda prosta operacja obejmująca element ze zmiennymi binarnymi:

0 + a = a

1 + a = 1

0 . A = 0

1 . A = a

Równe uprawnienia lub idEmploynce

Operacje między równymi zmiennymi są zdefiniowane jako:

Może ci służyć: zgodność: zgodne dane, kryteria, przykłady, ćwiczenia

A + a = a

DO . A = a

Uzupełnienie

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

A + nie a = 1

DO . Nie a = 0

Inwolucja lub podwójne zaprzeczenie

Całe podwójne zaprzeczenie będzie uważane za zmienną naturalną.

Nie (nie a) = a

Do pracy

A + B = B + A; Lato sumy.

DO . B = b . DO ; Przemówienie produktu.

Asocjacyjny

A + (b + c) = (a + b) + c = a + b + c; Suma asocjacyjność.

DO . (B . C) = (a . B) . C = a . B . C; Asocjalizacja produktu.

Dystrybucyjny

A + (B . C) = (a + b) . (A + C); Rozpowszechniać sumę w odniesieniu do produktu.

DO . (B + c) = (a . B) + (a + c); Dystrybucja produktów w odniesieniu do sum.

Przepisy dotyczące absorpcji

Istnieje wiele przepisów dotyczących absorpcji między wieloma odniesieniami, 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 + not 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 przepisy dotyczące transformacji, które zarządzają parami zmiennych, które oddziałują między zdefiniowanymi operacjami algebry boolowskiej ( + . ).

NOTATKA . B) = nie a + nie 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 mają moc dualności. Oznacza to, że poprzez wymianę zmiennych i operacji, wynikowa propozycja jest weryfikowana. To znaczy podczas wymiany 0 na 1 i i lub odwrotnie; Tworzenie wyrażenia, które będzie również całkowicie poprawne.

Na przykład, jeśli weźmiesz postulat

1 . 0 = 0

I stosuje się dualność

0 + 1 = 1

Uzyskany jest inny całkowicie ważny postulat.

Karnaugh Map

Mapa Karnaugh to schemat używany w algebrze logicznej do uproszczenia funkcji logicznych. Składa się z dwuwymiarowego układu podobnego do tabel prawdy logiki zdań. Dane dotyczące prawdziwych tabel można bezpośrednio zawierać na mapie Karnaugh.

Mapa Karnaugh może pomieścić procesy do 6 zmiennych. W przypadku funkcji z większą liczbą zmiennych zaleca się użycie oprogramowania do uproszczenia procesu.

Zaproponowany w 1953 r. Przez Maurice Karnaugh, został ustanowiony jako stałe narzędzie w dziedzinie boole.

Przykłady

Algebra boolejska służy do zmniejszenia drzwi logicznych w obwodzie, w którym priorytetem jest doprowadzenie złożoności lub poziomu obwodu do jego minimalnego możliwego wyrażenia. Wynika to z opóźnienia obliczeniowego, które zakłada każde drzwi.

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

Nie (AB + A + B) . Nie (A + Not B)

Nie [(b + 1) + b] . Nie (a + nie b); Fakorowanie A o współczynniku wspólnym.

Może ci służyć: obliczanie podejść z wykorzystaniem różnicowych

Nie [(1) + b] . Nie (a + nie b); Według twierdzenia A + 1 = 1.

Nie (A + B) . Nie (a + nie b); Według twierdzenia a . 1 = a

( NOTATKA . Nie b) . [ NOTATKA . Nie (nie b)];

Według twierdzenia Morgana nie (a + b) = nie a . Nie b

( NOTATKA . Nie b) .  ( NOTATKA . B); Przez podwójne twierdzenie o odmowie (nie a) = a

NOTATKA . Nie b . NOTATKA . B; Grupa algebraiczna.

NOTATKA . NOTATKA . Nie b . B; Przewidywanie produktu do . B = b . DO

NOTATKA . Nie b . B; Według twierdzenia a . A = a

NOTATKA . 0; Według twierdzenia a . Nie a = 0

0; Według twierdzenia a . 0 = 0

DO . B . C + nie a + a . Nie b . C

DO . C . (B + not b) + not a; Faktoryzacja (a . C) z wspólnym czynnikiem.

DO . C . (1) + nie a; Według twierdzenia a + nie a = 1

DO . C + nie a; Według zerowego twierdzenia o zasadzie i jednostce 1 . A = a

Nie a + c ; Zgodnie z prawem od Morgan do + nie . B = A + B

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

Nie (nie a) . C + not a = nie a + c

Ponieważ nie (nie a) = a przez inwolucję.

Uprościć funkcję logiczną

NOTATKA . Nie b . Nie c + nie a . Nie b . C + nie a . Nie C aż do minimalnego wyrażenia

NOTATKA . Nie b . (Nie c + c) + nie a . Nie c; Faktoryzacja (nie a . Nie b) z wspólnym czynnikiem

NOTATKA . Nie b . (1) + nie a . Nie c; Według twierdzenia a + nie a = 1

(NOTATKA . Nie b) + (nie a . Nie c);  Według zerowego twierdzenia o zasadzie i jednostce 1 . A = a

Nie A (nie b + nie c); Nie weźmie udziału w przypadku wspólnego czynnika

NOTATKA . Nie b . C); Przez prawa Morgana nie (a . B) = nie a + nie b

Nie [a + (b . C)] Przez prawa Morgana nie (a . B) = nie a + nie b

Każda z 4 odważnych opcji stanowi możliwe rozwiązanie zmniejszające poziom obwodu

Uprościj funkcję logiczną, aż jej minimalne wyrażenie

( DO . Nie b .  C + a . Nie b . B . D+ not a . Nie b) . C

( DO . Nie b . C + a . 0 . D + not a . Nie b) . C; Według twierdzenia a . Nie a = 0

( DO . Nie b . C + 0 + nie a . Nie b) . C; Według twierdzenia a . 0 = 0

( DO . Nie b . C + nie a . Nie b) . C; Według twierdzenia a + 0 = a

DO . Nie b . C . C + nie a . Nie b . C; Przez dystrybucję produktu w odniesieniu do sumy

DO . Nie b . C + nie a . Nie b . C; Według twierdzenia a . A = a

Nie b . C (a + not a) ; Faktoryzowanie (nie b . C) z wspólnym czynnikiem

Nie b . C (1); Według twierdzenia a + nie a = 1

Nie b . C; Według zerowego twierdzenia o zasadzie i jednostce 1 . A = a

Bibliografia

1. Boolean Algebra i jej aplikacje J. Eldon Whitesitt. Continental Editorial Company, 1980.
2. Matematyka i inżynieria w informatyce. Christopher J. Van Wyk. Instytut Nauk Komputerowych i technologii. Krajowe Biuro Standardów. Waszyngton, zm. C. 20234
3. Matematyka informatyki. Eric Lehman. Google Inc.
   F Thomson Leighton Department of Mathematics and the Computer Science and AI Laboratory, Massachussetts Institute of Technology; Akamai Technologies.
4. Elementy analizy abstrakcyjnej. Mícheál O'Searcoid Phd. Departament Matematyki. University College Dublin, Beldfield, Dubllind.
5.  Wprowadzenie do logiki i metodologii nauki dedukcyjnej. Alfred Tarski, Nowy Jork Oxford. Oxford University Press.