Boolen Algebran Matematiikka

Sisällysluettelo:

Boolen Algebran Matematiikka
Boolen Algebran Matematiikka

Video: Boolen Algebran Matematiikka

Video: Boolen Algebran Matematiikka
Video: Булева алгебра - Булева функция - Дискретная математика 2024, Maaliskuu
Anonim

Tämä tiedosto on Stanfordin filosofian tietosanakirjan arkistossa.

Boolen algebran matematiikka

Ensimmäinen julkaisu pe 5.7.2002; aineellinen tarkistus pe 27. helmikuuta 2009

Boolen algebra on kaksiarvoisen logiikan algebra, jossa on vain sensitiiviset liitännät, tai vastaavasti joukkojen algebrat, jotka ovat liiton ja komplementaation alla. Tiukka käsite on tietyn tyyppinen algebra, samanlainen kuin ryhmän matemaattinen käsitys. Tällä konseptilla on juuret ja sovellukset logiikassa (Lindenbaum-Tarski-algebrat ja malliteoria), joukkoteoria (joukkokentät), topologia (täysin irrotetut kompakti Hausdorff-tilat), joukkoteorian perusteet (Boolean-arvostetut mallit), mittausteoria (mitta) algebrat), funktionaalinen analyysi (projektioiden algebrat) ja rengasteoria (Boolen renkaat). Boolen algebran tutkimuksessa on useita näkökohtia: rakenneteoria, Boolen algebran malliteoria, Boolen algebran luokan päätöksenteko- ja päättämättömyyskysymykset sekä ilmoitetut sovellukset. Lisäksi,vaikka niitä ei selitetä täällä, on yhteyksiä muihin logiikoihin, alajaottelu osana erityyppisiä algebrallisia logiikoita, äärelliset Boolen algebrat ja kytkentäpiiriteoria sekä Boolen matriisit.

  • 1. Määritelmä ja yksinkertaiset ominaisuudet
  • 2. Alkebraaliteoria
  • 3. Boolen algebran erikoisluokat
  • 4. Boolen algebran rakenneteoria ja kardinaalitoiminnot
  • 5. Päättämis- ja päättämättömyyskysymykset
  • 6. Lindenbaum-Tarski algebrat
  • 7. Boolenarvoiset mallit
  • bibliografia
  • Muut Internet-resurssit
  • Aiheeseen liittyvät merkinnät

1. Määritelmä ja yksinkertaiset ominaisuudet

Boolen algebra (BA) on joukko A yhdessä binaaritoimintojen + ja · ja yksiarvoisen operaation kanssa, ja elementtejä 0, 1 A: sta siten, että seuraavat lait ovat voimassa: kommutatiiviset ja assosiatiiviset lait lisäämiseen ja kertomiseen, jakavat lait sekä kertolasku lisäyksellä ja lisäys kertolaskelmalla ja seuraavat erityislakit:

x + (x · y) = x

x · (x + y) = x

x + (−x) = 1

x · (−x) = 0

