equal
deleted
inserted
replaced
162 |
162 |
163 (* Thm.thm * (int * Thm.cterm) list -> Thm.thm * (int * Thm.cterm) list -> Thm.thm * (int * Thm.cterm) list *) |
163 (* Thm.thm * (int * Thm.cterm) list -> Thm.thm * (int * Thm.cterm) list -> Thm.thm * (int * Thm.cterm) list *) |
164 fun resolution (c1, hyps1) (c2, hyps2) = |
164 fun resolution (c1, hyps1) (c2, hyps2) = |
165 let |
165 let |
166 val _ = if !trace_sat then |
166 val _ = if !trace_sat then |
167 tracing ("Resolving clause: " ^ string_of_thm c1 ^ " (hyps: " ^ ML_Syntax.print_list (Sign.string_of_term (theory_of_thm c1)) (#hyps (rep_thm c1)) |
167 tracing ("Resolving clause: " ^ Display.string_of_thm c1 ^ " (hyps: " ^ ML_Syntax.print_list (Sign.string_of_term (theory_of_thm c1)) (#hyps (rep_thm c1)) |
168 ^ ")\nwith clause: " ^ string_of_thm c2 ^ " (hyps: " ^ ML_Syntax.print_list (Sign.string_of_term (theory_of_thm c2)) (#hyps (rep_thm c2)) ^ ")") |
168 ^ ")\nwith clause: " ^ Display.string_of_thm c2 ^ " (hyps: " ^ ML_Syntax.print_list (Sign.string_of_term (theory_of_thm c2)) (#hyps (rep_thm c2)) ^ ")") |
169 else () |
169 else () |
170 |
170 |
171 (* the two literals used for resolution *) |
171 (* the two literals used for resolution *) |
172 val (hyp1_is_neg, hyp1, hyp2, new_hyps) = find_res_hyps (hyps1, hyps2) [] |
172 val (hyp1_is_neg, hyp1, hyp2, new_hyps) = find_res_hyps (hyps1, hyps2) [] |
173 |
173 |
180 in |
180 in |
181 Thm.instantiate ([], [(cP, cLit)]) resolution_thm |
181 Thm.instantiate ([], [(cP, cLit)]) resolution_thm |
182 end |
182 end |
183 |
183 |
184 val _ = if !trace_sat then |
184 val _ = if !trace_sat then |
185 tracing ("Resolution theorem: " ^ string_of_thm res_thm) |
185 tracing ("Resolution theorem: " ^ Display.string_of_thm res_thm) |
186 else () |
186 else () |
187 |
187 |
188 (* Gamma1, Gamma2 |- False *) |
188 (* Gamma1, Gamma2 |- False *) |
189 val c_new = Thm.implies_elim |
189 val c_new = Thm.implies_elim |
190 (Thm.implies_elim res_thm (if hyp1_is_neg then c2' else c1')) |
190 (Thm.implies_elim res_thm (if hyp1_is_neg then c2' else c1')) |
191 (if hyp1_is_neg then c1' else c2') |
191 (if hyp1_is_neg then c1' else c2') |
192 |
192 |
193 val _ = if !trace_sat then |
193 val _ = if !trace_sat then |
194 tracing ("Resulting clause: " ^ string_of_thm c_new ^ " (hyps: " ^ ML_Syntax.print_list (Sign.string_of_term (theory_of_thm c_new)) (#hyps (rep_thm c_new)) ^ ")") |
194 tracing ("Resulting clause: " ^ Display.string_of_thm c_new ^ " (hyps: " ^ ML_Syntax.print_list (Sign.string_of_term (theory_of_thm c_new)) (#hyps (rep_thm c_new)) ^ ")") |
195 else () |
195 else () |
196 val _ = inc counter |
196 val _ = inc counter |
197 in |
197 in |
198 (c_new, new_hyps) |
198 (c_new, new_hyps) |
199 end |
199 end |
310 (* premises have been converted to clauses *) |
310 (* premises have been converted to clauses *) |
311 val clauses'' = filter (fn clause => |
311 val clauses'' = filter (fn clause => |
312 ((cnf.is_clause o HOLogic.dest_Trueprop o Thm.term_of) clause |
312 ((cnf.is_clause o HOLogic.dest_Trueprop o Thm.term_of) clause |
313 handle TERM ("dest_Trueprop", _) => false) |
313 handle TERM ("dest_Trueprop", _) => false) |
314 orelse ( |
314 orelse ( |
315 warning ("Ignoring non-clausal premise " ^ string_of_cterm clause); |
315 warning ("Ignoring non-clausal premise " ^ Display.string_of_cterm clause); |
316 false)) clauses' |
316 false)) clauses' |
317 (* remove trivial clauses -- this is necessary because zChaff removes *) |
317 (* remove trivial clauses -- this is necessary because zChaff removes *) |
318 (* trivial clauses during preprocessing, and otherwise our clause *) |
318 (* trivial clauses during preprocessing, and otherwise our clause *) |
319 (* numbering would be off *) |
319 (* numbering would be off *) |
320 val nontrivial_clauses = filter (not o cnf.clause_is_trivial o HOLogic.dest_Trueprop o Thm.term_of) clauses'' |
320 val nontrivial_clauses = filter (not o cnf.clause_is_trivial o HOLogic.dest_Trueprop o Thm.term_of) clauses'' |
323 (* Conjunction.intr_balanced and fold Thm.weaken below, is quadratic for *) |
323 (* Conjunction.intr_balanced and fold Thm.weaken below, is quadratic for *) |
324 (* terms sorted in descending order, while only linear for terms *) |
324 (* terms sorted in descending order, while only linear for terms *) |
325 (* sorted in ascending order *) |
325 (* sorted in ascending order *) |
326 val sorted_clauses = sort (Term.fast_term_ord o pairself Thm.term_of) nontrivial_clauses |
326 val sorted_clauses = sort (Term.fast_term_ord o pairself Thm.term_of) nontrivial_clauses |
327 val _ = if !trace_sat then |
327 val _ = if !trace_sat then |
328 tracing ("Sorted non-trivial clauses:\n" ^ space_implode "\n" (map string_of_cterm sorted_clauses)) |
328 tracing ("Sorted non-trivial clauses:\n" ^ space_implode "\n" (map Display.string_of_cterm sorted_clauses)) |
329 else () |
329 else () |
330 (* translate clauses from HOL terms to PropLogic.prop_formula *) |
330 (* translate clauses from HOL terms to PropLogic.prop_formula *) |
331 val (fms, atom_table) = fold_map (PropLogic.prop_formula_of_term o HOLogic.dest_Trueprop o Thm.term_of) sorted_clauses Termtab.empty |
331 val (fms, atom_table) = fold_map (PropLogic.prop_formula_of_term o HOLogic.dest_Trueprop o Thm.term_of) sorted_clauses Termtab.empty |
332 val _ = if !trace_sat then |
332 val _ = if !trace_sat then |
333 tracing ("Invoking SAT solver on clauses:\n" ^ space_implode "\n" (map string_of_prop_formula fms)) |
333 tracing ("Invoking SAT solver on clauses:\n" ^ space_implode "\n" (map string_of_prop_formula fms)) |