/

Theorem Proving with the Real Numbers

Harrison John
Heftet / 2011 / Engelsk

Produktdetaljer

ISBN
9781447115939
Publisert
2011-11-20
Utgiver
Vendor
Springer London Ltd
Høyde
235 mm
Bredde
155 mm
Aldersnivå
Research, P, 06
Språk
Product language
Engelsk
Format
Product format
Heftet

Forfatter
Harrison John

Theorem Proving with the Real Numbers

Harrison John
Heftet / 2011 / Engelsk
Harrison John
Heftet / 2011 / Engelsk
Nettpris:
1.481,-
Laveste pris siste 30 dager: 1.462,-
Levering 10-30 dager
Klikk og hent
This book discusses the use of the real numbers in theorem proving. Typ­ ically, theorem provers only support a few 'discrete' datatypes such as the natural numbers. However the availability of the real numbers opens up many interesting and important application areas, such as the verification of float­ ing point hardware and hybrid systems. It also allows the formalization of many more branches of classical mathematics, which is particularly relevant for attempts to inject more rigour into computer algebra systems. Our work is conducted in a version of the HOL theorem prover. We de­ scribe the rigorous definitional construction of the real numbers, using a new version of Cantor's method, and the formalization of a significant portion of real analysis. We also describe an advanced derived decision procedure for the 'Tarski subset' of real algebra as well as some more modest but practically useful tools for automating explicit calculations and routine linear arithmetic reasoning. Finally, we consider in more detail two interesting application areas. We discuss the desirability of combining the rigour of theorem provers with the power and convenience of computer algebra systems, and explain a method we have used in practice to achieve this. We then move on to the verification of floating point hardware. After a careful discussion of possible correctness specifications, we report on two case studies, one involving a transcendental function.
Les mer
This book discusses the use of the real numbers in theorem proving. We de­ scribe the rigorous definitional construction of the real numbers, using a new version of Cantor's method, and the formalization of a significant portion of real analysis.
Les mer
1. Introduction.- 1.1 Symbolic computation.- 1.2 Verification.- 1.3 Higher order logic.- 1.4 Theorem proving vs. model checking.- 1.5 Automated vs. interactive theorem proving.- 1.6 The real numbers.- 1.7 Concluding remarks.- 2 Constructing the Real Numbers.- 2.1 Properties of the real numbers.- 2.2 Uniqueness of the real numbers.- 2.3 Constructing the real numbers.- 2.4 Positional expansions.- 2.5 Cantor’s method.- 2.6 Dedekind’s method.- 2.7 What choice?.- 2.8 Lemmas about nearly-multiplicative functions.- 2.9 Details of the construction.- 2.10 Adding negative numbers.- 2.11 Handling equivalence classes.- 2.12 Summary and related work.- 3. Formalized Analysis.- 3.1 The rigorization and formalization of analysis.- 3.2 Some general theories.- 3.3 Sequences and series.- 3.4 Limits, continuity and differentiation.- 3.5 Power series and the transcendental functions.- 3.6 Integration.- 3.7 Summary and related work.- 4. Explicit Calculations.- 4.1 The need for calculation.- 4.2 Calculation with natural numbers.- 4.3 Calculation with integers.- 4.4 Calculation with rationals.- 4.5 Calculation with reals.- 4.6 Summary and related work.- 5. A Decision Procedure for Real Algebra.- 5.1 History and theory.- 5.2 Real closed fields.- 5.3 Abstract description of the algorithm.- 5.4 The HOL Implementation.- 5.5 Optimizing the linear case.- 5.6 Results.- 5.7 Summary and related work.- 6. Computer Algebra Systems.- 6.1 Theorem provers vs. computer algebra systems.- 6.2 Finding and checking.- 6.3 Combining systems.- 6.4 Applications.- 6.5 Summary and related work.- 7. Floating Point Verification.- 7.1 Motivation.- 7.2 Floating point error analysis.- 7.3 Specifying floating point operations.- 7.4 Idealized integer and floating point operations.- 7.5 A square root algorithm.- 7.6 ACORDIC natural logarithm algorithm.- 7.7 Summary and related work.- 8. Conclusions.- 8.1 Mathematical contributions.- 8.2 The formalization of mathematics.- 8.3 The LCF approach to theorem proving.- 8.4 Computer algebra systems.- 8.5 Verification applications.- 8.6 Concluding remarks.- A. Logical foundations of HOL.- B. Recent developments.
Les mer
Springer Book Archives
Springer Book Archives
Formal development of classical mathematics using a computer * Combines traditional lines of research in theorem proving and computer algebra * Shows usefulness of real numbers in verification

