Boole-algebra

Ez a cikk az algebrai rendszerről szól . A matematikai logika azon ágához, amely kijelentéseket és az azokra vonatkozó műveleteket vizsgál, lásd : Logikai algebra .

A logikai algebra [1] [2] [3] egy nem üres A halmaz két bináris művelettel ( konjunkció analógja ), ( diszjunkció analógja ), egy unáris művelettel ( tagadás analógja ) és két kiválasztott elemmel: 0 (vagy Hamis) és 1 (vagy igaz), így az A halmaz bármely a , b és c esetén a következő axiómák igazak : $\föld$ $\lor$ $\lnem$

$a \lor (b \lor c) = (a \lor b) \lor c$	$a \föld (b \föld c) = (a \föld b) \föld c$	asszociativitás
$a \lor b = b \vagy a$	$a \föld b = b \föld a$	kommutativitás
$a \lor (a \land b) = a$	$a \land (a \lor b) = a$	abszorpciós törvények
$a \lor (b \föld c) = (a \lor b) \föld (a \lor c)$	$a \land (b \lor c) = (a \land b) \lor (a \land c)$	disztributivitás
$a \vagy \lnot a = 1$	$a \land \lnot a = 0$	addicionalitás

A · + ¯ jelölésben

$\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{igazítás}$

Az első három axióma azt jelenti, hogy ( A , , ) egy rács . Így a Boole-algebra olyan eloszlási rácsként definiálható, amelyben az utolsó két axióma érvényes. Azt a struktúrát, amelyben az utolsó előtti axiómák kivételével az összes axióma érvényes, pszeudo- Boole-algebrának nevezzük . George Boole -ról kapta a nevét . $\föld$ $\lor$

Néhány tulajdonság

Az axiómákból látható, hogy a legkisebb elem 0, a legnagyobb 1, és bármely a elem ¬ a komplementere egyedileg meghatározott . Az A -ból származó a és b mindegyikére igazak a következő egyenlőségek is:

$a \lor a = a$	$a \land a = a$
$a \lor 0 = a$	$a \land 1 = a$
$a\vagy 1 = 1$	$a\land 0 = 0$
$\lnot 0 = 1$	$\lnot 1 = 0$	a 0 komplementer 1 és fordítva
$\lnot (a \lor b) = \lnot a \land \lnot b$	$\lnot (a \land b) = \lnot a \lor \lnot b$	de Morgan törvényei
$\lnot \lnot a = a$ .		a tagadás involutivitása , a kettős tagadás eltávolításának törvénye .

Alapvető identitások

Ez a szakasz megismétli a fent leírt tulajdonságokat és axiómákat néhány további hozzáadásával.

A fent leírt tulajdonságok és axiómák összefoglaló táblázata:

$a \lor b = b \vagy a$	$a \föld b = b \föld a$	1 kommutativitás , hordozhatóság
$a \lor (b \lor c) = (a \lor b) \lor c$	$a \föld (b \föld c) = (a \föld b) \föld c$	2 asszociativitás , kompatibilitás
3.1 konjunkció a diszjunkció tekintetében $a \lor (b \föld c) = (a \lor b) \föld (a \lor c)$	3.2 diszjunkció a konjunkció tekintetében $a \land (b \lor c) = (a \land b) \lor (a \land c)$	3 disztributivitás , disztributivitás
$a \vagy \lnot a = 1$	$a \land \lnot a = 0$	4 komplementaritás , komplementaritás (a tagadások tulajdonságai)
$\lnot (a \lor b) = \lnot a \land \lnot b$	$\lnot (a \land b) = \lnot a \lor \lnot b$	5 De Morgan törvényei
$a \lor (a \land b) = a$	$a \land (a \lor b) = a$	Az abszorpció 6 törvénye
$a \lor(\lnot a \land b) = a \lor b$	$a \land(\lnot a \lor b) = a \land b$	7 Blake-Poreckij
$a \lor a = a$	$a \land a = a$	8 Idempotencia
$\lnot \lnot a = a$		9 a tagadás involutivitása , a kettős tagadás eltávolításának törvénye
$a \lor 0 = a$	$a \land 1 = a$	10 állandó tulajdonság
$a\vagy 1 = 1$	$a\land 0 = 0$
összeadás 0 az 1 $\lnot 0 = 1$	összeadás 1 igen 0 $\lnot 1 = 0$
$(a \lor b)\land(\lnot a \lor b)=b$	$(a \land b) \lor (\lnot a \land b)=b$	11 Ragasztás

Példák

A legegyszerűbb, nem triviális Boole-algebra csak két elemet tartalmaz, a 0-t és az 1-et, és a benne lévő műveleteket a következő táblázat határozza meg:

∧	0	egy
0	0	0
egy	0	egy

∨	0	egy
0	0	egy
egy	egy	egy

a	0	egy
¬a	egy	0

Ezt a Boole-algebrát leggyakrabban a logikában használják , mivel ez a klasszikus propozíciós számítás pontos modellje . Ebben az esetben a 0-t hamisnak , az 1-et igaznak nevezzük . A logikai műveleteket és változókat tartalmazó kifejezések propozíciós formák.

