Redundant proof

In mathematical logic, a redundant proof is a proof that has a subset that is a shorter proof of the same result. That is, a proof ${\displaystyle \psi }$ of ${\displaystyle \kappa }$ is considered redundant if there exists another proof ${\displaystyle \psi ^{\prime }}$ of ${\displaystyle \kappa ^{\prime }}$ such that ${\displaystyle \kappa ^{\prime }\subseteq \kappa }$ (i.e. ${\displaystyle \kappa ^{\prime }\;{\text{subsumes}}\;\kappa }$) and ${\displaystyle |\psi ^{\prime }|<|\psi |}$ where ${\displaystyle |\varphi |}$ is the number of nodes in ${\displaystyle \varphi }$.[1]

Local redundancy

A proof containing a subproof of the shapes (here omitted pivots indicate that the resolvents must be uniquely defined)

${\displaystyle (\eta \odot \eta _{1})\odot (\eta \odot \eta _{2}){\text{ or }}\eta \odot (\eta _{1}\odot (\eta \odot \eta _{2}))}$

is locally redundant.

Indeed, both of these subproofs can be equivalently replaced by the shorter subproof ${\displaystyle \eta \odot (\eta _{1}\odot \eta _{2})}$. In the case of local redundancy, the pairs of redundant inferences having the same pivot occur close to each other in the proof. However, redundant inferences can also occur far apart in the proof.

The following definition generalizes local redundancy by considering inferences with the same pivot that occur within different contexts. We write ${\displaystyle \psi \left[\eta \right]}$ to denote a proof-context ${\displaystyle \psi \left[-\right]}$ with a single placeholder replaced by the subproof ${\displaystyle \eta }$.

Global redundancy

A proof

${\displaystyle \psi [\psi _{1}[\eta \odot _{p}\eta _{1}]\odot \psi _{2}[\eta \odot _{p}\eta _{2}]]{\text{ or }}\psi [\psi _{1}[\eta \odot _{p}(\eta _{1}\odot \psi _{2}[\eta \odot _{p}\eta _{2}])]]}$

is potentially (globally) redundant. Furthermore, it is (globally) redundant if it can be rewritten to one of the following shorter proofs:

${\displaystyle \psi [\eta \odot _{p}(\psi _{1}[\eta _{1}]\odot \psi _{2}[\eta _{2}])]{\text{ or }}\eta \odot _{p}\psi [\psi _{1}[\eta _{1}]\odot \psi _{2}[\eta _{2}]]{\text{ or }}\psi [\psi _{1}[\eta _{1}]\odot \psi _{2}[\eta _{2}]].}$

Example

The proof

${\displaystyle {\cfrac {{\cfrac {{\cfrac {\eta$ :\,p,q\,\,\,\,\eta _{1}:\,\neg p,r}{q,r}}p\,\,\,\,\,\,{\begin{array}{c}\\\eta _{3}:\,\neg q\end{array}}}{r}}q\,\,\,\,\,\,\,\,\,\,\,\,\,{\cfrac {{\cfrac {\eta \,\,\,\,\,\,\,\,\,\,\,\,\,\eta _{2}:\,\neg p,s,\neg r}{q,s,\neg r}}p\,\,\,\,{\begin{array}{c}\\\eta _{3}\end{array}}}{s,\neg r}}q}{\psi :\,s}}r}

is locally redundant as it is an instance of the first pattern in the definition ${\displaystyle ((\eta \odot _{p}\eta _{1})\odot \eta _{3})\odot ((\eta \odot _{p}\eta _{2})\odot \eta _{3}).}$

• The pattern is ${\displaystyle \psi [\psi _{1}[\eta \odot _{p}\eta _{1}]\odot \psi _{2}[\eta \odot _{p}\eta _{2}]]}$
• ${\displaystyle \psi _{1}[-]=\psi _{2}[-]=\_\odot \eta _{3}{\text{ and }}\psi [-]=\_}$

But it is not globally redundant because the replacement terms according to the definition contain ${\displaystyle \psi _{1}[\eta _{1}]\odot \psi _{2}[\eta _{2}]}$ in all the cases and ${\displaystyle \psi _{1}[\eta _{1}]\odot \psi _{2}[\eta _{2}]=(\eta _{1}\odot \eta _{3})\odot (\eta _{2}\odot \eta _{3})}$ does not correspond to a proof. In particular, neither ${\displaystyle \eta _{1}}$ nor ${\displaystyle \eta _{2}}$ can be resolved with ${\displaystyle \eta _{3}}$, as they do not contain the literal ${\displaystyle q}$.

The second pattern of potentially globally redundant proofs appearing in global redundancy definition is related to the well-known notion of regularity. Informally, a proof is irregular if there is a path from a node to the root of the proof such that a literal is used more than once as a pivot in this path.

Notes

1. Fontaine, Pascal; Merz, Stephan; Woltzenlogel Paleo, Bruno. Compression of Propositional Resolution Proofs via Partial Regularization. 23rd International Conference on Automated Deduction, 2011.