12 |
12 |
13 datatype boolex = Const bool | Var nat | Neg boolex |
13 datatype boolex = Const bool | Var nat | Neg boolex |
14 | And boolex boolex; |
14 | And boolex boolex; |
15 |
15 |
16 text{*\noindent |
16 text{*\noindent |
17 The two constants are represented by \isa{Const~True} and |
17 The two constants are represented by @{term"Const True"} and |
18 \isa{Const~False}. Variables are represented by terms of the form |
18 @{term"Const False"}. Variables are represented by terms of the form |
19 \isa{Var~$n$}, where $n$ is a natural number (type \isa{nat}). |
19 @{term"Var n"}, where @{term"n"} is a natural number (type \isa{nat}). |
20 For example, the formula $P@0 \land \neg P@1$ is represented by the term |
20 For example, the formula $P@0 \land \neg P@1$ is represented by the term |
21 \isa{And~(Var~0)~(Neg(Var~1))}. |
21 @{term"And (Var 0) (Neg(Var 1))"}. |
22 |
22 |
23 \subsubsection{What is the value of a boolean expression?} |
23 \subsubsection{What is the value of a boolean expression?} |
24 |
24 |
25 The value of a boolean expression depends on the value of its variables. |
25 The value of a boolean expression depends on the value of its variables. |
26 Hence the function \isa{value} takes an additional parameter, an {\em |
26 Hence the function \isa{value} takes an additional parameter, an {\em |
27 environment} of type \isa{nat \isasymFun\ bool}, which maps variables to |
27 environment} of type @{typ"nat => bool"}, which maps variables to |
28 their values: |
28 their values: |
29 *} |
29 *} |
30 |
30 |
31 consts value :: "boolex \\<Rightarrow> (nat \\<Rightarrow> bool) \\<Rightarrow> bool"; |
31 consts value :: "boolex \\<Rightarrow> (nat \\<Rightarrow> bool) \\<Rightarrow> bool"; |
32 primrec |
32 primrec |
91 not show them below. |
91 not show them below. |
92 |
92 |
93 More interesting is the transformation of If-expressions into a normal form |
93 More interesting is the transformation of If-expressions into a normal form |
94 where the first argument of \isa{IF} cannot be another \isa{IF} but |
94 where the first argument of \isa{IF} cannot be another \isa{IF} but |
95 must be a constant or variable. Such a normal form can be computed by |
95 must be a constant or variable. Such a normal form can be computed by |
96 repeatedly replacing a subterm of the form \isa{IF~(IF~b~x~y)~z~u} by |
96 repeatedly replacing a subterm of the form @{term"IF (IF b x y) z u"} by |
97 \isa{IF b (IF x z u) (IF y z u)}, which has the same value. The following |
97 @{term"IF b (IF x z u) (IF y z u)"}, which has the same value. The following |
98 primitive recursive functions perform this task: |
98 primitive recursive functions perform this task: |
99 *} |
99 *} |
100 |
100 |
101 consts normif :: "ifex \\<Rightarrow> ifex \\<Rightarrow> ifex \\<Rightarrow> ifex"; |
101 consts normif :: "ifex \\<Rightarrow> ifex \\<Rightarrow> ifex \\<Rightarrow> ifex"; |
102 primrec |
102 primrec |