Algebra Boole'a - Boolean algebra

W matematyce i logice matematycznej , Boole'a jest gałęzią algebry , w których wartości tych zmiennychwartości logicznych prawda i fałsz , zazwyczaj oznaczone 1 i 0, odpowiednio. Zamiast algebry elementarnej , gdzie wartości zmiennych są liczbami, a operacjami pierwszymi są dodawanie i mnożenie, głównymi operacjami algebry Boole'a są koniunkcja ( i ) oznaczona jako ∧, alternatywa ( lub ) oznaczona jako ∨ oraz negacja ( nie ) oznaczony jako ¬. Jest to zatem formalizm do opisu operacji logicznych , w taki sam sposób, w jaki algebra elementarna opisuje operacje numeryczne.

Algebra Boole'a została wprowadzona przez George'a Boole'a w jego pierwszej książce The Mathematical Analysis of Logic (1847), a dokładniej opisana w jego An Investigation of the Laws of Thought (1854). Według Huntingtona , termin „algebra Boole'a” został po raz pierwszy zaproponowany przez Sheffera w 1913 roku, chociaż Charles Sanders Peirce nadał tytuł „Algebra Boole'a z jedną stałą” pierwszemu rozdziałowi swojej „Najprostszej matematyki” w 1880 roku. był fundamentalny w rozwoju elektroniki cyfrowej i jest przewidziany we wszystkich nowoczesnych językach programowania . Jest również używany w teorii mnogości i statystyce .

Historia

Prekursor logicznego Algebra był Gottfried Wilhelm Leibniz jest Algebra koncepcji . Algebra pojęć Leibniza jest dedukcyjnie równoważna algebrze zbiorów Boole'a.

Algebra Boole'a wyprzedziła współczesne osiągnięcia algebry abstrakcyjnej i logiki matematycznej ; jest jednak postrzegana jako związana z początkami obu dziedzin. W abstrakcyjnym otoczeniu algebra Boole'a została udoskonalona pod koniec XIX wieku przez Jevonsa , Schrödera , Huntingtona i innych, aż osiągnęła nowoczesną koncepcję (abstrakcyjnej) struktury matematycznej . Na przykład, empiryczna obserwacja, że można manipulować wyrażeń w algebry zbiorów , tłumacząc je do wyrażeń w algebrze Boole'a jest, wyjaśnione jest w nowoczesnych warunkach, mówiąc, że algebra zbiorów jest Boole'a (uwaga nieokreślony ). W rzeczywistości MH Stone udowodnił w 1936 roku, że każda algebra Boole'a jest izomorficzna z ciałem zbiorów .

W latach 30. XX wieku, badając obwody przełączające , Claude Shannon zauważył, że w tym środowisku można również zastosować zasady algebry Boole'a i wprowadził algebrę przełączania jako sposób analizy i projektowania obwodów za pomocą środków algebraicznych pod kątem bramek logicznych . Shannon miał już do swojej dyspozycji abstrakcyjny aparat matematyczny, dlatego odrzucił swoją algebrę przełączania jako dwuelementową algebrę Boole'a . W nowoczesnych środowiskach inżynierii obwodów nie ma potrzeby brania pod uwagę innych algebr Boole'a, dlatego "algebry przełączania" i "algebry Boole'a" są często używane zamiennie.

Skuteczna realizacja z funkcji logicznych jest podstawowym problemem w projektowaniu z kombinowanych logiki obwodów. Nowoczesne narzędzia do automatyzacji projektowania elektronicznego dla obwodów VLSI często opierają się na wydajnej reprezentacji funkcji logicznych znanych jako (o zredukowanej kolejności) binarnych diagramach decyzyjnych (BDD) do syntezy logicznej i weryfikacji formalnej .

Zdania logiczne, które można wyrazić w klasycznym rachunku zdań, mają równoważne wyrażenie w algebrze Boole'a. Tak więc logika Boole'a jest czasami używana do oznaczenia rachunku zdań wykonywanego w ten sposób. Algebra Boole'a nie jest wystarczająca do przechwytywania formuł logicznych za pomocą kwantyfikatorów , jak te z logiki pierwszego rzędu .

Chociaż rozwój logiki matematycznej nie podążał za programem Boole'a, związek między jego algebrą a logiką został później położony na twardym gruncie w kontekście logiki algebraicznej , która bada również systemy algebraiczne wielu innych logik. Problem ustalenia, czy zmienne danego Boolean (zdań) formuły mogą być przypisane w taki sposób, aby uczynić formułę oceniać true nazywana jest problemem Boolean spełnialności (SAT) i ma znaczenie dla informatyki teoretycznej , będąc pierwszy problem okazał się NP-zupełny . Ściśle powiązany model obliczeń, znany jako obwód logiczny, wiąże złożoność czasową ( algorytmu ) ze złożonością obwodu .

Wartości

Podczas gdy wyrażenia oznaczają głównie liczby w algebrze elementarnej, w algebrze Boole'a oznaczają wartości prawdziwości false i true . Wartości te są reprezentowane przez bity (lub cyfry binarne), czyli 0 i 1. Nie zachowują się jak liczby całkowite 0 i 1, dla których 1 + 1 = 2 , ale mogą być identyfikowane z elementami pola dwuelementowego GF(2) , czyli arytmetyka liczb całkowitych modulo 2 , dla której 1 + 1 = 0 . Dodawanie i mnożenie odgrywają następnie role logiczne odpowiednio XOR (wykluczające-lub) i AND (koniunkcja), z alternatywą xy (włącznie-lub) definiowalną jako x + yxy .

Algebra Boole'a zajmuje się również funkcjami, które mają swoje wartości w zbiorze {0, 1}. Sekwencja bitów jest powszechnie stosowany dla takich funkcji. Innym przykładem jest podzbiorów zbioru E : podzbioru F od E , można określić funkcję wskaźnika , który przyjmuje wartości 1 w F i 0 poza F . Najbardziej ogólnym przykładem są elementy algebry Boole'a , a wszystkie powyższe są ich przykładami.

Podobnie jak w przypadku algebry elementarnej, czysto równania część teorii może być rozwijana bez uwzględniania wyraźnych wartości zmiennych.

Operacje

Podstawowe operacje

Podstawowe operacje algebry Boole'a to koniunkcja , alternatywa i negacja . Te operacje logiczne są wyrażane za pomocą odpowiednich operatorów binarnych AND i OR oraz jednoargumentowego operatora NOT , łącznie określanych jako operatory logiczne .

Podstawowe operacje logiczne na zmiennych x i y są zdefiniowane w następujący sposób:

Alternatywnie wartości xy , xy i ¬ x mogą być wyrażone przez tabelaryzowanie ich wartości za pomocą tabel prawdy w następujący sposób:

Jeśli wartości logiczne 0 i 1 są interpretowane jako liczby całkowite, to operacje te mogą być wyrażone zwykłymi operacjami arytmetycznymi (gdzie x + y używa dodawania, a xy używa mnożenia) lub za pomocą funkcji minimum/maksimum:

Można by uznać, że tylko negacja i jedna z dwóch pozostałych operacji są podstawowe, ze względu na następujące tożsamości, które pozwalają na zdefiniowanie koniunkcji w kategoriach negacji i alternatywy i odwrotnie ( prawa De Morgana ):

Operacje drugorzędne

Trzy operacje Boole'a opisane powyżej są określane jako podstawowe, co oznacza, że ​​mogą być traktowane jako podstawa dla innych operacji Boole'a, które można z nich zbudować przez kompozycję, sposób, w jaki operacje są łączone lub składane. Operacje złożone z operacji podstawowych obejmują następujące przykłady:

Warunek materialny :
Wyłączne LUB ( XOR ):
Równoważność logiczna :

Z tych definicji wynikają następujące tabele prawdy, podające wartości tych operacji dla wszystkich czterech możliwych danych wejściowych.

