Generating truth tables for logic expressions in Haskell

Answer 1

tough love

sometime the best help is no help. good luck on your homework, don't forget to do it next time, get a calendar.

Answer 2

When I was in college my best friend was a pocket-sized dayrunner. Never forgot about homework, prioritized by nearest due date (they say that's most efficient).

Answer 3

I recommend iPhone and a good to-do list / Calendar for it. (Here is my honesty: I can't help with the assignment. Sorry but good luck)

Answer 4

The basic evaluate is pretty straight forward:

import Data.Maybe (fromJust)
import Data.List (nub)

type Variable = Char
data LogicExpr
   = Var Variable
   | Neg LogicExpr
   | Conj LogicExpr LogicExpr
   | Disj LogicExpr LogicExpr
   | Impl LogicExpr LogicExpr
   deriving (Eq, Ord)

-- evaluates an expression
evaluate :: LogicExpr -> [(Variable, Bool)] -> Bool
evaluate (Var v) bs      = fromJust (lookup v bs)
evaluate (Neg e) bs      = not (evaluate e bs)
evaluate (Conj e1 e2) bs = evaluate e1 bs && evaluate e2 bs
evaluate (Disj e1 e2) bs = evaluate e1 bs || evaluate e2 bs
evaluate (Impl e1 e2) bs = not (evaluate e1 bs) || evaluate e2 bs

To generate a truth table, you first have to find all the variables in an expression and then generate all the possible assignments for these variables. The truth values of these assignments can easily be determined with the already implemented evaluate function:

-- get variables in an expression
varsp :: LogicExpr -> [Variable]
varsp (Var v)      = [v]
varsp (Neg e)      = varsp e
varsp (Conj e1 e2) = varsp e1 ++ varsp e2
varsp (Disj e1 e2) = varsp e1 ++ varsp e2
varsp (Impl e1 e2) = varsp e1 ++ varsp e2

-- get variables in an expression without duplicates
vars :: LogicExpr -> [Variable]
vars = nub . varsp

-- possible boolean values
bools = [True, False]

-- all possible combinations of variable assignments
booltable :: [Variable] -> [[(Variable, Bool)]]
booltable [] = [[]]
booltable (a:as) = [(a,b) : r | b <- bools, r <- booltable as]

-- variable assignments and corresponding evaluation of an expression
truthtable :: LogicExpr -> [([(Variable, Bool)], Bool)]
truthtable e = [(bs, evaluate e bs) | bs <- booltable (vars e)]

If you want to explore the dark corners of the standard library, you can also write a Read instance for easy input of LogicExprs:

-- read a right-associative infix operator
readInfix opprec constr repr prec r
   = readParen (prec > opprec)
     (\r -> [(constr e1 e2, u) |
             (e1,s) <- readsPrec (opprec+1) r,
             (op,t) <- lex s,
             op == repr,
             (e2,u) <- readsPrec (opprec) t]) r

instance Read LogicExpr where
   readsPrec prec r
      =  readInfix 1 Impl "->" prec r
      ++ readInfix 2 Disj "|" prec r
      ++ readInfix 3 Conj "&" prec r
      ++ readParen (prec > 4)
         (\r -> [(Neg e, t) |
                 ("!",s) <- lex r,
                 (e,t)   <- readsPrec 4 s]) r
      ++ readParen (prec > 5)
         (\r -> [(Var v, s) |
                 ([v], s) <- lex r]) r

And truth tables can be printed prettily:

showcell :: (Variable, Bool) -> String
showcell (v,b) = v : "=" ++ show b

showrow :: [(Variable, Bool)] -> Bool -> String
showrow []     b = show b
showrow [a]    b = showcell a ++ " => " ++ show b
showrow (a:as) b = showcell a ++ " && " ++ showrow as b

printrow :: ([(Variable, Bool)], Bool) -> IO ()
printrow = putStrLn . uncurry showrow

printtbl :: [([(Variable, Bool)], Bool)] -> IO ()
printtbl = mapM_ printrow

All together truth tables can be generated like this:

Prelude Main> printtbl $ truthtable $ read "(a -> b) & (b -> a)"
a=True && b=True => True
a=True && b=False => False
a=False && b=True => False
a=False && b=False => True

Prelude Main> printtbl $ truthtable $ read "(a | b) | (!a & !b)"
a=True && b=True => True
a=True && b=False => True
a=False && b=True => True
a=False && b=False => True