Boole-algebra

A Wikipédiából, a szabad lexikonból.

A matematikában, közelebbről az algebrában a Boole-algebra (vagy Boole-háló) az a kétműveletes algebrai struktúra (egy halmaz, az elemei között értelmezett két művelettel ellátva), amely a halmazműveletek, a logikai műveletek és az eseményalgebra műveleteinek közös tulajdonságaival rendelkezik. Matematikai szemszögből a Boole-algebra olyan (A, ∨, ∧) legalább kételemű egységelemes, zéruselemes háló, mely disztributív és komplementumos. Ez utóbbi tulajdonság azt jelenti, hogy az A halmaz minden a elemére teljesül, hogy létezik olyan \mbox{ }_{\overline{a}} elem, hogy:

a\vee\overline{a}=1\;\;\;\mbox{illetve}\;\;\;a\wedge\overline{a}=0

ahol 1 az egységelem, 0 a zéruselem, \mbox{ }_{\overline{a}}-t pedig az a komplementerének nevezzük.

Az {x,y,z} háromelemű halmaz részhalmazainak Boole-algebrája irányított gráfként ábrázolva. Az A ⊆ B ⇔ A → B reláció teszi relációs struktúrává.
Az {x,y,z} háromelemű halmaz részhalmazainak Boole-algebrája irányított gráfként ábrázolva. Az ABAB reláció teszi relációs struktúrává.

George Boole angol matematikus mutatott rá először arra, hogy az alábbi három terület közötti szoros algebrai jellegű kapcsolat áll fenn:

  • egy tetszőleges H halmaz hatványhalmaza, a H részhalmazai közötti unió és metszet tulajdonsággal; az A részhalmaz komplementere a H azon elemei, melyek nincsenek benne A-ban
  • az „igazságértékek” {0,1} halmaza, a logikai összeadás és a szorzás műveletével (mely rendre a „vagy” és az „és” szerepét tölti be); az a elem ¬a komplementere, az elem negációja
  • a valószínűség-elmélet egy Ω eseménytere, az események közötti összeg és szorzat műveletével; az \mbox{ }_{\overline{A}} komplementer az az esemény, hogy az A esemény nem következik be.

Mivel az igaz értéket bináris számokkal vagy logikai áramkörök feszültségszintjeivel is azonosíthatjuk, a párhuzam ezekre is fennáll. Így a Boole-algebra elmélete rengeteg gyakorlati alkalmazással bír a villamosmérnöki szakma és a számítógéptudomány területén, valamint a matematikai logikában. Erről lásd még: Boole-algebra (informatika)

Minden Boole-algebra megfeleltethető egy relációs struktúrának az aba = ab megfeleltetéssel. Ez a hálóelméleti definíció nyújt lehetőséget a Boole-algebra általánosítására. Ez a Heyting-algebra, mely nem tartalmazza azt a megkötést, hogy egy kijelentésnek mindenképpen igaznak vagy hamisnak kell lennie (lásd a fenti komplemeter azonosságot). Míg a Boole-algebra a klasszikus propozicionális logika algebrai interpretációjának tekinthető, addig a Heyting-algebra az intuicionista logika algebrai interpretációját adja.


Tartalomjegyzék

[szerkesztés] Részletes definíció

A Boole-algebra tehát egy A halmaz, melynek van legalább két eleme, az 1 és a 0, ellátva a kétváltozós ∨ (szóban: „vagy”) és ∧ (szóban „és”) művelettel és továbbá a célszerűségi indokokból megadott \mbox{ }_{\overline{(\;)}} egyváltozós művelettel, melyet komplementerképzésnek nevezünk és melyekre a következő művelet azonosságok teljesülnek:

a \lor (b \lor c) = (a \lor b) \lor c a \land (b \land c) = (a \land b) \land c asszociatív
a \lor b = b \lor a a \land  b = b \land a kommutatív
a  \lor (a \land b) = a a  \land (a \lor b) = a elnyelési tulajdonság
a \lor  (b \land c) = (a \lor b) \land (a \lor c) a \land  (b \lor c) = (a \land b) \lor (a \land c) disztributív
a \lor  \overline{a} = 1 a \land \overline{ a} = 0 komplementer képzés

Minedezekből következnek további tulajdonságok is:

a \lor a = a a \land a = a idempotencia
a \lor 0 = a a \land 1 = a korlátosság
a \lor 1 = 1 a \land 0 = 0
\overline{ 0} = 1 \overline{ 1} = 0 0 és 1 egymás komplementerei
\overline{ a \lor b} = \overline{ a } \land \overline{ b} \overline{ a \land b} = \overline{ a}  \lor \overline{ b} de Morgan azonosság
\overline{\overline{a}} = a

[szerkesztés] Példák

[szerkesztés] Kételemű Boole-algebra

A legegyszerűbb Boole-algebra csak az 1 és a 0 elemeket tartalmazza. Ez megfelel az igazságértékekkel végzett műveletek algebrájának. A műveleti táblák ekkor a műveletek explicit definícióját adják:

∧ (és)
\land 0 1
0 0 0
1 0 1
 
∨ (vagy)
\lor 0 1
0 0 1
1 1 1
 
komplementer
  \overline{(\;)}
0 1
1 0

[szerkesztés] Halmazműveletek

Ha megadunk egy H halmazt (vagy egy C osztályt – ahogy eredetileg Boole), akkor ennek részhalmazai Boole-algebrát alkotnak a következő műveletkiosztással:

∨ := ∪ (unió)
∧ := ∩ (metszet)
komplemeter: az alaphalmazból való halmazkivonás művelete

Ebben az interpretációban 1 megfelel az alaphalmaznak, 0 az üres halmaznak.

[szerkesztés] Logikai áramkörök

A logikai műveleteket elektromos kapcsolásokként (kapuáramkörökként) is értelmezhetjük. A logikai függvényeket így kapuáramkörök kombinálásával is felírhatjuk. Az ÉS, VAGY és NEGÁLT műveletek soros és párhuzamos kapcsolásnak, valamint invertereknek felelnek meg.

[szerkesztés] Története

A „Boole-algebrát” George Boole (1815–1864) tiszteletére nevezték el, aki autodidakta angol matematikus volt. A logika algebrai rendszerét 1854-es monográfiájában, A gondolkodás törvényeiben (The Laws of Thought) fogalmazta meg. Ez különbözött a fent leírttól pár fontos pontban. Például a konjunkció és a diszjunkció számára nem egy duális operátorpár volt. A Boole-algebra 1860-ban jött létre William Jevons és Charles Peirce cikkeiben. Ernst Schröder 1890-es Vorlesungenjének idejére már rendelkeztünk a Boole-algebra és a disztributív hálók első rendszerezett bemutatásával. Angol nyelvterületen a Boole-algebra első kiterjedt tárgyalása A. N. Whitehead 1898-ban írt Univerzális algebra (Universal Algebra) című műve volt. A Boole-algebrának az első axiomatikus algebrai struktúraként történő tárgyalása Edward Vermilye Huntington 1904-es dolgozatával kezdődött meg. Komoly matematikává Marshall Stone 1930-as években végzett munkájával és Garrett Birkhoff 1940-es Hálóelmélet (Lattice Theory) című művével vált. Az 1960-as években Paul Cohen, Dana Scott és mások mélyenszántó új eredményeket találtak a matematikai logika és az axiomatikus halmazelmélet területén a Boole-algebra ágainak használatával, név szerint a forszolással és a Boole-értékű modellekkel.

[szerkesztés] Lásd még