Nämä lait ymmärretään paremmin BA: n perusesimerkillä, joka koostuu joukosta X kuuluvien joukkojen A joukosta, joka on suljettu liitoksen, leikkauksen, X: n suhteen täydentämisen kanssa jäsenten ∅ ja X kanssa. Näistä aksioomista voidaan helposti johtaa monia peruslakeja, pitäen mielessä tämä motivaatioesimerkki. Millä tahansa BA: lla on luonnollinen osajärjestys ≤, joka määritetään sanomalla, että x ≤ y jos ja vain jos x + y = y. Tämä vastaa pääesimerkissämme ⊆. Erityisen tärkeätä on kaksielementti BA, joka on muodostettu ottamalla joukko X: stä vain yksi elementti. Kaksielementti BA osoittaa suoran yhteyden peruslogiikkaan. Kaksi jäsentä, 0 ja 1, vastaavat väärää ja totuutta. Boolen operaatiot ilmaisevat sitten tavalliset totuustaulukot disjunktiolle (+), konjunktiolle (kanssa ·) ja kieltämiselle (kanssa -). Tärkeä perustulos on, että yhtälö on kaikissa BA: issa vain silloin, kun se on kahden elementin BA: ssa. Seuraavaksi määrittelemme x ⊕ y = (x · - y) + (y · - x). Sitten A yhdessä ⊕: n ja · kanssa, yhdessä 0: n ja 1: n kanssa, muodostaa renkaan, jolla on identiteetti, jossa jokainen elementti on ideoiva. Sitä vastoin määritetään x + y = x ⊕ y ⊕ (x · y) ja - x = 1 ⊕ x, kun tällaiselle renkaalle lisätään ⊕ ja kertolasku. Tämä tekee renkaasta BA: n. Nämä kaksi prosessia ovat käänteisiä toisilleen ja osoittavat, että Boolen algebran ja rengasten, joiden identiteetti on identiteetti, jossa jokainen elementti on ideoiva, teoria ovat määritelmällisesti vastaavat. Tämä asettaa BA: n teoriasta algebran standardi tutkimuskohteen. BA: n atomi on nolla elementti a siten, että ei ole elementtiä b, jonka arvo on 0 <b <a. BA on atomi, jos jokainen BA: n nolla elementti on atomin yläpuolella. Rajoitetut BA: t ovat atomia, mutta niin ovat myös monet äärettömät BA: t. Edellä olevassa osittaisjärjestyksessä ≤ x + y on x: n ja y: n pienin yläraja ja x · y on x: n ja y: n suurin alaraja. Voimme yleistää tämän: Σ X on elementtijoukon X pienin yläraja ja Π X on elementtijoukon X suurin alaraja. Niitä ei ole kaikissa Boolean-algebras- sa kaikissa sarjoissa; jos niitä on aina olemassa, Boolean-algebran sanotaan olevan täydellinen. Boolen algebra sanotaan olevan täydellinen. Boolen algebra sanotaan olevan täydellinen.

2. Alkebraaliteoria

Useilla algebrallisilla rakenteilla on selvät määritelmät ja yksinkertaiset ominaisuudet BA: ille: subalgebrat, homomorfismit, isomorfismit ja suorat tuotteet (jopa äärettömän monessa algebras). Jotkut muut vakioalgebralliset rakenteet ovat ominaisia BA: ille. Ihanne BA: ssa on alajoukko, jonka olen suljettu alle +: n, jäsenenä 0, ja sellainen, että jos a ≤ b ∈ I, niin myös ∈ I. Vaikka tämä ei ole heti ilmeistä, tämä on sama kuin rengasteoreettinen käsite. Suodattimella on kaksi käsitettä (yleensä ilman vastinetta renkaissa). Suodatin on alajoukko F, joka on suljettu kohdasta · ja jonka jäsen on 1, ja sellainen, että jos a ≥ b ∈ F, niin myös ∈ F. A: n ultrasuodatin on suodatin F, jolla on seuraavat ominaisuudet: 0 ∉ F ja jokaiselle ∈ A joko ∈ F tai - a or F. Mikä tahansa ∈ A: n ollessa S (a) = {F: F on ultra-suodatin A: lla ja ∈ F}. Sitten S on isomorfismi kaikkien A: n ultrasuodattimien joukon X alaryhmien BA: n BA: lle. Tämä perustaa peruskiviä esittävän lauseen ja selventää BA: ien alkuperää joukkojen konkreettisina algebraina. Lisäksi joukot S (a) voidaan julistaa pohjaksi topologialle X: ssä, ja tämä muuttaa X: stä täysin irrotetun kompakti Hausdorff-tilan. Tämä luo yhden vastauksen BA-luokan ja tällaisten tilojen luokan välillä. Seurauksena, jota käytetään hyvin paljon BA: n teoriassa, monilla topologisilla lauseilla ja käsitteillä on vaikutuksia BA: iin. Jos x on BA: n elementti, annamme 0 x = - x ja 1 x = x. Jos (x (0),… x (m - 1)) on BA A: n elementtien sekvenssi, niin jokainen A: n alakampean elementti, jonka generoi {x (0),…,x (m - 1)} voidaan kirjoittaa monomiaalien summana e (0) x (0) ·… · e (m - 1) x (m - 1) e: lle joissakin funktioissa, jotka kuvaavat m = {0,…, M - 1} osaksi 2 = {0, 1}. Tämä on sensitiivisen logiikan disjunktiivisen normaalimuodon lauseen algebrallinen lauseke. Funktio f BA A: n generaattoreiden joukosta X BAB: ksi voidaan laajentaa homomorfismiin vain silloin, kun e (0) x (0) ·… · e (m - 1) x (m - 1) = 0 tarkoittaa aina, että e (0) f (x (0)) ·… · e (m - 1) f (x (m - 1)) = 0. Tämä on Sikorskin laajennuskriteeri. Jokainen BA A voidaan upottaa kokonaiseen BA B: ään siten, että jokainen B: n elementti on A: n elementtijoukon vähiten yläraja. B on ainutlaatuinen A-isomorfismiin saakka, ja sitä kutsutaan A: n loppuun saattamiseksi. Jos f on homomorfismi BA A: sta täydelliseksi BA B: ksi ja jos A on C: n alaalbra,sitten f voidaan laajentaa C: n homomorfismiin B: ksi. Tämä on Sikorskin jatkelause. Toinen yleinen algebrallinen käsite, jota sovelletaan Boolen algebraihin, on käsite vapaasta algebrasta. Tämä voidaan rakentaa konkreettisesti BA: ille. Nimittäin, vapaa BA on κ: n kahden elementin erillisen tilan suljettu-avoin osajoukko, jotka on nostettu κ-voimaan.

