De Wiskunde Van De Booleaanse Algebra

Inhoudsopgave:

De Wiskunde Van De Booleaanse Algebra
De Wiskunde Van De Booleaanse Algebra
Video: De Wiskunde Van De Booleaanse Algebra
Video: Vereenvoudigen van booleaanse expressies 2023, Februari
Anonim

Dit is een bestand in de archieven van de Stanford Encyclopedia of Philosophy.

De wiskunde van de Booleaanse algebra

Voor het eerst gepubliceerd op 5 juli 2002; inhoudelijke herziening vr 27 feb. 2009

Booleaanse algebra is de algebra van logica met twee waarden met alleen sentimentele connectieven, of equivalent van algebra's van verzamelingen onder unie en complementatie. Het rigoureuze concept is dat van een bepaald soort algebra, analoog aan het wiskundige idee van een groep. Dit concept heeft wortels en toepassingen in de logica (Lindenbaum-Tarski-algebra's en modeltheorie), verzamelingenleer (velden van verzamelingen), topologie (volledig losgekoppelde compacte Hausdorff-ruimtes), grondslagen van verzamelingenleer (Booleaans gewaardeerde modellen), meettheorie (maat algebra's), functionele analyse (algebra's van projecties) en ringtheorie (Booleaanse ringen). De studie van Booleaanse algebra's heeft verschillende aspecten: structuurtheorie, modeltheorie van Booleaanse algebra's, beslisbaarheid en onbeslisbaarheidsvragen voor de klasse van Booleaanse algebra's en de aangegeven toepassingen. In aanvulling op,hoewel hier niet uitgelegd, zijn er verbindingen met andere logica's, subsumptie als onderdeel van speciale soorten algebraïsche logica, eindige booleaanse algebra's en schakelcircuittheorie en booleaanse matrices.

  • 1. Definitie en eenvoudige eigenschappen
  • 2. De elementaire algebraïsche theorie
  • 3. Speciale klassen van Booleaanse algebra's
  • 4. Structuurtheorie en kardinale functies op Booleaanse algebra's
  • 5. Beslisbaarheid en onbeslisbaarheid vragen
  • 6. Lindenbaum-Tarski-algebra's
  • 7. Booleaans gewaardeerde modellen
  • Bibliografie
  • Andere internetbronnen
  • Gerelateerde vermeldingen

1. Definitie en eenvoudige eigenschappen

Een Booleaanse algebra (BA) is een verzameling A samen met binaire operaties + en · en een unaire operatie -, en elementen 0, 1 van A zodat de volgende wetten gelden: commutatieve en associatieve wetten voor optellen en vermenigvuldigen, distributieve wetten voor zowel vermenigvuldigen over optellen en voor optellen over vermenigvuldigen, en de volgende speciale wetten:

x + (x · y) = x

x · (x + y) = x

x + (−x) = 1

x · (−x) = 0

Deze wetten worden beter begrepen in termen van het basisvoorbeeld van een BA, bestaande uit een verzameling A van deelverzamelingen van een verzameling X gesloten onder de operaties van vakbond, kruising, aanvulling met betrekking tot X, met leden ∅ en X. Uit deze axioma's kunnen gemakkelijk veel elementaire wetten worden afgeleid, rekening houdend met dit voorbeeld ter motivatie. Elke BA heeft een natuurlijke partiële orde ≤ erop gedefinieerd door te zeggen dat x ≤ y als en alleen als x + y = y. Dit komt in ons hoofdvoorbeeld overeen met ⊆. Van bijzonder belang is de BA met twee elementen, gevormd door de set X slechts één element te geven. De uit twee elementen bestaande BA toont de directe verbinding met de elementaire logica. De twee leden, 0 en 1, komen respectievelijk overeen met valsheid en waarheid. De Booleaanse operaties drukken dan de gewone waarheidstabellen uit voor disjunctie (met +), voegwoord (met ·) en ontkenning (met -).Een belangrijk elementair resultaat is dat een vergelijking in alle BA's geldt, en alleen als deze in de BA met twee elementen geldt. Vervolgens definiëren we x ⊕ y = (x · - y) + (y · - x). Dan vormt A samen met ⊕ en ·, samen met 0 en 1, een ring met identiteit waarin elk element idempotent is. Omgekeerd, gegeven een dergelijke ring, met toevoeging ⊕ en vermenigvuldiging, definieer x + y = x ⊕ y ⊕ (x · y) en - x = 1 ⊕ x. Dit maakt de ring tot een BA. Deze twee processen zijn elkaars omgekeerde, en laten zien dat de theorie van de Booleaanse algebra's en van ringen met identiteit waarin elk element idempotent is, per definitie equivalent is. Dit plaatst de theorie van BA's in een standaard onderzoeksobject in de algebra. Een atoom in een BA is een niet-nulelement a zodat er geen element b is met 0 <b <a. Een BA is atomair als elk niet-nulelement van de BA zich boven een atoom bevindt.Eindige BA's zijn atomair, maar dat geldt ook voor veel oneindige BA's. Onder de gedeeltelijke volgorde ≤ hierboven is x + y de kleinste bovengrens van x en y en is x · y de grootste ondergrens van x en y. We kunnen dit generaliseren: Σ X is de kleinste bovengrens van een verzameling X van elementen en Π X is de grootste ondergrens van een verzameling X van elementen. Deze bestaan ​​niet voor alle sets in alle Booleaanse algebra's; als ze altijd bestaan, zou de Booleaanse algebra compleet zijn.de Booleaanse algebra zou compleet zijn.de Booleaanse algebra zou compleet zijn.

