author | paulson |
Fri, 03 Dec 2004 15:28:12 +0100 | |
changeset 15370 | 05b03ea0f18d |
parent 15359 | 8bad1f42fec0 |
child 15371 | 40f5045c5985 |
permissions | -rw-r--r-- |
15347 | 1 |
(* Author: Jia Meng, Cambridge University Computer Laboratory |
2 |
ID: $Id$ |
|
3 |
Copyright 2004 University of Cambridge |
|
4 |
||
5 |
Transformation of axiom rules (elim/intro/etc) into CNF forms. |
|
6 |
*) |
|
7 |
||
8 |
||
9 |
||
10 |
signature RES_ELIM_RULE = |
|
11 |
sig |
|
12 |
||
13 |
exception ELIMR2FOL of string |
|
14 |
val elimRule_tac : Thm.thm -> Tactical.tactic |
|
15 |
val elimR2Fol : Thm.thm -> Term.term |
|
16 |
val transform_elim : Thm.thm -> Thm.thm |
|
17 |
||
18 |
end; |
|
19 |
||
20 |
structure ResElimRule: RES_ELIM_RULE = |
|
21 |
||
22 |
struct |
|
23 |
||
24 |
||
25 |
fun elimRule_tac thm = |
|
26 |
((rtac impI 1) ORELSE (rtac notI 1)) THEN (etac thm 1) THEN |
|
27 |
REPEAT(Blast_tac 1); |
|
28 |
||
29 |
||
30 |
(* This following version fails sometimes, need to investigate, do not use it now. *) |
|
31 |
fun elimRule_tac' thm = |
|
32 |
((rtac impI 1) ORELSE (rtac notI 1)) THEN (etac thm 1) THEN |
|
33 |
REPEAT(SOLVE((etac exI 1) ORELSE (rtac conjI 1) ORELSE (rtac disjI1 1) ORELSE (rtac disjI2 1))); |
|
34 |
||
35 |
||
36 |
exception ELIMR2FOL of string; |
|
37 |
||
38 |
fun make_imp (prem,concl) = Const("op -->", Type("fun",[Type("bool",[]),Type("fun",[Type("bool",[]),Type("bool",[])])])) $ prem $ concl; |
|
39 |
||
40 |
||
41 |
fun make_disjs [x] = x |
|
42 |
| make_disjs (x :: xs) = Const("op |",Type("fun",[Type("bool",[]),Type("fun",[Type("bool",[]),Type("bool",[])])])) $ x $ (make_disjs xs) |
|
43 |
||
44 |
||
45 |
fun make_conjs [x] = x |
|
46 |
| make_conjs (x :: xs) = Const("op &", Type("fun",[Type("bool",[]),Type("fun",[Type("bool",[]),Type("bool",[])])])) $ x $ (make_conjs xs) |
|
47 |
||
48 |
||
49 |
fun add_EX term [] = term |
|
50 |
| add_EX term ((x,xtp)::xs) = add_EX (Const ("Ex",Type("fun",[Type("fun",[xtp,Type("bool",[])]),Type("bool",[])])) $ Abs (x,xtp,term)) xs; |
|
51 |
||
52 |
||
53 |
exception TRUEPROP of string; |
|
54 |
||
55 |
fun strip_trueprop (Const ("Trueprop", Type("fun",[Type("bool",[]),Type("prop",[])])) $ P) = P |
|
56 |
| strip_trueprop _ = raise TRUEPROP("not a prop!"); |
|
57 |
||
58 |
||
59 |
||
60 |
exception STRIP_CONCL; |
|
61 |
||
62 |
||
63 |
fun strip_concl prems bvs (Const ("all", _) $ Abs (x,xtp,body)) = strip_concl prems ((x,xtp)::bvs) body |
|
64 |
| strip_concl prems bvs (Const ("==>",_) $ P $ Q) = |
|
65 |
let val P' = strip_trueprop P |
|
66 |
val prems' = P'::prems |
|
67 |
in |
|
68 |
strip_concl prems' bvs Q |
|
69 |
end |
|
70 |
| strip_concl prems bvs _ = add_EX (make_conjs prems) bvs; |
|
71 |
||
72 |
||
73 |
||
74 |
fun trans_elim (main,others) = |
|
75 |
let val others' = map (strip_concl [] []) others |
|
76 |
val disjs = make_disjs others' |
|
77 |
in |
|
78 |
make_imp(strip_trueprop main,disjs) |
|
79 |
end; |
|
80 |
||
81 |
||
82 |
fun neg P = Const ("Not", Type("fun",[Type("bool",[]),Type("bool",[])])) $ P; |
|
83 |
||
84 |
||
85 |
fun elimR2Fol_aux prems = |
|
86 |
let val nprems = length prems |
|
87 |
val main = hd prems |
|
88 |
in |
|
89 |
if (nprems = 1) then neg (strip_trueprop main) |
|
90 |
else trans_elim (main, tl prems) |
|
91 |
end; |
|
92 |
||
93 |
||
94 |
fun trueprop term = Const ("Trueprop", Type("fun",[Type("bool",[]),Type("prop",[])])) $ term; |
|
95 |
||
96 |
||
97 |
fun elimR2Fol elimR = |
|
98 |
let val elimR' = Drule.freeze_all elimR |
|
99 |
val (prems,concl) = (prems_of elimR', concl_of elimR') |
|
100 |
in |
|
101 |
case concl of Const("Trueprop",_) $ Free(_,Type("bool",[])) |
|
102 |
=> trueprop (elimR2Fol_aux prems) |
|
103 |
| Free(x,Type("prop",[])) => trueprop(elimR2Fol_aux prems) |
|
104 |
| _ => raise ELIMR2FOL("Not an elimination rule!") |
|
105 |
end; |
|
106 |
||
107 |
||
108 |
||
109 |
||
110 |
(**** use prove_goalw_cterm to prove ****) |
|
111 |
||
112 |
fun transform_elim thm = |
|
113 |
let val tm = elimR2Fol thm |
|
114 |
val ctm = cterm_of (sign_of_thm thm) tm |
|
115 |
in |
|
116 |
prove_goalw_cterm [] ctm (fn prems => [elimRule_tac thm]) |
|
117 |
end; |
|
118 |
||
119 |
||
120 |
end; |
|
121 |
||
122 |
||
123 |
(* some lemmas *) |
|
124 |
||
125 |
Goal "(P==True) ==> P"; |
|
126 |
by(Blast_tac 1); |
|
127 |
qed "Eq_TrueD1"; |
|
128 |
||
129 |
Goal "(P=True) ==> P"; |
|
130 |
by(Blast_tac 1); |
|
131 |
qed "Eq_TrueD2"; |
|
132 |
||
133 |
Goal "(P==False) ==> ~P"; |
|
134 |
by(Blast_tac 1); |
|
135 |
qed "Eq_FalseD1"; |
|
136 |
||
137 |
Goal "(P=False) ==> ~P"; |
|
138 |
by(Blast_tac 1); |
|
139 |
qed "Eq_FalseD2"; |
|
140 |
||
15359
8bad1f42fec0
new CLAUSIFY attribute for proof reconstruction with lemmas
paulson
parents:
15347
diff
changeset
|
141 |
local |
15347 | 142 |
|
15359
8bad1f42fec0
new CLAUSIFY attribute for proof reconstruction with lemmas
paulson
parents:
15347
diff
changeset
|
143 |
fun prove s = prove_goal (the_context()) s (fn _ => [Simp_tac 1]); |
15347 | 144 |
|
15359
8bad1f42fec0
new CLAUSIFY attribute for proof reconstruction with lemmas
paulson
parents:
15347
diff
changeset
|
145 |
val small_simps = |
8bad1f42fec0
new CLAUSIFY attribute for proof reconstruction with lemmas
paulson
parents:
15347
diff
changeset
|
146 |
map prove |
8bad1f42fec0
new CLAUSIFY attribute for proof reconstruction with lemmas
paulson
parents:
15347
diff
changeset
|
147 |
["(P | True) == True", "(True | P) == True", |
8bad1f42fec0
new CLAUSIFY attribute for proof reconstruction with lemmas
paulson
parents:
15347
diff
changeset
|
148 |
"(P & True) == P", "(True & P) == P", |
8bad1f42fec0
new CLAUSIFY attribute for proof reconstruction with lemmas
paulson
parents:
15347
diff
changeset
|
149 |
"(False | P) == P", "(P | False) == P", |
8bad1f42fec0
new CLAUSIFY attribute for proof reconstruction with lemmas
paulson
parents:
15347
diff
changeset
|
150 |
"(False & P) == False", "(P & False) == False", |
8bad1f42fec0
new CLAUSIFY attribute for proof reconstruction with lemmas
paulson
parents:
15347
diff
changeset
|
151 |
"~True == False", "~False == True"]; |
8bad1f42fec0
new CLAUSIFY attribute for proof reconstruction with lemmas
paulson
parents:
15347
diff
changeset
|
152 |
in |
15347 | 153 |
|
15359
8bad1f42fec0
new CLAUSIFY attribute for proof reconstruction with lemmas
paulson
parents:
15347
diff
changeset
|
154 |
val small_simpset = empty_ss addsimps small_simps |
15347 | 155 |
|
15359
8bad1f42fec0
new CLAUSIFY attribute for proof reconstruction with lemmas
paulson
parents:
15347
diff
changeset
|
156 |
end; |
15347 | 157 |
|
158 |
||
159 |
signature RES_AXIOMS = |
|
160 |
sig |
|
161 |
||
162 |
val clausify_axiom : Thm.thm -> ResClause.clause list |
|
163 |
val cnf_axiom : Thm.thm -> Thm.thm list |
|
164 |
val cnf_elim : Thm.thm -> Thm.thm list |
|
165 |
val cnf_intro : Thm.thm -> Thm.thm list |
|
166 |
val cnf_rule : Thm.thm -> Thm.thm list |
|
167 |
val cnf_classical_rules_thy : Theory.theory -> Thm.thm list list * Thm.thm list |
|
168 |
val clausify_classical_rules_thy |
|
169 |
: Theory.theory -> ResClause.clause list list * Thm.thm list |
|
170 |
val cnf_simpset_rules_thy |
|
171 |
: Theory.theory -> Thm.thm list list * Thm.thm list |
|
172 |
val clausify_simpset_rules_thy |
|
173 |
: Theory.theory -> ResClause.clause list list * Thm.thm list |
|
174 |
val rm_Eps |
|
175 |
: (Term.term * Term.term) list -> Thm.thm list -> Term.term list |
|
176 |
end; |
|
177 |
||
178 |
structure ResAxioms : RES_AXIOMS = |
|
179 |
||
180 |
struct |
|
181 |
||
182 |
open ResElimRule; |
|
183 |
||
184 |
(* to be fixed: cnf_intro, cnf_rule, is_introR *) |
|
185 |
||
186 |
fun is_elimR thm = |
|
187 |
case (concl_of thm) of (Const ("Trueprop", _) $ Var (idx,_)) => true |
|
188 |
| Var(indx,Type("prop",[])) => true |
|
189 |
| _ => false; |
|
190 |
||
191 |
||
192 |
||
193 |
fun repeat_RS thm1 thm2 = |
|
194 |
let val thm1' = thm1 RS thm2 handle THM _ => thm1 |
|
195 |
in |
|
196 |
if eq_thm(thm1,thm1') then thm1' else (repeat_RS thm1' thm2) |
|
197 |
end; |
|
198 |
||
199 |
||
200 |
||
201 |
(* added this function to remove True/False in a theorem that is in NNF form. *) |
|
202 |
fun rm_TF_nnf thm = simplify small_simpset thm; |
|
203 |
||
204 |
fun skolem_axiom thm = |
|
205 |
let val thm' = (skolemize o rm_TF_nnf o make_nnf o ObjectLogic.atomize_thm o Drule.freeze_all) thm |
|
206 |
in |
|
207 |
repeat_RS thm' someI_ex |
|
208 |
end; |
|
209 |
||
210 |
||
211 |
fun isa_cls thm = |
|
212 |
let val thm' = skolem_axiom thm |
|
213 |
in |
|
214 |
map standard (make_clauses [thm']) |
|
215 |
end; |
|
216 |
||
217 |
||
218 |
fun cnf_elim thm = |
|
219 |
let val thm' = transform_elim thm; |
|
220 |
in |
|
221 |
isa_cls thm' |
|
222 |
end; |
|
223 |
||
224 |
||
225 |
val cnf_intro = isa_cls; |
|
226 |
val cnf_rule = isa_cls; |
|
227 |
||
228 |
||
229 |
fun is_introR thm = true; |
|
230 |
||
231 |
||
232 |
||
15370 | 233 |
(*Transfer a theorem in to theory Reconstruction.thy if it is not already |
15359
8bad1f42fec0
new CLAUSIFY attribute for proof reconstruction with lemmas
paulson
parents:
15347
diff
changeset
|
234 |
inside that theory -- because it's needed for Skolemization *) |
8bad1f42fec0
new CLAUSIFY attribute for proof reconstruction with lemmas
paulson
parents:
15347
diff
changeset
|
235 |
|
15370 | 236 |
val recon_thy = ThyInfo.get_theory"Reconstruction"; |
15359
8bad1f42fec0
new CLAUSIFY attribute for proof reconstruction with lemmas
paulson
parents:
15347
diff
changeset
|
237 |
|
15370 | 238 |
fun transfer_to_Reconstruction thm = |
239 |
transfer recon_thy thm handle THM _ => thm; |
|
15347 | 240 |
|
241 |
(* remove "True" clause *) |
|
242 |
fun rm_redundant_cls [] = [] |
|
243 |
| rm_redundant_cls (thm::thms) = |
|
244 |
let val t = prop_of thm |
|
245 |
in |
|
246 |
case t of (Const ("Trueprop", _) $ Const ("True", _)) => rm_redundant_cls thms |
|
247 |
| _ => thm::(rm_redundant_cls thms) |
|
248 |
end; |
|
249 |
||
250 |
(* transform an Isabelle thm into CNF *) |
|
251 |
fun cnf_axiom thm = |
|
15370 | 252 |
let val thm' = transfer_to_Reconstruction thm |
15347 | 253 |
val thm'' = if (is_elimR thm') then (cnf_elim thm') |
254 |
else (if (is_introR thm') then cnf_intro thm' else cnf_rule thm') |
|
255 |
in |
|
256 |
rm_redundant_cls thm'' |
|
257 |
end; |
|
258 |
||
259 |
||
260 |
(* changed: with one extra case added *) |
|
261 |
fun univ_vars_of_aux (Const ("Hilbert_Choice.Eps",_) $ Abs(_,_,body)) vars = univ_vars_of_aux body vars |
|
262 |
| univ_vars_of_aux (Const ("Ex",_) $ Abs(_,_,body)) vars = univ_vars_of_aux body vars (* EX x. body *) |
|
263 |
| univ_vars_of_aux (P $ Q) vars = |
|
264 |
let val vars' = univ_vars_of_aux P vars |
|
265 |
in |
|
266 |
univ_vars_of_aux Q vars' |
|
267 |
end |
|
268 |
| univ_vars_of_aux (t as Var(_,_)) vars = |
|
269 |
if (t mem vars) then vars else (t::vars) |
|
270 |
| univ_vars_of_aux _ vars = vars; |
|
271 |
||
272 |
||
273 |
fun univ_vars_of t = univ_vars_of_aux t []; |
|
274 |
||
275 |
||
276 |
fun get_new_skolem epss (t as (Const ("Hilbert_Choice.Eps",_) $ Abs(_,tp,_))) = |
|
277 |
let val all_vars = univ_vars_of t |
|
278 |
val sk_term = ResSkolemFunction.gen_skolem all_vars tp |
|
279 |
in |
|
280 |
(sk_term,(t,sk_term)::epss) |
|
281 |
end; |
|
282 |
||
283 |
||
284 |
fun sk_lookup [] t = None |
|
285 |
| sk_lookup ((tm,sk_tm)::tms) t = if (t = tm) then Some (sk_tm) else (sk_lookup tms t); |
|
286 |
||
287 |
||
288 |
fun get_skolem epss t = |
|
289 |
let val sk_fun = sk_lookup epss t |
|
290 |
in |
|
291 |
case sk_fun of None => get_new_skolem epss t |
|
292 |
| Some sk => (sk,epss) |
|
293 |
end; |
|
294 |
||
295 |
||
296 |
fun rm_Eps_cls_aux epss (t as (Const ("Hilbert_Choice.Eps",_) $ Abs(_,_,_))) = get_skolem epss t |
|
297 |
| rm_Eps_cls_aux epss (P $ Q) = |
|
298 |
let val (P',epss') = rm_Eps_cls_aux epss P |
|
299 |
val (Q',epss'') = rm_Eps_cls_aux epss' Q |
|
300 |
in |
|
301 |
(P' $ Q',epss'') |
|
302 |
end |
|
303 |
| rm_Eps_cls_aux epss t = (t,epss); |
|
304 |
||
305 |
||
306 |
fun rm_Eps_cls epss thm = |
|
307 |
let val tm = prop_of thm |
|
308 |
in |
|
309 |
rm_Eps_cls_aux epss tm |
|
310 |
end; |
|
311 |
||
312 |
||
313 |
||
314 |
fun rm_Eps _ [] = [] |
|
315 |
| rm_Eps epss (thm::thms) = |
|
316 |
let val (thm',epss') = rm_Eps_cls epss thm |
|
317 |
in |
|
318 |
thm' :: (rm_Eps epss' thms) |
|
319 |
end; |
|
320 |
||
321 |
||
322 |
||
323 |
(* changed, now it also finds out the name of the theorem. *) |
|
324 |
fun clausify_axiom thm = |
|
325 |
let val isa_clauses = cnf_axiom thm (*"isa_clauses" are already "standard"ed. *) |
|
326 |
val isa_clauses' = rm_Eps [] isa_clauses |
|
327 |
val thm_name = Thm.name_of_thm thm |
|
328 |
val clauses_n = length isa_clauses |
|
329 |
fun make_axiom_clauses _ [] = [] |
|
330 |
| make_axiom_clauses i (cls::clss) = (ResClause.make_axiom_clause cls (thm_name,i)) :: make_axiom_clauses (i+1) clss |
|
331 |
in |
|
332 |
make_axiom_clauses 0 isa_clauses' |
|
333 |
||
334 |
end; |
|
335 |
||
336 |
||
337 |
(******** Extracting and CNF/Clausify theorems from a classical reasoner and simpset of a given theory ******) |
|
338 |
||
339 |
||
340 |
local |
|
341 |
||
342 |
fun retr_thms ([]:MetaSimplifier.rrule list) = [] |
|
343 |
| retr_thms (r::rs) = (#thm r)::(retr_thms rs); |
|
344 |
||
345 |
||
346 |
fun snds [] = [] |
|
347 |
| snds ((x,y)::l) = y::(snds l); |
|
348 |
||
349 |
in |
|
350 |
||
351 |
||
352 |
fun claset_rules_of_thy thy = |
|
353 |
let val clsset = rep_cs (claset_of thy) |
|
354 |
val safeEs = #safeEs clsset |
|
355 |
val safeIs = #safeIs clsset |
|
356 |
val hazEs = #hazEs clsset |
|
357 |
val hazIs = #hazIs clsset |
|
358 |
in |
|
359 |
safeEs @ safeIs @ hazEs @ hazIs |
|
360 |
end; |
|
361 |
||
362 |
fun simpset_rules_of_thy thy = |
|
363 |
let val simpset = simpset_of thy |
|
364 |
val rules = #rules(fst (rep_ss simpset)) |
|
365 |
val thms = retr_thms (snds(Net.dest rules)) |
|
366 |
in |
|
367 |
thms |
|
368 |
end; |
|
369 |
||
370 |
end; |
|
371 |
||
372 |
||
373 |
(**** Translate a set of classical rules or simplifier rules into CNF (still as type "thm") from a given theory ****) |
|
374 |
||
375 |
(* classical rules *) |
|
376 |
fun cnf_classical_rules [] err_list = ([],err_list) |
|
377 |
| cnf_classical_rules (thm::thms) err_list = |
|
378 |
let val (ts,es) = cnf_classical_rules thms err_list |
|
379 |
in |
|
380 |
((cnf_axiom thm)::ts,es) handle _ => (ts,(thm::es)) |
|
381 |
end; |
|
382 |
||
383 |
||
384 |
(* CNF all rules from a given theory's classical reasoner *) |
|
385 |
fun cnf_classical_rules_thy thy = |
|
386 |
let val rules = claset_rules_of_thy thy |
|
387 |
in |
|
388 |
cnf_classical_rules rules [] |
|
389 |
end; |
|
390 |
||
391 |
||
392 |
(* simplifier rules *) |
|
393 |
fun cnf_simpset_rules [] err_list = ([],err_list) |
|
394 |
| cnf_simpset_rules (thm::thms) err_list = |
|
395 |
let val (ts,es) = cnf_simpset_rules thms err_list |
|
396 |
in |
|
397 |
((cnf_axiom thm)::ts,es) handle _ => (ts,(thm::es)) |
|
398 |
end; |
|
399 |
||
400 |
||
401 |
(* CNF all simplifier rules from a given theory's simpset *) |
|
402 |
fun cnf_simpset_rules_thy thy = |
|
403 |
let val thms = simpset_rules_of_thy thy |
|
404 |
in |
|
405 |
cnf_simpset_rules thms [] |
|
406 |
end; |
|
407 |
||
408 |
||
409 |
||
410 |
(**** Convert all theorems of a classical reason/simpset into clauses (ResClause.clause) ****) |
|
411 |
||
412 |
(* classical rules *) |
|
413 |
fun clausify_classical_rules [] err_list = ([],err_list) |
|
414 |
| clausify_classical_rules (thm::thms) err_list = |
|
415 |
let val (ts,es) = clausify_classical_rules thms err_list |
|
416 |
in |
|
417 |
((clausify_axiom thm)::ts,es) handle _ => (ts,(thm::es)) |
|
418 |
end; |
|
419 |
||
420 |
fun clausify_classical_rules_thy thy = |
|
421 |
let val rules = claset_rules_of_thy thy |
|
422 |
in |
|
423 |
clausify_classical_rules rules [] |
|
424 |
end; |
|
425 |
||
426 |
||
427 |
(* simplifier rules *) |
|
428 |
fun clausify_simpset_rules [] err_list = ([],err_list) |
|
429 |
| clausify_simpset_rules (thm::thms) err_list = |
|
430 |
let val (ts,es) = clausify_simpset_rules thms err_list |
|
431 |
in |
|
432 |
((clausify_axiom thm)::ts,es) handle _ => (ts,(thm::es)) |
|
433 |
end; |
|
434 |
||
435 |
||
436 |
fun clausify_simpset_rules_thy thy = |
|
437 |
let val thms = simpset_rules_of_thy thy |
|
438 |
in |
|
439 |
clausify_simpset_rules thms [] |
|
440 |
end; |
|
441 |
||
442 |
||
443 |
||
444 |
||
445 |
end; |