src/HOL/Induct/Mutil.thy
author paulson
Fri, 06 Jun 1997 10:47:16 +0200
changeset 3424 bf466159ef84
parent 3120 c58423c20740
child 5931 325300576da7
permissions -rw-r--r--
Tidying and simplification of declarations
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
3424
bf466159ef84 Tidying and simplification of declarations
paulson
parents: 3120
diff changeset
     1
(*  Title:      HOL/Induct/Mutil
3120
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
     2
    ID:         $Id$
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
     3
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
     4
    Copyright   1996  University of Cambridge
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
     5
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
     6
The Mutilated Chess Board Problem, formalized inductively
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
     7
  Originator is Max Black, according to J A Robinson.
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
     8
  Popularized as the Mutilated Checkerboard Problem by J McCarthy
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
     9
*)
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
    10
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
    11
Mutil = Finite +
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
    12
consts
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
    13
  domino  :: "(nat*nat)set set"
3424
bf466159ef84 Tidying and simplification of declarations
paulson
parents: 3120
diff changeset
    14
  tiling  :: "'a set set => 'a set set"
bf466159ef84 Tidying and simplification of declarations
paulson
parents: 3120
diff changeset
    15
  below   :: "nat => nat set"
3120
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
    16
  evnodd  :: "[(nat*nat)set, nat] => (nat*nat)set"
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
    17
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
    18
inductive domino
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
    19
  intrs
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
    20
    horiz  "{(i, j), (i, Suc j)} : domino"
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
    21
    vertl  "{(i, j), (Suc i, j)} : domino"
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
    22
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
    23
inductive "tiling A"
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
    24
  intrs
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
    25
    empty  "{} : tiling A"
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
    26
    Un     "[| a: A;  t: tiling A;  a <= Compl t |] ==> a Un t : tiling A"
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
    27
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
    28
defs
3424
bf466159ef84 Tidying and simplification of declarations
paulson
parents: 3120
diff changeset
    29
  below_def  "below n    == {i. i<n}"
3120
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
    30
  evnodd_def "evnodd A b == A Int {(i,j). (i+j) mod 2 = b}"
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
    31
c58423c20740 New directory to contain examples of (co)inductive definitions
paulson
parents:
diff changeset
    32
end