Some Formal Considerations on Gabbay's Restart Rule in Natural Deduction and Goal-Directed Reasoning
| Abstract | In this paper we make some observations about Natural Deduction derivations [Prawitz, 1965, van Dalen, 1986, Bell and Machover, 1977]. We assume the reader is familiar with it and with proof-theory in general. Our development will be simple, even simple-minded, and concrete. However, it will also be evident that general ideas motivate our examples, and we think both our specific examples and the ideas behind them are interesting and may be useful to some readers. In a sentence, the bare technical content of this paper is: Extending natural deduction with global well-formedness conditions can neatly and cheaply capture classical and intermediate logics. The interest here is in the ‘neatly’ and ‘cheaply’. By ‘neatly’ we mean ‘preserving proof-normalisation’,1 and ‘maintaining the subformula property’, and by ‘cheaply’ we mean ‘preserving the formal structure of deductions’ (so that a deduction in the original system is still, formally, a deduction in the extended system, and in particular it requires no extra effort to write just because it is in the extended system). To illustrate what we have in mind consider intuitionistic first-order logic (FOL) [van Dalen, 1986] as a paradigmatic example of a formal notion of deduction. A natural deduction derivation (or deduction) is an inductively defined tree structure where each node contains an instance of a formula. A deduction is valid when each successive node follows from its predecessors in accordance with some predetermined inference rules. A particular attraction of Natural Deduction is its clean and economical presentation. Here for example are deduction (fragments) proving A ∧ B from A and B, and ∀x. (P (x) ∧ Q(x)) from ∀x. P (x) and ∀x. Q(x): ∀x. P (x) (∀E) | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | No categories specified (fix it) | |||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,679 |
| External links | This entry has no external links. Add one. |
| Through your library | Only published papers are available at libraries |
Similar books and articlesMichael Barker (2001). The Proof Structure of Kant's a-Deduction. Kant-Studien 92 (3):259-282.
Torben BraÜner (2005). Natural Deduction for First-Order Hybrid Logic. Journal of Logic, Language and Information 14 (2).
Francis Jeffry Pelletier (1999). A Brief History of Natural Deduction. History and Philosophy of Logic 20 (1):1-31.
Sara Negri & Jan von Plato (2001). Sequent Calculus in Natural Deduction Style. Journal of Symbolic Logic 66 (4):1803-1816.
Hartley Slater (2008). Harmonising Natural Deduction. Synthese 163 (2):187 - 198.
Yannis Delmas-Rigoutsos (1997). A Double Deduction System for Quantum Logic Based on Natural Deduction. Journal of Philosophical Logic 26 (1):57-67.
Maria Luisa Bonet & Samuel R. Buss (1993). The Deduction Rule and Linear and Near-Linear Proof Simulations. Journal of Symbolic Logic 58 (2):688-709.
Dov M. Gabbay & Nicola Olivetti (1998). Algorithmic Proof Methods and Cut Elimination for Implicational Logics Part I: Modal Implication. Studia Logica 61 (2):237-280.
Allard Tamminga & Koji Tanaka (1999). A Natural Deduction System for First Degree Entailment. Notre Dame Journal of Formal Logic 40 (2):258-272.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-02-15Total downloads8 ( #123,092 of 549,087 )Recent downloads (6 months)1 ( #63,317 of 549,087 )How can I increase my downloads? |
My notes
Discussion
