Dwuelementowa algebra Boole'a - Two-element Boolean algebra

W matematyki i algebry abstrakcyjnej The dwuelementowa algebra Boole'a jest Boole'a którego bazowy zestaw (lub wszechświat lub nośnik ) B jest domeną Boolean . Elementy domeny boolowskiej mają zgodnie z konwencją 1 i 0, tak że B  = {0, 1}. Nazwa Paula Halmosa dla tej algebry „ 2 ” ma kilku zwolenników w literaturze i zostanie tutaj zastosowana.

Definicja

B jest zbiorem częściowo uporządkowanym, a elementy B są również jego granicami .

Działanie z Arity n jest mapowanie z B ^N do B . Algebra Boole'a składa się z dwóch operacji binarnych i jednoargumentowego uzupełnienia . Operacje binarne zostały nazwane i zapisane na różne sposoby. Tutaj są one nazywane „sumą” i „iloczynem” i oznaczone odpowiednio wrostkiem „+” i „∙”. Suma i iloczyn dojeżdżają i kojarzą , jak w zwykłej algebrze liczb rzeczywistych . Jeśli chodzi o kolejność operacji , decydujące są nawiasy, jeśli są obecne. W przeciwnym razie „∙” poprzedza „+”. Stąd A ∙ B + C jest analizowane jako (A ∙ B) + C, a nie jako A ∙ (B + C) . Uzupełnienie jest oznaczane przez napisanie nadpisania nad argumentem. Numeryczny analogiem dopełnieniem X jest 1 -  X . W języku algebry , algebry Boole'a jest algebra od typu . ${\ displaystyle \ langle B, +,., {\ overline {..}}, 1,0 \ rangle}$ ${\ Displaystyle \ langle 2,2,1,0,0 \ rangle}$

Każda zgodność jeden do jednego między {0,1} a { Prawda , Fałsz } daje klasyczną logikę dwuwartościową w postaci równania, z uzupełnieniem odczytywanym jako NIE . Jeśli 1 jest odczytywane jako Prawda , „+” jest odczytywane jako LUB , a „∙” jako ORAZ i odwrotnie, jeśli 1 jest odczytywane jako Fałsz . Te dwie operacje definiują semirowanie przemienne , znane jako semirowanie boolowskie .

Kilka podstawowych tożsamości

2 można uznać za uziemione w następującej trywialnej arytmetyce „boolowskiej”:

${\ Displaystyle {\ rozpocząć {wyrównane} i 1 + 1 = 1 + 0 = 0 + 1 = 1 \\ i 0 + 0 = 0 \\ i 0 \ cdot 0 = 0 \ cdot 1 = 1 \ cdot 0 = 0 \\ & 1 \ cdot 1 = 1 \\ & {\ overline {1}} = 0 \\ & {\ overline {0}} = 1 \ end {aligned}}}$

Zauważ, że:

• „+” i „∙” działają dokładnie tak samo, jak w arytmetyce numerycznej, z tą różnicą, że 1 + 1 = 1. „+” i „∙” wyprowadza się przez analogię z arytmetyki numerycznej; po prostu ustaw dowolną liczbę niezerową na 1.
• Zamiana 0 i 1 oraz „+” i „∙” zachowuje prawdę; na tym polega istota dwoistości przenikająca wszystkie algebry Boole'a.

Ta arytmetyka boolowska wystarcza do zweryfikowania dowolnego równania 2 , w tym aksjomatów, poprzez zbadanie każdego możliwego przypisania zer i jedynek do każdej zmiennej (patrz procedura decyzyjna ).

Teraz można zweryfikować następujące równania:

${\ Displaystyle {\ rozpocząć {wyrównane} i A + A = A \\ & A \ cdot A = A \\ & A + 0 = A \\ & A + 1 = 1 \\ & A \ cdot 0 = 0 \\ & {\ overline {\ overline {A}}} = A \ end {aligned}}}$

Każdy z „+” i „∙” rozdziela się po drugim:

• ${\ Displaystyle \ A \ cdot (B + C) = A \ cdot B + A \ cdot C;}$
• ${\ Displaystyle \ A + (B \ cdot C) = (A + B) \ cdot (A + C).}$

To „∙” rozkłada się na „+” jest zgodne z algebrą elementarną , ale nie „+” na „∙”. Z tego i innych powodów suma produktów (prowadząca do syntezy NAND ) jest częściej stosowana niż iloczyn sum (prowadzących do syntezy NOR ).

Każdy z „+” i „∙” można zdefiniować w kategoriach drugiego i uzupełnienia:

• ${\ Displaystyle A \ cdot B = {\ overline {{\ overline {A}} + {\ overline {B}}}}}$
• ${\ Displaystyle A + B = {\ overline {{\ overline {A}} \ cdot {\ overline {B}}}}.}$

