scientific article; zbMATH DE number 1302506
Familiar conversion (cut-elimination) rules for natural deduction are asymmetric: very simple for some connectives (like \(\&\) and \(\forall)\) and more complicated for others (like \(\vee)\). This makes normalization proofs look unbalanced: \(\&,\forall\)-cases of inductive proofs of lemmata are simple, \(\to\)-cases more complicated and \(\vee\)-cases are much more complicated, since they have to deal with permutative conversions. The author proposes changing elimination rules for all connectives to make all of them similar to standard \(\vee\)-elimination. For example \(\to\)-elimination becomes (when \(\vdash\) divides undischarged assumptions from the goal): \[ {\Gamma\vdash A\to B;\;\Delta\vdash A;\;B,\Sigma\vdash C\over\Gamma,\Delta,\Sigma\vdash C}. \] The list of reductions for the resulting system includes a lot of additional (compared to standard proof) permutative conversions corresponding to new kinds of ``segments introduced in this way. After this a long normalization proof (looking similar enough to Prawitz' original proof) for the \((\neg,\to, \vee)\)-fragment of intuitionistic and classical logic is presented. For the entire collection see [Zbl 0905.00049].
- Commuting conversions vs. the standard conversions of the ``good connectives
- Natural deduction with general elimination rules
- Proof theory for heterogeneous logic combining formulas and diagrams: proof normalization
- Normal proofs, cut free derivations and structural rules
- The calculus of higher-level rules, propositional quantification, and the foundational approach to proof-theoretic harmony
- Continuing Variations on a System of Gentzen
- Cut elimination and normalization for generalized single and multi-conclusion sequent and natural deduction calculi
- Prawitz, Proofs, and Meaning
- Meaning in use
- Generalized Elimination Inferences, Higher-Level Rules, and the Implications-as-Rules Interpretation of the Sequent Calculus
- A new connective in natural deduction, and its application to quantum computing
- Proof Terms for Generalized Natural Deduction
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4249036)