Álgebra de Kleene

Em matemática, uma álgebra de Kleene pode se referir a dois conceitos. Pode ser um reticulado distribuído limitado com uma involução que satisfaz os teoremas de De Morgan e ( x ∧ ∼ x ) ≤ ( y ∨ ∼ y ) {\displaystyle (x\wedge \sim x)\leq (y\vee \sim y)} . Logo, toda a álgebra booleana é uma álgebra de Kleene, mas a maioria das álgebras de Kleene não são álgebras booleanas. Assim como álgebras booleanas estão relacionadas à lógica proposicional clássica, as álgebras de Kleene estão relacionadas à lógica ternária. Também pode ser uma estrutura algébrica que generaliza as operações conhecidas através das expressões regulares.

Seu nome é uma referência ao matemático estado-unidense Stephen Cole Kleene, que, entretanto, não foi o responsável por sua definição. Ele introduziu as expressões regulares e questionou um conjunto completo de axiomas que permitiriam a derivação de todas as equações entre expressões regulares. O problema foi estudado originalmente por John Horton Conway com o nome de álgebras regulares. os axiomas das álgebras de Kleene resolvem o problema, como demonstrado por Dexter Kozen.

Definição

Várias definições não equivalentes de álgebras de Kleene estão presentes na literatura.

Ponto de vista das expressões regulares

Uma álgebra de Kleene é um conjunto A com duas operações binárias + ( a + b {\displaystyle a+b} ) e · ( a b {\displaystyle ab} ) e um operador unário * (fecho de Kleene; a ∗ {\displaystyle a*} ), de forma que os seguintes axiomas sejam satisfeitos:

  • Associatividade de + e ·: ∀ a , b , c ∈ A { a + ( b + c ) = ( a + b ) + c a ( b c ) = ( a b ) c {\displaystyle \forall a,b,c\in A{\begin{cases}a+(b+c)=(a+b)+c\\a(bc)=(ab)c\\\end{cases}}}
  • Comutatividade de +: ∀ a , b ∈ A a + b = b + a {\displaystyle \forall a,b\in A\quad a+b=b+a}
  • Distributividade: ∀ a , b , c ∈ A { a ( b + c ) = ( a b ) + ( a c ) ( b + c ) a = ( b a ) + ( c a ) {\displaystyle \forall a,b,c\in A{\begin{cases}a(b+c)=(ab)+(ac)\\(b+c)a=(ba)+(ca)\\\end{cases}}}
  • Elementos neutros de + e ·: { ∃ 0 ∈ A ∀ a ∈ A a + 0 = 0 + a = a ∃ 1 ∈ A ∀ a ∈ A a 1 = 1 a = a {\displaystyle {\begin{cases}\exists 0\in A\forall a\in A\quad a+0=0+a=a\\\exists 1\in A\forall a\in A\quad a1=1a=a\\\end{cases}}}
  • ∀ a ∈ A a 0 = 0 a = 0 {\displaystyle \forall a\in A\quad a0=0a=0}

Os axiomas acima definem um semianel. Há ainda outros requisitos:

  • Idempotência de + : ∀ a ∈ A a + a = a {\displaystyle \forall a\in A\quad a+a=a}

De acordo com os axiomas acima, pode-se concluir que uma álgebra de Kleene é um semianel idempotente. Agora é possível definir uma ordem parcial ≤ em A definindo a ≤ b se e somente se a + b = b (ou equivalentemente: a ≤ b se e somente se existe um x em A de forma que a + x = b). Com tal ordem pode-se formular os últimos axiomas da operação *:

  • ∀ a ∈ A 1 + a a ∗ ≤ a ∗ {\displaystyle \forall a\in A\quad 1+aa^{*}\leq a^{*}}
  • ∀ a ∈ A 1 + a ∗ a ≤ a ∗ {\displaystyle \forall a\in A\quad 1+a^{*}a\leq a^{*}}
  • ∀ a , x ∈ A , a x ≤ x → a ∗ x ≤ x {\displaystyle \forall a,x\in A,ax\leq x\to a^{*}x\leq x}
  • ∀ a , x ∈ A , x a ≤ x → x a ∗ ≤ x {\displaystyle \forall a,x\in A,xa\leq x\to xa^{*}\leq x}

Ponto de vista dos reticulados

Seja um reticulado L que satisfaz os teoremas de De Morgan com um operador unário ~ em que ( x ∧ ∼ x ) ≤ ( y ∨ ∼ y ) {\displaystyle (x\wedge \sim x)\leq (y\vee \sim y)} . Interpretando-se ' como ~, qualquer álgebra booleana também é uma álgebra de Kleene, mas a recíproca não é verdadeira.

Exemplos

Seja Σ um conjunto finito (um alfabeto) e A o conjunto de todas as expressões regulares em Σ. Considera-se que duas dessas expressões regulares são iguais se elas descrevem a mesma linguagem. então A forma uma álgebra de Kleene.

Seja Σ um alfabeto e A o conjunto de todas as linguagens regulares em Σ (ou o conjunto de todas as linguagens livres de contexto em Σ; ou o conjunto de todas as linguagens recursivas em Σ; ou o conjunto de todas as linguagens em Σ). Então a união (+) e a concatenação (·) de dois elementos de A também pertence a A, assim como o fecho de Kleene aplicado a qualquer elemento de A. Obtém-se uma álgebra de Kleene A com 0 sendo o conjunto vazio e 1 sendo o conjunto que somente contém o conjunto vazio.

Seja M um monóide com elemento neutro e e seja A um conjunto de todos os subconjuntos de M. Para dois desses subconjuntos S e T, seja S + T a união de S e T e o conjunto ST = {st : s em S e t em T}. S* é definido como o submonóide de M gerado por S, que pode ser descrito como {e} ∪ S ∪ SS ∪ SSS ∪ ... Logo, A forma uma álgebra de Kleene com 0 sendo o conjunto vazio e 1 sendo {e}.

Toda álgebra booleana com operações ∨ {\displaystyle \lor } e ∧ {\displaystyle \land } torna-se uma álgebra de Kleene se for usado ∨ {\displaystyle \lor } como +, ∧ {\displaystyle \land } como · e a* = 1 para todo a.

Ver também