Saltar para o conteúdo

Álgebra de De Morgan

Origem: Wikipédia, a enciclopédia livre.

Na matemática, uma Álgebra de De Morgan (assim chamada em homenagem a Augustus De Morgan, um matemático e lógico britânico) é uma estrutura A = (A, ∨, ∧, 0, 1, ¬)  tal que:

  • (A, ∨, ∧, 0, 1) é um reticulado distributivo limitado, e
  • ¬ é uma involução de De Morgan: ¬(xy) = ¬x ∨ ¬y e ¬¬x = x. (i.e. uma involução que adicionalmente satisfaz as leis de De Morgan).

Em uma álgebra de De Morgan, as leis

nem sempre se verificam. Na presença de leis de De Morgan, uma lei implica na outra, e uma álgebra que as satisfaz é dita álgebra booleana.

Observação: segue-se que ¬(x ∨ y) = ¬x ∧ ¬y, ¬1 = 0 e ¬0 = 1 (por exemplo, ¬1 = ¬1 ∨ 0 = ¬1 ∨ ¬¬0 = ¬(1 ∧ ¬0) = ¬¬0 = 0). É, portanto, um duplo automorfismo.

Se ao invés disso o reticulado é definido em termos da ordem, i.e. (A, ≤) é uma ordem parcial limitada com um menor limitante superior (supremo) e maior limitante inferior (ínfimo) para cada par de elementos, e as operações ∧ e ∨ satisfazem a lei distributiva, então a complementação pode também ser definida como um anti-automorfismo involutivo, isto é, uma estrutura A = (A, ≤,  ¬) tal que:

  • (A, ≤) é um reticulado distributivo limitado, e
  • ¬¬x = x, e
  • xy → ¬y ≤ ¬x.

Álgebras de De Morgan foram introduzidas por Grigore Moisil em cerca de 1935, embora sem a restrição de ter um 0 e um 1. Por isso, elas foram frequentemente chamadas de quase-álgebras booleanas na escola polaca, e.g. por Rasiowa e também i-reticulados distributivos por J. A. Kalman. (i-reticulado sendo uma abreviação para reticulado com involução.) Elas foram estudadas posteriormente na escola lógica algébrica argentina de Antonio Monteiro.

Álgebras de De Morgan são importantes para o estudo dos aspectos matemáticos da lógica difusa. A álgebra difusa canônica F = ([0, 1], max(x, y), min(x, y), 0, 1, 1 − x) é um exemplo de álgebra de De Morgan, onde a lei do terceiro excluído e o princípio da não contradição não valem.

Outro exemplo é a lógica 4-valorada de Dunn, na qual falso < nem verdadeiro, nem falso < verdadeiro e falso < ambos-verdadeiro-e-falso < verdadeiro, embora nem verdadeiro, nem falso e tanto-verdadeiro-quanto-falso não são comparáveis.

Álgebra de Kleene

[editar | editar código-fonte]

Se uma álgebra de De Morgan adicionalmente satisfaz ∧ ¬x ≤ y ∨ ¬y, é dita álgebra de Kleene. (Esse conceito não deve ser confundido com outra álgebra de Kleene generalizando expressões regulares.) Essa ideia também é chamada de i-reticulado normal por Kalman.

Exemplos de álgebras de Kleene no sentido definido acima incluem: grupos ordenados de reticulados, Pós-álgebras e álgebras de Lukasiewicz.Ágebras booleanas também atendem a essa definição da álgebra de Kleene. A mais simples álgebra de Kleene que não é Booleana é a lógica de três valores de Kleene K3. K3 , fez sua primeira aparição no livro On notation for ordinal numbers (1938) de Kleene.[1] A álgebra foi chamada de álgebra de Kleene por Brignole e Monteiro.[2]

Noções relacionadas

[editar | editar código-fonte]

A álgebra de De Morgan não é o único meio plausível de generalizar a álgebra booleana. Outro método é preservando ¬x ∧ x = 0 (i.e. o princípio da não contradição) mas ignorando a lei do terceiro excluído e a lei da dupla negação. Essa abordagem (chamada de semicomplementação) é bem definida mesmo para um [ ∧ ] semirreticulado; se o conjunto de semicomplementos tem um maior elemento, é geralmente chamado de pseudocomplemento. Se o pseudocomplemento nessas condições satisfaz a lei do terceiro excluído, então a álgebra resultante também é Booleana. Contudo, se apenas a lei  ¬x ∨ ¬¬x = 1 é satisfeita, isso resulta em uma álgebra de Stone. Geralmente, ambas álgebras de De Morgan e Stone são subclasses próprias de álgebras de Ockham.

Referências

  1. Kleene, S. C. (23 de julho de 2017). «On Notation for Ordinal Numbers». The Journal of Symbolic Logic. 3 (4): 150–155. doi:10.2307/2267778 – via JSTOR 
  2. Brignole, D. and Monteiro, A. Caracterisation des algebres de Nelson par des egalites, Notas de Logica Matematica, Instituto de Matematica Universidad del sur Bahia Blanca 20 (1964) A (possibly abbreviated) version of this paper appeared later in Proc.