Boolen algebra

Tämä artikkeli käsittelee algebrallista järjestelmää . Matemaattisen logiikan haarasta, joka tutkii lauseita ja niihin liittyviä operaatioita, katso logiikkaalgebra .

Boolen algebra [1] [2] [3] on ei-tyhjä joukko A , jossa on kaksi binaarioperaatiota ( konjunktion analogi ), ( disjunktion analogi ), yksi unaarioperaatio ( negation analogi ) ja kaksi valittua elementtiä: 0 (tai Epätosi) ja 1 (tai tosi) siten, että mille tahansa joukon A a , b ja c :lle seuraavat aksioomit ovat tosi : $\maa$ $\lor$ $\lei$

$a \lor (b \lor c) = (a \tai b) \tai c$	$a \maa (b \maa c) = (a \maa b) \maa c$	assosiatiivisuus
$a \lor b = b \tai a$	$a \maa b = b \maa a$	kommutatiivisuus
$a \lor (a \land b) = a$	$a \maa (a \tai b) = a$	absorptiolakeja
$a \lor (b \maa c) = (a \lor b) \maa (a \lor c)$	$a \maa (b \tai c) = (a \maa b) \lor (a \maa c)$	jakelukyky
$a \tai \lnot a = 1$	$a \land \lnot a = 0$	täydentävyyttä

Merkinnässä · + ¯

$\begin{align} & a+(b+c)=(a+b)+c & a(bc)=(ab)c \\ & a+b=b+a & ab=ba \\ & a+ab =a & a(a+b)=a \\ & a+bc=(a+b)(a+c) & a(b+c)=ab+ac \\ & a+\bar{a}=1 &a\bar{a} = 0 \end{align}$

Kolme ensimmäistä aksioomaa tarkoittavat , että ( A , , ) on hila . Siten Boolen algebra voidaan määritellä distributiiviseksi hilaksi , jossa kaksi viimeistä aksioomaa pätevät. Rakennetta, jossa kaikki paitsi toiseksi viimeiset aksioomat pätevät, kutsutaan pseudo- Boolen algebraksi . Nimetty George Boolen mukaan . $\maa$ $\lor$

Jotkut ominaisuudet

Aksioomista voidaan nähdä, että pienin alkio on 0, suurin on 1 ja minkä tahansa elementin a komplementti ¬ a on yksiselitteisesti määritetty. Kaikille a :lle ja b : lle A :sta seuraavat yhtälöt ovat tosia:

$a \lor a = a$	$a \land a = a$
$a \ tai 0 = a$	$a \land 1 = a$
$a\tai 1 = 1$	$a\land 0 = 0$
$\lnot 0 = 1$	$\lnot 1 = 0$	komplementti 0 on 1 ja päinvastoin
$\lnot (a \tai b) = \lnot a \land \lnot b$	$\lnot (a \land b) = \lnot a \tai \lnot b$	de Morganin lakeja
$\lnot \lnot a = a$ .		Negaation involutiivisuus , kaksoisnegaation poistamisen laki .

Perusidentiteetit

Tämä osio toistaa yllä kuvatut ominaisuudet ja aksioomit lisäten muutamalla lisää.

Yhteenvetotaulukko yllä kuvatuista ominaisuuksista ja aksioomista:

$a \lor b = b \tai a$	$a \maa b = b \maa a$	1 kommutatiivisuus , siirrettävyys
$a \lor (b \lor c) = (a \tai b) \tai c$	$a \maa (b \maa c) = (a \maa b) \maa c$	2 assosiatiivisuus , yhteensopivuus
3.1 konjunktio disjunktion suhteen $a \lor (b \maa c) = (a \lor b) \maa (a \lor c)$	3.2 disjunktio suhteessa konjunktiin $a \maa (b \tai c) = (a \maa b) \lor (a \maa c)$	3 distributiivisuus , distributiivisuus
$a \tai \lnot a = 1$	$a \land \lnot a = 0$	4 täydentävyys , täydentävyys (negatioiden ominaisuudet)
$\lnot (a \tai b) = \lnot a \land \lnot b$	$\lnot (a \land b) = \lnot a \tai \lnot b$	5 De Morganin lait
$a \lor (a \land b) = a$	$a \maa (a \tai b) = a$	6 absorption lakia
$a \lor(\lnot a \land b) = a \lor b$	$a \maa(\lnot a \tai b) = a \maa b$	7 Blake-Poretsky
$a \lor a = a$	$a \land a = a$	8 Idempotenssi
$\lnot \lnot a = a$		9 Negaation involutiivisuus , kaksoisnegaation poistamisen laki
$a \ tai 0 = a$	$a \land 1 = a$	10 vakioomaisuutta
$a\tai 1 = 1$	$a\land 0 = 0$
lisäys 0 on 1 $\lnot 0 = 1$	lisäys 1 kyllä 0 $\lnot 1 = 0$
$(a \tai b)\maa(\lnot a \tai b)=b$	$(a \land b) \lor (\lnot a \land b)=b$	11 Liimaus

Esimerkkejä

Yksinkertaisin ei-triviaali Boolen algebra sisältää vain kaksi elementtiä, 0 ja 1, ja sen toiminnot määritellään seuraavassa taulukossa:

∧	0	yksi
0	0	0
yksi	0	yksi

∨	0	yksi
0	0	yksi
yksi	yksi	yksi

a	0	yksi
¬a	yksi	0

Tätä Boolen algebraa käytetään yleisimmin logiikassa , koska se on klassisen lauselaskennan tarkka malli . Tässä tapauksessa arvoa 0 kutsutaan epätosi , 1:tä kutsutaan tosi . Boolen operaatioita ja muuttujia sisältävät lausekkeet ovat lausemuotoja.

Tietyn joukon S kaikkien osajoukkojen joukko muodostaa Boolen algebran operaatioiden ∨ := ∪ (liitto), ∧ := ∩ (leikkaus) ja unaarikomplementtioperaation suhteen. Pienin elementti tässä on tyhjä joukko ja suurin alkio on koko S.
Tarkastellaan tietyn neliöttömän luonnollisen luvun kaikkien luonnollisten jakajien joukkoa . Määritellään kaksi binäärioperaatiota: suurimman yhteisen jakajan löytäminen (analoginen konjunktiolle) ja pienimmän yhteisen kerrannaisen (analoginen disjunktiolle); Negaation roolia esittää yksipaikkainen operaatio, joka määrittää jakajan jakajalle Tuloksena oleva rakenne on Boolen algebra; siinä Boolen nollan ja ykkösen analogit ovat vastaavasti luvut 1 ja Boolen algebran edellä olevien yleisten aksioomien ja ominaisuuksien järjestys joukolle antaa joukon hyödyllisiä ja epäselviä lukuteoreettisia identiteettejä [4] . $U$ $m,$ $U$ $d$ $m/d.$ $m.$ $U$
Minkä tahansa lauselaskennan Lindenbaum-Tarskin algebra ( kaikkien lauseiden tekijäjoukko suhteessa ekvivalenssiin annetussa laskussa vastaavien operaatioiden kanssa) on Boolen algebra. Tässä tapauksessa laskentakaavojen totuusestimaatti on Lindenbaum-Tarskin algebran homomorfismi kaksielementtiseksi Boolen algebraksi.
Jos R on mielivaltainen rengas , niin joukko keskeisiä idempotentteja voidaan määritellä sille seuraavasti:
A = { e ∈ R : e² = e , ex = xe , ∀ x ∈ R }, silloin joukko A on a Boolen algebra operaatioilla e ∨ f : = e + f − ef ja e ∧ f := ef .

Kaksinaisuuden periaate

Boolen algebroissa on kaksoislauseita, ne ovat joko tosia tai molemmat vääriä. Nimittäin, jos kaavassa, joka on tosi jossain Boolen algebrassa, muutamme kaikki konjunktiot disjunktioiksi, 0 - 1, ≤ > ja päinvastoin tai < ≥ ja päinvastoin, niin saadaan kaava, joka on tosi myös tämä Boolen algebra. Tämä seuraa aksioomien symmetriasta tällaisten korvausten suhteen.

Boolen algebroiden esitykset

Voidaan todistaa, että mikä tahansa äärellinen Boolen algebra on isomorfinen jonkin joukon kaikkien osajoukkojen Boolen algebralle. Tästä seuraa, että minkä tahansa äärellisen Boolen algebran elementtien lukumäärä on kahden potenssi.

Stonen lause sanoo, että mikä tahansa Boolen algebra on isomorfinen jonkin kompaktin , täysin irrallisen Hausdorffin topologisen avaruuden kaikkien clopen-joukkojen Boolen algebralle .

Aksiomatisointi

Vuonna 1933 amerikkalainen matemaatikko Huntington ehdotti seuraavaa aksiomatisointia Boolen algebroille:

Kommutatiivisuuden aksiooma : x + y = y + x .
Assosiatiivisuusaksiooma : ( x + y ) + z = x + ( y + z ).
Huntingtonin yhtälö : n ( n ( x ) + y ) + n ( n ( x ) + n ( y )) = x .

Tässä käytetään Huntingtonin merkintää: + tarkoittaa disjunktiota, n tarkoittaa negaatiota.

Herbert Robbins esitti seuraavan kysymyksen: onko mahdollista pelkistää viimeinen aksiooma alla kirjoitetulla tavalla, eli onko alla kirjoitettujen aksioomien määrittelemä rakenne Boolen algebra?

Robbinsin algebran aksiomatisointi:

Kommutatiivisuuden aksiooma : x + y = y + x .
Assosiatiivisuusaksiooma : ( x + y ) + z = x + ( y + z ).
Robbinsin yhtälö : n ( n ( x + y )+ n ( x + n ( y )))= x .

Tämä kysymys on pysynyt avoimena 1930-luvulta lähtien ja on ollut Tarskin ja hänen oppilaidensa suosikkikysymys.

Vuonna 1996 William McCune antoi tähän kysymykseen myöntävän vastauksen käyttämällä joitakin ennen häntä saatuja tuloksia. Siten mikä tahansa Robbinsin algebra on Boolen algebra.

Katso myös

Muistiinpanot

↑ D.A. Vladimirov. Springer Online Reference Works - Boolen algebra . Springer-Verlag (2002). Haettu 4. elokuuta 2010. Arkistoitu alkuperäisestä 9. helmikuuta 2012.
↑ Vladimirov, 1969 , s. 19.
↑ Kuznetsov, 2007 .
↑ Vilenkin N. Ya., Shibasov L. P. Shibasova 3. F. Matematiikan oppikirjan sivujen takana: Aritmetiikka. Algebra. Geometria: Kirja. 10-11 luokkien opiskelijoille Yleissivistävä koulutus laitokset . - M . : Koulutus : JSC "Oppikirjallisuus", 1996. - S. 197. - 319 s.

Kirjallisuus

Vladimirov D. A. Boolen algebrat . - M . : "Nauka", 1969. - 320 s.
Kuznetsov OP Diskreetti matematiikka insinöörille . - Pietari. : Lan, 2007. - 394 s.
Ivanov B. N. Diskreetti matematiikka. Algoritmit ja ohjelmat. Syventävä kurssi . - M . : "Izvestia", 2011. - 512 s. (linkki ei saatavilla)
Gurov S.I. Boolen algebrat, järjestetyt joukot, hilat: määritelmät, ominaisuudet, esimerkit . - M. : Librokom, 2013. - 352 s.

Sanakirjat ja tietosanakirjat	Iso venäläinen Universalis

Diskreetti matematiikka
Kombinatoriikka graafiteoria