Hybrid logic
Encyclopedia
Hybrid logic refers to a number of extensions to propositional modal logic
Modal logic
Modal logic is a type of formal logic that extends classical propositional and predicate logic to include operators expressing modality. Modals — words that express modalities — qualify a statement. For example, the statement "John is happy" might be qualified by saying that John is...

 with more expressive power, though still less than first-order logic
First-order logic
First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...

. In formal logic
Formal logic
Classical or traditional system of determining the validity or invalidity of a conclusion deduced from two or more statements...

, there is a trade-off between expressiveness and computational tractability (how easy it is to compute
Computer
A computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...

/reason
Automated reasoning
Automated reasoning is an area of computer science dedicated to understand different aspects of reasoning. The study in automated reasoning helps produce software which allows computers to reason completely, or nearly completely, automatically...

 with logical languages). The history of hybrid logic began with Arthur Prior's work in tense logic.

Unlike ordinary modal logic, hybrid logic makes it possible to refer to states (possible worlds) in formulas.
This is achieved by a class of formulas called nominals, which are true in exactly one state, and by the use of the @ operator, which is defined as follows:
@i p is true if and only if
IFF
IFF, Iff or iff may refer to:Technology/Science:* Identification friend or foe, an electronic radio-based identification system using transponders...

 p is true in the unique state named by the nominal i (i.e., the state where i is true).


Hybrid logics with extra or other operators exist, but @ is more-or-less "standard."

Hybrid logics have many features in common with temporal logic
Temporal logic
In logic, the term temporal logic is used to describe any system of rules and symbolism for representing, and reasoning about, propositions qualified in terms of time. In a temporal logic we can then express statements like "I am always hungry", "I will eventually be hungry", or "I will be hungry...

s (which use nominal-like constructs to denote specific points in time), and they are a rich source of ideas for researchers in modern modal logic. They also have applications in the areas of feature logic, model theory
Model theory
In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....

, proof theory
Proof theory
Proof theory is a branch of mathematical logic that represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. Proofs are typically presented as inductively-defined data structures such as plain lists, boxed lists, or trees, which are constructed...

, and the logical analysis of natural language
Natural language
In the philosophy of language, a natural language is any language which arises in an unpremeditated fashion as the result of the innate facility for language possessed by the human intellect. A natural language is typically used for communication, and may be spoken, signed, or written...

. It is also deeply connected to description logic
Description logic
Description logic is a family of formal knowledge representation languages. It is more expressive than propositional logic but has more efficient decision problems than first-order predicate logic....

 because the use of nominals allows one to perform assertional ABox
Abox
In Computer Science, an ABox is an "assertion component"—a fact associated with a terminological vocabulary within a knowledge base.The terms ABox and TBox are used to describe two different types of statements in ontologies. TBox statements describe a system in terms of controlled vocabularies,...

 reasoning, as well as the more standard terminological TBox
Tbox
In Computer Science, a TBox is a "terminological component"—a conceptualization associated with a set of facts, known as an ABox.The terms ABox and TBox are used to describe two different types of statements in ontologies. TBox statements describe a conceptualization, a set of concepts and...

reasoning.

Further reading

  • P. Blackburn. 2000. Representation, reasoning and relational structures: a hybrid logic manifesto. Logic Journal of the IGPL, 8(3):339-365.

External links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK