{-# LANGUAGE ScopedTypeVariables #-} {-# OPTIONS_GHC -Wall #-} module Data.Logic.Harrison.Resolution ( resolution1 , resolution2 , resolution3 , presolution , matchAtomsEq ) where import Data.Logic.Classes.Atom (Atom(match)) import Data.Logic.Classes.Combine (Combination(..)) import Data.Logic.Classes.Equals (AtomEq, zipAtomsEq) import Data.Logic.Classes.FirstOrder (FirstOrderFormula(..), zipFirstOrder) import Data.Logic.Classes.Literal (Literal) import Data.Logic.Classes.Negate ((.~.), positive) import Data.Logic.Classes.Propositional (PropositionalFormula) import Data.Logic.Classes.Term (Term(vt, foldTerm)) import Data.Logic.Classes.Variable (Variable(prefix)) import Data.Logic.Failing (Failing(..), failing) import Data.Logic.Harrison.FOL (subst, fv, generalize, list_disj, list_conj) import Data.Logic.Harrison.Lib (settryfind, allpairs, allsubsets, setAny, setAll, allnonemptysubsets, (|->), apply, defined) import Data.Logic.Harrison.Normal (simpdnf, simpcnf, trivial) import Data.Logic.Harrison.Skolem (pnf, SkolemT, askolemize, specialize) import Data.Logic.Harrison.Tableaux (unify_literals) import Data.Logic.Harrison.Unif (solve) import qualified Data.Map as Map import Data.Maybe (fromMaybe) import qualified Data.Set as Set -- ========================================================================= -- Resolution. -- -- Copyright (c) 2003-2007, John Harrison. (See "LICENSE.txt" for details.) -- ========================================================================= -- ------------------------------------------------------------------------- -- MGU of a set of literals. -- ------------------------------------------------------------------------- mgu :: forall lit atom term v f. (Literal lit atom, Term term v f, Atom atom term v) => Set.Set lit -> Map.Map v term -> Failing (Map.Map v term) mgu l env = case Set.minView l of Just (a, rest) -> case Set.minView rest of Just (b, _) -> unify_literals env a b >>= mgu rest _ -> Success (solve env) _ -> Success (solve env) unifiable :: (Literal lit atom, Term term v f, Atom atom term v) => lit -> lit -> Bool unifiable p q = failing (const False) (const True) (unify_literals Map.empty p q) -- ------------------------------------------------------------------------- -- Rename a clause. -- ------------------------------------------------------------------------- rename :: (FirstOrderFormula fof atom v, Term term v f, Atom atom term v, Ord fof) => (v -> v) -> Set.Set fof -> Set.Set fof rename pfx cls = Set.map (subst (Map.fromList (zip fvs vvs))) cls where -- fvs :: [v] fvs = Set.toList (fv (list_disj cls)) -- vvs :: [term] vvs = map (vt . pfx) fvs -- ------------------------------------------------------------------------- -- General resolution rule, incorporating factoring as in Robinson's paper. -- ------------------------------------------------------------------------- resolvents :: (Literal fof atom, FirstOrderFormula fof atom v, Term term v f, Atom atom term v, Ord fof) => Set.Set fof -> Set.Set fof -> fof -> Set.Set fof -> Set.Set fof resolvents cl1 cl2 p acc = if Set.null ps2 then acc else Set.fold doPair acc pairs where doPair (s1,s2) sof = case mgu (Set.union s1 (Set.map (.~.) s2)) Map.empty of Success mp -> Set.union (Set.map (subst mp) (Set.union (Set.difference cl1 s1) (Set.difference cl2 s2))) sof Failure _ -> sof -- pairs :: Set.Set (Set.Set fof, Set.Set fof) pairs = allpairs (,) (Set.map (Set.insert p) (allsubsets ps1)) (allnonemptysubsets ps2) -- ps1 :: Set.Set fof ps1 = Set.filter (\ q -> q /= p && unifiable p q) cl1 -- ps2 :: Set.Set fof ps2 = Set.filter (unifiable ((.~.) p)) cl2 resolve_clauses :: forall fof atom v term f. (Literal fof atom, FirstOrderFormula fof atom v, Term term v f, Atom atom term v, Ord fof) => Set.Set fof -> Set.Set fof -> Set.Set fof resolve_clauses cls1 cls2 = let cls1' = rename (prefix "x") cls1 cls2' = rename (prefix "y") cls2 in Set.fold (resolvents cls1' cls2') Set.empty cls1' -- ------------------------------------------------------------------------- -- Basic "Argonne" loop. -- ------------------------------------------------------------------------- resloop1 :: forall atom v term f fof. (Literal fof atom, FirstOrderFormula fof atom v, Term term v f, Atom atom term v, Ord fof) => Set.Set (Set.Set fof) -> Set.Set (Set.Set fof) -> Failing Bool resloop1 used unused = maybe (Failure ["No proof found"]) step (Set.minView unused) where step (cl, ros) = if Set.member Set.empty news then return True else resloop1 used' (Set.union ros news) where used' = Set.insert cl used -- resolve_clauses is not in the Failing monad, so setmapfilter isn't appropriate. news = Set.fold Set.insert Set.empty ({-setmapfilter-} Set.map (resolve_clauses cl) used') pure_resolution1 :: forall fof atom v term f. (Literal fof atom, FirstOrderFormula fof atom v, Term term v f, Atom atom term v, Ord fof) => fof -> Failing Bool pure_resolution1 fm = resloop1 Set.empty (simpcnf (specialize (pnf fm))) resolution1 :: forall m fof term f atom v. (Literal fof atom, FirstOrderFormula fof atom v, PropositionalFormula fof atom, Term term v f, Atom atom term v, Ord fof, Monad m) => fof -> SkolemT v term m (Set.Set (Failing Bool)) resolution1 fm = askolemize ((.~.)(generalize fm)) >>= return . Set.map (pure_resolution1 . list_conj) . (simpdnf :: fof -> Set.Set (Set.Set fof)) -- ------------------------------------------------------------------------- -- Matching of terms and literals. -- ------------------------------------------------------------------------- term_match :: forall term v f. (Term term v f) => Map.Map v term -> [(term, term)] -> Failing (Map.Map v term) term_match env [] = Success env term_match env ((p, q) : oth) = foldTerm v fn p where v x = if not (defined env x) then term_match ((x |-> q) env) oth else if apply env x == Just q then term_match env oth else Failure ["term_match"] fn f fa = foldTerm v' fn' q where fn' g ga | f == g && length fa == length ga = term_match env (zip fa ga ++ oth) fn' _ _ = Failure ["term_match"] v' _ = Failure ["term_match"] {- case eqs of [] -> Success env (Fn f fa, Fn g ga) : oth | f == g && length fa == length ga -> term_match env (zip fa ga ++ oth) (Var x, t) : oth -> if not (defined env x) then term_match ((x |-> t) env) oth else if apply env x == t then term_match env oth else Failure ["term_match"] _ -> Failure ["term_match"] -} match_literals :: forall term f v fof atom. (FirstOrderFormula fof atom v, Atom atom term v, Term term v f) => Map.Map v term -> fof -> fof -> Failing (Map.Map v term) match_literals env t1 t2 = fromMaybe err (zipFirstOrder qu co tf at t1 t2) where qu _ _ _ _ _ _ = Nothing co ((:~:) p) ((:~:) q) = Just $ match_literals env p q co _ _ = Nothing tf a b = if a == b then Just (Success env) else Nothing at a1 a2 = Just (match env a1 a2) err = Failure ["match_literals"] -- Identical to unifyAtomsEq except calls term_match instead of unify. matchAtomsEq :: forall v f atom p term. (AtomEq atom p term, Term term v f) => Map.Map v term -> atom -> atom -> Failing (Map.Map v term) matchAtomsEq env a1 a2 = fromMaybe err (zipAtomsEq ap tf eq a1 a2) where ap p ts1 q ts2 = if p == q && length ts1 == length ts2 then Just (term_match env (zip ts1 ts2)) else Nothing tf p q = if p == q then Just (Success env) else Nothing eq pl pr ql qr = Just (term_match env [(pl, ql), (pr, qr)]) err = Failure ["matchAtomsEq"] {- case tmp of (Atom (R p a1), Atom(R q a2)) -> term_match env [(Fn p a1, Fn q a2)] (Not (Atom (R p a1)), Not (Atom (R q a2))) -> term_match env [(Fn p a1, Fn q a2)] _ -> Failure ["match_literals"] -} -- ------------------------------------------------------------------------- -- Test for subsumption -- ------------------------------------------------------------------------- subsumes_clause :: forall term f v fof atom. (FirstOrderFormula fof atom v, Term term v f, Atom atom term v) => Set.Set fof -> Set.Set fof -> Bool subsumes_clause cls1 cls2 = failing (const False) (const True) (subsume Map.empty cls1) where -- subsume :: Map.Map v term -> Set.Set fof -> Failing (Map.Map v term) subsume env cls = case Set.minView cls of Nothing -> Success env Just (l1, clt) -> settryfind (\ l2 -> case (match_literals env l1 l2) of Success env' -> subsume env' clt Failure msgs -> Failure msgs) cls2 -- ------------------------------------------------------------------------- -- With deletion of tautologies and bi-subsumption with "unused". -- ------------------------------------------------------------------------- replace :: forall term f v fof atom. (FirstOrderFormula fof atom v, Term term v f, Atom atom term v, Ord fof) => Set.Set fof -> Set.Set (Set.Set fof) -> Set.Set (Set.Set fof) replace cl st = case Set.minView st of Nothing -> Set.singleton cl Just (c, st') -> if subsumes_clause cl c then Set.insert cl st' else Set.insert c (replace cl st') incorporate :: forall fof term f v atom. (FirstOrderFormula fof atom v, Term term v f, Atom atom term v, Ord fof) => Set.Set fof -> Set.Set fof -> Set.Set (Set.Set fof) -> Set.Set (Set.Set fof) incorporate gcl cl unused = if trivial cl || setAny (\ c -> subsumes_clause c cl) (Set.insert gcl unused) then unused else replace cl unused resloop2 :: forall fof term f v atom. (Literal fof atom, FirstOrderFormula fof atom v, Term term v f, Atom atom term v, Ord fof) => Set.Set (Set.Set fof) -> Set.Set (Set.Set fof) -> Failing Bool resloop2 used unused = case Set.minView unused of Nothing -> Failure ["No proof found"] Just (cl {- :: Set.Set fof-}, ros {- :: Set.Set (Set.Set fof) -}) -> -- print_string(string_of_int(length used) ^ " used; "^ string_of_int(length unused) ^ " unused."); -- print_newline(); let used' = Set.insert cl used in let news = {-Set.fold Set.union Set.empty-} (Set.map (resolve_clauses cl) used') in if Set.member Set.empty news then return True else resloop2 used' (Set.fold (incorporate cl) ros news) pure_resolution2 :: forall fof atom v term f. (Literal fof atom, FirstOrderFormula fof atom v, Term term v f, Atom atom term v, Ord fof) => fof -> Failing Bool pure_resolution2 fm = resloop2 Set.empty (simpcnf (specialize (pnf fm))) resolution2 :: forall fof atom term v f m. (Literal fof atom, FirstOrderFormula fof atom v, PropositionalFormula fof atom, Term term v f, Atom atom term v, Ord fof, Monad m) => fof -> SkolemT v term m (Set.Set (Failing Bool)) resolution2 fm = askolemize ((.~.) (generalize fm)) >>= return . Set.map (pure_resolution2 . list_conj) . (simpdnf :: fof -> Set.Set (Set.Set fof)) -- ------------------------------------------------------------------------- -- Positive (P1) resolution. -- ------------------------------------------------------------------------- presolve_clauses :: (Literal fof atom, FirstOrderFormula fof atom v, Term term v f, Atom atom term v, Ord fof) => Set.Set fof -> Set.Set fof -> Set.Set fof presolve_clauses cls1 cls2 = if setAll positive cls1 || setAll positive cls2 then resolve_clauses cls1 cls2 else Set.empty presloop :: (Literal fof atom, FirstOrderFormula fof atom v, Term term v f, Atom atom term v, Ord fof) => Set.Set (Set.Set fof) -> Set.Set (Set.Set fof) -> Failing Bool presloop used unused = case Set.minView unused of Nothing -> Failure ["No proof found"] Just (cl, ros) -> -- print_string(string_of_int(length used) ^ " used; "^ string_of_int(length unused) ^ " unused."); -- print_newline(); let used' = Set.insert cl used in let news = Set.map (presolve_clauses cl) used' in if Set.member Set.empty news then Success True else presloop used' (Set.fold (incorporate cl) ros news) pure_presolution :: forall fof atom v term f. (Literal fof atom, FirstOrderFormula fof atom v, Term term v f, Atom atom term v, Ord fof) => fof -> Failing Bool pure_presolution fm = presloop Set.empty (simpcnf (specialize (pnf fm))) presolution :: forall fof atom term v f m. (Literal fof atom, FirstOrderFormula fof atom v, PropositionalFormula fof atom, Term term v f, Atom atom term v, Ord fof, Monad m) => fof -> SkolemT v term m (Set.Set (Failing Bool)) presolution fm = askolemize ((.~.) (generalize fm)) >>= return . Set.map (pure_presolution . list_conj) . (simpdnf :: fof -> Set.Set (Set.Set fof)) -- ------------------------------------------------------------------------- -- Introduce a set-of-support restriction. -- ------------------------------------------------------------------------- pure_resolution3 :: (Literal fof atom, FirstOrderFormula fof atom v, Term term v f, Atom atom term v, Ord fof) => fof -> Failing Bool pure_resolution3 fm = uncurry resloop2 (Set.partition (setAny positive) (simpcnf (specialize (pnf fm)))) resolution3 :: forall fof atom term v f m. (Literal fof atom, FirstOrderFormula fof atom v, PropositionalFormula fof atom, Term term v f, Atom atom term v, Ord fof, Monad m) => fof -> SkolemT v term m (Set.Set (Failing Bool)) resolution3 fm = askolemize ((.~.)(generalize fm)) >>= return . Set.map (pure_resolution3 . list_conj) . (simpdnf :: fof -> Set.Set (Set.Set fof)) {- -- ------------------------------------------------------------------------- -- The Pelletier examples again. -- ------------------------------------------------------------------------- {- ********** let p1 = time presolution <
q <=> ~q ==> ~p>>;; let p2 = time presolution <<~ ~p <=> p>>;; let p3 = time presolution <<~(p ==> q) ==> q ==> p>>;; let p4 = time presolution <<~p ==> q <=> ~q ==> p>>;; let p5 = time presolution <<(p \/ q ==> p \/ r) ==> p \/ (q ==> r)>>;; let p6 = time presolution <
>;; let p7 = time presolution <
>;; let p8 = time presolution <<((p ==> q) ==> p) ==> p>>;; let p9 = time presolution <<(p \/ q) /\ (~p \/ q) /\ (p \/ ~q) ==> ~(~q \/ ~q)>>;; let p10 = time presolution <<(q ==> r) /\ (r ==> p /\ q) /\ (p ==> q /\ r) ==> (p <=> q)>>;; let p11 = time presolution <
p>>;; let p12 = time presolution <<((p <=> q) <=> r) <=> (p <=> (q <=> r))>>;; let p13 = time presolution <
(p \/ q) /\ (p \/ r)>>;; let p14 = time presolution <<(p <=> q) <=> (q \/ ~p) /\ (~q \/ p)>>;; let p15 = time presolution <
q <=> ~p \/ q>>;; let p16 = time presolution <<(p ==> q) \/ (q ==> p)>>;; let p17 = time presolution <
r) ==> s <=> (~p \/ q \/ s) /\ (~p \/ ~r \/ s)>>;;
-- -------------------------------------------------------------------------
-- Monadic Predicate Logic.
-- -------------------------------------------------------------------------
let p18 = time presolution
< P(x,z))
==> P(f(a,b),f(a,c))>>;;
-- -------------------------------------------------------------------------
-- See info-hol, circa 1500.
-- -------------------------------------------------------------------------
let p58 = time presolution
< q <=> ~q ==> ~p>>;;
let p2 = time resolution
<<~ ~p <=> p>>;;
let p3 = time resolution
<<~(p ==> q) ==> q ==> p>>;;
let p4 = time resolution
<<~p ==> q <=> ~q ==> p>>;;
let p5 = time resolution
<<(p \/ q ==> p \/ r) ==> p \/ (q ==> r)>>;;
let p6 = time resolution
< >;;
let p7 = time resolution
< >;;
let p8 = time resolution
<<((p ==> q) ==> p) ==> p>>;;
let p9 = time resolution
<<(p \/ q) /\ (~p \/ q) /\ (p \/ ~q) ==> ~(~q \/ ~q)>>;;
let p10 = time resolution
<<(q ==> r) /\ (r ==> p /\ q) /\ (p ==> q /\ r) ==> (p <=> q)>>;;
let p11 = time resolution
< p>>;;
let p12 = time resolution
<<((p <=> q) <=> r) <=> (p <=> (q <=> r))>>;;
let p13 = time resolution
< (p \/ q) /\ (p \/ r)>>;;
let p14 = time resolution
<<(p <=> q) <=> (q \/ ~p) /\ (~q \/ p)>>;;
let p15 = time resolution
< q <=> ~p \/ q>>;;
let p16 = time resolution
<<(p ==> q) \/ (q ==> p)>>;;
let p17 = time resolution
< r) ==> s <=> (~p \/ q \/ s) /\ (~p \/ ~r \/ s)>>;;
(* ------------------------------------------------------------------------- *)
(* Monadic Predicate Logic. *)
(* ------------------------------------------------------------------------- *)
let p18 = time resolution
< P(x,z))
==> P(f(a,b),f(a,c))>>;;
(* ------------------------------------------------------------------------- *)
(* See info-hol, circa 1500. *)
(* ------------------------------------------------------------------------- *)
let p58 = time resolution
<