Boolen algebra

Boolen algebra on George Boolen mukaan nimensä saanut algebrallinen struktuuri, joka toimii loogisen lausekalkyylin ja joukko-opin mallina.

Määritelmä

Boolen algebran muodostaa joukko, jossa on määritelty kaksi laskutoimitusta, $\land$ ja $\lor$, laskutoimitusten neutraalialkiot 0 ja 1 (joista käytetään joskus myös merkintöjä ⊥ ja $\top$) ja jossa jokaisella alkiolla on lisäksi komplementti $\neg a$ siten, että ne toteuttavat seuraavat ehdot:

$a\lor (b\lor c)=(a\lor b)\lor c$	$a\land (b\land c)=(a\land b)\land c$	liitäntälait
$a\lor b=b\lor a$	$a\land b=b\land a$	vaihdantalait
$a\lor (a\land b)=a$	$a\land (a\lor b)=a$	absorptiolait
$a\lor (b\land c)=(a\lor b)\land (a\lor c)$	$a\land (b\lor c)=(a\land b)\lor (a\land c)$	osittelulait
$a\lor {\neg }a=1$	$a\land {\neg }a=0$

Toisinaan määritelmän ehdoista jätetään pois absorptiolait, ja ne korvataan uusilla ehdoilla $\mathbf {} a\lor 0=a$ ja $\mathbf {} a\land 1=a$ (Ehtojen kokonaismäärä pysyy siis kymmenessä.). Kummallakin tavalla kymmenen ehdon avulla esitetyt määritelmät ovat yhtäpitäviä, sillä voidaan osoittaa, että jos jokin struktuuri toteuttaa muut kahdeksan ehtoa ja lisäksi absorptiolait, se toteuttaa myös tässä esitetyt uudet ehdot, ja kääntäen, jos se toteuttaa muut kahdeksan ehtoa ja lisäksi nämä uudet ehdot se toteuttaa myös absorptiolait.

Toisinaan käytetään laskutoimitukselle $a\lor b$ myös merkintää a + b ja laskutoimitukselle $a\land b$ merkintää ab tai a · b. Ne eivät kuitenkaan kaikilta osin noudata reaalilukujen laskutoimituksia. Edellä esitetyistä Boolen algebran laskusäännöistä vain liitäntä- ja vaihdantalait sekä jälkimmäinen osittelulaki pätevät myös reaaliluvuille.

Yksinkertaisin Boolen algebra käsittää vain yhden alkion. Toisinaan määritelmään kuitenkin lisätään ehto, jonka mukaan 0 ja 1 eivät saa olla sama alkio, mikä sulkee tämän tapauksen pois.

Boolen algebra ja lausekalkyyli

Boolen algebraa voidaan käyttää matemaattisena esitystapana loogiselle lausekalkyylille. Tällöin laskutoimitus $\land$ vastaa lauseiden konjunktiota (JA, engl. AND), laskutoimitus $\lor$ taas disjunktiota (TAI, engl. OR) ja komplementti $\neg$negaatiota (EI, engl. NOT). Alkio 0 tarkoittaa epätotta ja 1 totta lausetta. Mikäli perusjoukossa on muita alkioita, ne vastaavat yleensä lauseita, joiden totuusarvoa ei tunneta. Tällöin lauseet a ja b, a tai b sekä ei a ovat a:sta ja b:stä riippuen tosia tai epätosia niin kuin seuraavat ns. totuusarvotaulukot osoittavat:

JA: Jos molemmat ehdot on tosia (eli arvo on 1), vastaus on tosi (1)

JA	0	1
0	0	0
1	0	1

TAI: Jos edes toinen ehdoista on tosi (eli arvo on 1), vastaus on tosi (1)

TAI	0	1
0	0	1
1	1	1

EI kääntää totuusarvon toiseksi: ykkösen nollaksi ja nollan ykköseksi.

	0	1
EI	1	0

	X = 0	X = 1	X = a
0 AND X	0	0	0
1 AND X	0	1	a
0 OR X	0	1	a
1 OR X	1	1	1

Voidaan osoittaa, että nämä loogiset operaatiot noudattavat kaikkia ylempänä esitettyjä Boolen algebran sääntöjä.

