Boole-algebra (struktúra)

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 ${\displaystyle (A,\lor ,\land )}$ legalább kételemű egységelemes, zéruselemes háló, mely disztributív és komplementumos. Ez utóbbi tulajdonság azt jelenti, hogy az ${\displaystyle A}$ halmaz minden a elemére teljesül, hogy létezik olyan ${\displaystyle {\overline {a}}}$ elem, hogy:

${\displaystyle a\lor {\overline {a}}=1\quad {\text{illetve}}\quad a\land {\overline {a}}=0}$

ahol 1 az egységelem, 0 a zéruselem, ${\displaystyle {\overline {a}}}$-t pedig az ${\displaystyle 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” ${\displaystyle \{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 ${\displaystyle a}$ elem komplementere ${\displaystyle \neg a}$, az elem negációja
• a valószínűség-elmélet egy ${\displaystyle \Omega }$ eseménytere, az események közötti összeg és szorzat műveletével; az ${\displaystyle {\overline {A}}}$ komplementer az az esemény, hogy az ${\displaystyle 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ép-tudomá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 ${\displaystyle a\leq b\Leftrightarrow a=a\land 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 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.

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.

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 ${\displaystyle +}$ két változós és az ${\displaystyle 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: ${\displaystyle x+y=y+x}$.
2. asszociativitás: ${\displaystyle (x+y)+z=x+(y+z)}$.
3. Huntington-egyenlőség: ${\displaystyle 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: ${\displaystyle 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.

A Boole-algebra tehát egy ${\displaystyle A}$ halmaz, melynek van legalább két eleme, az 1 és a 0, ellátva a kétváltozós ${\displaystyle \lor }$ (szóban: „vagy”) és ${\displaystyle \land }$ (szóban „és”) művelettel, továbbá a ${\displaystyle {\overline {x}}}$ (szóban: „felülvonás”, „tagadás”), avagy más jelöléssel: ${\displaystyle \lnot x}$ (szóban: „komplemens”, „ellentett”) egyváltozós művelettel, melyet komplementerképzésnek nevezünk és melyekre a következő művelet azonosságok teljesülnek:

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

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

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

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:

${\displaystyle \land }$ 0 1 0 0 0 1 0 1

${\displaystyle \lor }$ 0 1 0 0 1 1 1 1

${\displaystyle a}$ 0 1 ${\displaystyle \lnot a}$ 1 0

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:

${\displaystyle \lor :=\cup }$ (unió)

${\displaystyle \land :=\cap }$ (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.

• Legyen H egy teljesen rendezett halmaz, és vegyük a legszűkebb, az ${\displaystyle [a,b)}$ félig nyílt intervallumokat tartalmazó algebrát (${\displaystyle a\in H}$, ${\displaystyle b\in H}$ vagy ${\displaystyle b=\infty }$). 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: ${\displaystyle \lor :=\cup }$ egyesítés, és ${\displaystyle \land :=\cap }$ metszet.
• Legyen R gyűrű, és vegyük a centrális idempotens elemeket:

${\displaystyle A=\{e\in R:\ e^{2}=e,\ ex=xe,\ \forall x\in R\}}$

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

Amennyiben A halmaz, B az A bizonyos részhalmazainak halmaza, akkor abban az esetben mondjuk, hogy az ${\displaystyle (B,\cup ,\cap ,/_{A},A,0)}$ struktúra Boole-halmazalgebra, ha B zárt a ${\displaystyle \cup ,\cap ,/_{A}}$ halmazmű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 ${\displaystyle {\mathsf {BsA}}}$ osztályát végesen axiomatizálják a Boole-algebrák ${\displaystyle {\mathsf {BA}}}$ osztályát definiáló egyenletek.

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.

Ha A és B két Boole-algebra, akkor az ${\displaystyle f:\ A\rightarrow B}$ függvény homomorfizmus ${\displaystyle A}$ és ${\displaystyle B}$ között, ha ${\displaystyle \forall a,b\in A}$-ra:

${\displaystyle f(a\lor b)=f(a)\lor f(b)}$

${\displaystyle f(a\land b)=f(a)\land f(b)}$

${\displaystyle f(0)=0\,}$

${\displaystyle f(1)=1.\,}$

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

Ha ${\displaystyle (A,\land ,\lor )}$ Boole-algebra, akkor ad egy ${\displaystyle (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:

${\displaystyle 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 minden ${\displaystyle a}$ elemre ${\displaystyle a*a=a}$; az ilyen tulajdonságú gyűrűk a Boole-gyűrűk.

Megfordítva, ha adva van az ${\displaystyle A}$ Boole-gyűrű, akkor Boole-algebrához jutunk a ${\displaystyle x\lor y=x+y+xy}$ és a ${\displaystyle x\land y=xy}$ műveletekkel. Ez a két átalakítás egymás inverze, ezért ${\displaystyle f:\ A\rightarrow B}$ 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 ${\displaystyle I}$ halmaz, ha minden ${\displaystyle x,y\in I}$-re ${\displaystyle x\lor y}$ szintén ${\displaystyle I}$-ben van, és minden ${\displaystyle a\in A}$-ra ${\displaystyle a\land x}$ is ${\displaystyle I}$-ben van. Ez megfelel az A Boole-gyűrű ideáljainak. Egy ${\displaystyle I}$ ideál prímideál, ha ${\displaystyle I\neq A}$ és ha ${\displaystyle (a\land b)\in I}$, akkor a vagy b I-beli. Egy ${\displaystyle I\neq A}$ ideál maximális, ha nincs nála nagyobb ${\displaystyle J\neq A}$ 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 ${\displaystyle A}$-val jelölt Boole-algebrában ${\displaystyle p}$ szűrő, ha minden ${\displaystyle x,y\in p}$-re ${\displaystyle x\land y}$ is ${\displaystyle p}$-beli, és minden ${\displaystyle a\in A}$-ra ${\displaystyle a\lor x}$ szintén ${\displaystyle p}$-beli.

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.

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

A ${\displaystyle B}$ disztributív háló általános Boole-háló, ha van egy 0 legkisebb eleme, és ${\displaystyle \forall a,b\in B\ (a\leq b)}$-re van egy ${\displaystyle x}$ elem, hogy ${\displaystyle a\land x=0}$ és ${\displaystyle a\lor x=b}$. Ha most ${\displaystyle a\setminus b}$ az az ${\displaystyle x}$, amire ${\displaystyle (a\land b)\lor x=a}$ és ${\displaystyle (a\land b)\land x=0}$, a ${\displaystyle (B,\land ,\lor ,\setminus ,0)}$ struktúrát általános Boole-hálónak nevezzük, míg ${\displaystyle (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.

• 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. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

• 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.

• Ítéletlogika