Rincón Matemático

Matemática => Lógica, Conjuntos, Lenguajes Formales => Lógica => Mensaje iniciado por: argentinator en 24 Abril, 2009, 11:14 pm

Título: Lenguajes de 1er y 2do orden
Publicado por: argentinator en 24 Abril, 2009, 11:14 pm
Necesitaría una definición sencilla e informal y clara de lenguajes de 1er orden y 2do orden.
O sea, tengo una ideas de estas cosas, pero no lo tengo del todo claro, y no necesito adentrarme demasiado en la teoria, al menos por ahora.
Más que nada quiero abrir un poco la discusión a ver si lo que creo saber o entender está más o menos acertado.

¿Que puede hacerse con un lenguaje de 2do orden que no se pueda en uno de 1er orden?
¿Algún ejemplo típico de proposicion en lenguaje de 2do orden?
¿Puede instruirse a una computadora a procesar sentencias de 2do orden?
¿Lenguajes de 3er orden, 4to, n-ésimo orden?

Título: Re: Lenguajes de 1er y 2do orden
Publicado por: Teón en 25 Abril, 2009, 08:47 pm
Voy a dar una primera aproximación,
Un lenguaje del primer orden, es una extensión de la lógica proposicional, a la que se agregan los cuantificadores, los cuantificadores, en este lenguaje, solo se pueden aplicar sobre variables de individuo (no se permite \( \forall{P} \) donde P es un predicado).
Con esta lógica se puede hacer casi todo, además está respaldada por los teoremas de completitud y de corrección.

Una fórmula en lenguaje del primer orden sería:
\( \forall x \exists yP(x,y) \)
Por supuesto que una fórmula proposicional sin cuantificadores, también pertenecería a este lenguaje.

La siguiente fórmula, no es una fórmula bien hecha (fbh) en LPO:

(1)\( \forall X (X0 \wedge \forall y(Xy \rightarrow X(sig(y)))\rightarrow \forall xXx)  \)

Sin embargo, la fórmula aludida (1), es una fbh en un lenguaje del segundo orden.
Pero (1) es, nada menos que la formalización del principio de inducción completa.

Saludos.
Título: Re: Lenguajes de 1er y 2do orden
Publicado por: argentinator en 25 Abril, 2009, 10:37 pm
¿El principio de induccion puede expresarse de alguna manera en lenguaje de primer orden?

Otra pregunta.
Supongamos que quiero probar teoremas automaticamente con una computadora.
¿Debo restringirme a lenguajes de 1er orden, de 2do orden, o puedo trabajar con cualquiera?
Título: Re: Lenguajes de 1er y 2do orden
Publicado por: Teón en 29 Abril, 2009, 09:45 pm
Hola.
Si el principio de inducción completa, pudiera expresarse en lenguaje del primer orden, la aritmética se podría construir con enunciados en lógica del primer orden, luego, tendríamos los teortemas de corrección y completitud para la aritmética. Contrariamente al teorema de Gödel.
Saludos.