{-# LANGUAGE LambdaCase #-} module OdFOL where import Data.List import Data.Char import Control.Monad import System.IO ----Type System type Var = String type Cons = String type Func = String data Term = V Var | C Cons | F1 Func Term | F2 Func Term Term deriving Eq type Pred = Char data Atom = Pos1 Pred Term | Neg1 Pred Term | Pos2 Pred Term Term | Neg2 Pred Term Term deriving Eq data Unit = T | F deriving Eq data PVar = PPos String | PNeg String deriving Eq data Quant = ForAll | Exists | PosQuant String | NegQuant String deriving Eq data Sub = SubI Term Var | SubA Term Var | SubV String type Color = String data InfRule = Up String | Down String | Lin String | EqRule deriving Eq type IRtest = Dev -> Dev -> Bool data Dev = A Atom | U Unit | P PVar | Disj {dconts :: [Dev]} | Conj {cconts :: [Dev]} | Q Quant Var Dev | S Sub Dev | Inf Dev InfRule Dev | Infn {infhead :: Dev, inftail :: [(InfRule,Dev)]} | Devn {devpr :: Maybe Dev, devtail :: [(String,Dev,String)]} | Context PVar (Maybe Dev) | NContext PVar [(Maybe Dev)] | CDev Color Dev | Box Dev data Rewrite1 = R1 Dev Dev data Rewrite2 = R2 Dev Dev -------------------Show Instances instance Show Term where show (V v) = v show (C c) = c show (F1 f t) = f ++ "(" ++ show t ++ ")" show (F2 f t1 t2) = f ++ "(" ++ show t1 ++ "," ++ show t2 ++ ")" instance Show Atom where show (Pos1 p t) = p : show t show (Neg1 p t) = ['-',p] ++ show t show (Pos2 p t1 t2) = p : show t1 ++ show t2 show (Neg2 p t1 t2) = ['-',p] ++ show t1 ++ show t2 instance Show Unit where show T = "\\ttt" show F = "\\fff" instance Show PVar where show (PPos a) = a show (PNeg a) = '-' : a instance Show Quant where show ForAll = "\\forall " show Exists = "\\exists " show (PosQuant q) = q show (NegQuant q) = "-" ++ q instance Show Sub where show (SubI t v) = "{\\vlnos[" ++ show t ++ " \\rightarrow " ++ v ++ "]}" show (SubA t v) = "{\\vlnos[" ++ show t ++ " \\Rightarrow " ++ v ++ "]}" show (SubV s ) = s instance Show InfRule where show (Up a) = "\\" ++ a ++ "U" show (Down a) = "\\" ++ a ++ "D" show (Lin a) = a show (EqRule) = "=" isForm :: Dev -> Bool isForm = \case (A _) -> True (U _) -> True (P _) -> True (Q _ _ d) -> isForm d (S _ d) -> isForm d (Disj ds) -> all isForm ds (Conj ds) -> all isForm ds (Inf _ _ _) -> False (Infn dh []) -> isForm dh (Infn _ _ ) -> False (Devn Nothing []) -> True (Devn (Just dh) []) -> isForm dh (Devn _ _ ) -> False (CDev _ d) -> isForm d (Box d) -> isForm d showincon :: Dev -> String showincon = \case Q q x (Disj ds) -> show q ++ x ++ show (Disj ds) Q q x (Conj ds) -> show q ++ x ++ show (Conj ds) Q q x (Q q' y d) -> show q ++ x ++ showincon (Q q' y d) Q q x (Inf d1 r d2) -> show q ++ x ++ "[" ++ show (Inf d1 r d2) ++ "]" Q q x (Infn dh rds) -> show q ++ x ++ "[" ++ show (Infn dh rds) ++ "]" S s d -> show s ++ showincon d d -> show d showAfterQ :: Dev -> String showAfterQ = \case (Disj ds) -> if all isForm ds then "[" ++ show (Disj ds) ++ "]" else show (Box (Disj ds)) (Conj ds) -> if all isForm ds then "(" ++ show (Conj ds) ++ ")" else show (Box (Conj ds)) (Inf d1 r d2) -> show (Box (Inf d1 r d2)) (Infn dh rds) -> show (Box (Infn dh rds)) (CDev c (Disj ds)) -> concat ["[","{\\color{",c,"}",show (Disj ds),"}","]"] (CDev c (Conj ds)) -> concat ["(","{\\color{",c,"}",show (Conj ds),"}",")"] (CDev c (Inf d1 r d2)) -> concat ["\\odbox{\\color{",c,"}",show (Inf d1 r d2),"}"] (CDev c (Infn dh rds)) -> concat ["\\odbox{\\color{",c,"}",show (Infn dh rds),"}"] d -> show d showContext :: (Maybe Dev) -> String showContext Nothing = "\\gap" showContext (Just d) = concat ["\\left\\{",show d,"\\right\\}"] showNContext :: [(Maybe Dev)] -> String showNContext mds = concat $ map showContext mds instance Show Dev where show (A a) = show a show (U a) = show a show (P a) = show a show (Disj []) = [] show (Disj [d]) = show d show (Disj ds) = concat ["[",(init . concat . map (\d -> showincon d ++ ".")) ds,"]"] show (Conj []) = [] show (Conj [d]) = show d show (Conj ds) = concat ["(",(init . concat . map (\d -> showincon d ++ ".")) ds,")"] show (Q q x d) = show q ++ x ++ showAfterQ d show (S s d) = show s ++ showAfterQ d show (Inf d1 r d2) = concat ["\\odn{",show d1,"}{",show r,"}{",show d2,"}{}"] show (Infn dh []) = show dh show (Infn dh [(r1,d1)]) = show (Inf dh r1 d1) show (Infn dh rds) = concat ["\\od{",(concat . map (\_ -> "\\odi{")) rds,"\\odh\n{" ,show dh,"}}", (concat . map (\ (rn,dn) -> concat ["\n{",show rn,"}{",show dn,"}{}}"])) rds] show (Devn Nothing [] ) = [] show (Devn Nothing ((s1,d1,s2):rds)) = concat ["\n\\od{",(concat.map (\_ -> "\\odd{")) rds,"\\odP\n{",s1,"}{" ,show d1,"}{",s2,"}}", (concat . map (\ (sn1,dn,sn2) -> concat ["\n{",sn1,"}{",show dn,"}{",sn2,"}}"])) rds] show (Devn (Just dh) []) = show dh show (Devn (Just dh) rds) = concat ["\n\\od{",(concat . map (\_ -> "\\odd{")) rds,"\\odh\n{" ,show dh,"}}", (concat . map (\ (sn1,dn,sn2) -> concat ["\n{",sn1, "}{",show dn,"}{",sn2,"}}"])) rds] show (Context a md) = show a ++ showContext md show (NContext a mds) = show a ++ showNContext mds show (CDev c d) = concat ["{\\color{",c,"}",show d,"}"] show (Box d) = "\\odbox{" ++ show d ++ "}" instance Show Rewrite1 where show (R1 d1 d2) = "\\[" ++ show d1 ++ "\n\\quad \\longrightarrow \\quad\n" ++ show d2 ++ "\\]" instance Show Rewrite2 where show (R2 d1 d2) = show d1 ++ "\n& \\longrightarrow &\n" ++ show d2 ------Operations on Derivations ---Map for Infn mapFst :: (a -> b) -> [(a,c)] -> [(b,c)] mapFst f = map (\(x,y) -> (f x,y)) mapFst' :: (a -> b) -> [(a,c,d)] -> [(b,c,d)] mapFst' f = map (\(x,y,z) -> (f x,y,z)) mapSnd :: (a -> b) -> [(c,a)] -> [(c,b)] mapSnd f = map (\(x,y) -> (x,f y)) mapSnd' :: (a -> b) -> [(c,a,d)] -> [(c,b,d)] mapSnd' f = map (\(x,y,z) -> (x,f y,z)) mapBth :: (a -> c) -> (b -> d) -> [(a,b)] -> [(c,d)] mapBth f g = map (\(x,y) -> (f x,g y)) mapInfn :: (Dev -> Dev) -> Dev -> Dev mapInfn f = \case Infn dh rds -> Infn (f dh) $ mapSnd f rds Inf d1 r d2 -> Inf (f d1) r (f d2) Devn Nothing rds -> Devn Nothing $ mapSnd' f rds Devn (Just dh) rds -> Devn (Just (f dh)) $ mapSnd' f rds --Map on InfRules as well mapInfn' :: (Dev -> Dev) -> (InfRule -> InfRule) -> Dev -> Dev mapInfn' f g (Infn dh rds) = Infn (f dh) $ mapBth g f rds mapInfn' f g (Inf d1 r d2) = Inf (f d1) (g r) (f d2) --Including Quantifers + Bound Variables renamet :: Var -> Term -> Term -> Term renamet x t = \case V v | x == v -> t | otherwise -> V v C c -> C c F1 f t1 -> F1 f (renamet x t t1) F2 f t1 t2 -> F2 f (renamet x t t1) (renamet x t t2) renamev :: Var -> Var -> Dev -> Dev renamev x y = \case A (Pos1 p t) -> A (Pos1 p (renamet x (V y) t)) A (Neg1 p t) -> A (Neg1 p (renamet x (V y) t)) A (Pos2 p t1 t2) -> A (Pos2 p (renamet x (V y) t1) (renamet x (V y) t2)) A (Neg2 p t1 t2) -> A (Neg2 p (renamet x (V y) t1) (renamet x (V y) t2)) U a -> U a P a -> P a Q q z d | x == z -> Q q y (renamev x y d) | otherwise -> Q q z (renamev x y d) Disj ds -> Disj $ map (renamev x y) ds Conj ds -> Conj $ map (renamev x y) ds d -> mapInfn (renamev x y) d --Only Free Variables renamef :: Var -> Term -> Dev -> Dev renamef x t = \case A (Pos1 p t') -> A (Pos1 p (renamet x t t')) A (Neg1 p t') -> A (Neg1 p (renamet x t t')) A (Pos2 p t1' t2') -> A (Pos2 p (renamet x t t1') (renamet x t t2')) A (Neg2 p t1' t2') -> A (Neg2 p (renamet x t t1') (renamet x t t2')) U a -> U a P a -> P a Q q z d | t == (V z) -> Q q z d | otherwise -> Q q z (renamef x t d) Disj ds -> Disj $ map (renamef x t) ds Conj ds -> Conj $ map (renamef x t) ds d -> mapInfn (renamef x t) d terms :: Dev -> [Term] terms = \case A (Pos1 _ t) -> [t] A (Neg1 _ t) -> [t] A (Pos2 _ t1 t2) -> [t1,t2] A (Neg2 _ t1 t2) -> [t1,t2] U _ -> [] P _ -> [] Q _ v d -> delete (V v) (terms d) Disj ds -> nub (concat (map terms ds)) Conj ds -> nub (concat (map terms ds)) isVar :: Term -> Bool isVar (V _) = True isVar _ = False fv :: Dev -> [Term] fv d = filter isVar (terms d) --Premise and Conclusion pr :: Dev -> Dev pr = \case (A a) -> A a (U a) -> U a (P a) -> P a (Q q x d) -> Q q x $ pr d (Disj ds) -> Disj $ map pr ds (Conj ds) -> Conj $ map pr ds (Inf d1 r d2) -> pr d1 (Infn dh rds) -> pr dh (Devn (Just dh) _) -> dh (Devn (Nothing) _) -> t (Context k Nothing) -> Context k Nothing (Context k (Just d)) -> Context k (Just (pr d)) (CDev c d) -> pr d (Box d) -> pr d cn :: Dev -> Dev cn = \case (A a) -> A a (U a) -> U a (P a) -> P a (Q q x d) -> Q q x $ cn d (Disj ds) -> Disj $ map cn ds (Conj ds) -> Conj $ map cn ds (Inf d1 r d2) -> cn d2 (Infn dh rds) -> cn $ snd $ last rds (Devn Nothing []) -> t (Devn _ rds) -> cn $ (\(x,y,z) -> y) $ last rds (Context k Nothing) -> Context k Nothing (Context k (Just d)) -> Context k (Just (cn d)) (CDev c d) -> cn d (Box d) -> cn d --Conversion of derivations to sequential form toInfn :: Dev -> Dev toInfn = \case (A a) -> Infn (A a) [] (U u) -> Infn (U u) [] (Q q x p) -> Infn (Q q x p) [] (S s d) -> Infn (S s d) [] (Disj ds) -> Infn (Disj ds) [] (Conj ds) -> Infn (Conj ds) [] (Inf d1 r d2) -> Infn d1 [(r,d2)] (Infn dh rds) -> Infn dh rds (Box d) -> Infn (Box d) [] seqlize :: Dev -> Dev seqlize = \case (A a) -> (A a) (U a) -> (U a) (P a) -> (P a) (Q q x d) -> (Q q x (seqlize d)) (S s d) -> (S s (seqlize d)) (Disj ds) -> Disj $ map seqlize ds (Conj ds) -> Conj $ map seqlize ds (Inf (Inf d1 r1 d2) r2 d3) -> seqlize (Infn d1 [(r1,d2),(r2,d3)]) (Inf d1 r1 (Inf d2 r2 d3)) -> seqlize (Infn d1 [(r1,d2),(r2,d3)]) (Inf (Infn dh rds) r d) -> seqlize (Infn dh (rds ++ [(r,d)])) (Inf d r (Infn dh rds)) -> seqlize (Infn d ((r,dh) : rds)) (Inf d1 r d2) -> Inf (seqlize d1) r (seqlize d2) (Infn dh [] ) -> seqlize dh (Infn (Inf d1 r d2) rds) -> seqlize (Infn d1 ((r,d2) : rds)) (Infn (Infn dh rds1) rds2) -> seqlize (Infn dh (rds1 ++ rds2)) (Infn dh [(r1,d1)]) -> seqlize (Inf dh r1 d1) (Infn dh rds) -> Infn (seqlize dh) (concat (map (\(r,d) -> let Infn dh' rds' = (toInfn . seqlize) d in [(r, dh')] ++ rds') rds)) (Devn dh rds) -> Infn (mapInfn seqlize (Devn dh rds)) [] (CDev c d) -> CDev c (seqlize d) (Box d) -> Box (seqlize d) --Flattening of conjunction and disjunction assocform :: Dev -> Dev assocform = \case (A a) -> A a (U a) -> U a (P a) -> P a (Q q x p) -> Q q x $ assocform p (Disj []) -> Disj [] (Disj ((Disj ds1) : ds2)) -> Disj (ds1' ++ ds2') where Disj ds1' = assocform (Disj ds1) Disj ds2' = assocform (Disj ds2) (Disj (dh : dt)) -> Disj (dh' : dt') where dh' = assocform dh Disj dt' = assocform (Disj dt) (Conj []) -> Conj [] (Conj ((Conj ds1) : ds2)) -> Conj (ds1' ++ ds2') where Conj ds1' = assocform (Conj ds1) Conj ds2' = assocform (Conj ds2) (Conj (dh : dt)) -> Conj (dh' : dt') where dh' = assocform dh Conj dt' = assocform (Conj dt) d -> mapInfn assocform d --Multiset Equality of Lists listeq :: Eq a => [a] -> [a] -> Bool listeq as bs = length as == length bs && as \\ bs == [] ---Eq Instance for Dev instance Eq Dev where (A a) == (A b) = a == b (A a) == _ = False _ == (A b) = False (U a) == (U b) = a == b (U a) == _ = False _ == (U b) = False (P a) == (P b) = a == b (P a) == _ = False _ == (P b) = False (Q q x p) == (Q q' x' p') | q /= q' = False | x == x' = p == p' | otherwise = p == renamef x' (V x) p' (Q q x p) == _ = False _ == (Q q' x' p') = False (Disj ds) == (Disj ds') = listeq ds ds' (Disj ds) == _ = False _ == (Disj ds') = False (Conj ds) == (Conj ds') = listeq ds ds' (Conj ds) == _ = False _ == (Conj ds') = False d == d' = dh == dh' && and (zipWith (==) rds rds') where Infn dh rds = seqlize d Infn dh' rds' = seqlize d' -------Functions for simpler construction of derivations ---Units t,f :: Dev t = U T f = U F ---Predicates p, q, p', q' :: Term -> Dev p x = A $ Pos1 'P' x q x = A $ Pos1 'Q' x p' x = A $ Neg1 'P' x q' x = A $ Neg1 'Q' x p2, q2, p2', q2' :: Term -> Term -> Dev p2 x1 x2 = A $ Pos2 'P' x1 x2 q2 x1 x2 = A $ Pos2 'Q' x1 x2 p2' x1 x2 = A $ Neg2 'P' x1 x2 q2' x1 x2 = A $ Neg2 'Q' x1 x2 px, py, pz, pw, pu, pv, pa, pb, pc :: Dev px = p (V "x") py = p (V "y") pz = p (V "z") pw = p (V "w") pu = p (V "u") pv = p (V "v") pa = p (C "a") pb = p (C "b") pc = p (C "c") qx, qy, qz :: Dev qx = q (V "x") qy = q (V "y") qz = q (V "z") px', py', pz', pw', pu', pv', pa', pb', pc' :: Dev px' = p' (V "x") py' = p' (V "y") pz' = p' (V "z") pw' = p' (V "w") pu' = p' (V "u") pv' = p' (V "v") pa' = p' (C "a") pb' = p' (C "b") pc' = p' (C "c") qx', qy', qz' :: Dev qx' = q' (V "x") qy' = q' (V "y") qz' = q' (V "z") ---Propositional Variables aa = P (PPos "A") bb = P (PPos "B") cc = P (PPos "C") dd = P (PPos "D") ee = P (PPos "E") aa' = P (PNeg "A") bb' = P (PNeg "B") cc' = P (PNeg "C") dd' = P (PNeg "D") ee' = P (PNeg "E") ---Contexts con :: Dev -> Maybe Dev -> Dev con (P x) = Context x con _ = error "Not a propositional variable" ncon :: Dev -> [Maybe Dev] -> Dev ncon (P x) = NContext x ncon _ = error "Not a propositional variable" con' :: String -> Maybe Dev -> Dev con' st = Context (PPos st) conk x = (con (P (PPos "K"))) (Just x) conk' x = (con (P (PNeg "K"))) (Just x) conh x = (con (P (PPos "H"))) (Just x) conh' x = (con (P (PNeg "H"))) (Just x) nconk = ncon (P (PPos "K")) nconk' = ncon (P (PNeg "K")) nconh = ncon (P (PPos "H")) nconh' = ncon (P (PNeg "H")) ---Quantifiers ex :: Var -> Dev -> Dev ex x d = Q Exists x d fa :: Var -> Dev -> Dev fa x d = Q ForAll x d fax = fa "x" exx = ex "x" fay = fa "y" exy = ex "y" faz = fa "z" exz = ex "z" faw = fa "w" exw = ex "w" fau = fa "u" exu = ex "u" fav = fa "v" exv = ex "v" --Substitutions subI, subA :: Term -> Var -> Dev -> Dev subI t v = S (SubI t v) subA t v = S (SubA t v) ---Connectives (-/\-) :: Dev -> Dev -> Dev d1 -/\- d2 = Conj [d1,d2] (-\/-) :: Dev -> Dev -> Dev d1 -\/- d2 = Disj [d1,d2] negQ :: Quant -> Quant negQ ForAll = Exists negQ Exists = ForAll negQ (PosQuant s) = NegQuant s negQ (NegQuant s) = PosQuant s negQ' :: Quant -> Quant negQ' ForAll = Exists negQ' Exists = ForAll negQ' (PosQuant s) = PosQuant s negQ' (NegQuant s) = NegQuant s negIR :: InfRule -> InfRule negIR = \case (Up s) -> Down s (Down s) -> Up s (Lin s) -> Lin s EqRule -> EqRule negPV :: PVar -> PVar negPV (PPos x) = PNeg x negPV (PNeg x) = PPos x shift :: Dev -> [(InfRule,Dev)] -> ([(InfRule,Dev)], Dev) shift d [(r1,d1)] = ([(r1,d)],d1) shift d ((r1,d1):rds) = ((r1,d):rds',dn) where (rds',dn) = shift d1 rds neg :: Dev -> Dev neg = \case (A (Pos1 p t)) -> A (Neg1 p t) (A (Neg1 p t)) -> A (Pos1 p t) (A (Pos2 p t1 t2)) -> A (Neg2 p t1 t2) (A (Neg2 p t1 t2)) -> A (Pos2 p t1 t2) (U T) -> U F (U F) -> U T (P a) -> P (negPV a) (Q q x p) -> Q (negQ q) x (neg p) (S s d) -> S s (neg d) (Disj ds) -> Conj $ map neg ds (Conj ds) -> Disj $ map neg ds (Inf d1 r d2) -> mapInfn' neg negIR (Inf d2 r d1) (Infn dh []) -> Infn (neg dh) [] (Infn dh rds) -> mapInfn' neg negIR $ Infn dn (reverse rds') where (rds',dn) = shift dh rds (Context k Nothing) -> Context (negPV k) Nothing (Context k (Just d)) -> Context (negPV k) (Just (neg d)) (CDev c d) -> CDev c (neg d) (Box d) -> Box (neg d) neg' :: Dev -> Dev neg' = \case (A x) -> A x (U T) -> U F (U F) -> U T (P x) -> P x (Q q x p) -> Q (negQ' q) x (neg' p) (S s d) -> S s (neg' d) (Disj ds) -> Conj $ map neg' ds (Conj ds) -> Disj $ map neg' ds (Inf d1 r d2) -> mapInfn' neg' negIR (Inf d2 r d1) (Infn dh []) -> Infn (neg' dh) [] (Infn dh rds) -> mapInfn' neg' negIR $ Infn dn (reverse rds') where (rds',dn) = shift dh rds (Context k Nothing) -> Context k Nothing (Context k (Just d)) -> Context k (Just (neg' d)) (CDev c d) -> CDev c (neg' d) (Box d) -> Box (neg' d) --------Inference Rules eq :: InfRule eq = EqRule --SKS aiU, acU, awU, aiD, acD, awD, sw, me, sw2, sw3 :: InfRule aiU = Up "ai" acU = Up "ac" awU = Up "aw" aiD = Down "ai" acD = Down "ac" awD = Down "aw" sw = Lin "\\sw" me = Lin "\\me" sw2 = Lin "2\\sw" sw3 = Lin "3\\sw" --SKSg iU, cU, wU, iD, cD, wD :: InfRule iU = Up "i" cU = Up "c" wU = Up "w" iD = Down "i" cD = Down "c" wD = Down "w" --SKSq nU, uU, nD, uD :: InfRule nU = Up "n" uU = Up "u" nD = Down "n" uD = Down "u" moU, mtU, qcU, moD, mtD, qcD :: InfRule moU = Up "mo" mtU = Up "mt" qcU = Up "qc" moD = Down "mo" mtD = Down "mt" qcD = Down "qc" --ROP roD, roU, rtD, rtU, rthD, rthU, rfD, rfU :: InfRule roD = Down "ro" roU = Up "ro" rtD = Down "rt" rtU = Up "rt" rthD = Down "rth" rthU = Up "rth" rfD = Down "rf" rfU = Up "rf" --SKSh qiD, qiU, vqeD, vqeU, vqaD, vqaU, hD, hU :: InfRule qiD = Down "qi" qiU = Up "qi" vqeD = Down "vqe" vqeU = Up "vqe" vqaD = Down "vqa" vqaU = Up "vqa" hD = Down "h" hU = Up "h" --SKSex exD, exU :: InfRule exD = Down "ex" exU = Up "ex" ---Types of formulae type FormCheck = Dev -> Bool isAtom, isAtomic, isQuant, isExists, isForall, isQuantic :: FormCheck isAtom (A _) = True isAtom (P (PPos (s:_))) = isLower s isAtom (P (PNeg (s:_))) = isLower s isAtom _ = False isAtomic (Conj ds) = all isAtom ds isAtomic (Disj ds) = all isAtom ds isAtomic d = isAtom d isQuant (Q _ _ _) = True isQuant _ = False isExists (Q Exists _ _) = True isExists _ = False isForall (Q ForAll _ _) = True isForall _ = False isQuantic (Conj ds) = all isQuant ds isQuantic (Disj ds) = all isQuant ds isQuantic d = isQuant d ---Inference Rule Application dual :: (Dev -> Dev) -> (Dev -> Dev) dual f = neg . f . neg dual2 :: (Dev -> Dev -> Dev) -> (Dev -> Dev -> Dev) dual2 f d1 d2 = neg $ f (neg d1) (neg d2) --SKS(g) iDapp, iUapp, cDapp, cUapp, wDapp, wUapp :: Dev -> Dev iDapp d | isAtom d = Inf t aiD (d -\/- neg d) | isQuant d = Inf t qiD (d -\/- neg d) | otherwise = Inf t iD (d -\/- neg d) iUapp = dual iDapp cDapp d | isAtom d = Inf (d -\/- d) acD (cn d) | isQuant d = Inf (d -\/- d) qcD (cn d) | otherwise = Inf (d -\/- d) cD (cn d) cUapp = dual cDapp wDapp d | isAtom d = Inf f awD d | otherwise = Inf f wD d wUapp = dual wDapp nDapp, nUapp :: Var -> Term -> Dev -> Dev nDapp x t p = Inf (renamef x t p) nD (ex x p) nUapp x t = dual $ nDapp x t swapp :: Dev -> Dev -> Dev -> Dev swapp d1 d2 d3 = Inf (d1 -/\- (d2 -\/- d3)) sw ((cn d1 -/\- cn d2) -\/- cn d3) swapp' d1 d2 d3 = Inf (pr d1 -/\- (pr d2 -\/- pr d3)) sw ((d1 -/\- d2) -\/- d3) meapp,meapp' :: Dev -> Dev -> Dev -> Dev -> Dev meapp d1 d2 d3 d4 = Inf ((d1 -/\- d2) -\/- (d3 -/\- d4)) me ((cn d1 -\/- cn d3) -/\- (cn d2 -\/- cn d4)) meapp' d1 d2 d3 d4 = Inf ((pr d1 -/\- pr d2) -\/- (pr d3 -/\- pr d4)) me ((d1 -\/- d3) -/\- (d2 -\/- d4)) --Rules of Passage roDapp, rtDapp, rthDapp, rfDapp, roUapp, rtUapp, rthUapp, rfUapp :: Var -> Dev -> Dev -> Dev roDapp v d1 d2 = Inf (fa v (d1 -\/- d2)) roD (fa v d1 -\/- d2) rtDapp v d1 d2 = Inf (fa v (d1 -/\- d2)) rtD (fa v d1 -/\- d2) rthDapp v d1 d2 = Inf (ex v (d1 -\/- d2)) rthD (ex v d1 -\/- d2) rfDapp v d1 d2 = Inf (ex v (d1 -/\- d2)) rfD (ex v d1 -/\- d2) roUapp v = dual2 $ roDapp v rtUapp v = dual2 $ rtDapp v rthUapp v = dual2 $ rthDapp v rfUapp v = dual2 $ rfDapp v --exD, exU exDapp, exUapp, exDapp', exUapp' :: Term -> Var -> Dev -> Dev exDapp t v d = Inf (S (SubI t v) d ) exD (S (SubA t v) (cn d)) exUapp t v d = Inf (S (SubA t v) d ) exU (S (SubI t v) (cn d)) exDapp' t v d = Inf (S (SubI t v) (pr d)) exD (S (SubA t v) d ) exUapp' t v d = Inf (S (SubA t v) (pr d)) exU (S (SubI t v) d ) ----Check for correctness type RuleCheck = Dev -> Dev -> Bool --Identity/Cut checkiD, checkaiD, checkqiD, checkiU, checkaiU, checkqiU :: RuleCheck checkiD d1 (Disj [d2,d3]) = d1 == t && neg d2 == d3 checkiD _ _ = False checkaiD d1 d2 = isAtomic d2 && checkiD d1 d2 checkqiD d1 d2 = isQuantic d2 && checkiD d1 d2 checkiU (Conj [d1,d2]) d3 = neg d1 == d2 && d3 == f checkiU _ _ = False checkaiU d1 d2 = isAtomic d1 && checkiU d1 d2 checkqiU d1 d2 = isQuantic d1 && checkiD d1 d2 --(Co)Contraction checkcD, checkacD, checkqcD, checkcU, checkacU, checkqcU :: RuleCheck checkcD (Disj [d1,d2]) d3 = d1 == d2 && d2 == d3 checkcD _ _ = False checkacD d1 d2 = isAtom d2 && checkcD d1 d2 checkqcD d1 d2 = isExists d2 && checkcD d1 d2 checkcU d1 (Conj [d2,d3]) = d1 == d2 && d2 == d3 checkcU _ _ = False checkacU d1 d2 = isAtom d1 && checkcU d1 d2 checkqcU d1 d2 = isForall d1 && checkcU d1 d2 --(Co)Weakening checkwD, checkawD, checkwU, checkawU :: RuleCheck checkwD d1 _ = d1 == f checkawD d1 d2 = d1 == f && isAtom d2 checkwU _ d2 = d2 == t checkawU d1 d2 = d2 == t && isAtom d1 --Switch/Medial checksw, checkme, checksw2 :: RuleCheck checksw (Conj [a,Disj [b,c]]) (Disj [Conj [a',b'],c']) = (a,b,c) == (a',b',c') checksw _ _ = False checkme (Disj [(Conj [a,b]),(Conj [c,d])]) (Conj [(Disj [a',c']),Disj [b',d']]) = (a,b,c,d) == (a',b',c',d') checkme _ _ = False checksw2 (Conj [(Conj [a,b]),(Disj [c,d])]) (Disj [(Conj [a',c']),Conj [b',d']]) = (a,b,c,d) == (a',b',c',d') checksw2 (Conj [(Disj [a,b]),(Conj [c,d])]) (Disj [(Conj [a',c']),Conj [b',d']]) = (a,b,c,d) == (a',b',c',d') checksw2 (Conj [(Disj [a,b]),Disj [c,d]]) (Disj [(Conj [a',c']),(Disj [b',d'])]) = (a,b,c,d) == (a',b',c',d') checksw2 (Conj [(Disj [a,b]),Disj [c,d]]) (Disj [(Disj [a',c']),(Conj [b',d'])]) = (a,b,c,d) == (a',b',c',d') ----FOL Rules checknD, checknU, checkhD, checkhU :: RuleCheck checknD _ _ = True checknU _ _ = True checkhD _ _ = True checkhU _ _ = True ----Check for Soundness checkInf :: InfRule -> RuleCheck checkInf r | r == iD = checkiD | r == aiD = checkaiD | r == qiD = checkqiD | r == iU = checkiU | r == aiU = checkaiU | r == qiU = checkqiU | r == cD = checkcD | r == acD = checkacD | r == qcD = checkqcD | r == cU = checkcU | r == acU = checkacU | r == qcU = checkqcU | r == wD = checkwD | r == awD = checkawD | r == wU = checkwU | r == awU = checkawU | r == sw = checksw | r == me = checkme | r == sw2 = checksw2 | r == nD = checknD | r == nU = checknU | r == hD = checkhD | r == hU = checkhU | otherwise = \_ _ -> True checkSound :: Dev -> Bool checkSound = \case A a -> True U u -> True P p -> True Q q v d -> checkSound d Disj ds -> and (map checkSound ds) Conj ds -> and (map checkSound ds) Inf d1 r d2 -> checkSound d1 && checkSound d2 && checkInf r (cn d1) (pr d2) Infn dh rds -> checkSound dh && checkInf r1 (cn dh) (pr dh') && checkSound (Infn dh' rds') where (r1,dh') = head rds rds' = tail rds Devn Nothing rds -> and (map (\(x,y,z) -> checkSound y) rds) Devn (Just dh) rds -> checkSound dh && and (map (\(x,y,z) -> checkSound y) rds) Context p Nothing -> True Context p (Just d) -> checkSound d CDev c d -> checkSound d --Useful Building blocks qiD1, qiD2, qiU1, qiU2, qiD1', qiD2', qiD3', qiD4', qiU1', qiU2', qiU3', qiU4' :: (Term -> Dev) -> Var -> Dev qiD1 p y = let py = p (V y) in Inf (fa y (iDapp py)) uD ((fa y) py -\/- (ex y) (neg py)) qiD2 p y = let py = p (V y) in Inf (fa y (iDapp py)) uD ((ex y) py -\/- (fa y) (neg py)) qiU1 p y = neg $ qiD2 (\z -> neg (p z)) y qiU2 p y = neg $ qiD1 (\z -> neg (p z)) y qiD1' p y = Inf t qiD ((fa y) (p (V y)) -\/- (ex y) (neg (p (V y)))) qiD2' p y = Inf t qiD ((fa y) (neg (p (V y))) -\/- (ex y) (p (V y))) qiD3' p y = Inf t qiD ((ex y) (p (V y)) -\/- (fa y) (neg (p (V y)))) qiD4' p y = Inf t qiD ((ex y) (neg (p (V y))) -\/- (fa y) (p (V y))) qiU1' = (curry (neg . (uncurry qiD4'))) qiU2' = (curry (neg . (uncurry qiD3'))) qiU3' = (curry (neg . (uncurry qiD2'))) qiU4' = (curry (neg . (uncurry qiD1'))) ---Colours blue, red, green, black, magenta, conred, congreen :: Dev -> Dev blue = CDev "blue" red = CDev "red" green = CDev "darkgreen" black = CDev "black" magenta = CDev "magenta" conred = CDev "conred" congreen = CDev "condarkgreen"