Fragment (logic) (original) (raw)
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. Hence, the well-formed formulae of the fragment are a subset of those in the original logic. However, the semantics of the formulae in the fragment and in the logic coincide, and any formula of the fragment can be expressed in the original logic.
| Property | Value |
|---|---|
| dbo:abstract | 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. Hence, the well-formed formulae of the fragment are a subset of those in the original logic. However, the semantics of the formulae in the fragment and in the logic coincide, and any formula of the fragment can be expressed in the original logic. 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. (en) |
| dbo:wikiPageID | 43571557 (xsd:integer) |
| dbo:wikiPageLength | 1970 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 761979983 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Descriptive_complexity_theory dbr:Mathematical_logic dbr:Model_checking dbr:Complexity_class dbr:Computational_complexity_theory dbr:Computational_logic dbr:First-order_logic dbr:Well-formed_formula dbr:Reduction_(complexity) dbc:Mathematical_logic dbr:Syntax dbr:Theory_(mathematical_logic) dbr:Satisfiability |
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:Logic-stub |
| dct:subject | dbc:Mathematical_logic |
| gold:hypernym | dbr:Subset |
| rdf:type | dbo:ProgrammingLanguage |
| rdfs:comment | 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. Hence, the well-formed formulae of the fragment are a subset of those in the original logic. However, the semantics of the formulae in the fragment and in the logic coincide, and any formula of the fragment can be expressed in the original logic. (en) |
| rdfs:label | Fragment (logic) (en) |
| owl:sameAs | freebase:Fragment (logic) wikidata:Fragment (logic) https://global.dbpedia.org/id/mS6s |
| prov:wasDerivedFrom | wikipedia-en:Fragment_(logic)?oldid=761979983&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Fragment_(logic) |
| is dbo:wikiPageDisambiguates of | dbr:Fragment |
| is dbo:wikiPageRedirects of | dbr:Fragment_(logics) |
| is dbo:wikiPageWikiLink of | dbr:Description_logic dbr:Logic_of_graphs dbr:Datalog dbr:Abstract_elementary_class dbr:Monadic_second-order_logic dbr:Fragment dbr:Tuple-generating_dependency dbr:Fragment_(logics) |
| is foaf:primaryTopic of | wikipedia-en:Fragment_(logic) |