{-# LANGUAGE LambdaCase #-} module OdProp where import Data.List import Data.Char import Control.Monad import System.IO data Atom = Pos Char | Neg Char deriving Eq data Unit = T | F deriving Eq data PVar = PPos String | PNeg String deriving Eq type Color = String data InfRule = Up String | Down String | Lin String | EqRule | NoRule deriving (Eq, Read) type IRtest = Dev -> Dev -> Bool data Dev = A Atom | U Unit | P PVar | Disj {dconts :: [Dev]} | Conj {cconts :: [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 Atom where show (Pos a) = [a] show (Neg a) = '-' : [a] instance Show Unit where show T = "\\ttt" show F = "\\fff" instance Show PVar where show (PPos a) = a show (PNeg a) = '-' : a instance Show InfRule where show (Up a) = "\\" ++ a ++ "U" show (Down a) = "\\" ++ a ++ "D" show (Lin a) = a show (EqRule) = "=" show (NoRule) = [] isForm :: Dev -> Bool isForm = \case (A _) -> True (U _) -> True (P _) -> True (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 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 -> show d ++ ".")) ds,"]"] show (Conj []) = [] show (Conj [d]) = show d show (Conj ds) = concat ["(",(init . concat . map (\d -> show d ++ ".")) ds,")"] 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 ["\\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 ["\\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 (Conj ds)) | take 3 c == "con" = concat ["(\\color{",drop 3 c,"}",(init . concat . map (\d -> show (black d) ++ ".")) ds,")"] | otherwise = concat ["{\\color{",c,"}",show (Conj ds),"}"] show (CDev c (Disj ds)) | take 3 c == "con" = concat ["[\\color{",drop 3 c,"}",(init . concat . map (\d -> show (black d) ++ ".")) ds,"]"] | otherwise = concat ["{\\color{",c,"}",show (Disj ds),"}"] show (CDev c d) | take 3 c == "con" = show d | otherwise = 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 [] = [] mapFst f ((x,y):xys) = (f x,y) : (mapFst f xys) mapSnd :: (a -> b) -> [(c,a)] -> [(c,b)] mapSnd f [] = [] mapSnd f ((x,y):xys) = (x,f y) : (mapSnd f xys) mapSnd' :: (a -> b) -> [(c,a,d)] -> [(c,b,d)] mapSnd' f [] = [] mapSnd' f ((x,y,z):xyzs) = (x,f y,z) : (mapSnd' f xyzs) mapBth :: (a -> c) -> (b -> d) -> [(a,b)] -> [(c,d)] mapBth f g = (mapFst f) . (mapSnd g) 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) --Premise and Conclusion pr :: Dev -> Dev pr = \case (A a) -> A a (U a) -> U a (P a) -> P a (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 (CDev c d) -> CDev c $ pr d cn :: Dev -> Dev cn = \case (A a) -> A a (U a) -> U a (P a) -> P a (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 (CDev c d) -> CDev c $ cn d Context p d -> Context p $ fmap cn d --Conversion of derivations to sequential form toInfn :: Dev -> Dev toInfn = \case (A a) -> Infn (A a) [] (U u) -> Infn (U u) [] (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) (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 (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 (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 CDev _ d == CDev _ d' = d == d' CDev _ d == d' = d == d' d == CDev _ d' = d == d' 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 ---Atoms a, b, c, d, e, g :: Dev a = A (Pos 'a') b = A (Pos 'b') c = A (Pos 'c') d = A (Pos 'd') e = A (Pos 'e') g = A (Pos 'g') a', b', c', d', e', g' :: Dev a' = A (Neg 'a') b' = A (Neg 'b') c' = A (Neg 'c') d' = A (Neg 'd') e' = A (Neg 'e') g' = A (Neg 'g') ---Propositional Variables aa, bb, cc, dd, ee, ff, p, q, r, s :: Dev aa = P (PPos "A") bb = P (PPos "B") cc = P (PPos "C") dd = P (PPos "D") ee = P (PPos "E") ff = P (PPos "F") p = P (PPos "P") q = P (PPos "Q") r = P (PPos "R") s = P (PPos "S") aa', bb', cc', dd', ee', ff', p', q', r', s' :: Dev aa' = P (PNeg "A") bb' = P (PNeg "B") cc' = P (PNeg "C") dd' = P (PNeg "D") ee' = P (PNeg "E") ff' = P (PNeg "F") p' = P (PNeg "P") q' = P (PNeg "Q") r' = P (PNeg "R") s' = P (PNeg "S") ---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")) ---Connectives (-/\-) :: Dev -> Dev -> Dev d1 -/\- d2 = Conj [d1,d2] (-\/-) :: Dev -> Dev -> Dev d1 -\/- d2 = Disj [d1,d2] negIR :: InfRule -> InfRule negIR (Up s) = Down s negIR (Down s) = Up s negIR (Lin s) = Lin s negIR EqRule = EqRule negIR NoRule = NoRule 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 shift' :: Dev -> [(String,Dev,String)] -> ([(String,Dev,String)], Dev) shift' d [(s1,d1,s2)] = ([(s1,d,s2)],d1) shift' d ((s1,d1,s2):rds) = ((s1,d,s2):rds',dn) where (rds',dn) = shift' d1 rds neg :: Dev -> Dev neg = \case (A (Pos a)) -> A (Neg a) (A (Neg a)) -> A (Pos a) (U T) -> U F (U F) -> U T (P a) -> P (negPV a) (Disj ds) -> Conj $ map neg ds (Conj ds) -> Disj $ map neg ds (Inf d1 r d2) -> Inf (neg d2) (negIR r) (neg d1) (Infn dh []) -> Infn (neg dh) [] (Infn dh rds) -> mapInfn neg $ (let (rds',dn) = shift dh rds in Infn dn (reverse 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) neg' :: Dev -> Dev neg' = \case (A x) -> A x (U T) -> U F (U F) -> U T (P x) -> P x (Disj ds) -> Conj $ map neg' ds (Conj ds) -> Disj $ map neg' ds (Inf d1 r d2) -> Inf (neg' d2) (negIR r) (neg' d1) (Infn dh []) -> Infn (neg' dh) [] (Infn dh rds) -> mapInfn neg' $ 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) --------Inference Rules eq :: InfRule eq = EqRule nr :: InfRule nr = NoRule --SKS aiU, acU, awU, aiD, acD, awD, sw, me, sw2, sw3, swD, swU :: 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" swD = Down "sw" swU = Up "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" ---Types of formulae type FormCheck = Dev -> Bool isAtom, isAtomic :: 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 ---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, cDapp, wDapp, iUapp, cUapp, wUapp :: Dev -> Dev iDapp d | isAtom d = Inf t aiD (d -\/- neg d) | otherwise = Inf t iD (d -\/- neg d) cDapp d | isAtom d = Inf (d -\/- d) acD (cn d) | otherwise = Inf (d -\/- d) cD (cn d) wDapp d | isAtom d = Inf f awD d | otherwise = Inf f wD d iUapp = dual iDapp cUapp = dual cDapp wUapp = dual wDapp swapp, swapp', swapp2, swapp2' :: Dev -> Dev -> Dev -> Dev swapp d1 d2 d3 = Inf (d1 -/\- (d2 -\/- d3)) sw ((cn d1 -/\- cn d2) -\/- cn d3) swapp' d1 d2 d3 = Inf (d1 -/\- (d2 -\/- d3)) nr ((cn d1 -/\- cn d2) -\/- cn d3) swapp2 d1 d2 d3 = Inf (pr d1 -/\- (pr d2 -\/- pr d3)) sw ((d1 -/\- d2) -\/- d3) swapp2' d1 d2 d3 = Inf (pr d1 -/\- (pr d2 -\/- pr d3)) nr ((d1 -/\- d2) -\/- d3) meapp,meapp',meapp2,meapp2' :: 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 ((d1 -/\- d2) -\/- (d3 -/\- d4)) nr ((cn d1 -\/- cn d3) -/\- (cn d2 -\/- cn d4)) meapp2 d1 d2 d3 d4 = Inf ((pr d1 -/\- pr d2) -\/- (pr d3 -/\- pr d4)) me ((d1 -\/- d3) -/\- (d2 -\/- d4)) meapp2' d1 d2 d3 d4 = Inf ((pr d1 -/\- pr d2) -\/- (pr d3 -/\- pr d4)) nr ((d1 -\/- d3) -/\- (d2 -\/- d4)) swDapp, swUapp :: Dev -> Dev -> Dev -> Dev -> Dev swDapp d1 d2 d3 d4 = Inf ((d1 -\/- d2) -/\- (d3 -\/- d4)) swD ((cn d1 -/\- cn d3) -\/- (cn d2 -\/- cn d4)) swUapp d1 d2 d3 d4 = Inf ((d1 -/\- d2) -/\- (d3 -\/- d4)) swU ((cn d1 -/\- cn d3) -\/- (cn d2 -/\- cn d4)) --Derivations dev :: Dev -> String -> Dev -> String -> Dev dev d1 st1 d2 st2 = Devn (Just d1) [(st1,d2,st2)] prf :: String -> Dev -> String -> Dev prf st1 d2 st2 = Devn Nothing [(st1,d2,st2)] ----Check for correctness type RuleCheck = Dev -> Dev -> Bool --Identity/Cut checkiD, checkaiD, checkiU, checkaiU :: RuleCheck checkiD d1 (Disj [d2,d3]) = d1 == t && neg d2 == d3 checkiD _ _ = False checkaiD d1 d2 = isAtomic d2 && checkiD d1 d2 checkiU (Conj [d1,d2]) d3 = neg d1 == d2 && d3 == f checkiU _ _ = False checkaiU d1 d2 = isAtomic d1 && checkiU d1 d2 --(Co)Contraction checkcD, checkacD, checkcU, checkacU :: RuleCheck checkcD (Disj [d1,d2]) d3 = d1 == d2 && d2 == d3 checkcD _ _ = False checkacD d1 d2 = isAtom d2 && checkcD d1 d2 checkcU d1 (Conj [d2,d3]) = d1 == d2 && d2 == d3 checkcU _ _ = False checkacU d1 d2 = isAtom 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') checkInf :: InfRule -> RuleCheck checkInf r | r == iD = checkiD | r == aiD = checkaiD | r == iU = checkiU | r == aiU = checkaiU | r == cD = checkcD | r == acD = checkacD | r == cU = checkcU | r == acU = checkacU | r == wD = checkwD | r == awD = checkawD | r == wU = checkwU | r == awU = checkawU | r == sw = checksw | r == me = checkme | r == sw2 = checksw2 | otherwise = \_ _ -> True check :: Dev -> Bool check = \case A a -> True U u -> True P p -> True Disj ds -> and (map check ds) Conj ds -> and (map check ds) Inf d1 r d2 -> check d1 && check d2 && checkInf r (cn d1) (pr d2) Infn dh rds -> check dh && checkInf r1 (cn dh) (pr dh') && check (Infn dh' rds') where (r1,dh') = head rds rds' = tail rds Devn Nothing rds -> and (map (\(x,y,z) -> check y) rds) Devn (Just dh) rds -> check dh && and (map (\(x,y,z) -> check y) rds) Context p Nothing -> True Context p (Just d) -> check d CDev c d -> check d ---Colours blue = CDev "blue" red = CDev "red" green = CDev "darkgreen" black = CDev "black" magenta = CDev "magenta" conred = CDev "conred" congreen = CDev "condarkgreen"