equal
deleted
inserted
replaced
29 @{term"And (Var 0) (Neg(Var 1))"}. |
29 @{term"And (Var 0) (Neg(Var 1))"}. |
30 |
30 |
31 \subsubsection{The Value of a Boolean Expression} |
31 \subsubsection{The Value of a Boolean Expression} |
32 |
32 |
33 The value of a boolean expression depends on the value of its variables. |
33 The value of a boolean expression depends on the value of its variables. |
34 Hence the function @{text"value"} takes an additional parameter, an |
34 Hence the function \<open>value\<close> takes an additional parameter, an |
35 \emph{environment} of type @{typ"nat => bool"}, which maps variables to their |
35 \emph{environment} of type @{typ"nat => bool"}, which maps variables to their |
36 values: |
36 values: |
37 \<close> |
37 \<close> |
38 |
38 |
39 primrec "value" :: "boolex \<Rightarrow> (nat \<Rightarrow> bool) \<Rightarrow> bool" where |
39 primrec "value" :: "boolex \<Rightarrow> (nat \<Rightarrow> bool) \<Rightarrow> bool" where |
137 apply(induct_tac b) |
137 apply(induct_tac b) |
138 by(auto) |
138 by(auto) |
139 (*>*) |
139 (*>*) |
140 text\<open>\noindent |
140 text\<open>\noindent |
141 Note that the lemma does not have a name, but is implicitly used in the proof |
141 Note that the lemma does not have a name, but is implicitly used in the proof |
142 of the theorem shown above because of the @{text"[simp]"} attribute. |
142 of the theorem shown above because of the \<open>[simp]\<close> attribute. |
143 |
143 |
144 But how can we be sure that @{term"norm"} really produces a normal form in |
144 But how can we be sure that @{term"norm"} really produces a normal form in |
145 the above sense? We define a function that tests If-expressions for normality: |
145 the above sense? We define a function that tests If-expressions for normality: |
146 \<close> |
146 \<close> |
147 |
147 |
166 by(auto) |
166 by(auto) |
167 (*>*) |
167 (*>*) |
168 |
168 |
169 text\<open>\medskip |
169 text\<open>\medskip |
170 How do we come up with the required lemmas? Try to prove the main theorems |
170 How do we come up with the required lemmas? Try to prove the main theorems |
171 without them and study carefully what @{text auto} leaves unproved. This |
171 without them and study carefully what \<open>auto\<close> leaves unproved. This |
172 can provide the clue. The necessity of universal quantification |
172 can provide the clue. The necessity of universal quantification |
173 (@{text"\<forall>t e"}) in the two lemmas is explained in |
173 (\<open>\<forall>t e\<close>) in the two lemmas is explained in |
174 \S\ref{sec:InductionHeuristics} |
174 \S\ref{sec:InductionHeuristics} |
175 |
175 |
176 \begin{exercise} |
176 \begin{exercise} |
177 We strengthen the definition of a @{const normal} If-expression as follows: |
177 We strengthen the definition of a @{const normal} If-expression as follows: |
178 the first argument of all @{term IF}s must be a variable. Adapt the above |
178 the first argument of all @{term IF}s must be a variable. Adapt the above |
179 development to this changed requirement. (Hint: you may need to formulate |
179 development to this changed requirement. (Hint: you may need to formulate |
180 some of the goals as implications (@{text"\<longrightarrow>"}) rather than |
180 some of the goals as implications (\<open>\<longrightarrow>\<close>) rather than |
181 equalities (@{text"="}).) |
181 equalities (\<open>=\<close>).) |
182 \end{exercise} |
182 \end{exercise} |
183 \index{boolean expressions example|)} |
183 \index{boolean expressions example|)} |
184 \<close> |
184 \<close> |
185 (*<*) |
185 (*<*) |
186 |
186 |