equal
deleted
inserted
replaced
8 The aim of this case study is twofold: it shows how to model boolean |
8 The aim of this case study is twofold: it shows how to model boolean |
9 expressions and some algorithms for manipulating them, and it demonstrates |
9 expressions and some algorithms for manipulating them, and it demonstrates |
10 the constructs introduced above. |
10 the constructs introduced above. |
11 *} |
11 *} |
12 |
12 |
13 subsubsection{*How Can We Model Boolean Expressions?*} |
13 subsubsection{*Modelling Boolean Expressions*} |
14 |
14 |
15 text{* |
15 text{* |
16 We want to represent boolean expressions built up from variables and |
16 We want to represent boolean expressions built up from variables and |
17 constants by negation and conjunction. The following datatype serves exactly |
17 constants by negation and conjunction. The following datatype serves exactly |
18 that purpose: |
18 that purpose: |
26 @{term"Const False"}. Variables are represented by terms of the form |
26 @{term"Const False"}. Variables are represented by terms of the form |
27 @{term"Var n"}, where @{term"n"} is a natural number (type @{typ"nat"}). |
27 @{term"Var n"}, where @{term"n"} is a natural number (type @{typ"nat"}). |
28 For example, the formula $P@0 \land \neg P@1$ is represented by the term |
28 For example, the formula $P@0 \land \neg P@1$ is represented by the term |
29 @{term"And (Var 0) (Neg(Var 1))"}. |
29 @{term"And (Var 0) (Neg(Var 1))"}. |
30 |
30 |
31 \subsubsection{What is 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 @{text"value"} 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: |
64 "valif (VIF x) env = env x" |
64 "valif (VIF x) env = env x" |
65 "valif (IF b t e) env = (if valif b env then valif t env |
65 "valif (IF b t e) env = (if valif b env then valif t env |
66 else valif e env)"; |
66 else valif e env)"; |
67 |
67 |
68 text{* |
68 text{* |
69 \subsubsection{Transformation Into and of If-Expressions} |
69 \subsubsection{Converting Boolean and If-Expressions} |
70 |
70 |
71 \REMARK{is this the title you wanted?} |
|
72 The type @{typ"boolex"} is close to the customary representation of logical |
71 The type @{typ"boolex"} is close to the customary representation of logical |
73 formulae, whereas @{typ"ifex"} is designed for efficiency. It is easy to |
72 formulae, whereas @{typ"ifex"} is designed for efficiency. It is easy to |
74 translate from @{typ"boolex"} into @{typ"ifex"}: |
73 translate from @{typ"boolex"} into @{typ"ifex"}: |
75 *} |
74 *} |
76 |
75 |