A Matemática Da Álgebra Booleana

Índice:

A Matemática Da Álgebra Booleana
A Matemática Da Álgebra Booleana

Vídeo: A Matemática Da Álgebra Booleana

Vídeo: A Matemática Da Álgebra Booleana
Vídeo: 56 - Álgebra Booleana (programação para iniciantes) 2024, Março
Anonim

Este é um arquivo nos arquivos da Enciclopédia Stanford of Philosophy.

A Matemática da Álgebra Booleana

Publicado pela primeira vez em 5 de julho de 2002; revisão substantiva sexta-feira 27 de fevereiro de 2009

Álgebra booleana é a álgebra da lógica de dois valores, com apenas conectivos sentenciais, ou equivalentemente, álgebras de conjuntos sob união e complementação. O conceito rigoroso é o de um certo tipo de álgebra, análogo à noção matemática de um grupo. Este conceito tem raízes e aplicações em lógica (álgebras de Lindenbaum-Tarski e teoria dos modelos), teoria dos conjuntos (campos dos conjuntos), topologia (espaços Hausdorff compactos totalmente desconectados), fundamentos da teoria dos conjuntos (modelos com valor booleano), teoria da medida (medida álgebras), análise funcional (álgebras de projeções) e teoria dos anéis (anéis booleanos). O estudo de álgebras booleanas tem vários aspectos: teoria da estrutura, teoria dos modelos de álgebras booleanas, questões de decidibilidade e indecidibilidade para a classe de álgebras booleanas e as aplicações indicadas. Além do que, além do mais,embora não explicado aqui, existem conexões com outras lógicas, subsunção como parte de tipos especiais de lógica algébrica, álgebras booleanas finitas e teoria de circuitos de comutação e matrizes booleanas.

  • 1. Definição e propriedades simples
  • 2. A teoria algébrica elementar
  • 3. Classes especiais de álgebras booleanas
  • 4. Teoria da estrutura e funções cardinais em álgebras booleanas
  • 5. Questões de decidibilidade e indecidibilidade
  • 6. Álgebras de Lindenbaum-Tarski
  • 7. Modelos com valor booleano
  • Bibliografia
  • Outros recursos da Internet
  • Entradas Relacionadas

1. Definição e propriedades simples

Uma álgebra booleana (BA) é um conjunto A, juntamente com operações binárias + e · e uma operação unária - e os elementos 0, 1 de A, de modo que as seguintes leis são válidas: leis comutativas e associativas para adição e multiplicação, leis distributivas tanto para multiplicação sobre adição e para adição sobre multiplicação, e as seguintes leis especiais:

x + (x · y) = x

x · (x + y) = x

x + (−x) = 1

x · (−x) = 0

Essas leis são melhor compreendidas em termos do exemplo básico de um BA, consistindo em uma coleção A de subconjuntos de um conjunto X fechado sob as operações de união, interseção, complementação em relação a X, com membros ∅ e X. Pode-se facilmente derivar muitas leis elementares desses axiomas, tendo em mente este exemplo de motivação. Qualquer BA tem uma ordem parcial natural ≤ definida, dizendo que x ≤ y se e somente se x + y = y. Isso corresponde em nosso exemplo principal a ⊆. De importância especial é o BA de dois elementos, formado pelo fato de o conjunto X ter apenas um elemento. O BA de dois elementos mostra a conexão direta com a lógica elementar. Os dois membros, 0 e 1, correspondem à falsidade e verdade, respectivamente. As operações booleanas expressam as tabelas verdadeiras comuns para disjunção (com +), conjunção (com ·) e negação (com -). Um resultado elementar importante é que uma equação é válida em todos os BAs se e somente se for válida nos dois elementos BA. Em seguida, definimos x ⊕ y = (x · - y) + (y · - x). Então A junto com ⊕ e ·, junto com 0 e 1, forma um anel com identidade na qual todo elemento é idempotente. Inversamente, dado esse anel, com adição ⊕ e multiplicação, defina x + y = x ⊕ y ⊕ (x · y) e - x = 1 x. Isso transforma o anel em um BA. Esses dois processos são inversos um do outro e mostram que a teoria das álgebras booleanas e dos anéis com identidade em que todo elemento é idempotente é definicionalmente equivalente. Isso coloca a teoria dos BAs em um objeto padrão de pesquisa em álgebra. Um átomo em um BA é um elemento diferente de zero a tal que não há elemento b com 0 <b <a. Um BA é atômico se cada elemento diferente de zero do BA estiver acima de um átomo. BAs finitos são atômicos, mas também muitos BAs infinitos. Sob a ordem parcial ≤ acima, x + y é o menor limite superior de xey, e x · y é o maior limite inferior de x e y. Podemos generalizar isso: Σ X é o menor limite superior de um conjunto X de elementos e Π X é o maior limite inferior de um conjunto X de elementos. Eles não existem para todos os conjuntos em todas as álgebras booleanas; se eles sempre existirem, a álgebra booleana é considerada completa.a álgebra booleana é considerada completa.a álgebra booleana é considerada completa.

