Á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 A_{}^{}, es decir,  a,b \in A , se llama a <a,b>_{}^{} 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 <c,d>_{}^{} exclusivamente en este orden, primero a con c y luego b con d.

Producto cartesiano[editar]

Se llama producto cartesiano de dos conjuntos A_{}^{} y B_{}^{} al conjunto  A \times B := \{ <a ,\; b> : a \in A ,\; b \in B \}.

Palabras sobre un alfabeto[editar]

Dado un conjunto A_{}^{} y un número natural  n \geq 1_{}^{}, se define el conjunto de las sucesiones finitas de longitud n de elementos de A_{}^{}, A_{}^n, como el n-ésimo conjunto de la lista siguiente definida por inducción:

\begin{matrix}
A^1 & = & A \\
A^2 & = & A \times A \\
& \vdots & \\
A^n & = & A^{n-1} \times A \\
& \vdots &
\end{matrix}

Se llaman palabras sobre un alfabeto A_{}^{} al conjunto de las sucesiones finitas de elementos de A definido como el conjunto A^{\ast} = \bigcup_{n \geq 1} A^n, 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 A^1_{} son elementos notados por x := < x_{}^{}> donde  x \in A.
  • Los elementos de A^2_{} son pares ordenados, notados como < a ,\; b >:=<<a> ,\; b_{}^{}> donde  a,b \in A.
  • Los elementos de A^3_{} son ternas ordenadas, notadas como < a ,\; b ,\; c >:=<<a ,\; b >,\; c_{}^{} > donde  a,b,c \in A.
  • En general, para A^n_{} se tienen sucesiones finitas de longitud n notadas como < a_1 ,\; \dots ,\; a_{n-1}^{} ,\; a_n >:= < < a_1 ,\; \dots ,\; a_{n-1}^{} > ,\; a_n > donde  a_i \in A, \forall i \in \{1 ,\; \dots ,\; n \}.
  • Para determinar el contenido de un elemento a \in A^n_{} se indica como a=<a_1 ,\; \dots ,\; a_n^{}> donde a_i^{} 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 a^n,b^n \in A^n , entonces

a^n=<a_1 ,\; \dots ,\; a_n > = <b_1^{} ,\; \dots ,\; b_n >=b^n \Leftrightarrow a_i=b_i ,\; \forall i \in \{1 ,\; \dots ,\; n \}.

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 <a_1^{}>=<b_1> por notación sabemos que a_1^{}=b_1.
Si n=2, es decir un par ordenado, se tiene <a_1 ,\; a_2>=<b_1 ,\; b_2^{}> por comparación de un par ordenado a_1=b_1^{} y a_2=b_2^{}.
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 a^{n-1}=<a_1 ,\; \dots ,\; a_{n-1}^{}> =  <b_1 ,\; \dots ,\; b_{n-1}^{} >=b^{n-1} \Leftrightarrow a_i=b_i ,\; \forall i \in \{1 ,\; \dots ,\; n-1 \}, y ahora se tiene que comprobar para el caso n:
<<a_1 ,\; \dots ,\; a_{n-1} > ,\; a_n^{} >=<<b_1 ,\; \dots ,\; b_{n-1} > ,\; b_n >, es decir, <<a^{n-1}> ,\; a_n >=<<b^{n-1}> ,\; b_n^{}>, es decir, < a^{n-1} ,\; a_n >=<b^{n-1} ,\; b_n^{}> \Leftrightarrow a^{n-1}=b_{}^{n-1} y a_n=b_n^{} como se vio en el caso n=2.

Sucesiones de diferente longitud[editar]

Dado dos elementos a^m,b^{m+k} \in A^\ast tales que a_{}^m= <a_1 ,\; \dots ,\; a_m^{} >= <b_1^{} ,\; \dots ,\; b_{m+k}>= b_{}^{m+k} con k>0 y m>1, entonces:

a_1^{}=<b_1 ,\; \dots ,\; b_{k+1}^{}> y a_i=b_{i+k}^{}, \forall i \in \{1 ,\; \dots ,\; m \}.

Informalmente es evidente que  a_1^{}= <b_1 ,\; \dots ,\; b_{k+1}^{}> debido al resultado anterior para sucesiones de igual longitud, para demostrarlo formalmente se procede del modo siguiente:

Si m=1, se tiene directamente que  a_1^{}= <b_1 ,\; \dots ,\; b_{k+1}^{}>, y por tanto es cierto.
Si m=2, se tiene que <a_1^{} ,\; a_2>= <<b_1 ,\; \dots ,\; b_{k+1}> ,\; b_{k+2}>, como par ordenado, sucede que  a_1^{}= <b_1 ,\; \dots ,\; b_{k+1}^{}>.
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 <<a_1 ,\; \dots ,\; a_{m-1}^{}> ,\; a_m>= <<b_1 ,\; \dots ,\; b_{(m-1)+k}> ,\; b_{m+k}^{}>, esto prueba la certeza, pues tienen las mismas hipótesis para una k>0 fijada.

Corolario[editar]

Dado un conjunto A_{}^{} sin elementos expresados mediante sucesiones finitas de sus propios elementos, si a,b \in A_{}^\ast : a=b entonces:

  • a y b son de la misma longitud,
  • A_{}^n \cap A^m = \emptyset para n \neq m_{}^{}.

Concatenación[editar]

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

\begin{matrix}
\circ : & A^\ast \times A^\ast & \longrightarrow & A^\ast \\
& < <a_1 ,\; \dots ,\; a_n>,<b_1 ,\; \dots ,\; b_m> > & \longmapsto & <a_1 ,\; \dots ,\; a_n > \circ <b_1 ,\; \dots ,\; b_m> = <a_1 ,\; \dots ,\; a_n ,\; b_1 ,\; \dots ,\; b_m>.
\end{matrix}

Por tanto la estructura <A^\ast ,\; \circ > es un grupoide libre generado por el conjunto A_{}^{}.

Para hacer referencia al mismo objeto matemático, se escribe por comodidad simplemente a_1 \dots a_n := <a_1 ,\; \dots ,\; a_n>= <a_1>\circ \cdots \circ<a_n>.

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.