Operacje drugorzędne. Tabela 1
0 0 1 0 1
1 0 0 1 0
0 1 1 1 0
1 1 1 0 1
Warunki materialne
Pierwsza operacja x  →  y lub C xy nazywana jest implikacją materialną . Jeśli x jest prawdą, to wartość x  →  y jest uważana za wartość y (np. jeśli x jest prawdziwe, a y jest fałszywe, to x  →  y również jest fałszywe). Ale jeśli x jest fałszywe, to wartość y można zignorować; jednak operacja musi zwrócić jakąś wartość logiczną i są tylko dwie możliwości. Czyli z definicji x  →  y jest prawdziwe, gdy x jest fałszywe. ( logika istotności sugeruje tę definicję, postrzegając implikację z fałszywą przesłanką jako coś innego niż prawda lub fałsz).
Wyłączne OR ( XOR )
Druga operacja, x  ⊕  Y lub J -y , nazywany jest wyłącznym lub (często w skrócie jako XOR), w celu odróżnienia go od alternatywy jak rodzaj włącznie. Wyklucza to możliwość, że zarówno x, jak i y są prawdziwe (np. patrz tabela): jeśli oba są prawdziwe, wynik jest fałszywy. Zdefiniowany w kategoriach arytmetycznych jest to dodawanie, gdzie mod 2 to 1 + 1 = 0.
Równoważność logiczna
Trzecią operacją, uzupełnieniem wyłączności lub, jest równoważność lub równość Boole'a: x  ≡  y lub E xy , jest prawdziwe tylko wtedy, gdy x i y mają tę samą wartość. Stąd x  ⊕  y jako jego uzupełnienie można rozumieć jako x  ≠  y , będąc prawdziwe tylko wtedy, gdy x i y są różne. Zatem jego odpowiednikiem w arytmetycznym mod 2 jest x + y . Odpowiednikiem równoważności w arytmetycznym mod 2 jest x + y + 1.

Biorąc pod uwagę dwa argumenty, każdy z dwiema możliwymi wartościami, istnieją 2 2 = 4 możliwe kombinacje wejść. Ponieważ każde wyjście może mieć dwie możliwe wartości, istnieje łącznie 2 4 = 16 możliwych binarnych operacji logicznych . Każda taka operacja lub funkcja (jak również każda funkcja logiczna z większą liczbą danych wejściowych) może być wyrażona za pomocą podstawowych operacji z góry. Stąd podstawowe operacje są funkcjonalnie kompletne .

Prawa

Prawo Boole'a Algebra jest tożsamości , takie jak X ∨ ( yz ) = ( xy ) ∨ z dwóch logicznymi warunkami, w których logiczne określenie jest zdefiniowana jako wyraz zbudowany ze zmiennych i stałych 0 i 1 z użyciem operacje ∧, ∨ i ¬. Pojęcie można rozszerzyć na terminy obejmujące inne operacje logiczne, takie jak ⊕, → i ≡, ale takie rozszerzenia są niepotrzebne do celów, do których są przypisane prawa. Do takich celów należy zdefiniowanie algebry Boole'a jako dowolnego modelu praw Boole'a oraz jako środka do wyprowadzania nowych praw ze starych, jak w wyprowadzeniu x ∨ ( yz ) = x ∨ ( zy ) z yz = zy (jak omówiono w § Aksjomatyzującą algebrę Boole'a ).

Monotonne prawa

Algebra Boole'a spełnia wiele takich samych praw jak zwykła algebra, gdy dopasujemy ∨ z dodawaniem i ∧ z mnożeniem. W szczególności następujące prawa są wspólne dla obu rodzajów algebry:

Stowarzyszenie :
Stowarzyszenie :
Przemienność :
Przemienność :
Dystrybucja ponad :
Tożsamość dla :
Tożsamość dla :
Anihilator dla :

Następujące prawa obowiązują w algebrze Boole'a, ale nie w zwykłej algebrze:

Anihilator dla :
Idempotencja :
Idempotencja :
Absorpcja 1:
Absorpcja 2:
Dystrybucja ponad :

Przyjęcie x = 2 w trzecim prawie powyżej pokazuje, że nie jest to zwykłe prawo algebry, ponieważ 2 × 2 = 4 . Pozostałe pięć praw można sfalsyfikować w zwykłej algebrze, przyjmując, że wszystkie zmienne mają wartość 1. Na przykład, w prawie absorpcji 1, lewa strona miałaby wartość 1(1 + 1) = 2 , a prawa strona 1 ( i tak dalej).

Wszystkie prawa omówione do tej pory dotyczyły koniunkcji i alternatywy. Operacje te mają właściwość polegającą na tym, że zmiana dowolnego argumentu pozostawia dane wyjściowe bez zmian lub dane wyjściowe zmieniają się w taki sam sposób, jak dane wejściowe. Podobnie, zmiana dowolnej zmiennej z 0 na 1 nigdy nie powoduje zmiany wyniku z 1 na 0. Operacje z tą właściwością są nazywane monotone . Tak więc dotychczas wszystkie aksjomaty dotyczyły monotonicznej logiki Boole'a. Niemonotoniczność wchodzi przez dopełnienie ¬ w następujący sposób.

Prawa niemonotoniczne

Operacja dopełnienia jest zdefiniowana przez następujące dwa prawa.

Wszystkie własności negacji, w tym poniższe prawa, wynikają wyłącznie z dwóch powyższych praw.

Zarówno w algebrze zwykłej, jak i Boole'a, negacja działa na zasadzie wymiany par elementów, dzięki czemu w obu algebrach spełnia prawo podwójnej negacji (zwane również prawem inwolucji)

Ale podczas gdy algebra zwykła spełnia te dwa prawa

Algebra Boole'a spełnia prawa De Morgana :

Kompletność

Wymienione powyżej prawa definiują algebrę Boole'a w tym sensie, że pociągają za sobą resztę podmiotu. Do tego celu wystarczą prawa Uzupełnienia 1 i 2 wraz z prawami monotonicznymi i dlatego mogą być traktowane jako jeden możliwy kompletny zbiór praw lub aksjomatyzacja algebry Boole'a. Każde prawo algebry Boole'a wynika logicznie z tych aksjomatów. Co więcej, algebry Boole'a można następnie zdefiniować jako modele tych aksjomatów, jak potraktowano w § Algebry Boole'a .

Dla wyjaśnienia, spisanie dalszych praw algebry Boole'a nie może rodzić żadnych nowych konsekwencji tych aksjomatów, ani nie może wykluczyć żadnego ich modelu. W przeciwieństwie do tego, na liście niektórych, ale nie wszystkich tych samych praw, mogły istnieć prawa Boole'a, które nie wynikają z tych na liście, a ponadto istniałyby modele wymienionych praw, które nie były algebrami Boole'a.

Ta aksjomatyzacja nie jest bynajmniej jedyna, a nawet niekoniecznie najbardziej naturalna, biorąc pod uwagę, że nie zwracaliśmy uwagi na to, czy niektóre z aksjomatów wynikają z innych, ale po prostu zdecydowaliśmy się zatrzymać, gdy zauważyliśmy, że mamy wystarczająco dużo praw, omówionych dalej w § Aksjomatyzacja Algebra Boole'a . Lub pośrednie pojęcie aksjomatu można całkowicie ominąć, definiując prawo Boole'a bezpośrednio jako dowolną tautologię , rozumianą jako równanie, które obowiązuje dla wszystkich wartości jego zmiennych powyżej 0 i 1. Wszystkie te definicje algebry Boole'a można wykazać, że są równoważne.

Zasada dualności

Zasada: Jeśli {X, R} jest posetem , to {X, R(inverse)} jest również posetem.

