En lógica matemática , un fragmento de un lenguaje o teoría lógica es un subconjunto de este lenguaje lógico obtenido al imponer restricciones sintácticas al lenguaje. [1] Por lo tanto, las fórmulas bien formadas del fragmento son un subconjunto de las de la lógica original. Sin embargo, la semántica de las fórmulas en el fragmento y en la lógica coincide, y cualquier fórmula del fragmento puede expresarse en la lógica original.
La complejidad computacional de tareas como la satisfacibilidad o la verificación del modelo para el fragmento lógico no puede ser mayor que la de las mismas tareas en la lógica original, ya que hay 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 expresivas posible pero que sean decidibles o que tengan una complejidad computacional más baja. [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 exactamente ciertas clases de complejidad . [2]