Potrzebujemy tylko jednej operacji binarnej, a do jej oznaczenia wystarczy konkatenacja . Stąd konkatenacja i overbar wystarczą, aby zanotować 2 . Ten zapis jest również, że od Quine „s Boolean termin schematów . Pozwalając ( X ) oznacza uzupełnienie X i „()”, oznaczają 0 lub 1, otrzymuje się składni pierwotnego algebrze G. Spencer, Brown „a U. Postaci .

Podstawę do 2 to zestaw równań zwane aksjomaty , z których każdy z powyższych wzorów (i więcej) mogą być uzyskane. Istnieje wiele znanych baz dla wszystkich algebr Boole'a, a zatem dla 2 . Elegancka podstawa zapisana przy użyciu tylko konkatenacji i nadpisania to:

1. ${\ displaystyle \ ABC = BCA}$ (Dojazdy do pracy konkatenacyjnej, współpracownicy)
2. ${\ displaystyle {\ overline {A}} A = 1}$ ( 2 to uzupełniona krata, z górną granicą 1)
3. ${\ displaystyle \ A0 = A}$ (0 to dolna granica ).
4. ${\ displaystyle A {\ overline {AB}} = A {\ overline {B}}}$ ( 2 to krata rozdzielcza )

Gdzie konkatenacja = LUB, 1 = prawda i 0 = fałsz lub konkatenacja = ORAZ, 1 = fałsz i 0 = prawda. (overbar jest zaprzeczeniem w obu przypadkach.)

Jeśli 0 = 1, (1) - (3) są aksjomatami dla grupy abelowej .

(1) służy tylko do udowodnienia, że ​​konkatenacja dojeżdża i współpracuje. Najpierw załóżmy, że (1) współpracownicy z lewej lub prawej strony, a następnie udowodnij przemienność. Następnie udowodnij skojarzenie z innego kierunku. Łączność to po prostu skojarzenie z lewej i prawej strony połączone.

Ta podstawa umożliwia łatwe podejście do dowodu, zwanego „obliczeniem” w Prawach Formy , który przebiega przez uproszczenie wyrażeń do 0 lub 1, przywołanie aksjomatów (2) - (4), tożsamości elementarnych i prawa dystrybucyjnego. ${\ Displaystyle AA = A, {\ overline {\ overline {A}}} = A, 1 + A = 1}$

Metateoria

Twierdzenie De Morgana stwierdza, że ​​jeśli wykonamy następujące czynności, w podanej kolejności, do dowolnej funkcji boolowskiej :

• Uzupełnij każdą zmienną;
• Zamień operatory „+” i „∙” (uważając, aby dodać nawiasy, aby kolejność operacji pozostała taka sama);
• Uzupełnij wynik,

wynik jest logicznie równoważny z tym, od czego zacząłeś. Wielokrotne stosowanie twierdzenia De Morgana do części funkcji może posłużyć do sprowadzenia wszystkich uzupełnień do poszczególnych zmiennych.

Potężny i nietrywialny metateoremat stwierdza, że ​​każde twierdzenie 2 jest prawdziwe dla wszystkich algebr Boole'a. I odwrotnie, tożsamość, która zachodzi dla arbitralnej nietrywialnej algebry Boole'a, zachodzi również w 2 . Stąd cała matematyczna zawartość algebry Boole'a jest wychwycona przez 2 . To twierdzenie jest przydatne, ponieważ każde równanie w 2 można zweryfikować za pomocą procedury decyzyjnej . Logicy określają ten fakt jako „ 2 jest rozstrzygalne ”. Wszystkie znane procedury decyzyjne wymagają szeregu kroków, które są wykładniczą funkcją liczby zmiennych N występujących w równaniu do weryfikacji. Niezależnie od tego, istnieje procedurę decyzyjną której etapy są funkcja wielomianowa z N podlega P = NP hipotezy.

Zobacz też

• Algebra Boole'a
• Zbiór ograniczony
• Krata (zamówienie)
• Teoria porządku

Bibliografia

Dalsza lektura

We wczesnych latach ery komputerów opublikowano wiele podstawowych tekstów dotyczących algebry Boole'a. Być może najlepsza z nich i wciąż w druku to:

• Mendelson, Elliot, 1970. Zarys algebry Boole'a Schauma . McGraw – Hill.

Poniższe punkty pokazują, jak dwuelementowa algebra Boole'a jest matematycznie nietrywialna.

• Stanford Encyclopedia of Philosophy : „ Matematyka algebry Boole'a ” J. Donalda Monka.
• Burris, Stanley N. i HP Sankappanavar, HP, 1981. Kurs algebry uniwersalnej. Springer-Verlag. ISBN   3-540-90578-2 .