Disjunktio (TAI) merkitsee tässä ns. inklusiivista disjunktiota ("ja/tai"), joka on tosi, kun ainakin toinen lauseista a ja b on tosi. Tämän vuoksi sovellettaessa Boolen algebraa lausekalkyyliin ei operaatiolle a $\lor$ b pidä käyttää merkintää a + b, koska sillä tarkoitetaan toisinaan ns. ekslusiivista disjunktiota, joka on tosi vain silloin, kun vain toinen sen yhdistämistä lauseista on tosi.

Esimerkiksi seuraavassa taulukossa analysoidaan, miten A OR B voidaan esittää toisessa muodossa:

A OR B = NOT( ( NOT(A) ) AND ( NOT(B) ) )

	( A	OR	B ) =	NOT( (	NOT(	A) )	AND (	NOT(	B) ) )
A=0,B=0	0	0	0	0	1	0	1	1	0
A=1,B=0	1	1	0	1	0	1	0	1	0
A=0,B=1	0	1	1	1	1	0	0	0	1
A=1,B=1	1	1	1	1	0	1	0	0	1

Boolen algebran läheinen yhteys joukko-oppiin

Minkä tahansa perusjoukon osajoukoille voidaan määritellä joukko-opilliset operaatiot unioni $A\cup B$, leikkaus $A\cap B$ ja komplementti $\mathbf {} A^{c}$. Nämä noudattavat myös Boolen algebran sääntöjä, kun unioni vastaa laskutoimitusta $\lor$, leikkaus laskutoimitusta $\land$ ja komplementti operaatiota $\neg$. Ykkösalkiona on tällöin perusjoukko, nolla-alkiona tyhjä joukko. Kääntäen voidaan osoittaa, että jokainen määritelmässä esitetyt "Boolen ehdot" toteuttava algebra on isomorfinen jonkin joukon osajoukkoalgebran kanssa eli se voidaan tulkita algebraksi, jonka alkioina ovat jonkin perusjoukon osajoukot ja laskutoimitukset on määritelty joukkojen unionin, leikkauksen ja komplementin perusteella. Tämä tulos seuraa Stonen esityslauseesta. Tämä Boolen algebran joukko-opillinen esitys ei ole yksikäsitteinen, mutta kaikki tiettyyn Boolen algebraan liittyvät joukko-opilliset esitykset ovat isomorfisia keskenään ja kyseisen Boolen algebran kanssa.

Boolen algebra biteistä koostuvana

Boolen algebran ajatellaan usein koostuvan vain biteistä $\mathbf {} 0$ ja $\mathbf {} 1$, ja joukko-opillinen yhteys oikeuttaakin tämän tulkinnan siinä mielessä, että perusjoukon $\mathbf {} E$ jokaiseen pisteeseen voidaan ajatella liitetyn bitti-arvo $\mathbf {} B$ sen mukaan kuuluuko kyseinen piste haluttuun joukkoon. Esimerkiksi jos $\mathbf {} E=\{a,b,c\}$ tarkoittaa $\mathbf {} B(a)=1,B(b)=0$ ja $\mathbf {} B(c)=1$ joukkoa $\mathbf {} \{a,c\}$. Tästä seuraa se, että joukkojen joukko-opillisten operaatioiden voidaan tulkita tapahtuvan pisteittäin bitteihin sovellettavien lausekalkyylin $\mathbf {} \lor ,\land$ ja $\mathbf {} \neg$ avulla, jolloin esimerkiksi unionia vastaa "pistebiteittäin" sovellettava $\mathbf {} \lor$, sillä unioniin tullakseen riittää, että piste kuuluu edes toiseen joukoista, ja vastaavasti $\mathbf {} \lor$ antaa bittiarvon $\mathbf {} 1$, jos edes toinen bitti on $\mathbf {} 1$. Äärettömissä eli äärettömän monta alkiota omaavissa Boolen algebroissa "bittitulkinnassa" on kuitenkin se ongelma, että eri pisteisiin liitettäviä bittejä ei välttämättä voida valita toisistaan riippumattomasti, sillä riippumattomasti valittaessa alkioina käytettäviksi osajoukoiksi saataisiin kaikki perusjoukon osajoukot, mikä ei seuraavan alakappaleen mukaan ole aina mahdollista. Kuitenkin äärellisen monta alkiota omaavalle Boolen algebralle löytyy "Äärellisistä Boolen algebroista"-alakappaleen mukaisesti aina kaikki osajoukot käyttävä joukko-opillinen tulkinta, jolloin pisteisiin liitettävät bitit voidaan valita toisistaan riippumattomasti.

Joukko-opillisen Boolen algebran alkioina käyttämät osajoukot

