Improving legibility of natural deduction proofs is not trivial. (English) Zbl 1341.68196

Summary: In formal proof checking environments such as Mizar it is not merely the validity of mathematical formulas that is evaluated in the process of adoption to the body of accepted formalizations, but also the readability of the proofs that witness validity. As in case of computer programs, such proof scripts may sometimes be more and sometimes be less readable. To better understand the notion of readability of formal proofs, and to assess and improve their readability, we propose in this paper a method of improving proof readability based on Behaghel’s First Law of sentence structure. Our method maximizes the number of local references to the directly preceding statement in a proof linearisation. It is shown that our optimization method is NP-complete.


68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
00A35 Methodology of mathematics
03B35 Mechanization of proofs and logical operations
03F07 Structure of proofs
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI arXiv