2. A teoria algébrica elementar

Várias construções algébricas têm definições óbvias e propriedades simples para BAs: subalgebras, homomorfismos, isomorfismos e produtos diretos (mesmo de infinitas álgebras). Algumas outras construções algébricas padrão são mais peculiares às BAs. Um ideal em um BA é um subconjunto que fechei em +, com 0 como membro, e tal que se a ≤ b ∈ I, também a ∈ I. Embora não seja imediatamente óbvio, é o mesmo que o conceito da teoria dos anéis. Existe uma noção dupla de filtro (sem contrapartida nos anéis em geral). Um filtro é um subconjunto F fechado em ·, tendo 1 como membro, e de modo que se a ≥ b ∈ F, então também a ∈ F. Um ultrafiltro em A é um filtro F com as seguintes propriedades: 0 ∉ F e para qualquer a ∈ A, seja ∈ F ou - a ∈ F. Para qualquer a ∈ A, seja S (a) = {F: F é um ultrafiltro em A e ∈ F}. Então S é um isomorfismo em um BA de subconjuntos do conjunto X de todos os ultrafiltros em A. Isso estabelece o teorema básico da representação de Stone e esclarece a origem dos BAs como álgebras concretas de conjuntos. Além disso, os conjuntos S (a) podem ser declarados como base para uma topologia em X, e isso transforma X em um espaço Hausdorff compacto totalmente desconectado. Isso estabelece uma correspondência individual entre a classe de BAs e a classe de tais espaços. Como conseqüência, muito usado na teoria dos BAs, muitos teoremas e conceitos topológicos têm conseqüências para os BAs. Se x é um elemento de um BA, deixamos 0 x = - x e 1 x = x. Se (x (0),… x (m - 1)) é uma sequência finita de elementos de um BA A, então todo elemento da subalgebra de A gerado por {x (0),…,x (m - 1)} pode ser escrito como uma soma dos monômios e (0) x (0) ·… · e (m - 1) x (m - 1) para e em algum conjunto de funções mapeado m = {0,…, M - 1} em 2 = {0, 1}. Esta é uma expressão algébrica do teorema da forma normal disjuntiva da lógica sentencial. Uma função f de um conjunto X de geradores de um BA A para um BA B pode ser estendida a um homomorfismo se e somente se e (0) x (0) ·… · e (m - 1) x (m - 1) = 0 sempre implica que e (0) f (x (0)) ·… · e (m - 1) f (x (m - 1)) = 0. Esse é o critério de extensão de Sikorski. Todo BA A pode ser incorporado em um BA B completo de tal maneira que todo elemento de B seja o limite superior menos de um conjunto de elementos de A. B é único até o isomorfismo A e é chamado de conclusão de A. Se f é um homomorfismo de um BA A em um BA B completo, e se A é uma subalgebra de C,então f pode ser estendido a um homomorfismo de C em B. Este é o teorema da extensão de Sikorski. Outra noção algébrica geral que se aplica às álgebras booleanas é a noção de álgebra livre. Isso pode ser construído concretamente para os BAs. Ou seja, o BA livre em κ é o BA de subconjuntos fechados-abertos do espaço discreto de dois elementos elevado à potência κ.

3. Classes especiais de álgebras booleanas

Existem muitas classes especiais de álgebra booleana que são importantes tanto para a teoria intrínseca dos BAs quanto para aplicações:

  • BAs atômicos, já mencionados acima.
  • BAs sem atom, que são definidos como BAs sem átomos. Por exemplo, qualquer BA livre infinito não tem átomos.
  • BAs completos, definidos acima. Estes são especialmente importantes nos fundamentos da teoria dos conjuntos.
  • Álgebras de intervalo. Estes são derivados de conjuntos ordenados linearmente (L, <) com um primeiro elemento da seguinte maneira. Um toma a menor álgebra de subconjuntos de L contendo todos os intervalos semi-abertos [a, b) com a em L e b em L ou igual a ∞. Esses BAs são úteis no estudo das álgebras de Lindenbaum-Tarski. Todo BA contável é isomórfico para uma álgebra de intervalo e, portanto, um BA contável pode ser descrito indicando um conjunto ordenado de modo que seja isomórfico para a álgebra de intervalo correspondente.
  • Álgebras de árvores. Uma árvore é um conjunto parcialmente ordenado (T, <), no qual o conjunto de predecessores de qualquer elemento é bem ordenado. Dada essa árvore, considera-se a álgebra de subconjuntos de T gerados por todos os conjuntos da forma {b: a ≤ b} para alguns a em T.
  • BAs Superatômicos. Estes são BAs que não são apenas atômicos, mas são tais que cada imagem subalgebra e homomórfica é atômica.

4. Teoria da estrutura e funções cardinais em álgebras booleanas

Grande parte da teoria mais profunda das álgebras booleanas, que fala sobre sua estrutura e classificação, pode ser formulada em termos de certas funções definidas para todas as álgebras booleanas, com infinitos cardeais como valores. Definimos algumas das funções cardinais mais importantes e declaramos alguns dos fatos estruturais conhecidos, formulados principalmente em termos deles.

  1. A celularidade c (A) de um BA é o supremo das cardinalidades de conjuntos de elementos disjuntos em pares de A.
  2. Um subconjunto X de um BA A é independente se X for um conjunto de geradores livres da subalgebra que ele gera. A independência de A é o supremo de cardinalidades de subconjuntos independentes de A.
  3. Um subconjunto X de um BA A é denso em A se todo elemento diferente de zero de A for ≥ um elemento diferente de zero de X. O peso π de A é a menor cardinalidade de um subconjunto denso de A.
  4. Dois elementos x, y de A são incomparáveis se nenhum deles for ≤ o outro. O supremo de cardinalidades do subconjunto X de A consistindo em elementos incomparáveis em pares é a incomparabilidade de A.
  5. Um subconjunto X de A é irredundante se nenhum elemento de X estiver na subalgebra gerada pelos outros.

Um fato importante a respeito da celularidade é o teorema de Erdos-Tarski: se a celularidade de um BA é um cardeal singular, então há realmente um conjunto de elementos disjuntos desse tamanho; para limite regular de celularidade (inacessível), existem contra-exemplos. Todo BA completo infinito possui um subconjunto independente do mesmo tamanho da álgebra. Todo BA A infinito tem um subconjunto incomparável irredundante, cujo tamanho é o peso π de A. Cada álgebra de intervalo tem independência contável. Uma álgebra superatômica nem sequer possui um subconjunto independente infinito. Cada álgebra de árvore pode ser incorporada em uma álgebra de intervalo. Um BA com apenas o automorfismo de identidade é chamado de rígido. Existem BAs completas rígidas, também álgebras de intervalo rígidas e álgebras de árvores rígidas.

5. Questões de decidibilidade e indecidibilidade

Um resultado básico de Tarski é que a teoria elementar das álgebras booleanas é decidível. Mesmo a teoria das álgebras booleanas com um ideal distinto é decidível. Por outro lado, a teoria de uma álgebra booleana com uma subalgebra distinta é indecidível. Os resultados da decidibilidade e da indecisão se estendem de várias maneiras às álgebras booleanas em extensões da lógica de primeira ordem.

6. Álgebras de Lindenbaum-Tarski

Uma construção muito importante, que transporta muitas lógicas e muitas álgebras além das álgebras booleanas, é a construção de uma álgebra booleana associada às sentenças de alguma lógica. O caso mais simples é a lógica sentencial. Aqui há símbolos de frases e conectivos comuns construindo frases mais longas a partir deles: disjunção, conjunção e negação. Dado um conjunto A de sentenças nesse idioma, duas sentenças s são equivalentes ao módulo A se e somente se o bicondicional entre elas for uma conseqüência lógica de A. As classes de equivalência podem ser transformadas em um BA tal que + corresponde à disjunção, · à conjunção e - à negação. Qualquer BA é isomórfica para uma desta forma. Pode-se fazer algo semelhante para uma teoria de primeira ordem. Seja T uma teoria de primeira ordem em uma linguagem de primeira ordem L. Chamamos fórmulas φ e ψ equivalentes, desde que T ⊢ φ ↔ ψ. A classe de equivalência de uma sentença φ é denotada por [φ]. Seja A a coleção de todas as classes de equivalência sob essa relação de equivalência. Podemos transformar A em BA pelas seguintes definições, que são facilmente justificáveis:

