Decidability of Fluted Logic with Identity

Notre Dame Journal of Formal Logic 37 (1):84-104 (1996)
  Copy   BIBTEX

Abstract

Fluted logic is the restriction of pure predicate logic to formulas in which variables play no essential role. Although fluted logic is significantly weaker than pure predicate logic, it is of interest because it seems closely to parallel natural logic, the logic that is conducted in natural language. It has been known since 1969 that if conjunction in fluted formulas is restricted to subformulas of equal arity, satisfiability is decidable. However, the decidability of sublogics lying between this restricted (homogeneous) fluted logic and full predicate logic remained unknown. In 1994 it was shown that the satisfiability of fluted formulas without restriction is decidable, thus reducing the unknown region significantly. This paper further reduces the unknown region. It shows that fluted logic with the logical identity is decidable. Since the reflection functor can be defined in fluted logic with identity, it follows that fluted logic with the reflection functor also lies within the region of decidability. Relevance to natural logic is increased since the identity permits definition of singular predicates, which can represent anaphoric pronouns

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,252

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Complexity and nicety of fluted logic.William C. Purdy - 2002 - Studia Logica 71 (2):177 - 198.
Fluted formulas and the limits of decidability.William C. Purdy - 1996 - Journal of Symbolic Logic 61 (2):608-620.
Decidability and generalized quantifiers.Andreas Baudisch (ed.) - 1980 - Berlin: Akademie Verlag.
Issues of decidability and tractability.Witold Marciszewski (ed.) - 2006 - Białystok: University of Białystok.
Axiomatisation and decidability off andp in cyclical time.Mark Reynolds - 1994 - Journal of Philosophical Logic 23 (2):197 - 224.
Identity, Structure and Logic.Jean-Yves Beziau - 1996 - Bulletin of the Section of Logic 25:89-9.
Decidability of independence-friendly modal logic.Merlijn Sevenster - 2010 - Review of Symbolic Logic 3 (3):415-441.
Predicate-functors and the limits of decidability in logic.Aris Noah - 1980 - Notre Dame Journal of Formal Logic 21 (4):701-707.
The strong decidability of cut logics. II. Generalizations.E. William Chapin - 1971 - Notre Dame Journal of Formal Logic 12 (4):429-434.
Relevant identity.Philip Kremer - 1999 - Journal of Philosophical Logic 28 (2):199-222.

Analytics

Added to PP
2010-08-24

Downloads
21 (#700,240)

6 months
5 (#565,734)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Quine's 'limits of decision'.William C. Purdy - 1999 - Journal of Symbolic Logic 64 (4):1439-1466.

Add more citations

References found in this work

Variables Explained Away.Willard V. Quine - 1960 - Journal of Symbolic Logic 32 (1):112-112.
Predicate functors revisited.W. V. Quine - 1981 - Journal of Symbolic Logic 46 (3):649-652.
Predicate-functors and the limits of decidability in logic.Aris Noah - 1980 - Notre Dame Journal of Formal Logic 21 (4):701-707.
Fluted formulas and the limits of decidability.William C. Purdy - 1996 - Journal of Symbolic Logic 61 (2):608-620.

Add more references