What is a decidable fragment?

387 Views Asked by At

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?

2

There are 2 best solutions below

0
On BEST ANSWER

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.

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.