Fragment (logic)

In logic, a fragment refers to a restricted subset of a larger, more expressive logical system. The motivation for studying fragments is often to achieve a balance between expressive power and computational tractability. A fragment may be defined by limiting the available logical connectives, quantifiers, or the structural rules of inference.

The primary reasons for investigating fragments are:

• Decidability: The full logical system might be undecidable (meaning there is no algorithm to determine whether a given formula is valid or not). However, a carefully chosen fragment may possess decidability. This allows for automated reasoning and verification within that fragment.
• Computational Complexity: Even if the full system is decidable, the computational complexity of determining validity or satisfiability may be too high for practical applications (e.g., NP-complete or worse). Fragments can be designed to have lower complexity, allowing for more efficient algorithms.
• Practical Applications: Certain fragments may be particularly well-suited for modeling specific domains or solving particular problems. By focusing on a fragment, one can develop specialized tools and techniques that are more effective than general-purpose methods.
• Understanding Expressiveness: Studying the properties of different fragments helps to understand the relative expressive power of different logical constructs and how they contribute to the overall complexity of the system.

Examples of fragments include:

• Propositional Logic: A fragment of first-order logic that only allows propositional variables and logical connectives (e.g., AND, OR, NOT, IMPLIES).
• Description Logic: A family of logics designed for knowledge representation and reasoning, which can be seen as fragments of first-order logic with specific restrictions on quantifiers and predicates. Various DLs exist with different levels of expressiveness and computational complexity.
• Modal Logic: A fragment of first-order logic interpreted over possible worlds, often focusing on reasoning about knowledge, belief, or time.
• Horn Logic: A fragment of first-order logic where all clauses are Horn clauses (clauses with at most one positive literal). Horn logic is the basis for logic programming languages like Prolog.

The process of identifying and analyzing logical fragments often involves:

• Defining the fragment precisely by specifying the allowed syntax and inference rules.
• Proving properties of the fragment, such as decidability, complexity, and expressiveness.
• Developing algorithms for reasoning within the fragment.
• Comparing the fragment to other fragments and to the full logical system.