Nie ma nic magicznego w doborze symboli dla wartości algebry Boole'a. Moglibyśmy zmienić nazwy 0 i 1 na α i β , i tak długo, jak robiliśmy to konsekwentnie, nadal byłaby to algebra Boole'a, choć z pewnymi oczywistymi różnicami kosmetycznymi.

Ale załóżmy, że zmieniamy nazwy 0 i 1 na 1 i 0 odpowiednio. Wtedy nadal byłaby to algebra Boole'a, a ponadto operująca na tych samych wartościach. Jednak nie byłoby to identyczne z naszą oryginalną algebrą Boole'a, ponieważ teraz znajdujemy ∨ zachowujący się tak jak zwykł robić i na odwrót. Tak więc nadal istnieją pewne kosmetyczne różnice, które pokazują, że majstrowaliśmy przy zapisie, mimo że nadal używamy zer i jedynek.

Ale jeśli oprócz zamiany nazw wartości wymieniamy również nazwy dwóch operacji binarnych, teraz nie ma śladu po tym, co zrobiliśmy. Produkt końcowy jest całkowicie nie do odróżnienia od tego, od czego zaczęliśmy. Możemy zauważyć, że kolumny dla xy i xy w tabelach prawdy nie zmieniło miejsca, ale że przełącznik jest nieistotna.

Gdy wartości i operacje można sparować w taki sposób, że wszystko, co ważne, pozostaje niezmienione, gdy wszystkie pary są przełączane jednocześnie, nazywamy członków każdej pary podwójnymi . Zatem 0 i 1 są podwójne, a ∧ i ∨ są podwójne. Duality Zasada , zwana również De Morgan dwoistość , twierdzi, że Boole'a jest niezmienione, gdy wszystkie podwójne pary są zamienione.

Jedyną zmianą, której nie musieliśmy wprowadzać w ramach tego węzła, było uzupełnienie. Mówimy, że dopełnienie jest działaniem samopodwójnym . Operacja tożsamości lub nic nie rób x (skopiuj dane wejściowe na dane wyjściowe) jest również samodzielna. Bardziej skomplikowanym przykładem samo-podwójnej operacji jest ( xy ) ∨ ( yz ) ∨ ( zx ) . Nie istnieje samodzielna operacja binarna, która zależy od obu jego argumentów. Kompozycja operacji samodwuliniowych jest operacją samodwójną. Na przykład, jeśli f ( x , y , z ) = ( xy ) ∨ ( yz ) ∨ ( zx ) , wtedy f ( f ( x , y , z ), x , t ) jest jaźnią -podwójne działanie czterech argumentów x , y , z , t .

Zasada dualności może być wyjaśniona z perspektywy teorii grup przez fakt, że istnieją dokładnie cztery funkcje, które są odwzorowaniami jeden do jednego ( automorfizmami ) zbioru wielomianów Boole'a z powrotem do siebie samego: funkcja tożsamości, funkcja dopełnienia, funkcja dualna i funkcja kontradualna (uzupełniona dualność). Te cztery funkcje tworzą grupę w ramach składu funkcji , izomorficzną z czterogrupą Kleina , działającą na zbiorze wielomianów Boole'a. Walter Gottschalk zauważył, że w konsekwencji bardziej odpowiednią nazwą dla tego zjawiska byłaby zasada (lub kwadrat ) czwartorzędności .

Reprezentacje schematyczne

Diagramy Venna

Venna można stosować jako reprezentacji logicznego operacji z wykorzystaniem zacienione obszary nakładających się na siebie. Dla każdej zmiennej istnieje jeden region, wszystkie okrągłe w przykładach. Wewnętrzna i zewnętrzna strona obszaru x odpowiada odpowiednio wartościom 1 (prawda) i 0 (fałsz) dla zmiennej x . Cieniowanie wskazuje wartość operacji dla każdej kombinacji regionów, przy czym ciemnym oznacza 1 i jasnym 0 (niektórzy autorzy stosują odwrotną konwencję).

Te trzy wykresy Venna na rysunku poniżej przedstawiają odpowiednio połączeniową xY , dysjunkcję xy i dopełnienie Kontakty x .

Rysunek 2. Diagramy Venna dla koniunkcji, alternatywy i dopełnienia

Dla związku, obszar wewnątrz obu kół jest zaciemniona, aby wskazać, że Xr oznacza 1, gdy obie zmienne 1. Inne regiony po nieosłoniętych, aby wskazać, że Xr wynosi 0 dla pozostałych trzech kombinacji.

Drugi diagram przedstawia alternatywę xy przez zacienienie tych obszarów, które leżą wewnątrz jednego lub obu okręgów. Trzeci diagram przedstawia dopełnienie ¬ x przez zacienienie regionu nie znajdującego się wewnątrz okręgu.

Chociaż nie pokazaliśmy diagramów Venna dla stałych 0 i 1, są one trywialne, będąc odpowiednio białym i ciemnym pudełkiem, a żadne z nich nie zawiera koła. Moglibyśmy jednak umieścić okrąg dla x w tych polach, w którym to przypadku każde oznaczałoby funkcję jednego argumentu x , która zwraca tę samą wartość niezależnie od x , zwaną funkcją stałą. Jeśli chodzi o ich wyjścia, stałe i stałe funkcje są nie do odróżnienia; różnica polega na tym, że stała nie przyjmuje żadnych argumentów, co nazywa się operacją zerową lub nullarną , podczas gdy funkcja stała przyjmuje jeden argument, który ignoruje, i jest operacją jednoargumentową .

Diagramy Venna są pomocne w wizualizacji praw. Prawa przemienności dla ∧ i ∨ można zobaczyć na podstawie symetrii diagramów: operacja binarna, która nie była przemienna, nie miałaby diagramu symetrycznego, ponieważ zamiana x i y miałaby efekt odzwierciedlania diagramu w poziomie, a każda awaria przemienności miałaby następnie pojawiają się jako brak symetrii.

Idempotencja ∧ i ∨ można zwizualizować, przesuwając oba okręgi razem i zauważając, że zacieniony obszar staje się wtedy całym okręgiem, zarówno dla ∧, jak i ∨.

Aby zobaczyć pierwsze prawo absorpcji, x ∧( xy ) = x , zacznij od diagramu pośrodku dla xy i zauważ, że część zacieniowanego obszaru wspólna z kołem x jest całością koła x . Dla drugiego prawa absorpcji, x ∨( xy ) = x , zacznij od lewego diagramu dla xy i zauważ, że zacienienie całego okręgu x powoduje zacienienie tylko okręgu x , ponieważ poprzednie cieniowanie było wewnątrz x krąg.

Podwójna negacja prawo widać uzupełniając cieniowanie w trzecim schemacie dla ¬ x , który odcieniach x okręgu.

Aby zwizualizować pierwsze prawo De Morgana, (¬ x )∧(¬ y ) = ¬( xy ), zacznij od środkowego diagramu dla xy i uzupełnij jego zacienienie tak, aby zacieniować tylko obszar poza oboma okręgami, co tak opisuje prawa strona prawa. Wynik jest taki sam, jak gdybyśmy zacieniowali obszar, który jest zarówno poza kołem x, jak i poza kołem y , tj. koniunkcja ich zewnętrznych części, co opisuje lewa strona prawa.

Drugie prawo De Morgana, (¬ x )∨(¬ y ) = ¬( xy ), działa w ten sam sposób z dwoma zamienionymi diagramami.

Pierwsze prawo dopełnienia, x ∧¬ x = 0, mówi, że wnętrze i zewnętrze okręgu x nie zachodzą na siebie. Drugie prawo dopełnienia, x ∨¬ x = 1, mówi, że wszystko jest wewnątrz lub na zewnątrz okręgu x .

Cyfrowe bramki logiczne