Jos joukko-opillisessa tulkinnassa mielivaltaisesti valitun perusjoukon $\mathbf {} E$ kaikki osajoukot otetaan alkioiksi, saadaan varmasti Boolen algebra, mutta on huomattava, että on olemassa Boolen algebroja, joiden yhdessäkään joukko-opillisessa esityksessä ei voida hyväksyä alkioiksi kaikkia käytetyn perusjoukon osajoukkoja, vaan algebran alkioina on vain osa niistä. Tämä seuraa siitä, että kaikkien osajoukkojen joukossa on myös perusjoukon yksittäisistä $\mathbf {} p$-pisteistä koostuvat $\mathbf {} \{p\}$-joukot, jotka ovat selvästi atomeja eli sellaisia Boolen algebran alkioiksi hyväksyttyjä epätyhjiä osajoukkoja $\mathbf {} A$, joilla kaikilla alkioiksi hyväksytyillä osajoukoilla $\mathbf {} P$ pätee se, että $\mathbf {} A\cap P=A$ tai $\mathbf {} A\cap P=\emptyset$. Alkion atomi-ominaisuus säilyy isomorfismeissa, eli atomi-alkion vastine on myös atomi siinä Boolen algebrassa, joka on isomorfinen alkuperäisen Boolen algebran kanssa. On kuitenkin olemassa myös Boolen algebroja, joiden alkioista yksikään ei ole atomi, ja tällainen Boolen algebra ei siis voi olla isomorfisesti sama kuin sellainen Boolen algebra, jonka joukko-opillinen esitys ottaa alkioiksi kaikki osajoukot, sillä edellä todettiin, että kaikki osajoukot käyttävissä Boolen algebroissa on atomeja.

Esimerkki atomittomasta Boolen algebrasta

Atomittomasta Boolen algebrasta saamme esimerkin valitsemalla $\mathbf {} E=[0,1)$ (Perusjoukkona $\mathbf {} E$ on nyt siis puoliavoin reaalilukuväli.) ja ottamalla alkioiksi ne osajoukot, jotka saadaan valitsemalla ensin $\mathbf {} n\in \{1,2,3,\cdots \}$ ja ottamalla sitten jokin unioni ("tyhjä unioni" antaa tyhjän joukon) muotoa $\mathbf {} [(m)/2^{n},(m+1)/2^{n})$ olevista erillisistä puoliavoimista reaalilukuväleistä, missä $\mathbf {} m\in \{0,\cdots ,2^{n}-1\}$. Esimerkiksi joukko

$\mathbf {} {\Big [}[1/2^{4},2/2^{4})\cup [10/2^{4},11/2^{4})\cup [11/2^{4},12/2^{4}){\Big ]}$

on tämän Boolen algebran alkio, joka on saatu unionina kolmesta annettua muotoa olevasta puoliavoimesta reaalilukuvälistä. Kyseessä on todella Boolen algebra, sillä tällaisiin joukkoihin sovelletut operaatiot antavat edelleen kyseistä muotoa olevia $\mathbf {} E$:n osajoukkoja, mikä nähdään tarkastelemalla operaatiossa mukana olevia joukkoja suurimman niissä käytetyn $\mathbf {} n$-arvon mukaisina. Esimerkiksi

$\mathbf {} {\Big [}[2/2^{2},3/2^{2}){\Big ]}\cap {\Big [}[3/2^{3},4/2^{3})\cup [4/2^{3},5/2^{3})\cup [6/2^{3},7/2^{3}){\Big ]}$ $\mathbf {} ={\Big [}[4/2^{3},5/2^{3})\cup [5/2^{3},6/2^{3}){\Big ]}\cap {\Big [}[3/2^{3},4/2^{3})\cup [4/2^{3},5/2^{3})\cup [6/2^{3},7/2^{3}){\Big ]}={\Big [}[4/2^{3},5/2^{3}){\Big ]},$

missä leikkauksen ensimmäinen joukkokin on nyt tulkittu hienomman $\mathbf {} 1/2^{3}$-jaon mukaisena. Yksikään tällainen epätyhjä joukko ei ole tämän Boolen algebran atomi, sillä jokaisessa joukossa $\mathbf {} A$ on käytetty jotain tiettyä $\mathbf {} n$-arvoa, jota voidaan aina kasvattaa yhdellä ja näin "hienontamalla" voidaan ottaa alkuperäisen joukon aito epätyhjä osajoukko, joka $\mathbf {} P$:ksi ottamalla nähdään, että $\mathbf {} A$ ei toteuta atomin määritelmää, sillä nyt (koska $\mathbf {} \emptyset \subset P\subset A$) $\mathbf {} A\cap P=P\neq \emptyset ,A$. Esimerkiksi

