Hilateriasta Boolen algebroihin ja propositiologiikkaan
Pro Gradu -tutkielma Hanna Kauppinen 260373
Fysiikan ja matematiikan laitos Itä-Suomen yliopisto
15.5.2019
Tiivistelmä
Tämä tutkielma käsittelee hilateorian perusteita ja erityisesti erästä tiettyä hilaa, jota kutsutaan Boolen algebraksi, sekä sen yhteyttä propositiologiik- kaan.
Toisessa luvussa käsitellään lyhyesti hilateorian historiaa.
Kolmannessa luvussa tutustutaan osittain järjestettyihin joukkoihin, esi- tellään duaalisuusperiaate ja esitetään supremumin ja infimumin määritelmä.
Nämä kaikki ovat tärkeitä käsitteitä hiloja tarkasteltaessa.
Neljännessä luvussa hilat määritellään kahdella tavalla, ensinnäkin osit- tain järjestettynä joukkona ja toiseksi algebrallisena rakenteena, jossa supre- mum ja infimum ovat binäärioperaatioita. Luvussa esitetään myös muita hila- teorian perusteita ja näytetään, kuinka hiloja voidaan havainnollistaa Hasse- kaavioiden avulla.
Viidennessä luvussa esitellään modulaariset ja distributiiviset hilat, jotka ovat merkittäviä hilojen erityistapauksia. Näitä hilatyyppejä luonnehditaan viisikulmioksi ja timantiksi kutsuttujen alihilojen avulla. Työssä esitetään todistukset lauseille, jotka helpottavat modulaaristen ja distributiivisten hi- lojen tunnistamista.
Kuudennessa luvussa esitellään Boolen algebrat sekä näihin liittyviä tär- keitä ominaisuuksia. Boolen algebralle esitetään vaihtoehtoisia määrittelyta- poja. Tarkastelun kohteena on myös Boolen rengas ja luvun lopuksi esitetään kuinka Boolen algebran avulla voidaan konstruoida Boolen rengas ja kään- teisesti.
Boolen algebralle on olemassa useita sovelluksia, joista tämän tutkielman seitsemännessä luvussa esitetään esimerkkinä propositiologiikka. Luvussa esi- tellään propositiologiikan perusteet ja todistetaan väittämien joukon varus- tettuna loogisilla konnektiiveilla ja negaatiolla olevan Boolen algebra.
Abstract
This thesis concerns lattice theory. In particular, a lattice called Boolean algebra as well as its connection to propositional logic are considered.
Chapter two concerns briefly the history of lattice theory.
Chapter three introduces partially ordered sets, the principle of duality as well as supremum and infimum. All of these are important concepts when considering lattices.
Chapter four introduces lattices with two definitons. Firstly, as partially ordered set and secondly, as an algebraic structure with two binary opera- tions, supremum and infimum. This chapter also introduces basics of lattice theory and shows how lattices can be described with Hasse-diagrams.
Chapter five concerns modular and distributive lattices that are sig- nificant lattices. A sublattice called diamond is typical example of non- modular and non-distributive lattices. Also a sublattice called pentagon is non-modular. With these two sublattices it is easier to identify distributive and modular lattices.
Chapter six introduces Boolean algebras and important properties of them. There are at least two to define Boolean algebras and this thesis int- roduces both of them. Boolean rings are studied at the end of the chapter and it is shown how to construct a Boolean algebra from a Boolean ring and conversely.
Chapter seven introduces one of the many applications of Boolen algebra, propositional logic. This chapter shows why the set of propositions with lo- gical connectives and negation is Boolean algebra.
Sisältö
1 Johdanto 1
2 Hilateorian historiasta ja merkityksestä 2
3 Osittain järjestetty joukko 3
3.1 Relaatiot . . . 3
3.2 Osittain järjestetty joukko . . . 3
3.3 Isomorfismi ja duaalisuus . . . 5
3.4 Supremum ja infimum . . . 6
4 Hilat 9 4.1 Hilat osittain järjestettyinä joukkoina . . . 9
4.2 Hilojen kuvaaminen Hasse-kaaviolla . . . 11
4.3 Hilat algebrallisina rakenteina . . . 14
5 Modulaariset ja distributiiviset hilat 18 5.1 Hilojen epäyhtälöitä . . . 18
5.2 Modulaariset hilat . . . 20
5.3 Distributiiviset hilat . . . 20
5.4 Viisikulmiot ja timantit . . . 22
6 Boolen algebrat 28 6.1 Boolen algebrat . . . 28
6.2 Boolen rengas . . . 31
7 Propositiologiikka 37
1 Johdanto
Tämä tutkielma käsittelee hilateorian perusteita, sekä tärkeitä hilojen erikois- tapauksia, kuten modulaarisia ja distributiivisia hiloja sekä Boolen algebraa.
Lisäksi näytetään Boolen algebran yhteys propositiologiikkaan.
Tutkielmassa esitetään aluksi hilateorian historiaa Boolen algebrasta ylei- sen hilateorian kehitykseen. Tässä työssä lähdetään päinvastoin kehittämään Boolen algebran määritelmää hilateorian perusteista alkaen. Lopulta tarkas- tellaan kuinka Boolen algebrasta voidaan kontruoida Boolen rengas ja päin- vastoin, sekä kuinka propositiologiikka liittyy Boolen algebraan.
Hilateoriaan liittyviä tärkeitä käsitteitä ovat osittain järjestetyt joukot, duaalisuusperiaate sekä supremum ja infimum. Hilat voidaan määritellä se- kä osittain järjestettyjen joukkojen että binäärioperaatioilla varustetun al- gebrallisen rakenteen näkökulmasta. Hiloja voidaan havainnollistaa Hasse- kaavioiden avulla.
Modulaariset ja distributiiviset hilat ovat hilojen tärkeitä erikoistapauk- sia, joista erityisesti distributiivisuutta tarvitaan Boolen algebran määrittä- miseksi. Boolen algebra on komplementoitu distributiivinen hila. Tästä näkö- kulmasta voidaan tarkastella useita Boolen algebralle tärkeitä ominaisuuksia.
2 Hilateorian historiasta ja merkityksestä
Hilateoria sai alkunsa Boolen algebrasta, joka oli ensimmäinen esitetty hilara- kenne. 1800-luvun puolivälissä George Boole loi formaalin propositiologiikan pyrkiessään esittämään logiikkaa algebrallisin merkinnöin ja menetelmin. [1]
Boolen työtä jatkoivat muun muassa Charles Peirce ja Ernst Schröder.
Peirce teki parannuksia Boolen logiikkaan erityisesti sen aksioomien suhteen.
Schröder puolestaan edesauttoi hilojen tutkimiseen johtavaa kehitystä osoit- tamalla, että osittelulait ovat riippumattomia muista laeista. [1]
Myös Richard Dedekind edesauttoi hilateorian syntyä tutkimalla algebral- listen lukujen ideaaleja ja moduleita. Dedekindin lähtökohta oli hyvin erilai- nen kuin edellä mainituilla matemaatikoilla, mutta hänkin päätyi hilan kä- sitteeseen ja esitteli myös modulaariset hilat. [1]
1930-luvulle asti hilateoriaa tutkittiin lähinnä Boolen algebrojen näkökul- masta. Garrett Birkhoff julkaisi vuonna 1940 teoksensa Lattice Theory, jossa hän esitteli hilateorian merkinnät, sen yhteneväisyydet muihin matematiikan osa-alueisiin sekä sen sovelluksia. Birkhoffin tutkimuksia pidettiin merkittä- vinä ja hilateorian tutkimus laajentui valtavasti. Birkhoff julkaisi vielä kaksi laitosta kirjastaan, joista kolmas [2] on tämän tutkielman tärkeä lähde. [1]
Toinen merkittävä hilateorin tutkija on George Grätzer. Grätzer pyrki sy- ventämään hilateoriaa ja julkaisi tutkimustensa pohjalta muun muassa teok- sen General Lattice Theory [4] vuonna 1978, joka on merkittävä lähde tässä tutkielmassa. [1]
Hilateorian merkitys ei ole sen historian aikana ollut aina selvä. Boole ei saanut alkuun paljon kannattajia ja Schröderin ja Dedekindin tutkimukset eivät johtaneet jatkotutkimuksiin, koska abstraktien rakenteiden tutkiminen ei ollut muodissa 1800-luvun puolivälissä. Grätzer toivoi, että hilateoria voisi kiinnostaa lukijoita sen sisäisen kauneuden tähden. [1]
On kuitenkin perusteita hilateorian tärkeydestä sekä matematiikan että erilaisten sovellusten kannalta. Matematiikan puolella hilojen merkitys tulee esille muun muassa universaalialgebran puolella. Esimerkiksi alialgebrojen ja algebran kongruenssien struktuurit muodostavat hilan. Hilateorian tunte- muksesta on myös hyötyä, kun tarkastellaan rakenteita, jotka omaavat ope- raatioiden lisäksi myös jonkinlaisen sisäisen järjestyksen. Tällaisia rakenteita ovat esimerkiksi ryhmät, renkaat ja vektoriavaruudet. [3, s.iii-iv]
Käytännön sovelluksia hilateorialle löytyy muun muassa kuvankäsittelyn, teoreettisen tietojenkäsittelyn, virtapiirien ja kvanttimekaniikan alueilta. [1]
[3, s.iii-iv]
3 Osittain järjestetty joukko
Tässä luvussa käsitellään hiloihin liittyviä tärkeitä käsitteitä, joita tarvitaan luvussa 4 hilateorian perusteiden pohjatiedoksi. Ensimmäiseksi esitellään osittain järjestetty joukko relaationa, jolla on tiettyjä ominaisuuksia. Osittain järjestettyjä joukkoja voidaan havainnollistaa Hasse-kaavioiden avulla. Seu- raavaksi luvussa esitetään duaalisuusperiaate, joka on hyödyllinen apuväline hiloihin liittyvissä todistuksissa. Lopuksi käydään läpi käsitteet supremum ja infimum, joiden avulla luvussa 4 määritellään hilat vaihtoehtoisena mää- ritelmänä osittain järjestettyihin joukkoihin pohjautuvalle määritelmälle.
3.1 Relaatiot
Määritellään aluksi binäärirelaatio, siihen liittyviä tärkeitä ominaisuuksia se- kä käänteisrelaatio.
Määritelmä 3.1. Olkoot X epätyhjä joukko. Jos R ⊆ X ×X, niin R on binäärirelaatio joukon X yli. Jos alkio x ∈ X on relaatiossa alkion y ∈ X kanssa, merkitään xRy tai (x, y)∈R. [6, s.11]
Määritelmä 3.2. [6, s. 12] Olkoon R ⊆ X ×X binäärirelaatio. Binäärire- laatio R on
1. refleksiivinen, jos kaikilla x∈X pätee xRx.
2. symmetrinen, jos kaikilla x, y ∈X pätee xRy⇒yRx
3. antisymmetrinen, jos kaikilla x, y ∈X pätee xRy∧yRx⇒x=y 4. transitiivinen, jos kaikilla x, y, z ∈X pätee xRy∧yRz ⇒xRz
Määritelmä 3.3. BinäärirelaationR käänteisrelaatio on R¯ siten, että xRy¯ jos ja vain jos yRx. [2, s. 3]
3.2 Osittain järjestetty joukko
Osittain järjestetty joukko koostuu joukosta alkioita ja järjestysrelaatiosta
≤, joka määrittelee alkioiden järjestyksen. Merkintä a ≤ b tarkoittaa "a on pienempi tai yhtä suuri kuin b"tai toisaalta "b on suurempi tai yhtä suuri kuin a". Voidaan myös sanoa, että "alkio a on alkion b alla"tai "alkio b on alkion a yllä". [6, s. 14]
Määritelmä 3.4. [6, s. 13-14](P,≤)onosittain järjestetty joukko, josP ̸=∅ ja ≤ on binäärirelaatio, jolle kaikilla a, b, c∈P
1. a≤a, (refleksiivisyys)
2. josa≤b ja b≤a, niin a=b, (antisymmetrisyys) 3. josa≤b ja b≤c, niina ≤c. (transitiivisyys)
Usein sanotaan, että P on osittain järjestetty joukko, jos voidaan olet- taa, että osittainen järjestys on tunnettu. Seuraavaksi esitellään esimerkkejä osittain järjestetyistä joukoista.
Esimerkki 3.5. a) Tarkastellaan joukkoa P(X), joka koostuu kaikista jou- konP osajoukoistaXsisältäen joukonP ja tyhjän joukon∅. JoukkoP(X)ja relaatio ⊆ muodostavat osittain järjestetyn joukon (P(x),⊆), missä A⊆B, A, B ∈P(X), tarkoittaa "joukko A on joukon B osajoukko". [2, s. 1]
b) Positiivisten kokonaislukujen joukkoZ+ ja relaatio m≤n "alkio m jakaa alkion n"muodostavat osittain järjestetyn joukon [2, s. 1]. Osoitetaan tämä käymällä läpi Määritelmän 3.4 ehdot 1-3. Olkoon l, m, n ∈Z+. Jaollisuuden määritelmän mukaan luku n on jaollinen luvulla m, jos on olemassa c ∈ Z siten, että n =mc.
1. Koska m= 1m, niin m≤m.
2. Olkoon m≤ n eli n =mc ja n ≤ m elim = nc. Tämä on totta jos ja vain jos c= 1, joten n=m, eli antisymmetrisyys on voimassa.
3. Olkoon m ≤ n eli n = mc ja n ≤ l eli l =nc. Siispä l = mcc = mc2, missä c2 ∈Z+. Näin ollen m≤l eli transitiivisuus toteutuu.
Toisaalta (Z,≤) ei ole osittain järjestetty joukko, sillä esimerkiksi−1≤1ja 1≤ −1 ja −1̸= 1 eli antisymmetrisyys ei ole voimassa kaikilla alkioilla.
Määritelmä 3.6. Osittain järjestetty joukko on täysin järjestetty, jos 4. joko x≤y tai y≤x. (vertailullisuus)
Tällöin osittain järjestettyä joukkoa kutsutaan ketjuksi. [2, s. 2]
Ketjussa siis kaikki joukon jäsenet ovatvertailullisia. Tarkasteltaessa kah- ta täysin järjestetyn joukon eri jäsentä, voidaan sanoa, että toinen on pienem- pi ja toinen on suurempi. Jos a ja b ovat eivät ole verrattavissa keskenään, ne ovat vertailukelvottomia ja merkitääna||b. [4, s.2]
Esimerkki 3.7. Luonnollisella järjestyksellään varustettuna lukujoukotN,Z ja Q muodostavat ketjun. [3, s. 1]
Seuraavaksi määritellään peittämisrelaatio osittain järjestetyssä joukossa.
Määritelmä 3.8. Osittain järjestetyssä joukossa P ilmaisu "alkio a peittää alkion b", jota merkitään b ≺ a, tarkoittaa, että a > b, a, b ∈ P ja millään x∈P ei pädea > x > b. [2, s.4]
Osittain järjestettyjä joukkoja voidaan havainnollistaa Hasse-kaavioiden avulla. Relaatiosta≺on hyötyä Hasse-kaaviota piirrettäessä. Jokaista alkiota piirretään edustamaan pieni ympyrä ja jos a > b, alkio a piirretään alkion b yläpuolelle. Silloin kun b ≺ a, niin alkioiden a ja b välille piirretään suora viiva. [2, s. 4]
Esimerkki 3.9. Esitetään Hasse-kaavion avulla osittain järjestetty joukko, jossa P ={a, b, c, d, e}sekä b≺a,d ≺b,c≺b, e≺cjae≺d. Kun kaaviota lähdetään piirtämään, esimerkiksib ≺atarkoittaa, ettäapiirretään alkion b yläpuolelle ja näiden välille piirretään viiva. Vastaavasti kaavioon piirretään muut alkiot ja määrättyjen alkioiden välille piirretään viivat. Näin saadaan kuvassa 1 esitetty Hasse-kaavio.
a ◦
b ◦
c ◦ ◦ d
e ◦
Kuva 1: Osittain järjestetyn joukon Hasse-kaavio
3.3 Isomorfismi ja duaalisuus
Määritelmä 3.10. [2, s. 2] Olkoot P ja Q osittain järjestettyjä joukkoja a ∈P jab∈Q. Funktio F :P →Q onjärjestyksen säilyttävä eliisotoninen, jos
a≤b ⇒F(a)≤F(b).
Määritelmä 3.11. Olkoot P ja Q osittain järjestettyjä joukkoja ja a ∈ P ja b ∈Q. Funktio F :P →Q onisomorfismi, jos se on bijektio ja sille pätee
a≤b ⇔F(a)≤F(b).
Jos joukkojen P ja Q välillä on isomorfismi, sanotaan, että ne ovat isomor- fisia ja merkitään P ∼= Q. Isomorfismia joukolta P itselleen sanotaan auto- morfismiksi. [2, s. 2-3]
Kaksi osittain järjestettyä joukkoa ovat isomorfiset jos ja vain jos niille voidaan piirtää identtiset Hasse-kaaviot [3, s.7] .
Tarkastellaan seuraavaksi käänteisrelaatioita. Olkoon(P,≤) osittain jär- jestetty joukko. Olkoon relaatio ≥ relaation ≤ käänteisrelaatio eli Määri- telmän 3.3 mukaan b ≥ a jos ja vain jos a ≤ b, missä a, b ∈ P. Helposti nähdään, että (P,≥)on myös osittain järjestetty joukko, sillä se on refleksii- vinen, antisymmetrinen ja transitiivinen. Paria (P,≥) kutsutaan osittaisen järjestyksen(P,≤)duaaliksi ja relaatiota≥relaation≤duaaliseksi järjestyk- seksi. Kun tarkastellaan jotakin väitettäΦosittain järjestetyssä joukossa, sen duaalinen väite saadaan vaihtamalla relaatio≤relaatioksi≥. Tästä saadaan duaalisuusperiaate: [3, s. 8]
Duaalisuusperiaate: Jos väite Φon tosi kaikissa osittain järjestetyissä joukoissa, niin sen duaali Φd on tosi kaikissa osittain järjestetyissä joukoissa. [4, s. 3]
Duaalisuusperiaate on hyödyllinen osittain järjestettyjä joukkoja tarkas- teltaessa, sillä niitä koskevia väitteitä todistettaessa riittää monesti, että to- distetaan toinen puoli väitteestä, jolloin toinen seuraa duaalisuuden perus- teella.
Määritelmä 3.12. Funktio F :P →Q onantitoninen jos 1. a≤b ⇒ F(a)≥F(b),
2. F(a)≤F(b) ⇒ a≥b.
BijektiotaF, joka täyttää Määritelmän 3.12 ehdot 1 ja 2, kutsutaan du- aaliseksi isomorfismiksi [2, s. 3].
3.4 Supremum ja infimum
Määritelmä 3.13. Olkoon P osittain järjestetty joukko jaX ⊂P. Joukon X pienin alkio on a ∈X siten, että a ≤x kaikilla x∈ X. JoukonX suurin alkio vastaavasti on b ∈ X siten, että x ≤ b kaikilla x ∈ X. Joukon X minimaalinen alkio on m ∈ X siten, että jos x≤ m, seuraa m =x kaikilla x ∈ X. Vastaavasti joukonX maksimaalinen alkio on n ∈ X siten, että jos n ≤x, seuraan =x kaikilla x∈X. [2, s. 4]
Pienintä ja suurinta alkiota ei tule sekoittaa minimaaliseen ja maksimaali- seen alkioon. Määritelmästä nähdään, että pienin alkio on aina minimaalinen alkio ja suurin alkio on aina maksimaalinen alkio, mutta päinvastaiset eivät päde. [2, s. 4]
Osittain järjestetyssä joukossa voi olla pienin ja suurin alkio, joita mer- kitään vastaavasti 0 ja 1. Näiden yksikäsitteisyys on helppo osoittaa, mikäli tällaiset alkiot ovat olemassa. Perustellaan malliksi alkion0yksikäsitteisyys.
Olkoon 0∈P, jolle pätee0≤xkaikillax∈P. Jos on olemassa kaksi alkiota a ja b, joille tämä pätee, niin a ≤ b ja b ≤ a, jolloin antisymmetrisyyden nojalla a =b. [2, s. 1-2]
Tarkasteltaessa osittain järjestetyn joukon osajoukkoa tärkeiksi käsitteiksi nousee supremum eli pienin yläraja ja infimum eli suurin alaraja.
Määritelmä 3.14. OlkoonX ⊆P, missä(P,≤)on osittain järjestetty jouk- ko. Alkio i∈P on joukon X infimum eli suurin alaraja jos seuraavat ehdot ovat totta:
1. Kaikilla x∈X pätee i≤x,
2. Jos i0 ∈P ja i0 ≤x kaikilla x∈X, niini0 ≤i.
Merkitään joukon X infimumiai= infX. [5, s. 4]
Määritelmän ensimmäinen ehto tarkoittaa, että i on joukon X alaraja.
Toinen ehto tarkoitttaa, että josi0on myös joukonX alaraja, se on pienempi kuin i, eli i on siis joukon X suurin alaraja. Supremumin määritelmä on samantapainen.
Määritelmä 3.15. OlkoonX ⊆P, missä(P,≤)on osittain järjestetty jouk- ko. Alkios∈P on joukonX supremum elipienin yläraja jos seuraavat ehdot ovat totta:
1. Kaikilla x∈X pätee x≤s,
2. Jos s0 ∈P ja x≤s0 kaikillax∈X, niin s≤s0. Merkitään joukon X supremumia s= supX. [5, s.4]
Osittain järjestetyssä joukossa supremum ja infimum ovat yksikäsitteisiä ja niiden ei tarvitse kuulua osajoukkoon X.
Lause 3.16. OlkoonP osittain järjestetty joukko ja Qsen epätyhjä osajouk- ko. Jos infQ on olemassa, niin tämä infimum on yksikäsitteinen. Vastaavas- ti, jos supQ on olemassa, niin tämä supremum on yksikäsitteinen.
Todistus. Oletetaan, että s1 ja s2 ovat molemmat joukon Q supremum.
Määritelmän 3.15 mukaan jokaiselle joukonQ muulle ylärajalley pätees1 ≤ y. Erityisesti, koskas2 on joukon Qyläraja, niin s1 ≤s2. Toisaalta, koska s2 on joukonQsupremum, jokaiselle joukonQmuulle ylärajalle ypätees2 ≤y.
Erityisesti s2 ≤ s1. Näin ollen s1 = s2 antisymmetrisyyden nojalla, jolloin joukon Q supremumin täytyy olla yksikäsitteinen. Duaalisuuden perusteella myös joukon Q infimum on yksikäsitteinen. [7, s. 398] □
Käytetään joukon {x, y}infimumista ja supremumista merkitöjä x∧y= inf{x, y}
ja
x∨y= sup{x, y}.
Seuraava lemma liittää binäärioperaatiot ∨ ja ∧ yhteen relataation ≤ kanssa.
Lemma 3.17. Olkoon (P,≤)osittain järjestetty joukko ja x, y ∈P. Tällöin 1. x≤y⇔(x∨y) = y,
2. x≤y⇔(x∧y) = x.
Todistus. Todistetaan ensimmäinen väite.
(⇒) Jos x≤ y, niin y on joukon {x, y} yläraja. Koska kaikki joukon {x, y}
muut ylärajat ovat välttämättä suurempia kuin y ja x, niin y on pienin yläraja. Näin ollen (x∨y) =y.
(⇐) Olkoon (x∨y) = y, toisin sanoen y on joukon {x, y} pienin yläraja.
Tällöin pätee erityisesti x≤y.
Duaalisuuden perusteella myös toinen väite pätee. [5, s.5] □
4 Hilat
Tässä luvussa käydään läpi hilateorian perusteita. Hiloja voidaan kuvata kah- della eri tavalla. Ensinnäkin ne voidaan määritellään osittain järjestettyinä joukkoina, joissa kaikille mielivaltaisille alkiopareille on olemassa infimum ja supremum. Toisaalta hiloja voidaan tarkastella algebrallisina rakenteina, eli joukkoina, joissa on laskutoimituksia. Tässä luvussa hilat määritellään näis- tä kahdesta näkökulmasta, tarkastellaan hiloja Hasse-kaavioiden avulla sekä esitellään hiloihin liittyviä ominaisuuksia.
4.1 Hilat osittain järjestettyinä joukkoina
Määritelmä 4.1. Osittain järjestetty joukko(L,≤)onhilajos kaikillax, y ∈ L on olemassa x∨y ja x∧y. [2, s. 6]
Tarkastellaan esimerkkejä hiloista.
Esimerkki 4.2. a) Kaikki ketjut ovat hiloja, missä x∧y on alkioista xja y pienempi ja vastaavasti x∨y on alkioista x ja y suurempi. [2, s. 7]
b) Joukon X kaikkien osajoukkojen joukkoP(X)on hila, jossa osajoukkojen A ja B yhdiste A∪ B on A ∨B ja leikkaus A∩ B on A ∧B [7, s.398].
Esimerkissä 3.5 a) todettiin, että (P(X),⊆) on osittain järjestetty joukko.
Osoitetaan, että A∪B = sup{A, B}. Olkoon A, B ⊆P. SelvästiA⊆A∪B ja B ⊆A∪B eliA∪B on joukon {A, B} yläraja.
Lähteessä [7, s.484] todetaan, että joukkojen yhdisteellä ja leikkauksella on seuraavat ominaisuudet:
Y ⊆Z jos ja vain josY ∪Z =Z ja
Y ⊆Z jos ja vain jos Y ∩Z =Y.
Olkoon C ⊆ P ja A ⊆ C sekä B ⊆ C eli A∪C = C ja B ∪C = C.
Osoitetaan, että A∪B ⊆ C. Tämä pätee, koska (A∪B)∪C = A∪(B ∪ C) = A ∪C = C. Siis A∪B on sup{A, B}. Vastaavasti näytetään, että A∩B = inf{A, B}.
c) Pari (Z+,|)on hila, missäx∨yon alkioidenx jay pienin yhteinen jakaja ja x∧y on alkioiden x ja y suurin yhteinen tekijä. [3, s. 11]
Esimerkissä 3.5 b) on todettu, että(Z+,|)on osittain järjestetty joukko.
Osoitetaan, että syt(x, y) = inf{x, y}. Olkoon d = syt(x, y). Tällöin d|x ja d|y, joten d on joukon{x, y} alaraja.
Olkoon c∈Z+ jokin joukon {x, y} alaraja, eli c|x ja c|y. Koska x=cm, y =cn ja lähteen [7, s. 7] nojalla
d=xk+yl jollekin m, n, k, l, niin
d=cmk+cnl =c(mk+nl).
Siis c|d, joten d on suurin joukon {x, y}alaraja.
Vastaavasti on selvää, että pyj(x, y) =:eon joukon{x, y}yläraja. Olkoon c∈Z+ joku joukon {x, y} yläraja, toisin sanoen x|cja y|c. Nyt e|c, sillä jos näin ei ole, niin kokonaislukujen jakoyhtälön (ks. [7, s.2]) nojalla c=ke+r missä 0< r < e. Tällöin r =c−ke on jaollinen sekä luvulla x, että luvulla y, mikä on ristiriita sen kanssa, että e on pienin yhteinen monikerta.
d) Hilan(L,≤) duaali(L,≥) on hila. [4, s. 4]
Lause 4.3. Osittain järjestetty joukko (L,≤) on hila jos ja vain jos supH ja infH ovat olemassa kaikilla joukon L äärellisillä epätyhjillä osajoukoilla H.
Todistus. Riittää todistaa väite suuntaan ⇒, sillä suunta ⇐ on triviaalisti totta.
Olkoon(L,≤)hila jaH ⊆Lepätyhjä ja äärellinen. Todistetaan väite induk- tiolla joukon H alkioiden lukumäärän suhteen. Jos H on yhden tai kahden alkion joukko, väite pätee Määritelmän 4.1 nojalla.
Oletetaan, että supremum on olemassa n −1 alkion tapauksessa ja nimi- tetään sitä s = supH, missä s ∈ L, H = {a0, a1,· · ·an−1} ja n ≥ 2. Siis Määritelmän 3.15 mukaan ai ≤ s kaikilla ai ∈ H ja jos s0 ∈ L ja ai ≤ s0 kaikilla ai, niin s≤s0.
Osoitetaan nyt, että supremum on olemassa n alkion tapauksessa. Olkoon H ={a0, a1,· · ·an},n ≥2. Osoitetaan, että
sup{a0, a1,· · · , an−1, an}= sup{s, an}=:s1.
Ensinnäkin ai ≤ s kaikilla i = 1,· · · , n −1 induktio-oletuksen nojalla ja s ≤ s1, joten transitiivisuuden nojalla ai ≤ s1 kaikilla i = 1,· · · , n −1.
Lisäksi pätee an ≤ s1, joten s1 on joukon H yläraja. Toiseksi, jos s2 on joukon H yläraja, niin s ≤ s2 sillä s = sup{a1,· · · , an−1. Myös an ≤ s2, jolloin sup{s, an} ≤s2. Näin ollens1 ≤s2, elis1 on joukon H pienin yläraja eli supremum.
Duaalisuuden perusteella myös infH on olemassa. □
Määritelmä 4.4. Hila Lontäydellinen, jos sen jokaisella osajoukollaX on supremum ja infimum joukossa L.
Epätyhjä täydellinen hila sisältää aina pienimmän alkion 0 ja suurim- man alkion 1. Äärellinen hila on aina täydellinen. Täydellisen hilan duaali on aina täydellinen hila, duaalissa ∨ ja ∧ vaihtavat paikkoja. Rationaalilu- vut ja reaaliluvut luonnollisessa järjestyksessään eivät ole täydellisiä hiloja, ellei joukkoihin lisätä +∞ ja −∞. Esimerkissä 4.2 esitetyistä hiloista a)-c) ainoastaan (P(X),⊂) on täydellinen hila. Siinä ∅= 0 ja X = 1. [2, s. 6-7]
Määritelmä 4.5. Olkoon (L,≤) hila. Joukko S ⊂ L on tämän alihila jos kaikilla x, y ∈S pätee x∨y∈S ja x∧y∈S. [2, s. 7]
Jokaisella hilalla L on triviaalit alihilat hila L itse sekä jokainen hilan L yksialkioinen osajoukko. Hilan kaksialkioinen osajoukko {x, y}, jossa x ja y ovat vertailullisia, on alihila. Alihila on on aina hila, mutta hilan osajoukko, joka on hila, ei ole aina alihila, kuten seuraavassa esimerkissä nähdään. [3, s.
16]
Esimerkki 4.6. Olkoon L = (P({1,2,3}),⊂) ja K = (K,⊂), missä K = {∅,{1},{2},{1,2,3}}. Sekä L että K ovat hiloja ja K ⊂ P({1,2,3}). K on hila, sillä operaatio ⊂ määrittää osittaisen järjestyksen siten, että ∅ ⊂ {1},∅ ⊂ {2},∅ ⊂ {1,2,3},{1} ⊂ {1,2,3} ja {2} ⊂ {1,2,3}.
{1,2,3}
{1} {2}
∅
Kuva 2: HilaK
Kuvassa 2 on esitetty osittainen järjestys Hasse-kaaviossa ja siitä nähdään helposti, että jokaisella alkioparilla on olemassa supremum ja infimum.
Hila K ei ole hilanL alihila, sillä hilassa L {1} ∨ {2}={1,2}, kun taas hilassa K {1} ∨ {2}={1,2,3}. HilanKoperaatiot∨ ja ∧eivät siis ole hilan L operaatioita. [3, s. 16]
4.2 Hilojen kuvaaminen Hasse-kaaviolla
Hiloja voidaan havainnollistaa Hasse-kaavioiden avulla samalla tavoin kuin osittain järjestettyjä joukkoja, kuten jo esimerkissä 4.6 nähtiin.
Esimerkki 4.7. Tarkastellaan Kuvissa 3 ja 4 esitettyjä Hasse-kaavioita ja tutkitaan ovatko esitetyt kaaviot hiloja.
Kuvassa 3 esitetyt Hasse-kaaviot eivät kuvaa hiloja. KaaviossaP1alkioilla a ja b ei ole suurinta yhteistä alarajaa. Kaaviossa P2 alkioilla a ja b ei ole alarajaa. [3, s. 10]
◦
a ◦ ◦ b ◦
◦ ◦ a ◦ ◦b
◦
P1 P2
Kuva 3:
... {x, y, z}
1◦ ◦ {x, y} {x, z} {y, z}
a ◦ ◦b ◦ {x} {y} {z}
0◦ ◦ ∅
L1 L2 L3
Kuva 4:
Kuvassa 4 esitetyt Hasse-kaaviot ovat hiloja.
Hila L1 = (L,≤) on osittaisella järjestyksellä ≤ varustettu joukko L = {0, a, b,1}. Osittaista järjestystä≤voidaan kuvata pareina(x, y), jossax≤y.
Siis ≤= {(0,0),(0, a),(0, b),(0,1),(a, a),(a,1),(b, b),(b,1),(1,1)}. Toisaalta kaikki parit, jotka ovat muotoa (x, x) voidaan jättää pois, sillä x ≤ x.
Transitiivisuuden nojalla pois voidaan jättää myös 0 ≤ 1, sillä 0 ≤ a ja a ≤ 1 kertoo saman asian. Tällöin jäljelle jää vain parit, joista toinen peit- tää toisen. Ilmaistaan siis hila L1 relaation ≺ avulla: L1 = (L,≺), missä
≺={(0, a),(0, b),(a,1),(b,1)}. [4, s. 9-10]
HilaL2 on ääretön ketju. Äärettömien hilojen Hasse-kaavio voidaan piir- tää, mikäli hila on säännöllinen ja kuvan ohessa on selitysteksti.
Hila L3 on esimerkissä 4.6 esitetyn hilan L = (P({1,2,3}),⊂) Hasse- kaavio.
Hilaa kuvaavan Hasse-kaavion sanotaan olevan tasainen, jos sen viivat eivät risteä. Kaavio on optimaalinen, jos mahdollisimman harvat viivat ris- teävät keskenään. Optimaaliset kaaviot ovat käytännöllisimpiä hilojen ha- vainnollistamisessa. [4, s.10-11]
◦ ◦
◦ ◦ ◦ ◦ ◦ ◦
◦ ◦ ◦ ◦
◦ ◦
[4, s. 13]
Kuva 5:
Esimerkki 4.8. Kuvassa 5 on esitetty kahden hilan Hasse-kaaviot, jotka tarkemmin tarkasteltaessa huomataan esittävän samaa hilaa. Näistä oikean puoleinen kaavio on tasainen, koska sen viivat eivät risteä. Tämä kaavio on siis myös optimaalinen. Vasemman puoleinen kaavio ei ole tasainen eikä op- timaalinen.
Kuvassa 6 esitetty hila ei ole tasainen, sillä siinä viivat risteävät, mutta se kuitenkin on optimaalinen, sillä sitä ei voisi esittää muulla tavoin siten, että kaaviossa olisi vähemmän risteäviä viivoja.
◦
◦ ◦ ◦
◦ ◦ ◦
◦
Kuva 6:
4.3 Hilat algebrallisina rakenteina
Hiloja voidaan kuvata algebrallisina rakenteina, eli laskutoimituksilla varus- tettuna joukkona. Relaatio ≤on joukon L2 osajoukko, kun taas ∨ja ∧ ovat kuvauksia joukoltaL2joukkoonL. Käsittelemällä hiloja algebrallisena, saam- me käyttöömme yleisiä algebran tuloksia. Seuraavaksi käsitellään operaatioi- den ∨ ja ∧ algebrallisia ominaisuuksia hiloissa. [4, s.4-5]
Lemma 4.9. Olkoon L hila siten, että x, y, z ∈L. Joukossa L operaatioilla
∨ ja ∧ pätevät seuraavat säännöt:
(L1) x∨x=x, x∧x=x. (idempotenttisuus) (L2) x∨y=y∨x, x∧y =y∧x. (vaihdannaisuus)
(L3) x∨(y∨z) = (x∨y)∨z, x∧(y∧z) = (x∧y)∧z. (liitännäisyys) (L4) x∨(x∧y) = x, x∧(x∨y) =x. (absorptiolait)
Todistus. [2, s. 8] Riittää, että jokaisesta kohdasta todistetaan vain ensim- mäinen väite, toinen väite on totta duaalisuuden perusteella.
(L1) Tiedetään, että x ∨x on joukon {x, x} = {x} supremum. Toisaalta on selvää, että joukon {x} supremum on x. Siispä Lauseen 3.16 perusteella x∨x=x. [7, s. 400]
(L2) Tiedetään, että x∨yon joukon {x, y}supremum jay∨x joukon{y, x}
supremum. Koska{x, y} ja{y, x} ovat sama joukko, Lauseen 3.16 perusteel- la x∨y=y∨x. [7, s. 399]
(L3) Osoitetaan ensin, että (x∨y)∨z on joukon {x, y, z} yläraja. Olkoon d=x∨y. Ylärajan määritelmän mukaanz ≤d∨z = (x∨y)∨z. Vastaavasti x≤x∨yjax∨y=d≤d∨z = (x∨y)∨z. Siispä transitiivisuuden perusteel- la x≤(x∨y)∨z. Vastaavalla tavalla osoitetaan, että myös y≤(x∨y)∨z.
Näin ollen (x∨y)∨z on joukon {x, y, z} yläraja.
Seuraavaksi osoitetaan. että (x∨y)∨z on joukon {x, y, z} pienin yläraja.
Jos v on joukon {x, y, z} mikä tahansa muu yläraja, niin x ≤ v ja y ≤ v.
Määritelmästä 3.15 seuraa, että d =x∨y ≤ v. Koska d ≤ v ja z ≤ v, niin vastaavasti Määritelmän 3.15 perusteella (x∨y)∨z =d∨z ≤v. Näin ollen (x∨y)∨z on joukon{x, y, z} pienin yläraja.
Vastaavalla argumentoinnilla voidaan osoittaa, että myös x ∨ (y ∨ z) on joukon {x, y, z} pienin yläraja. Tästä seuraa Lauseen 3.16 perusteella, et- tä (x∨y)∨z =x∨(y∨z). [7, s. 399-400]
(L4) Absorptiolait nähdään helposti toteen Lemman 3.17 avulla. Olkoon x ≤ y. Tällöin x ∧ (x∨ y) = x ∧ y = x ja x ∨ (x ∧ y) = x ∨x = x.
Vastaavasti, jos y≤x, niinx∧(x∨y) =x∧x=xjax∨(x∧y) =x∨y =x.
[2, s. 8] □
Määritellään nyt hilat tietynlaisena algebrallisena struktuurina.
Määritelmä 4.10. Rakenne (L,∨,∧) on hila, jos L on epätyhjä joukko, molemmat ∧ ja ∨ ovat binäärioperaatioita joukossa L, sekä molemmat ovat idempotentteja, liitännäisiä ja vaihdannaisia, sekä absorptiolait ovat voimas- sa kummallakin. [4, s.5]
Seuraavaksi esitetään tärkeitä aputuloksia.
Lemma 4.11. Jos osittain järjestetyssä joukossa P on pienin alkio 0, niin 0∧x= 0 ja 0∨x=x kaikilla x∈P.
Vastaavasti, jos joukossa P on suurin alkio 1, niin
x∧1 =x ja x∨1 = 1 kaikilla x∈P.
Todistus. Olkoon 0 osittain järjestetyn joukon (P,≤) pienin alkio. Silloin 0 ≤ x kaikilla x ∈ P. Lemman 3.17 mukaan 0∧x = 0 ja 0∨x =x kaikilla x∈P. Suurimman alkion 1 todistus on edellisen duaali. [2, s. 9] □ Lemma 4.12. Kaikissa hiloissa operaatiot ∨ ja ∧ ovat isotonisia:
Jos y ≤z,niin x∨y≤x∨z ja x∧y≤x∧z.
Todistus. Olkoon y≤z. Tällöin
x∧y= (x∧x)∧(y∧z) (L1), Lemma 3.17
= (x∧y)∧(x∧z) (L2), (L3)
eli Lemman 3.17 mukaan x∧y ≤ x∧z. Duaalisesti voidaan osoittaa, että
myös x∧y≤x∧z pätee. [2, s.9] □
Seuraava lause liittää yhteen Määritelmät 4.1 ja 4.10.
Lause 4.13. i) Olkoon(L,≤)hila. Asetetaanx∨y= sup{x, y}jax∧y= inf{x, y}. Tällöin (L,∧,∨) on hila.
ii) Olkoon(L,∧,∨)hila. Asetetaanx≤yjos ja vain josx∧y=x. Tällöin (L,≤) on hila.
Todistus. i) Koska (L,≤)on hila, joukko L on epätyhjä. Määrittelynsä pe- rusteella∨ja∧ovat laskutoimituksia. Todistetaan Lemman 4.9 ehdot L1-L4:
(L1) Refleksiivisyyden ja Lemman 3.17 perusteella idempotenttisuus on voi- massa.
(L2) Vaihdannaisuus seuraa siitä, että sup{x, y}= sup{y, x} ja inf{x, y}= inf{y, x}aina, kun x, y ∈L.
(L3) Koska sup{sup{x, y}, z}= sup{x, y, z}= sup{x,sup{y, z}}, niin x∧(y∧z) = (x∧y)∧z.
Sama päättely pätee infimumin tapauksessa eli liitännäisyys on voimassa.
(L4) Koska x∧y ≤ x, niin käyttämällä Lemmaa 3.17 ja Määritelmän 4.9 kohtaa (L2) saadaanx∨(x∧y) = x. Vastaavasti saadaan toinen puoli ehdosta ja absorptiolait ovat siis voimassa. [3, s. 14]
ii) Asetetaanx≤y tarkoittamaan x∧y=x.
Osoitetaan ensin, että (L,≤)on osittain järjestetty joukko.
Ensimmäiseksi, koska ∧on idempotentti, niin ≤ on refleksiivinen.
Toiseksi x ≤ y ja y ≤ x tarkoittaa vastaavasti, että x∧y = x ja y∧x =y.
Koska ∧ on vaihdannainen voidaan päätellä, että x =x∧y = y∧x =y eli
≤ on antisymmetrinen.
Kolmanneksi ≤on transitiivinen, koska jos x≤y ja y≤z, niinx=x∧y ja y =y∧z ja siis liitännäisyyden nojalla
x=x∧y =x∧(y∧z) = (x∧y)∧z =x∧z eli siis x≤z.
Näistä seuraa, että (L,≤) on osittain järjestetty joukko. Seuraavaksi osoite- taan, että (L,≤) on hila näyttämällä, että sup{x, y} =x∨y ja inf{x, y}= x∧y.
Käyttämällä liitännäisyyttä, vaihdannaisuutta ja idempotenttisuutta saa- daan
(x∧y)∧x=x∧(y∧x) = x∧(x∧y) = (x∧x)∧y =x∧y.
Tästä nähdään, että x∧y≤x. Vastaavasti nähdään, että x∧y≤y.
Jos z ≤ x ja z ≤ y, eli toisin ilmaistuina z ∧x = z ja z ∧y = z, niin z ∧(x∧y) = (z ∧x)∧y = z ∧y = z. Täten x∧y = inf{x, y}. Lopuksi
x ≤x∨y ja y ≤x∨y, koska absorptiolakien perusteella x=x∧(x∨y) ja y =y∧(x∨y). Jos x≤z ja y≤z, jotka ovat toisin ilmaistuinax=x∧z ja y =y∧z, niin absorptiolakien perusteellax∨z = (x∧z)∨z =z jay∨z =z.
Nyt
(x∨y)∧z = (x∨y)∧(x∨z) = (x∨y)∧(x∨(y∨z)) = (x∨y)∧((x∨y)∨z) =x∨y, mikä tarkoittaa, että x∨y≤z eli x∨y= sup{x, y}. [4, s. 5] □
5 Modulaariset ja distributiiviset hilat
Tässä luvussa esitellään kaksi merkittävää hilojen erikoistapausta, modulaa- riset hilat ja distributiiviset hilat. Ensimmäiseksi esitetään aputuloksia, muun muassa distributiivisia ja modulaarisia epäyhtälöitä, jotka pätevät kaikissa hiloissa. Kun nämä epäyhtälöt tarkennetaan yhtälöiksi, saadaan hilojen eri- koistapauksena seuraavaksi esiteltävät modulaariset ja distributiiviset hilat.
Lopuksi tarkastellaan kyseisiä hiloja alihilojen avulla ja todistetaan lauseet, joiden avulla on helppo tunnistaa modulaarisia ja distributiivisia hiloja.
5.1 Hilojen epäyhtälöitä
Seuraavaksi esitetään joitakin epäyhtälöitä, jotka ovat yleisesti voimassa hi- loissa. Lauseen 5.1 kohta ii) on nimeltään minimax-lause ja kohta i) on sen erikoistapaus.
Lause 5.1. Jokaisessa hilassa on voimassa epäyhtälöt i) (a∧b)∨(c∧d)≤(a∨c)∧(b∨d),
ii)
n
⋁
j=1
(m
⋀
i=1
aij )
≤
m
⋀
i=1
( n
⋁
j=1
aij )
.
Todistus. [3, s. 23] i) Koska a∧b ≤ a ≤ a∨c ja c∧d ≤ c ≤ a∨c, niin (a∧b)∨(c∧d)≤ a∨c. Vastaavasti a∧b≤ b ≤b∨d ja c∧d ≤d ≤b∨d, joten(a∧b)∨(c∧d)≤b∨d. Näistä seuraa(a∧b)∨(c∧d)≤(a∨c)∧(b∨d).
ii) Koska
m
⋀
i=1
aij0 ≤ai0j0 ≤
n
⋁
j=1
ai0j
aina, kun 1≤i0 ≤m ja 1≤j0 ≤n, niin
n
⋁
j=1
(
m
⋀
i=1
aij)≤
n
⋁
j=1
ai0j
aina, kun 1≤i0 ≤m. Tällöin ⋁n j=1(⋀m
i=1aij)≤⋀m i=1(⋁n
j=1aij).
□ Lauseen 5.2 kohtia i)-iii) kutsutaandistributiivisiksi epäyhtälöiksi ja koh- tia iv) - v) kutsutaan modulaarisiksi epäyhtälöiksi.
Lause 5.2. Jokaisessa hilassa ovat voimassa seuraavat epäyhtälöt
i) x∨(y∧z)≤(x∨y)∧(x∨z), ii) (x∧y)∨(x∧z)≤x∧(y∨z),
iii) (x∧y)∨(y∧z)∨(z∧x)≤(x∨y)∧(y∨z)∧(z∧x), iv) x≤z ⇒x∨(y∧z)≤(x∨y)∧z,
v) (x∧y)∨(x∧z)≤x∧(y∨(x∧z)).
Todistus. [3, s. 24] i) Sovelletaan Lausetta 5.1 i) alkioihin a=b = x, c=y ja d=z. Tästä saadaan idempotenttisuutta käyttämällä
x∨(y∧z) = (x∧x)∨(y∧z)≤(x∨y)∧(x∨z).
ii) Sovelletaan Lausetta 5.1 i) alkioihin a = b = x, c = y ja d = z. Tästä saadaan idempotenttisuutta käyttämällä
(x∧y)∨(x∧z)≤(x∨x)∧(y∨z) =x∧(y∨z).
iii) Sovelletaan Lausetta 5.1 ii) alkioihin
a11=x, a21=y, a31=x, a12 =y, a22=y, a32=z, a13=x, a23=z, a33=z.
Tästä saadaan
(x∧y)∨(y∧z)∨(z∧x) = (x∧y∧x)∨(y∧y∧z)∨(x∧z∧z)
≤(x∨y∨x)∧(y∨y∨z)∧(x∨z∨z)
= (x∨y)∧(y∨z)∧(z∨x)
käyttämällä idempotenttisuutta, vaihdannaisuutta ja liitännäisyyttä.
iv) Olkoon x≤z. Kohdan i) ja Lemman 3.17 perusteella saadaan x∨(y∧z)≤(x∨y)∧(x∨z) = (x∨y)∧z.
v) Kohdan i), vaihdannaisuuden ja absorptiolain perusteella (x∧y)∨(x∧z) = (x∧z)∨(x∧y)
≤((x∧z)∨x)∧((x∧z)∨y)
=x∧(y∨(x∧z)).
□
5.2 Modulaariset hilat
Lause 5.3. Seuraavat ehdot ovat ekvivalentteja kaikissa hiloissa:
(L5) kaikilla x, y, z pätee (x∧y)∨(x∧z) = x∧(y∨(x∧z)), (L5’) kaikilla x, y, z pätee x≤z ⇒(x∨y)∧z =x∨(y∧z) .
Todistus. [3, s.27] Oletaan, että ehto (L5) on voimassa ja että x ≤ z. Siis x=x∧z, joten ehdon (L5) ja vaihdannaisuuden perusteella
x∨(y∧z) = (z∧y)∨(z∧x) =z∧(y∨(z∧x)) = (x∨y)∧z.
Käänteisesti oletetaan, että ehto (L5’) on voimassa. Koska x∧z ≤ x, niin ehdon (L5’) ja vaihdannaisuuden perusteella.
(x∧y)∨(x∧z) = (x∧z)∨(y∧x) = ((x∧z)∨y)∧x=x∧(y∨(x∧z)).
□ Määritelmä 5.4. Hila L on modulaarinen, jos se toteuttaa ehdot (L5) ja (L5’). [3, s. 27]
Lemma 5.5. Modulaarisen hilan alihila on modulaarinen.
Todistus. Olkoon L modulaarinen hila ja s ⊂ L sen alihila. Mielivaltaiset alkiot x, y, z ∈ S toteuttavat ehdot (L5) ja (L5’) hilassa L, joten ehtojen täytyy olla voimassa myös hilassa S. Näin ollen S on modulaarinen hila. □
5.3 Distributiiviset hilat
Monissa hiloissa operaatiot ∧ ja ∨ ovat analogisia aritmeettisiin operaatioi- hin ·ja + myös osittelulakien osalta. Aritmetiikassa osittelulaki on muotoa x(y+z) =xy+xz. Osittelulain toteuttavissa hiloissa distributiiviset epäyhtä- löt voidaan tarkentaa yhtälöiksi, jotka eivät kuitenkaan päde kaikissa hiloissa.
[2, s. 11]
Lause 5.6. Seuraavat ehdot ovat ekvivalentteja kaikissa hiloissa:
(L6) kaikilla x, y, z pätee x∧(y∨z) = (x∧y)∨(x∧z), (L6’) kaikilla x, y, z pätee x∨(y∧z) = (x∨y)∧(x∨z).
Todistus. [2, s. 11] Osoitetaan, että implikaatio (L6)⇒(L6’) on totta. Kään- teinen väite (L6’)⇒(L6) seuraa duaalisuuden nojalla. Kaikillax,yjazpätee
(x∨y)∧(x∨z) = [(x∨y)∧x]∨[(x∨y)∧z] (L6)
=x∨[z∧(x∨y)] (L4) ja (L2)
=x∨[(z∧x)∨(z∧y] (L6)
= [x∨(z∧x)]∨(z∧y) (L3)
=x∨(z∧y) (L4)
=x∨(y∧z). (L2)
□ Määritelmä 5.7. HilaLondistributiivinen, jos se toteuttaa osittelulait (L6) ja (L6’). [2, s. 12]
Kaikki ketjut ovat distributiivisia. Distributiivisen hilan duaali on distri- butiivinen hila. [2, s. 12] Luvussa 5.4 esitetään esimerkkejä ei-distributiivisista hiloista. Huomaa, että jokainen distributiivinen hila on modulaarinen, mutta kaikki modulaariset hilat eivät ole distributiivisia.
Lemma 5.8. Distributiivisen hilan alihila on distributiivinen hila. [2, s. 12]
Todistus. Olkoon L distributiivinen hila ja S ⊂ L sen alihila. Mielivaltai- set alkiot x, y, z ∈ S toteuttavat osittelulait L6 ja L6’ hilassa L, joten ne toteutuvat myös sen alihilassa S. Näin ollen S on distributiivinen hila. □ Lause 5.9. Distributiivisessa hilassa pätee implikaatio: Jos c∧x =c∧y ja c∨x=c∨y, niin x=y. [2, s. 12]
Todistus. Oletetaan, että c∧x = c∧y ja c∨x = c∨y pätee. Oletusta hyödyntämällä saadaan
x=x∧(c∨x) (L4)
=x∧(c∨y)
= (x∧c)∨(x∧y) (L6)
= (c∧y)∨(x∧y) (L2)
= (c∨x)∧y (L6)
= (c∨y)∧y
=y. (L2), (L4)
□
5.4 Viisikulmiot ja timantit
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
y∨(x∨(y∧z)) = (y∨x)∨(y∧z) = (x∨y)∨(y∧z) = x∨(y∨(y∧z)) = x∨y ja
y∧((x∨y)∧z) = (y∧(x∨y))∧z =y∧z.
Tiedetään, että y∧z ≤ y, y∧z ≤ x∨(y∧z) ja x∨(y∧z) < (x∨y)∧z, josta seuraa
y∧z ≤y∧(x∨(y∧z))≤y∧((x∨y)∧z) =y∧z.
Tämän perusteella y∧(x∨(y∧z)) =y∧z. Vastaavasti
x∨y=y∨(x∨(y∧z))≤y∨((x∨y)∧z)≤x∨y,
joteny∨((x∨y)∧z) =x∨y. Nyt on siis osoitettu, että kaikkien alkioparien 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 eivä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∈Lkomple- 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.
6.2 Boolen rengas
Tässä aliluvussa määritellään Boolen rengas ja näytetään, kuinka Boolen algebrasta voidaan konstruoida Boolen rengas ja päinvastoin. Käydään ensin läpi renkaan määritelmä ja muita tarvittavia määritelmiä.
Määritelmä 6.7. [7, s. 40]Rengas on epätyhjä joukkoR, joka on varustettu kahdella joukon Rbinäärioperaatiolla+ja·siten, että ehdot 1-8 toteutuvat.
Kaikilla x, y, z ∈R pätee
(1) Jos x∈R ja y∈R, niin x+y∈R, (2) x+ (y+z) = (x+y) +z,
(3) x+y=y+x,
(4) On olemassa alkio 0∈R siten, että x+ 0 =x= 0 +x kaikilla x∈R, (5) Yhtälölle x+a= 0 on ratkaisu x joukossa R kaikilla a∈R,
(6) Jos x∈R ja y∈R, niin x·y ∈R, (7) x·(y·z) = (x·y)·z,
(8) x·(y+z) = (x·y) + (x·z) ja (x+y)·z = (x·z) + (y·z).
Määritelmä 6.8. Kommutatiivinen rengas on rengas R, joka toteuttaa eh- don
(9) x·y=y·x.
Määritelmä 6.9. [7, s. 40] Ykkösellinen rengas on rengas R, joka sisältää alkion 1, jolle
(10) x·1 = x= 1·x kaikillax∈R.
Määritelmä 6.10. [7, s. 55] Olkoon R rengas ja r ∈ R. Määritellään yh- teenlaskulle
2r :=r+r ja kertolaskulle
r2 :=rr.
Määritellään nyt Boolen rengas.
Määritelmä 6.11. Rengas(R,+,·,0,1), joka on ykkösellinen rengas ja jossa kaikki alkiot ovat idempotentteja eli
r2 =r kaikilla r∈R, on Boolen rengas. [8, s. 131]
Lause 6.12. Boolen rengas on kommutatiivinen ja 2r= 0 kaikilla r∈R.
Todistus. [8, s. 132] Olkoon R Boolen rengas. Osoitetaan ensin, että2r = 0.
Voidaan päätellä, että
2r=r+r= (r+r)2 =r2+ 2rr+r2 =r+ 2r+r =r+r+ 2r.
Ehdosta 2r=r+r+ 2r saadaan lisäämällä−2r puolittain 0 = 2r.
Osoitetaan seuraavaksi, että Boolen rengas on kommutatiivinen. Renkaan laskusääntöjen nojalla
x+y= (x+y)2 =x2+ 2xy+y2 =x+ 2xy+y=x+y+ 2xy ja
y+x= (y+x)2 =y2+ 2yx+x2 =y+yx+x=x+y+ 2yx.
Yhteenlaskun vaihdannaisuuden perusteella x+y=y+x
⇔x+y+ 2xy=x+y+ 2yx
⇔2xy= 2yx
⇔xy=yx
eli Boolen rengas on kommutatiivinen. □ Minkä tahansa Boolen algebran alkioista voidaan muodostaa rengas mää- rittelemällä kertolasku infimumiksi ja yhteenlasku symmetriseksi erotukseksi [2, s. 47]. Joukko-opin mielessä symmetrinen erotus tarkoittaa, että joukko- jen yhdisteestä otetaan pois niiden leikkaus. Seuraavassa lauseessa esitetään Boolen algebrasta tällä tavoin muodostettu Boolen rengas.
Lause 6.13. Olkoon (B,∧,∨,0,1,′) Boolen algebra ja määritellään sen bi- näärioperaatiot + ja · seuraavasti
x+y= (x∧y′)∨(x′∧y) ja
x·y=x∧y.
Näillä operaatioilla varustettuna B on Boolen rengas. [8, s. 132]
Todistus. [7, s. 410-411] Joukko B on suljettu operaatioiden +ja · suhteen, sillä se on suljettu operaatioiden ∨ ja ∧ suhteen.
Koska ∨ ja ∧ ovat vaihdannaisia, niin myös + on vaihdannainen:
x+y= (x∧y′)∨(x′∧y) = (x′∧y)∨(x∧y′) = (y∧x′)∨(y′∧x) =y+x.
Operaation + määritelmästä saadaan
(x+y) +z = [((x∧y′)∨(x′∧y))∧z′]∨[((x∧y′)∨(x′∧y))′∧z].
Tarkastellaan ensin komplementtia ((x∧y′)∨(x′∧y))′, tälle saadaan esitys ((x∧y′)∨(x′∧y))′ = (x∧y′)′∧(x′∧y)′ (L10)
= (x′ ∨(y′)′)∧((x′)′∨y′) (L10)
= (x′ ∨y)∧(x∨y′) (L9)
= [(x′∨y)∧x]∨[(x′∨y)∧y′] (L6)
= [(x∧x′)∨(x∧y)]∨[(x′ ∧y′)∨(y∧y′)] (L2), (L6)
= [0∨(x∧y)]∨[(x′ ∧y′)∨0] (L8)
= (x∧y)∨(x′∧y′). Lause 6.5, 2.
Tämän tuloksen sekä operaatioiden ∨ ja ∧ distributiivisuuden, liitännäisyy- den ja vaihdannaisuuden avulla saadaan
(x+y) +z = [((x∧y′)∨(x′ ∧y))∧z′]∨[((x∧y)∨(x′ ∧y′))∧z]
= [((x∧y′)∧z′)∨((x′∧y)∧z′)]∨[((x∧y)∧z)∨((x′∧y′)∧z)]
= (x∧y′∧z′)∨(x′∧y∧z′)∨(x∧y∧z)∨(x′∧y′∧z).
Operaation + vaihdannaisuuden, edellisen tuloksen ja operaatioiden ∨ ja ∧ vaihdannaisuuden perusteella saamme
x+ (y+z) = (y+z) +x
= (y∧z′∧x′)∨(y′∧z∧x′)∨(y∧z∧x)∨(y′∧z′∧x)
= (x∧y′∧z′)∨(x′∧y∧z′)∨(x∧y∧z)∨(x′∧y′∧z)
= (x+y) +z.
Näin ollen yhteenlasku on liitännäinen. Nolla-alkio on 0 koska Lauseiden 6.5 ja 6.4 perusteella
x+ 0 = (x∧0′)∨(x′∧0)
= (x∧1)∨(x′∧0) Lause 6.4,(2)
=x∨(x′ ∧0) Lause 6.5,(2)
= (x∨x′)∧(x∨0) (L6’)
= 1∧(x∨0) (L8)
=x∨0 Lause 6.5,(2)
=x. Lause 6.5,(2)
Jokainen x∈B on itsensä vasta-alkio, sillä Lauseen 6.5 perusteella x+x= (x∧x′)∨(x′∧x) = 0∨0 = 0.
Lauseesta 6.5 seuraa, että kertolasku ·eli∧on vaihdannainen ja liitännäinen ja että 1 on ykkösalkio. Kertolasku on idempotentti sillä
x·x=x∧x
=x∧(x∨0) (L4)
=x. Lause 6.5,(2)
Lopuksi on vielä osoitettava, että distributiivisuus on voimassa:
xy+xz = [(x∧y)∧(x∧z)′]∨[(x∧y)′ ∧(x∧z)]
= [(x∧y)∧(x′∨z′)]∨[(x′∨y′)∧(x∧z)] (L10)
= [((x∧y)∧x′)∨((x∧y)∧z′)]∨[(x′∧(x∧z))∨(y′ ∧(x∧z))] (L6), (L2)
= ((x∧x′)∧y)∨(x∧(y∧z′))∨((x′∧x)∧z)∨(y′∧(x∧z)) (L2), (L3)
= (0∧y)∨(x∧(y∧z′))∨(0∧z)∨(x∧(y′∧z)) Lause 6.5,3
= 0∨(x∧(y∧z′))∨0∨(x∧(y′∧z)) Lause 6.4,1
= (x∧(y∧z′))∨(x∧(y′∧z)) Lause 6.5,2
=x∧[(y∧z′)∨(y′ ∧z)] (L6)
=x·(y+z)
□ Kääntäen jokaisen Boolen renkaan avulla voidaan konstruoida Boolen algebra seuraavasti.
Lause 6.14. Olkoon (R,+,·,0,1) Boolen rengas. Määritellään binääriope- raatiot ∨ ja ∧ sekä unaarioperaatio ′ joukossa R seuraavasti
x∧y=xy, x∨y=x+y+xy,
x′ = 1 +x.
Tällöin (R,∧,∨,0,1,′) on Boolen algebra. [8, s. 132]
Todistus. Osoitetaan, että Lauseen 6.5 kaikki kohdat ovat voimassa joukossa R binäärioperaatioilla ∨ja ∧.
(1) On selvää, että ∧ on liitännäinen ja vaihdannainen. Selvästi myös ∨ on vaihdannainen. Osoitetaan binäärioperaation ∨liitännäisyys: Koska
(x∨y)∨z = (x+y+xy)∨z =x+y+xy+z+z(x+y+xy)
=x+y+z+xy+xz+yz+xyz ja
x∨(y∨z) =x∨(y+z+yz) = x(y+z+yz) +x+y+z+yz
=x+y+z+xy+xz+yz +xyz, niin (x∨y)∨z =x∨(y∨z) eli∨ on liitännäinen.
Osoitetaan vielä, että distributiivisuus on voimassa. Koska x∧(y∨z) =x(y+z+yz) =xy+xz+xyz ja
(x∧y)∨(x∧z) =xy∨xz=xy+xz+xyxz =xy+xz+x2yz
=xy+xz+xyz,
niin x∧(y∨z) = (x∧y)∨(x∧z). Myös toinen distributiivisuuslaki pätee, sillä
x∨(y∧z) = x+yz+xyz
ja hyödyntäen Määritelmää 6.11 ja Lausetta 6.12 saadaan (x∨y)∧(x∨z) = (x+y+xy)∧(x+z+xz)
=xx+xz+xxz+yx+yz+yxz+xyx+xyz+xyxz
=x+xz+xz+yx+yx+yz+xyz +xyz+xyz
=x+yz+xyz+ 2xz+ 2xy+ 2xyz
=x+yz+xyz,
eli x∨(y∧z) = (x∨y)∧(x∨z). Näin on osoitettu, että distributiivisuus pätee.
(2) Näytetään seuraavaksi nolla- ja ykkösalkion olemassaolo. Suoraan mää- ritelmästä saadaan
x∨0 = x+ 0 +x0 =x
kaikilla x ∈ R, sillä jokaisessa renkaassa nolla-alkiolla kertominen tuottaa nollan. Lisäksi
x∧1 = x1 =x kaikilla x∈R.
(3) Lopuksi, jokaisella alkiolla on olemassa komplementti, sillä kaikilla x∈R alkio x′ = 1 +x toteuttaa
x∨x′ =x+x′+xx′ =x+ 1 +x+x(1 +x) = 1 + 2x+x+x2 = 1 + 2x+ 2x= 1 ja
x∧x′ =xx′ =x(1 +x) = x+x2 =x+x= 2x= 0.
Koska Lauseen 6.5 kaikki kohdat ovat voimassa joukossa R binääriope- raatioilla ∨ ja ∧, niin (R,∧,∨,0,1,′) on Boolen algebra. □
