S5 (modal logic)

S5 (modal logic)

In logic and philosophy, S5 is one of five systems of modal logic proposed by
Clarence Irving Lewis and Cooper Harold Langford in their 1932 book "Symbolic Logic". It is a normal modal logic, and one of the oldest systems of modal logic of any kind.

Axiomatics

S5 is characterized by the axioms:
*K: Box(A o B) o(Box A oBox B);
*T: Box A o A,

and either:

* 5: Diamond A o BoxDiamond A;
* or both of the following::* 4: Box A oBoxBox A, and:* B: A oBoxDiamond A.

Kripke semantics

In terms of Kripke semantics, S5 is characterized by models where the accessibility relation is an equivalence relation: it is reflexive, transitive, and symmetric. Alternatively, the accessibility relation is "universal", that is, every world is accessible from any other.

Determining the satisfiability of an S5 formula is an NP-complete problem. The hardness proof is trivial, as S5 includes the propositional logic. Membership is proved by showing that any satisfiable formula has a Kripke model where the number of worlds is at most linear in the size of the formula.

Applications

S5 is useful because it avoids superfluous iteration of qualifiers of different kinds. For example, under S5, if "X" is necessarily, possibly, necessarily possible, then "X" is possible. The unbolded qualifiers are superfluous under S5. Only the final "possible" is important. While this is useful for keeping propositions reasonably short, it also might appear counter-intuitive in that, under S5, if something is possibly necessary, then it is necessary.

ee also

* Modal logic
* Normal modal logic
* Kripke semantics

External links

* http://home.utah.edu/~nahaj/logic/structures/systems/s5.html
* http://www.columbia.edu/~av72/modallogic/LectureNotes/ModalLogic06.pdf


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • 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… …   Wikipedia

  • modal logic — mo dal log ic, n. A system of logic which studies how to combine propositions which include the concepts of necessity, possibility, and obligation. [PJC] …   The Collaborative International Dictionary of English

  • modal logic — Formal systems incorporating modalities such as necessity, possibility, impossibility, contingency, strict implication, and certain other closely related concepts. The most straightforward way of constructing a modal logic is to add to some… …   Universalium

  • modal logic — A logic studying the notions of necessity and possibility. Modal logic was of great importance historically, particularly in the light of various doctrines concerning the necessary properties of the deity, but was not a central topic of modern… …   Philosophy dictionary

  • Epistemic modal logic — is a subfield of modal logic that is concerned with reasoning about knowledge. While epistemology has a long philosophical tradition dating back to Ancient Greece, epistemic logic is a much more recent development with applications in many fields …   Wikipedia

  • Classical modal logic — In modal logic, a classical modal logic L is any modal logic containing (as axiom or theorem) the duality of the modal operators which is also closed under the rule Alternatively one can give a dual definition of L by which L is classical iff it… …   Wikipedia

  • Regular modal logic — In modal logic, a regular modal logic L is a modal logic closed underDiamond A equiv lnotBoxlnot Aand the rule(Aland B) o C vdash (Box AlandBox B) oBox C.Every regular modal logic is classical, and every normal modal logic is regular and hence… …   Wikipedia

  • Normal modal logic — In logic, a normal modal logic is a set L of modal formulas such that L contains: All propositional tautologies; All instances of the Kripke schema: and it is closed under: Detachment rule (Modus Ponens): ; Necessitation rule: implies . The… …   Wikipedia

  • modal logic — noun 1. the logical study of necessity and possibility • Hypernyms: ↑logic 2. a system of logic whose formal properties resemble certain moral and epistemological concepts • Hypernyms: ↑symbolic logic, ↑mathematical logic, ↑formal logic • …   Useful english dictionary

  • modal logic — noun Any formal system that attempts to deal with modalities, such as possibility and necessity, but also obligation and permission. See Also: deontic logic, doxastic logic, epistemic logic …   Wiktionary

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”