Concept
Fragment (logic)
Overview
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. 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. 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.
Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).
In the original texts
Passages from public-domain books where Fragment (logic) is discussed.
In the lava and in the scoriae of this little crater, I found several fragments, which, from their angular form, their granular structure, their freedom from air-cells, their brittle and burnt condition, closely resembled those fragments of primary rocks which are occasionally ejected, as at Ascension, from volcanoes. These fragments consist of glassy albite, much mackled, and with very imperfect cleavages, mingled…
Charles Darwin, Volcanic Islands
names the idea; a chapter is titled for it; opens on it
Let an architect be compelled to build an edifice with uncut stones, fallen from a precipice. The shape of each fragment may be called accidental; yet the shape of each has been determined by the force of gravity, the nature of the rock, and the slope of the precipice,—events and circumstances, all of which depend on natural laws; but there is no relation between these laws and the purpose for which each fragment is…
Charles Darwin, The Variation of Animals and Plants under Domestication
names the idea; states what it is
Take a handful of any pounded substance, containing fragments of all sizes; and let it fall to the ground while a gentle breeze is blowing. The large fragments will be collected together on the ground almost immediately under the hand; somewhat smaller fragments will be carried a little to the leeward; still smaller ones a little further; and those minute particles which we call dust, will be drifted a long way…
Herbert Spencer, First Principles
names the idea
This is nothing else than the necessity of abstract logic, which is the presupposition involved in the very fact of interrelated existence as disclosed in each immediate occasion of experience. The key to the pattern means this fact:—that from a select set of those general conditions, exemplified in any one and the same occasion, a pattern involving an infinite variety of other such conditions, also exemplified in…
Alfred North Whitehead, Science and the modern world
states what it is
Such, however, is Spencer's illusion. He takes reality in its present form; he breaks it to pieces, he scatters it in fragments which he throws to the winds; then he "integrates" these fragments and "dissipates their movement." Having _imitated_ the Whole by a work of mosaic, he imagines he has retraced the design of it, and made the genesis.
Henri Bergson, Creative Evolution
names the idea
Related ideas
- First-order logic
- Mathematical logic
- Syntax
- Model checking
- Well-formed formula
- Computational complexity theory
Place in the tradition
Part of Description logic.