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:
- 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 | | | | |
- 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
Prova das propriedades |
UId1 | | If x ∨ o = x for all x, then o = 0 | Prova: | | Se x ∨ o = x, então | | | 0 | | = | 0 ∨ o | usando assumption | | = | o ∨ 0 | usando Cmm1 | | = | o | usando Idn1 | | UId2 [dual] If x ∧ i = x for all x, then i = 1 |
Idm1 | | x ∨ x = x | Prova: | | x ∨ x | | = | (x ∨ x) ∧ 1 | usando Idn2 | | = | (x ∨ x) ∧ (x ∨ ¬x) | usando Cpl1 | | = | x ∨ (x ∧ ¬x) | usando Dst1 | | = | x ∨ 0 | usando Cpl2 | | = | x | usando Idn1 | | Idm2 [dual] x ∧ x = x |
Bnd1 | | x ∨ 1 = 1 | Prova: | | x ∨ 1 | | = | (x ∨ 1) ∧ 1 | usando Idn2 | | = | 1 ∧ (x ∨ 1) | usando Cmm2 | | = | (x ∨ ¬x) ∧ (x ∨ 1) | usado Cpl1 | | = | x ∨ (¬x ∧ 1) | usando Dst1 | | = | x ∨ ¬x | usando Idn2 | | = | 1 | usando Cpl1 | | Bnd2 [dual] x ∧ 0 = 0 |
Abs1 | | x ∨ (x ∧ y) = x | Prova: | | x ∨ (x ∧ y) | | = | (x ∧ 1) ∨ (x ∧ y) | usando Idn2 | | = | x ∧ (1 ∨ y) | usando Dst2 | | = | x ∧ (y ∨ 1) | usando Cmm1 | | = | x ∧ 1 | usando Bnd1 | | = | x | usando Idn2 | | Abs2 [dual] x ∧ (x ∨ y) = x |
UNg | | se x ∨ xn = 1 e x ∧ xn = 0, então xn = ¬x | Prova: | | Se x ∨ xn = 1 e x ∧ xn = 0, então | | | xn | | = | xn ∧ 1 | usando Idn2 | | = | 1 ∧ xn | usando Cmm2 | | = | (x ∨ ¬x) ∧ xn | usando Cpl1 | | = | xn ∧ (x ∨ ¬x) | usando Cmm2 | | = | (xn ∧ x) ∨ (xn ∧ ¬x) | usando Dst2 | | = | (x ∧ xn) ∨ (¬x ∧ xn) | usando Cmm2 | | = | 0 ∨ (¬x ∧ xn) | usando assumption | | = | (x ∧ ¬x) ∨ (¬x ∧ xn) | usando Cpl2 | | = | (¬x ∧ x) ∨ (¬x ∧ xn) | usando Cmm2 | | = | ¬x ∧ (x ∨ xn) | usando Dst2 | | = | ¬x ∧ 1 | usando assumption | | = | ¬x | usando Idn2 | |
DNg | | ¬¬x = x | Prova: | | ¬x ∨ x = x ∨ ¬x = 1 | usando Cmm1, Cpl1 | | e | ¬x ∧ x = x ∧ ¬x = 0 | usando Cmm2, Cpl2 | | por isso | x = ¬¬x | usando UNg | |
A1 | | x ∨ (¬x ∨ y) = 1 | Prova: | | x ∨ (¬x ∨ y) | | = | (x ∨ (¬x ∨ y)) ∧ 1 | usando Idn2 | | = | 1 ∧ (x ∨ (¬x ∨ y)) | usando Cmm2 | | = | (x ∨ ¬x) ∧ (x ∨ (¬x ∨ y)) | usando Cpl1 | | = | x ∨ (¬x ∧ (¬x ∨ y)) | usando Dst1 | | = | x ∨ ¬x | usando XIb | | = | 1 | usando Cpl1 | | A2 [dual] x ∧ (¬x ∧ y) = 0 |
B1 | | (x ∨ y) ∨ (¬x ∧ ¬y) = 1 | Prova: | | (x ∨ y) ∨ (¬x ∧ ¬y) | | = | ((x ∨ y) ∨ ¬x) ∧ ((x ∨ y) ∨ ¬y) | usando Dst1 | | = | (¬x ∨ (x ∨ y)) ∧ (¬y ∨ (y ∨ x)) | usando Cmm1 | | = | (¬x ∨ (¬¬x ∨ y)) ∧ (¬y ∨ (¬¬y ∨ x)) | usando DNg | | = | 1 ∧ 1 | usando A1 | | = | 1 | usando Idn2 | | B1 [dual] (x ∧ y) ∧ (¬x ∨ ¬y) = 0 |
C1 | | (x ∨ y) ∧ (¬x ∧ ¬y) = 0 | Prova: | | (x ∨ y) ∧ (¬x ∧ ¬y) | | = | (¬x ∧ ¬y) ∧ (x ∨ y) | usando Cmm2 | | = | ((¬x ∧ ¬y) ∧ x) ∨ ((¬x ∧ ¬y) ∧ y) | usando Dst2 | | = | (x ∧ (¬x ∧ ¬y)) ∨ (y ∧ (¬y ∧ ¬x)) | usando Cmm2 | | = | 0 ∨ 0 | usando A2 | | = | 0 | usando Idn1 | | C2 [dual] (x ∧ y) ∨ (¬x ∨ ¬y) = 1 |
DMg1 | | ¬(x ∨ y) = ¬x ∧ ¬y | Prova: | | usando B1, C1, and UNg | | DMg2 [dual] ¬(x ∧ y) = ¬x ∨ ¬y |
D1 | | (x∨(y∨z)) ∨ ¬x = 1 | Prova: | | (x ∨ (y ∨ z)) ∨ ¬x | | = | ¬x ∨ (x ∨ (y ∨ z)) | usando Cmm1 | | = | ¬x ∨ (¬¬x ∨ (y ∨ z)) | usando DNg | | = | 1 | usando A1 | | D2 [dual] (x∧(y∧z)) ∧ ¬x = 0 |
E1 | | y ∧ (x∨(y∨z)) = y | Prova: | | y ∧ (x ∨ (y ∨ z)) | | = | (y ∧ x) ∨ (y ∧ (y ∨ z)) | usando Dst2 | | = | (y ∧ x) ∨ y | usando Abs2 | | = | y ∨ (y ∧ x) | usando Cmm1 | | = | y | usando Abs1 | | E2 [dual] y ∨ (x∧(y∧z)) = y |
F1 | | (x∨(y∨z)) ∨ ¬y = 1 | Prova: | | (x ∨ (y ∨ z)) ∨ ¬y | | = | ¬y ∨ (x ∨ (y ∨ z)) | usando Cmm1 | | = | (¬y ∨ (x ∨ (y ∨ z))) ∧ 1 | usando Idn2 | | = | 1 ∧ (¬y ∨ (x ∨ (y ∨ z))) | usando Cmm2 | | = | (y ∨ ¬y) ∧ (¬y ∨ (x ∨ (y ∨ z))) | usando Cpl1 | | = | (¬y ∨ y) ∧ (¬y ∨ (x ∨ (y ∨ z))) | usando Cmm1 | | = | ¬y ∨ (y ∧ (x ∨ (y ∨ z))) | usando Dst1 | | = | ¬y ∨ y | usando E1 | | = | y ∨ ¬y | usando Cmm1 | | = | 1 | usando Cpl1 | | F2 [dual] (x∧(y∧z)) ∧ ¬y = 0 |
G1 | | (x∨(y∨z)) ∨ ¬z = 1 | Prova: | | (x ∨ (y ∨ z)) ∨ ¬z | | = | (x ∨ (z ∨ y)) ∨ ¬z | usando Cmm1 | | = | 1 | usando F1 | | G2 [dual] (x∧(y∧z)) ∧ ¬z = 0 |
H1 | | ¬((x∨y)∨z) ∧ x = 0 | Prova: | | ¬((x ∨ y) ∨ z) ∧ x | | = | (¬(x ∨ y) ∧ ¬z) ∧ x | usando DMg1 | | = | ((¬x ∧ ¬y) ∧ ¬z) ∧ x | usando DMg1 | | = | x ∧ ((¬x ∧ ¬y) ∧ ¬z) | usando Cmm2 | | = | (x ∧ ((¬x ∧ ¬y) ∧ ¬z)) ∨ 0 | usando Idn1 | | = | 0 ∨ (x ∧ ((¬x ∧ ¬y) ∧ ¬z)) | usando Cmm1 | | = | (x ∧ ¬x) ∨ (x ∧ ((¬x ∧ ¬y) ∧ ¬z)) | usando Cpl1 | | = | x ∧ (¬x ∨ ((¬x ∧ ¬y) ∧ ¬z)) | usando Dst2 | | = | x ∧ (¬x ∨ (¬z ∧ (¬x ∧ ¬y))) | usando Cmm2 | | = | x ∧ ¬x | usando E2 | | = | 0 | usando Cpl2 | | H2 [dual] ¬((x∧y)∧z) ∨ x = 1 |
I1 | | ¬((x∨y)∨z) ∧ y = 0 | Prova: | | ¬((x ∨ y) ∨ z) ∧ y | | = | ¬((y ∨ x) ∨ z) ∧ y | usando Cmm1 | | = | 0 | usando H1 | | I2 [dual] ¬((x∧y)∧z) ∨ y = 1 |
J1 | | ¬((x∨y)∨z) ∧ z = 0 | Prova: | | ¬((x ∨ y) ∨ z) ∧ z | | = | (¬(x ∨ y) ∧ ¬z) ∧ z | usando DMg1 | | = | z ∧ (¬(x ∨ y) ∧ ¬z) | usando Cmm2 | | = | z ∧ (¬z ∧ ¬(x ∨ y)) | usando Cmm2 | | = | 0 | usando A2 | | J2 [dual] ¬((x∧y)∧z) ∨ z = 1 |
K1 | | (x ∨ (y ∨ z)) ∨ ¬((x ∨ y) ∨ z) = 1 | Prova: | | (x∨(y∨z)) ∨ ¬((x ∨ y) ∨ z) | | = | (x∨(y∨z)) ∨ (¬(x ∨ y) ∧ ¬z) | usando DMg1 | | = | (x∨(y∨z)) ∨ ((¬x ∧ ¬y) ∧ ¬z) | usando DMg1 | | = | ((x∨(y∨z)) ∨ (¬x ∧ ¬y)) ∧ ((x∨(y∨z)) ∨ ¬z) | usando Dst1 | | = | (((x∨(y∨z)) ∨ ¬x) ∧ ((x∨(y∨z)) ∨ ¬y)) ∧ ((x∨(y∨z)) ∨ ¬z) | usando Dst1 | | = | (1 ∧ 1) ∧ 1 | usando D1,F1,G1 | | = | 1 | usando Idn2 | | K2 [dual] (x ∧ (y ∧ z)) ∧ ¬((x ∧ y) ∧ z) = 0 |
L1 | | (x ∨ (y ∨ z)) ∧ ¬((x ∨ y) ∨ z) = 0 | Prova: | | (x ∨ (y ∨ z)) ∧ ¬((x ∨ y) ∨ z) | | = | ¬((x∨y)∨z) ∧ (x ∨ (y ∨ z)) | usando Cmm2 | | = | (¬((x∨y)∨z) ∧ x) ∨ (¬((x∨y)∨z) ∧ (y ∨ z)) | usando Dst2 | | = | (¬((x∨y)∨z) ∧ x) ∨ ((¬((x∨y)∨z) ∧ y) ∨ (¬((x∨y)∨z) ∧ z)) | usando Dst2 | | = | (0 ∨ 0) ∨ 0 | usando H1,I1,J1 | | = | 0 | usando Idn1 | | L2 [dual] (x ∧ (y ∧ z)) ∨ ¬((x ∧ y) ∧ z) = 1 |
Ass1 | | x ∨ (y ∨ z) = (x ∨ y) ∨ z | Prova: | | by K1, L1, UNg, DNg | | Ass2 [dual] x ∧ (y ∧ z) = (x ∧ y) ∧ z |
Abreviações | UId | Identidade única | Idm | Idepotencia | Bnd | Reticulados delimitados | Abs | Lei da absorção | UNg | Negação única | DNg | Negação dupla | DMg | Lei de De Morgan | Ass | Associatividade | |
Axiomas álgebricos booleanos de Huntington 1904 |
Idn1 | x ∨ 0 = x | Idn2 | x ∧ 1 = x |
Cmm1 | x ∨ y = y ∨ x | Cmm2 | x ∧ y = y ∧ x |
Dst1 | x ∨ (y∧z) = (x∨y) ∧ (x∨z) | Dst2 | x ∧ (y∨z) = (x∧y) ∨ (x∧z) |
Cpl1 | x ∨ ¬x = 1 | Cpl2 | x ∧ ¬x = 0 |
Abreviações | Idn | Identidade | Cmm | Comutatividade | Dst | Distributividade | Cpl | Complementar | |
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:
- Comutatividade: x + y = y + x.
- Associatividade: (x + y) + z = x + (y + z).
- 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
- Brown, Stephen; Vranesic, Zvonko (2002), Fundamentals of Digital Logic with VHDL Design, ISBN 978-0-07-249938-4 2nd ed. , McGraw–Hill . See Section 2.5.
- A. Boudet, J.P. Jouannaud, M. Schmidt-Schauß (1989). «Unification of Boolean Rings and Abelian Groups» (PDF). Journal of Symbolic Computation. 8: 449-477 !CS1 manut: Nomes múltiplos: lista de autores (link)
- Cori, Rene; Lascar, Daniel (2000), Mathematical Logic: A Course with Exercises, ISBN 978-0-19-850048-3, Oxford University Press . See Chapter 2.
- Dahn, B. I. (1998), «Robbins Algebras are Boolean: A Revision of McCune's Computer-Generated Solution of the Robbins Problem», Journal of Algebra, 208 (2): 526–532, doi:10.1006/jabr.1998.7467 .
- B.A. Davey, H.A. Priestley (1990). Introduction to Lattices and Order. Col: Cambridge Mathematical Textbooks. [S.l.]: Cambridge University Press
- Givant, Steven; Halmos, Paul (2009), Introduction to Boolean Algebras, ISBN 978-0-387-40293-2, Undergraduate Texts in Mathematics, Springer .
- Halmos, Paul (1963), Lectures on Boolean Algebras, ISBN 978-0-387-90094-0, Van Nostrand .
- Halmos, Paul; Givant, Steven (1998), Logic as Algebra, ISBN 978-0-88385-327-6, Dolciani Mathematical Expositions, 21, Mathematical Association of America .
- Hsiang, Jieh (1985). «Refutational Theorem Proving Using Term Rewriting Systems» (PDF). AI. 25: 255-300
- Edward V. Huntington (1904). «Sets of Independent Postulates for the Algebra of Logic» (PDF). These Transactions. 5: 288-309
- Huntington, E. V. (1933), «New sets of independent postulates for the algebra of logic» (PDF), American Mathematical Society, Transactions of the American Mathematical Society, 35 (1): 274–304, JSTOR 1989325, doi:10.2307/1989325 .
- Huntington, E. V. (1933), «Boolean algebra: A correction», American Mathematical Society, Transactions of the American Mathematical Society, 35 (2): 557–558, JSTOR 1989783, doi:10.2307/1989783 .
- Mendelson, Elliott (1970), Boolean Algebra and Switching Circuits, ISBN 978-0-07-041460-0, Schaum's Outline Series in Mathematics, McGraw–Hill .
- Monk, J. Donald; Bonnet, R., eds. (1989), Handbook of Boolean Algebras, ISBN 978-0-444-87291-3, North-Holland . In 3 volumes. (Vol.1:ISBN 978-0-444-70261-6, Vol.2:ISBN 978-0-444-87152-7, Vol.3:ISBN 978-0-444-87153-4)
- Padmanabhan, Ranganathan; Rudeanu, Sergiu (2008), Axioms for lattices and boolean algebras, ISBN 978-981-283-454-6, World Scientific .
- Sikorski, Roman (1966), Boolean Algebras, Ergebnisse der Mathematik und ihrer Grenzgebiete, Springer Verlag .
- Stoll, R. R. (1963), Set Theory and Logic, ISBN 978-0-486-63829-4, W. H. Freeman . Reprinted by Dover Publications, 1979.
- Marshall H. Stone (1936). «The Theory of Representations for Boolean Algebra». Trans. AMS. 40: 37-111
- A.N. Whitehead (1898). A Treatise on Universal Algebra. [S.l.]: Cambridge University Press. ISBN 1-4297-0032-7
Ver também
Ligações externas
- Hazewinkel, Michiel, ed. (2001), «Boolean algebra», Enciclopédia de Matemática, ISBN 978-1-55608-010-4 (em inglês), Springer
- Boolean Algebrade AllAboutCircuits
- Stanford Encyclopedia of Philosophy: "The Mathematics of Boolean Algebra," by J. Donald Monk.
- McCune W., 1997. Robbins Algebras Are Boolean JAR 19(3), 263—276
- "Boolean Algebra"by Eric W. Weisstein, Wolfram Demonstrations Project, 2007.
Uma monografia disponível em:
- Burris, Stanley N.; Sankappanavar, H. P., 1981. A Course in Universal Algebra. Springer-Verlag. ISBN 3-540-90578-2.
- Weisstein, Eric W. «Boolean Algebra». MathWorld (em inglês)