Tarkastellaan seuraavaksi kahta hilaa, jotka ovat tyypillisiä esimerkkejä ei-distributiivisista hiloista. Kuvassa 7 on esitetty hila N5. Hilan Losajoukkoa A kutsutaan tästä eteenpäin viisikulmioksi, jos ja vain jos se on alihila, joka on isomorfinen hilan N5 kanssa. [4, s. 59]
◦ 1
z ◦
◦ x
y ◦
◦ 0
Kuva 7: Hila N5 eli "Viisikulmio"@
Kuvassa 8 on puolestaan esitetty hilaM3. Hilan L osajoukkoa B kutsu-taan tästä eteenpäin timantiksi, jos ja vain jos se on alihila, joka on isomor-finen hilan M3 kanssa. [4, s. 59]
◦ 1
x ◦ ◦ y ◦ z
◦ 0
Kuva 8: HilaM3 eli "Timantti"@
Näiden hilojen ei-distributiivisuus on helppo todeta, sillä hilassaN5 y∨(z∧x) =y∨0 = y
ja
(y∨z)∧(y∨x) =z∧1 =z, eli y∨(z∧x)̸= (y∨z)∧(y∨x).
Vastaavasti hilassaM3
x∨(y∧z) =x∨0 = x ja
(x∨y)∧(x∨z) = 1∧1 = 1 eli x∨(y∧z)̸= (x∨y)∧(x∨z). [3, s. 25]
Lisäksi hilaN5 ei ole modulaarinen, silläy≤z, muttay∨(x∧z) =y∨0 = y ̸=z = 1∧z = (y∨x)∧z [3, s. 27].
Hilat N5 ja M3 ovat olennaisia tutkittaessa hilojen modulaarisuutta ja distributiivisuutta, kuten lauseita 5.10 ja 5.11 tarkasteltaessa huomataan.
Lause 5.10. Hila L on modulaarinen jos ja vain jos se ei sisällä alihilaa, joka on isomorfisesti viisikulmio. [4, s. 59]
Todistus. Jos hilaLon modulaarinen, niin lemman 5.5 mukaan sen jokainen alihila on myös modulaarinen. Hila N5 ei ole modulaarinen, joten se ei voi olla hilan L alihila.
Oletetaan, että hilaLei ole modulaarinen, jolloin on olemassa hilan Lalkiot x, y ja z siten, että x≤z ja x∨(y∧z)̸= (x∨y)∧z. Siispä lauseen 5.2 iv) perusteella x∨(y∧z)<(x∨y)∧z.
Osoitetaan, että alkiot y∧z,y,x∨(y∧z),(x∨y)∧z ja x∨y muodostavat Kuvan 9 mukaisen hilan L alihilan, joka on isomorfisesti viisikulmio. On siis osoitettava, että nämä alkiot ovat erillisiä ja että niiden supremumit ja infimumit ovat Kuvan 9 mukaiset.
◦ x∨y
(x∨y)∧z ◦
◦ y
x∨(y∧z) ◦
◦y∧z
Kuva 9:
Todistetaan ensin alkioiden erillisyys. On selvää, että epäyhtälöt y∧z ≤y≤x∨y
ja
y∧z ≤x∨(y∧z)<(x∨y)∧z ≤x∨y
ovat voimassa. Helpoilla laskutoimituksilla huomataan, että jos edellisissä epäyhtälöissä olisi voimassa yhtäsuuruus jossakin kohtaa, päädytään ristirii-taan x∨(y∧z) = (x∨y)∧z. Näytetään esimerkiksi yksi tapaus: Olkoon y∧z =y. Tällöin
x∨(y∧z) =x∨y.
Toisaalta
(x∨y)∧z ≤x∨y=x∨(y∧z),
joka on ristiriita. Vastaavaan ristiriitaan päädytään, jos oletetaan, että y on vertailullinen (ks. Määritelmä 3.6) joko alkiox∨(y∧z)tai alkion(x∨y)∧z kanssa. Näytetään esimerkiksi tapaus, jossa oletetaan, ettäyon vertailullinen alkion x∨(y∧z) kanssa, eli y ≤x∨(y∧z) tai x∨(y∧z)≤ y. Näin ollen näiden viiden alkion on oltava erillisiä ja niiden järjestyssuhteet ovat Kuvan 9 mukaiset.
Seuraavaksi osoitetaan, että Kuvan 9 alkioparien supremumit ja infimumit ovat kuvan mukaiset. Keskenään vertailullisten alkioparien supremumit ja infimumit ovat selvästi Kuvan 9 mukaiset. Käydään läpi vertailukelvottomien alkioparien supremumit ja infimumit. Liitännäisyyttä, vaihdannaisuutta ja absorptiolakeja apuna käyttämällä saadaan supremumit ja infimumit ovat Kuvan 9 mukaiset. Näin ollen nämä alkiot muodostavat hilan L alihilan, joka on isomorfisesti viisikulmio. [3, s. 28-31]
□
Lause 5.11. HilaLon distributiivinen jos ja vain jos se ei sisällä alihilanaan kumpaakaan hiloista, joka on isomorfisesti timantti tai viisikulmio. [3, s.29]
Todistus. Jos hila L on distributiivinen, niin silloin jokainen sen alihila on myös distributiivinen, kuten Lemmassa 5.8 on osoitettu. Hilat N5 ja M3 ei-vät ole distributiivisia, joten ne eiei-vät voi olla hilan Lalihiloja.
Oletetaan, että hila L ei ole distributiivinen. Jos L ei ole myöskään modu-laarinen, niin silloin Lauseen 5.10 perusteella hila N5 on hilan Lalihila.
Käydään vielä läpi tapaus, jossaLon modulaarinen, muttei distributiivinen.
Tällöin on olemassa sellaiset alkiotx, y, z ∈L, ettäx∨(y∧z)̸= (x∨y)∧(x∨z).
Lauseen 5.2 i) perusteella x∨(y∧z)<(x∨y)∧(x∨z). Osoitetaan, että on olemassa hilan Lalihila, joka on isomorfisesti timantti kuvan 10
◦ b
x1 ◦ ◦ y1 ◦z1
◦ a Kuva 10:
mukaisesti.
Tässä
a = (x∧y)∨(y∧z)∨(z∧x), b = (x∨y)∧(y∨z)∧(z∨x), x1 =a∨(b∧x),
y1 =a∨(b∧y), z1 =a∨(b∧z).
On siis osoitettava, että kaikkien alihilan alkioparien supremumit ja infi-mumit ovat kuvan 10 mukaiset, ja että kaikki alkiot ovat erillisiä. Todistetaan ensin, että supremumit ja infimumit ovat kuvan 10 mukaiset. Helposti näh-dään, että a ≤ a∨(b∧x) = x1. Lauseen 5.2 iii) perusteella a ≤ b. Tästä seuraa Lemmaa 4.12 ja absorptiolakia käyttämällä
a≤x1 =a∨(b∧x)≤b∨(b∧x) = b.
Vastaavalla päättelyllä myösa≤y1 ≤bjaa≤z1 ≤b. Näin ollen supremumit ja infimumit ovat oikein niillä alkiopareilla, joissa ainakin toinen alkio on a
tai b. Osoitetaan seuraavaksi, että
x1∧y1 =y1∧z1 =x1∧z1 =a ja
x1∨y1 =y1∨z1 =x1∨z1 =b.
Käydään tapaus x1∧y1 =a läpi yksityiskohtaisesti, muut osoitetaan vastaa-vasti. Voidaan päätellä, että
x1∧y1 = (a∨(b∧x))∧(a∨(b∧y))
=a∨[(b∧x)∧(a∨(b∧y))] (L5’), missä a≤a∨(b∧y)
=a∨[(b∧x)∧(a∨(y∧b))] (L2)
=a∨[(b∧x)∧((a∨y)∧b)] (L5’), missä a ≤b
=a∨[((b∧x)∧b)∧(a∨y)] (L2), (L3)
=a∨((b∧x)∧(a∨y)). (L2), (L3), (L1)
Tässä alkiolle b∧xsaadaan esitys
b∧x=x∧b (L2)
=x∧[(x∨y)∧(y∨z)∧(z∨x)]
= [x∧(x∨y)]∧[x∧(z∨x)]∧[x∧(y∨z)] (L2), (L3), (L6)
=x∧x∧(x∧(y∨z)) (L4
=x∧(y∨z). (L1)
Vastaavasti saadaan, että a∨y=y∨(x∧z). Jatketaan nyt päättelyä
a∨((b∧x)∧(a∨y)) = a∨[(x∧(y∨z))∧(y∨(x∧z))] (L2), (L6), (L4)
=a∨[x∧[(y∨z)∧(y∨(x∧z))]] (L3)
=a∨[x∧((y∨(x∧z))∧(y∨z))] (L2)
=a∨[x∧[y∨((x∧z)∧(y∨z))]] (L5’), missä y≤y∨z
=a∨[x∧(y∨(x∧z))] (L3), (L4)
=a∨((x∧y)∨(x∧z)) (L5)
=a.
Nyt on todistettu, että kaikkien alkioparien supremumit ja infimumit ovat Kuvan 10 mukaiset. Todistetaan seuraavaksi, että alkiota,b,x1,y1 jaz1 ovat erillisiä. Ensinnäkin a ja b eivät voi olla samoja, koska tällöin olisi
x∨(y∧z) = x∨((x∧y)∨(y∧z)∨(z∧x)) (L4)
=x∨a
=x∨b
=x∨((y∨z)∧((x∨y)∧(x∨z)))
= (x∨(y∨z))∧((x∨y)∧(x∨z)) (L5’), missä x≤((x∨y)∧(x∨z))
= (x∨y)∧(x∨z), mikä on vastoin oletusta.
Seuraavaksi havaitaan, että x1 ja y1 eivät voi olla samoja, sillä tällöin a=x1∧y1 =x1∧x1 =x1 =x1∨x1 =x1∨y1 =b,
mikä todettiin edellä mahdottomaksi. Vastaavasti on mahdotonta, että olisi y1 = z1 tai z1 = x1. Edelleen, jos a = x1, niin aiemmin todettujen ehtojen a ≤y1, a≤z1 ja x1∨y1 =b seurauksena
y1 =a∨y1 =x1∨y1 =b =x1∨z1 =a∨z1 =z1,
mikä on edellisen perusteella ristiriidassa. Vastaavasti myös a=y1 ja a=z1 johtavat ristiriitaan. Lopuksi, jos b =x1, niin ehdon y1 ≤b seurauksena
y1 =y1∧b =y1∧x1 =a,
mikä on jälleen ristiriita. Samalla tavoin myös b =y1 ja b =z1 ovat mahdot-tomia. Siispä on todistettu, että alkiot a, b, x1, y1 ja z1 ovat erillisiä. Nämä alkiot siis muodostavat hilan Lalihilan, joka on isomorfisesti timantti. [3, s.
29-31] □
6 Boolen algebrat
Tässä luvussa esitellään Boolen algebrat. Lisäksi esitellään Boolen rengas ja konstruoidaan Boolen algebran avulla Boolen rengas ja päin vastoin.
6.1 Boolen algebrat
Tässä aliluvussa käsitellään Boolen algebroita ja niiden ominaisuuksia sekä esitetään erilaisia määrittelyjä käsitteelle. Aluksi tarkastellaan mitä komple-mentti tarkoittaa hilassa.
Määritelmä 6.1. HilassaL, joka sisältää alkiot 0 ja 1, alkionx∈L komple-mentti on alkio y ∈ L siten, että x∧y = 0 ja x∨y = 1. Hilaa L sanotaan komplementoiduksi, jos kaikilla sen alkioilla on komplementti. [2, s. 16]
Määritelmä 6.2. Boolen algebra on komplementoitu distributiivinen hila.
[7, s. 406]
Määritelmästä 6.2 nähdään suoraan, että Boolen algebra sisältää aina suurimman alkion 1 ja pienimmäin alkion 0.
Lause 6.3. Kaikissa Boolen algebroissa jokaisella alkiolla x on tasan yksi komplementti x′, eli ehdoista x∨c= 1 ja x∧c= 0 saadaan c=x′. Lisäksi (L8) x∧x′ = 0 ja x∨x′ = 1,
(L9) (x′)′ =x,
(L10) (x∧y)′ =x′∨y′ ja (x∨y)′ =x′∧y′.
Todistus. [2, s. 17] [7, s.408-409] Määritelmien 6.1 ja 6.2 perusteella (L8) on selvästi tosi.
Komplementtien yksikäsitteisyys seuraa ehdosta (L8) ja Lauseesta 5.9. Jos x∨c= 1 ja x∧c= 0, niin x∨c=x∨x′ ja x∧c=x∧x′. Näin ollen c=x′ Lauseen 5.9 perusteella.
Käyttämällä ehtoa (L8) ja komplementin yksikäsitteisyyttä saadaan: Josx′∨ x= 1 ja x′∧x= 0, niin x= (x′)′ eli (L9) pätee.
Ehto (L10) voidaan osoittaa soveltamalla komplementin yksikäsitteisyyttä.
Riittää osoittaa, että (x∨y)∨(x′∧y′) = 1 ja (x∨y)∧(x′ ∧y′) = 0, josta
seuraa, että x′∧y′ = (x∨y)′. Oletuksia käyttäen voidaan päätellä (x∨y)∨(x′∧y′) =x∨(y∨(x′∧y′)) (L3)
=x∨((y∨x′)∧(y∨y′) (L6’)
=x∨((y∨x′)∧1) (L8)
=x∨(x′∨y) Lemma 4.11, (L2)
= (x∨x′)∨y (L3)
= 1∨y (L8)
= 1 Lemma 4.11
ja toisaalta
(x∨y)∧(x′∧y′) = (x′∧y′)∧(x∨y) (L2)
= ((x′∧y′)∧x)∨((x′ ∧y′)∧y) (L6)
= ((x′∧x)∧y′)∨(x′∧(y′∧y)) (L2), (L3)
= (0∧y′)∨(x′∧0) (L8)
= (0∨0) Lemma 4.11
= 0. (L1)
Duaalisuuden nojalla toinen osa ehdosta (L10) osoitetaan vastaavasti.
□ Lauseessa 6.3 esitetyt ehdot ovat tärkeitä ominaisuuksia Boolen algebrois-sa. Lähteessä [2, s. 18] Boolen algebra on määritelty algebraksi, joka sisältää lait (L1)-(L10) toteuttavat operaatiot ∨, ∧ja ′.
Lauseessa 6.4 esitellään lisää ominaisuuksia, joita Boolen algebroilla on.
Näitä ominaisuuksia tarvitaan Lauseen 6.5 todistuksessa.
Lause 6.4. [7, s. 408] Jos B on Boolen algebra ja x, y, z ∈B, niin (1) x∨1 = 1 ja x∧0 = 0.
(2) 0′ = 1 ja 1′ = 0.
Todistus. (1) Lemmasta 4.11 seuraa, että x∨1 = 1 ja x∧0 = 0 pätevät Boolen algebrassa, sillä Boolen algebra on hila ja edelleen hila on osittain järjestetty joukko.
(2) Komplementin määritelmän mukaan alkion 0komplementti on alkio y∈ B siten, että 0∧y = 0 ja 0∨y = 1. Koska 0 ≤ 1 saadaan 0∧y = 0∧1 ja 0∨y = 0∨1. Nyt Lauseen 5.9 mukaan y = 1 eli alkion 0 komplementti on 0′ = 1. Vastaavasti osoitetaan, että1′ = 0. □
Lause 6.5. Epätyhjä joukkoB on Boolen algebra jos ja vain jos on olemassa binäärioperaatiot ∨ ja ∧ siten, että ehdot (1)-(3) ovat voimassa:
(1) Operaatiot ∨ ja ∧ toteuttavat ehdot (L2), (L3), (L6) ja (L6)’ eli ovat vaihdannaisia, liitännäisiä ja distributiivisia.
(2) On olemassa alkiot 1,0∈B siten, että
x∨0 =x ja x∧1 =x kaikilla x∈B.
(3) Kaikille x∈B on olemassa x′ ∈B siten, että x∨x′ = 1 ja x∧x′ = 0.
Todistus. [7, s. 407-408] Jos B on Boolen algebra määritelmän mukaan se on komplementoitu distributiivinen hila, joka sisältää pienimmän alkion 0 ja suurimman alkion 1 eli Lemmojen 4.9 ja 4.11 sekä Määritelmien 5.7 ja 6.1 perusteella (1)-(3) ovat voimassa, kun x∨y = sup{x, y},x∧y= inf{x, y}ja x′ on alkion x komplementti.
Käänteisesti, jos B on ehdon (1) täyttävillä binäärioperaatioilla ∨ ja ∧ va-rustettu joukko, niin B on distributiivinen hila Määritelmien 4.10 ja 5.7 pe-rusteella, kunhan se on idempotentti (L1) ja toteuttaa absorptiolait (L4).
Idempotenttisuus on voimassa, koska
x=x∨0 (2)
=x∨(x′∧x) (3), (L2)
= (x∨x′)∧(x∨x) (L6’)
= 1∧(x∨x) (3)
=x∨x. (2)
Vastaavasti näytetään, ettäx=x∧x. Ensimmäinen absorptiolaki pätee, sillä x∧(x∨y) = (x∨0)∧(x∨y) (2)
=x∨(0∧y) (L6)
=x∨(y∧(y∧y′)) (L2), (3)
=x∨((y∧y)∧y′) (L3)
=x∨(y∧y′) (L1)
=x∨0 (3)
=x (2)
Vastaavasti osoitetaan toisen absorptiolain voimassaolo. Näin ollen B on di-stributiivinen hila, jossa x≤y tarkoittaa x∧y=xLauseen 4.13 kohdan ii) perusteella.
Vielä on osoitettava, että hila B on komplementoitu. Osoitetaan, että hilassa B on olemassa suurin ja pienin alkio. Jos x ∈ B, niin x∧ 1 = x kohdan (2) perusteella. Näin ollenx≤1kaikillax∈B. Lemman 3.17 mukaan x∨y=y ja x∧y=x ovat ekvivalentteja. Näin ollen vaihdannaisuudesta ja kohdasta (2) eli 0∨x=xseuraa, että 0≤xkaikilla x∈B. Siis1 on suurin alkio ja 0 pienin alkio joukossa B, joten B on komplementoitu hila kohdan (3) perustella ja näin ollen Boolen algebra.
□ Lausetta 6.5 käytetään usein Boolen algebran määritelmänä, ks. [8, s.
130-131].
Määritelmä 6.6. Boolen algebran A (Boolen) alialgebra B on epätyhjä os-ajoukko, jossa mille tahansa alkiolle x, y ∈B myös(x∨y),(x∧y), x′ ∈B.