[φ] + [ψ] = [φ ∨ ψ]
[φ] · [ψ] = [φ ∧ ψ]
- [φ] = [¬φ]
0 0 = [F]
1 = [T]

Todo BA é isomórfico para uma álgebra de Lindenbaum-Tarski. No entanto, um dos usos mais importantes dessas álgebras clássicas de Lindenbaum-Tarski é descrevê-las para teorias importantes (geralmente teorias decidíveis). Para idiomas contáveis, isso pode ser feito descrevendo suas álgebras com intervalo isomórfico. Geralmente, isso fornece um conhecimento completo da teoria. Alguns exemplos são:

Teoria Álgebra isomórfica para intervalo em
(1) teoria essencialmente indecidível Q, os racionais
2) BAs
Natural
Natural

×

Naturals
Naturals

quadrado dos números inteiros positivos, ordenados lexicograficamente

(3) ordens lineares

A × Q ordenou antilexicograficamente, onde A está

Naturals
Naturals

à

Naturals
Naturals

potência em sua ordem usual

4) grupos abelianos (Q + A) × Q

7. Modelos com valor booleano

Na teoria dos modelos, pode-se tomar valores em qualquer BA completa, em vez da BA de dois elementos. Essa teoria de modelo com valor booleano foi desenvolvida entre 1950 e 1970, mas não tem sido trabalhada muito desde então. Mas um caso especial, modelos com valor booleano para teoria dos conjuntos, está muito na vanguarda da pesquisa atual em teoria dos conjuntos. Na verdade, forma uma maneira equivalente de olhar para a construção forçada de Cohen e possui algumas vantagens e desvantagens técnicas. Filosoficamente, parece mais satisfatório do que o conceito de forçar. Nós descrevemos este caso da teoria dos conjuntos aqui; ficará evidente por que apenas os BAs de competição são considerados. Seja B um BA completo. Primeiro, definimos o universo com valor booleano V (B). O universo ordinário da teoria dos conjuntos pode ser identificado com V (2), em que 2 é o 2-elemento BA. A definição é por recursão transfinita, onde α,β são ordinais e λ é um ordinal limite:

V (B, 0) =
V (B, α + 1) = o conjunto de todas as funções f, de modo que o domínio de f seja um subconjunto de V (B, α) e o intervalo de f seja um subconjunto de B
V (B, λ) = a união de todos os V (B, β) para β <λ.

O universo avaliado por B é a classe V adequada (B), que é a união de todos esses Vs. Em seguida, define-se por uma recursão transfinita bastante complicada sobre conjuntos bem fundamentados o valor de uma fórmula teórica de conjuntos com elementos do universo de valor booleano atribuído a suas variáveis livres

|| x ∈ y || = Σ {(|| x = t || · y (t)): t ∈ domínio (y)}
|| x ⊆ y || = Π {- x (t) + || t y ||: t ∈ domínio (x)}
|| x = y || = || x ⊆ y || · || y ⊆ x ||
|| ¬φ || = - || φ ||
|| ψ ∨ ψ || = || φ || + || ψ ||
|| ∃ x φ (x) || = Σ {|| φ (a) ||: a ∈ V (B)}

Bibliografia

  • Halmos, P., 1963, Palestras sobre Álgebras Booleanas, Princeton: Van Nostrand
  • Heindorf, L. e Shapiro, L., 1994, Álgebras booleanas quase projetivas, Lecture Notes in Mathematics no. 1596, Berlim: Springer-Verlag
  • Jech, T., 1997, Teoria dos Conjuntos, 2ª edição corrigida, Berlim, Nova York: Springer-Verlag
  • Monk, JD e Bonnet, R., (eds), 1989, Handbook of Boolean álgebras, 3 volumes, Amsterdã: Holanda do Norte.

Outros recursos da Internet

[Entre em contato com o autor com sugestões.]

Recomendado: