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
Los alfabetos se asocian a conjuntos que pueden ser finitos, numerables de símbolos.
Introducción
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
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.
Se llama producto cartesiano de dos conjuntos y al conjunto
Palabras sobre un alfabeto
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
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
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
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
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
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.
Datos:Q6172678
Junio 26, 2022
Álgebra, palabras, álgebra, palabras, estudia, formalización, gramatical, construcciones, palabras, sobre, alfabeto, para, lenguaje, desde, perspectiva, matemática, permita, modo, firme, afirmar, rechazar, diversos, resultados, necesarios, para, fundamentar, c. El algebra de las palabras estudia la formalizacion gramatical de las construcciones de palabras sobre un alfabeto para un lenguaje desde una perspectiva matematica que permita de un modo firme afirmar o rechazar diversos resultados necesarios para fundamentar cualquier modelo matematico de un lenguaje y mas inmediatamente el lenguaje proposicional Indice 1 El algebra de las palabras sobre un alfabeto 2 Introduccion 2 1 Par ordenado 2 2 Producto cartesiano 3 Palabras sobre un alfabeto 3 1 Sucesiones de igual longitud 3 2 Sucesiones de diferente longitud 3 3 Corolario 4 Concatenacion 5 Vease tambien 6 BibliografiaEl algebra de las palabras sobre un alfabeto EditarLos alfabetos se asocian a conjuntos que pueden ser finitos numerables de simbolos Introduccion EditarLa notacion matematica utilizada es la desarrollada en teoria de conjuntos por lo que requiere una base minima para un rapido trabajo y asimilacion con simplicidad y fluidez de los nuevos conceptos Para introducir nociones que permitan unir simbolos se necesita las siguientes definiciones Par ordenado Editar Dado un par de elementos de un conjunto A displaystyle A es decir a b A displaystyle a b in A se llama a lt a b gt displaystyle lt a b gt un par ordenado Nota Estos pares pueden ser formalmente elementos de nuevos conjuntos sin ningun impedimento y se pueden comparar con otros pares ordenados lt c d gt displaystyle lt c d gt exclusivamente en este orden primero a con c y luego b con d Producto cartesiano Editar Articulo principal Producto cartesiano Se llama producto cartesiano de dos conjuntos A displaystyle A y B displaystyle B al conjunto A B lt a b gt a A b B displaystyle A times B lt a b gt a in A b in B Palabras sobre un alfabeto EditarDado un conjunto A displaystyle A y un numero natural n 1 displaystyle n geq 1 se define el conjunto de las sucesiones finitas de longitud n de elementos de A displaystyle A A n displaystyle A n como el n esimo conjunto de la lista siguiente definida por induccion A 1 A A 2 A A A n A n 1 A displaystyle begin matrix A 1 amp amp A A 2 amp amp A times A amp vdots amp A n amp amp A n 1 times A amp vdots amp end matrix Se llaman palabras sobre un alfabeto A displaystyle A al conjunto de las sucesiones finitas de elementos de A definido como el conjunto A n 1 A n displaystyle A ast bigcup n geq 1 A n es decir las palabras son por definicion una coleccion de todas las sucesiones finitas de elementos de un mismo alfabeto Notaciones Los elementos de A 1 displaystyle A 1 son elementos notados por x lt x gt displaystyle x lt x gt donde x A displaystyle x in A Los elementos de A 2 displaystyle A 2 son pares ordenados notados como lt a b gt lt lt a gt b gt displaystyle lt a b gt lt lt a gt b gt donde a b A displaystyle a b in A Los elementos de A 3 displaystyle A 3 son ternas ordenadas notadas como lt a b c gt lt lt a b gt c gt displaystyle lt a b c gt lt lt a b gt c gt donde a b c A displaystyle a b c in A En general para A n displaystyle A n se tienen sucesiones finitas de longitud n notadas como lt a 1 a n 1 a n gt displaystyle lt a 1 dots a n 1 a n gt lt lt a 1 a n 1 gt a n gt displaystyle lt lt a 1 dots a n 1 gt a n gt donde a i A displaystyle a i in A i 1 n displaystyle forall i in 1 dots n Para determinar el contenido de un elemento a A n displaystyle a in A n se indica como a lt a 1 a n gt displaystyle a lt a 1 dots a n gt donde a i displaystyle a i sera el i esimo termino de la sucesion Esta ultima notacion permite ya comparar palabras son destacables los resultados siguientes Sucesiones de igual longitud Editar Dado dos elementos a n b n A n displaystyle a n b n in A n entonces a n lt a 1 a n gt lt b 1 b n gt b n displaystyle a n lt a 1 dots a n gt lt b 1 dots b n gt b n Leftrightarrow a i b i i 1 n displaystyle a i b i forall i in 1 dots n No es necesario definirlo asi pues se puede demostrar a partir de las definiciones que ya se tiene la demostracion habitual para sucesiones es comparando los elementos ordenadamente segun existan es decir mediante induccion Si n 1 se tiene lt a 1 gt lt b 1 gt displaystyle lt a 1 gt lt b 1 gt por notacion sabemos que a 1 b 1 displaystyle a 1 b 1 Si n 2 es decir un par ordenado se tiene lt a 1 a 2 gt lt b 1 b 2 gt displaystyle lt a 1 a 2 gt lt b 1 b 2 gt por comparacion de un par ordenado a 1 b 1 displaystyle a 1 b 1 y a 2 b 2 displaystyle a 2 b 2 Supongase que para el caso n 1 es cierto vease que tambien lo es para n es decir que es cierto que a n 1 lt a 1 a n 1 gt displaystyle a n 1 lt a 1 dots a n 1 gt lt b 1 b n 1 gt b n 1 displaystyle lt b 1 dots b n 1 gt b n 1 Leftrightarrow a i b i i 1 n 1 displaystyle a i b i forall i in 1 dots n 1 y ahora se tiene que comprobar para el caso n lt lt a 1 a n 1 gt a n gt lt lt b 1 b n 1 gt b n gt displaystyle lt lt a 1 dots a n 1 gt a n gt lt lt b 1 dots b n 1 gt b n gt es decir lt lt a n 1 gt a n gt lt lt b n 1 gt b n gt displaystyle lt lt a n 1 gt a n gt lt lt b n 1 gt b n gt es decir lt a n 1 a n gt lt b n 1 b n gt displaystyle lt a n 1 a n gt lt b n 1 b n gt Leftrightarrow a n 1 b n 1 displaystyle a n 1 b n 1 y a n b n displaystyle a n b n como se vio en el caso n 2 dd Sucesiones de diferente longitud Editar Dado dos elementos a m b m k A displaystyle a m b m k in A ast tales que a m displaystyle a m lt a 1 a m gt displaystyle lt a 1 dots a m gt lt b 1 b m k gt displaystyle lt b 1 dots b m k gt b m k displaystyle b m k con k gt 0 y m gt 1 entonces a 1 lt b 1 b k 1 gt displaystyle a 1 lt b 1 dots b k 1 gt y a i b i k displaystyle a i b i k i 1 m displaystyle forall i in 1 dots m Informalmente es evidente que a 1 displaystyle a 1 lt b 1 b k 1 gt displaystyle lt b 1 dots b k 1 gt 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 displaystyle a 1 lt b 1 b k 1 gt displaystyle lt b 1 dots b k 1 gt y por tanto es cierto Si m 2 se tiene que lt a 1 a 2 gt displaystyle lt a 1 a 2 gt lt lt b 1 b k 1 gt b k 2 gt displaystyle lt lt b 1 dots b k 1 gt b k 2 gt como par ordenado sucede que a 1 displaystyle a 1 lt b 1 b k 1 gt displaystyle lt b 1 dots b k 1 gt Supongase que el caso m 1 es cierto vease ahora que tambien lo es para m Por hipotesis se puede tomar el par ordenado lt lt a 1 a m 1 gt a m gt displaystyle lt lt a 1 dots a m 1 gt a m gt lt lt b 1 b m 1 k gt b m k gt displaystyle lt lt b 1 dots b m 1 k gt b m k gt esto prueba la certeza pues tienen las mismas hipotesis para una k gt 0 fijada dd Corolario Editar Dado un conjunto A displaystyle A sin elementos expresados mediante sucesiones finitas de sus propios elementos si a b A a b displaystyle a b in A ast a b entonces a y b son de la misma longitud A n A m displaystyle A n cap A m emptyset para n m displaystyle n neq m Concatenacion EditarSe llama operacion concatenacion entre sucesiones finitas a A A A lt lt a 1 a n gt lt b 1 b m gt gt lt a 1 a n gt lt b 1 b m gt lt a 1 a n b 1 b m gt displaystyle begin matrix circ amp A ast times A ast amp longrightarrow amp A ast amp lt lt a 1 dots a n gt lt b 1 dots b m gt gt amp longmapsto amp lt a 1 dots a n gt circ lt b 1 dots b m gt lt a 1 dots a n b 1 dots b m gt end matrix Por tanto la estructura lt A gt displaystyle lt A ast circ gt es un grupoide libre generado por el conjunto A displaystyle A Para hacer referencia al mismo objeto matematico se escribe por comodidad simplemente a 1 a n displaystyle a 1 dots a n lt a 1 a n gt displaystyle lt a 1 dots a n gt lt a 1 gt lt a n gt displaystyle lt a 1 gt circ cdots circ lt a n gt Vease tambien EditarLenguaje proposicional Logica de primer ordenBibliografia EditarHerbert 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 Exposicion propia del algebra de las palabras Nino B Cocchiarella and Max A Freund Modal Logica An Introduction to Its Syntax and Semantics Oxford 2008 Contiene un resumen en el primer tema con cierta informalidad Datos Q6172678 Obtenido de https es wikipedia org w index php title Algebra de las palabras amp oldid 133825803, wikipedia, wiki, leyendo, leer, libro, biblioteca,