Álgebra booliana (estrutura)

Em álgebra abstrata, a álgebra booleana ou álgebra reticulada é um reticulado distribuído complementar. Este tipo de estrutura estrutura algébrica captura propriedades essenciais das operações de conjuntos e operações lógicas. A álgebra booleana pode ser vista como uma generalização do conjunto das partes algébrico ou como um campo de conjuntos, ou seus elementos pode ser vistos como valores verdades generalizados. Ele também é um caso especial da álgebra de De Morgan e da álgebra de Kleene.

Um anel booleano é, essencialmente, o mesmo que uma álgebra booleana, com o anel multiplicador correspondendo a uma conjunção ∧, e o anel somador correspondendo a uma disjunção exclusiva ou uma diferença simétrica (não disjunção ∨).

História

O termo “álgebra booleana” honra George Boole (1815-1864), um matemático inglês autodidata. Ele introduziu o sistema algébrico inicialmente em uma pequena publicação chamada The Mathematical Analysis of Logic, publicada em 1847. Alguns anos depois veio um outro livro, Leis do Pensamento, publicado em 1854. A formulação de Boole difere do que foi descrito acima, em alguns aspectos importantes. Por exemplo, conjunção e disjunção para Boole não eram pares de operações. A álgebra booleana por volta de 1860, em aritgos escritos por William Jevons e Charles Sanders Peirce. A primeira apresentação sistemática da álgebra booleana e reticulados distribuídos aconteceu devido a Vorlesungen de Ernst Schröder, em 1890. O primeiro tratamento extensivo de Álgebra booleana em Inglês foi em 1898 com a Álgebra Universal de N. Whitehead. A álgebra booleana, como uma estrutura axiomática no senso moderno de axiomático, começou em 1904 com o artigo de Edward V. Huntington. A álgebra booleana começou a ser considerada uma matemática séria com o trabalho de Marshal Stone em 1930, e com Garret Birkhoff em 1940, a Teoria do Reticulado. Na década de 60, Paul Cohen, Dana Scott, e outros acharam novos resultados profundos na matemática lógica e teoria dos conjuntos usando ramificações da álgebra booleana, ou seja, usando o forçamento e modelo booleano-valorizado.

Definição

A álgebra boolena é uma seis-tupla consistido de um conjunto A, equipado com duas operações binárias ∧ (chamado de “e”), ∨ (chamado de “ou”), a operação unária ¬ (chamada de “complemento” ou “negação”) e dois elementos 0 e 1 (chamado de “bottom” e “top”, ou “menor” e “maior” elemento, também denotado pelos símbolos ⊥ e ⊤, respectivamente), tal que, para todos os elementos a,b e c de A, os seguintes axiomas abaixo:

a ∨ (b ∨ c) = (a ∨ b) ∨ c a ∧ (b ∧ c) = (a ∧ b) ∧ c associatividade
a ∨ b = b ∨ a a ∧ b = b ∧ a comutatividade
a ∨ (a ∧ b) = a a ∧ (a ∨ b) = a absorção
a ∨ 0 = a a ∧ 1 = a identidade
a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) distributividade
a ∨ ¬a = 1 a ∧ ¬a = 0 complemento reticular

A álgebra booleana com apenas um elemento é chamada de álgebra booleana trivial (alguns autores requerem 0 e 1 para serem elementos distintos, a fim de excluir este caso).

Seguindo os três últimos pares de axiomas acima (identidade, distributividade e complemento), isso

a = b ∧ a     se somente se     a ∨ b = b.

A relação ≤ definida por a ≤ b se essas condições são equivalentes, um conjunto parcial com o menor elemento 0 e o maior elemento 1. A conjunção a ∧ b e a disjunção a ∨ b em dois elementos coincidem com o seu ínfimo e o seu supremo, respectivamente, com a relação ≤.

Os quatro primeiros pares de axiomas constituem a definição de reticulados delimitados.

Segue-se que os cinco pares de axiomas que qualquer complemento é único.

Exemplos

  • O mais simples não trivial na álgebra booleana, o dois elementos da álgebra booleana, tem apenas dois elementos, 0 e 1, definido pelas regas:
