A proof that P(L) is true for each base case and a proof that if P(L) is true for some list L, and if L satisfies the inductive case, then P(M) must also be true. Structural induction is a proof method used in mathematical logic, computer science, graph theory, and other fields to prove propositions about recursively defined structures. It involves defining a well-founded partial order on the structures and proving the proposition holds for all minimal structures and that if it holds for the immediate substructures of a certain structure S, then it must hold for S as well. Structural recursion is a related method used to define recursive functions.
University of Washington
Autumn 2021
CSE 311 introduces theoretical computer science, the theory background necessary for other CSE courses, and how to construct rigorous, formal arguments. Topics include logic, set theory, modular arithmetic, induction, regular expression, and relations.
No concepts data
+ 33 more concepts