src/Doc/Prog_Prove/Bool_nat_list.thy
changeset 58504 5f88c142676d
parent 57805 eea1e7cb4262
child 58521 b70e93c05efe
equal deleted inserted replaced
58503:ea22f2380871 58504:5f88c142676d
   167 Hence all lists are of the form @{const Nil}, or @{term"Cons x Nil"},
   167 Hence all lists are of the form @{const Nil}, or @{term"Cons x Nil"},
   168 or @{term"Cons x (Cons y Nil)"}, etc.
   168 or @{term"Cons x (Cons y Nil)"}, etc.
   169 \item \isacom{datatype} requires no quotation marks on the
   169 \item \isacom{datatype} requires no quotation marks on the
   170 left-hand side, but on the right-hand side each of the argument
   170 left-hand side, but on the right-hand side each of the argument
   171 types of a constructor needs to be enclosed in quotation marks, unless
   171 types of a constructor needs to be enclosed in quotation marks, unless
   172 it is just an identifier (e.g.\ @{typ nat} or @{typ 'a}).
   172 it is just an identifier (e.g., @{typ nat} or @{typ 'a}).
   173 \end{itemize}
   173 \end{itemize}
   174 We also define two standard functions, append and reverse: *}
   174 We also define two standard functions, append and reverse: *}
   175 
   175 
   176 fun app :: "'a list \<Rightarrow> 'a list \<Rightarrow> 'a list" where
   176 fun app :: "'a list \<Rightarrow> 'a list \<Rightarrow> 'a list" where
   177 "app Nil ys = ys" |
   177 "app Nil ys = ys" |
   219 \subsubsection{Structural Induction for Lists}
   219 \subsubsection{Structural Induction for Lists}
   220 
   220 
   221 Just as for natural numbers, there is a proof principle of induction for
   221 Just as for natural numbers, there is a proof principle of induction for
   222 lists. Induction over a list is essentially induction over the length of
   222 lists. Induction over a list is essentially induction over the length of
   223 the list, although the length remains implicit. To prove that some property
   223 the list, although the length remains implicit. To prove that some property
   224 @{text P} holds for all lists @{text xs}, i.e.\ \mbox{@{prop"P(xs)"}},
   224 @{text P} holds for all lists @{text xs}, i.e., \mbox{@{prop"P(xs)"}},
   225 you need to prove
   225 you need to prove
   226 \begin{enumerate}
   226 \begin{enumerate}
   227 \item the base case @{prop"P(Nil)"} and
   227 \item the base case @{prop"P(Nil)"} and
   228 \item the inductive case @{prop"P(Cons x xs)"} under the assumption @{prop"P(xs)"}, for some arbitrary but fixed @{text x} and @{text xs}.
   228 \item the inductive case @{prop"P(Cons x xs)"} under the assumption @{prop"P(xs)"}, for some arbitrary but fixed @{text x} and @{text xs}.
   229 \end{enumerate}
   229 \end{enumerate}