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
elem, hogy:
ahol 1 az egységelem, 0 a zéruselem,
-t pedig az a komplementerének nevezzük.
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
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 a ≤ b ⇔ a = a ∧ b 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
egyváltozós művelettel, melyet komplementerképzésnek nevezünk és melyekre a következő művelet azonosságok teljesülnek:
-


asszociatív 

kommutatív 

elnyelési tulajdonság 

disztributív 

komplementer képzés
Minedezekből következnek további tulajdonságok is:
-


idempotencia 

korlátosság 



0 és 1 egymás komplementerei 

de Morgan azonosság 
[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:
|
|
|
[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.






Based on work by