src/HOL/Metis_Examples/TransClosure.thy
author blanchet
Wed Apr 28 14:19:26 2010 +0200 (2010-04-28)
changeset 36490 5abf45444a16
parent 35096 f36965a1fd42
child 36494 2478dd225b68
permissions -rw-r--r--
redo Sledgehammer proofs (and get rid of "neg_clausify")
paulson@23449
     1
(*  Title:      HOL/MetisTest/TransClosure.thy
paulson@23449
     2
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
paulson@23449
     3
paulson@23449
     4
Testing the metis method
paulson@23449
     5
*)
paulson@23449
     6
paulson@23449
     7
theory TransClosure
blanchet@36490
     8
imports Sledgehammer2d (* ### *)
paulson@23449
     9
begin
paulson@23449
    10
paulson@23449
    11
types addr = nat
paulson@23449
    12
paulson@23449
    13
datatype val
paulson@23449
    14
  = Unit        -- "dummy result value of void expressions"
paulson@23449
    15
  | Null        -- "null reference"
paulson@23449
    16
  | Bool bool   -- "Boolean value"
paulson@23449
    17
  | Intg int    -- "integer value" 
paulson@23449
    18
  | Addr addr   -- "addresses of objects in the heap"
paulson@23449
    19
blanchet@36490
    20
consts R :: "(addr \<times> addr) set"
paulson@23449
    21
blanchet@36490
    22
consts f :: "addr \<Rightarrow> val"
paulson@23449
    23
blanchet@36490
    24
lemma "\<lbrakk>f c = Intg x; \<forall>y. f b = Intg y \<longrightarrow> y \<noteq> x; (a, b) \<in> R\<^sup>*; (b, c) \<in> R\<^sup>*\<rbrakk>
blanchet@36490
    25
       \<Longrightarrow> \<exists>c. (b, c) \<in> R \<and> (a, c) \<in> R\<^sup>*"
blanchet@36490
    26
by (metis converse_rtranclE transitive_closure_trans(6))
paulson@23449
    27
blanchet@36490
    28
lemma "\<lbrakk>f c = Intg x; \<forall>y. f b = Intg y \<longrightarrow> y \<noteq> x; (a, b) \<in> R\<^sup>*; (b,c) \<in> R\<^sup>*\<rbrakk>
blanchet@36490
    29
       \<Longrightarrow> \<exists>c. (b, c) \<in> R \<and> (a, c) \<in> R\<^sup>*"
blanchet@36490
    30
(* sledgehammer [isar_proof, shrink_factor = 2] *)
blanchet@36490
    31
proof -
blanchet@36490
    32
  assume A1: "f c = Intg x"
blanchet@36490
    33
  assume A2: "\<forall>y. f b = Intg y \<longrightarrow> y \<noteq> x"
blanchet@36490
    34
  assume A3: "(a, b) \<in> R\<^sup>*"
blanchet@36490
    35
  assume A4: "(b, c) \<in> R\<^sup>*"
blanchet@36490
    36
  have "(R\<^sup>*) (a, b)" using A3 by (metis mem_def)
blanchet@36490
    37
  hence F1: "(a, b) \<in> R\<^sup>*" by (metis mem_def)
blanchet@36490
    38
  have "b \<noteq> c" using A1 A2 by metis
blanchet@36490
    39
  hence "\<exists>x\<^isub>1. (b, x\<^isub>1) \<in> R" using A4 by (metis mem_def converse_rtranclE)
blanchet@36490
    40
  thus "\<exists>c. (b, c) \<in> R \<and> (a, c) \<in> R\<^sup>*" using F1 by (metis transitive_closure_trans(6))
paulson@23449
    41
qed
paulson@23449
    42
blanchet@36490
    43
lemma "\<lbrakk>f c = Intg x; \<forall>y. f b = Intg y \<longrightarrow> y \<noteq> x; (a, b) \<in> R\<^sup>*; (b, c) \<in> R\<^sup>*\<rbrakk> 
blanchet@36490
    44
       \<Longrightarrow> \<exists>c. (b, c) \<in> R \<and> (a, c) \<in> R\<^sup>*"
blanchet@36490
    45
apply (erule_tac x = b in converse_rtranclE)
blanchet@36490
    46
 apply metis
blanchet@36490
    47
by (metis transitive_closure_trans(6))
paulson@23449
    48
paulson@23449
    49
end