src/HOL/ex/veriT_Preprocessing.thy
changeset 69597 ff784d5a5bfb
parent 69220 c6b15fc78f78
child 74395 5399dfe9141c
equal deleted inserted replaced
69596:c8a2755bf220 69597:ff784d5a5bfb
    45     val lambda_T = fastype_of lambda_t;
    45     val lambda_T = fastype_of lambda_t;
    46 
    46 
    47     val left_prems = map2 (curry Ctr_Sugar_Util.mk_Trueprop_eq) ts us;
    47     val left_prems = map2 (curry Ctr_Sugar_Util.mk_Trueprop_eq) ts us;
    48     val right_prem = Ctr_Sugar_Util.mk_Trueprop_eq (list_comb (p, us), q);
    48     val right_prem = Ctr_Sugar_Util.mk_Trueprop_eq (list_comb (p, us), q);
    49     val concl = Ctr_Sugar_Util.mk_Trueprop_eq
    49     val concl = Ctr_Sugar_Util.mk_Trueprop_eq
    50       (Const (@{const_name Let}, tuple_T --> lambda_T --> B) $ tuple_t $ lambda_t, q);
    50       (Const (\<^const_name>\<open>Let\<close>, tuple_T --> lambda_T --> B) $ tuple_t $ lambda_t, q);
    51 
    51 
    52     val goal = Logic.list_implies (left_prems @ [right_prem], concl);
    52     val goal = Logic.list_implies (left_prems @ [right_prem], concl);
    53     val vars = Variable.add_free_names ctxt goal [];
    53     val vars = Variable.add_free_names ctxt goal [];
    54   in
    54   in
    55     Goal.prove_sorry ctxt vars [] goal (fn {context = ctxt, ...} =>
    55     Goal.prove_sorry ctxt vars [] goal (fn {context = ctxt, ...} =>
    67 | Sko_Ex
    67 | Sko_Ex
    68 | Sko_All
    68 | Sko_All
    69 | Let of term list;
    69 | Let of term list;
    70 
    70 
    71 fun str_of_rule_name Refl = "Refl"
    71 fun str_of_rule_name Refl = "Refl"
    72   | str_of_rule_name (Taut th) = "Taut[" ^ @{make_string} th ^ "]"
    72   | str_of_rule_name (Taut th) = "Taut[" ^ \<^make_string> th ^ "]"
    73   | str_of_rule_name (Trans t) = "Trans[" ^ Syntax.string_of_term @{context} t ^ "]"
    73   | str_of_rule_name (Trans t) = "Trans[" ^ Syntax.string_of_term \<^context> t ^ "]"
    74   | str_of_rule_name Cong = "Cong"
    74   | str_of_rule_name Cong = "Cong"
    75   | str_of_rule_name Bind = "Bind"
    75   | str_of_rule_name Bind = "Bind"
    76   | str_of_rule_name Sko_Ex = "Sko_Ex"
    76   | str_of_rule_name Sko_Ex = "Sko_Ex"
    77   | str_of_rule_name Sko_All = "Sko_All"
    77   | str_of_rule_name Sko_All = "Sko_All"
    78   | str_of_rule_name (Let ts) =
    78   | str_of_rule_name (Let ts) =
    79     "Let[" ^ commas (map (Syntax.string_of_term @{context}) ts) ^ "]";
    79     "Let[" ^ commas (map (Syntax.string_of_term \<^context>) ts) ^ "]";
    80 
    80 
    81 datatype node = N of rule_name * node list;
    81 datatype node = N of rule_name * node list;
    82 
    82 
    83 fun lambda_count (Abs (_, _, t)) = lambda_count t + 1
    83 fun lambda_count (Abs (_, _, t)) = lambda_count t + 1
    84   | lambda_count ((t as Abs _) $ _) = lambda_count t - 1
    84   | lambda_count ((t as Abs _) $ _) = lambda_count t - 1
    85   | lambda_count ((t as Const (@{const_name case_prod}, _) $ _) $ _) = lambda_count t - 1
    85   | lambda_count ((t as Const (\<^const_name>\<open>case_prod\<close>, _) $ _) $ _) = lambda_count t - 1
    86   | lambda_count (Const (@{const_name case_prod}, _) $ t) = lambda_count t - 1
    86   | lambda_count (Const (\<^const_name>\<open>case_prod\<close>, _) $ t) = lambda_count t - 1
    87   | lambda_count _ = 0;
    87   | lambda_count _ = 0;
    88 
    88 
    89 fun zoom apply =
    89 fun zoom apply =
    90   let
    90   let
    91     fun zo 0 bound_Ts (Abs (r, T, t), Abs (s, U, u)) =
    91     fun zo 0 bound_Ts (Abs (r, T, t), Abs (s, U, u)) =
    94         end
    94         end
    95       | zo 0 bound_Ts ((t as Abs (_, T, _)) $ arg, u) =
    95       | zo 0 bound_Ts ((t as Abs (_, T, _)) $ arg, u) =
    96         let val (t', u') = zo 1 (T :: bound_Ts) (t, u) in
    96         let val (t', u') = zo 1 (T :: bound_Ts) (t, u) in
    97           (t' $ arg, u')
    97           (t' $ arg, u')
    98         end
    98         end
    99       | zo 0 bound_Ts ((t as Const (@{const_name case_prod}, _) $ _) $ arg, u) =
    99       | zo 0 bound_Ts ((t as Const (\<^const_name>\<open>case_prod\<close>, _) $ _) $ arg, u) =
   100         let val (t', u') = zo 1 bound_Ts (t, u) in
   100         let val (t', u') = zo 1 bound_Ts (t, u) in
   101           (t' $ arg, u')
   101           (t' $ arg, u')
   102         end
   102         end
   103       | zo 0 bound_Ts tu = apply bound_Ts tu
   103       | zo 0 bound_Ts tu = apply bound_Ts tu
   104       | zo n bound_Ts (Const (@{const_name case_prod},
   104       | zo n bound_Ts (Const (\<^const_name>\<open>case_prod\<close>,
   105           Type (@{type_name fun}, [Type (@{type_name fun}, [A, Type (@{type_name fun}, [B, _])]),
   105           Type (\<^type_name>\<open>fun\<close>, [Type (\<^type_name>\<open>fun\<close>, [A, Type (\<^type_name>\<open>fun\<close>, [B, _])]),
   106             Type (@{type_name fun}, [AB, _])])) $ t, u) =
   106             Type (\<^type_name>\<open>fun\<close>, [AB, _])])) $ t, u) =
   107         let
   107         let
   108           val (t', u') = zo (n + 1) bound_Ts (t, u);
   108           val (t', u') = zo (n + 1) bound_Ts (t, u);
   109           val C = range_type (range_type (fastype_of t'));
   109           val C = range_type (range_type (fastype_of t'));
   110         in
   110         in
   111           (Const (@{const_name case_prod}, (A --> B --> C) --> AB --> C) $ t', u')
   111           (Const (\<^const_name>\<open>case_prod\<close>, (A --> B --> C) --> AB --> C) $ t', u')
   112         end
   112         end
   113       | zo n bound_Ts (Abs (s, T, t), u) =
   113       | zo n bound_Ts (Abs (s, T, t), u) =
   114         let val (t', u') = zo (n - 1) (T :: bound_Ts) (t, u) in
   114         let val (t', u') = zo (n - 1) (T :: bound_Ts) (t, u) in
   115           (Abs (s, T, t'), u')
   115           (Abs (s, T, t'), u')
   116         end
   116         end
   128     if c aconv d andalso length ts = ary andalso length us = ary then (nth ts j, nth us j)
   128     if c aconv d andalso length ts = ary andalso length us = ary then (nth ts j, nth us j)
   129     else raise TERM ("apply_Cong", [lhs, rhs]));
   129     else raise TERM ("apply_Cong", [lhs, rhs]));
   130 
   130 
   131 fun apply_Bind (lhs, rhs) =
   131 fun apply_Bind (lhs, rhs) =
   132   (case (lhs, rhs) of
   132   (case (lhs, rhs) of
   133     (Const (@{const_name All}, _) $ Abs (_, T, t), Const (@{const_name All}, _) $ Abs (s, U, u)) =>
   133     (Const (\<^const_name>\<open>All\<close>, _) $ Abs (_, T, t), Const (\<^const_name>\<open>All\<close>, _) $ Abs (s, U, u)) =>
   134     (Abs (s, T, t), Abs (s, U, u))
   134     (Abs (s, T, t), Abs (s, U, u))
   135   | (Const (@{const_name Ex}, _) $ t, Const (@{const_name Ex}, _) $ u) => (t, u)
   135   | (Const (\<^const_name>\<open>Ex\<close>, _) $ t, Const (\<^const_name>\<open>Ex\<close>, _) $ u) => (t, u)
   136   | _ => raise TERM ("apply_Bind", [lhs, rhs]));
   136   | _ => raise TERM ("apply_Bind", [lhs, rhs]));
   137 
   137 
   138 fun apply_Sko_Ex (lhs, rhs) =
   138 fun apply_Sko_Ex (lhs, rhs) =
   139   (case lhs of
   139   (case lhs of
   140     Const (@{const_name Ex}, _) $ (t as Abs (_, T, _)) =>
   140     Const (\<^const_name>\<open>Ex\<close>, _) $ (t as Abs (_, T, _)) =>
   141     (t $ (HOLogic.choice_const T $ t), rhs)
   141     (t $ (HOLogic.choice_const T $ t), rhs)
   142   | _ => raise TERM ("apply_Sko_Ex", [lhs]));
   142   | _ => raise TERM ("apply_Sko_Ex", [lhs]));
   143 
   143 
   144 fun apply_Sko_All (lhs, rhs) =
   144 fun apply_Sko_All (lhs, rhs) =
   145   (case lhs of
   145   (case lhs of
   146     Const (@{const_name All}, _) $ (t as Abs (s, T, body)) =>
   146     Const (\<^const_name>\<open>All\<close>, _) $ (t as Abs (s, T, body)) =>
   147     (t $ (HOLogic.choice_const T $ Abs (s, T, HOLogic.mk_not body)), rhs)
   147     (t $ (HOLogic.choice_const T $ Abs (s, T, HOLogic.mk_not body)), rhs)
   148   | _ => raise TERM ("apply_Sko_All", [lhs]));
   148   | _ => raise TERM ("apply_Sko_All", [lhs]));
   149 
   149 
   150 fun apply_Let_left ts j (lhs, _) =
   150 fun apply_Let_left ts j (lhs, _) =
   151   (case lhs of
   151   (case lhs of
   152     Const (@{const_name Let}, _) $ t $ _ =>
   152     Const (\<^const_name>\<open>Let\<close>, _) $ t $ _ =>
   153     let val ts0 = HOLogic.strip_tuple t in
   153     let val ts0 = HOLogic.strip_tuple t in
   154       (nth ts0 j, nth ts j)
   154       (nth ts0 j, nth ts j)
   155     end
   155     end
   156   | _ => raise TERM ("apply_Let_left", [lhs]));
   156   | _ => raise TERM ("apply_Let_left", [lhs]));
   157 
   157 
   158 fun apply_Let_right ts bound_Ts (lhs, rhs) =
   158 fun apply_Let_right ts bound_Ts (lhs, rhs) =
   159   let val t' = mk_tuple1 bound_Ts ts in
   159   let val t' = mk_tuple1 bound_Ts ts in
   160     (case lhs of
   160     (case lhs of
   161       Const (@{const_name Let}, _) $ _ $ u => (u $ t', rhs)
   161       Const (\<^const_name>\<open>Let\<close>, _) $ _ $ u => (u $ t', rhs)
   162     | _ => raise TERM ("apply_Let_right", [lhs, rhs]))
   162     | _ => raise TERM ("apply_Let_right", [lhs, rhs]))
   163   end;
   163   end;
   164 
   164 
   165 fun reconstruct_proof ctxt (lrhs as (_, rhs), N (rule_name, prems)) =
   165 fun reconstruct_proof ctxt (lrhs as (_, rhs), N (rule_name, prems)) =
   166   let
   166   let
   167     val goal = HOLogic.mk_Trueprop (HOLogic.mk_eq lrhs);
   167     val goal = HOLogic.mk_Trueprop (HOLogic.mk_eq lrhs);
   168     val ary = length prems;
   168     val ary = length prems;
   169 
   169 
   170     val _ = warning (Syntax.string_of_term @{context} goal);
   170     val _ = warning (Syntax.string_of_term \<^context> goal);
   171     val _ = warning (str_of_rule_name rule_name);
   171     val _ = warning (str_of_rule_name rule_name);
   172 
   172 
   173     val parents =
   173     val parents =
   174       (case (rule_name, prems) of
   174       (case (rule_name, prems) of
   175         (Refl, []) => []
   175         (Refl, []) => []
   217   end;
   217   end;
   218 \<close>
   218 \<close>
   219 
   219 
   220 ML \<open>
   220 ML \<open>
   221 val proof0 =
   221 val proof0 =
   222   ((@{term "\<exists>x :: nat. p x"},
   222   ((\<^term>\<open>\<exists>x :: nat. p x\<close>,
   223     @{term "p (SOME x :: nat. p x)"}),
   223     \<^term>\<open>p (SOME x :: nat. p x)\<close>),
   224    N (Sko_Ex, [N (Refl, [])]));
   224    N (Sko_Ex, [N (Refl, [])]));
   225 
   225 
   226 reconstruct_proof @{context} proof0;
   226 reconstruct_proof \<^context> proof0;
   227 \<close>
   227 \<close>
   228 
   228 
   229 ML \<open>
   229 ML \<open>
   230 val proof1 =
   230 val proof1 =
   231   ((@{term "\<not> (\<forall>x :: nat. \<exists>y :: nat. p x y)"},
   231   ((\<^term>\<open>\<not> (\<forall>x :: nat. \<exists>y :: nat. p x y)\<close>,
   232     @{term "\<not> (\<exists>y :: nat. p (SOME x :: nat. \<not> (\<exists>y :: nat. p x y)) y)"}),
   232     \<^term>\<open>\<not> (\<exists>y :: nat. p (SOME x :: nat. \<not> (\<exists>y :: nat. p x y)) y)\<close>),
   233    N (Cong, [N (Sko_All, [N (Bind, [N (Refl, [])])])]));
   233    N (Cong, [N (Sko_All, [N (Bind, [N (Refl, [])])])]));
   234 
   234 
   235 reconstruct_proof @{context} proof1;
   235 reconstruct_proof \<^context> proof1;
   236 \<close>
   236 \<close>
   237 
   237 
   238 ML \<open>
   238 ML \<open>
   239 val proof2 =
   239 val proof2 =
   240   ((@{term "\<forall>x :: nat. \<exists>y :: nat. \<exists>z :: nat. p x y z"},
   240   ((\<^term>\<open>\<forall>x :: nat. \<exists>y :: nat. \<exists>z :: nat. p x y z\<close>,
   241     @{term "\<forall>x :: nat. p x (SOME y :: nat. \<exists>z :: nat. p x y z)
   241     \<^term>\<open>\<forall>x :: nat. p x (SOME y :: nat. \<exists>z :: nat. p x y z)
   242         (SOME z :: nat. p x (SOME y :: nat. \<exists>z :: nat. p x y z) z)"}),
   242         (SOME z :: nat. p x (SOME y :: nat. \<exists>z :: nat. p x y z) z)\<close>),
   243    N (Bind, [N (Sko_Ex, [N (Sko_Ex, [N (Refl, [])])])]));
   243    N (Bind, [N (Sko_Ex, [N (Sko_Ex, [N (Refl, [])])])]));
   244 
   244 
   245 reconstruct_proof @{context} proof2
   245 reconstruct_proof \<^context> proof2
   246 \<close>
   246 \<close>
   247 
   247 
   248 ML \<open>
   248 ML \<open>
   249 val proof3 =
   249 val proof3 =
   250   ((@{term "\<forall>x :: nat. \<exists>x :: nat. \<exists>x :: nat. p x x x"},
   250   ((\<^term>\<open>\<forall>x :: nat. \<exists>x :: nat. \<exists>x :: nat. p x x x\<close>,
   251     @{term "\<forall>x :: nat. p (SOME x :: nat. p x x x) (SOME x. p x x x) (SOME x. p x x x)"}),
   251     \<^term>\<open>\<forall>x :: nat. p (SOME x :: nat. p x x x) (SOME x. p x x x) (SOME x. p x x x)\<close>),
   252    N (Bind, [N (Sko_Ex, [N (Sko_Ex, [N (Refl, [])])])]));
   252    N (Bind, [N (Sko_Ex, [N (Sko_Ex, [N (Refl, [])])])]));
   253 
   253 
   254 reconstruct_proof @{context} proof3
   254 reconstruct_proof \<^context> proof3
   255 \<close>
   255 \<close>
   256 
   256 
   257 ML \<open>
   257 ML \<open>
   258 val proof4 =
   258 val proof4 =
   259   ((@{term "\<forall>x :: nat. \<exists>x :: nat. \<exists>x :: nat. p x x x"},
   259   ((\<^term>\<open>\<forall>x :: nat. \<exists>x :: nat. \<exists>x :: nat. p x x x\<close>,
   260     @{term "\<forall>x :: nat. \<exists>x :: nat. p (SOME x :: nat. p x x x) (SOME x. p x x x) (SOME x. p x x x)"}),
   260     \<^term>\<open>\<forall>x :: nat. \<exists>x :: nat. p (SOME x :: nat. p x x x) (SOME x. p x x x) (SOME x. p x x x)\<close>),
   261    N (Bind, [N (Bind, [N (Sko_Ex, [N (Refl, [])])])]));
   261    N (Bind, [N (Bind, [N (Sko_Ex, [N (Refl, [])])])]));
   262 
   262 
   263 reconstruct_proof @{context} proof4
   263 reconstruct_proof \<^context> proof4
   264 \<close>
   264 \<close>
   265 
   265 
   266 ML \<open>
   266 ML \<open>
   267 val proof5 =
   267 val proof5 =
   268   ((@{term "\<forall>x :: nat. q \<and> (\<exists>x :: nat. \<exists>x :: nat. p x x x)"},
   268   ((\<^term>\<open>\<forall>x :: nat. q \<and> (\<exists>x :: nat. \<exists>x :: nat. p x x x)\<close>,
   269     @{term "\<forall>x :: nat. q \<and>
   269     \<^term>\<open>\<forall>x :: nat. q \<and>
   270         (\<exists>x :: nat. p (SOME x :: nat. p x x x) (SOME x. p x x x) (SOME x. p x x x))"}),
   270         (\<exists>x :: nat. p (SOME x :: nat. p x x x) (SOME x. p x x x) (SOME x. p x x x))\<close>),
   271    N (Bind, [N (Cong, [N (Refl, []), N (Bind, [N (Sko_Ex, [N (Refl, [])])])])]));
   271    N (Bind, [N (Cong, [N (Refl, []), N (Bind, [N (Sko_Ex, [N (Refl, [])])])])]));
   272 
   272 
   273 reconstruct_proof @{context} proof5
   273 reconstruct_proof \<^context> proof5
   274 \<close>
   274 \<close>
   275 
   275 
   276 ML \<open>
   276 ML \<open>
   277 val proof6 =
   277 val proof6 =
   278   ((@{term "\<not> (\<forall>x :: nat. p \<and> (\<exists>x :: nat. \<forall>x :: nat. q x x))"},
   278   ((\<^term>\<open>\<not> (\<forall>x :: nat. p \<and> (\<exists>x :: nat. \<forall>x :: nat. q x x))\<close>,
   279     @{term "\<not> (\<forall>x :: nat. p \<and>
   279     \<^term>\<open>\<not> (\<forall>x :: nat. p \<and>
   280         (\<exists>x :: nat. q (SOME x :: nat. \<not> q x x) (SOME x. \<not> q x x)))"}),
   280         (\<exists>x :: nat. q (SOME x :: nat. \<not> q x x) (SOME x. \<not> q x x)))\<close>),
   281    N (Cong, [N (Bind, [N (Cong, [N (Refl, []), N (Bind, [N (Sko_All, [N (Refl, [])])])])])]));
   281    N (Cong, [N (Bind, [N (Cong, [N (Refl, []), N (Bind, [N (Sko_All, [N (Refl, [])])])])])]));
   282 
   282 
   283 reconstruct_proof @{context} proof6
   283 reconstruct_proof \<^context> proof6
   284 \<close>
   284 \<close>
   285 
   285 
   286 ML \<open>
   286 ML \<open>
   287 val proof7 =
   287 val proof7 =
   288   ((@{term "\<not> \<not> (\<exists>x. p x)"},
   288   ((\<^term>\<open>\<not> \<not> (\<exists>x. p x)\<close>,
   289     @{term "\<not> \<not> p (SOME x. p x)"}),
   289     \<^term>\<open>\<not> \<not> p (SOME x. p x)\<close>),
   290    N (Cong, [N (Cong, [N (Sko_Ex, [N (Refl, [])])])]));
   290    N (Cong, [N (Cong, [N (Sko_Ex, [N (Refl, [])])])]));
   291 
   291 
   292 reconstruct_proof @{context} proof7
   292 reconstruct_proof \<^context> proof7
   293 \<close>
   293 \<close>
   294 
   294 
   295 ML \<open>
   295 ML \<open>
   296 val proof8 =
   296 val proof8 =
   297   ((@{term "\<not> \<not> (let x = Suc x in x = 0)"},
   297   ((\<^term>\<open>\<not> \<not> (let x = Suc x in x = 0)\<close>,
   298     @{term "\<not> \<not> Suc x = 0"}),
   298     \<^term>\<open>\<not> \<not> Suc x = 0\<close>),
   299    N (Cong, [N (Cong, [N (Let [@{term "Suc x"}], [N (Refl, []), N (Refl, [])])])]));
   299    N (Cong, [N (Cong, [N (Let [\<^term>\<open>Suc x\<close>], [N (Refl, []), N (Refl, [])])])]));
   300 
   300 
   301 reconstruct_proof @{context} proof8
   301 reconstruct_proof \<^context> proof8
   302 \<close>
   302 \<close>
   303 
   303 
   304 ML \<open>
   304 ML \<open>
   305 val proof9 =
   305 val proof9 =
   306   ((@{term "\<not> (let x = Suc x in x = 0)"},
   306   ((\<^term>\<open>\<not> (let x = Suc x in x = 0)\<close>,
   307     @{term "\<not> Suc x = 0"}),
   307     \<^term>\<open>\<not> Suc x = 0\<close>),
   308    N (Cong, [N (Let [@{term "Suc x"}], [N (Refl, []), N (Refl, [])])]));
   308    N (Cong, [N (Let [\<^term>\<open>Suc x\<close>], [N (Refl, []), N (Refl, [])])]));
   309 
   309 
   310 reconstruct_proof @{context} proof9
   310 reconstruct_proof \<^context> proof9
   311 \<close>
   311 \<close>
   312 
   312 
   313 ML \<open>
   313 ML \<open>
   314 val proof10 =
   314 val proof10 =
   315   ((@{term "\<exists>x :: nat. p (x + 0)"},
   315   ((\<^term>\<open>\<exists>x :: nat. p (x + 0)\<close>,
   316     @{term "\<exists>x :: nat. p x"}),
   316     \<^term>\<open>\<exists>x :: nat. p x\<close>),
   317    N (Bind, [N (Cong, [N (Taut @{thm add_0_right}, [])])]));
   317    N (Bind, [N (Cong, [N (Taut @{thm add_0_right}, [])])]));
   318 
   318 
   319 reconstruct_proof @{context} proof10;
   319 reconstruct_proof \<^context> proof10;
   320 \<close>
   320 \<close>
   321 
   321 
   322 ML \<open>
   322 ML \<open>
   323 val proof11 =
   323 val proof11 =
   324   ((@{term "\<not> (let (x, y) = (Suc y, Suc x) in y = 0)"},
   324   ((\<^term>\<open>\<not> (let (x, y) = (Suc y, Suc x) in y = 0)\<close>,
   325     @{term "\<not> Suc x = 0"}),
   325     \<^term>\<open>\<not> Suc x = 0\<close>),
   326    N (Cong, [N (Let [@{term "Suc y"}, @{term "Suc x"}], [N (Refl, []), N (Refl, []),
   326    N (Cong, [N (Let [\<^term>\<open>Suc y\<close>, \<^term>\<open>Suc x\<close>], [N (Refl, []), N (Refl, []),
   327      N (Refl, [])])]));
   327      N (Refl, [])])]));
   328 
   328 
   329 reconstruct_proof @{context} proof11
   329 reconstruct_proof \<^context> proof11
   330 \<close>
   330 \<close>
   331 
   331 
   332 ML \<open>
   332 ML \<open>
   333 val proof12 =
   333 val proof12 =
   334   ((@{term "\<not> (let (x, y) = (Suc y, Suc x); (u, v, w) = (y, x, y) in w = 0)"},
   334   ((\<^term>\<open>\<not> (let (x, y) = (Suc y, Suc x); (u, v, w) = (y, x, y) in w = 0)\<close>,
   335     @{term "\<not> Suc x = 0"}),
   335     \<^term>\<open>\<not> Suc x = 0\<close>),
   336    N (Cong, [N (Let [@{term "Suc y"}, @{term "Suc x"}], [N (Refl, []), N (Refl, []),
   336    N (Cong, [N (Let [\<^term>\<open>Suc y\<close>, \<^term>\<open>Suc x\<close>], [N (Refl, []), N (Refl, []),
   337      N (Let [@{term "Suc x"}, @{term "Suc y"}, @{term "Suc x"}],
   337      N (Let [\<^term>\<open>Suc x\<close>, \<^term>\<open>Suc y\<close>, \<^term>\<open>Suc x\<close>],
   338        [N (Refl, []), N (Refl, []), N (Refl, []), N (Refl, [])])])]));
   338        [N (Refl, []), N (Refl, []), N (Refl, []), N (Refl, [])])])]));
   339 
   339 
   340 reconstruct_proof @{context} proof12
   340 reconstruct_proof \<^context> proof12
   341 \<close>
   341 \<close>
   342 
   342 
   343 ML \<open>
   343 ML \<open>
   344 val proof13 =
   344 val proof13 =
   345   ((@{term "\<not> \<not> (let x = Suc x in x = 0)"},
   345   ((\<^term>\<open>\<not> \<not> (let x = Suc x in x = 0)\<close>,
   346     @{term "\<not> \<not> Suc x = 0"}),
   346     \<^term>\<open>\<not> \<not> Suc x = 0\<close>),
   347    N (Cong, [N (Cong, [N (Let [@{term "Suc x"}], [N (Refl, []), N (Refl, [])])])]));
   347    N (Cong, [N (Cong, [N (Let [\<^term>\<open>Suc x\<close>], [N (Refl, []), N (Refl, [])])])]));
   348 
   348 
   349 reconstruct_proof @{context} proof13
   349 reconstruct_proof \<^context> proof13
   350 \<close>
   350 \<close>
   351 
   351 
   352 ML \<open>
   352 ML \<open>
   353 val proof14 =
   353 val proof14 =
   354   ((@{term "let (x, y) = (f (a :: nat), b :: nat) in x > a"},
   354   ((\<^term>\<open>let (x, y) = (f (a :: nat), b :: nat) in x > a\<close>,
   355     @{term "f (a :: nat) > a"}),
   355     \<^term>\<open>f (a :: nat) > a\<close>),
   356    N (Let [@{term "f (a :: nat) :: nat"}, @{term "b :: nat"}],
   356    N (Let [\<^term>\<open>f (a :: nat) :: nat\<close>, \<^term>\<open>b :: nat\<close>],
   357      [N (Cong, [N (Refl, [])]), N (Refl, []), N (Refl, [])]));
   357      [N (Cong, [N (Refl, [])]), N (Refl, []), N (Refl, [])]));
   358 
   358 
   359 reconstruct_proof @{context} proof14
   359 reconstruct_proof \<^context> proof14
   360 \<close>
   360 \<close>
   361 
   361 
   362 ML \<open>
   362 ML \<open>
   363 val proof15 =
   363 val proof15 =
   364   ((@{term "let x = (let y = g (z :: nat) in f (y :: nat)) in x = Suc 0"},
   364   ((\<^term>\<open>let x = (let y = g (z :: nat) in f (y :: nat)) in x = Suc 0\<close>,
   365     @{term "f (g (z :: nat) :: nat) = Suc 0"}),
   365     \<^term>\<open>f (g (z :: nat) :: nat) = Suc 0\<close>),
   366    N (Let [@{term "f (g (z :: nat) :: nat) :: nat"}],
   366    N (Let [\<^term>\<open>f (g (z :: nat) :: nat) :: nat\<close>],
   367      [N (Let [@{term "g (z :: nat) :: nat"}], [N (Refl, []), N (Refl, [])]), N (Refl, [])]));
   367      [N (Let [\<^term>\<open>g (z :: nat) :: nat\<close>], [N (Refl, []), N (Refl, [])]), N (Refl, [])]));
   368 
   368 
   369 reconstruct_proof @{context} proof15
   369 reconstruct_proof \<^context> proof15
   370 \<close>
   370 \<close>
   371 
   371 
   372 ML \<open>
   372 ML \<open>
   373 val proof16 =
   373 val proof16 =
   374   ((@{term "a > Suc b"},
   374   ((\<^term>\<open>a > Suc b\<close>,
   375     @{term "a > Suc b"}),
   375     \<^term>\<open>a > Suc b\<close>),
   376    N (Trans @{term "a > Suc b"}, [N (Refl, []), N (Refl, [])]));
   376    N (Trans \<^term>\<open>a > Suc b\<close>, [N (Refl, []), N (Refl, [])]));
   377 
   377 
   378 reconstruct_proof @{context} proof16
   378 reconstruct_proof \<^context> proof16
   379 \<close>
   379 \<close>
   380 
   380 
   381 thm Suc_1
   381 thm Suc_1
   382 thm numeral_2_eq_2
   382 thm numeral_2_eq_2
   383 thm One_nat_def
   383 thm One_nat_def
   384 
   384 
   385 ML \<open>
   385 ML \<open>
   386 val proof17 =
   386 val proof17 =
   387   ((@{term "2 :: nat"},
   387   ((\<^term>\<open>2 :: nat\<close>,
   388     @{term "Suc (Suc 0) :: nat"}),
   388     \<^term>\<open>Suc (Suc 0) :: nat\<close>),
   389    N (Trans @{term "Suc 1"}, [N (Taut @{thm Suc_1[symmetric]}, []), N (Cong,
   389    N (Trans \<^term>\<open>Suc 1\<close>, [N (Taut @{thm Suc_1[symmetric]}, []), N (Cong,
   390      [N (Taut @{thm One_nat_def}, [])])]));
   390      [N (Taut @{thm One_nat_def}, [])])]));
   391 
   391 
   392 reconstruct_proof @{context} proof17
   392 reconstruct_proof \<^context> proof17
   393 \<close>
   393 \<close>
   394 
   394 
   395 ML \<open>
   395 ML \<open>
   396 val proof18 =
   396 val proof18 =
   397   ((@{term "let x = a in let y = b in Suc x + y"},
   397   ((\<^term>\<open>let x = a in let y = b in Suc x + y\<close>,
   398     @{term "Suc a + b"}),
   398     \<^term>\<open>Suc a + b\<close>),
   399    N (Trans @{term "let y = b in Suc a + y"},
   399    N (Trans \<^term>\<open>let y = b in Suc a + y\<close>,
   400      [N (Let [@{term "a :: nat"}], [N (Refl, []), N (Refl, [])]),
   400      [N (Let [\<^term>\<open>a :: nat\<close>], [N (Refl, []), N (Refl, [])]),
   401       N (Let [@{term "b :: nat"}], [N (Refl, []), N (Refl, [])])]));
   401       N (Let [\<^term>\<open>b :: nat\<close>], [N (Refl, []), N (Refl, [])])]));
   402 
   402 
   403 reconstruct_proof @{context} proof18
   403 reconstruct_proof \<^context> proof18
   404 \<close>
   404 \<close>
   405 
   405 
   406 ML \<open>
   406 ML \<open>
   407 val proof19 =
   407 val proof19 =
   408   ((@{term "\<forall>x. let x = f (x :: nat) :: nat in g x"},
   408   ((\<^term>\<open>\<forall>x. let x = f (x :: nat) :: nat in g x\<close>,
   409     @{term "\<forall>x. g (f (x :: nat) :: nat)"}),
   409     \<^term>\<open>\<forall>x. g (f (x :: nat) :: nat)\<close>),
   410    N (Bind, [N (Let [@{term "f :: nat \<Rightarrow> nat"} $ Bound 0],
   410    N (Bind, [N (Let [\<^term>\<open>f :: nat \<Rightarrow> nat\<close> $ Bound 0],
   411      [N (Refl, []), N (Refl, [])])]));
   411      [N (Refl, []), N (Refl, [])])]));
   412 
   412 
   413 reconstruct_proof @{context} proof19
   413 reconstruct_proof \<^context> proof19
   414 \<close>
   414 \<close>
   415 
   415 
   416 ML \<open>
   416 ML \<open>
   417 val proof20 =
   417 val proof20 =
   418   ((@{term "\<forall>x. let y = Suc 0 in let x = f (x :: nat) :: nat in g x"},
   418   ((\<^term>\<open>\<forall>x. let y = Suc 0 in let x = f (x :: nat) :: nat in g x\<close>,
   419     @{term "\<forall>x. g (f (x :: nat) :: nat)"}),
   419     \<^term>\<open>\<forall>x. g (f (x :: nat) :: nat)\<close>),
   420    N (Bind, [N (Let [@{term "Suc 0"}], [N (Refl, []), N (Let [@{term "f (x :: nat) :: nat"}],
   420    N (Bind, [N (Let [\<^term>\<open>Suc 0\<close>], [N (Refl, []), N (Let [\<^term>\<open>f (x :: nat) :: nat\<close>],
   421      [N (Refl, []), N (Refl, [])])])]));
   421      [N (Refl, []), N (Refl, [])])])]));
   422 
   422 
   423 reconstruct_proof @{context} proof20
   423 reconstruct_proof \<^context> proof20
   424 \<close>
   424 \<close>
   425 
   425 
   426 ML \<open>
   426 ML \<open>
   427 val proof21 =
   427 val proof21 =
   428   ((@{term "\<forall>x :: nat. let x = f x :: nat in let y = x in p y"},
   428   ((\<^term>\<open>\<forall>x :: nat. let x = f x :: nat in let y = x in p y\<close>,
   429     @{term "\<forall>z :: nat. p (f z :: nat)"}),
   429     \<^term>\<open>\<forall>z :: nat. p (f z :: nat)\<close>),
   430    N (Bind, [N (Let [@{term "f (z :: nat) :: nat"}],
   430    N (Bind, [N (Let [\<^term>\<open>f (z :: nat) :: nat\<close>],
   431      [N (Refl, []), N (Let [@{term "f (z :: nat) :: nat"}],
   431      [N (Refl, []), N (Let [\<^term>\<open>f (z :: nat) :: nat\<close>],
   432        [N (Refl, []), N (Refl, [])])])]));
   432        [N (Refl, []), N (Refl, [])])])]));
   433 
   433 
   434 reconstruct_proof @{context} proof21
   434 reconstruct_proof \<^context> proof21
   435 \<close>
   435 \<close>
   436 
   436 
   437 ML \<open>
   437 ML \<open>
   438 val proof22 =
   438 val proof22 =
   439   ((@{term "\<forall>x :: nat. let x = f x :: nat in let y = x in p y"},
   439   ((\<^term>\<open>\<forall>x :: nat. let x = f x :: nat in let y = x in p y\<close>,
   440     @{term "\<forall>x :: nat. p (f x :: nat)"}),
   440     \<^term>\<open>\<forall>x :: nat. p (f x :: nat)\<close>),
   441    N (Bind, [N (Let [@{term "f (x :: nat) :: nat"}],
   441    N (Bind, [N (Let [\<^term>\<open>f (x :: nat) :: nat\<close>],
   442      [N (Refl, []), N (Let [@{term "f (x :: nat) :: nat"}],
   442      [N (Refl, []), N (Let [\<^term>\<open>f (x :: nat) :: nat\<close>],
   443        [N (Refl, []), N (Refl, [])])])]));
   443        [N (Refl, []), N (Refl, [])])])]));
   444 
   444 
   445 reconstruct_proof @{context} proof22
   445 reconstruct_proof \<^context> proof22
   446 \<close>
   446 \<close>
   447 
   447 
   448 ML \<open>
   448 ML \<open>
   449 val proof23 =
   449 val proof23 =
   450   ((@{term "\<forall>x :: nat. let (x, a) = (f x :: nat, 0 ::nat) in let y = x in p y"},
   450   ((\<^term>\<open>\<forall>x :: nat. let (x, a) = (f x :: nat, 0 ::nat) in let y = x in p y\<close>,
   451     @{term "\<forall>z :: nat. p (f z :: nat)"}),
   451     \<^term>\<open>\<forall>z :: nat. p (f z :: nat)\<close>),
   452    N (Bind, [N (Let [@{term "f (z :: nat) :: nat"}, @{term "0 :: nat"}],
   452    N (Bind, [N (Let [\<^term>\<open>f (z :: nat) :: nat\<close>, \<^term>\<open>0 :: nat\<close>],
   453      [N (Refl, []), N (Refl, []), N (Let [@{term "f (z :: nat) :: nat"}],
   453      [N (Refl, []), N (Refl, []), N (Let [\<^term>\<open>f (z :: nat) :: nat\<close>],
   454        [N (Refl, []), N (Refl, [])])])]));
   454        [N (Refl, []), N (Refl, [])])])]));
   455 
   455 
   456 reconstruct_proof @{context} proof23
   456 reconstruct_proof \<^context> proof23
   457 \<close>
   457 \<close>
   458 
   458 
   459 ML \<open>
   459 ML \<open>
   460 val proof24 =
   460 val proof24 =
   461   ((@{term "\<forall>x :: nat. let (x, a) = (f x :: nat, 0 ::nat) in let y = x in p y"},
   461   ((\<^term>\<open>\<forall>x :: nat. let (x, a) = (f x :: nat, 0 ::nat) in let y = x in p y\<close>,
   462     @{term "\<forall>x :: nat. p (f x :: nat)"}),
   462     \<^term>\<open>\<forall>x :: nat. p (f x :: nat)\<close>),
   463    N (Bind, [N (Let [@{term "f (x :: nat) :: nat"}, @{term "0 :: nat"}],
   463    N (Bind, [N (Let [\<^term>\<open>f (x :: nat) :: nat\<close>, \<^term>\<open>0 :: nat\<close>],
   464      [N (Refl, []), N (Refl, []), N (Let [@{term "f (x :: nat) :: nat"}],
   464      [N (Refl, []), N (Refl, []), N (Let [\<^term>\<open>f (x :: nat) :: nat\<close>],
   465        [N (Refl, []), N (Refl, [])])])]));
   465        [N (Refl, []), N (Refl, [])])])]));
   466 
   466 
   467 reconstruct_proof @{context} proof24
   467 reconstruct_proof \<^context> proof24
   468 \<close>
   468 \<close>
   469 
   469 
   470 ML \<open>
   470 ML \<open>
   471 val proof25 =
   471 val proof25 =
   472   ((@{term "let vr0 = vr1 in let vr1 = vr2 in vr0 + vr1 + vr2 :: nat"},
   472   ((\<^term>\<open>let vr0 = vr1 in let vr1 = vr2 in vr0 + vr1 + vr2 :: nat\<close>,
   473     @{term "vr1 + vr2 + vr2 :: nat"}),
   473     \<^term>\<open>vr1 + vr2 + vr2 :: nat\<close>),
   474    N (Trans @{term "let vr1a = vr2 in vr1 + vr1a + vr2 :: nat"},
   474    N (Trans \<^term>\<open>let vr1a = vr2 in vr1 + vr1a + vr2 :: nat\<close>,
   475      [N (Let [@{term "vr1 :: nat"}], [N (Refl, []), N (Refl, [])]),
   475      [N (Let [\<^term>\<open>vr1 :: nat\<close>], [N (Refl, []), N (Refl, [])]),
   476       N (Let [@{term "vr2 :: nat"}], [N (Refl, []), N (Refl, [])])]));
   476       N (Let [\<^term>\<open>vr2 :: nat\<close>], [N (Refl, []), N (Refl, [])])]));
   477 
   477 
   478 reconstruct_proof @{context} proof25
   478 reconstruct_proof \<^context> proof25
   479 \<close>
   479 \<close>
   480 
   480 
   481 end
   481 end