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 vaihdannaisuuliitännäisyy-den 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. □
7 Propositiologiikka
Tässä luvussa tarkastellaan proposiotilogiikan yhteyttä Boolen algebroihin.
Ensin esitellään lyhyesti propositiologiikka ja lopuksi osoitetaan, että joukko B, joka sisältää lauseilla, binäärioperaatiolla ∨, ∧, unaarioperaatiolla ′ ja sulkeilla muodostettua loogisia lauseita on Boolen algebra.
Propositio eli väitelause tai lyhyesti lause on toteava väite, joka on joko tosi tai epätosi. Johdettuja lauseita voidaan muodostaa loogisten konnektii-vien avulla. Jos p ja q ovat lauseita, niin johdettu lause "p ja q"esitetään muodossa p∨q. Johdettu lause "ptai q"ilmaistaan muodossap∧q. Lauseen pnegaatio ilmaistaan muodossap′. Johdettujen lauseiden totuusarvo riippuu siihen sisältyvien lauseiden totuusarvoista. Taulokoissa 1, 2 ja 3 on esitetty totuusarvot konnektiiveille ∨ja ∧ sekä negaatiolle ′.
p q p∧q
T T T
T E E
E T E
E E E
Taulukko 1:p ja q
p q p∨q
T T T
T E T
E T T
E E E
Taulukko 2:p tai q
p p′
T E
E T
Taulukko 3: Negaatio
Olkoon p1, p2,· · · , pn lauseita. Kaksi johdettua lausetta, jotka on muo-dostettu käyttämällä pi, ∨, ∧, ′ ja sulkeita, ovat ekvivalentteja, jos niillä on sama totuusarvo kaikilla mahdollisilla lauseiden p1, p2,· · · , pn totuusarvojen yhdistelmillä.
Lause 7.1. Olkoon p1, p2,· · · , pn lauseita ja olkoon B kaikkien lauseiden joukko, joka voidaan muodostaa käyttämällä pi, ∨, ∧, ′ ja sulkeita. Tällöin B varustettuna binäärioperaatioilla ∨ ja ∧ on Boolen algebra.
Todistus. [7, s. 417-418] Jos p ja q ovat lauseita, jotka ovat muodostettu käyttämällä pi, ∨,∧, ′ ja sulkeita, niin sama pätee myös johdetuille lauseille p∨q ja p∧q. Siispä∨ ja ∧ ovat binäärioperaatioita joukossaB.
Osoitetaan Lauseen 6.5 avulla, ettäB varustettuna binäärioperaatioilla∨ ja∧on Boolen algebra. Lauseen 6.5 mukaan∨ja∧täytyy olla vaihdannaisia, liitännäisiä ja distributiivisia. Olkoon p, q, r joukkoon B kuuluvia lauseita.
Ensimmäiseksi näytetään toteen vaihdannaisuus. On selvää, että p∨ q ja q ∨ p saavat samat totuusarvot kaikilla lauseiden p ja q totuusarvojen yhdistelmillä, joten p∨qjaq∨povat ekvivalentteja eli p∨q=q∨p. Samoilla perusteilla myös p∧q=q∧p.
Toiseksi näytetään, että liitännäisyys on voimassa. Tarkastellaan johdet-tujen lauseiden (p∨ q)∨ r ja p ∨(q ∨ r) totuustauluja, jotka on esitetty
Koska johdettujen lauseiden(p∨q)∨r jap∨(q∨r)sarakkeiden totuusar-vot ovat samat, ne ovat ekvivalentteja eli (p∨q)∨r =p∨(q∨r). Vastaavalla tarkastelulla voidaan osoittaa, että(p∧q)∧r=p∧(q∧r). Viimeiseksi osoite-taan, että osittelulait ovat voimassa. Tarkastellaan totuustauluja johdetuille väitteille p∨(q∧r) ja (p∨q)∧(p∨r), jotka on esitetty Taulukossa 5.
Koska johdettujen lauseiden p∨(q∧r) ja (p∨q)∧(p∨r) sarakkeiden totuusarvot ovat samat, lauseet ovat ekvivalentteja eli p∨ (q∧ r) = (p∨ q)∧(p∨r). Vastaavasti voidaan todeta toisen osittelulain olevan voimassa eli p∧(q∨r) = (p∧q)∨(p∧r).
Joukko B sisältää johdettuja lauseita, jotka ovat aina epätosia. Esimer-kiksi lause p∧p′ on tällainen, kuten Taulukosta 6 näemme.
p q r q∧r p∨(q∧r) p∨q p∨r (p∨q)∧(p∨r)
Kaikki lauseet, jotka ovat aina epätosia ovat ekvivalentteja keskenään.
Olkoon 0 ∈ B lause, joka on aina epätosi. Jos p ∈ B, niin p∨ 0 on tosi ainoastaan silloin, kunpon tosi ja epätosi ainoastaan silloin, kunpon epätosi.
Näin ollen p∨0on ekvivalentti lauseen pkanssa eli p∨0 = pkaikillap∈B.
Edelleen p∨p′ = 0, koska p∧p′ on aina epätosi.
Vastaavasti mitkä tahansa kaksi lausetta, jotka ovat aina tosia, ovat ekvi-valentteja. Esimerkiksi p∨p′ on aina tosi, kuten Taulukosta 7 näemme.
p p′ p∨p′
T E T
E T T
Taulukko 7:
Olkoon1∈Blause, joka on aina tosi. Vastaavalla päättelyllä kuin lauseen 0 tapauksessa voidaan osoittaa, että p∧1 =p ja p∨p′ = 1 kaikillap∈B.
On osoitettu, että B täyttää kaikki Lauseessa 6.5 esitetyt ehdot ja näin
ollen B on Boolen algebra. □
Propositiologiikassa tärkeitä käsitteitä ovat ehtolauseet implikaatio ja ekvi-valenssi. Implikaationp⇒qja ekvivalenssinp⇔qtotuustaulut ovat esitetty Taulukossa 8 .
Implikaatio voidaan ilmaista myös muodossa p′ ∨q ja ekvivalenssi muo-dossa (p′ ∨q)∧(q′ ∨p), kuten huomataan vertaamalla Taulukkojen 8 ja 9 totuustauluja.
p q p⇒q p⇔q
T T T T
T E E E
E T T E
E E T T
Taulukko 8: Implikaatio ja ekvivalenssi p q p′ q′ q′∨p p′ ∨q (p′∨q)∧(q′∨p)
T T E E T T T
T E E T T E E
E T T E E T E
E E T T T T T
Taulukko 9:
Boolen algebran ominaisuuksia voidaan hyödyntää toisten loogisten ekvi-valenssien osoittamiseksi. Esimerkiksi ehtolause p⇒q on ekvivalentti kont-raposition q′ ⇒p′ kanssa, koska
(q′ ⇒p′) = (q′)′∨p′ =q∨p′ =p′∨q= (p⇒q).
Voidaan huomata, että konnektiivien "ja"sekä "tai"komplementit ovat oikeastaan De Morganin lait
(p∧q)′ =p′∨q′ ja
(p∨q)′ =p′∧q′. Tautologia on johdettu lause, joka on aina tosi.
Esimerkki 7.2. Osoitetaan, että [p ⇒ (q∧r)] ⇔ [(p ⇒ q)∧(p ⇒ r)] on tautologia. Riittää osoittaa, että [p ⇒ (q∧r)] ja [(p ⇒ q)∧(p ⇒ r)] ovat ekvivalentteja. Käyttämällä Boolen algebran laskusääntöjä saadaan
[p⇒(q∧r)] = [p′∨(q∧r)]
= (p′∨q)∧(p′∨r)
= [(p⇒q)∧(p⇒r)].
Lähteet
[1] Bilová, S. Lattice Theory - its birth and life teoksessa Mathematics th-roughout the ages toim. Fuchs E. Holbaek, Denmark, October 28-31, 1999, and Brno, the Czech Republic, November 2-5, 2000. (English).
Praha: Prometheus, 2001.
[2] Birkhoff, G. Lattice Theory. Providence, Rhode Island, 1979. third edi-tion.
[3] Eronen, M. Hilateoriaa. Tampereen yliopisto, 1999.
[4] Grätzer, G. General Lattice Theory. Academic press, New York, 1978.
[5] Garg, V.Lattice Theory with Applications. University of Texas at Austin [6] Harzheim, E. Ordered sets. Springer, New York. 2005.
[7] Hungerford, T. Abstract algebra, an introduction. Saunders College.
1990.
[8] Roman, S.Lattices and ordered sets. Springer cop, New York. 2008.