∧ 0 1
0 0 0
1 0 1
∨ 0 1
0 0 1
1 1 1
a 0 1
¬a 1 0
  • Uma aplicação em lógica, interpretando 0 como falso, 1 como verdadeiro, ∧ como “e”, ∨ como “ou”, ¬ como “negação”. Expressões envolvendo variáveis e operadores booleanos representam formas declaradas, e duas dessas expressões podem ser mostradas para serem iguais usando os axiomas acima se e somente se as formas declaradas correspondentes são logicamente equivalentes.
  • A álgebra de dois elementos também é usada para design de circuitos em engenharia elétrica, onde 0 e 1 representam dois diferentes estados de um bit em um circuito digital, como alta e baixa voltagem. Circuitos são descritos por expressões contendo variáveis, e duas dadas expressões são iguais para todos os valores das variáveis se e somente se os circuitos correspondentes tem o mesmo comportamento de entradas e saídas. Além disso, cada possível comportamento de entrada e saída podem ser modeladas utilizando uma expressão booleana apropriada.
  • A álgebra de dois elementos também é importante na teoria de álgebra booleana, porque uma equação envolvendo um grande número de variáveis é geralmente verdade em todas as álgebras booleanas se e somente se ela é verdade em uma álgebra de dois elementos(o que pode ser provado por um algoritmo de força bruta com um pequeno número de variáveis). Isso pode, por exemplo, ser usado para mostrar que as seguintes leis (teoremas do consenso) são geralmente válidas em todas as álgebras booleanas:
      • (a ∨ b) ∧ (¬a ∨ c) ∧ (b ∨ c) ≡ (a ∨ b) ∧ (¬a ∨ c)
      • (a ∧ b) ∨ (¬a ∧ c) ∨ (b ∧ c) ≡ (a ∧ b) ∨ (¬a ∧ c)
  • O conjunto das partes (conjunto de todos os subconjuntos) de um dado não-vazio conjunto S de formulas a álgebra booleana, como álgebra dos conjuntos, com duas operações ∨:= ∪ (união) e ∧:= ∩ (interseção). O menor elemento 0 é o conjunto vazio e o maior elemento é o 1 que é o próprio conjunto S.
    • Depois da álgebra de dois elementos, o mais simples booleano algébrico é aquele que é definido pelo conjunto das partes de dois átomos.
∧ 0 a b 1
0 0 0 0 0
a 0 a 0 a
b 0 0 b b
1 0 a b 1
∨ 0 a b 1
0 0 a b 1
a a a 1 1
b b 1 b 1
1 1 1 1 1
x 0 a b 1
¬x 1 b a 0
  • O conjunto das partes de todos os subconjuntos são tanto finitos ou cofinitos é a álgebra booleana, como a álgebra dos conjuntos.

Homomorfismo e isomorfismo

O homomorfismo entre dois booleanos algébricos A e B é uma função f: A → B, tal que para todo a, b em A:

f(a ∨ b) = f(a) ∨ f(b),
f(a ∧ b) = f(a) ∧ f(b),
f(1) = 1.

Segue-se então que f(¬a) = ¬f(a) para todos a em A e f(0) = 0. A classe de todos os booleanos algébricos, juntamente com essa noção de morfismo, forma uma subcategoria de reticulados.

Aneis booleanos

Todo algébrico booleano (A, ∧, ∨) dá origem a um anel (A, +, •) definindo a + b:= (a ∧ ¬b) ∨ (b ∧ ¬a) = (a ∨ b) ∧ ¬(a ∧ b) (esta operação chama-se diferença simétrica, no caso dos conjuntos e en:XOR no caso da lógica) e b:= a ∧ b. O elemento zero deste anel coincide com o 0 da álgebra booleana, o elemento do anel de identidade multiplicava é o 1 da álgebra booleana. Este anel tem a propriedade de que a • a = a para todo a em A; Anéis com propriedades são chamados de anéis de boolean.

Por outro lado, se um anel booleana A é dado, podemos transformá-lo em uma álgebra booleana definindo x ∨ y:= x + y + (x • y) e x ∧ y:= x • y. Uma vez que estas duas construções são inversas uns das outras, podemos dizer que cada anel booleano surge da uma álgebra booleana, e vice-versa. Além disso, um mapeamento f: A  B é um homomorfismo de álgebras booleanas se e somente se ele é um homomorfismo de anéis booleanos. As categorias de anéis booleanos e álgebras booleanas equivalentes.

Hsiang (1985) deu um algoritmo baseado em regras para verificar se duas expressões arbitrárias denotam o mesmo valor em cada anel booleano. Mais geralmente, Boudet, Jouannaud, e Schimit-Schauß (1989) deu um algoritmo para resolver equações entre as expressões de um anel booleano arbitrário. Empregando assim a semelhança de anéis booleanos e álgebras booleana, ambos os algoritmos têm aplicações de prova de teorema automatizado.

Ideal e Filtro