3. Boolen algebran erikoisluokat

Boolen algebralla on monia erityisluokkia, jotka ovat tärkeitä sekä BA: n luontaisen teorian että sovellusten kannalta:

  • Atomic BA, jo mainittu edellä.
  • Atomittomat BA: t, jotka on määritelty BA: ksi, joissa ei ole atomia. Esimerkiksi mikä tahansa ääretön vapaa BA on atomiton.
  • Täydelliset BA-määritelmät, määritelty edellä. Nämä ovat erityisen tärkeitä joukkoteorian perusteissa.
  • Väli-algebrat. Ne johdetaan lineaarisesti järjestetyistä sarjoista (L, <) ensimmäisellä elementillä seuraavasti. L otetaan L: n osajoukkojen pienin algebra, joka sisältää kaikki puoliaukioloajat [a, b), joissa a on L ja b L: ssä tai yhtä suuri kuin ∞. Nämä BA: t ovat hyödyllisiä tutkittaessa Lindenbaum-Tarski algebrat. Jokainen laskettava BA on isomorfinen intervalliagebraan nähden, ja siten laskettavissa oleva BA voidaan kuvata osoittamalla tilattu joukko siten, että se on isomorfinen vastaavalle intervallialgebralle.
  • Puun algebrat. Puu on osittain tilattu joukko (T, <), jossa minkä tahansa elementin edeltäjäjoukot on hyvin järjestetty. Tällaiselle puulle annetaan T: n osajoukkojen algebra, jonka muodostavat kaikki muodon {b: a ≤ b} ryhmät joillekin t: lle a.
  • Superatomic BA: t. Nämä ovat BA: ita, jotka eivät ole vain atomisia, mutta ovat sellaisia, että kukin alaalbra ja homomorfinen kuva on atomi.

4. Boolen algebran rakenneteoria ja kardinaalitoiminnot

Suuri osa Boolen algebran syvemmästä teoriasta, joka kertoo niiden rakenteesta ja luokituksesta, voidaan muotoilla tietyillä funktioilla, jotka on määritelty kaikille Boolen algebreille, arvoina äärettömät kardinaalit. Määrittelemme joitain tärkeimmistä näistä kardinaalitoiminnoista ja ilmoitamme joitain tunnettuja rakenteellisia tosiasioita, jotka on enimmäkseen muotoiltu niiden perusteella

  1. BA: n sellulaarisuus c (A) on A: n parisuuntaisesti hajoavien elementtien sarjojen ylemmän tason yläpiiri.
  2. BA A: n osajoukko X on riippumaton, jos X on joukko vapaita generaattoreita sen tuottamasta alialgebrasta. A: n riippumattomuus on A: n riippumattomien alajoukkojen kardinaliteettien yläraja.
  3. BA A: n osajoukko X on tiheä A: ssa, jos A: n jokainen ei-nolla elementti on ≥ X: n ei-nolla elementti. A: n π-paino on pienimmän kardinaalisuuden tiheä A-alajoukko.
  4. Kaksi A: n elementtiä x, y ovat keskenään vertailukelvottomia, jos kumpikaan niistä ei ole ≤ toinen. A: n osajoukon X kardinaliteettien yläraja, joka koostuu parillisesti vertailukelvottomista elementeistä, on A: n vertaamattomuus.
  5. A: n osajoukko X on tarpeeton, jos mikään X: n elementti ei ole muiden muodostamassa alialgebrassa.

Tärkeä tosiasia solujen suhteen on Erdos-Tarskin lause: jos BA: n sellulaarisuus on yksittäinen kardinaali, niin todellakin on joukko samankokoisia disjunktioelementtejä; solutasoisuuden säännölliselle rajalle (saavuttamaton) on vasta-esimerkkejä. Jokaisella ääretöntä täydellisellä BA: lla on itsenäinen alajoukko, joka on samankokoinen kuin algebra. Jokaisella äärettömällä BA A: lla on verrattoman verraton alajoukko, jonka koko on A: n π-paino. Jokaisella aikaväli-algebralla on laskettava riippumattomuus. Superatomisella algebralla ei ole edes ääretöntä itsenäistä osajoukkoa. Jokainen puun algebra voidaan upottaa väli-algebraan. BA: ta, jolla on vain identiteettiautomorfismi, kutsutaan jäykäksi. On olemassa jäykkiä kokonaisia BA: ita, myös jäykkiä välivälgerreja ja jäykkiä puualgebreita.

5. Päättämis- ja päättämättömyyskysymykset

Tarskin perustulos on, että Boolen algebran alkuteoria on päätettävissä. Jopa Boolen algebran teoria erotetulla ihanteella on päätettävissä. Toisaalta teoria Boolen algebrista, jolla on erotettu alaalbra, on päättämätön. Sekä päätöksenteko- että päättämättömyystulokset ulottuvat eri tavoin Boolen algeereihin ensimmäisen kertaluvun logiikan laajennuksissa.

6. Lindenbaum-Tarski algebrat

Erittäin tärkeä rakenne, joka siirtyy monille logiikoille ja monille muille algebreille kuin Boolen algebreille, on Boolen algebra, joka liittyy jonkin logiikan lauseisiin. Yksinkertaisin tapaus on sensitiivinen logiikka. Täällä on lausemerkkejä, ja yleiset liitososat, jotka rakentavat niistä pidempiä lauseita: disjunktio, konjunktio ja kieltäminen. Koska tällä kielellä on joukko A lauseita, kaksi virkettä s ja t ovat samanarvoisia modulo A: ta vain ja jos niiden väliset bicondition ovat A: n looginen seuraus. Vastaavuusluokat voidaan tehdä BA: ksi siten, että + vastaa disjunktiota, · konjunktiota ja - negatiivisuutta. Mikä tahansa BA on isomorfinen jollekin tästä muodosta. Yksi voi tehdä jotain samanlaista ensimmäisen asteen teoriassa. Olkoon T ensimmäisen kertaluvun teoria ensimmäisen kertaluvun kielellä L. Kutsumme kaavoja φ ja ψ vastaaviksi edellyttäen, että T ⊢ φ ↔ ψ. Lauseen φ ekvivalenssiluokka merkitään merkinnällä [φ]. Olkoon A kaikkien tämän ekvivalenttisuhteen mukaisten vastaavuusluokkien kokoelma. Voimme tehdä A: sta BA: n seuraavilla, helposti perusteltavilla määritelmillä:

[φ] + [ψ] = [φ ∨ ψ]
[φ] · [ψ] = [φ ∧ ψ]
- [φ] = [¬φ]
0 = [F]
1 = [T]

