フラグメント（ロジック）

数理論理学では、論理言語または理論のフラグメントは、言語に統語的制約を課すことによって得られるこの論理言語のサブセットです。 ^[1]したがって、フラグメントの整形式の式は、元の論理のサブセットです。ただし、フラグメントとロジックの式の意味は一致しており、フラグメントの任意の式は元のロジックで表現できます。

論理フラグメントの充足可能性やモデル検査などのタスクの計算複雑度は、最初の問題から他の問題への還元があるため、元のロジックの同じタスクよりも高くすることはできません。計算論理における重要な問題は、可能な限り表現力がありながら決定可能であるか、より強く計算複雑性が低い、一階述語論理などのよく知られたロジックのフラグメントを決定することです。 ^[1]記述的複雑性理論の分野では、特定の複雑性クラスを正確に捉える論理フラグメントを特定することにより、ロジックと計算複雑性理論を結び付けることを目的としています。^[2]