On the computational consequences of independence in propositional logic

Synthese 149 (2):257 - 283 (2006)
Sandu and Pietarinen [Partiality and Games: Propositional Logic. Logic J. IGPL 9 (2001) 101] study independence friendly propositional logics. That is, traditional propositional logic extended by means of syntax that allow connectives to be independent of each other, although the one may be subordinate to the other. Sandu and Pietarinen observe that the IF propositional logics have exotic properties, like functional completeness for three-valued functions. In this paper we focus on one of their IF propositional logics and study its properties, by means of notions from computational complexity. This approach enables us to compare propositional logic before and after the IF make-over. We observe that all but one of the best-known decision problems experience a complexity jump, provided that the complexity classes at hand are not equal. Our results concern every discipline that incorporates some notion of independence such as computer science, natural language semantics, and game theory. A corollary of one of our theorems illustrates this claim with respect to the latter discipline.
Keywords Philosophy   Philosophy   Epistemology   Logic   Metaphysics   Philosophy of Language
Categories (categorize this paper)
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
Download options
PhilPapers Archive

Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 23,217
External links
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
References found in this work BETA
Wilfrid Hodges (2001). Formal Features of Compositionality. Journal of Logic, Language and Information 10 (1):7-28.
Jon Barwise (1979). On Branching Quantifiers in English. Journal of Philosophical Logic 8 (1):47 - 80.

View all 9 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Monthly downloads

Added to index


Total downloads

26 ( #182,739 of 1,932,483 )

Recent downloads (6 months)

13 ( #66,441 of 1,932,483 )

How can I increase my downloads?

My notes
Sign in to use this feature

Start a new thread
There  are no threads in this forum
Nothing in this forum yet.