Fragment (logic)

In mathematical logic, a fragment of a logical language or theory is a subset of this logical language obtained by imposing syntactical restrictions on the language, while still imposing the same semantics as the unrestricted language.^[1] The well-formed formulae of the fragment then form a subset of those in the original logic.

Fragments are useful in that, certain classes of meanings does not require the full strength of the full language to be expressed, and so it is parsimonious to express these meanings with the weakened strength that they require, i.e. by a fragment of the full language. The benefit is that, usually the fragment satisfies nicer properties, is more efficiently computable, etc, than the full language,

The computational complexity of tasks such as satisfiability or model checking for the logical fragment can be no higher than the same tasks in the original logic, as there is a reduction from the first problem to the other. An important problem in computational logic is to determine fragments of well-known logics such as first-order logic that are as expressive as possible yet are decidable or more strongly have low computational complexity.^[1] The field of descriptive complexity theory aims at establishing a link between logics and computational complexity theory, by identifying logical fragments that exactly capture certain complexity classes.^[2]