Logika cyfrowa to zastosowanie algebry Boole'a 0 i 1 do sprzętu elektronicznego składającego się z bramek logicznych połączonych w celu utworzenia schematu obwodu . Każda bramka realizuje operację logiczną i jest przedstawiona schematycznie za pomocą kształtu wskazującego operację. Kształty skojarzone z bramkami dla koniunkcji (bramki AND), alternatywy (bramki OR) i dopełnienia (falowniki) są następujące.

Od lewej do prawej: bramki AND , OR i NOT .

Linie po lewej stronie każdej bramki reprezentują przewody lub porty wejściowe . Wartość wejścia jest reprezentowana przez napięcie na przewodzie. W przypadku tak zwanej logiki „aktywny-wysoki” 0 jest reprezentowane przez napięcie bliskie zeru lub „uziemienie”, podczas gdy 1 jest reprezentowane przez napięcie zbliżone do napięcia zasilania; active-low odwraca to. Linia po prawej stronie każdej bramki reprezentuje port wyjściowy, który zwykle jest zgodny z tymi samymi konwencjami napięcia, co porty wejściowe.

Uzupełnienie jest realizowane z bramą inwerterową. Trójkąt oznacza operację, która po prostu kopiuje dane wejściowe do danych wyjściowych; małe kółko na wyjściu oznacza rzeczywistą inwersję uzupełniającą dane wejściowe. Konwencja umieszczenia takiego kółka na dowolnym porcie oznacza, że ​​sygnał przechodzący przez ten port jest uzupełniany po drodze, niezależnie od tego, czy jest to port wejściowy, czy wyjściowy.

Dwoisto Zasada lub prawa De Morgana , mogą być rozumiane jako twierdzenie, że uzupełnianie wszystkich trzech portów elementu I przekształca na albo bramy i vice versa, jak pokazano na figurze 4, poniżej. Uzupełnienie obu portów falownika pozostawia jednak działanie bez zmian.

DeMorganGates.GIF

Bardziej ogólnie można uzupełnić dowolny z ośmiu podzbiorów trzech portów bramki AND lub OR. Wynikające z tego szesnaście możliwości daje początek tylko ośmiu operacjom logicznym, a mianowicie tym, które w tabeli prawdy mają nieparzystą liczbę jedynek. Jest ich osiem, ponieważ „odd-bit-out” może wynosić 0 lub 1 i może zająć dowolną z czterech pozycji w tabeli prawdy. Istnieje szesnaście binarnych operacji logicznych, to musi pozostawić osiem operacji z parzystą liczbą jedynek w ich tabelach prawdy. Dwie z nich to stałe 0 i 1 (jako operacje binarne, które ignorują oba ich wejścia); cztery z nich są operacje, które zależne nontrivially dokładnie na jednym z ich dwóch wejść, a mianowicie x , y , Ź x , a Ź Y ; a pozostałe dwa są xY (XOR), a jej dopełnienie xy .

Algebry Boole'a

Termin „algebra” oznacza zarówno podmiot, czyli podmiot algebry , jak i przedmiot, czyli strukturę algebraiczną . Podczas gdy powyższe dotyczyło tematu algebry Boole'a, ta sekcja dotyczy obiektów matematycznych zwanych algebrami Boole'a, zdefiniowanych w pełnej ogólności jako dowolny model praw Boole'a. Rozpoczynamy od szczególnego przypadku pojęcia definiowalnego bez odwoływania się do praw, a mianowicie konkretnych algebr Boole'a, a następnie podajemy formalną definicję pojęcia ogólnego.

Konkretne algebry Boole'a

Betonu Boole'a lub ciało zbiorów jakikolwiek niepusty zbiór podzbiorów danego zbioru X zamknięte pod zestaw operacji jedności , przecięcia i uzupełnienie w stosunku do X .

(Na marginesie, historycznie sam X musiał być również niepusty, aby wykluczyć zdegenerowaną lub jednoelementową algebrę Boole'a, co jest jedynym wyjątkiem od reguły, że wszystkie algebry Boole'a spełniają te same równania, ponieważ algebra zdegenerowana spełnia każde równanie. Jednak to wykluczenie jest sprzeczne z preferowaną czysto równania definicją „algebry Boole'a", nie ma możliwości wykluczenia algebry jednoelementowej przy użyciu tylko równań — 0 1 nie liczy się, będąc równaniem zanegowanym. Dlatego współcześni autorzy dopuszczają degenerację Algebra Boole'a i niech X będzie puste.)

Przykład 1. zasilania ustawiony 2 X z X , składający się z wszystkich podgrup o X . Tutaj X może być dowolnym zbiorem: pustym, skończonym, nieskończonym, a nawet niepoliczalnym .

Przykład 2. Pusty zbiór i X . Ta dwuelementowa algebra pokazuje, że konkretna algebra Boole'a może być skończona, nawet jeśli składa się z podzbiorów zbioru nieskończonego. Można zauważyć, że każde pole podzbiorów X musi zawierać pusty zbiór i X . Stąd nie ma mniejszego przykładu, innego niż algebra zdegenerowana uzyskana przez przyjęcie X jako pustego, tak aby zbiór pusty i X pokrywały się.

Przykład 3. Zbiór skończonych i cofinite zbiorów liczb całkowitych, gdzie cofinite to zbiór pomijający tylko skończenie wiele liczb całkowitych. Jest to wyraźnie zamknięte pod dopełnieniem i jest zamknięte pod sumą, ponieważ suma zbioru koskończonego z dowolnym zbiorem jest skończona, podczas gdy suma dwóch zbiorów skończonych jest skończona. Przecięcie zachowuje się jak suma z zamienionymi słowami „skończone” i „cofinite”.

Przykład 4. W przypadku mniej oczywiste przykład punktu wykonany w przykładzie 2, za diagram Vienn'a utworzony przez n krzywe zamknięte partycjonowania ze schematem z 2 n regionów i pozwolić X jest (nieskończone) zbiór wszystkich punktów płaszczyzny nie na dowolna krzywa, ale gdzieś w obrębie diagramu. Wnętrze każdego regionu jest zatem nieskończonym podzbiorem X , a każdy punkt w X znajduje się dokładnie w jednym regionie. Następnie zbiór wszystkich 2 2 n możliwych sum regionów (włączając zbiór pusty otrzymany jako suma zbioru pustego regionów i X otrzymany jako suma wszystkich 2 n regionów) jest zamykany pod sumą, przecięciem i uzupełnieniem względem X i dlatego tworzy konkretną algebrę Boole'a. Znowu mamy skończenie wiele podzbiorów nieskończonego zbioru tworzących konkretną algebrę Boole'a, z Przykładem 2 powstałym jako przypadek n = 0 braku krzywych.

Podzbiory jako wektory bitowe

Podzbiór Y z X może być identyfikowane z indeksowanych rodziny bitów ze zbioru wskaźnik X , z nieco indeksowane xX jako 0 lub 1 zależnie od tego, czy xY . (Jest to tak zwane pojęcie funkcji charakterystycznej podzbioru.) Na przykład, 32-bitowe słowo komputerowe składa się z 32 bitów indeksowanych przez zbiór {0,1,2,...,31}, z 0 i 31 indeksowanie odpowiednio bitów niskiego i wysokiego rzędu. Dla mniejszego przykładu, jeśli X = { a, b, c } gdzie a, b, c są postrzegane jako pozycje bitowe w tej kolejności od lewej do prawej, osiem podzbiorów {}, { c }, { b }, { b , c }, { a }, { a , c }, { a , b } i { a , b , c } z X można zidentyfikować za pomocą odpowiednich wektorów bitowych 000, 001, 010, 011, 100, 101, 110 i 111. Wektory bitowe indeksowane zbiorem liczb naturalnych są nieskończonymi ciągami bitów, podczas gdy te indeksowane liczbami rzeczywistymi w przedziale jednostkowym [0,1] są upakowane zbyt gęsto, aby móc pisać konwencjonalnie, ale zdefiniowane indeksowane rodziny (wyobraźmy sobie kolorowanie każdego punktu przedziału [0,1] niezależnie od koloru czarnego lub białego; czarne punkty tworzą wtedy dowolny podzbiór [0,1]).

Z tego bitu wektora punktu widzenia konkretny Boole'a można zdefiniować równoważnie jako niepusty zestaw bitowych wektorów wszystkie o tej samej długości (bardziej ogólnie, indeksowanej samym zestawie) i zamknięty w tych operacjach nieco wektora bitowego ∧, ∨ i ¬, jak w 1010∧0110 = 0010, 1010∨0110 = 1110 i ¬1010 = 0101, realizacje wektorów bitowych odpowiednio przecięcia, sumy i dopełnienia.

Prototypowa algebra Boole'a

Zbiór {0,1} i jego operacje boolowskie, jak potraktowano powyżej, można rozumieć jako szczególny przypadek wektorów bitowych o długości jeden, które poprzez identyfikację wektorów bitowych z podzbiorami mogą być również rozumiane jako dwa podzbiory jednoelementowego ustawić. Nazywamy to prototypową algebrą Boole'a, uzasadnioną następującą obserwacją.

Prawa spełniane przez wszystkie niezdegenerowane konkretne algebry Boole'a pokrywają się z prawami spełnianymi przez prototypową algebrę Boole'a.

Obserwację tę można łatwo udowodnić w następujący sposób. Z pewnością każde prawo spełnione przez wszystkie konkretne algebry Boole'a jest spełnione przez prawo prototypowe, ponieważ jest ono konkretne. I odwrotnie, każde prawo, które zawodzi w przypadku jakiejś konkretnej algebry Boole'a, musiało zawieść na określonej pozycji bitowej, w którym to przypadku ta pozycja sama w sobie dostarcza jednobitowego kontrprzykładu dla tego prawa. Niedegeneracja zapewnia istnienie co najmniej jednej pozycji bitowej, ponieważ istnieje tylko jeden pusty wektor bitowy.

Ostateczny cel kolejnego rozdziału można rozumieć jako wyeliminowanie „betonu” z powyższej obserwacji. Cel ten osiągniemy jednak poprzez zaskakująco silniejszą obserwację, że aż do izomorfizmu wszystkie algebry Boole'a są konkretne.

Algebry Boole'a: definicja

Wszystkie algebry Boole'a, które widzieliśmy do tej pory, były konkretne, składały się z wektorów bitowych lub równoważnie z podzbiorów jakiegoś zbioru. Taka algebra Boole'a składa się ze zbioru i operacji na tym zbiorze, co do których można wykazać, że spełniają prawa algebry Boole'a.

Zamiast pokazywać, że prawa Boole'a są spełnione, możemy zamiast tego postulować zbiór X , dwie operacje binarne na X i jedną operację jednoargumentową i wymagać, aby te operacje spełniały prawa algebry Boole'a. Elementy X nie muszą być wektorami bitów ani podzbiorami, ale mogą być w ogóle czymkolwiek. Prowadzi to do bardziej ogólnej abstrakcyjnej definicji.

Boole'a jest dowolny zestaw z operacji binarnych ∧ i ∨ i jednoskładnikowa operacja ¬ niej spełniającą logicznych przepisów.

Dla celów tej definicji nie ma znaczenia, w jaki sposób operacje doszły do ​​spełnienia praw, czy to na podstawie fiat czy dowodu. Wszystkie konkretne algebry Boole'a spełniają prawa (raczej przez dowód niż fiat), z których każda konkretna algebra Boole'a jest algebrą Boole'a według naszych definicji. Ta aksjomatyczna definicja algebry Boole'a jako zbioru i pewnych operacji spełniających pewne prawa lub aksjomaty przez fiat jest całkowicie analogiczna do abstrakcyjnych definicji grupy , pierścienia , pola itp. charakterystycznych dla algebry nowoczesnej lub abstrakcyjnej .

Biorąc pod uwagę jakąkolwiek pełną aksjomatyzację algebry Boole'a, taką jak aksjomaty dla uzupełnionej sieci rozdzielczej , wystarczającym warunkiem, aby tego rodzaju struktura algebraiczna spełniała wszystkie prawa Boole'a jest to, że spełnia ona tylko te aksjomaty. Poniższa definicja jest zatem równoważną definicją.

Boole'a jest uzupełniona rozdzielcze kraty.

Rozdział o aksjomatyzacji wymienia inne aksjomatyzacje, z których każda może być oparta na równoważnej definicji.

Reprezentatywne algebry Boole'a

Chociaż każda konkretna algebra Boole'a jest algebrą Boole'a, nie każda algebra Boole'a musi być konkretna. Niech n będzie bezkwadratową dodatnią liczbą całkowitą, niepodzielną przez kwadrat liczby całkowitej, na przykład 30, ale nie 12. Działania największego wspólnego dzielnika , najmniejszej wspólnej wielokrotności i dzielenia przez n (czyli ¬ x = n / x ), można wykazać, że spełniają wszystkie prawa Boole'a, gdy ich argumenty przekraczają dodatnie dzielniki n . Stąd te dzielniki tworzą algebrę Boole'a. Te dzielniki nie są podzbiorami zbioru, czyniąc dzielniki n Boolean algebra, który nie jest beton zgodnie z naszymi definicjami.

Jeśli jednak przedstawimy każdy dzielnik liczby n przez zbiór jego czynników pierwszych, stwierdzimy, że ta niekonkretna algebra Boole'a jest izomorficzna z konkretną algebrą Boole'a składającą się ze wszystkich zbiorów czynników pierwszych n , z sumą odpowiadającą najmniejszej wspólnej wielokrotności, przecięcie do największego wspólnego dzielnika i uzupełnienie do podziału na n . Tak więc ten przykład, choć nie jest technicznie konkretny, jest przynajmniej „moralnie” konkretny poprzez tę reprezentację, zwaną izomorfizmem . Ten przykład jest przykładem następującego pojęcia.

Algebra Boole'a nazywana jest reprezentowalną, gdy jest izomorficzna z konkretną algebrą Boole'a.

Na kolejne oczywiste pytanie odpowiada się twierdząco w następujący sposób.

Każda algebra Boole'a jest reprezentowalna.

Oznacza to, że aż do izomorfizmu abstrakcyjne i konkretne algebry Boole'a są tym samym. Ten dość nietrywialny wynik zależy od Boole'a pierwszego idealnego twierdzenia , zasady wyboru nieco słabszej niż aksjomat wyboru , i jest omówiony bardziej szczegółowo w artykule Twierdzenie Stone'a o reprezentacji dla algebr Boole'a . Ta silna zależność implikuje słabszy wynik, wzmacniając obserwację w poprzednim podrozdziale do następującej łatwej konsekwencji reprezentowalności.

Prawa spełnione przez wszystkie algebry Boole'a pokrywają się z prawami spełnianymi przez prototypową algebrę Boole'a.

Jest słabszy w tym sensie, że sam w sobie nie implikuje reprezentowalności. Algebry Boole'a są tu szczególne, na przykład algebra relacji jest algebrą Boole'a z dodatkową strukturą, ale nie jest tak, że każda algebra relacji jest reprezentowalna w sensie właściwym dla algebr relacji.

Aksjomatyzowanie algebry Boole'a

Powyższa definicja abstrakcyjnej algebry Boole'a jako zbioru i operacji spełniających „prawa Boole'a” nasuwa pytanie, czym są te prawa? Prostą odpowiedzią są „wszystkie prawa Boole'a”, które można zdefiniować jako wszystkie równania, które dotyczą algebry Boole'a 0 i 1. Ponieważ takich praw jest nieskończenie wiele, w praktyce nie jest to strasznie zadowalająca odpowiedź, prowadząca do następne pytanie: czy wystarczy wymagać, aby obowiązywała tylko skończona liczba praw?

W przypadku algebr Boole'a odpowiedź brzmi tak. W szczególności wystarcza skończenie wiele równań, które wymieniliśmy powyżej. Mówimy, że algebra Boole'a jest skończenie aksjomatyzowalna lub skończenie oparta.

Czy tę listę można jeszcze skrócić? Znowu odpowiedź brzmi tak. Po pierwsze, niektóre z powyższych praw są implikowane przez inne. Wystarczający podzbiór powyższych praw składa się z par praw asocjacji, przemienności i absorpcji, rozdzielności ∧ przez ∨ (lub innego prawa rozdzielności — jedno wystarczy) oraz dwóch praw dopełnienia. W rzeczywistości jest to tradycyjna aksjomatyzacja algebry Boole'a jako uzupełnionej sieci rozdzielczej .

Wprowadzenie dodatkowych przepisów niewymienionych powyżej umożliwia dalsze skrócenie listy; na przykład, z pionową kreską reprezentującą operację pociągnięcia Sheffera , pojedynczy aksjomat jest wystarczający do całkowitej aksjomatyzacji algebry Boole'a. Możliwe jest również znalezienie dłuższych pojedynczych aksjomatów przy użyciu bardziej konwencjonalnych operacji; zobacz Minimalne aksjomaty dla algebry Boole'a .

Logika zdań

Logika zdań to system logiczny ściśle związany z algebrą Boole'a. Wiele pojęć składniowych algebry Boole'a przechodzi do logiki zdań z niewielkimi zmianami w notacji i terminologii, podczas gdy semantyka logiki zdań jest definiowana za pomocą algebr Boole'a w taki sposób, że tautologie (twierdzenia) logiki zdań odpowiadają twierdzeniom równań algebry Boole'a .

Syntaktycznie każdy termin boolowski odpowiada zdaniowej formule logiki zdań. W tym tłumaczeniu między algebrą Boole'a a logiką zdań zmienne boolowskie x,y ... stają się zmiennymi zdaniowymi (lub atomami ) P,Q ,..., wyrażenia boolowskie, takie jak xy stają się formułami zdań PQ , 0 stają się fałszywe lub , a 1 staje się prawdziwe lub T . Przy odwoływaniu się do zdań generycznych wygodnie jest używać greckich liter Φ, Ψ,... jako metazmiennych (zmiennych poza językiem rachunku zdań, używanym przy mówieniu o rachunku zdań) do oznaczania zdań.

Semantyka logiki zdań opiera się na przypisaniu prawdy . Istotną ideą przypisania prawdziwości jest to, że zmienne zdaniowe są odwzorowywane na elementy ustalonej algebry Boole'a, a następnie wartość prawdziwości formuły zdaniowej używającej tych liter jest elementem algebry Boole'a, który jest uzyskiwany przez obliczenie wartości Wyrażenie logiczne odpowiadające wzorowi. W semantyce klasycznej używa się tylko dwuelementowej algebry Boole'a, podczas gdy w semantyce o wartościach Boole'a brane są pod uwagę arbitralne algebry Boole'a. Tautology jest propositional formułę, która jest przypisana wartość logiczną 1 przez każdego zadania logicznej jego zmiennych propozycjonalnych do dowolnego logicznego Algebra (lub, równoważnie, co prawda przyporządkowanie do elementu logicznego dwa Algebra).

Ta semantyka umożliwia translację między tautologiami logiki zdań a twierdzeniami równaniami algebry Boole'a. Każdą tautologię Φ logiki zdań można wyrazić jako równanie Boole'a Φ = 1, które będzie twierdzeniem algebry Boole'a. Odwrotnie, każde twierdzenie Φ = Ψ algebry Boole'a odpowiada tautologiem (Φ∨¬Ψ) ∧ (¬Φ∨Ψ) i (Φ∧Ψ) ∨ (¬Φ∧¬Ψ). Jeśli → jest w języku, te ostatnie tautologie można również zapisać jako (Φ→Ψ) ∧ (Ψ→Φ) lub jako dwa oddzielne twierdzenia Φ→Ψ i Ψ→Φ; jeśli ≡ jest dostępne, można zastosować pojedynczą tautologię Φ ≡ Ψ.

Aplikacje

Jednym z motywujących zastosowań rachunku zdań jest analiza zdań i argumentów dedukcyjnych w języku naturalnym. Podczas gdy zdanie „jeżeli x = 3 to x +1 = 4” zależy od znaczeń takich symboli jak + i 1, zdanie „jeżeli x = 3 to x = 3” nie; jest to prawdziwe jedynie ze względu na swoją strukturę i pozostaje prawdziwe niezależnie od tego, czy „ x = 3” zostanie zastąpione przez „ x = 4”, czy „księżyc jest zrobiony z zielonego sera”. Ogólną lub abstrakcyjną formą tej tautologii jest „jeśli P to P ” lub w języku algebry Boole'a „ PP ”.

Wymiana P przez x = 3 lub każdej innej propozycji nazywa instancji z P tą propozycją. Wynik utworzenia P w abstrakcyjnym zdaniu nazywamy instancją zdania. Zatem „ x = 3 → x = 3” jest tautologią z racji bycia instancją abstrakcyjnej tautologii „ PP ”. Wszystkie wystąpienia instancjonowanej zmiennej muszą być tworzone z tą samą propozycją, aby uniknąć takich nonsensów jak Px = 3 lub x = 3 → x = 4.

Rachunek zdań ogranicza uwagę do zdań abstrakcyjnych, zbudowanych ze zmiennych zdań za pomocą operacji logicznych. Tworzenie instancji jest nadal możliwe w ramach rachunku zdań, ale tylko poprzez tworzenie instancji zmiennych zdaniowych przez zdania abstrakcyjne, takie jak tworzenie instancji Q przez QP w P →( QP ), aby otrzymać instancję P →(( QP )→ P ).

(Dostępność konkretyzacji jako części mechanizmu rachunku zdań pozwala uniknąć konieczności stosowania metazmiennych w języku rachunku zdań, ponieważ zwykłe zmienne zdań mogą być rozpatrywane w tym języku, aby oznaczać dowolne zdania. Same metazmienne są poza zasięgiem tworzenia instancji, nie będąc częścią języka rachunku zdań, ale raczej częścią tego samego języka, aby mówić o tym, w którym to zdanie jest napisane, gdzie musimy być w stanie odróżnić zmienne zdaniowe i ich instancje jako odrębne byty składniowe).

Systemy dedukcyjne dla logiki zdań

Aksjomatyzacja rachunku zdań to zbiór tautologii zwanych aksjomatami i jedna lub więcej reguł wnioskowania do tworzenia nowych tautologii ze starych. Dowód w aksjomatykę A jest skończoną sekwencję niepusty zdań, z których każdy jest albo wystąpienie aksjomatowi A lub następuje po jakimś reguły A z propozycji występujących wcześniej w dowodzie (a tym samym uniemożliwiając błędnego koła). Ostatnie twierdzenie to twierdzenie udowodnione dowodem. Każdy niepusty początkowy segment dowodu jest sam w sobie dowodem, stąd każde twierdzenie w dowodzie samo jest twierdzeniem. Dzana jest dźwięk , kiedy każdy twierdzenie jest tautologią, a pełna , kiedy każda tautologia jest twierdzeniem.

Rachunek sekwencyjny

