equal
deleted
inserted
replaced
9 sig |
9 sig |
10 val trace: bool Unsynchronized.ref |
10 val trace: bool Unsynchronized.ref |
11 val term_pair_of: indexname * (typ * 'a) -> term * 'a |
11 val term_pair_of: indexname * (typ * 'a) -> term * 'a |
12 val flexflex_first_order: thm -> thm |
12 val flexflex_first_order: thm -> thm |
13 val size_of_subgoals: thm -> int |
13 val size_of_subgoals: thm -> int |
14 val estimated_num_clauses: Proof.context -> int -> term -> int |
|
15 val has_too_many_clauses: Proof.context -> term -> bool |
14 val has_too_many_clauses: Proof.context -> term -> bool |
16 val make_cnf: thm list -> thm -> Proof.context -> thm list * Proof.context |
15 val make_cnf: thm list -> thm -> Proof.context -> thm list * Proof.context |
17 val finish_cnf: thm list -> thm list |
16 val finish_cnf: thm list -> thm list |
18 val presimplify: thm -> thm |
17 val presimplify: thm -> thm |
19 val make_nnf: Proof.context -> thm -> thm |
18 val make_nnf: Proof.context -> thm -> thm |
92 (**** Operators for forward proof ****) |
91 (**** Operators for forward proof ****) |
93 |
92 |
94 |
93 |
95 (** First-order Resolution **) |
94 (** First-order Resolution **) |
96 |
95 |
97 fun typ_pair_of (ix, (sort,ty)) = (TVar (ix,sort), ty); |
|
98 fun term_pair_of (ix, (ty,t)) = (Var (ix,ty), t); |
96 fun term_pair_of (ix, (ty,t)) = (Var (ix,ty), t); |
99 |
97 |
100 (*FIXME: currently does not "rename variables apart"*) |
98 (*FIXME: currently does not "rename variables apart"*) |
101 fun first_order_resolve thA thB = |
99 fun first_order_resolve thA thB = |
102 (case |
100 (case |
115 fun flexflex_first_order th = |
113 fun flexflex_first_order th = |
116 case Thm.tpairs_of th of |
114 case Thm.tpairs_of th of |
117 [] => th |
115 [] => th |
118 | pairs => |
116 | pairs => |
119 let val thy = theory_of_thm th |
117 let val thy = theory_of_thm th |
120 val (tyenv, tenv) = |
118 val (_, tenv) = |
121 fold (Pattern.first_order_match thy) pairs (Vartab.empty, Vartab.empty) |
119 fold (Pattern.first_order_match thy) pairs (Vartab.empty, Vartab.empty) |
122 val t_pairs = map term_pair_of (Vartab.dest tenv) |
120 val t_pairs = map term_pair_of (Vartab.dest tenv) |
123 val th' = Thm.instantiate ([], map (pairself (cterm_of thy)) t_pairs) th |
121 val th' = Thm.instantiate ([], map (pairself (cterm_of thy)) t_pairs) th |
124 in th' end |
122 in th' end |
125 handle THM _ => th; |
123 handle THM _ => th; |
152 | NONE => raise THM("forward_res", 0, [st]) |
150 | NONE => raise THM("forward_res", 0, [st]) |
153 end; |
151 end; |
154 |
152 |
155 (*Are any of the logical connectives in "bs" present in the term?*) |
153 (*Are any of the logical connectives in "bs" present in the term?*) |
156 fun has_conns bs = |
154 fun has_conns bs = |
157 let fun has (Const(a,_)) = false |
155 let fun has (Const _) = false |
158 | has (Const(@{const_name Trueprop},_) $ p) = has p |
156 | has (Const(@{const_name Trueprop},_) $ p) = has p |
159 | has (Const(@{const_name Not},_) $ p) = has p |
157 | has (Const(@{const_name Not},_) $ p) = has p |
160 | has (Const(@{const_name HOL.disj},_) $ p $ q) = member (op =) bs @{const_name HOL.disj} orelse has p orelse has q |
158 | has (Const(@{const_name HOL.disj},_) $ p $ q) = member (op =) bs @{const_name HOL.disj} orelse has p orelse has q |
161 | has (Const(@{const_name HOL.conj},_) $ p $ q) = member (op =) bs @{const_name HOL.conj} orelse has p orelse has q |
159 | has (Const(@{const_name HOL.conj},_) $ p $ q) = member (op =) bs @{const_name HOL.conj} orelse has p orelse has q |
162 | has (Const(@{const_name All},_) $ Abs(_,_,p)) = member (op =) bs @{const_name All} orelse has p |
160 | has (Const(@{const_name All},_) $ Abs(_,_,p)) = member (op =) bs @{const_name All} orelse has p |
236 |
234 |
237 |
235 |
238 (*** Removal of duplicate literals ***) |
236 (*** Removal of duplicate literals ***) |
239 |
237 |
240 (*Forward proof, passing extra assumptions as theorems to the tactic*) |
238 (*Forward proof, passing extra assumptions as theorems to the tactic*) |
241 fun forward_res2 ctxt nf hyps st = |
239 fun forward_res2 nf hyps st = |
242 case Seq.pull |
240 case Seq.pull |
243 (REPEAT |
241 (REPEAT |
244 (Misc_Legacy.METAHYPS (fn major::minors => rtac (nf (minors@hyps) major) 1) 1) |
242 (Misc_Legacy.METAHYPS (fn major::minors => rtac (nf (minors@hyps) major) 1) 1) |
245 st) |
243 st) |
246 of SOME(th,_) => th |
244 of SOME(th,_) => th |
248 |
246 |
249 (*Remove duplicates in P|Q by assuming ~P in Q |
247 (*Remove duplicates in P|Q by assuming ~P in Q |
250 rls (initially []) accumulates assumptions of the form P==>False*) |
248 rls (initially []) accumulates assumptions of the form P==>False*) |
251 fun nodups_aux ctxt rls th = nodups_aux ctxt rls (th RS disj_assoc) |
249 fun nodups_aux ctxt rls th = nodups_aux ctxt rls (th RS disj_assoc) |
252 handle THM _ => tryres(th,rls) |
250 handle THM _ => tryres(th,rls) |
253 handle THM _ => tryres(forward_res2 ctxt (nodups_aux ctxt) rls (th RS disj_forward2), |
251 handle THM _ => tryres(forward_res2 (nodups_aux ctxt) rls (th RS disj_forward2), |
254 [disj_FalseD1, disj_FalseD2, asm_rl]) |
252 [disj_FalseD1, disj_FalseD2, asm_rl]) |
255 handle THM _ => th; |
253 handle THM _ => th; |
256 |
254 |
257 (*Remove duplicate literals, if there are any*) |
255 (*Remove duplicate literals, if there are any*) |
258 fun nodups ctxt th = |
256 fun nodups ctxt th = |
261 else th; |
259 else th; |
262 |
260 |
263 |
261 |
264 (*** The basic CNF transformation ***) |
262 (*** The basic CNF transformation ***) |
265 |
263 |
266 fun estimated_num_clauses ctxt bound t = |
264 fun estimated_num_clauses bound t = |
267 let |
265 let |
268 fun sum x y = if x < bound andalso y < bound then x+y else bound |
266 fun sum x y = if x < bound andalso y < bound then x+y else bound |
269 fun prod x y = if x < bound andalso y < bound then x*y else bound |
267 fun prod x y = if x < bound andalso y < bound then x*y else bound |
270 |
268 |
271 (*Estimate the number of clauses in order to detect infeasible theorems*) |
269 (*Estimate the number of clauses in order to detect infeasible theorems*) |
292 | signed_nclauses _ _ = 1; (* literal *) |
290 | signed_nclauses _ _ = 1; (* literal *) |
293 in signed_nclauses true t end |
291 in signed_nclauses true t end |
294 |
292 |
295 fun has_too_many_clauses ctxt t = |
293 fun has_too_many_clauses ctxt t = |
296 let val max_cl = Config.get ctxt max_clauses in |
294 let val max_cl = Config.get ctxt max_clauses in |
297 estimated_num_clauses ctxt (max_cl + 1) t > max_cl |
295 estimated_num_clauses (max_cl + 1) t > max_cl |
298 end |
296 end |
299 |
297 |
300 (*Replaces universally quantified variables by FREE variables -- because |
298 (*Replaces universally quantified variables by FREE variables -- because |
301 assumptions may not contain scheme variables. Later, generalize using Variable.export. *) |
299 assumptions may not contain scheme variables. Later, generalize using Variable.export. *) |
302 local |
300 local |
446 else th; |
444 else th; |
447 |
445 |
448 (*Generate Horn clauses for all contrapositives of a clause. The input, th, |
446 (*Generate Horn clauses for all contrapositives of a clause. The input, th, |
449 is a HOL disjunction.*) |
447 is a HOL disjunction.*) |
450 fun add_contras crules th hcs = |
448 fun add_contras crules th hcs = |
451 let fun rots (0,th) = hcs |
449 let fun rots (0,_) = hcs |
452 | rots (k,th) = zero_var_indexes (make_horn crules th) :: |
450 | rots (k,th) = zero_var_indexes (make_horn crules th) :: |
453 rots(k-1, assoc_right (th RS disj_comm)) |
451 rots(k-1, assoc_right (th RS disj_comm)) |
454 in case nliterals(prop_of th) of |
452 in case nliterals(prop_of th) of |
455 1 => th::hcs |
453 1 => th::hcs |
456 | n => rots(n, assoc_right th) |
454 | n => rots(n, assoc_right th) |
637 (** Iterative deepening version **) |
635 (** Iterative deepening version **) |
638 |
636 |
639 (*This version does only one inference per call; |
637 (*This version does only one inference per call; |
640 having only one eq_assume_tac speeds it up!*) |
638 having only one eq_assume_tac speeds it up!*) |
641 fun prolog_step_tac' horns = |
639 fun prolog_step_tac' horns = |
642 let val (horn0s, hornps) = (*0 subgoals vs 1 or more*) |
640 let val (horn0s, _) = (*0 subgoals vs 1 or more*) |
643 take_prefix Thm.no_prems horns |
641 take_prefix Thm.no_prems horns |
644 val nrtac = net_resolve_tac horns |
642 val nrtac = net_resolve_tac horns |
645 in fn i => eq_assume_tac i ORELSE |
643 in fn i => eq_assume_tac i ORELSE |
646 match_tac horn0s i ORELSE (*no backtracking if unit MATCHES*) |
644 match_tac horn0s i ORELSE (*no backtracking if unit MATCHES*) |
647 ((assume_tac i APPEND nrtac i) THEN check_tac) |
645 ((assume_tac i APPEND nrtac i) THEN check_tac) |