author berghofe
Fri, 24 Jul 1998 13:39:47 +0200
changeset 5191 8ceaa19f7717
parent 3424 bf466159ef84
child 5931 325300576da7
permissions -rw-r--r--
Renamed '$' to 'Scons' because of clashes with constants of the same name in theories using datatypes.

(*  Title:      HOL/Induct/Mutil
    ID:         $Id$
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
    Copyright   1996  University of Cambridge

The Mutilated Chess Board Problem, formalized inductively
  Originator is Max Black, according to J A Robinson.
  Popularized as the Mutilated Checkerboard Problem by J McCarthy

Mutil = Finite +
  domino  :: "(nat*nat)set set"
  tiling  :: "'a set set => 'a set set"
  below   :: "nat => nat set"
  evnodd  :: "[(nat*nat)set, nat] => (nat*nat)set"

inductive domino
    horiz  "{(i, j), (i, Suc j)} : domino"
    vertl  "{(i, j), (Suc i, j)} : domino"

inductive "tiling A"
    empty  "{} : tiling A"
    Un     "[| a: A;  t: tiling A;  a <= Compl t |] ==> a Un t : tiling A"

  below_def  "below n    == {i. i<n}"
  evnodd_def "evnodd A b == A Int {(i,j). (i+j) mod 2 = b}"