$\mathbf {} \emptyset \subset {\Big [}[203/2^{(7+1)},204/2^{(7+1)}){\Big ]}\subset {\Big [}[202/2^{(7+1)},203/2^{(7+1)})\cup [203/2^{(7+1)},204/2^{(7+1)}){\Big ]}={\Big [}[101/2^{7},102/2^{7}){\Big ]}.$

Äärellisistä Boolen algebroista

Boolen algebran sanotaan olevan äärellinen, jos sen alkioiden määrä on äärellinen. Äärellisille Boolen algebroille saadaan hyvin yksinkertainen joukko-opillinen esitysmuoto, sillä silloin voidaan perusjoukoksi $\mathbf {} E$ valita äärellinen joukko ja Boolen algebran alkioiksi kaikki $\mathbf {} E$:n osajoukot. Äärellisen Boolen algebran kohdalla löydetään siis perusjoukko, josta voidaan käyttää kaikki osajoukot, mikä on yksinkertaisin tilanne. Tästä selvästi seuraa myös, että äärellisen Boolen algebran alkioiden lukumäärä on välttämättä muotoa $\mathbf {} 2^{n}$, missä $\mathbf {} n\in \{1,2,3,\cdots \}$. Yllä esimerkkinä annetussa atomittomassa Boolen algebrassa osajoukko-alkioiden määrä sen sijaan ei ole äärellinen, vaan se on numeroituvasti ääretön.

Joukko-opillisen Boolen algebran yhteys Sigma-algebraan

Joukko-opillista Boolen algebraa vaativampi perusjoukon $\mathbf {} E$ osajoukkojen kokoelma on sigma-algebra. Joukko-opilliselta Boolen algebralta vaaditaan, että alkioksi hyväksytyn osajoukon komplementti on myös alkioksi hyväksytty ja kahden (Tätä kautta induktiivisesti myös äärellisen monen.) alkioksi hyväksytyn osajoukon unioni on myös alkioksi hyväksytty, jolloin De Morganin laeista selvästi seuraa, että sama vaatimus toteutuu myös leikkauksen suhteen. Sigma-algebralta sen sijaan vaaditaan komplementti-ehto ja se, että numeroituvasti äärettömän monen (Boolen algebralla vain kahden) alkioksi hyväksytyn osajoukon unioni on myös alkioksi hyväksytty osajoukko, mikä on vaativampi ehto. Vastaavasti De Morganin laeista seuraa sigma-algebran kohdalla, että sigma-algebrassa myös numeroituvasti äärettömän monen alkioksi hyväksytyn osajoukon leikkaus on alkioksi hyväksytty osajoukko. Jokainen sigma-algebra on selvästi Boolen algebra, mutta käänteinen ei päde. Esimerkiksi yllä esitetty atomiton Boolen algebra ei ole sigma-algebra, sillä

$\mathbf {} {\Big [}[0/2^{1},1/2^{1}){\Big ]}\cap {\Big [}[0/2^{2},1/2^{2}){\Big ]}\cap {\Big [}[0/2^{3},1/2^{3}){\Big ]}\cap {\Big [}[0/2^{4},1/2^{4}){\Big ]}\cap \cdots =\{0\},$

mutta $\mathbf {} \{0\}$ koostuu vain yhdestä $\mathbf {} E=[0,1)$-perusjoukon pisteestä ($\mathbf {} 0$), eikä se siis selvästikään voi olla alkioksi hyväksytty $\mathbf {} E$:n osajoukko, eli sigma-algebraa koskeva numeroituvasti äärettömän monen alkion leikkausta koskeva sääntö ei nyt toteudu, eli kyseinen Boolen algebra ei ole sigma-algebra.

Kuviollinen esitys

Venn-diagrammit leikkaukselle, unionille ja komplementille.

Venn-diagrammia voidaan käyttää kuviolliseen esitykseen.

Katso myös

• Tietokonearitmetiikka
• Looginen portti
• Totuusfunktio
• Totuustaulu
• Toistorakenne
• Ikuinen silmukka
• Valoportti

Aiheesta muualla

• Kuvia tai muita tiedostoja aiheesta Boolen algebra Wikimedia Commonsissa