CS Paper Radar

Natural Deduction Derivations as Directed Acyclic Proof Graphs

Jonathan Chan, Aaron Stump

cs.LO ·submitted 2026-10-19 19:31 UTC · v1

Abstract

In conventional natural deduction, a proof of a proposition is a derivation tree constructed out of inference rules with some number of premises and a conclusion judgement. For propositional logic, in contrast to the other connectives, the rule for disjunction elimination of $A \vee B$ involves concluding with an auxiliary formula C from $A \vdash C$ and $B \vdash C$. Not only is this asymmetry unsightly, it also introduces the need for commuting conversions across disjunction eliminations to transform between proof derivations that are morally equivalent but not $βη$-equivalent. To resolve the asymmetry, Jean-Yves Girard suggests a disjunction elimination rule with multiple conclusions A and B, but claims that "we have no way of bringing them back together". In this work, we pursue Girard's proposal using the key insight that proof derivations need not be trees, but may be directed acyclic graphs (DAGs) in general. Derivation rules are represented as nodes, premises as incoming edges, and conclusions as outgoing edges. Treating derivations as DAGs permits using the alternate rule by ensuring that the subderivations pointed at by each conclusion eventually join up at a new concluding node. Commuting conversions can then be formulated in terms of interactions with this join node. We explore ways to design a proof graph language with reduction and commutation rules such that proof simplification retains its concluding judgements, i.e. type preservation. In particular, we examine two styles of reduction rules: a local style, which only requires looking at the relevant subgraph of a whole proof but necessitates a number of extraneous constructs to satisfy type preservation; and a global style, which doesn't require all the extraneous constructs but necessitates looking at the entire proof graph as a whole.

Closest papers

Nearest neighbours by meaning across the whole index.

A Fibrational Framework For Multi-Conclusion Logics

cs.LO math.LO ·2026-10-27 ·Oualid Merzouga
theory similarity 0.63
Abstract

The fibrational framework of Licata, Shulman, and Riley gives a uniform account of substructural and modal logics for single-conclusion judgments. This thesis extends it to a multiple-output setting in which cartesian resources may be used freely, while linear resources occur exactly once on either side of the turnstile. Judgments are indexed by descriptors: directed acyclic graphs generalizing the tree-shaped expressions of the original framework. Descriptor $2$-cells encode structural transformations, and explicit gates provide weakening, contraction, coweakening, and cocontraction at linear modes. We define a sequent calculus generated by two connectives, $F$ and $U$. We prove identity, invertibility, and cut admissibility. The mode and type theories present linear-non-linear $2$-polycategories, and the projection is a local discrete fibration and a fibration, with opcartesian lifts for one-output base morphisms. Two adequacy results validate the framework: its cartesian fragment recovers the Licata--Shulman--Riley calculus, and its purely linear fragment presents classical multiplicative linear logic. Finally, we relate indexed and fibrational semantics. After developing representability correspondences for multicategories and polycategories, we establish an equivalence between multi-indexed categories over a fixed representable base and multicategorical opfibrations over it, together with its biclosed bifibrational version. We also give a one-way construction from planar poly-indexed data to a planar polycategory.

0.33

The Proof-Theoretic Foundations of the Principle of Reiteration in Natural Deduction

cs.LO ·2026-10-26 ·Khashayar Irani
similarity 0.62
Abstract · 14 Pages

This paper investigates the proof-theoretic foundations of the principle of reiteration (R) in natural deduction, arguing that its legitimacy originates in the structural preservation of formulae within sequent calculus rather than in an independent logical rule. By examining singlesuccedent and multisuccedent sequent calculus, we demonstrate how logical operations transform principal formulae while preserving unaffected antecedent and succedent contexts. We subsequently analyse the schematic formulation of reiteration and compare natural deduction derivations with corresponding sequent calculus derivations. This comparison identifies two fundamental functions of reiteration, namely the reuse of previously employed formulae and the restoration of previously derived conclusions. We conclude that reiteration introduces no independent inferential content but explicitly represents the structural continuity of inferential dependencies already included into sequent calculus.

0.26

New Proofs of Weak Normalization for Propositional Logic

cs.LO ·2026-09-13 ·S P Suresh
similarity 0.62
Abstract

We present new proofs of weak normalization for intuitionistic and classical propositional logics (with the full set of operators -- falsum, implication, conjunction and disjunction). These proofs work with cuts rather than cut segments, and they provide explicit ``local'' rules for determining whether to contract a whole proof or reduce one of its subproofs, and in the latter case, which subproof to reduce. Interestingly, much of the complication in the case of intuitionistic logic is due to the disjunction elimination rule, while our version of the same rule for classical logic has falsum as conclusion always, and so is much easier to handle. All the complication in the case of classical logic shifts to cuts involving the reductio ad absurdum rule. We also discuss a formalization of the entire proof in Lean, and present a deterministic algorithm for weak normalization.

0.20

The Nonlocal Nature of Natural Deduction & the Introduction of Assumptions in Derivations

cs.LO ·2026-10-12 ·Khashayar Irani
unusual similarity 0.60
Abstract · 9 Pages

This concise manuscript investigates the nonlocal nature of natural deduction, particularly the possibility of introducing assumptions at intermediate stages of a derivation after those stages have already been passed. By examining the structural correspondence between natural deduction and sequent calculus, we demonstrate how the structural rule of left-weakening (LW) permits the enlargement of an antecedent after its corresponding succedent has been derived, without modifying the original inference. Through a number of symmetrical derivations, we establish the proof-theoretic relationship between the introduction of assumptions in natural deduction and antecedent expansion in sequent calculus. On this basis, we formulate the principle of Nonlocal Assumption Introduction (NAI), according to which assumptions may be introduced at any intermediate stage prior to the final conclusion, provided that the corresponding structural expansion is proof-theoretically valid. We further specify the conditions governing this operation, including the preservation of inferential validity, assumption dependencies, and the scope and discharge requirements of the resulting derivation.

0.27

A Counterexample to KL1 Completeness and a Complete Disjunctive Calculus

cs.LO ·2026-10-27 ·Damiano Presa, Fabio Aurelio D'Asaro, Massimiliano Badino
theory similarity 0.60
Abstract

The logic KL$_1$ of Evans, Sergot and Stephenson formalizes Kant's rules as conditional imperatives $B \square\to C$ and permissives $B \diamond\to C$ over acts. Its consequence relation is operational: a rule follows from a set of rules when adjoining it leaves the set of outcomes unchanged for every input. The authors proved their calculus sound and conjectured that it is complete. We show that the conjecture fails: for distinct atoms $b,c,d$ the rules $\top \diamond\to b \lor d$, $b \diamond\to c$, $d \diamond\to c$ and $c \square\to b \lor d$ entail $\top \diamond\to c$, which is not derivable. Non-derivability is proved by an invariant that holds at every derivation depth and for arbitrary intermediate atoms. The obstruction is the side condition of may-trans, which requires each new act to bring with it a single intermediary act. Replacing it by a disjunctive side condition yields may-trans-disj, a strict generalization from which the original rule is derivable. Using a local characterization of entailment, we prove the repaired calculus sound for arbitrary sets of rules and complete for finite ones, and we show that, with finite inputs, completeness cannot be extended to infinite sets. The main results on KL$_1$ are formalized in Agda. For KL$_2$ we observe that the published reduction to KL$_1$ passes through infinite rule sets; re-establishing the decomposition for finite rule sets, we prove that KL$_2$ with the disjunctive rule is sound and complete for finite sets of rules. We close with remarks on KL$_3$ and on the significance of completeness for the relation between the operational and the inferential questions of Kant's logic.

0.32

Structural Morphisms for Nested Conditions - Full Version

cs.LO ·2026-08-12 ·Arend Rensink, Andrea Corradini
published similarity 0.59
Abstract · This is the full version (including proofs) of the paper published in GCM 2026

Nested conditions are used, among other things, as a graphical way to express first order formulas ruling the applicability of a graph transformation rule to a given match. In this paper, we first introduce several operators on conditions mimicking logical connectives. Next we propose an original notion of structural morphism among nested conditions, and we identify circumstances under which morphisms are consistent with the entailment of the corresponding conditions. Finally we frame the results in a categorical context, proving functoriality and universality properties of the various operations.

0.19

Automated Theorem Generation in First-Order Logic by Construction from Triangular Standard Contradictions

cs.AI ·2026-10-30 ·Yang Xu, Shuwei Chen, Hailin Guo, Jun Liu
theory similarity 0.58
Abstract · 46 pages, 11 figures

Automated theorem generation (ATG) seeks to construct new theorems rather than merely prove given conjectures. Existing approaches typically generate candidate statements that require subsequent proof or formal verification. We propose a constructive framework for ATG in first-order logic based on triangular standard contradictions. The method constructs minimally unsatisfiable clause sets from selected first-order literals, then forms theorems by retaining some clauses as premises and taking the negation of one clause, or a conjunction of clauses, as the conclusion. Minimal unsatisfiability ensures that the remaining premises are satisfiable, avoiding trivial inference by explosion, while unsatisfiability of the full set guarantees the resulting entailment. Theorems are therefore correct by construction, without a separate proof procedure for each instance. Extending the previously developed $Δ_1$ generator, we introduce seven methods, $Δ_2$--$Δ_8$, forming a unified family of eight theorem-generation methods. Four generators, $Δ_1$--$Δ_4$, have been implemented and released. We also formulate a general $Δ$-class method encompassing the family. Combinatorial analysis demonstrates the capacity to generate large numbers of distinct theorems systematically. This framework offers a principled foundation for automated theorem discovery and the construction of logically guaranteed knowledge.

0.28

Apply All, Prove Once: Embedding Parameterized Lemmas in DRAT

cs.LO ·2026-11-17 ·Randal E. Bryant, Zachary Battleman, Marijn J. H. Heule
similarity 0.58
Abstract

The deletion-resolution-asymmetric-tautology (DRAT) proof format is widely used to express unsatisfiability proofs of Boolean formulas. Our DRATL format extends DRAT with parameterized lemmas, allowing a single proof to succinctly capture the common case where multiple instances of a pattern occur in a formula, differing in the identities and phases of the variables. Proofs expressed in DRATL can be hierarchical, with the proof of one lemma containing instantiations of others. Our elaborator program expands a DRATL proof containing multiple, nested lemmas into a standard DRAT proof. Most significantly, the elaboration yields compact proofs, where a single sequencing of the proof steps for each lemma covers all of its instantiations. Several case studies demonstrate that lemmas can provide a powerful method to generate short proofs for challenging problems.

0.21