Boole-algebra

A Wikipédiából, a szabad enciklopédiábó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 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 komplementer 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.

Története[szerkesztés | forrásszöveg szerkesztése]

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 Alfred North 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.

Axiomatizálása[szerkesztés | forrásszöveg szerkesztése]

1933-ban Edward Vermilye Huntington amerikai matematikus (1874–1952) egy elegáns axiómarendszert dolgozott ki a Boole-algebrák számára. Ehhez két alapműveletre volt szüksége, a + két változós és az n() egy változós műveletre, ami a komplementert adja vissza. A Boole-algebra eleget tesz a következő követelményeknek.

  1. kommutativitás: x + y = y + x.
  2. asszociativitás: (x + y) + z = x + (y + z).
  3. Huntington-egyenlőség: n(n(x) + y) + n(n(x) + n(y)) = x.

Herbert Robbins az utolsó egyenlőséget a duálisával helyettesítette:

4. Robbins-egyenlet: n(n(x + y) + n(x + n(y))) = x

Évtizedekig nyitott kérdés volt, hogy az 1., 2., és a 4. axióma együtt szintén Boole-algebrát ad-e. A sejtést csak 1996-ban sikerült bebizonyítani.

A Robbins-sejtés évtizedeken át nyitott maradt, és Alfred Tarski és köre kedvenc témájává vált. 1996-ban William McCune igazolta Larry Wos, Steve Winker, és Bob Veroff eredményeinek felhasználásával. Dahn egyszerűsítette a bizonyítást.

Részletes definíció[szerkesztés | forrásszöveg szerkesztése]

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 továbbá a \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

Mindezekbő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ágok
 \overline{\overline{a}} = a

Példák[szerkesztés | forrásszöveg szerkesztése]

Kételemű Boole-algebra[szerkesztés | forrásszöveg szerkesztése]

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:

0 1
0 0 0
1 0 1
0 1
0 0 1
1 1 1
a 0 1
¬a 1 0

Halmazműveletek[szerkesztés | forrásszöveg szerkesztése]

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.

Szintén Boole-algebra a H alaphalmaz véges és ko-véges részhalmazainak rendszere.

Egyéb példák[szerkesztés | forrásszöveg szerkesztése]

  • Legyen H egy teljesen rendezett halmaz, és vegyük a legszűkebb, az [a,b) félig nyílt intervallumokat tartalmazó algebrát (aH, b ∈ H vagy b=∞). Az így kapott Boole-algebrák az intervallumalgebrák; minden megszámlálható Boole-algebra izomorf egy intervallumalgebrával.
  • Egy n természetes számra n pozitív osztói disztributív hálót adnak, ha a rendezés az oszthatóság, a metszet a legnagyobb közös osztó, az egyesítés a legkisebb közös többszörös képzése. Ebben a hálóban a legkisebb elem az 1, a legnagyobb elem n. Ez a háló akkor és csak akkor Boole-algebra, ha n négyzetmentes.
  • Legyen X topologikus tér. Ekkor X összes olyan részhalmaza, ami nyílt és zárt is, Boole-algebrát alkot. A műveletek: \lor := \cup egyesítés, és \land := \cap metszet.
  • Legyen R gyűrű, és vegyük a centrális idempotens elemeket:
A = { eR : e2 = e, ex = xe, ∀xR }

Ekkor A Boole-algebra lesz a e \lor f := e + f - ef és az e \land f := ef műveletekkel.

Boole-halmazalgebra[szerkesztés | forrásszöveg szerkesztése]

Amennyiben A halmaz, B az A bizonyos részhalmazainak halmaza, akkor abban az esetben mondjuk, hogy az (B,∪,∩,/A,A,0) struktúra Boole-halmazalgebra, ha B zárt a ∪, ∩, /A halmaz műveletekre, az üres halmaz (0) és A eleme B-nek.

Stone tétele szerint minden (absztrakt) Boole-algebra izomorf egy Boole-halmazalgebrával.

Ez azt is jelenti, hogy a Boole-halmazalgebrák \mbox{ }_\mathsf{BsA} osztályát végesen axiomatizálják a Boole-algebrák \mbox{ }_\mathsf{BA} osztályát definiáló egyenletek.

Logikai áramkörök[szerkesztés | forrásszöveg szerkesztése]

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.

Homomorfizmusok és izomorfizmusok[szerkesztés | forrásszöveg szerkesztése]

Ha A és B két Boole-algebra, akkor az f : AB függvény homomorfizmus A és B között, ha minden a és bA-ra:

f(a \lor b) = f(a) \lor f(b)
f(a \land b) = f(a) \land f(b)
f(0) = 0\,
f(1) = 1.\,

Következik, hogy f({\neg}a) = {\neg}f(a) minden a eleme A-ra. A Boole-algebrák osztálya ezekkel a morfizmusokkal teljes alkategóriát alkotnak a hálók kategóriájában.

Boole gyűrűk, ideálok és szűrők[szerkesztés | forrásszöveg szerkesztése]

Ha (A, \land, \lor) Boole-algebra, akkor ad egy (A, +, *) gyűrűt a metszésre, mint szorzásra, és a szimmetrikus differenciára, mint összeadásra nézve. Ahol is a szimmetrikus differencia:

a + b = (a \land {\neg}b) \lor (b \land {\neg}a).

ugyanezt a műveletet a logika nyelvén kizáró vagynak nevezik.

