Natural Deduction Derivations as Directed Acyclic Proof Graphs

Overview & Synopsis

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.