Álgebra de las palabras

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Arbol.PNG

El álgebra de las palabras estudia la formalización gramatical de las construcciones de palabras sobre un alfabeto para un lenguaje, desde una perspectiva matemática que permita, de un modo firme, afirmar o rechazar diversos resultados necesarios para fundamentar cualquier modelo matemático de un lenguaje, y más inmediatamente el lenguaje proposicional.

El álgebra de las palabras sobre un alfabeto[editar]

Los alfabetos se asocian a conjuntos que pueden ser finitos, numerables de símbolos.

Introducción[editar]

La notación matemática utilizada es la desarrollada en teoría de conjuntos, por lo que requiere una base mínima para un rápido trabajo y asimilación con simplicidad y fluidez de los nuevos conceptos.

Para introducir nociones que permitan unir símbolos se necesita las siguientes definiciones.

Par ordenado[editar]

Dado un par de elementos de un conjunto , es decir, , se llama a un par ordenado.

Nota:

Estos pares pueden ser formalmente elementos de nuevos conjuntos sin ningún impedimento, y se pueden comparar con otros pares ordenados exclusivamente en este orden, primero a con c y luego b con d.

Producto cartesiano[editar]

Se llama producto cartesiano de dos conjuntos y al conjunto

Palabras sobre un alfabeto[editar]

Dado un conjunto y un número natural , se define el conjunto de las sucesiones finitas de longitud n de elementos de , , como el n-ésimo conjunto de la lista siguiente definida por inducción:

Se llaman palabras sobre un alfabeto al conjunto de las sucesiones finitas de elementos de A definido como el conjunto , es decir, las palabras son por definición una colección de todas las sucesiones finitas de elementos de un mismo alfabeto.

Notaciones:

  • Los elementos de son elementos notados por donde
  • Los elementos de son pares ordenados, notados como donde
  • Los elementos de son ternas ordenadas, notadas como donde
  • En general, para se tienen sucesiones finitas de longitud n notadas como donde ,
  • Para determinar el contenido de un elemento se indica como donde será el i-ésimo termino de la sucesión.

Esta última notación permite, ya, comparar palabras, son destacables los resultados siguientes:

Sucesiones de igual longitud[editar]

Dado dos elementos , entonces

No es necesario definirlo así, pues se puede demostrar a partir de las definiciones que ya se tiene, la demostración habitual, para sucesiones, es comparando los elementos ordenadamente según existan, es decir, mediante inducción:

Si n=1, se tiene por notación sabemos que
Si n=2, es decir un par ordenado, se tiene por comparación de un par ordenado y
Supóngase que para el caso n-1 es cierto, véase que también lo es para n, es decir, que es cierto que , y ahora se tiene que comprobar para el caso n:
, es decir, , es decir, y como se vio en el caso n=2.

Sucesiones de diferente longitud[editar]

Dado dos elementos tales que con k>0 y m>1, entonces:

y ,

Informalmente es evidente que debido al resultado anterior para sucesiones de igual longitud, para demostrarlo formalmente se procede del modo siguiente:

Si m=1, se tiene directamente que , y por tanto es cierto.
Si m=2, se tiene que , como par ordenado, sucede que
Supóngase que el caso m-1 es cierto, véase ahora que también lo es para m:
Por hipótesis se puede tomar el par ordenado , esto prueba la certeza, pues tienen las mismas hipótesis para una k>0 fijada.

Corolario[editar]

Dado un conjunto sin elementos expresados mediante sucesiones finitas de sus propios elementos, si entonces:

  • a y b son de la misma longitud,
  • para

Concatenación[editar]

Se llama operación concatenación entre sucesiones finitas a:

Por tanto la estructura es un grupoide libre generado por el conjunto .

Para hacer referencia al mismo objeto matemático, se escribe por comodidad simplemente

Páginas relacionadas[editar]

lenguaje proposicional

lenguaje de orden cero

lenguaje de predicados

lenguaje de primer orden

Bibliografía[editar]

Herbert B. Enderton, Elements of set theory, Academic Press, INC. 1977.

Contiene normas para la correcta lectura del texto.

Herbert B. Enderton, A mathematical introduction to logic, A Harcourt Science an Tecnology Company 2001.

Exposición propia del álgebra de las palabras.

Nino B. Cocchiarella and Max A. Freund, Modal Lógica An Introduction to Its Syntax and Semantics, Oxford 2008.

Contiene un resumen en el primer tema con cierta informalidad.