Algebra Boole'a jest to struktura matematyczna złożona z uniwersumUniwersum to pochodzące z łaciny określenie równoznaczne ze słowem wszechświat. W matematyce uniwersum danego modelu to klasa wszystkich jego elementów. Na przykład uniwersum modelu teorii mnogości stanowią wszystkie zbiory....
[click for more] X, trzech funkcji: działań binarnych +, * i działania unarnego ~ oraz wyróżnionych elementów 0, 1 spełniających następujące aksjomaty:

zarówno + jak i * są łączne i przemienne:
- x + y = y + x
- x * y = y * x
- (x + y) + z = x + (y + z)
- (x * y) * z = x * (y * z)
x + 0 = x
x * 1 = x
x + (~x) = 1
x * (~x) = 0
+ i * są rozdzielne względem siebie:
- x * (y + z) = (x * y) + (x * z)
- x + (y * z) = (x + y) * (x + z)
dwa działania ~ się znoszą: ~~x = x
prawa de Morgana
- ~(x * y) = (~x) + (~y)
- ~(x + y) = (~x) * (~y)

Operacje + i * można interpretować jako operacje odpowiednio brania maksimum i miniumum w odpowiednim porządku częściowym. Warto zwrócić uwagę, że w algebrze Boole'a operacja dodawania nie tworzy struktury grupy.

Przykłady algebr Boole'a

1. Algebra zbiorów. X jest w tym przypadku jakimś ciałem zbiorów. Działanie + jest to suma zbiorów, * - przekrój zbiorów, a ~ - dopełnienie. 0 to zbiór pusty, a 1 - cały zbiór X.

2. Rachunek zdań. X to w tym przypadku zbiór formuł logicznych, działanie * to koniunkcja, + - alternatywaAlternatywa to zdanie złożone mające postać p lub q, gdzie p i q są zdaniami. W rachunku zdań dla alternatywy stosowany jest zapis . Przez alternatywę rozumie się też zdanie mające postać p(1) lub p(2) lub ... lub p(n). Alternatywę można zdefiniować bardziej formalnie jako dwuargumentowe działanie określone w zbiorze zdań, które zdaniom p, q przyporządkowuje zdanie p lub q....
[click for more], zaś ~ - negacjaNegacja (inaczej zaprzeczenie) to zdanie mające postać nieprawda, że p, gdzie p jest zdaniem. W rachunku zdań negacja zapisywana jest jako: (lub ). Negację można zdefiniować ściślej jako jednoargumentowe działanie określone w zbiorze zdań, które każdemu zdaniu p przyporządkowuje zdanie nieprawda, że p. Negację zdania p uważa się za prawdziwą, gdy zdanie p jest fałszywe, zaś za fałszywą, gdy zdanie p jest prawdziwe....
[click for more]. Wreszcie 1 to formuła zawsze prawdziwa, a 0 - zawsze fałszywa (tak naprawdę elementami X nie są same formuły logiczne, a klasy abstrakcji ze względu na relację: formuła f jest równoważna formule g, jeśli dla tych samych podstawień zmiennych ich wartość logiczna jest taka sama).

Minimalna aksjomatyzacja

Algebra Boole'a jest oczywiście "przedefiniowana" - 0 i 1 można zastąpić przez odpowiednio (x + (~x)) i ~(x + (~x)), zaś dzięki prawom de Morgana można wyeliminować * (w istocie wszystkie działania można tak naprawdę zastąpić jednym - kreską Scheffera Dysjunkcja to w logice jeden ze spójników zdaniowych. Mianem tym określa się zresztą - w zależności od źródła - aż cztery różne spójniki zdaniowe: 1.NAND (funktor Sheffera, kreska Sheffera, dawniej:niewspółzachodzenie) to logiczne albo w sensie: co najwyżej jedno z dwojga. Dysjunkcja zdań p|q jest fałszywa tylko wtedy, gdy oba zdania zarówno p jak i q są prawdziwe. Charakterystyczną własnością dysjunkcji jest to, że można przy jej pomocy zdefiniować wszystkie pozostałe spójnik...
[click for more]). Standardowa jest jednak powyższa definicja i powyższa aksjomatyka - ze względu na wygodę i zgodność z intuicją.

Ważne jest pytanie: jaki jest minimalny zestaw aksjomatów definiujących algebry Boole'a ?

Przykładowy minimalny zestaw aksjomatów to:

+ jest przemienne
+ jest łączne
aksjomat Huntingtona: $\neg(\neg x + y) + \neg (\neg x + \neg y) = x$

Inny taki zestaw to:

+ jest przemienne
+ jest łączne
aksjomat Robbinsa: $\neg(\neg(x + y) + \neg(x + \neg y)) = x$

Powyższe fakty zostały udowodnione przez system automatycznego dowodzenia twierdzeń (czyli przez komputer) po ponad 60 latach niepowodzeń matematyków.

Zobacz też:

przegląd zagadnień z zakresu matematyki
funkcja boolowska
George BooleGeorge Boole (2 listopada 1815 - 8 grudnia 1864) to angielski matematyk i filozof. Jego głównym osiągnięciem było wprowadzenie do matematyki i logiki pojęcia algebry Boole'a. Ze względu na wagę tego pojęcia oraz jego zastosowań w informatyce i logice matematycznej Boole jest powszechnie uważany za jednego z twórców tych dziedzin nauki....
[click for more].

Kategorie: LogikaG...
[click for more]