Rachunek zdań jest powszechnie zorganizowany jako system Hilberta , którego działania są tylko operacjami algebry Boole'a i których twierdzenia są tautologiami boolowskimi, te terminy boolowskie równe stałej boolowskiej 1. Inną formą jest rachunek sekwencyjny , który ma dwa rodzaje zdań jak w zwykłym rachunku zdań i par list zdań zwanych sekwencjami , takich jak AB , AC ,... A , BC ,.... Dwie połowy ciągu nazywamy odpowiednio poprzednikiem i następnikiem. Zwyczajowa metazmienna oznaczająca poprzednika lub jego część to Γ, a dla następnika Δ; zatem Γ, A Δ oznaczałoby sekwen, którego następcą jest lista Δ i poprzednikiem jest lista Γ z dodatkowym zdaniem A dołączonym po nim. Poprzednik jest interpretowany jako koniunkcja jego zdań, następnik jako alternatywa jego zdań, a sama sekwencja jako pociąganie następnika przez poprzednik.

Entailment różni się od implikacji tym, że podczas gdy to drugie jest operacją binarną , która zwraca wartość w algebrze Boole'a, to pierwsze jest relacją binarną, która albo zachodzi, albo nie. W tym sensie implikacja jest zewnętrzną formą implikacji, to znaczy zewnętrzną w stosunku do algebry Boole'a, myślącą o czytelniku sekwencji jako również zewnętrznym, interpretującym i porównującym poprzedniki i następniki w jakiejś algebrze Boole'a. Naturalna interpretacja jest jako ≤ w częściowym porządku algebry Boole'a zdefiniowanej przez xy tylko wtedy, gdy xy = y . Ta umiejętność mieszania implikacji zewnętrznej i wewnętrznej → w jednej logice jest jedną z zasadniczych różnic między rachunkiem sekwencyjnym a rachunkiem zdań.

Aplikacje

Algebra Boole'a jako rachunek dwóch wartości jest podstawą obwodów komputerowych, programowania komputerowego i logiki matematycznej, a także jest wykorzystywana w innych dziedzinach matematyki, takich jak teoria mnogości i statystyka.

Komputery

Na początku XX wieku kilku inżynierów elektryków intuicyjnie rozpoznało, że algebra Boole'a jest analogiczna do zachowania pewnych typów obwodów elektrycznych. Claude Shannon formalnie udowodnił, że takie zachowanie było logicznie równoważne z algebrą Boole'a w swojej pracy magisterskiej z 1937 roku pt. „ A Symbolic Analysis of Relay and Switching Circuits” .

Obecnie wszystkie nowoczesne komputery ogólnego przeznaczenia wykonują swoje funkcje za pomocą dwuwartościowej logiki logicznej; to znaczy ich obwody elektryczne są fizyczną manifestacją dwuwartościowej logiki Boole'a. Osiągają to na różne sposoby: jako napięcia na przewodach w szybkich obwodach i pojemnościowych urządzeniach pamięciowych, jako orientacje domeny magnetycznej w ferromagnetycznych urządzeniach pamięciowych, jako otwory w kartach dziurkowanych lub taśmie papierowej i tak dalej. (Niektóre wczesne komputery wykorzystywały obwody lub mechanizmy dziesiętne zamiast dwuwartościowych obwodów logicznych.)

Oczywiście możliwe jest zakodowanie więcej niż dwóch symboli w dowolnym medium. Na przykład, można użyć odpowiednio 0, 1, 2 i 3 V do zakodowania czterosymbolowego alfabetu na drucie lub dziurek o różnych rozmiarach w karcie dziurkowanej. W praktyce ciasne ograniczenia związane z dużą prędkością, małym rozmiarem i małą mocą sprawiają, że hałas jest głównym czynnikiem. To sprawia, że ​​trudno jest odróżnić symbole, gdy istnieje kilka możliwych symboli, które mogą wystąpić w jednym miejscu. Zamiast próbować rozróżniać cztery napięcia na jednym przewodzie, projektanci cyfrowi zdecydowali się na dwa napięcia na przewód, wysokie i niskie.

Komputery używają dwuwartościowych obwodów logicznych z powyższych powodów. Najpopularniejsze architektury komputerowe używają uporządkowanych sekwencji wartości logicznych, zwanych bitami, o wartościach 32 lub 64, np. 01101000110101100101010101001011. Podczas programowania w kodzie maszynowym , języku asemblerowym i niektórych innych językach programowania, programiści pracują z niskopoziomową strukturą cyfrową rejestry danych . Rejestry te działają na napięciach, gdzie zero woltów reprezentuje Boolean 0, a napięcie odniesienia (często +5 V, +3,3 V, +1,8 V) reprezentuje Boolean 1. Takie języki obsługują zarówno operacje numeryczne, jak i operacje logiczne. W tym kontekście „numeryczny” oznacza, że ​​komputer traktuje sekwencje bitów jako liczby binarne (podstawowe dwie liczby) i wykonuje operacje arytmetyczne, takie jak dodawanie, odejmowanie, mnożenie lub dzielenie. „Logiczny” odnosi się do logicznych operacji logicznych alternatywy, koniunkcji i negacji między dwiema sekwencjami bitów, w których każdy bit w jednej sekwencji jest po prostu porównywany z jego odpowiednikiem w drugiej sekwencji. Programiści mają zatem możliwość pracy i stosowania reguł algebry numerycznej lub algebry Boole'a w razie potrzeby. Podstawową cechą odróżniającą te rodziny operacji jest istnienie operacji przenoszenia w pierwszej, ale nie w drugiej.

Logika dwuwartościowa

Inne obszary, w których dwie wartości są dobrym wyborem, to prawo i matematyka. W codziennej swobodnej rozmowie dopuszczalne są zróżnicowane lub złożone odpowiedzi, takie jak „może” lub „tylko w weekend”. W bardziej skoncentrowanych sytuacjach, takich jak sąd lub matematyka oparta na twierdzeniach, uważa się jednak, że korzystne jest sformułowanie pytań tak, aby przyznać prostą odpowiedź tak lub nie – czy oskarżony jest winny, czy nie, czy twierdzenie jest prawdziwe czy fałszywe — i zabronić jakiejkolwiek innej odpowiedzi. Bez względu na to, jak bardzo może to okazać się dla respondenta w praktyce kaftanem bezpieczeństwa, zasada prostego pytania tak-nie stała się centralną cechą zarówno logiki sądowej, jak i matematycznej, czyniąc logikę dwuwartościową samodzielną organizacją i badaniem.

Centralną koncepcją teorii mnogości jest członkostwo. Teraz organizacja może zezwalać na wiele stopni członkostwa, takich jak nowicjusz, współpracownik i pełny. W zestawach jednak element jest albo na wejściu, albo na zewnątrz. Kandydaci do członkostwa w zbiorze działają tak samo jak przewody w komputerze cyfrowym: każdy kandydat jest albo członkiem, albo nie-członkiem, tak jak każdy przewód jest albo wysoki, albo niski.

Algebra, będąca podstawowym narzędziem w każdej dziedzinie podlegającej obróbce matematycznej, łączy te rozważania, tworząc algebrę dwóch wartości o fundamentalnym znaczeniu dla sprzętu komputerowego, logiki matematycznej i teorii mnogości.

Logika dwuwartościowa może zostać rozszerzona na logikę wielowartościową , w szczególności przez zastąpienie domeny Boole'a {0, 1} przedziałem jednostkowym [0,1], w którym to przypadku zamiast przyjmowania tylko wartości 0 lub 1, dowolnej wartości między i w tym 0 i 1 można założyć. Algebraicznie, negacja (NOT) jest zastąpiona przez 1 −  x , koniunkcja (AND) jest zastąpiona przez mnożenie ( ), a alternatywa (OR) jest zdefiniowana przez prawo De Morgana . Interpretacja tych wartości jako logicznej prawdy daje logikę wielowartościową, która stanowi podstawę logiki rozmytej i logiki probabilistycznej . W tych interpretacjach wartość jest interpretowana jako „stopień” prawdziwości – w jakim stopniu zdanie jest prawdziwe lub prawdopodobieństwo, że zdanie jest prawdziwe.

