|
1 (* Title: HOL/Tools/SMT2/z3_new_proof.ML |
|
2 Author: Sascha Boehme, TU Muenchen |
|
3 Author: Jasmin Blanchette, TU Muenchen |
|
4 |
|
5 Proof methods for replaying Z3 proofs. |
|
6 *) |
|
7 |
|
8 signature Z3_NEW_PROOF_METHODS = |
|
9 sig |
|
10 (*abstraction*) |
|
11 type abs_context = int * term Termtab.table |
|
12 type 'a abstracter = term -> abs_context -> 'a * abs_context |
|
13 val add_arith_abstracter: (term abstracter -> term option abstracter) -> |
|
14 Context.generic -> Context.generic |
|
15 |
|
16 (*theory lemma methods*) |
|
17 type th_lemma_method = Proof.context -> thm list -> term -> thm |
|
18 val add_th_lemma_method: string * th_lemma_method -> Context.generic -> |
|
19 Context.generic |
|
20 |
|
21 (*methods for Z3 proof rules*) |
|
22 type z3_method = Proof.context -> thm list -> term -> thm |
|
23 val true_axiom: z3_method |
|
24 val mp: z3_method |
|
25 val refl: z3_method |
|
26 val symm: z3_method |
|
27 val trans: z3_method |
|
28 val cong: z3_method |
|
29 val quant_intro: z3_method |
|
30 val distrib: z3_method |
|
31 val and_elim: z3_method |
|
32 val not_or_elim: z3_method |
|
33 val rewrite: z3_method |
|
34 val rewrite_star: z3_method |
|
35 val pull_quant: z3_method |
|
36 val push_quant: z3_method |
|
37 val elim_unused: z3_method |
|
38 val dest_eq_res: z3_method |
|
39 val quant_inst: z3_method |
|
40 val lemma: z3_method |
|
41 val unit_res: z3_method |
|
42 val iff_true: z3_method |
|
43 val iff_false: z3_method |
|
44 val comm: z3_method |
|
45 val def_axiom: z3_method |
|
46 val apply_def: z3_method |
|
47 val iff_oeq: z3_method |
|
48 val nnf_pos: z3_method |
|
49 val nnf_neg: z3_method |
|
50 val mp_oeq: z3_method |
|
51 val th_lemma: string -> z3_method |
|
52 val is_assumption: Z3_New_Proof.z3_rule -> bool |
|
53 val method_for: Z3_New_Proof.z3_rule -> z3_method |
|
54 end |
|
55 |
|
56 structure Z3_New_Proof_Methods: Z3_NEW_PROOF_METHODS = |
|
57 struct |
|
58 |
|
59 type z3_method = Proof.context -> thm list -> term -> thm |
|
60 |
|
61 |
|
62 |
|
63 (* utility functions *) |
|
64 |
|
65 val trace = SMT2_Config.trace_msg |
|
66 |
|
67 fun pretty_thm ctxt thm = Syntax.pretty_term ctxt (Thm.concl_of thm) |
|
68 |
|
69 fun pretty_goal ctxt msg rule thms t = |
|
70 let |
|
71 val full_msg = msg ^ ": " ^ quote (Z3_New_Proof.string_of_rule rule) |
|
72 val assms = |
|
73 if null thms then [] |
|
74 else [Pretty.big_list "assumptions:" (map (pretty_thm ctxt) thms)] |
|
75 val concl = Pretty.big_list "proposition:" [Syntax.pretty_term ctxt t] |
|
76 in Pretty.big_list full_msg (assms @ [concl]) end |
|
77 |
|
78 fun replay_error ctxt msg rule thms t = error (Pretty.string_of (pretty_goal ctxt msg rule thms t)) |
|
79 |
|
80 fun replay_rule_error ctxt = replay_error ctxt "Failed to replay Z3 proof step" |
|
81 |
|
82 fun trace_goal ctxt rule thms t = |
|
83 trace ctxt (fn () => Pretty.string_of (pretty_goal ctxt "Goal" rule thms t)) |
|
84 |
|
85 fun as_prop (t as Const (@{const_name Trueprop}, _) $ _) = t |
|
86 | as_prop t = HOLogic.mk_Trueprop t |
|
87 |
|
88 fun dest_prop (Const (@{const_name Trueprop}, _) $ t) = t |
|
89 | dest_prop t = t |
|
90 |
|
91 fun dest_thm thm = dest_prop (Thm.concl_of thm) |
|
92 |
|
93 fun certify_prop ctxt t = SMT2_Utils.certify ctxt (as_prop t) |
|
94 |
|
95 fun try_provers ctxt rule [] thms t = replay_rule_error ctxt rule thms t |
|
96 | try_provers ctxt rule ((name, prover) :: named_provers) thms t = |
|
97 (case (trace ctxt (K ("Trying prover " ^ quote name)); try prover t) of |
|
98 SOME thm => thm |
|
99 | NONE => try_provers ctxt rule named_provers thms t) |
|
100 |
|
101 fun match ctxt pat t = |
|
102 (Vartab.empty, Vartab.empty) |
|
103 |> Pattern.first_order_match (Proof_Context.theory_of ctxt) (pat, t) |
|
104 |
|
105 fun gen_certify_inst sel mk cert ctxt thm t = |
|
106 let |
|
107 val inst = match ctxt (dest_thm thm) (dest_prop t) |
|
108 fun cert_inst (ix, (a, b)) = (cert (mk (ix, a)), cert b) |
|
109 in Vartab.fold (cons o cert_inst) (sel inst) [] end |
|
110 |
|
111 fun match_instantiateT ctxt t thm = |
|
112 if Term.exists_type (Term.exists_subtype Term.is_TVar) (dest_thm thm) then |
|
113 let val certT = Thm.ctyp_of (Proof_Context.theory_of ctxt) |
|
114 in Thm.instantiate (gen_certify_inst fst TVar certT ctxt thm t, []) thm end |
|
115 else thm |
|
116 |
|
117 fun match_instantiate ctxt t thm = |
|
118 let |
|
119 val cert = SMT2_Utils.certify ctxt |
|
120 val thm' = match_instantiateT ctxt t thm |
|
121 in Thm.instantiate ([], gen_certify_inst snd Var cert ctxt thm' t) thm' end |
|
122 |
|
123 fun apply_rule ctxt t = |
|
124 (case Z3_New_Proof_Rules.apply ctxt (certify_prop ctxt t) of |
|
125 SOME thm => thm |
|
126 | NONE => raise Fail "apply_rule") |
|
127 |
|
128 fun discharge _ [] thm = thm |
|
129 | discharge i (rule :: rules) thm = discharge (i + Thm.nprems_of rule) rules (rule RSN (i, thm)) |
|
130 |
|
131 fun by_tac ctxt thms ns ts t tac = |
|
132 Goal.prove ctxt [] (map as_prop ts) (as_prop t) |
|
133 (fn {context, prems} => HEADGOAL (tac context prems)) |
|
134 |> Drule.generalize ([], ns) |
|
135 |> discharge 1 thms |
|
136 |
|
137 fun prove ctxt t tac = by_tac ctxt [] [] [] t (K o tac) |
|
138 |
|
139 fun prop_tac ctxt prems = |
|
140 Method.insert_tac prems THEN' (Classical.fast_tac ctxt ORELSE' Clasimp.force_tac ctxt) |
|
141 |
|
142 fun quant_tac ctxt = Blast.blast_tac ctxt |
|
143 |
|
144 |
|
145 |
|
146 (* plug-ins *) |
|
147 |
|
148 type abs_context = int * term Termtab.table |
|
149 |
|
150 type 'a abstracter = term -> abs_context -> 'a * abs_context |
|
151 |
|
152 type th_lemma_method = Proof.context -> thm list -> term -> thm |
|
153 |
|
154 fun id_ord ((id1, _), (id2, _)) = int_ord (id1, id2) |
|
155 |
|
156 structure Plugins = Generic_Data |
|
157 ( |
|
158 type T = |
|
159 (int * (term abstracter -> term option abstracter)) list * |
|
160 th_lemma_method Symtab.table |
|
161 val empty = ([], Symtab.empty) |
|
162 val extend = I |
|
163 fun merge ((abss1, ths1), (abss2, ths2)) = ( |
|
164 Ord_List.merge id_ord (abss1, abss2), |
|
165 Symtab.merge (K true) (ths1, ths2)) |
|
166 ) |
|
167 |
|
168 fun add_arith_abstracter abs = Plugins.map (apfst (Ord_List.insert id_ord (serial (), abs))) |
|
169 fun get_arith_abstracters ctxt = map snd (fst (Plugins.get (Context.Proof ctxt))) |
|
170 |
|
171 fun add_th_lemma_method method = Plugins.map (apsnd (Symtab.update_new method)) |
|
172 fun get_th_lemma_method ctxt = snd (Plugins.get (Context.Proof ctxt)) |
|
173 |
|
174 |
|
175 |
|
176 (* abstraction *) |
|
177 |
|
178 fun prove_abstract ctxt thms t tac f = |
|
179 let |
|
180 val ((prems, concl), (_, ts)) = f (1, Termtab.empty) |
|
181 val ns = Termtab.fold (fn (_, v) => cons (fst (Term.dest_Free v))) ts [] |
|
182 in |
|
183 by_tac ctxt [] ns prems concl tac |
|
184 |> match_instantiate ctxt t |
|
185 |> discharge 1 thms |
|
186 end |
|
187 |
|
188 fun prove_abstract' ctxt t tac f = |
|
189 prove_abstract ctxt [] t tac (f #>> pair []) |
|
190 |
|
191 fun lookup_term (_, terms) t = Termtab.lookup terms t |
|
192 |
|
193 fun abstract_sub t f cx = |
|
194 (case lookup_term cx t of |
|
195 SOME v => (v, cx) |
|
196 | NONE => f cx) |
|
197 |
|
198 fun mk_fresh_free t (i, terms) = |
|
199 let val v = Free ("t" ^ string_of_int i, fastype_of t) |
|
200 in (v, (i + 1, Termtab.update (t, v) terms)) end |
|
201 |
|
202 fun apply_abstracters _ [] _ cx = (NONE, cx) |
|
203 | apply_abstracters abs (abstracter :: abstracters) t cx = |
|
204 (case abstracter abs t cx of |
|
205 (NONE, _) => apply_abstracters abs abstracters t cx |
|
206 | x as (SOME _, _) => x) |
|
207 |
|
208 fun abstract_term (t as _ $ _) = abstract_sub t (mk_fresh_free t) |
|
209 | abstract_term (t as Abs _) = abstract_sub t (mk_fresh_free t) |
|
210 | abstract_term t = pair t |
|
211 |
|
212 fun abstract_bin abs f t t1 t2 = abstract_sub t (abs t1 ##>> abs t2 #>> f) |
|
213 |
|
214 fun abstract_ter abs f t t1 t2 t3 = |
|
215 abstract_sub t (abs t1 ##>> abs t2 ##>> abs t3 #>> (Parse.triple1 #> f)) |
|
216 |
|
217 fun abstract_lit (@{const HOL.Not} $ t) = abstract_term t #>> HOLogic.mk_not |
|
218 | abstract_lit t = abstract_term t |
|
219 |
|
220 fun abstract_not abs (t as @{const HOL.Not} $ t1) = |
|
221 abstract_sub t (abs t1 #>> HOLogic.mk_not) |
|
222 | abstract_not _ t = abstract_lit t |
|
223 |
|
224 fun abstract_conj (t as @{const HOL.conj} $ t1 $ t2) = |
|
225 abstract_bin abstract_conj HOLogic.mk_conj t t1 t2 |
|
226 | abstract_conj t = abstract_lit t |
|
227 |
|
228 fun abstract_disj (t as @{const HOL.disj} $ t1 $ t2) = |
|
229 abstract_bin abstract_disj HOLogic.mk_disj t t1 t2 |
|
230 | abstract_disj t = abstract_lit t |
|
231 |
|
232 fun abstract_prop (t as (c as @{const If (bool)}) $ t1 $ t2 $ t3) = |
|
233 abstract_ter abstract_prop (fn (t1, t2, t3) => c $ t1 $ t2 $ t3) t t1 t2 t3 |
|
234 | abstract_prop (t as @{const HOL.disj} $ t1 $ t2) = |
|
235 abstract_bin abstract_prop HOLogic.mk_disj t t1 t2 |
|
236 | abstract_prop (t as @{const HOL.conj} $ t1 $ t2) = |
|
237 abstract_bin abstract_prop HOLogic.mk_conj t t1 t2 |
|
238 | abstract_prop (t as @{const HOL.implies} $ t1 $ t2) = |
|
239 abstract_bin abstract_prop HOLogic.mk_imp t t1 t2 |
|
240 | abstract_prop (t as @{term "HOL.eq :: bool => _"} $ t1 $ t2) = |
|
241 abstract_bin abstract_prop HOLogic.mk_eq t t1 t2 |
|
242 | abstract_prop t = abstract_not abstract_prop t |
|
243 |
|
244 fun abstract_arith ctxt u = |
|
245 let |
|
246 fun abs (t as (c as Const _) $ Abs (s, T, t')) = |
|
247 abstract_sub t (abs t' #>> (fn u' => c $ Abs (s, T, u'))) |
|
248 | abs (t as (c as Const (@{const_name If}, _)) $ t1 $ t2 $ t3) = |
|
249 abstract_ter abs (fn (t1, t2, t3) => c $ t1 $ t2 $ t3) t t1 t2 t3 |
|
250 | abs (t as @{const HOL.Not} $ t1) = abstract_sub t (abs t1 #>> HOLogic.mk_not) |
|
251 | abs (t as @{const HOL.disj} $ t1 $ t2) = |
|
252 abstract_sub t (abs t1 ##>> abs t2 #>> HOLogic.mk_disj) |
|
253 | abs (t as (c as Const (@{const_name uminus_class.uminus}, _)) $ t1) = |
|
254 abstract_sub t (abs t1 #>> (fn u => c $ u)) |
|
255 | abs (t as (c as Const (@{const_name plus_class.plus}, _)) $ t1 $ t2) = |
|
256 abstract_sub t (abs t1 ##>> abs t2 #>> (fn (u1, u2) => c $ u1 $ u2)) |
|
257 | abs (t as (c as Const (@{const_name minus_class.minus}, _)) $ t1 $ t2) = |
|
258 abstract_sub t (abs t1 ##>> abs t2 #>> (fn (u1, u2) => c $ u1 $ u2)) |
|
259 | abs (t as (c as Const (@{const_name times_class.times}, _)) $ t1 $ t2) = |
|
260 abstract_sub t (abs t1 ##>> abs t2 #>> (fn (u1, u2) => c $ u1 $ u2)) |
|
261 | abs (t as (c as Const (@{const_name z3div}, _)) $ t1 $ t2) = |
|
262 abstract_sub t (abs t1 ##>> abs t2 #>> (fn (u1, u2) => c $ u1 $ u2)) |
|
263 | abs (t as (c as Const (@{const_name z3mod}, _)) $ t1 $ t2) = |
|
264 abstract_sub t (abs t1 ##>> abs t2 #>> (fn (u1, u2) => c $ u1 $ u2)) |
|
265 | abs (t as (c as Const (@{const_name HOL.eq}, _)) $ t1 $ t2) = |
|
266 abstract_sub t (abs t1 ##>> abs t2 #>> (fn (u1, u2) => c $ u1 $ u2)) |
|
267 | abs (t as (c as Const (@{const_name ord_class.less}, _)) $ t1 $ t2) = |
|
268 abstract_sub t (abs t1 ##>> abs t2 #>> (fn (u1, u2) => c $ u1 $ u2)) |
|
269 | abs (t as (c as Const (@{const_name ord_class.less_eq}, _)) $ t1 $ t2) = |
|
270 abstract_sub t (abs t1 ##>> abs t2 #>> (fn (u1, u2) => c $ u1 $ u2)) |
|
271 | abs t = abstract_sub t (fn cx => |
|
272 if can HOLogic.dest_number t then (t, cx) |
|
273 else |
|
274 (case apply_abstracters abs (get_arith_abstracters ctxt) t cx of |
|
275 (SOME u, cx') => (u, cx') |
|
276 | (NONE, _) => abstract_term t cx)) |
|
277 in abs u end |
|
278 |
|
279 |
|
280 |
|
281 (* truth axiom *) |
|
282 |
|
283 fun true_axiom _ _ _ = @{thm TrueI} |
|
284 |
|
285 |
|
286 |
|
287 (* modus ponens *) |
|
288 |
|
289 fun mp _ [p, p_eq_q] _ = discharge 1 [p_eq_q, p] iffD1 |
|
290 | mp ctxt thms t = replay_rule_error ctxt Z3_New_Proof.Modus_Ponens thms t |
|
291 |
|
292 val mp_oeq = mp |
|
293 |
|
294 |
|
295 |
|
296 (* reflexivity *) |
|
297 |
|
298 fun refl ctxt _ t = match_instantiate ctxt t @{thm refl} |
|
299 |
|
300 |
|
301 |
|
302 (* symmetry *) |
|
303 |
|
304 fun symm _ [thm] _ = thm RS @{thm sym} |
|
305 | symm ctxt thms t = replay_rule_error ctxt Z3_New_Proof.Reflexivity thms t |
|
306 |
|
307 |
|
308 |
|
309 (* transitivity *) |
|
310 |
|
311 fun trans _ [thm1, thm2] _ = thm1 RSN (1, thm2 RSN (2, @{thm trans})) |
|
312 | trans ctxt thms t = replay_rule_error ctxt Z3_New_Proof.Transitivity thms t |
|
313 |
|
314 |
|
315 |
|
316 (* congruence *) |
|
317 |
|
318 fun ctac prems i st = st |> ( |
|
319 resolve_tac (@{thm refl} :: prems) i |
|
320 ORELSE (cong_tac i THEN ctac prems (i + 1) THEN ctac prems i)) |
|
321 |
|
322 fun cong_basic ctxt thms t = |
|
323 let val st = Thm.trivial (certify_prop ctxt t) |
|
324 in |
|
325 (case Seq.pull (ctac thms 1 st) of |
|
326 SOME (thm, _) => thm |
|
327 | NONE => raise THM ("cong", 0, thms @ [st])) |
|
328 end |
|
329 |
|
330 val cong_dest_rules = @{lemma |
|
331 "(~ P | Q) & (P | ~ Q) ==> P = Q" |
|
332 "(P | ~ Q) & (~ P | Q) ==> P = Q" |
|
333 by fast+} |
|
334 |
|
335 fun cong_full ctxt thms t = prove ctxt t (fn ctxt' => |
|
336 Method.insert_tac thms |
|
337 THEN' (Classical.fast_tac ctxt' |
|
338 ORELSE' dresolve_tac cong_dest_rules |
|
339 THEN' Classical.fast_tac ctxt')) |
|
340 |
|
341 fun cong ctxt thms = try_provers ctxt Z3_New_Proof.Monotonicity [ |
|
342 ("basic", cong_basic ctxt thms), |
|
343 ("full", cong_full ctxt thms)] thms |
|
344 |
|
345 |
|
346 |
|
347 (* quantifier introduction *) |
|
348 |
|
349 val quant_intro_rules = @{lemma |
|
350 "(!!x. P x = Q x) ==> (ALL x. P x) = (ALL x. Q x)" |
|
351 "(!!x. P x = Q x) ==> (EX x. P x) = (EX x. Q x)" |
|
352 "(!!x. (~ P x) = Q x) ==> (~ (EX x. P x)) = (ALL x. Q x)" |
|
353 "(!!x. (~ P x) = Q x) ==> (~ (ALL x. P x)) = (EX x. Q x)" |
|
354 by fast+} |
|
355 |
|
356 fun quant_intro ctxt [thm] t = |
|
357 prove ctxt t (K (REPEAT_ALL_NEW (resolve_tac (thm :: quant_intro_rules)))) |
|
358 | quant_intro ctxt thms t = replay_rule_error ctxt Z3_New_Proof.Quant_Intro thms t |
|
359 |
|
360 |
|
361 |
|
362 (* distributivity of conjunctions and disjunctions *) |
|
363 |
|
364 (* TODO: there are no tests with this proof rule *) |
|
365 fun distrib ctxt _ t = |
|
366 prove_abstract' ctxt t prop_tac (abstract_prop (dest_prop t)) |
|
367 |
|
368 |
|
369 |
|
370 (* elimination of conjunctions *) |
|
371 |
|
372 fun and_elim ctxt [thm] t = |
|
373 prove_abstract ctxt [thm] t prop_tac ( |
|
374 abstract_lit (dest_prop t) ##>> |
|
375 abstract_conj (dest_thm thm) #>> |
|
376 apfst single o swap) |
|
377 | and_elim ctxt thms t = replay_rule_error ctxt Z3_New_Proof.And_Elim thms t |
|
378 |
|
379 |
|
380 |
|
381 (* elimination of negated disjunctions *) |
|
382 |
|
383 fun not_or_elim ctxt [thm] t = |
|
384 prove_abstract ctxt [thm] t prop_tac ( |
|
385 abstract_lit (dest_prop t) ##>> |
|
386 abstract_not abstract_disj (dest_thm thm) #>> |
|
387 apfst single o swap) |
|
388 | not_or_elim ctxt thms t = |
|
389 replay_rule_error ctxt Z3_New_Proof.Not_Or_Elim thms t |
|
390 |
|
391 |
|
392 |
|
393 (* rewriting *) |
|
394 |
|
395 fun abstract_eq f1 f2 (Const (@{const_name HOL.eq}, _) $ t1 $ t2) = |
|
396 f1 t1 ##>> f2 t2 #>> HOLogic.mk_eq |
|
397 | abstract_eq _ _ t = abstract_term t |
|
398 |
|
399 fun prove_prop_rewrite ctxt t = |
|
400 prove_abstract' ctxt t prop_tac ( |
|
401 abstract_eq abstract_prop abstract_prop (dest_prop t)) |
|
402 |
|
403 fun arith_rewrite_tac ctxt _ = |
|
404 TRY o Simplifier.simp_tac ctxt |
|
405 THEN_ALL_NEW (Arith_Data.arith_tac ctxt ORELSE' Clasimp.force_tac ctxt) |
|
406 |
|
407 fun prove_arith_rewrite ctxt t = |
|
408 prove_abstract' ctxt t arith_rewrite_tac ( |
|
409 abstract_eq (abstract_arith ctxt) (abstract_arith ctxt) (dest_prop t)) |
|
410 |
|
411 fun rewrite ctxt _ = try_provers ctxt Z3_New_Proof.Rewrite [ |
|
412 ("rules", apply_rule ctxt), |
|
413 ("prop_rewrite", prove_prop_rewrite ctxt), |
|
414 ("arith_rewrite", prove_arith_rewrite ctxt)] [] |
|
415 |
|
416 fun rewrite_star ctxt = rewrite ctxt |
|
417 |
|
418 |
|
419 |
|
420 (* pulling quantifiers *) |
|
421 |
|
422 fun pull_quant ctxt _ t = prove ctxt t quant_tac |
|
423 |
|
424 |
|
425 |
|
426 (* pushing quantifiers *) |
|
427 |
|
428 fun push_quant _ _ _ = raise Fail "unsupported" (* FIXME *) |
|
429 |
|
430 |
|
431 |
|
432 (* elimination of unused bound variables *) |
|
433 |
|
434 val elim_all = @{lemma "P = Q ==> (ALL x. P) = Q" by fast} |
|
435 val elim_ex = @{lemma "P = Q ==> (EX x. P) = Q" by fast} |
|
436 |
|
437 fun elim_unused_tac i st = ( |
|
438 match_tac [@{thm refl}] |
|
439 ORELSE' (match_tac [elim_all, elim_ex] THEN' elim_unused_tac) |
|
440 ORELSE' ( |
|
441 match_tac [@{thm iff_allI}, @{thm iff_exI}] |
|
442 THEN' elim_unused_tac)) i st |
|
443 |
|
444 fun elim_unused ctxt _ t = prove ctxt t (fn _ => elim_unused_tac) |
|
445 |
|
446 |
|
447 |
|
448 (* destructive equality resolution *) |
|
449 |
|
450 fun dest_eq_res _ _ _ = raise Fail "dest_eq_res" (* FIXME *) |
|
451 |
|
452 |
|
453 |
|
454 (* quantifier instantiation *) |
|
455 |
|
456 val quant_inst_rule = @{lemma "~P x | Q ==> ~(ALL x. P x) | Q" by fast} |
|
457 |
|
458 fun quant_inst ctxt _ t = prove ctxt t (fn _ => |
|
459 REPEAT_ALL_NEW (rtac quant_inst_rule) |
|
460 THEN' rtac @{thm excluded_middle}) |
|
461 |
|
462 |
|
463 |
|
464 (* propositional lemma *) |
|
465 |
|
466 exception LEMMA of unit |
|
467 |
|
468 val intro_hyp_rule1 = @{lemma "(~P ==> Q) ==> P | Q" by fast} |
|
469 val intro_hyp_rule2 = @{lemma "(P ==> Q) ==> ~P | Q" by fast} |
|
470 |
|
471 fun norm_lemma thm = |
|
472 (thm COMP_INCR intro_hyp_rule1) |
|
473 handle THM _ => thm COMP_INCR intro_hyp_rule2 |
|
474 |
|
475 fun negated_prop (@{const HOL.Not} $ t) = HOLogic.mk_Trueprop t |
|
476 | negated_prop t = HOLogic.mk_Trueprop (HOLogic.mk_not t) |
|
477 |
|
478 fun intro_hyps tab (t as @{const HOL.disj} $ t1 $ t2) cx = |
|
479 lookup_intro_hyps tab t (fold (intro_hyps tab) [t1, t2]) cx |
|
480 | intro_hyps tab t cx = |
|
481 lookup_intro_hyps tab t (fn _ => raise LEMMA ()) cx |
|
482 |
|
483 and lookup_intro_hyps tab t f (cx as (thm, terms)) = |
|
484 (case Termtab.lookup tab (negated_prop t) of |
|
485 NONE => f cx |
|
486 | SOME hyp => (norm_lemma (Thm.implies_intr hyp thm), t :: terms)) |
|
487 |
|
488 fun lemma ctxt (thms as [thm]) t = |
|
489 (let |
|
490 val tab = Termtab.make (map (`Thm.term_of) (#hyps (Thm.crep_thm thm))) |
|
491 val (thm', terms) = intro_hyps tab (dest_prop t) (thm, []) |
|
492 in |
|
493 prove_abstract ctxt [thm'] t prop_tac ( |
|
494 fold (snd oo abstract_lit) terms #> |
|
495 abstract_disj (dest_thm thm') #>> single ##>> |
|
496 abstract_disj (dest_prop t)) |
|
497 end |
|
498 handle LEMMA () => replay_error ctxt "Bad proof state" Z3_New_Proof.Lemma thms t) |
|
499 | lemma ctxt thms t = replay_rule_error ctxt Z3_New_Proof.Lemma thms t |
|
500 |
|
501 |
|
502 |
|
503 (* unit resolution *) |
|
504 |
|
505 fun abstract_unit (t as (@{const HOL.Not} $ (@{const HOL.disj} $ t1 $ t2))) = |
|
506 abstract_sub t (abstract_unit t1 ##>> abstract_unit t2 #>> |
|
507 HOLogic.mk_not o HOLogic.mk_disj) |
|
508 | abstract_unit (t as (@{const HOL.disj} $ t1 $ t2)) = |
|
509 abstract_sub t (abstract_unit t1 ##>> abstract_unit t2 #>> |
|
510 HOLogic.mk_disj) |
|
511 | abstract_unit t = abstract_lit t |
|
512 |
|
513 fun unit_res ctxt thms t = |
|
514 prove_abstract ctxt thms t prop_tac ( |
|
515 fold_map (abstract_unit o dest_thm) thms ##>> |
|
516 abstract_unit (dest_prop t) #>> |
|
517 (fn (prems, concl) => (prems, concl))) |
|
518 |
|
519 |
|
520 |
|
521 (* iff-true *) |
|
522 |
|
523 val iff_true_rule = @{lemma "P ==> P = True" by fast} |
|
524 |
|
525 fun iff_true _ [thm] _ = thm RS iff_true_rule |
|
526 | iff_true ctxt thms t = replay_rule_error ctxt Z3_New_Proof.Iff_True thms t |
|
527 |
|
528 |
|
529 |
|
530 (* iff-false *) |
|
531 |
|
532 val iff_false_rule = @{lemma "~P ==> P = False" by fast} |
|
533 |
|
534 fun iff_false _ [thm] _ = thm RS iff_false_rule |
|
535 | iff_false ctxt thms t = replay_rule_error ctxt Z3_New_Proof.Iff_False thms t |
|
536 |
|
537 |
|
538 |
|
539 (* commutativity *) |
|
540 |
|
541 fun comm ctxt _ t = match_instantiate ctxt t @{thm eq_commute} |
|
542 |
|
543 |
|
544 |
|
545 (* definitional axioms *) |
|
546 |
|
547 fun def_axiom_disj ctxt t = |
|
548 (case dest_prop t of |
|
549 @{const HOL.disj} $ u1 $ u2 => |
|
550 prove_abstract' ctxt t prop_tac ( |
|
551 abstract_prop u2 ##>> abstract_prop u1 #>> HOLogic.mk_disj o swap) |
|
552 | u => prove_abstract' ctxt t prop_tac (abstract_prop u)) |
|
553 |
|
554 fun def_axiom ctxt _ = try_provers ctxt Z3_New_Proof.Def_Axiom [ |
|
555 ("rules", apply_rule ctxt), |
|
556 ("disj", def_axiom_disj ctxt)] [] |
|
557 |
|
558 |
|
559 |
|
560 (* application of definitions *) |
|
561 |
|
562 fun apply_def _ [thm] _ = thm (* TODO: cover also the missing cases *) |
|
563 | apply_def ctxt thms t = replay_rule_error ctxt Z3_New_Proof.Apply_Def thms t |
|
564 |
|
565 |
|
566 |
|
567 (* iff-oeq *) |
|
568 |
|
569 fun iff_oeq _ _ _ = raise Fail "iff_oeq" (* FIXME *) |
|
570 |
|
571 |
|
572 |
|
573 (* negation normal form *) |
|
574 |
|
575 fun nnf_prop ctxt thms t = |
|
576 prove_abstract ctxt thms t prop_tac ( |
|
577 fold_map (abstract_prop o dest_thm) thms ##>> |
|
578 abstract_prop (dest_prop t)) |
|
579 |
|
580 fun nnf ctxt rule thms = try_provers ctxt rule [ |
|
581 ("prop", nnf_prop ctxt thms), |
|
582 ("quant", quant_intro ctxt [hd thms])] thms |
|
583 |
|
584 fun nnf_pos ctxt = nnf ctxt Z3_New_Proof.Nnf_Pos |
|
585 fun nnf_neg ctxt = nnf ctxt Z3_New_Proof.Nnf_Neg |
|
586 |
|
587 |
|
588 |
|
589 (* theory lemmas *) |
|
590 |
|
591 fun arith_th_lemma_tac ctxt prems = |
|
592 Method.insert_tac prems |
|
593 THEN' SELECT_GOAL (Local_Defs.unfold_tac ctxt @{thms z3div_def z3mod_def}) |
|
594 THEN' Arith_Data.arith_tac ctxt |
|
595 |
|
596 fun arith_th_lemma ctxt thms t = |
|
597 prove_abstract ctxt thms t arith_th_lemma_tac ( |
|
598 fold_map (abstract_arith ctxt o dest_thm) thms ##>> |
|
599 abstract_arith ctxt (dest_prop t)) |
|
600 |
|
601 val _ = Theory.setup (Context.theory_map (add_th_lemma_method ("arith", arith_th_lemma))) |
|
602 |
|
603 fun th_lemma name ctxt thms = |
|
604 (case Symtab.lookup (get_th_lemma_method ctxt) name of |
|
605 SOME method => method ctxt thms |
|
606 | NONE => replay_error ctxt "Bad theory" (Z3_New_Proof.Th_Lemma name) thms) |
|
607 |
|
608 |
|
609 |
|
610 (* mapping of rules to methods *) |
|
611 |
|
612 fun is_assumption Z3_New_Proof.Asserted = true |
|
613 | is_assumption Z3_New_Proof.Goal = true |
|
614 | is_assumption Z3_New_Proof.Hypothesis = true |
|
615 | is_assumption Z3_New_Proof.Intro_Def = true |
|
616 | is_assumption Z3_New_Proof.Skolemize = true |
|
617 | is_assumption _ = false |
|
618 |
|
619 fun unsupported rule ctxt = replay_error ctxt "Unsupported" rule |
|
620 fun assumed rule ctxt = replay_error ctxt "Assumed" rule |
|
621 |
|
622 fun choose Z3_New_Proof.True_Axiom = true_axiom |
|
623 | choose (r as Z3_New_Proof.Asserted) = assumed r |
|
624 | choose (r as Z3_New_Proof.Goal) = assumed r |
|
625 | choose Z3_New_Proof.Modus_Ponens = mp |
|
626 | choose Z3_New_Proof.Reflexivity = refl |
|
627 | choose Z3_New_Proof.Symmetry = symm |
|
628 | choose Z3_New_Proof.Transitivity = trans |
|
629 | choose (r as Z3_New_Proof.Transitivity_Star) = unsupported r |
|
630 | choose Z3_New_Proof.Monotonicity = cong |
|
631 | choose Z3_New_Proof.Quant_Intro = quant_intro |
|
632 | choose Z3_New_Proof.Distributivity = distrib |
|
633 | choose Z3_New_Proof.And_Elim = and_elim |
|
634 | choose Z3_New_Proof.Not_Or_Elim = not_or_elim |
|
635 | choose Z3_New_Proof.Rewrite = rewrite |
|
636 | choose Z3_New_Proof.Rewrite_Star = rewrite_star |
|
637 | choose Z3_New_Proof.Pull_Quant = pull_quant |
|
638 | choose (r as Z3_New_Proof.Pull_Quant_Star) = unsupported r |
|
639 | choose Z3_New_Proof.Push_Quant = push_quant |
|
640 | choose Z3_New_Proof.Elim_Unused_Vars = elim_unused |
|
641 | choose Z3_New_Proof.Dest_Eq_Res = dest_eq_res |
|
642 | choose Z3_New_Proof.Quant_Inst = quant_inst |
|
643 | choose (r as Z3_New_Proof.Hypothesis) = assumed r |
|
644 | choose Z3_New_Proof.Lemma = lemma |
|
645 | choose Z3_New_Proof.Unit_Resolution = unit_res |
|
646 | choose Z3_New_Proof.Iff_True = iff_true |
|
647 | choose Z3_New_Proof.Iff_False = iff_false |
|
648 | choose Z3_New_Proof.Commutativity = comm |
|
649 | choose Z3_New_Proof.Def_Axiom = def_axiom |
|
650 | choose (r as Z3_New_Proof.Intro_Def) = assumed r |
|
651 | choose Z3_New_Proof.Apply_Def = apply_def |
|
652 | choose Z3_New_Proof.Iff_Oeq = iff_oeq |
|
653 | choose Z3_New_Proof.Nnf_Pos = nnf_pos |
|
654 | choose Z3_New_Proof.Nnf_Neg = nnf_neg |
|
655 | choose (r as Z3_New_Proof.Nnf_Star) = unsupported r |
|
656 | choose (r as Z3_New_Proof.Cnf_Star) = unsupported r |
|
657 | choose (r as Z3_New_Proof.Skolemize) = assumed r |
|
658 | choose Z3_New_Proof.Modus_Ponens_Oeq = mp_oeq |
|
659 | choose (Z3_New_Proof.Th_Lemma name) = th_lemma name |
|
660 |
|
661 fun with_tracing rule method ctxt thms t = |
|
662 let val _ = trace_goal ctxt rule thms t |
|
663 in method ctxt thms t end |
|
664 |
|
665 fun method_for rule = with_tracing rule (choose rule) |
|
666 |
|
667 end |