Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
Induction
Erschienen in: The Calculus of Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
This chapter discusses
induction
, a classic proof technique for proving first-order theorems with universal quantifiers. Section 4.1 begins with
stepwise induction
, which may be familiar to the reader from earlier education. Section 4.2 then introduces
complete induction
in the context of arithmetic. Complete induction is theoretically equivalent in power to stepwise induction but sometimes produces more concise proofs. Section 4.3 generalizes complete induction to
well-founded induction
in the context of arithmetic and recursive data structures. Finally, Section 4.4 covers a form of well-founded induction over logical formulae called
structural induction
. It is useful for reasoning about correctness of decision procedures and properties of logical theories and their interpretations.