Relaterte produkter

This book discusses the use of the real numbers in theorem proving. Typ­ ically, theorem provers only support a few 'discrete' datatypes such as the natural numbers. However the availability of the real numbers opens up many interesting and important application areas, such as the verification of float­ ing point hardware and hybrid systems. It also allows the formalization of many more branches of classical mathematics, which is particularly relevant for attempts to inject more rigour into computer algebra systems. Our work is conducted in a version of the HOL theorem prover. We de­ scribe the rigorous definitional construction of the real numbers, using a new version of Cantor's method, and the formalization of a significant portion of real analysis. We also describe an advanced derived decision procedure for the 'Tarski subset' of real algebra as well as some more modest but practically useful tools for automating explicit calculations and routine linear arithmetic reasoning. Finally, we consider in more detail two interesting application areas. We discuss the desirability of combining the rigour of theorem provers with the power and convenience of computer algebra systems, and explain a method we have used in practice to achieve this. We then move on to the verification of floating point hardware. After a careful discussion of possible correctness specifications, we report on two case studies, one involving a transcendental function.
Les mer
This book discusses the use of the real numbers in theorem proving. We de­ scribe the rigorous definitional construction of the real numbers, using a new version of Cantor's method, and the formalization of a significant portion of real analysis.
Les mer
1. Introduction.- 1.1 Symbolic computation.- 1.2 Verification.- 1.3 Higher order logic.- 1.4 Theorem proving vs. model checking.- 1.5 Automated vs. interactive theorem proving.- 1.6 The real numbers.- 1.7 Concluding remarks.- 2 Constructing the Real Numbers.- 2.1 Properties of the real numbers.- 2.2 Uniqueness of the real numbers.- 2.3 Constructing the real numbers.- 2.4 Positional expansions.- 2.5 Cantor’s method.- 2.6 Dedekind’s method.- 2.7 What choice?.- 2.8 Lemmas about nearly-multiplicative functions.- 2.9 Details of the construction.- 2.10 Adding negative numbers.- 2.11 Handling equivalence classes.- 2.12 Summary and related work.- 3. Formalized Analysis.- 3.1 The rigorization and formalization of analysis.- 3.2 Some general theories.- 3.3 Sequences and series.- 3.4 Limits, continuity and differentiation.- 3.5 Power series and the transcendental functions.- 3.6 Integration.- 3.7 Summary and related work.- 4. Explicit Calculations.- 4.1 The need for calculation.- 4.2 Calculation with natural numbers.- 4.3 Calculation with integers.- 4.4 Calculation with rationals.- 4.5 Calculation with reals.- 4.6 Summary and related work.- 5. A Decision Procedure for Real Algebra.- 5.1 History and theory.- 5.2 Real closed fields.- 5.3 Abstract description of the algorithm.- 5.4 The HOL Implementation.- 5.5 Optimizing the linear case.- 5.6 Results.- 5.7 Summary and related work.- 6. Computer Algebra Systems.- 6.1 Theorem provers vs. computer algebra systems.- 6.2 Finding and checking.- 6.3 Combining systems.- 6.4 Applications.- 6.5 Summary and related work.- 7. Floating Point Verification.- 7.1 Motivation.- 7.2 Floating point error analysis.- 7.3 Specifying floating point operations.- 7.4 Idealized integer and floating point operations.- 7.5 A square root algorithm.- 7.6 ACORDIC natural logarithm algorithm.- 7.7 Summary and related work.- 8. Conclusions.- 8.1 Mathematical contributions.- 8.2 The formalization of mathematics.- 8.3 The LCF approach to theorem proving.- 8.4 Computer algebra systems.- 8.5 Verification applications.- 8.6 Concluding remarks.- A. Logical foundations of HOL.- B. Recent developments.
Les mer
Springer Book Archives
Springer Book Archives
Formal development of classical mathematics using a computer * Combines traditional lines of research in theorem proving and computer algebra * Shows usefulness of real numbers in verification

Produktdetaljer

ISBN
9781447115939
Publisert
2011-11-20
Utgiver
Vendor
Springer London Ltd
Høyde
235 mm
Bredde
155 mm
Aldersnivå
Research, P, 06
Språk
Product language
Engelsk
Format
Product format
Heftet

Forfatter
Harrison John

Relaterte produkter