src/HOL/Tools/sat_solver.ML
changeset 36692 54b64d4ad524
parent 35011 9e55e87434ff
child 37254 3625d37a0079
equal deleted inserted replaced
36674:d95f39448121 36692:54b64d4ad524
   348     (conjunction
   348     (conjunction
   349     o (map disjunction)
   349     o (map disjunction)
   350     o (map (map literal_from_int))
   350     o (map (map literal_from_int))
   351     o clauses
   351     o clauses
   352     o (map int_from_string)
   352     o (map int_from_string)
   353     o (maps (String.tokens (fn c => c mem [#" ", #"\t", #"\n"])))
   353     o (maps (String.tokens (member (op =) [#" ", #"\t", #"\n"])))
   354     o filter_preamble
   354     o filter_preamble
   355     o filter (fn l => l <> "")
   355     o filter (fn l => l <> "")
   356     o split_lines
   356     o split_lines
   357     o File.read)
   357     o File.read)
   358       path
   358       path
   419       else
   419       else
   420         (* set the lowest bit that wasn't set before, keep the higher bits *)
   420         (* set the lowest bit that wasn't set before, keep the higher bits *)
   421         SOME (y::x::xs)
   421         SOME (y::x::xs)
   422     (* int list -> int -> bool *)
   422     (* int list -> int -> bool *)
   423     fun assignment_from_list xs i =
   423     fun assignment_from_list xs i =
   424       i mem xs
   424       member (op =) xs i
   425     (* int list -> SatSolver.result *)
   425     (* int list -> SatSolver.result *)
   426     fun solver_loop xs =
   426     fun solver_loop xs =
   427       if PropLogic.eval (assignment_from_list xs) fm then
   427       if PropLogic.eval (assignment_from_list xs) fm then
   428         SatSolver.SATISFIABLE (SOME o (assignment_from_list xs))
   428         SatSolver.SATISFIABLE (SOME o (assignment_from_list xs))
   429       else
   429       else
   488           eval_and_force (xs@xs') fm'  (* xs and xs' should be distinct, so '@' here should have *)
   488           eval_and_force (xs@xs') fm'  (* xs and xs' should be distinct, so '@' here should have *)
   489                                        (* the same effect as 'union_int'                         *)
   489                                        (* the same effect as 'union_int'                         *)
   490       end
   490       end
   491       (* int list -> int option *)
   491       (* int list -> int option *)
   492       fun fresh_var xs =
   492       fun fresh_var xs =
   493         Library.find_first (fn i => not (i mem_int xs) andalso not ((~i) mem_int xs)) indices
   493         find_first (fn i => not (member (op =) xs i) andalso not (member (op =) xs (~i))) indices
   494       (* int list -> prop_formula -> int list option *)
   494       (* int list -> prop_formula -> int list option *)
   495       (* partial assignment 'xs' *)
   495       (* partial assignment 'xs' *)
   496       fun dpll xs fm =
   496       fun dpll xs fm =
   497       let
   497       let
   498         val (xs', fm') = eval_and_force xs fm
   498         val (xs', fm') = eval_and_force xs fm