Álgebra de De Morgan: diferenças entre revisões
Criado ao traduzir a página "De Morgan algebra" |
(Sem diferenças)
|
Revisão das 20h12min de 28 de novembro de 2016
Na matemática, uma Álgebra de De Morgan (nomeado após Augustus De Morgan, um matemático e lógico britânico) é uma estrutura A = (A, ∨, ∧, 0, 1, ¬) tal que:
- (A, ∨, ∧, 0, 1) é um reticulado limitado distributivo, e
- ¬ é uma involução de De Morgan: ¬(x ∧ y) = ¬x ∨ ¬y e ¬¬x = x. (i.e. uma involução que adicionalmente satisfaz leis de De Morgan).
Em uma álgebra de De Morgan, as leis
- ¬x ∨ x = 1 (lei do terceiro excluído), e
- ¬x ∧ x = 0 (princípio da não contradição)
não se sustentam sempre. Na presença de leis de De Morgan, uma lei implica na outra, e uma álgebra que satisfá-las é 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, ≤) é um delimitada ordem parcial com um menor limite superior (supremo) e maior limite 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 definido como um anti-automorfismo involutivo, isto é, uma estrutura A = (A, ≤, ¬) tal que:
- (A, ≤) é um reticulado distributivo limitado, e
- ¬¬x = x, e
- x ≤ y → ¬y ≤ ¬x.
Álgebras de De Morgan foram introduzidas por Grigore Moisil[1][2] em cerca de 1935,[2] embora sem a restrição de ter um 0 e um 1.[3] 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.[2] (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.[1][2]
Á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 príncipio da não contradição não se sustentam.
Outro exemplo é 4-valorada lógica 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.[2]
Álgebra de Kleene
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.[3] Álgebras booleanas também atendem a essa definição da álgebra de Kleene. A mais simples álgebra de Kleene que não é Booleano é a lógica de três valores de Kleene K3.[4] K3 , fez sua primeira aparição no livro On notation for ordinal numbers (1938) de Kleene.[5] A álgebra foi nomeada de Kleene por Brignole e Monteiro.[6]
Noções relacionadas
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 complementaçã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
- ↑ a b [S.l.: s.n.] Em falta ou vazio
|título=(ajuda) - ↑ a b c d e [S.l.: s.n.] Em falta ou vazio
|título=(ajuda) - ↑ a b Citação vazia (ajuda)
- ↑ [S.l.: s.n.] Em falta ou vazio
|título=(ajuda) - ↑ http://www.jstor.org/stable/2267778
- ↑ 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.
Ler mais
- [S.l.: s.n.] Em falta ou vazio
|título=(ajuda) - Birkhoff, G. review of Moisil Gr. C.. Recherches sur l’algèbre de la logique. Annales scientifiques de l’Université de Jassy, vol. 22 (1936), pp. 1–118. in J. symb. log. 1, p. 63 (1936) doi:10.2307/2268551
- J. A. Kalman Lattices with involution, Trans. Amer. Math. Soc. 87 (1958), 485-491, doi:10.1090/S0002-9947-1958-0095135-X
- [S.l.: s.n.] Em falta ou vazio
|título=(ajuda) - Cattaneo, G. & Ciucci, D. Lattices with Interior and Closure Operators and Abstract Approximation Spaces. Lecture Notes in Computer Science 67–116 (2009). doi:10.1007/978-3-642-03281-3_3
- [S.l.: s.n.] Em falta ou vazio
|título=(ajuda) CS1 maint: Uses authors parameter (link) CS1 maint: Uses editors parameter (link) - [S.l.: s.n.] Em falta ou vazio
|título=(ajuda)