Boole-algebra
A Wikipédiából, a szabad lexikonból.
Az absztrakt algebra területén a George Boole nevét viselő Boole-algebra egy algebrai struktúra (elemek és azokon értelmezett utasítások gyűjteménye, melyekre bizonyos axiómák érvényesek) amely a halmazműveletek és a logikai műveletek legalapvetőbb tulajdonságait gyűjti össze. Speciálisan a metszet, az unió, a komplementer műveletekét a halmazelméletből és a konjunkció (ÉS, AND), diszjunkció (VAGY, OR) és a negáció (NEM, NOT) műveletét a logikából.
Például egy logikai kijelentés: egy a állítás és a ¬a negáltja nem lehet egyszerre igaz,
az ennek megfelelő halmazelméleti állítás a következő: egy A részhalmaz és annak AC komplementerének a metszete üres halmaz,
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.
A Boole-algebrát Boole-hálónak is nevezik. A hálókkal (a speciális részben rendezett halmazokkal) való kapcsolatot a részhalmaz reláció (A ⊆ B) és a rendezés (a ≤ b) közötti hasonlóság adja. Tekintsük a {x,y,z} halmaz összes részhalmazát a részhalmaz reláció szerint rendezve. Ez a Boole-háló részben rendezett halmaz, amelyben {x} ≤ {x,y}. Bármely két eleme a hálónak, pl. p = {x,y} és q = {y,z}, rendelkezik egy legkisebb felső korláttal, itt {x,y,z}, és egy legnagyobb alsó korláttal, itt {y}. Suggestively, legkisebb felső korlát (vagy szuprémum) jelölése egyezik a logikai VAGY-éval, p ∨ q; és a legnagyobb alsó korláté (vagy infimumé) a logikai ÉS jelölésével, p ∧ q.
A hálóinterpretáció lehetőséget biztosít a Boole-algebra általánosításának megalkotására. A Heyting-algebra a Boole-algebra olyan általánosítása, mely nem tartalmazza azt a megkötést, hogy egy kijelentésnek mindenképpen igaznak vagy hamisnak kell lennie. Érdemes megjegyezni, hogy 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] Operátorok, műveletek
Logikai alapműveletek az (ÉS),
(VAGY) és
(NEGÁLT). Minden további definiált alapművelet összetett, ezekből levezethető:
- implikáció

- ekvivalencia

- kizáró vagy (SEM-SEM)
- Scheffer-féle művelet
[szerkesztés] A logikai változók értéke
Kétváltozós kifejezések értéke, a változók értékétől és a rájuk alkalmazott művelettől függ, amit igazságtáblázat segítségével szemléltetünk. A Boole-algebra alapműveleteinek igazságtáblázata így néz ki:
|
|
|
[szerkesztés] Ítéletlogikai műveletek tulajdonságai, azonosságok
A főbb logikai azonosságok egy, kettő illetve három változóra az
(ÉS),
(VAGY) és
(NEGÁLT) operátorokkal. A logikai változók értékénél 0 hamis állítást (üres halmazt), 1 pedig igaz állítást (az a, b és c elemeket tartalmazó halmazt) jelöli.
-


asszociatív 

kommutatív 

absorption 

disztributív 

komplementerek
Ezek az állítások ugyanis a halmazelméletben is megtalálhatóak, következésképpen halmazelméleti azonosságokként is értelmezhetőek. (Például a következő logikai műveletek halmazelméleti fogalmaknak felelnek meg.: ÉS→metszet, VAGY→unió, negált→komplementer, kizáró vagy→halmazok különbsége stb.)
A De-Morgan azonosságok igazságtáblázattal való bizonyítása:
| Függvény | Igazságtáblázat | |||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
![]() |
|
| Függvény | Igazságtáblázat | |||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
![]() |
|
[szerkesztés] Prioritás
Boole-algebrában a műveletek sorrendje szigorúan meghatározott:
- negált
- konjunkció, diszjunkció
A műveleti sorrend természetesen zárójelekkel megbontható.
[szerkesztés] Példa logikai függvény alkalmazására
[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