Boolsk algebra

Denne artikel handler om det algebraiske system . For den gren af matematisk logik, der studerer propositioner og operationer på dem, se Algebra of logic .

Boolsk algebra [1] [2] [3] er et ikke-tomt sæt A med to binære operationer (analog af konjunktion ), (analog af disjunktion ), en unær operation (analog af negation ) og to udvalgte elementer: 0 (eller Falsk) og 1 (eller Sand), således at for enhver a , b og c fra mængden A er følgende aksiomer sande : $\jord$ $\lor$ $\likke$

$a \lor (b \lor c) = (a \lor b) \lor c$	$a \land (b \land c) = (a \land b) \land c$	associativitet
$a \lor b = b \lor a$	$a \land b = b \land a$	kommutativitet
$a \lor (a \land b) = a$	$a \land (a \lor b) = a$	absorptionslove
$a \lor (b \land c) = (a \lor b) \land (a \lor c)$	$a \land (b \lor c) = (a \land b) \lor (a \land c)$	distributionsevne
$a \eller \likke a = 1$	$a \land \likke a = 0$	additionalitet

I notationen · + ¯

$\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}$

De første tre aksiomer betyder, at ( A ,, ) er et gitter . En boolsk algebra kan således defineres som et distributivt gitter , hvori de sidste to aksiomer holder. En struktur, hvor alle undtagen de næstsidste aksiomer gælder, kaldes en pseudo- boolsk algebra . Opkaldt efter George Boole . $\jord$ $\lor$

Nogle egenskaber

Det kan ses ud fra aksiomerne, at det mindste element er 0, det største er 1, og komplementet ¬ a af ethvert element a er entydigt bestemt. For alle a og b fra A gælder følgende ligheder også:

$a \lor a = a$	$a \land a = a$
$a \lor 0 = a$	$a \land 1 = a$
$eller 1 = 1$	$a\land 0 = 0$
$\likke 0 = 1$	$\likke 1 = 0$	komplement 0 er 1 og omvendt
$\likke (a \lor b) = \likke et \land \likke b$	$\likke (a \land b) = \likke en \eller \likke b$	de Morgans love
$\likke \likke a = a$ .		involutivity of negation , loven om fjernelse af dobbelt negation .

Grundlæggende identiteter

Dette afsnit gentager de ovenfor beskrevne egenskaber og aksiomer med tilføjelse af et par flere.

Oversigtstabel over egenskaber og aksiomer beskrevet ovenfor:

$a \lor b = b \lor a$	$a \land b = b \land a$	1 kommutativitet , bærbarhed
$a \lor (b \lor c) = (a \lor b) \lor c$	$a \land (b \land c) = (a \land b) \land c$	2 associativitet , kompatibilitet
3.1 konjunktion med hensyn til disjunktion $a \lor (b \land c) = (a \lor b) \land (a \lor c)$	3.2 disjunktion med hensyn til konjunktion $a \land (b \lor c) = (a \land b) \lor (a \land c)$	3 distributivitet , distributivitet
$a \eller \likke a = 1$	$a \land \likke a = 0$	4 komplementaritet , komplementaritet (egenskaber ved negationer)
$\likke (a \lor b) = \likke et \land \likke b$	$\likke (a \land b) = \likke en \eller \likke b$	5 De Morgans love
$a \lor (a \land b) = a$	$a \land (a \lor b) = a$	6 love for absorption
$a \lor(\likke a \land b) = a \lor b$	$a \land(\likke a \lor b) = a \land b$	7 Blake-Poretsky
$a \lor a = a$	$a \land a = a$	8 Idempotens
$\likke \likke a = a$		9 involutivitet af negation , loven om fjernelse af dobbelt negation
$a \lor 0 = a$	$a \land 1 = a$	10 konstante egenskaber
$eller 1 = 1$	$a\land 0 = 0$
addition 0 er 1 $\likke 0 = 1$	tilføjelse 1 ja 0 $\likke 1 = 0$
$(a \lor b)\land(\likke a \lor b)=b$	$(a \land b) \lor (\likke et \land b)=b$	11 Binding

Eksempler

Den enkleste ikke-trivielle boolske algebra indeholder kun to elementer, 0 og 1, og handlingerne i den er defineret af følgende tabel:

∧	0	en
0	0	0
en	0	en

∨	0	en
0	0	en
en	en	en

-en	0	en
¬a	en	0

Denne boolske algebra er mest almindeligt anvendt i logik , da det er en nøjagtig model af den klassiske propositionsregning . I dette tilfælde kaldes 0 falsk , 1 kaldes sand . Udtryk, der indeholder booleske operationer og variabler, er propositionelle former.

Mængden af alle delmængder af en given mængde S danner en boolsk algebra med hensyn til operationerne ∨ := ∪ (union), ∧ := ∩ (skæring) og den unære komplementoperation. Det mindste element her er det tomme sæt , og det største element er hele S.
Overvej mængden af alle naturlige divisorer af et givet kvadratfrit naturligt tal . Lad os definere to binære operationer: at finde den største fælles divisor (analog med konjunktion) og den mindste fælles multiplum (analog med disjunktion); rollen som negation spilles af en operation på ét sted, der tildeler en divisor til en divisor Den resulterende struktur er en boolsk algebra; i den er analogerne til boolsk nul og en henholdsvis tallene 1 og Arrangement af ovenstående generelle aksiomer og egenskaber for boolsk algebra for en mængde giver en række nyttige og ikke indlysende talteoretiske identiteter [4] . $U$ $m,$ $U$ $d$ $m/d.$ $m.$ $U$
Lindenbaum-Tarski-algebraen ( faktorsættet af alle udsagn med hensyn til ækvivalensen i den givne kalkulus med de tilsvarende operationer) af enhver propositionelregning er en boolsk algebra. I dette tilfælde er sandhedsestimatet af kalkulusformlerne en homomorfi af Lindenbaum-Tarski-algebraen til en to-element boolesk algebra.
Hvis R er en vilkårlig ring , så kan sættet af centrale idempotenter defineres på den som følger:
A = { e ∈ R : e ² = e , ex = xe , ∀ x ∈ R },
så vil mængden A være en Boolesk algebra med operationer e ∨ f : = e + f − ef og e ∧ f := ef .

Princippet om dualitet

Der er to udsagn i boolske algebraer, de er enten sande eller begge falske. Nemlig hvis vi i en formel, der er sand i en boolsk algebra, ændrer alle konjunktioner til disjunktioner, 0 til 1, ≤ til > og omvendt, eller < til ≥ og omvendt, så får vi en formel, der også er sand i denne boolske algebra. Dette følger af aksiomernes symmetri med hensyn til sådanne udskiftninger.

Repræsentationer af boolske algebraer

Det kan bevises, at enhver finit boolsk algebra er isomorf med den boolske algebra af alle delmængder af en eller anden mængde. Det følger heraf, at antallet af elementer i enhver endelig boolsk algebra vil være en potens af to.

Stones sætning siger, at enhver boolsk algebra er isomorf i forhold til den boolske algebra af alle clopen-sæt af et kompakt totalt adskilt Hausdorff topologisk rum .

Aksiomatisering

I 1933 foreslog den amerikanske matematiker Huntington følgende aksiomatisering for boolske algebraer:

Aksiom for kommutativitet : x + y = y + x .
Associativitetsaksiom : ( x + y ) + z = x + ( y + z ).
Huntingtons ligning : n ( n ( x ) + y ) + n ( n ( x ) + n ( y )) = x .

Huntingtons notation bruges her: + betyder disjunktion, n betyder negation.

Herbert Robbins stillede følgende spørgsmål: er det muligt at reducere det sidste aksiom som skrevet nedenfor, det vil sige, vil strukturen defineret af aksiomerne nedenfor være en boolsk algebra?

Aksiomatisering af Robbins algebra:

Aksiom for kommutativitet : x + y = y + x .
Associativitetsaksiom : ( x + y ) + z = x + ( y + z ).
Robbins ligning : n ( n ( x + y ) + n ( x + n ( y ))) = x .

Dette spørgsmål har været åbent siden 1930'erne og har været Tarskis og hans elevers yndlingsspørgsmål.

I 1996 gav William McCune , ved hjælp af nogle af de resultater, der var opnået før ham, et bekræftende svar på dette spørgsmål. Således er enhver Robbins algebra en boolsk algebra.

Se også

Noter

↑ D.A. Vladimirov. Springer Online Reference Works - Boolean algebra . Springer-Verlag (2002). Hentet 4. august 2010. Arkiveret fra originalen 9. februar 2012.
↑ Vladimirov, 1969 , s. 19.
↑ Kuznetsov, 2007 .
↑ Vilenkin N. Ya., Shibasov L. P. Shibasova 3. F. Bag siderne i en matematiklærebog: Aritmetik. Algebra. Geometri: Bog. for elever i 10.-11 almen uddannelse institutioner . - M . : Uddannelse : JSC "Uddannelseslitteratur", 1996. - S. 197. - 319 s.

Litteratur

Vladimirov D. A. Booleske algebraer . - M . : "Nauka", 1969. - 320 s.
Kuznetsov OP Diskret matematik for en ingeniør . - Sankt Petersborg. : Lan, 2007. - 394 s.
Ivanov B. N. Diskret matematik. Algoritmer og programmer. Videregående kursus . - M . : "Izvestia", 2011. - 512 s. (utilgængeligt link)
Gurov S.I. Booleske algebraer, ordnede sæt, gitter: definitioner, egenskaber, eksempler . - M. : Librokom, 2013. - 352 s.

Ordbøger og encyklopædier	Stor russer Universalis

Diskret matematik
Kombinatorik grafteori