doc-src/TutorialI/Ifexpr/Ifexpr.thy
changeset 9541 d17c0b34d5c8
parent 9458 c613cd06d5cf
child 9792 bbefb6ce5cb2
equal deleted inserted replaced
9540:02c51ca9c531 9541:d17c0b34d5c8
    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