Egy adott S halmaz összes részhalmaza egy Boole-algebrát alkot a ∨ := ∪ (egyesülés), ∧ := ∩ (metszéspont) és az unáris komplementművelet tekintetében. A legkisebb elem itt az üres halmaz , a legnagyobb elem pedig az egész S.
Tekintsük egy adott négyzet nélküli természetes szám összes természetes osztójának halmazát . Definiáljunk két bináris műveletet: a legnagyobb közös osztó megtalálása (analóg a konjunkcióval) és a legkisebb közös többszörös (analóg a diszjunkcióval); a negáció szerepét egy egyhelyes művelet játssza, amely osztót rendel az osztóhoz.A kapott struktúra egy Boole-algebra; benne a Boole-féle nulla és egy analógjai rendre az 1-es számok, és a Boole-algebra fenti általános axiómáinak és tulajdonságainak elrendezése halmazra számos hasznos és nem nyilvánvaló számelméleti azonosságot ad [4] . $U$ $m,$ $U$ $d$ $m/d.$ $m.$ $U$
Bármely kijelentésszámítás Lindenbaum-Tarski algebra ( az adott számításban a megfelelő műveletekkel való ekvivalenciára vonatkozó összes állítás faktorhalmaza) egy Boole-algebra . Ebben az esetben a számítási képletek igazságbecslése a Lindenbaum-Tarski algebra homomorfizmusa egy kételemes Boole-algebrává.
Ha R egy tetszőleges gyűrű , akkor a központi idempotensek halmaza a következőképpen definiálható rajta:
A = { e ∈ R : e ² = e , ex = xe , ∀ x ∈ R },
akkor az A halmaz egy Boole-algebra e ∨ f : = e + f − ef és e ∧ f := ef műveletekkel .

A kettősség elve

A Boole-algebrákban kettős állítások vannak, vagy mindkettő igaz, vagy mindkettő hamis. Ugyanis, ha egy olyan képletben, amely bizonyos Boole-algebrában igaz, az összes kötőszót diszjunkcióra változtatjuk, 0-t 1-re, ≤ >-re és fordítva, vagy <-t ≥-re és fordítva, akkor egy olyan képletet kapunk, amely igaz ez a Boole-algebra. Ez az axiómák szimmetriájából következik az ilyen helyettesítések tekintetében.

Boole-algebrák ábrázolásai

Bebizonyítható, hogy bármely véges Boole-algebra izomorf valamely halmaz összes részhalmazának Boole-algebrájával. Ebből következik, hogy bármely véges Boole-algebra elemeinek száma kettő hatványa lesz.

Stone tétele kimondja, hogy bármely Boole-algebra izomorf valamilyen kompakt , teljesen szétválasztott Hausdorff topológiai tér összes clopen halmazának Boole-algebrájával .

Axiomatizálás

1933- ban Huntington amerikai matematikus a következő javasolta a Boole-algebrák számára:

A kommutativitás axiómája : x + y = y + x .
Aszociativitási axióma : ( x + y ) + z = x + ( y + z ).
Huntington-egyenlet : n ( n ( x ) + y ) + n ( n ( x ) + n ( y )) = x .

Itt a Huntington-féle jelölést használjuk: + diszjunkciót, n tagadást jelent.

Herbert Robbins a következő kérdést tette fel: lehetséges-e redukálni az utolsó axiómát az alábbiak szerint, vagyis az alább írt axiómák által meghatározott szerkezet Boole-algebra lesz?

A Robbins algebra axiomatizálása:

A kommutativitás axiómája : x + y = y + x .
Aszociativitási axióma : ( x + y ) + z = x + ( y + z ).
Robbins egyenlet : n ( n ( x + y )+ n ( x + n ( y )))= x .

Ez a kérdés az 1930-as évek óta nyitott maradt, és Tarski és tanítványai kedvenc kérdése.

1996- ban William McCune az előtte kapott eredmények egy részét felhasználva igenlő választ adott erre a kérdésre. Így minden Robbins-algebra Boole-algebra.

Lásd még

Jegyzetek

↑ D. A. Vladimirov. Springer Online Reference Works – Boole-algebra . Springer-Verlag (2002). Letöltve: 2010. augusztus 4. Az eredetiből archiválva : 2012. február 9..
↑ Vladimirov, 1969 , p. 19.
↑ Kuznyecov, 2007 .
↑ Vilenkin N. Ya., Shibasov L. P. Shibasova 3. F. Egy matematika tankönyv lapjai mögött: Számtan. Algebra. Geometria: Könyv. osztályos tanulók számára a 10-11 Általános oktatás intézmények . - M . : Oktatás : JSC "Oktatási irodalom", 1996. - S. 197. - 319 p.

Irodalom

Vladimirov D. A. Boole-algebrák . - M . : "Nauka", 1969. - 320 p.
Kuznyecov OP Diszkrét matematika mérnöknek . - Szentpétervár. : Lan, 2007. - 394 p.
Ivanov B. N. Diszkrét matematika. Algoritmusok és programok. Haladó tanfolyam . - M . : "Izvestija", 2011. - 512 p. (nem elérhető link)
Gurov S.I. Boole-algebrák, rendezett halmazok, rácsok: definíciók, tulajdonságok, példák . - M. : Librokom, 2013. - 352 p.

Szótárak és enciklopédiák	Nagy orosz Universalis

Diszkrét matematika
Kombinatorika gráfelmélet