OKlibrary  0.2.1.6
Backtracking.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 10.2.2008 (Swansea) */
00002 /* Copyright 2008 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00022 oklib_include("OKlib/ComputerAlgebra/Satisfiability/Lisp/PropositionalLogic/Formulas.mac");
00023 
00024 /* SAT-decision for formula trees by backtracking; the heuristics
00025   h has as input a formula tree and returns a literal (first set to true). */
00026 sat_backtracking_ft(F,h) := block([FS : basic_simplification_ft(F),x],
00027   if truefalse_ft(FS) then return(FS[1]),
00028   x : h(FS),
00029   return(sat_backtracking_ft(apply_pa_ft({x},FS),h) 
00030          or sat_backtracking_ft(apply_pa_ft({neg(x)},FS),h)))$
00031 
00032 trivial_heuristics_bft(F) := first(listify(var_ft(F)))$
00033 
00034 sat_backtracking_trivh_bft(F) := sat_backtracking_ft(F,trivial_heuristics_bft)$
00035 
00036 firstliteralheuristics_bft(F) := if length(F) = 1 then F[1]
00037  else firstliteralheuristics_bft(F[2])$
00038 
00039 sat_backtracking_firstlh_bft(F) := sat_backtracking_ft(F,firstliteralheuristics_bft)$
00040