Autor Tema: Lenguajes de 1er y 2do orden

0 Usuarios y 1 Visitante están viendo este tema.

24 Abril, 2009, 11:14 pm
Leído 1171 veces

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,292
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
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?


25 Abril, 2009, 08:47 pm
Respuesta #1

Teón

  • Lathi
  • Mensajes: 1,322
  • Karma: +0/-0
  • Sexo: Masculino
  • C:.J:.T:.
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.
Eram quod es, eris quod sum.

25 Abril, 2009, 10:37 pm
Respuesta #2

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,292
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
¿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?

29 Abril, 2009, 09:45 pm
Respuesta #3

Teón

  • Lathi
  • Mensajes: 1,322
  • Karma: +0/-0
  • Sexo: Masculino
  • C:.J:.T:.
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.
Eram quod es, eris quod sum.