Algebra Boole'a jest to struktura matematyczna złożona z uniwersum 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)
  • 0 jest elementem neutralnym dla +: x + 0 = x
  • 1 jest elementem neutralnym dla *: 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)

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, + - alternatywa, zaś ~ - negacja. 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). 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.
Publikacja wraz ze zdjęciami jest udostępniona w Encyklopedii "Zgapedia" części portalu zgapa.pl. Treść objęta jest licencją GNU FDL Wolnej Dokumentacji w wersji 1.3 lub dowolnej pózniejszej opublikowanej przez Free Software Foundation i została ona opracowana na podstawie Wikipedii, tutaj możesz znaleźć artykuł źródłowy oraz autorów. Warunki użytkowania Encyklopedii znajdziesz na tej stronie.