Fragmento (lógica)

En lógica matemática , un fragmento de un lenguaje o teoría lógica es un subconjunto de dicho lenguaje, obtenido al imponer restricciones sintácticas , manteniendo la misma semántica que el lenguaje original. ^{[ 1 ]} Las fórmulas bien formadas del fragmento constituyen entonces un subconjunto de las fórmulas de la lógica original.

Los fragmentos son útiles porque ciertas clases de significados no requieren la fuerza completa del lenguaje para ser expresadas, por lo que es parsimonioso expresar estos significados con la fuerza reducida que requieren, es decir, mediante un fragmento del lenguaje completo. La ventaja es que, por lo general, el fragmento satisface propiedades más agradables, es computable de manera más eficiente, etc., que el lenguaje completo.

La complejidad computacional de tareas como la satisfacibilidad o la verificación de modelos para el fragmento lógico no puede ser mayor que la de las mismas tareas en la lógica original, ya que existe una reducción del primer problema al otro. Un problema importante en la lógica computacional es determinar fragmentos de lógicas bien conocidas, como la lógica de primer orden, que sean lo más expresivos posible y a la vez decidibles o, mejor aún, que tengan una baja complejidad computacional. ^{[ 1 ]} El campo de la teoría de la complejidad descriptiva tiene como objetivo establecer un vínculo entre las lógicas y la teoría de la complejidad computacional , mediante la identificación de fragmentos lógicos que capturen con precisión ciertas clases de complejidad . ^{[ 2 ]}