Abstract
Natural deduction systems were motivated by the desire to define the meaning of each connective by specifying how it is introduced and eliminated from inference. In one sense, this attempt fails, for it is well known that propositional logic rules (however formulated) underdetermine the classical truth tables. Natural deduction rules are too weak to enforce the intended readings of the connectives; they allow non-standard models. Two reactions to this phenomenon appear in the literature. One is to try to restore the standard readings, for example by adopting sequent rules with multiple conclusions. Another is to explore what readings the natural deduction rules do enforce. When the notion of a model of a rule is generalized, it is found that natural deduction rules express “intuitionistic” readings of their connectives. A third approach is presented here. The intuitionistic readings emerge when models of rules are defined globally, but the notion of a local model of a rule is also natural. Using this benchmark, natural deduction rules enforce exactly the classical readings of the connectives, while this is not true of axiomatic systems. This vindicates the historical motivation for natural deduction rules. One odd consequence of using the local model benchmark is that some systems of propositional logic are not complete for the semantics that their rules express. Parallels are drawn with incompleteness results in modal logic to help make sense of this.
Similar content being viewed by others
References
Belnap, N. (1962). Tonk, plonk and plink. Analysis, 22(6), 130–134.
Belnap, N., & Massey, G. (1990). Semantic holism. Studia Logica, 49, 67–82.
Blackburn, P., de Rijke, M., & Venema, Y. (2002). Modal logic. Cambridge: Cambridge University Press.
Boolos, G. (1993). The logic of provability. Cambridge: Cambridge University Press.
Carnap, R. (1943). Formalization of logic. Cambridge: Harvard University Press.
Dummett, M. (1978). The philosophical basis of intuitionistic logic. In M. Dummett (Ed.), Truth and other enigmas (pp. 215–247). Cambridge: Harvard University Press.
Garson, J. (2001). Natural semantics: why natural deduction is intuitionistic. Theoria, 67(2), 114–137.
Hacking, I. (1979). What is logic? Journal of Philosophy, 76, 285–319.
Kracht, M. (2007). Modal consequence relations. In P. Blackburn, J. Van Bentham & F. Wolter (Eds.), Handbook of modal logic (pp. 491–545). Oxford: Oxford University Press.
McCawley, J. (1981). Everything that linguists have always wanted to know about logic. Chicago: University of Chicago Press.
Sahlqvist, H. (1975). Completeness and correspondence in the first and second order semantics for modal logic, in (1973). In S. Kanger (Ed.), Proceedings of the third Scandinavian logic symposium. Amsterdam: North-Holland.
Shoesmith, D. J., & Smiley, T. J. (1978). Multiple-conclusion logic. Cambridge: Cambridge University Press.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Garson, J.W. Expressive Power and Incompleteness of Propositional Logics. J Philos Logic 39, 159–171 (2010). https://doi.org/10.1007/s10992-009-9120-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10992-009-9120-z