Algebra Boole'a - Polski Serwis Naukowy

Diagram Hassego dla algebry Boole'a podzbiorów zbioru trójelementowego

Algebra Boole'a – struktura algebraiczna stosowana w matematyce, informatyce teoretycznej oraz elektronice cyfrowej. Jej nazwa pochodzi od nazwiska angielskiego matematyka, filozofa i logika George'a Boole'a. Teoria algebr Boole'a jest działem matematyki na styku teorii porządków częściowych, algebry, logiki matematycznej i topologii.

Wielka Brytania (), Zjednoczone Królestwo Wielkiej Brytanii i Irlandii Północnej (ang. United Kingdom of Great Britain and Northern Ireland) – unitarne państwo wyspiarskie położone w Europie Zachodniej. W skład Wielkiej Brytanii wchodzą: Anglia, Walia i Szkocja położone na wyspie Wielka Brytania, Irlandia Północna leżąca w północnej części wyspy Irlandia. Guernsey, Jersey i Wyspa Man, posiadają odrębny status dependencji Korony brytyjskiej i nie wchodzą w skład Zjednoczonego Królestwa.
Andrzej Stanisław Mostowski (ur. 1 listopada 1913 we Lwowie, zm. 22 sierpnia 1975 w Vancouver, Kanada) – polski matematyk zajmujący się głównie podstawami matematyki, przedstawiciel warszawskiej szkoły matematycznej.

Typowymi przykładami algebr Boole'a są: rodzina wszystkich podzbiorów ustalonego zbioru wraz działaniami na zbiorach jako operacjami algebry oraz dwuelementowa algebra wartości logicznych {0, 1} z działaniami koniunkcji, alternatywy i negacji.

Definicja

Algebra Boole'a to struktura algebraiczna ${\mathbb B}:=(B,\cup,\cap,\sim,0,1)$ , w której $\cup$ i $\cap$ są działaniami dwuargumentowymi, $\sim$ jest operacją jednoargumentową, a 0 i 1 są wyróżnionymi różnymi elementami zbioru $B\;$ , spełniająca następujące warunki dla wszystkich $a,b,c\in B$ :

Oznaczenia

Istnieją co najmniej trzy różne, szeroko rozpowszechnione tradycje oznaczeń w teorii algebr Boole'a. W definicji sformułowanej powyżej użyto symboli $\cup,\cap,\sim$ , ale w częstym użyciu są również $+,\cdot,-$ oraz $\lor,\land,\lnot$ . Symbole oznaczające operacje dwuczłonowe algebry Boole'a są prawie zawsze wprowadzane przez wybór jednej z par $(+,\cdot)$ , $(\lor,\land)$ albo $(\cup,\cap)$ . W oznaczeniach operacji jednoargumentowej algebry istnieje mniejsza konsekwencja i można się spotkać zarówno z symbolami $+,\cdot,\sim$ jak i $\lor,\land,{}^\prime$ .

Rachunek zdań to dział logiki matematycznej badający związki między zdaniami (zmiennymi zdaniowymi) lub funkcjami zdaniowymi utworzonymi za pomocą spójników zdaniowych ze zdań lub funkcji zdaniowych prostszych. Rachunek zdań określa sposoby stosowania spójników zdaniowych w poprawnym wnioskowaniu.
Podzbiór – pewna „część” danego zbioru, czyli dla danego zbioru, nazywanego nadzbiorem, zbiór składający się z pewnej liczby jego elementów, np. żadnego, jednego, wszystkich. Pierwszy przypadek nazywa się podzbiorem pustym, drugi – podzbiorem jednoelementowym lub singletonem, trzeci – podzbiorem niewłaściwym.

System oznaczeń przedstawiony powyżej (i dalej przyjmowany w tym artykule) jest używany np. w podręczniku Heleny Rasiowej.

W badaniach teoriomnogościowych aspektów algebr Boole'a przeważa tradycja używania oznaczeń $(+,\cdot,-)$ . Ten sam system został też wybrany za wiodący przez redaktorów monografii Handbook of Boolean Algebras.