2. De elementaire algebraïsche theorie

Verschillende algebraïsche constructies hebben duidelijke definities en eenvoudige eigenschappen voor BA's: subalgebra's, homomorfismen, isomorfismen en directe producten (zelfs van oneindig veel algebra's). Enkele andere standaard algebraïsche constructies zijn meer eigen aan BA's. Een ideaal in een BA is een deelverzameling die ik heb gesloten onder +, met 0 als lid, en zodanig dat als a ≤ b ∈ I, dan ook een ∈ I. Hoewel niet meteen duidelijk, is dit hetzelfde als het ringtheoretische concept. Er is een dubbel begrip van een filter (zonder tegenhanger in ringen in het algemeen). Een filter is een subset F gesloten onder ·, met 1 als lid, en zodanig dat als a ≥ b ∈ F, dan ook een ∈ F. Een ultrafilter op A is een filter F met de volgende eigenschappen: 0 ∉ F, en voor elke ∈ A ofwel een ∈ F of - een ∈ F. Voor elke ∈ A, laat S (a) = {F: F is een ultrafilter op A en een ∈ F}.Dan is S een isomorfisme op een BA van subsets van de set X van alle ultrafilters op A. Dit stelt de basisstelling van de steenrepresentatie vast en verduidelijkt de oorsprong van BA's als concrete algebra's van verzamelingen. Bovendien kunnen de sets S (a) worden gedeclareerd als basis voor een topologie op X, en dit verandert X in een volledig losgekoppelde compacte Hausdorff-ruimte. Dit brengt een een-een-overeenkomst tot stand tussen de klasse van BA's en de klasse van dergelijke ruimtes. Als gevolg hiervan, veel gebruikt in de theorie van BA's, hebben veel topologische stellingen en concepten gevolgen voor BA's. Als x een element is van een BA, laten we 0 x = - x en 1 x = x. Als (x (0), … x (m - 1)) een eindige reeks elementen van een BA A is, dan wordt elk element van de subalgebra van A gegenereerd door {x (0), …,x (m - 1)} kan worden geschreven als een som van monomials e (0) x (0) · … · e (m - 1) x (m - 1) voor e in een aantal functies die m = {0 in kaart brengen,…, M - 1} in 2 = {0, 1}. Dit is een algebraïsche uitdrukking van de disjunctieve normaalvormstelling van de sententiële logica. Een functie f van een verzameling X van generatoren van een BA A naar een BA B kan worden uitgebreid tot een homomorfisme als en alleen als e (0) x (0) · … · e (m - 1) x (m - 1) = 0 betekent altijd dat e (0) f (x (0)) · … · e (m - 1) f (x (m - 1)) = 0. Dit is het uitbreidingscriterium van Sikorski. Elke BA A kan zo worden ingebed in een complete BA B dat elk element van B de minste bovengrens is van een set elementen van A. B is uniek tot A-isomorfisme en wordt de voltooiing van A genoemd. Als f een homomorfisme is van een BA A naar een complete BA B, en als A een subalgebra van C is,dan kan f worden uitgebreid tot een homomorfisme van C in B. Dit is de uitbreidingsstelling van Sikorski. Een ander algemeen algebraïsch idee dat van toepassing is op Booleaanse algebra's is het idee van een vrije algebra. Dit kan concreet worden geconstrueerd voor BA's. Namelijk, de vrije BA op κ is de BA van gesloten-open subsets van de discrete ruimte met twee elementen, verhoogd tot de κ-macht.

3. Speciale klassen van Booleaanse algebra's

Er zijn veel speciale klassen van Booleaanse algebra die zowel belangrijk zijn voor de intrinsieke theorie van BA's als voor toepassingen:

  • Atomic BAs, hierboven al genoemd.
  • Atoomloze BA's, die zijn gedefinieerd als BA's zonder atomen. Elke oneindige gratis BA is bijvoorbeeld atoomloos.
  • Volledige BA's, hierboven gedefinieerd. Deze zijn vooral belangrijk in de grondslagen van de verzamelingenleer.
  • Intervalalgebra's. Deze zijn afgeleid van lineair geordende sets (L, <) met een eerste element als volgt. Men neemt de kleinste algebra van deelverzamelingen van L die alle halfopen intervallen [a, b) bevat met a in L en b in L of gelijk aan ∞. Deze BA's zijn nuttig bij de studie van Lindenbaum-Tarski-algebra's. Elke telbare BA is isomorf met een intervalalgebra, en dus kan een telbare BA worden beschreven door een geordende verzameling zodanig aan te geven dat deze isomorf is met de corresponderende intervalalgebra.
  • Boomalgebra's. Een boom is een gedeeltelijk geordende set (T, <) waarin de set voorgangers van elk element goed geordend is. Gegeven een dergelijke boom, beschouwt men de algebra van subsets van T gegenereerd door alle sets van de vorm {b: a ≤ b} voor sommigen in T.
  • Superatomische BA's. Dit zijn BA's die niet alleen atomair zijn, maar zodanig zijn dat elk subalgebra en homomorf beeld atomair is.

4. Structuurtheorie en kardinale functies op Booleaanse algebra's

Veel van de diepere theorie van Booleaanse algebra's, die vertellen over hun structuur en classificatie, kan worden geformuleerd in termen van bepaalde functies die zijn gedefinieerd voor alle Booleaanse algebra's, met oneindige kardinalen als waarden. We definiëren enkele van de belangrijkste van deze kardinale functies en noemen enkele van de bekende structurele feiten, meestal geformuleerd in termen van hen

  1. De cellulariteit c (A) van een BA is het supremum van de cardinaliteiten van sets van paarsgewijs gescheiden elementen van A.
  2. Een subset X van een BA A is onafhankelijk als X een set vrije generatoren is van de subalgebra die het genereert. De onafhankelijkheid van A is het supremum van kardinalen van onafhankelijke subsets van A.
  3. Een deelverzameling X van een BA A is dicht in A als elk niet-nulelement van A ≥ een niet-nulelement van X is. Het π-gewicht van A is de kleinste kardinaliteit van een dichte subset van A.
  4. Twee elementen x, y van A zijn onvergelijkbaar als geen van beide ≤ de andere is. Het supremum van kardinalen van subset X van A bestaande uit paarsgewijs onvergelijkbare elementen is de onvergelijkbaarheid van A.
  5. Een subset X van A is overbodig als er geen element van X in de door de anderen gegenereerde subalgebra zit.

Een belangrijk feit met betrekking tot cellulariteit is de stelling van Erdos-Tarski: als de cellulariteit van een BA een enkelvoudige kardinaal is, dan is er eigenlijk een reeks onsamenhangende elementen van die omvang; voor cellulariteit reguliere limiet (ontoegankelijk), zijn er tegenvoorbeelden. Elke oneindig complete BA heeft een onafhankelijke subset van dezelfde grootte als de algebra. Elke oneindige BA A heeft een overvloedige onvergelijkbare subset waarvan de grootte het π-gewicht van A is. Elke intervalalgebra heeft telbare onafhankelijkheid. Een superatomaire algebra heeft niet eens een oneindige onafhankelijke subset. Elke boomalgebra kan worden ingebed in een intervalalgebra. Een BA met alleen de identiteit automorfisme wordt star genoemd. Er bestaan ​​starre complete BA's, ook starre intervalalgebra's en starre boomalgebra's.

5. Beslisbaarheid en onbeslisbaarheid vragen

Een basisresultaat van Tarski is dat de elementaire theorie van Booleaanse algebra's beslissend is. Zelfs de theorie van Booleaanse algebra's met een onderscheiden ideaal is beslissend. Aan de andere kant is de theorie van een Booleaanse algebra met een voorname subalgebra onbeslist. Zowel de beslisbaarheidsresultaten als de onbeslisbaarheidsresultaten strekken zich op verschillende manieren uit tot Booleaanse algebra's in uitbreidingen van eerste-orde logica.

6. Lindenbaum-Tarski-algebra's

Een zeer belangrijke constructie, die doorwerkt in veel logica's en veel andere algebra's dan Booleaanse algebra's, is de constructie van een Booleaanse algebra die in een of andere logica aan de zinnen is gekoppeld. Het eenvoudigste geval is sententiële logica. Hier zijn er zinsymbolen en veelvoorkomende connectieven die daaruit langere zinnen opbouwen: disjunctie, voegwoord en ontkenning. Gegeven een reeks A van zinnen in deze taal, zijn twee zinnen s en t equivalent modulo A als en alleen als de biconditionele tussen hen een logisch gevolg is van A. Van de equivalentieklassen kan een BA worden gemaakt zodat + overeenkomt met disjunctie, · conjunctie en - negatie. Elke BA is isomorf voor een van deze vormen. Iets soortgelijks kan men doen voor een theorie van de eerste orde. Laat T een eerste-orde theorie zijn in een eerste-orde taal L.We noemen formules φ en ψ equivalent mits T ⊢ φ ↔ ψ. De equivalentieklasse van een zin φ wordt aangegeven met [φ]. Laat A de verzameling zijn van alle equivalentieklassen onder deze equivalentierelatie. We kunnen van A een BA maken door de volgende definities, die gemakkelijk te rechtvaardigen zijn:

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

Elke BA is isomorf voor een Lindenbaum-Tarski-algebra. Een van de belangrijkste toepassingen van deze klassieke Lindenbaum-Tarski-algebra's is echter om ze te beschrijven voor belangrijke theorieën (meestal beslisbare theorieën). Voor telbare talen kan dit worden gedaan door hun isomorfe intervalalgebra's te beschrijven. Dit geeft over het algemeen een grondige kennis van de theorie. Voorbeelden zijn:

Theorie Isomorf met intervalalgebra aan
(1) in wezen onbeslisbare theorie Q, de rationals
(2) BA's
Natuurlijk
Natuurlijk

×

Naturals
Naturals

, kwadraat van de positieve gehele getallen, lexicografisch gerangschikt

(3) lineaire orders Een x Q bestelde antilexicographically, waarbij A is

Naturals
Naturals

de

Naturals
Naturals

kracht in zijn gebruikelijke volgorde

(4) abelse groepen (Q + A) × Q

7. Booleaans gewaardeerde modellen

In de modeltheorie kan men waarden nemen in elke complete BA in plaats van de twee-elementen BA. Deze door Booleaans gewaardeerde modeltheorie werd ontwikkeld rond 1950-1970, maar er is sindsdien niet veel aan gewerkt. Maar een speciaal geval, door Booleaans gewaardeerde modellen voor verzamelingenleer, loopt sterk voorop in het huidige onderzoek naar verzamelingenleer. Het vormt eigenlijk een gelijkwaardige manier om naar de gedwongen constructie van Cohen te kijken, en heeft een aantal technische voor- en nadelen. Filosofisch lijkt het bevredigender dan het dwingende concept. We beschrijven deze verzamelingenleer hier het zal dan duidelijk worden waarom alleen competitieve BA's worden overwogen. Laat B een complete BA zijn. Eerst definiëren we het Booleaanse gewaardeerde universum V (B). Het gewone set-theoretische universum kan worden geïdentificeerd met V (2), waarbij 2 het 2-element BA is. De definitie is door transfinite recursie, waarbij α,β zijn ordinalen en λ is een limiet ordinaal:

V (B, 0) =
V (B, α + 1) = de verzameling van alle functies f zodat het domein van f een deelverzameling is van V (B, α) en het bereik van f een deelverzameling is van B
V (B, λ) = de vereniging van alle V (B, β) voor β <λ.

Het B-gewaardeerde universum is de juiste klasse V (B) die de vereniging is van al deze V's. Vervolgens definieert men door een nogal gecompliceerde transfinite recursie over goed gefundeerde sets de waarde van een set-theoretische formule met elementen van het Booleaanse gewaardeerde universum toegewezen aan zijn vrije variabelen

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

Bibliografie

  • Halmos, P., 1963, Lezingen over Booleaanse algebra's, Princeton: Van Nostrand
  • Heindorf, L., en Shapiro, L., 1994, bijna projectieve Booleaanse algebra's, aantekeningen bij wiskunde nr. 1596, Berlijn: Springer-Verlag
  • Jech, T., 1997, Set Theory, 2e gecorrigeerde editie, Berlijn, New York: Springer-Verlag
  • Monk, JD, en Bonnet, R., (eds), 1989, Handbook of Boolean algebras, 3 delen, Amsterdam: Noord-Holland.

Andere internetbronnen

[Neem contact op met de auteur voor suggesties.]

Populair per onderwerp