En àlgebra abstracta, un àlgebra de Boole o retícul booleano és un retícul complementat distributivo. Este tipo d'estructura algebraica captura propietats essencials tant de les operacions sobre conjunts com de les operacions llògiques. Un àlgebra de Boole pot vore's com una generalisació d'un àlgebra de potència o d'un camp de conjunts, o els seus elements poden interpretar-se com valor de veresos generalisats. També és un cas particular d'àlgebra de De Morgan i d'àlgebra de Kleene (en involució).

Tot àlgebra de Boole dona lloc a un anell booleano, i viceversa, en la multiplicació de l'anell corresponent a la conjunció o meet ∧, i la suma de l'anell a la disjunció exclusiva o diferència simètrica (no a la disjunció ∨). No obstant, la teoria dels anells booleanos presenta una asimetria inherent entre els dos operadors, mentres que els axiomes i teoremes de l'àlgebra de Boole expressen la simetria de la teoria descrita pel principi de dualitat.[1]

Retícul booleano de subconjunts

Història

El terme «àlgebra de Boole» honra a George Boole (1815–1864), un matemàtic anglés autodidacta. Va introduir el sistema algebraic inicialment en un chicotet panflet, The Mathematical Analysis of Logic, publicat en 1847 en resposta a una controvèrsia pública en curs entre Augustus De Morgan i William Hamilton, i més tart com un llibre més substancial, Les lleis del pensament, publicat en 1854. La formulació de Boole diferix en alguns aspectes importants de la descrita anteriorment. Per eixemple, la conjunció i la disjunció en Boole no eren un parell dual d'operacions. L'àlgebra de Boole va sorgir en la década de 1860, en treballs escrits per William Jevons i Charles Sanders Peirce.

La primera presentació sistemàtica de l'àlgebra de Boole i dels retículs distributivos es deu a les Vorlesungen de 1890 d'Ernst Schröder. El primer tractament extens de l'àlgebra de Boole en anglés és Universal Algebra d'A. N. Whitehead en 1898. L'àlgebra de Boole com a estructura algebraica axiomàtica en el sentit axiomàtic modern comença en un artícul de 1904 d'Edward V. Huntington.[2] L'àlgebra de Boole va alcançar la seua madurea com a matemàtica séria en els treballs de Marshall Stone en la década de 1930, i en Lattice Theory de Garrett Birkhoff en 1940. En la década de 1960, Paul Cohen, Dana Scott i uns atres varen trobar resultats profunts nous en llògica matemàtica i teoria axiomàtica de conjunts utilisant derivats de l'àlgebra de Boole, concretament el forçat i el model booleanos.

Definició

Un àlgebra de Boole és un conjunt A, equipat en dos operació binàries ∧ (cridada «meet» o «i»), ∨ (cridada «join» o «o»), una operació unaria ¬ (cridada «complement» o «no») i dos elements 0 i 1 en A (cridats «element inferior» i «element superior», o «element mínim» i «element màxim», també denotats pels símbols ⊥ i ⊤, respectivament), tals que para tots els elements a, b i c de A, es complixen els següents axiomes:[3]

a ∨ (b ∨ c) = (a ∨ b) ∨ c a ∧ (b ∧ c) = (a ∧ b) ∧ c asociatividad
a ∨ b = b ∨ a a ∧ b = b ∧ a commutativitat
a ∨ (a ∧ b) = a a ∧ (a ∨ b) = a llei d'absorció
a ∨ 0 = a a ∧ 1 = a element identitat
a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) distributividad
a ∨ ¬a = 1 a ∧ ¬a = 0 complements

Note's, no obstant, que la llei d'absorció i inclús la llei de asociatividad poden excloure's del conjunt de axioma, ya que poden derivar-se dels atres axioma.

Un àlgebra de Boole en un sol element es diu àlgebra de Boole trivial o àlgebra de Boole degenerada. (En treballs antics, alguns autors requerien que 0 i 1 anaren elements distints per a excloure este cas.)cita requerida

Dels últims tres parells de axioma anteriors (identitat, distributividad i complements), o de l'axioma d'absorció, es deduïx que

a = b ∧ a si i solament si a ∨ b = b.

La relació ≤ definida per a ≤ b si es complixen estes condicions equivalents, és un orde parcial en element mínim 0 i element màxim 1. El meet a ∧ b i el join a ∨ b de dos elements coincidixen en el seu ínfim i suprem, respectivament, respecte de ≤.

Els primers quatre parells de axioma constituïxen una definició d'un retícul acotat.

Es deduïx dels primers cinc parells de axioma que tot complement és únic.

El conjunt de axioma és auto-dual en el sentit de que si s'intercanvien ∨ en ∧ i 0 en 1 en un axioma, el resultat és novament un axioma. Per lo tant, aplicant esta operació a un àlgebra de Boole (o retícul booleano), s'obté un atre àlgebra de Boole en els mateixos elements; es diu el seu dual.[4]

Vore també

Notes

Referències

  1. ↑ Givant i Halmos, 2009, p. 20.
  2. ↑ Huntington, 1904, p. 288.
  3. ↑ Davey i Priestley, 1990, pp. 109, 131, 144.
  4. ↑ Goodstein, 2012, p. 21ff.

Bibliografia

Referències generals

  • Brown, Stephen; Vranesic, Zvonko(2002).«Fundamentals of Digital Logic with VHDL Design».McGraw–Hill.(en en). Vore Section 2.5
  • Cori, Rene; Lascar, Daniel(2000).«Mathematical Logic: A Course with Exercises».Oxford University Press.(en en). Vore Chapter 2.