Jokainen BA on isomorfinen Lindenbaum-Tarskin algebralle. Yksi näiden klassisen Lindenbaum-Tarski-algebran tärkeimmistä käyttötavoista on kuitenkin kuvata niitä tärkeille teorioille (yleensä päätöksentekoon perustuvat teoriat). Laskettavissa olevilla kielillä tämä voidaan tehdä kuvaamalla niiden isomorfiset aikavälialgebrat. Yleensä tämä antaa perusteellisen tietämyksen teoriasta. Joitakin esimerkkejä ovat:

Teoria Isomorfinen algebran välillä
(1) pohjimmiltaan päättämätön teoria Q, rationaalit
(2) BA
luonnollinen
luonnollinen

×

Naturals
Naturals

positiivisten kokonaislukujen neliö, leksikografisesti järjestetty

(3) lineaariset tilaukset

× Q määräsi antilexicographically, missä on kuin valta sen tavallisessa järjestyksessä

Naturals
Naturals
Naturals
Naturals
(4) abelialaiset ryhmät (Q + A) × Q

7. Boolenarvoiset mallit

Malliteoriassa voidaan ottaa arvoja missä tahansa täydellisessä BA: ssa kuin kahden elementin BA: ssa. Tätä Boolean-arvostettua malliteoriaa kehitettiin noin 1950–1970, mutta siitä lähtien ei ole tehty paljon työtä. Mutta erityistapaus, Boolean-arvostettu malli joukkoteorialle, on hyvin tärkeä osa nykyistä joukkoteorian tutkimuksen eturintamassa. Se muodostaa todella vastaavan tavan tarkastella Cohenin pakottavaa rakentamista, ja sillä on joitain teknisiä etuja ja haittoja. Filosofisesti se näyttää tyydyttävämmältä kuin pakottava käsite. Kuvailemme tätä joukon teoriatapausta tässä; sitten tulee ilmeiseksi, miksi vain kilpailijoita BA: ta pidetään. Olkoon B täydellinen BA. Ensin määritetään Boolen arvoinen universumi V (B). Tavallinen joukko-teoreettinen universumi voidaan tunnistaa V: llä (2), missä 2 on 2-elementti BA. Määritelmä on transfinite rekursiolla, missä α,β ovat ordinaalit ja λ on raja-ordinaali:

V (B, 0) =
V (B, a + 1) = kaikkien funktioiden f joukko siten, että f-alue on V: n osajoukko (B, α) ja f-alue on B: n osajoukko
V (B, λ) = kaikkien V: n (B, β) liitos β <λ: lle.

B-arvoinen maailmankaikkeus on oikea luokka V (B), joka on kaikkien näiden V: n liitto. Seuraavaksi määritellään melko monimutkaisella transfiniittisellä rekursiolla perusteltujen joukkojen kanssa set-teoreettisen kaavan arvoksi, jonka Boolean-arvoisen maailmankaikkeuden elementeille on osoitettu sen vapaat muuttujat

|| x ∈ y || = Σ {(|| x = t || · y (t)): t ∈ verkkotunnus (y)}
|| x ⊆ y || = Π {- x (t) + || t ∈ y ||: t ∈ verkkotunnus (x)}
|| x = y || = || x ⊆ y || · || y ⊆ x ||
|| ¬φ || = - || φ ||
|| φ ∨ ψ || = || φ || + || ψ ||
|| ∃ x φ (x) || = Σ {|| φ (a) ||: a ∈ V (B)}

bibliografia

  • Halmos, P., 1963, Luennot Boolen algegereista, Princeton: Van Nostrand
  • Heindorf, L. ja Shapiro, L., 1994, melkein projektiiviset Boolean algebrat, Lecture Notes in Mathematics no. 1596, Berliini: Springer-Verlag
  • Jech, T., 1997, Set Theory, 2. korjattu painos, Berliini, New York: Springer-Verlag
  • Monk, JD, ja Bonnet, R., (toim.), 1989, Boolean algebras -käsikirja, 3 osaa, Amsterdam: Pohjois-Hollanti.

Muut Internet-resurssit

[Ota yhteyttä kirjoittajaan ehdotuksilla.]

Suositeltava: