src/CCL/ex/nat.thy
author wenzelm
Mon, 09 Nov 1998 15:32:43 +0100
changeset 5824 91113aa09371
parent 0 a5a9c433f639
permissions -rw-r--r--
Proof methods.
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     1
(*  Title: 	CCL/ex/nat.thy
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     2
    ID:         $Id$
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     3
    Author: 	Martin Coen, Cambridge University Computer Laboratory
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     4
    Copyright   1993  University of Cambridge
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     5
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     6
Programs defined over the natural numbers
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     7
*)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     8
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     9
Nat = Wfd +
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    10
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    11
consts
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    12
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    13
  not              :: "i=>i"
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    14
  "#+","#*","#-",
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    15
  "##","#<","#<="  :: "[i,i]=>i"            (infixr 60)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    16
  ackermann        :: "[i,i]=>i"
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    17
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    18
rules 
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    19
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    20
  not_def     "not(b) == if b then false else true"
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    21
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    22
  add_def     "a #+ b == nrec(a,b,%x g.succ(g))"
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    23
  mult_def    "a #* b == nrec(a,zero,%x g.b #+ g)"
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    24
  sub_def     "a #- b == letrec sub x y be ncase(y,x,%yy.ncase(x,zero,%xx.sub(xx,yy))) \
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    25
\                        in sub(a,b)"
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    26
  le_def     "a #<= b == letrec le x y be ncase(x,true,%xx.ncase(y,false,%yy.le(xx,yy))) \
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    27
\                        in le(a,b)"
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    28
  lt_def     "a #< b == not(b #<= a)"
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    29
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    30
  div_def    "a ## b == letrec div x y be if x #< y then zero else succ(div(x#-y,y)) \
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    31
\                       in div(a,b)"
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    32
  ack_def    
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    33
  "ackermann(a,b) == letrec ack n m be ncase(n,succ(m),%x. \
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    34
\                          ncase(m,ack(x,succ(zero)),%y.ack(x,ack(succ(x),y))))\
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    35
\                    in ack(a,b)"
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    36
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    37
end
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    38