Synthese 149 (2):257 - 283 (2006)
|Abstract||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||No keywords specified (fix it)|
No categories specified
(categorize this paper)
|Through your library||Configure|
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 downloads3 ( #213,250 of 722,774 )
Recent downloads (6 months)0
How can I increase my downloads?