src/HOL/Tools/sat_funcs.ML
changeset 26928 ca87aff1ad2d
parent 23590 ad95084a5c63
child 26931 aa226d8405a8
equal deleted inserted replaced
26927:8684b5240f11 26928:ca87aff1ad2d
   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))