Operacje logiczne

Pierwotnym zastosowaniem operacji Boolean była logika matematyczna , w której łączy się wartości logiczne , prawdziwe lub fałszywe, poszczególnych formuł.

Język naturalny

Języki naturalne, takie jak angielski, zawierają słowa dla kilku operacji logicznych, w szczególności koniunkcji ( i ), alternatywy ( lub ), negacji ( nie ) i implikacji ( implikuje ). Ale nie jest synonimem i nie . W przypadku połączenia twierdzeń sytuacyjnych, takich jak „blok jest na stole” i „koty piją mleko”, które naiwnie są albo prawdziwe, albo fałszywe, znaczenia tych spójników logicznych często mają znaczenie swoich logicznych odpowiedników. Jednak przy opisach zachowań typu "Jim przeszedł przez drzwi", zaczyna się zauważać różnice takie jak brak przemienności, np. połączenie "Jim otworzył drzwi" z "Jim przeszedł przez drzwi" w tej kolejności jest nie jest równoznaczny z ich koniunkcją w innym porządku, ponieważ i zwykle oznacza a następnie w takich przypadkach. Pytania mogą być podobne: kolejność „Czy niebo jest niebieskie i dlaczego niebo jest niebieskie?” ma więcej sensu niż odwrotna kolejność. Łączne polecenia dotyczące zachowania są jak zapewnienia behawioralne, jak ubieranie się i chodzenie do szkoły . Dysjunktywny polecenia takie miłość mnie lub zostaw mnie lub ryby lub wyciąć przynęty mają tendencję do być asymetryczne przez implikację, że jedna alternatywa jest mniej korzystne. Rzeczowniki zrośnięte, takie jak herbata i mleko, ogólnie opisują agregację jak w przypadku połączenia zbiorowego, podczas gdy herbata lub mleko to wybór. Jednak kontekst może odwrócić te zmysły, ponieważ w Twoich wyborach jest kawa i herbata, co zwykle oznacza to samo, co wybór kawy lub herbaty (alternatywy). Podwójna negacja, jak w „Nie lubię mleka” rzadko oznacza dosłownie „lubię mleko”, ale raczej oznacza pewien rodzaj zabezpieczenia, jakby sugerował, że istnieje trzecia możliwość. „Not not P” może być luźno interpretowane jako „na pewno P” i chociaż P z konieczności implikuje „not not P ”, odwrotność jest podejrzana w języku angielskim, podobnie jak w przypadku logiki intuicjonistycznej . Ze względu na wysoce idiosynkratyczne użycie spójników w językach naturalnych, algebry Boole'a nie można uznać za niezawodny sposób ich interpretacji.

Logika cyfrowa

Operacje logiczne są używane w logice cyfrowej do łączenia bitów przenoszonych na poszczególnych przewodach, tym samym interpretując je na {0,1}. Gdy wektor o n identycznych bramkach binarnych jest używany do łączenia dwóch wektorów bitowych, każdy z n bitów, poszczególne operacje bitowe można rozumieć zbiorczo jako pojedynczą operację na wartościach z algebry Boole'a z 2 n elementami.

Naiwna teoria mnogości

Naiwna teoria zbiorów interpretuje operacje Boole'a jako działanie na podzbiorach danego zbioru X . Jak widzieliśmy wcześniej, to zachowanie dokładnie odpowiada współrzędnościowym kombinacjom wektorów bitowych, z połączeniem dwóch zestawów odpowiadającym alternatywie dwóch wektorów bitowych i tak dalej.

Karty wideo

256-elementowa wolna algebra Boole'a na trzech generatorach jest wdrażana na ekranach komputerowych opartych na grafice rastrowej , które używają bit blit do manipulowania całymi regionami składającymi się z pikseli , opierając się na operacjach Boole'a w celu określenia, jak region źródłowy powinien być połączony z miejscem docelowym, zazwyczaj z pomocą trzeciego obszaru zwanego maską . Nowoczesne karty graficzne oferują  w tym celu wszystkie 2 2 3 = 256 operacji trójskładnikowych, przy czym wybór operacji jest parametrem jednobajtowym (8-bitowym). Stałe SRC = 0xaa lub 10101010, DST = 0xcc lub 11001100 oraz MSK = 0xf0 lub 11110000 umożliwiają zapisywanie operacji logicznych, takich jak (SRC^DST)&MSK (co oznacza XOR źródło i cel, a następnie AND wynik z maską) bezpośrednio jako stała oznaczająca bajt wyliczony w czasie kompilacji, 0x60 w przykładzie (SRC^DST)&MSK, 0x66 jeśli tylko SRC^DST itd. W czasie wykonywania karta graficzna interpretuje bajt jako operację rastrową wskazaną przez oryginalne wyrażenie w jednolity sposób, który wymaga niezwykle małego sprzętu i który zajmuje czas całkowicie niezależny od złożoności wyrażenia.

Modelowanie i CAD

Systemy modelowania bryłowego do komputerowego wspomagania projektowania oferują różnorodne metody budowania obiektów z innych obiektów, a jedną z nich jest łączenie operacji logicznych. W ten sposób przestrzeń, w której obiekty istnieje, jest rozumiane jako zbiór S z wokseli (trójwymiarowy analogiem pikseli w grafice dwuwymiarowej) i kształtach są określone w podgrupach S , dzięki czemu przedmioty do łączenia w zestawy za pomocą związku, przecięcie itp. Jednym z oczywistych zastosowań jest budowanie złożonego kształtu z prostych kształtów po prostu jako połączenie tych ostatnich. Innym zastosowaniem jest rzeźbienie rozumiane jako usuwanie materiału: wszelkie operacje szlifowania, frezowania, frezowania lub wiercenia, które można wykonać za pomocą maszyn fizycznych na materiałach fizycznych, można symulować na komputerze za pomocą operacji logicznej x  ∧ ¬ y lub x  −  y , które w teorii mnogości jest różnicą mnogości, usuń elementy y z elementów x . W ten sposób, mając dwa kształty, jeden do obróbki, a drugi materiał do usunięcia, wynik obróbki tego pierwszego w celu usunięcia drugiego jest opisany po prostu jako ich zadana różnica.

Wyszukiwania logiczne

Zapytania wyszukiwarek również wykorzystują logikę Boole'a. W przypadku tego zastosowania każda strona internetowa w Internecie może być uważana za „element” „zestawu”. W poniższych przykładach użyto składni obsługiwanej przez Google .

  • Podwójne cudzysłowy służą do łączenia słów oddzielonych spacjami w jedno wyszukiwane hasło.
  • Whitespace służy do określenia logicznego AND, ponieważ jest domyślnym operatorem do łączenia wyszukiwanych haseł:
"Search term 1" "Search term 2"
  • Słowo kluczowe OR służy do logicznego OR:
"Search term 1" OR "Search term 2"
  • Znak minus z przedrostkiem jest używany dla logicznego NIE:
"Search term 1" −"Search term 2"

Zobacz też

Bibliografia

Źródła

Dalsza lektura

  • J. Eldona Whitesitta (1995). Algebra Boole'a i jej zastosowania . Publikacje kurierskie Dover. Numer ISBN 978-0-486-68483-3. Odpowiednie wprowadzenie dla studentów w stosowanych dziedzinach.
  • Dwinger, Filip (1971). Wprowadzenie do algebr Boole'a . Würzburg: Physica Verlag.
  • Sikorski, Roman (1969). Algebry Boole'a (wyd. 3/e). Berlin: Springer-Verlag. Numer ISBN 978-0-387-04469-9.
  • Bocheński, Józef Maria (1959). Precis logiki matematycznej . Przetłumaczone z wydania francuskiego i niemieckiego przez Otto Birda. Dordrecht, Holandia Południowa: D. Reidel.

Perspektywa historyczna

Zewnętrzne linki