src/HOL/Decision_Procs/Cooper.thy
changeset 69597 ff784d5a5bfb
parent 69266 7cc2d66a92a6
child 69605 a96320074298
equal deleted inserted replaced
69596:c8a2755bf220 69597:ff784d5a5bfb
  2387 
  2387 
  2388 fun num_of_term vs (t as Free (xn, xT)) =
  2388 fun num_of_term vs (t as Free (xn, xT)) =
  2389       (case AList.lookup (=) vs t of
  2389       (case AList.lookup (=) vs t of
  2390         NONE => error "Variable not found in the list!"
  2390         NONE => error "Variable not found in the list!"
  2391       | SOME n => @{code Bound} (@{code nat_of_integer} n))
  2391       | SOME n => @{code Bound} (@{code nat_of_integer} n))
  2392   | num_of_term vs @{term "0::int"} = @{code C} (@{code int_of_integer} 0)
  2392   | num_of_term vs \<^term>\<open>0::int\<close> = @{code C} (@{code int_of_integer} 0)
  2393   | num_of_term vs @{term "1::int"} = @{code C} (@{code int_of_integer} 1)
  2393   | num_of_term vs \<^term>\<open>1::int\<close> = @{code C} (@{code int_of_integer} 1)
  2394   | num_of_term vs @{term "- 1::int"} = @{code C} (@{code int_of_integer} (~ 1))
  2394   | num_of_term vs \<^term>\<open>- 1::int\<close> = @{code C} (@{code int_of_integer} (~ 1))
  2395   | num_of_term vs (@{term "numeral :: _ \<Rightarrow> int"} $ t) =
  2395   | num_of_term vs (\<^term>\<open>numeral :: _ \<Rightarrow> int\<close> $ t) =
  2396       @{code C} (@{code int_of_integer} (HOLogic.dest_numeral t))
  2396       @{code C} (@{code int_of_integer} (HOLogic.dest_numeral t))
  2397   | num_of_term vs (@{term "- numeral :: _ \<Rightarrow> int"} $ t) =
  2397   | num_of_term vs (\<^term>\<open>- numeral :: _ \<Rightarrow> int\<close> $ t) =
  2398       @{code C} (@{code int_of_integer} (~(HOLogic.dest_numeral t)))
  2398       @{code C} (@{code int_of_integer} (~(HOLogic.dest_numeral t)))
  2399   | num_of_term vs (Bound i) = @{code Bound} (@{code nat_of_integer} i)
  2399   | num_of_term vs (Bound i) = @{code Bound} (@{code nat_of_integer} i)
  2400   | num_of_term vs (@{term "uminus :: int \<Rightarrow> int"} $ t') = @{code Neg} (num_of_term vs t')
  2400   | num_of_term vs (\<^term>\<open>uminus :: int \<Rightarrow> int\<close> $ t') = @{code Neg} (num_of_term vs t')
  2401   | num_of_term vs (@{term "(+) :: int \<Rightarrow> int \<Rightarrow> int"} $ t1 $ t2) =
  2401   | num_of_term vs (\<^term>\<open>(+) :: int \<Rightarrow> int \<Rightarrow> int\<close> $ t1 $ t2) =
  2402       @{code Add} (num_of_term vs t1, num_of_term vs t2)
  2402       @{code Add} (num_of_term vs t1, num_of_term vs t2)
  2403   | num_of_term vs (@{term "(-) :: int \<Rightarrow> int \<Rightarrow> int"} $ t1 $ t2) =
  2403   | num_of_term vs (\<^term>\<open>(-) :: int \<Rightarrow> int \<Rightarrow> int\<close> $ t1 $ t2) =
  2404       @{code Sub} (num_of_term vs t1, num_of_term vs t2)
  2404       @{code Sub} (num_of_term vs t1, num_of_term vs t2)
  2405   | num_of_term vs (@{term "(*) :: int \<Rightarrow> int \<Rightarrow> int"} $ t1 $ t2) =
  2405   | num_of_term vs (\<^term>\<open>(*) :: int \<Rightarrow> int \<Rightarrow> int\<close> $ t1 $ t2) =
  2406       (case try HOLogic.dest_number t1 of
  2406       (case try HOLogic.dest_number t1 of
  2407         SOME (_, i) => @{code Mul} (@{code int_of_integer} i, num_of_term vs t2)
  2407         SOME (_, i) => @{code Mul} (@{code int_of_integer} i, num_of_term vs t2)
  2408       | NONE =>
  2408       | NONE =>
  2409           (case try HOLogic.dest_number t2 of
  2409           (case try HOLogic.dest_number t2 of
  2410             SOME (_, i) => @{code Mul} (@{code int_of_integer} i, num_of_term vs t1)
  2410             SOME (_, i) => @{code Mul} (@{code int_of_integer} i, num_of_term vs t1)
  2411           | NONE => error "num_of_term: unsupported multiplication"))
  2411           | NONE => error "num_of_term: unsupported multiplication"))
  2412   | num_of_term vs t = error ("num_of_term: unknown term " ^ Syntax.string_of_term @{context} t);
  2412   | num_of_term vs t = error ("num_of_term: unknown term " ^ Syntax.string_of_term \<^context> t);
  2413 
  2413 
  2414 fun fm_of_term ps vs @{term True} = @{code T}
  2414 fun fm_of_term ps vs \<^term>\<open>True\<close> = @{code T}
  2415   | fm_of_term ps vs @{term False} = @{code F}
  2415   | fm_of_term ps vs \<^term>\<open>False\<close> = @{code F}
  2416   | fm_of_term ps vs (@{term "(<) :: int \<Rightarrow> int \<Rightarrow> bool"} $ t1 $ t2) =
  2416   | fm_of_term ps vs (\<^term>\<open>(<) :: int \<Rightarrow> int \<Rightarrow> bool\<close> $ t1 $ t2) =
  2417       @{code Lt} (@{code Sub} (num_of_term vs t1, num_of_term vs t2))
  2417       @{code Lt} (@{code Sub} (num_of_term vs t1, num_of_term vs t2))
  2418   | fm_of_term ps vs (@{term "(\<le>) :: int \<Rightarrow> int \<Rightarrow> bool"} $ t1 $ t2) =
  2418   | fm_of_term ps vs (\<^term>\<open>(\<le>) :: int \<Rightarrow> int \<Rightarrow> bool\<close> $ t1 $ t2) =
  2419       @{code Le} (@{code Sub} (num_of_term vs t1, num_of_term vs t2))
  2419       @{code Le} (@{code Sub} (num_of_term vs t1, num_of_term vs t2))
  2420   | fm_of_term ps vs (@{term "(=) :: int \<Rightarrow> int \<Rightarrow> bool"} $ t1 $ t2) =
  2420   | fm_of_term ps vs (\<^term>\<open>(=) :: int \<Rightarrow> int \<Rightarrow> bool\<close> $ t1 $ t2) =
  2421       @{code Eq} (@{code Sub} (num_of_term vs t1, num_of_term vs t2))
  2421       @{code Eq} (@{code Sub} (num_of_term vs t1, num_of_term vs t2))
  2422   | fm_of_term ps vs (@{term "(dvd) :: int \<Rightarrow> int \<Rightarrow> bool"} $ t1 $ t2) =
  2422   | fm_of_term ps vs (\<^term>\<open>(dvd) :: int \<Rightarrow> int \<Rightarrow> bool\<close> $ t1 $ t2) =
  2423       (case try HOLogic.dest_number t1 of
  2423       (case try HOLogic.dest_number t1 of
  2424         SOME (_, i) => @{code Dvd} (@{code int_of_integer} i, num_of_term vs t2)
  2424         SOME (_, i) => @{code Dvd} (@{code int_of_integer} i, num_of_term vs t2)
  2425       | NONE => error "num_of_term: unsupported dvd")
  2425       | NONE => error "num_of_term: unsupported dvd")
  2426   | fm_of_term ps vs (@{term "(=) :: bool \<Rightarrow> bool \<Rightarrow> bool"} $ t1 $ t2) =
  2426   | fm_of_term ps vs (\<^term>\<open>(=) :: bool \<Rightarrow> bool \<Rightarrow> bool\<close> $ t1 $ t2) =
  2427       @{code Iff} (fm_of_term ps vs t1, fm_of_term ps vs t2)
  2427       @{code Iff} (fm_of_term ps vs t1, fm_of_term ps vs t2)
  2428   | fm_of_term ps vs (@{term HOL.conj} $ t1 $ t2) =
  2428   | fm_of_term ps vs (\<^term>\<open>HOL.conj\<close> $ t1 $ t2) =
  2429       @{code And} (fm_of_term ps vs t1, fm_of_term ps vs t2)
  2429       @{code And} (fm_of_term ps vs t1, fm_of_term ps vs t2)
  2430   | fm_of_term ps vs (@{term HOL.disj} $ t1 $ t2) =
  2430   | fm_of_term ps vs (\<^term>\<open>HOL.disj\<close> $ t1 $ t2) =
  2431       @{code Or} (fm_of_term ps vs t1, fm_of_term ps vs t2)
  2431       @{code Or} (fm_of_term ps vs t1, fm_of_term ps vs t2)
  2432   | fm_of_term ps vs (@{term HOL.implies} $ t1 $ t2) =
  2432   | fm_of_term ps vs (\<^term>\<open>HOL.implies\<close> $ t1 $ t2) =
  2433       @{code Imp} (fm_of_term ps vs t1, fm_of_term ps vs t2)
  2433       @{code Imp} (fm_of_term ps vs t1, fm_of_term ps vs t2)
  2434   | fm_of_term ps vs (@{term "Not"} $ t') =
  2434   | fm_of_term ps vs (\<^term>\<open>Not\<close> $ t') =
  2435       @{code NOT} (fm_of_term ps vs t')
  2435       @{code NOT} (fm_of_term ps vs t')
  2436   | fm_of_term ps vs (Const (@{const_name Ex}, _) $ Abs (xn, xT, p)) =
  2436   | fm_of_term ps vs (Const (\<^const_name>\<open>Ex\<close>, _) $ Abs (xn, xT, p)) =
  2437       let
  2437       let
  2438         val (xn', p') = Syntax_Trans.variant_abs (xn, xT, p);  (* FIXME !? *)
  2438         val (xn', p') = Syntax_Trans.variant_abs (xn, xT, p);  (* FIXME !? *)
  2439         val vs' = (Free (xn', xT), 0) :: map (fn (v, n) => (v, n + 1)) vs;
  2439         val vs' = (Free (xn', xT), 0) :: map (fn (v, n) => (v, n + 1)) vs;
  2440       in @{code E} (fm_of_term ps vs' p) end
  2440       in @{code E} (fm_of_term ps vs' p) end
  2441   | fm_of_term ps vs (Const (@{const_name All}, _) $ Abs (xn, xT, p)) =
  2441   | fm_of_term ps vs (Const (\<^const_name>\<open>All\<close>, _) $ Abs (xn, xT, p)) =
  2442       let
  2442       let
  2443         val (xn', p') = Syntax_Trans.variant_abs (xn, xT, p);  (* FIXME !? *)
  2443         val (xn', p') = Syntax_Trans.variant_abs (xn, xT, p);  (* FIXME !? *)
  2444         val vs' = (Free (xn', xT), 0) :: map (fn (v, n) => (v, n + 1)) vs;
  2444         val vs' = (Free (xn', xT), 0) :: map (fn (v, n) => (v, n + 1)) vs;
  2445       in @{code A} (fm_of_term ps vs' p) end
  2445       in @{code A} (fm_of_term ps vs' p) end
  2446   | fm_of_term ps vs t = error ("fm_of_term : unknown term " ^ Syntax.string_of_term @{context} t);
  2446   | fm_of_term ps vs t = error ("fm_of_term : unknown term " ^ Syntax.string_of_term \<^context> t);
  2447 
  2447 
  2448 fun term_of_num vs (@{code C} i) = HOLogic.mk_number HOLogic.intT (@{code integer_of_int} i)
  2448 fun term_of_num vs (@{code C} i) = HOLogic.mk_number HOLogic.intT (@{code integer_of_int} i)
  2449   | term_of_num vs (@{code Bound} n) =
  2449   | term_of_num vs (@{code Bound} n) =
  2450       let
  2450       let
  2451         val q = @{code integer_of_nat} n
  2451         val q = @{code integer_of_nat} n
  2452       in fst (the (find_first (fn (_, m) => q = m) vs)) end
  2452       in fst (the (find_first (fn (_, m) => q = m) vs)) end
  2453   | term_of_num vs (@{code Neg} t') = @{term "uminus :: int \<Rightarrow> int"} $ term_of_num vs t'
  2453   | term_of_num vs (@{code Neg} t') = \<^term>\<open>uminus :: int \<Rightarrow> int\<close> $ term_of_num vs t'
  2454   | term_of_num vs (@{code Add} (t1, t2)) = @{term "(+) :: int \<Rightarrow> int \<Rightarrow> int"} $
  2454   | term_of_num vs (@{code Add} (t1, t2)) = \<^term>\<open>(+) :: int \<Rightarrow> int \<Rightarrow> int\<close> $
  2455       term_of_num vs t1 $ term_of_num vs t2
  2455       term_of_num vs t1 $ term_of_num vs t2
  2456   | term_of_num vs (@{code Sub} (t1, t2)) = @{term "(-) :: int \<Rightarrow> int \<Rightarrow> int"} $
  2456   | term_of_num vs (@{code Sub} (t1, t2)) = \<^term>\<open>(-) :: int \<Rightarrow> int \<Rightarrow> int\<close> $
  2457       term_of_num vs t1 $ term_of_num vs t2
  2457       term_of_num vs t1 $ term_of_num vs t2
  2458   | term_of_num vs (@{code Mul} (i, t2)) = @{term "(*) :: int \<Rightarrow> int \<Rightarrow> int"} $
  2458   | term_of_num vs (@{code Mul} (i, t2)) = \<^term>\<open>(*) :: int \<Rightarrow> int \<Rightarrow> int\<close> $
  2459       term_of_num vs (@{code C} i) $ term_of_num vs t2
  2459       term_of_num vs (@{code C} i) $ term_of_num vs t2
  2460   | term_of_num vs (@{code CN} (n, i, t)) =
  2460   | term_of_num vs (@{code CN} (n, i, t)) =
  2461       term_of_num vs (@{code Add} (@{code Mul} (i, @{code Bound} n), t));
  2461       term_of_num vs (@{code Add} (@{code Mul} (i, @{code Bound} n), t));
  2462 
  2462 
  2463 fun term_of_fm ps vs @{code T} = @{term True}
  2463 fun term_of_fm ps vs @{code T} = \<^term>\<open>True\<close>
  2464   | term_of_fm ps vs @{code F} = @{term False}
  2464   | term_of_fm ps vs @{code F} = \<^term>\<open>False\<close>
  2465   | term_of_fm ps vs (@{code Lt} t) =
  2465   | term_of_fm ps vs (@{code Lt} t) =
  2466       @{term "(<) :: int \<Rightarrow> int \<Rightarrow> bool"} $ term_of_num vs t $ @{term "0::int"}
  2466       \<^term>\<open>(<) :: int \<Rightarrow> int \<Rightarrow> bool\<close> $ term_of_num vs t $ \<^term>\<open>0::int\<close>
  2467   | term_of_fm ps vs (@{code Le} t) =
  2467   | term_of_fm ps vs (@{code Le} t) =
  2468       @{term "(\<le>) :: int \<Rightarrow> int \<Rightarrow> bool"} $ term_of_num vs t $ @{term "0::int"}
  2468       \<^term>\<open>(\<le>) :: int \<Rightarrow> int \<Rightarrow> bool\<close> $ term_of_num vs t $ \<^term>\<open>0::int\<close>
  2469   | term_of_fm ps vs (@{code Gt} t) =
  2469   | term_of_fm ps vs (@{code Gt} t) =
  2470       @{term "(<) :: int \<Rightarrow> int \<Rightarrow> bool"} $ @{term "0::int"} $ term_of_num vs t
  2470       \<^term>\<open>(<) :: int \<Rightarrow> int \<Rightarrow> bool\<close> $ \<^term>\<open>0::int\<close> $ term_of_num vs t
  2471   | term_of_fm ps vs (@{code Ge} t) =
  2471   | term_of_fm ps vs (@{code Ge} t) =
  2472       @{term "(\<le>) :: int \<Rightarrow> int \<Rightarrow> bool"} $ @{term "0::int"} $ term_of_num vs t
  2472       \<^term>\<open>(\<le>) :: int \<Rightarrow> int \<Rightarrow> bool\<close> $ \<^term>\<open>0::int\<close> $ term_of_num vs t
  2473   | term_of_fm ps vs (@{code Eq} t) =
  2473   | term_of_fm ps vs (@{code Eq} t) =
  2474       @{term "(=) :: int \<Rightarrow> int \<Rightarrow> bool"} $ term_of_num vs t $ @{term "0::int"}
  2474       \<^term>\<open>(=) :: int \<Rightarrow> int \<Rightarrow> bool\<close> $ term_of_num vs t $ \<^term>\<open>0::int\<close>
  2475   | term_of_fm ps vs (@{code NEq} t) =
  2475   | term_of_fm ps vs (@{code NEq} t) =
  2476       term_of_fm ps vs (@{code NOT} (@{code Eq} t))
  2476       term_of_fm ps vs (@{code NOT} (@{code Eq} t))
  2477   | term_of_fm ps vs (@{code Dvd} (i, t)) =
  2477   | term_of_fm ps vs (@{code Dvd} (i, t)) =
  2478       @{term "(dvd) :: int \<Rightarrow> int \<Rightarrow> bool"} $ term_of_num vs (@{code C} i) $ term_of_num vs t
  2478       \<^term>\<open>(dvd) :: int \<Rightarrow> int \<Rightarrow> bool\<close> $ term_of_num vs (@{code C} i) $ term_of_num vs t
  2479   | term_of_fm ps vs (@{code NDvd} (i, t)) =
  2479   | term_of_fm ps vs (@{code NDvd} (i, t)) =
  2480       term_of_fm ps vs (@{code NOT} (@{code Dvd} (i, t)))
  2480       term_of_fm ps vs (@{code NOT} (@{code Dvd} (i, t)))
  2481   | term_of_fm ps vs (@{code NOT} t') =
  2481   | term_of_fm ps vs (@{code NOT} t') =
  2482       HOLogic.Not $ term_of_fm ps vs t'
  2482       HOLogic.Not $ term_of_fm ps vs t'
  2483   | term_of_fm ps vs (@{code And} (t1, t2)) =
  2483   | term_of_fm ps vs (@{code And} (t1, t2)) =
  2485   | term_of_fm ps vs (@{code Or} (t1, t2)) =
  2485   | term_of_fm ps vs (@{code Or} (t1, t2)) =
  2486       HOLogic.disj $ term_of_fm ps vs t1 $ term_of_fm ps vs t2
  2486       HOLogic.disj $ term_of_fm ps vs t1 $ term_of_fm ps vs t2
  2487   | term_of_fm ps vs (@{code Imp} (t1, t2)) =
  2487   | term_of_fm ps vs (@{code Imp} (t1, t2)) =
  2488       HOLogic.imp $ term_of_fm ps vs t1 $ term_of_fm ps vs t2
  2488       HOLogic.imp $ term_of_fm ps vs t1 $ term_of_fm ps vs t2
  2489   | term_of_fm ps vs (@{code Iff} (t1, t2)) =
  2489   | term_of_fm ps vs (@{code Iff} (t1, t2)) =
  2490       @{term "(=) :: bool \<Rightarrow> bool \<Rightarrow> bool"} $ term_of_fm ps vs t1 $ term_of_fm ps vs t2
  2490       \<^term>\<open>(=) :: bool \<Rightarrow> bool \<Rightarrow> bool\<close> $ term_of_fm ps vs t1 $ term_of_fm ps vs t2
  2491   | term_of_fm ps vs (@{code Closed} n) =
  2491   | term_of_fm ps vs (@{code Closed} n) =
  2492       let
  2492       let
  2493         val q = @{code integer_of_nat} n
  2493         val q = @{code integer_of_nat} n
  2494       in (fst o the) (find_first (fn (_, m) => m = q) ps) end
  2494       in (fst o the) (find_first (fn (_, m) => m = q) ps) end
  2495   | term_of_fm ps vs (@{code NClosed} n) = term_of_fm ps vs (@{code NOT} (@{code Closed} n));
  2495   | term_of_fm ps vs (@{code NClosed} n) = term_of_fm ps vs (@{code NOT} (@{code Closed} n));
  2496 
  2496 
  2497 fun term_bools acc t =
  2497 fun term_bools acc t =
  2498   let
  2498   let
  2499     val is_op =
  2499     val is_op =
  2500       member (=) [@{term HOL.conj}, @{term HOL.disj}, @{term HOL.implies},
  2500       member (=) [\<^term>\<open>HOL.conj\<close>, \<^term>\<open>HOL.disj\<close>, \<^term>\<open>HOL.implies\<close>,
  2501       @{term "(=) :: bool \<Rightarrow> _"},
  2501       \<^term>\<open>(=) :: bool \<Rightarrow> _\<close>,
  2502       @{term "(=) :: int \<Rightarrow> _"}, @{term "(<) :: int \<Rightarrow> _"},
  2502       \<^term>\<open>(=) :: int \<Rightarrow> _\<close>, \<^term>\<open>(<) :: int \<Rightarrow> _\<close>,
  2503       @{term "(\<le>) :: int \<Rightarrow> _"}, @{term "Not"}, @{term "All :: (int \<Rightarrow> _) \<Rightarrow> _"},
  2503       \<^term>\<open>(\<le>) :: int \<Rightarrow> _\<close>, \<^term>\<open>Not\<close>, \<^term>\<open>All :: (int \<Rightarrow> _) \<Rightarrow> _\<close>,
  2504       @{term "Ex :: (int \<Rightarrow> _) \<Rightarrow> _"}, @{term "True"}, @{term "False"}]
  2504       \<^term>\<open>Ex :: (int \<Rightarrow> _) \<Rightarrow> _\<close>, \<^term>\<open>True\<close>, \<^term>\<open>False\<close>]
  2505     fun is_ty t = not (fastype_of t = HOLogic.boolT)
  2505     fun is_ty t = not (fastype_of t = HOLogic.boolT)
  2506   in
  2506   in
  2507     (case t of
  2507     (case t of
  2508       (l as f $ a) $ b =>
  2508       (l as f $ a) $ b =>
  2509         if is_ty t orelse is_op t then term_bools (term_bools acc l) b
  2509         if is_ty t orelse is_op t then term_bools (term_bools acc l) b