Z kolei symbole $\wedge,\vee$ zgodne z oznaczeniami w teorii krat są częściej używane w kontekstach algebraicznych (i teoriokratowych).

prof. Kazimierz Kuratowski (ur. 2 lutego 1896 w Warszawie, zm. 18 czerwca 1980 w Warszawie), polski matematyk, jeden z czołowych przedstawicieli warszawskiej szkoły matematycznej.
Homomorfizm – funkcja odwzorowująca jedną algebrę ogólną (czyli strukturę algebraiczną taką jak grupa, pierścień czy przestrzeń wektorowa) w drugą, zachowująca przy tym odpowiadające sobie operacje. Jest to podstawowe narzędzie w badaniu i porównywaniu algebr.

Spotykane są też inne kombinacje tychże symboli lub wręcz inne symbole (na przykład & w miejsce $\cap$ , lub $a^\prime$ zamiast $\;\sim a$ ). W elektronice i informatyce często stosuje się OR, AND oraz NOT w miejsce $\cup$ , $\cap$ oraz $\sim$ .

Minimalna aksjomatyzacja

Powyższa (tradycyjna) definicja algebry Boole'a nie jest minimalna, np. nie jest konieczne wprowadzanie w niej symboli 0 i 1. Mogą one być konsekwencją aksjomatyki a nie niezbędną dla niej definicją. 0 można zastąpić przez $\sim (x \cup (\sim x))$ a 1 przez $(x \cup (\sim x))$ . Dzięki prawom de Morgana można też z aksjomatyki wyeliminować działanie $\cap$ lub $\cup$ . (W istocie wszystkie działania można tak naprawdę zastąpić jednym – dysjunkcją (NAND) lub binegacją (NOR)).

Topologia (gr. tópos – miejsce, okolica; lógos – słowo, nauka) – jeden z najważniejszych kierunków w matematyce współczesnej. Obiektem jej badań są te własności figur geometrycznych i brył, które nie ulegają zmianie nawet po radykalnym zdeformowaniu tych figur (a więc np. położenie i sąsiedztwo). Własności takie nazywa się własnościami topologicznymi figury.
Prawo podwójnej negacji albo prawo podwójnego zaprzeczenia – reguła rachunku zdań, która stwierdza, że zaprzeczenie negacji zdania jest tym samym zdaniem (bardziej formalnie: jest równoważne ze zdaniem wyjściowym).

Istnieją równoważne, ale oszczędniejsze definicje algebry Boole'a. Przykładowy układ niezależnych aksjomatów to:

$\cup\;$ jest przemienne,

$\cup\;$ jest łączne,

aksjomat Huntingtona: $\sim(\sim x \cup y)\; \cup \sim (\sim x\; \cup \sim y) = x$ .

Inny taki układ to:

$\cup\;$ jest przemienne

$\cup\;$ jest łączne

aksjomat Robbinsa: $\sim(\sim(x \cup y)\; \cup \sim(x\; \cup \sim y)) = x$

Istnieją też systemy z jednym aksjomatem.

Przykłady

Najprostsza algebra Boole'a ma tylko dwa elementy, 0 i 1, a operacje tej algebry są zdefiniowane przez następujące tabele działań:

Elektronika cyfrowa jest dziedziną elektroniki zajmującą się wytwarzaniem i przetwarzaniem sygnałów cyfrowych przy użyciu układów cyfrowych. Obecnie najczęściej stosowane są układy półprzewodnikowe TTL (ang. transistor-transistor logic) oraz CMOS (ang. complementary metal-oxide-semiconductor).
Relacja równoważności – zwrotna, symetryczna i przechodnia relacja dwuargumentowa określona na pewnym zbiorze utożsamiająca ze sobą w pewien sposób jego elementy, co ustanawia podział tego zbioru na rozłączne podzbiory według tej relacji. Podobnie każdy podział zbioru niesie ze sobą informację o pewnej relacji równoważności.

Algebra ta stanowi podstawę elektroniki cyfrowej.

Jeśli ${\mathcal F}$ jest ciałem podzbiorów zbioru $X$ , to $({\mathcal F},\cup,\cap,{}^\prime,\varnothing,X)$ jest algebrą Boole'a (gdzie ${}^\prime$ oznacza operację dopełnienia).

Niech ${\mathcal Z}$ będzie zbiorem zdań w rachunku zdań. Niech $\equiv$ będzie relacją dwuargumentową na zbiorze ${\mathcal Z}$ określoną jako: $\varphi\equiv\psi$ wtedy i tylko wtedy, gdy $\varphi\Leftrightarrow\psi$ jest tautologią rachunku zdań.

Można sprawdzić, że $\equiv$ jest relacją równoważności na zbiorze ${\mathcal Z}$ . Na zbiorze $X$ wszystkich klas abstrakcji $[\varphi]$ relacji $\equiv$ można wprowadzić operacje $\cup,\cap,\sim$ przez następujące formuły:

Dopełnienie zbioru – intuicyjnie, zbiór wszystkich elementów (pewnego ustalonego nadzbioru), które do danego zbioru nie należą. W niektórych pozycjach można spotkać się również z alternatywną nazwą uzupełnienie zbioru.
Teoria mnogości (również: teoria zbiorów) – dział matematyki a zarazem logiki matematycznej zapoczątkowany przez niemieckiego matematyka Georga Cantora pod koniec XIX wieku. Początkowo wzbudzała wiele kontrowersji, jednak wraz z postępem matematyki zaczęła ona pełnić rolę fundamentu, na którym opiera się większość matematycznych rozważań.

$[\varphi] \cup [\psi] := [\varphi\vee\psi]$ , $[\varphi] \cap [\psi] := [\varphi\wedge\psi]$ , $\sim[\varphi] := [\neg\varphi]$ .

W ten sposób otrzymuje się poprawnie zdefiniowane operacje na zbiorze $X$ (tzn. wynik nie zależy od wyboru reprezentantów klas abstrakcji), a $(X,\cup,\cap,\sim,[p\wedge\neg p],[p\vee\neg p])$ jest algebrą Boole'a. Algebra ta jest nazywana algebrą Lindenbauma-Tarskiego.

Algebry Lindenbauma-Tarskiego rozważa się również dla języków pierwszego rzędu. Niech ${\bold Z}$ będzie zbiorem zdań w ustalonym alfabecie $\tau$ i niech $T\subseteq {\bold Z}$ będzie niesprzeczną teorią w tym samym języku. Relację dwuargumentową $\equiv$ na zbiorze ${\bold Z}$ można wprowadzić przez określenie $\varphi\equiv\psi$ wtedy i tylko wtedy, gdy $T\vdash\varphi\Leftrightarrow\psi$ .

Wówczas $\equiv$ jest relacją równoważności na zbiorze ${\bold Z}$ . Podobnie jak wcześniej:

Aksjomat wyboru (ozn. AC) – jeden z aksjomatów teorii mnogości. Używa się różnych jego równoważnych sformułowań. Najczęściej spotykane jest następujące:
Porządek zupełny – własność porządków częściowych postulująca istnienie kresów. W literaturze matematycznej istnieje kilka definicji tego pojęcia różniących się szczegółami technicznymi zależnymi od kontekstu matematycznego.

$[\varphi] \cup [\psi] := [\varphi\vee\psi]$ , $[\varphi] \cap [\psi] := [\varphi\wedge\psi]$ , $\sim[\varphi] := [\neg\varphi]$ .

Można pokazać, że $({\bold Z}/\equiv,\cup,\cap,\sim,[\psi\wedge\neg \psi]_\equiv,[\psi\vee\neg \psi]_\equiv)$ jest algebrą Boole'a.

czytaj dalej: [2], [3]

w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)