Um ideal de um booleano algébrico A é um subconjunto I tal que para todo x, y em I, temos x ∨ y em I e para todo a em A, temos a ∧ x em I. Esta noção de ideal coincide com a noção de anel ideal no anel booleano A. Um ideal I de a é chamado de primo se I ≠ A e se a ∧ b em I sempre implica a em I ou b em I. Além disso, para cada a ∈ A temos que a ∧ -a = 0 ∈ I e, em seguida, a ∈ I ou -a ∈ I para cada a ∈ A, se I é primo. Um ideal I de A é chamado de máximo se I ≠ A e se o único ideal que contém I é o próprio A. Para um ideal I, se a ∉ I e ¬a∉ I, então I ∪ {a} ou I ∪ {-a} está devidamente contido em outro ideal J. Com isso, I não é máximo e, portanto, as noções de ideal primo e ideal máximo são equivalentes em álgebra booleana.

A dupla de um ideal é um filtro. Um filtro da álgebra booleana A é um subconjunto p tal que para todo x, y em p temos x ∧ y em p e para todos a em A, temos a ∨ x em p. A dupla de um máximo (ou primo) ideal em uma álgebra booleana é ultrafiltro. A declaração de cada filtro em uma álgebra booleana pode ser estendida para um ultrafiltro é chamada de Teorema do Ultrafiltro e não pode ser provado em ZF, se ZF é consistente. Dentro ZF, é estritamente mais fraco do que o axioma da escolha. O Teorema do Ultrafiltro tem muitas formulações equivalentes: cada álgebra booleana tem um ultrafiltro, cada ideal em uma álgebra booleana pode ser estendida para um ideal primo, etc.

Representações

Pode ser mostrado que toda álgebra booleana finita é isomorfa à álgebra booleana de todos os subconjuntos de um conjunto finito. Portanto, o número de elementos de cada finito da álgebra booleana é uma potência de dois.

A célebre representação do Teorema para álgebra booleana de Marshal Stone, afirma que cada álgebra booleana A é isomorfo à álgebra booleana de todos os conjuntos clopen definido em algum espaço topológico.

Axiomáticas

A primeira axiomatização de booleanos reticulados/ álgebra booeala em geral foi dada por Alfred North Whitehead em 1898. [4][5] incluiu os axiomas acima e, adicionalmente em x ∨ 1 = 1 e x ∧ 0 = 0. Em 1904, o matemático Edward V. Huntington (1874-1952), criou um axioma com base em ∧, ∨, ¬, mesmo provando as leis associatividade (ver caixa). [6] Ele também provou que estes axiomas são independentes um do outro. [7] Em 1933, Huntington estabeleceu a seguinte axiomatização elegante para a álgebra booleana. Ele requer apenas uma operação binária + e um símbolo funcional unário n, deve ser lido como "complemento", que satisfazem as seguintes leis:

  1. Comutatividade: x + y = y + x.
  2. Associatividade: (x + y) + z = x + (y + z).
  3. Equação de Huntington: n(n(x) + y) + n(n(x) + n(y)) = x.

Herbert Robbins imediatamente perguntou: Se a equação Huntington é substituído por uma dualidade, a saber:

4. Equação de Robbins: n(n(x + y) + n(x + n(y))) = x,

. (1), (2) e (4) formam uma base álgebrica booleana? Chamando (1), (2) e (4) de “Equações de Robbins”, a questão torna-se então: Toda equação de Robbins é uma álgebra booleana? Esta questão (que ficou conhecida como conjectural| conjectura de Robbins) permaneceu aberta durante décadas, e tornou-se uma das perguntas favoritas de Tarski| Alfred Tarski e seus alunos. Em 1996, McCune em National Laboratory com base em trabalhos anteriores de Larry Wos, Steve Winker e Bob Veroff, respondeu à pergunta de Robbins, afirmou: Toda equação de Robbins é uma álgebra booleana. A prova crucial de McCune, foi o reasoning program| programa de raciocínio automatizado en:EQP que ele projetou. Para a simplificação da prova de McCune, consulte Dahn (1998).

Generalizações

Eliminando a necessidade de existência de uma unidade a partir dos axiomas da álgebra booleana que produz "álgebras generalizadas de Boole". Formalmente, uma estrutura distributiva B é um reticulado Booleano generalizado, se ele tem o menor elemento 0 e para todos os elementos a e b em B de tal modo que a ≤ b, existe um elemento x tal que a ∧ x = 0 e a ∨ x = b. Definindo a ∖ b como o único x tal que (a ∧ b) ∨ x = a e (a ∧ b) ∧ x = 0, dizemos que a estrutura (B, ∧, ∨, ∖, 0) é um valor booleano generalizad, enquanto (B, ∨, 0) é um semi-reticulado. Reticulados booleanos generalizados são exatamente os ideais de reticulados booleanos.

Referências

Ver também

Ligações externas

Uma monografia disponível em: