I read everywhere that description logics are decidable fragments of first-order logic. What does this mean? What is a decidable fragment of first-order logic?
2026-03-27 03:46:17.1774583177
On
What is a decidable fragment?
387 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
2
There are 2 best solutions below
0
On
It is a "subset" of first-order logic that is decidable.
Another example is Monadic predicate calculus :
in which all relation symbols are monadic (that is, they take only one argument), and there are no function symbols. This means that all atomic formulas are thus of the form $P(x)$.
In the case of a logical system, decidability means that :
there is an effective method for determining whether arbitrary formulas are theorems of the logical system. For example, propositional logic is decidable, because the truth-table method can be used to determine whether an arbitrary propositional formula is logically valid.
A decidable logic is one where, given a statement, you can compute whether or not that statement is true in the logic.
A fragment of a logic is a subset of that logic obtained by imposing syntactic restrictions. The fragment has the same semantics, but possibly fewer well-formed formulae.
So a decidable fragment of first-order logic is a syntactically-restricted subset of first-order logic in which truth is computable.