src/HOL/Decision_Procs/MIR.thy
changeset 69597 ff784d5a5bfb
parent 69325 4b6ddc5989fc
child 69605 a96320074298
equal deleted inserted replaced
69596:c8a2755bf220 69597:ff784d5a5bfb
  5573 val mk_Bound = @{code Bound} o @{code nat_of_integer};
  5573 val mk_Bound = @{code Bound} o @{code nat_of_integer};
  5574 
  5574 
  5575 fun num_of_term vs (t as Free (xn, xT)) = (case AList.lookup (=) vs t
  5575 fun num_of_term vs (t as Free (xn, xT)) = (case AList.lookup (=) vs t
  5576      of NONE => error "Variable not found in the list!"
  5576      of NONE => error "Variable not found in the list!"
  5577       | SOME n => mk_Bound n)
  5577       | SOME n => mk_Bound n)
  5578   | num_of_term vs @{term "of_int (0::int)"} = mk_C 0
  5578   | num_of_term vs \<^term>\<open>of_int (0::int)\<close> = mk_C 0
  5579   | num_of_term vs @{term "of_int (1::int)"} = mk_C 1
  5579   | num_of_term vs \<^term>\<open>of_int (1::int)\<close> = mk_C 1
  5580   | num_of_term vs @{term "0::real"} = mk_C 0
  5580   | num_of_term vs \<^term>\<open>0::real\<close> = mk_C 0
  5581   | num_of_term vs @{term "1::real"} = mk_C 1
  5581   | num_of_term vs \<^term>\<open>1::real\<close> = mk_C 1
  5582   | num_of_term vs @{term "- 1::real"} = mk_C (~ 1)
  5582   | num_of_term vs \<^term>\<open>- 1::real\<close> = mk_C (~ 1)
  5583   | num_of_term vs (Bound i) = mk_Bound i
  5583   | num_of_term vs (Bound i) = mk_Bound i
  5584   | num_of_term vs (@{term "uminus :: real \<Rightarrow> real"} $ t') = @{code Neg} (num_of_term vs t')
  5584   | num_of_term vs (\<^term>\<open>uminus :: real \<Rightarrow> real\<close> $ t') = @{code Neg} (num_of_term vs t')
  5585   | num_of_term vs (@{term "(+) :: real \<Rightarrow> real \<Rightarrow> real"} $ t1 $ t2) =
  5585   | num_of_term vs (\<^term>\<open>(+) :: real \<Rightarrow> real \<Rightarrow> real\<close> $ t1 $ t2) =
  5586       @{code Add} (num_of_term vs t1, num_of_term vs t2)
  5586       @{code Add} (num_of_term vs t1, num_of_term vs t2)
  5587   | num_of_term vs (@{term "(-) :: real \<Rightarrow> real \<Rightarrow> real"} $ t1 $ t2) =
  5587   | num_of_term vs (\<^term>\<open>(-) :: real \<Rightarrow> real \<Rightarrow> real\<close> $ t1 $ t2) =
  5588       @{code Sub} (num_of_term vs t1, num_of_term vs t2)
  5588       @{code Sub} (num_of_term vs t1, num_of_term vs t2)
  5589   | num_of_term vs (@{term "(*) :: real \<Rightarrow> real \<Rightarrow> real"} $ t1 $ t2) =
  5589   | num_of_term vs (\<^term>\<open>(*) :: real \<Rightarrow> real \<Rightarrow> real\<close> $ t1 $ t2) =
  5590       (case (num_of_term vs t1)
  5590       (case (num_of_term vs t1)
  5591        of @{code C} i => @{code Mul} (i, num_of_term vs t2)
  5591        of @{code C} i => @{code Mul} (i, num_of_term vs t2)
  5592         | _ => error "num_of_term: unsupported Multiplication")
  5592         | _ => error "num_of_term: unsupported Multiplication")
  5593   | num_of_term vs (@{term "of_int :: int \<Rightarrow> real"} $ (@{term "numeral :: _ \<Rightarrow> int"} $ t')) =
  5593   | num_of_term vs (\<^term>\<open>of_int :: int \<Rightarrow> real\<close> $ (\<^term>\<open>numeral :: _ \<Rightarrow> int\<close> $ t')) =
  5594       mk_C (HOLogic.dest_numeral t')
  5594       mk_C (HOLogic.dest_numeral t')
  5595   | num_of_term vs (@{term "of_int :: int \<Rightarrow> real"} $ (@{term "- numeral :: _ \<Rightarrow> int"} $ t')) =
  5595   | num_of_term vs (\<^term>\<open>of_int :: int \<Rightarrow> real\<close> $ (\<^term>\<open>- numeral :: _ \<Rightarrow> int\<close> $ t')) =
  5596       mk_C (~ (HOLogic.dest_numeral t'))
  5596       mk_C (~ (HOLogic.dest_numeral t'))
  5597   | num_of_term vs (@{term "of_int :: int \<Rightarrow> real"} $ (@{term "floor :: real \<Rightarrow> int"} $ t')) =
  5597   | num_of_term vs (\<^term>\<open>of_int :: int \<Rightarrow> real\<close> $ (\<^term>\<open>floor :: real \<Rightarrow> int\<close> $ t')) =
  5598       @{code Floor} (num_of_term vs t')
  5598       @{code Floor} (num_of_term vs t')
  5599   | num_of_term vs (@{term "of_int :: int \<Rightarrow> real"} $ (@{term "ceiling :: real \<Rightarrow> int"} $ t')) =
  5599   | num_of_term vs (\<^term>\<open>of_int :: int \<Rightarrow> real\<close> $ (\<^term>\<open>ceiling :: real \<Rightarrow> int\<close> $ t')) =
  5600       @{code Neg} (@{code Floor} (@{code Neg} (num_of_term vs t')))
  5600       @{code Neg} (@{code Floor} (@{code Neg} (num_of_term vs t')))
  5601   | num_of_term vs (@{term "numeral :: _ \<Rightarrow> real"} $ t') =
  5601   | num_of_term vs (\<^term>\<open>numeral :: _ \<Rightarrow> real\<close> $ t') =
  5602       mk_C (HOLogic.dest_numeral t')
  5602       mk_C (HOLogic.dest_numeral t')
  5603   | num_of_term vs (@{term "- numeral :: _ \<Rightarrow> real"} $ t') =
  5603   | num_of_term vs (\<^term>\<open>- numeral :: _ \<Rightarrow> real\<close> $ t') =
  5604       mk_C (~ (HOLogic.dest_numeral t'))
  5604       mk_C (~ (HOLogic.dest_numeral t'))
  5605   | num_of_term vs t = error ("num_of_term: unknown term " ^ Syntax.string_of_term @{context} t);
  5605   | num_of_term vs t = error ("num_of_term: unknown term " ^ Syntax.string_of_term \<^context> t);
  5606 
  5606 
  5607 fun fm_of_term vs @{term True} = @{code T}
  5607 fun fm_of_term vs \<^term>\<open>True\<close> = @{code T}
  5608   | fm_of_term vs @{term False} = @{code F}
  5608   | fm_of_term vs \<^term>\<open>False\<close> = @{code F}
  5609   | fm_of_term vs (@{term "(<) :: real \<Rightarrow> real \<Rightarrow> bool"} $ t1 $ t2) =
  5609   | fm_of_term vs (\<^term>\<open>(<) :: real \<Rightarrow> real \<Rightarrow> bool\<close> $ t1 $ t2) =
  5610       @{code Lt} (@{code Sub} (num_of_term vs t1, num_of_term vs t2))
  5610       @{code Lt} (@{code Sub} (num_of_term vs t1, num_of_term vs t2))
  5611   | fm_of_term vs (@{term "(\<le>) :: real \<Rightarrow> real \<Rightarrow> bool"} $ t1 $ t2) =
  5611   | fm_of_term vs (\<^term>\<open>(\<le>) :: real \<Rightarrow> real \<Rightarrow> bool\<close> $ t1 $ t2) =
  5612       @{code Le} (@{code Sub} (num_of_term vs t1, num_of_term vs t2))
  5612       @{code Le} (@{code Sub} (num_of_term vs t1, num_of_term vs t2))
  5613   | fm_of_term vs (@{term "(=) :: real \<Rightarrow> real \<Rightarrow> bool"} $ t1 $ t2) =
  5613   | fm_of_term vs (\<^term>\<open>(=) :: real \<Rightarrow> real \<Rightarrow> bool\<close> $ t1 $ t2) =
  5614       @{code Eq} (@{code Sub} (num_of_term vs t1, num_of_term vs t2))
  5614       @{code Eq} (@{code Sub} (num_of_term vs t1, num_of_term vs t2))
  5615   | fm_of_term vs (@{term "(rdvd)"} $ (@{term "of_int :: int \<Rightarrow> real"} $ (@{term "numeral :: _ \<Rightarrow> int"} $ t1)) $ t2) =
  5615   | fm_of_term vs (\<^term>\<open>(rdvd)\<close> $ (\<^term>\<open>of_int :: int \<Rightarrow> real\<close> $ (\<^term>\<open>numeral :: _ \<Rightarrow> int\<close> $ t1)) $ t2) =
  5616       mk_Dvd (HOLogic.dest_numeral t1, num_of_term vs t2)
  5616       mk_Dvd (HOLogic.dest_numeral t1, num_of_term vs t2)
  5617   | fm_of_term vs (@{term "(rdvd)"} $ (@{term "of_int :: int \<Rightarrow> real"} $ (@{term "- numeral :: _ \<Rightarrow> int"} $ t1)) $ t2) =
  5617   | fm_of_term vs (\<^term>\<open>(rdvd)\<close> $ (\<^term>\<open>of_int :: int \<Rightarrow> real\<close> $ (\<^term>\<open>- numeral :: _ \<Rightarrow> int\<close> $ t1)) $ t2) =
  5618       mk_Dvd (~ (HOLogic.dest_numeral t1), num_of_term vs t2)
  5618       mk_Dvd (~ (HOLogic.dest_numeral t1), num_of_term vs t2)
  5619   | fm_of_term vs (@{term "(=) :: bool \<Rightarrow> bool \<Rightarrow> bool"} $ t1 $ t2) =
  5619   | fm_of_term vs (\<^term>\<open>(=) :: bool \<Rightarrow> bool \<Rightarrow> bool\<close> $ t1 $ t2) =
  5620       @{code Iff} (fm_of_term vs t1, fm_of_term vs t2)
  5620       @{code Iff} (fm_of_term vs t1, fm_of_term vs t2)
  5621   | fm_of_term vs (@{term HOL.conj} $ t1 $ t2) =
  5621   | fm_of_term vs (\<^term>\<open>HOL.conj\<close> $ t1 $ t2) =
  5622       @{code And} (fm_of_term vs t1, fm_of_term vs t2)
  5622       @{code And} (fm_of_term vs t1, fm_of_term vs t2)
  5623   | fm_of_term vs (@{term HOL.disj} $ t1 $ t2) =
  5623   | fm_of_term vs (\<^term>\<open>HOL.disj\<close> $ t1 $ t2) =
  5624       @{code Or} (fm_of_term vs t1, fm_of_term vs t2)
  5624       @{code Or} (fm_of_term vs t1, fm_of_term vs t2)
  5625   | fm_of_term vs (@{term HOL.implies} $ t1 $ t2) =
  5625   | fm_of_term vs (\<^term>\<open>HOL.implies\<close> $ t1 $ t2) =
  5626       @{code Imp} (fm_of_term vs t1, fm_of_term vs t2)
  5626       @{code Imp} (fm_of_term vs t1, fm_of_term vs t2)
  5627   | fm_of_term vs (@{term "Not"} $ t') =
  5627   | fm_of_term vs (\<^term>\<open>Not\<close> $ t') =
  5628       @{code NOT} (fm_of_term vs t')
  5628       @{code NOT} (fm_of_term vs t')
  5629   | fm_of_term vs (Const (@{const_name Ex}, _) $ Abs (xn, xT, p)) =
  5629   | fm_of_term vs (Const (\<^const_name>\<open>Ex\<close>, _) $ Abs (xn, xT, p)) =
  5630       @{code E} (fm_of_term (map (fn (v, n) => (v, n + 1)) vs) p)
  5630       @{code E} (fm_of_term (map (fn (v, n) => (v, n + 1)) vs) p)
  5631   | fm_of_term vs (Const (@{const_name All}, _) $ Abs (xn, xT, p)) =
  5631   | fm_of_term vs (Const (\<^const_name>\<open>All\<close>, _) $ Abs (xn, xT, p)) =
  5632       @{code A} (fm_of_term (map (fn (v, n) => (v, n + 1)) vs) p)
  5632       @{code A} (fm_of_term (map (fn (v, n) => (v, n + 1)) vs) p)
  5633   | fm_of_term vs t = error ("fm_of_term : unknown term " ^ Syntax.string_of_term @{context} t);
  5633   | fm_of_term vs t = error ("fm_of_term : unknown term " ^ Syntax.string_of_term \<^context> t);
  5634 
  5634 
  5635 fun term_of_num vs (@{code C} i) = @{term "of_int :: int \<Rightarrow> real"} $
  5635 fun term_of_num vs (@{code C} i) = \<^term>\<open>of_int :: int \<Rightarrow> real\<close> $
  5636       HOLogic.mk_number HOLogic.intT (@{code integer_of_int} i)
  5636       HOLogic.mk_number HOLogic.intT (@{code integer_of_int} i)
  5637   | term_of_num vs (@{code Bound} n) =
  5637   | term_of_num vs (@{code Bound} n) =
  5638       let
  5638       let
  5639         val m = @{code integer_of_nat} n;
  5639         val m = @{code integer_of_nat} n;
  5640       in fst (the (find_first (fn (_, q) => m = q) vs)) end
  5640       in fst (the (find_first (fn (_, q) => m = q) vs)) end
  5641   | term_of_num vs (@{code Neg} (@{code Floor} (@{code Neg} t'))) =
  5641   | term_of_num vs (@{code Neg} (@{code Floor} (@{code Neg} t'))) =
  5642       @{term "of_int :: int \<Rightarrow> real"} $ (@{term "ceiling :: real \<Rightarrow> int"} $ term_of_num vs t')
  5642       \<^term>\<open>of_int :: int \<Rightarrow> real\<close> $ (\<^term>\<open>ceiling :: real \<Rightarrow> int\<close> $ term_of_num vs t')
  5643   | term_of_num vs (@{code Neg} t') = @{term "uminus :: real \<Rightarrow> real"} $ term_of_num vs t'
  5643   | term_of_num vs (@{code Neg} t') = \<^term>\<open>uminus :: real \<Rightarrow> real\<close> $ term_of_num vs t'
  5644   | term_of_num vs (@{code Add} (t1, t2)) = @{term "(+) :: real \<Rightarrow> real \<Rightarrow> real"} $
  5644   | term_of_num vs (@{code Add} (t1, t2)) = \<^term>\<open>(+) :: real \<Rightarrow> real \<Rightarrow> real\<close> $
  5645       term_of_num vs t1 $ term_of_num vs t2
  5645       term_of_num vs t1 $ term_of_num vs t2
  5646   | term_of_num vs (@{code Sub} (t1, t2)) = @{term "(-) :: real \<Rightarrow> real \<Rightarrow> real"} $
  5646   | term_of_num vs (@{code Sub} (t1, t2)) = \<^term>\<open>(-) :: real \<Rightarrow> real \<Rightarrow> real\<close> $
  5647       term_of_num vs t1 $ term_of_num vs t2
  5647       term_of_num vs t1 $ term_of_num vs t2
  5648   | term_of_num vs (@{code Mul} (i, t2)) = @{term "(*) :: real \<Rightarrow> real \<Rightarrow> real"} $
  5648   | term_of_num vs (@{code Mul} (i, t2)) = \<^term>\<open>(*) :: real \<Rightarrow> real \<Rightarrow> real\<close> $
  5649       term_of_num vs (@{code C} i) $ term_of_num vs t2
  5649       term_of_num vs (@{code C} i) $ term_of_num vs t2
  5650   | term_of_num vs (@{code Floor} t) = @{term "of_int :: int \<Rightarrow> real"} $ (@{term "floor :: real \<Rightarrow> int"} $ term_of_num vs t)
  5650   | term_of_num vs (@{code Floor} t) = \<^term>\<open>of_int :: int \<Rightarrow> real\<close> $ (\<^term>\<open>floor :: real \<Rightarrow> int\<close> $ term_of_num vs t)
  5651   | term_of_num vs (@{code CN} (n, i, t)) = term_of_num vs (@{code Add} (@{code Mul} (i, @{code Bound} n), t))
  5651   | term_of_num vs (@{code CN} (n, i, t)) = term_of_num vs (@{code Add} (@{code Mul} (i, @{code Bound} n), t))
  5652   | term_of_num vs (@{code CF} (c, t, s)) = term_of_num vs (@{code Add} (@{code Mul} (c, @{code Floor} t), s));
  5652   | term_of_num vs (@{code CF} (c, t, s)) = term_of_num vs (@{code Add} (@{code Mul} (c, @{code Floor} t), s));
  5653 
  5653 
  5654 fun term_of_fm vs @{code T} = @{term True}
  5654 fun term_of_fm vs @{code T} = \<^term>\<open>True\<close>
  5655   | term_of_fm vs @{code F} = @{term False}
  5655   | term_of_fm vs @{code F} = \<^term>\<open>False\<close>
  5656   | term_of_fm vs (@{code Lt} t) =
  5656   | term_of_fm vs (@{code Lt} t) =
  5657       @{term "(<) :: real \<Rightarrow> real \<Rightarrow> bool"} $ term_of_num vs t $ @{term "0::real"}
  5657       \<^term>\<open>(<) :: real \<Rightarrow> real \<Rightarrow> bool\<close> $ term_of_num vs t $ \<^term>\<open>0::real\<close>
  5658   | term_of_fm vs (@{code Le} t) =
  5658   | term_of_fm vs (@{code Le} t) =
  5659       @{term "(\<le>) :: real \<Rightarrow> real \<Rightarrow> bool"} $ term_of_num vs t $ @{term "0::real"}
  5659       \<^term>\<open>(\<le>) :: real \<Rightarrow> real \<Rightarrow> bool\<close> $ term_of_num vs t $ \<^term>\<open>0::real\<close>
  5660   | term_of_fm vs (@{code Gt} t) =
  5660   | term_of_fm vs (@{code Gt} t) =
  5661       @{term "(<) :: real \<Rightarrow> real \<Rightarrow> bool"} $ @{term "0::real"} $ term_of_num vs t
  5661       \<^term>\<open>(<) :: real \<Rightarrow> real \<Rightarrow> bool\<close> $ \<^term>\<open>0::real\<close> $ term_of_num vs t
  5662   | term_of_fm vs (@{code Ge} t) =
  5662   | term_of_fm vs (@{code Ge} t) =
  5663       @{term "(\<le>) :: real \<Rightarrow> real \<Rightarrow> bool"} $ @{term "0::real"} $ term_of_num vs t
  5663       \<^term>\<open>(\<le>) :: real \<Rightarrow> real \<Rightarrow> bool\<close> $ \<^term>\<open>0::real\<close> $ term_of_num vs t
  5664   | term_of_fm vs (@{code Eq} t) =
  5664   | term_of_fm vs (@{code Eq} t) =
  5665       @{term "(=) :: real \<Rightarrow> real \<Rightarrow> bool"} $ term_of_num vs t $ @{term "0::real"}
  5665       \<^term>\<open>(=) :: real \<Rightarrow> real \<Rightarrow> bool\<close> $ term_of_num vs t $ \<^term>\<open>0::real\<close>
  5666   | term_of_fm vs (@{code NEq} t) =
  5666   | term_of_fm vs (@{code NEq} t) =
  5667       term_of_fm vs (@{code NOT} (@{code Eq} t))
  5667       term_of_fm vs (@{code NOT} (@{code Eq} t))
  5668   | term_of_fm vs (@{code Dvd} (i, t)) =
  5668   | term_of_fm vs (@{code Dvd} (i, t)) =
  5669       @{term "(rdvd)"} $ term_of_num vs (@{code C} i) $ term_of_num vs t
  5669       \<^term>\<open>(rdvd)\<close> $ term_of_num vs (@{code C} i) $ term_of_num vs t
  5670   | term_of_fm vs (@{code NDvd} (i, t)) =
  5670   | term_of_fm vs (@{code NDvd} (i, t)) =
  5671       term_of_fm vs (@{code NOT} (@{code Dvd} (i, t)))
  5671       term_of_fm vs (@{code NOT} (@{code Dvd} (i, t)))
  5672   | term_of_fm vs (@{code NOT} t') =
  5672   | term_of_fm vs (@{code NOT} t') =
  5673       HOLogic.Not $ term_of_fm vs t'
  5673       HOLogic.Not $ term_of_fm vs t'
  5674   | term_of_fm vs (@{code And} (t1, t2)) =
  5674   | term_of_fm vs (@{code And} (t1, t2)) =
  5676   | term_of_fm vs (@{code Or} (t1, t2)) =
  5676   | term_of_fm vs (@{code Or} (t1, t2)) =
  5677       HOLogic.disj $ term_of_fm vs t1 $ term_of_fm vs t2
  5677       HOLogic.disj $ term_of_fm vs t1 $ term_of_fm vs t2
  5678   | term_of_fm vs (@{code Imp}  (t1, t2)) =
  5678   | term_of_fm vs (@{code Imp}  (t1, t2)) =
  5679       HOLogic.imp $ term_of_fm vs t1 $ term_of_fm vs t2
  5679       HOLogic.imp $ term_of_fm vs t1 $ term_of_fm vs t2
  5680   | term_of_fm vs (@{code Iff} (t1, t2)) =
  5680   | term_of_fm vs (@{code Iff} (t1, t2)) =
  5681       @{term "(=) :: bool \<Rightarrow> bool \<Rightarrow> bool"} $ term_of_fm vs t1 $ term_of_fm vs t2;
  5681       \<^term>\<open>(=) :: bool \<Rightarrow> bool \<Rightarrow> bool\<close> $ term_of_fm vs t1 $ term_of_fm vs t2;
  5682 
  5682 
  5683 in
  5683 in
  5684   fn (ctxt, t) =>
  5684   fn (ctxt, t) =>
  5685   let
  5685   let
  5686     val fs = Misc_Legacy.term_frees t;
  5686     val fs = Misc_Legacy.term_frees t;