Ebben a gyűrűben a Boole-algebra 0 eleme neutrális elem, és a Boole-algebra 1 eleme a gyűrű egységeleme. Ebben a gyűrűben mindena elemre a * a = a; az ilyen tulajdonságú gyűrűk a Boole-gyűrűk.

Megfordítva, ha adva van az A Boole-gyűrű, akkor Boole-algebrához jutunk a x \lor y = x + y + xy és a x \land y = xy műveletekkel. Ez a két átalakítás egymás inverze, ezért f : AB akkor és csak akkor homomorfizmusa a Boole-algebrán, ha a Boole-gyűrűn is homomorfizmus. A Boole-gyűrűk és a Boole-algebrák kategóriái ekvivalensek.

Egy A Boole-algebrának ideálja az I halmaz, ha minden x, y I-beli elemre x \lor y szintén I-ben van, és minden a eleme A-ra a \land x is I-ben van. Ez megfelel az A Boole-gyűrű ideáljainak. Egy I ideál prímideál, ha IA és ha a \land b I-beli, akkor a vagy b I-beli. Egy IA ideál maximális, ha nincs nála nagyobb JA ideál, ami tartalmazza. Az algebrában és a gyűrűben ugyanazok a részhalmazok prímideálok, vagy maximális ideálok.

Az ideálok duálisai a szűrők. Egy A-val jelölt Boole-algebrában p szűrő, ha minden x, y eleme p-re x \land y is p-beli, és minden a eleme A-ra a \lor x szintén p-beli.

Reprezentációi[szerkesztés | forrásszöveg szerkesztése]

Megmutatható, hogy minden véges Boole-algebra izomorf egy teljes halmazalgebrával. Ezért egy Boole-algebra elemszáma vagy kettőhatvány, vagy végtelen.

M. H. Stone híres tétele azt állítja, hogy minden Boole-algebra izomorf egy Hausdorff-tér összes nyílt-zárt halmazának Boole-algebrájával.

Általánosításai[szerkesztés | forrásszöveg szerkesztése]

Az egységelem követelményének elejtése az általános Boole-algebrákhoz vezet. Képletekkel:

A B disztributív háló általános Boole-háló, ha van egy 0 legkisebb eleme, és minden a és b eleme B-re, amire ab, van egy x elem, hogy a \land x = 0 és a \lor x = b. Ha most a\setminus b az az x, amire (a \land b) \lor x = a és (a \land b) \land x = 0, a (B,\land,\lor,\setminus,0) struktúrát általános Boole-hálónak nevezzük, míg (B,\lor,0) általános Boole-félháló. Az általános Boole-hálók éppen a Boole-hálók ideáljai.

A disztributivitás követelményének elejtésével az ortokomplementumos hálókhoz jutunk. Az ilyen hálók természetes módon adódnak a kvantumlogikában, mint szeparábilis Hilbert-terek zárt részhalmazainak hálói.

Kapcsolódó szócikkek[szerkesztés | forrásszöveg szerkesztése]

Források[szerkesztés | forrásszöveg szerkesztése]

Brown, Stephen & Vranesic, Zvonko (2002), Fundamentals of Digital Logic with VHDL Design (2nd ed.), McGraw–Hill, ISBN 978-0-07-249938-4. See Section 2.5.

Cori, Rene & Lascar, Daniel (2000), Mathematical Logic: A Course with Exercises, Oxford University Press, ISBN 978-0-19-850048-3. See Chapter 2.

Dahn, B. I. (1998), "Robbins Algebras are Boolean: A Revision of McCune's Computer-Generated Solution of the Robbins Problem", Journal of Algebra 208: 526–532, DOI 10.1006/jabr.1998.7467.

Givant, Steven & Halmos, Paul (2009), Introduction to Boolean Algebras, Undergraduate Texts in Mathematics, Springer, ISBN 978-0-387-40293-2.

Halmos, Paul (1963), Lectures on Boolean Algebras, Van Nostrand, ISBN 978-0-387-90094-0.

Halmos, Paul & Givant, Steven (1998), Logic as Algebra, vol. 21, Dolciani Mathematical Expositions, Mathematical Association of America, ISBN 978-0-88385-327-6.

Huntington, E. V. (1933), "New sets of independent postulates for the algebra of logic", Transactions of the American Mathematical Society (American Mathematical Society) 35 (1): 274–304, doi:10.2307/1989325, <http://jstor.org/stable/1989325>.

Huntington, E. V. (1933), "Boolean algebra: A correction", Transactions of the American Mathematical Society (American Mathematical Society) 35 (2): 557–558, doi:10.2307/1989783, <http://jstor.org/stable/1989783>.

Mendelson, Elliott (1970), Boolean Algebra and Switching Circuits, Schaum's Outline Series in Mathematics, McGraw–Hill, ISBN 978-0-07-041460-0.

Monk, J. Donald & Bonnet, R., eds. (1989), Handbook of Boolean Algebras, North-Holland, ISBN 978-0-444-87291-3. In 3 volumes. (Vol.1:ISBN 978-0-444-70261-6, Vol.2:ISBN 978-0-444-87152-7, Vol.3:ISBN 978-0-444-87153-4)

Stoll, R. R. (1963), Set Theory and Logic, W. H. Freeman, ISBN 978-0-486-63829-4. Reprinted by Dover Publications, 1979.

Fordítás[szerkesztés | forrásszöveg szerkesztése]

Ez a szócikk részben vagy egészben a Boolean algebra (structure) című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel.