Tactics From Proofs

Gurukumba, Tawanda (2007). Tactics From Proofs. MPhil thesis The Open University.

DOI: https://doi.org/10.21954/ou.ro.0000fd50

Abstract

Proof guarantees the correctness of a formal specification with respect to formal requirements, and of an implementation with respect to a specification, and so provides valuable verification methods in high integrity system development. However, proof development by hand tends to be an erudite, error-prone and seemingly interminable task.

Tactics are programs that drive theorem-provers, thus automating proof development and alleviating some of the problems mentioned above. The development of tactics for a particular application domain also extends the domain of application of the theorem-prover. A LCF-tactic is safe in that if it fails to be applicable to a particular conjecture, then it will not produce an incorrect proof.

The current construction of tactics from proofs does not yield sufficiently robust tactics. Proofs tend to be specific to the details of a specification and so are not reusable in general, e.g. the same proof may not work when the definition of a conjecture is changed. The major challenges in proof development are deciding which proof rule and instantiations to apply in order to prove a conjecture.

Discerning patterns in formal interactive proof development facilitates the construction of robust tactics that can withstand definitional changes in conjectures. Having developed an interactive proof for a conjecture, we develop the necessary abstractions of the proof steps used, to construct a tactic th at can be applicable to other conjectures in that domain. By so doing we encode human expertise used in the proof development, and make proofs robust and thus generally reusable.

We apply our theory on the proofs of conjectures involving some set theory operators, and on the proof obligations that arise in the formal development of numerical specifications using the retrenchment method under the IEEE-854 floating-point standard in the PVS theorem-prover/proof-checker.

Viewing alternatives

Download history

Metrics

Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions

Item Actions

Export

About

Recommendations