David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Ezio Di Nucci
Jack Alan Reynolds
Learn more about PhilPapers
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)|
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
Michael R. Garey & David S. Johnson (1983). Computers and Intractability. A Guide to the Theory of NP-Completeness. Journal of Symbolic Logic 48 (2):498-500.
Jaakko Hintikka (1996). The Principles of Mathematics Revisited. Cambridge University Press.
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.
A. Blass & Y. Gurevich (1986). Henkin Quantifiers and Complete Problems. Annals of Pure and Applied Logic 32 (1):1--16.
Citations of this work BETA
No citations found.
Similar books and articles
Valery Plisko (2009). A Survey of Propositional Realizability Logic. Bulletin of Symbolic Logic 15 (1):1-42.
George Bealer (1989). On the Identification of Properties and Propositional Functions. Linguistics and Philosophy 12 (1):1 - 14.
Alexander Bochman & Dov M. Gabbay (2012). Sequential Dynamic Logic. Journal of Logic, Language and Information 21 (3):279-298.
A. D. Yashin (1999). Irreflexive Modality in the Intuitionistic Propositional Logic and Novikov Completeness. Journal of Philosophical Logic 28 (2):175-197.
Alexander S. Karpenko (2000). The Classification of Propositional Calculi. Studia Logica 66 (2):253-271.
Kevin C. Klement, Propositional Logic. Internet Encyclopedia of Philosophy.
Leon Horsten & Philip Welch (2007). The Undecidability of Propositional Adaptive Logic. Synthese 158 (1):41 - 60.
Nathan Segerlind (2007). The Complexity of Propositional Proofs. Bulletin of Symbolic Logic 13 (4):417-481.
Jan Krajíček (1995). Bounded Arithmetic, Propositional Logic, and Complexity Theory. Cambridge University Press.
Added to index2009-01-28
Total downloads13 ( #272,650 of 1,907,520 )
Recent downloads (6 months)3 ( #274,312 of 1,907,520 )
How can I increase my downloads?