Matematika | Tanulmányok, esszék » Boole-algebra

Boole-algebra George Boole (1815-1864) Lincolnban, Angliában született egy szegény cipész fiaként. Az iskolában nem kapott elég képzést, ezért autodidakta módon tanult. Kezdetben a nyelvek érdekelték, de húsz éves korában saját iskolát alapított, ekkor kezdett el komolyan foglalkozni a matematikával. 1847-ben jelent meg a �Logika matematikai analízise� címû munkája, amelyben elôször mutatta meg, hogy az arisztotelészi logika algebrai egyenletekként is leírható. Maga Boole ezt így fogalmazta meg: �Többé nem a logikát és a metafizikát kell összekapcsolnunk, hanem a logikát és a matematikát. 1849-ben az írországi Corkban a Queen�s College matematika professzora lett, itt tanított élete hátralevô részében. 1854 -ben megjelentette �A gondolkodás törvényeinek vizsgálata, amelyeken a logika és a valószínûség matematikai teóriái alapulnak� címû mûvét. Ez tartalmazza azokat a koncepciókat, amelyek ma Boole-algebra

néven ismeretesek. Ezek nem csak a matemetika tanításában használatosak, de az informatikában, a kapcsolástechnikában, a gráf-elméletben, a számítástechnikában, valamint a mesterséges intelligencia kutatásában. Értelmezzük egy halmaz részhalmazainak halmazára két kétargumentumos (binér) mûveletet, az unió- és a metszetképzést, valamint egy egyargumentumos (unér) mûveletet, a komplementumképzést, és vizsgáljuk meg a tulajdonságikat. Így egy hárommûveletes struktúrát kapunk, ezt nevezzük Boole-algebrának. Egy halmaz részhalmazainak halmaza az unió, a metszet- és a komplementumképzés mûveleteire zárt. 1. A Ç B = B Ç A 2. A È B = B È A 3. (A È B) È C = A È (B È C) 4. (A Ç B) Ç C = A Ç (B Ç C) 5. A Ç A = A 6. A È A = A 7. A Ç (B È C) = (A Ç B) È (A Ç C) 8. A È (B Ç C) = (A È B) Ç (A È C) 9. A Ç A� = Ø 10. A È A� = E 11. A Ç Ø = Ø 12. A Ç E = A 13. A È Ø = A 14. A È E = E 15. (A� )� = A 16. (A Ç

B)� = A� È B� 17. (A È B)� = A� Ç B� E tulajdonságok tekinthetôk a hárommûveletes struktúra axiómáinak, másnéven Boole- axiómáknak. Boole saját megfogalmazásában az egység- és a nullelemet adta meg. Ezek: az alaphalmaz (jelölése: E) és az üres halmaz (jelölése: Ø). Látható, hogy a három mûvelet a következô tulajdonságokkal rendelkezik: kommutativitás (1, 2), asszociativitás (3, 4), idempotencia (5, 6), a metszet az unióra, az unió a metszetre vonatkozólag disztributív (7, 8). Mivel a tizenhatodik és a tizenhetedik axióma (de Morgan-tételei) levezethetô a többibôl, ezért ezeket el lehet hagyni. Mindössze hagyományból szokás kiírni ôket, mert eredetileg ezek szerepeltek az axiómák között, de bonyolultságuk miatt késõbb egyszerûbb összefüggések kerültek az axiómák közé. Ez a Boole-algebra képezi a halmazelmélet alapját, amely a matematika nagyon fontos része, mivel a halmazok fogalmakat jelölnek, az

fogalmakban való gondolkodás alapja a halmazelmélet. Gyakorlati jelentôségük fôleg a véges Boole-algebráknak van, azaz az olyan halmazoknak, amelyek részhalmazainak száma véges. Tekintsük az E = {1} egyelemû halmazt. Részhalmazait az egyszerûség kedvéért jelöljük a következôképpen: 0-val az üres halmazt és 1-gyel az {1} halmazt. Ha az unió mûveletét * jellel, a metszetét pedig + jellel jelöljük, a részhalmazokra felírva a mûveleteket a következôt kapjuk: Metszet Unió 0*0=0 0+0=0 0*1=0 0+1=1 1*1=1 1+1=1 Komplementumképzés 0 1 = 0 = 1 Táblázatba foglalva: Metszet Unió * 0 1 +01 0 0 0 0 01 1 0 1 1 11 Egy E alaphalmaz minden A részhalmazának feleltessünk meg egy karakterisztikus függvényt (olyan függvény, amely csak 0 vagy 1 értéket vehet fel), oly módon, hogy • f(x) = 1, ha x Î A • f(x) = 0, ha x Ï A. Könnyen belátható, hogy az E halmaz részhalmazainak halmazán végzett mûveleteknek megfeleltethetô

egy, az E halmaz karakterisztikus függvényeinek halmazában végzett mûvelet. Látható, hogy a karakterisztikus függvények halmaza kétértékû Boole-algebra, így sok részhalmaz esetén is alkalmazhatóak az egyszerû mûveleti szabályok. Ezzel eljutottunk a logikai mûveletek Boole-algebrájához. Itt az egységelem az 1, a nullelem a 0. Egy feltétel teljesülését jelöljük 1-gyel (igaz), nem teljesülését pedig 0-val (hamis) Ekkor egy két feltételbôl álló feltételrendszer (A és B feltétel) Boole-algebrát alkot. Az ÉS kapcsolatnak megfelel a metszetképzés, mivel a feltételrendszer akkor igaz ha A és B feltétel is igaz, ami úgy modellezhetô, hogy eleme A feltétel és B feltétel igaz halmazának is, azaz a két halmaz metszetében található. A VAGY kapcsolatnak hasonlóképpen megfelel az unió, mivel a feltételrendszer akkor igaz, ha eleme A vagy B feltétel igaz halmazának, azaz e kettô uniójának. E kapcsolatok több feltétel esetén

is fennállnak Állításkalkulusban ezen algebra segítségével minden tétel bebizonyítható vagy megcáfolható, azaz levezethetõ igaz vagy hamis eredményre. A logikai mûveletek Boole-algebrája az alapja a vezérléstechnikának, a gépi matematikának, a számítástechnikának