Generating truth tables for logic expressions in Haskell

Question

The first part is an evaluation function that has the following type signature:

evaluate :: Logic Expr -> [(Variable, Bool)] -> Bool

This takes a logic expression and a list of assignment pairs as input and returns the value of the expression according to the Boolean assignment provided. The assignment list is a distinct list of pairs where each pair contains a variable and its Boolean assignment. That is, if you pass to the function the expression A ∧ B and the assignment A = 1 and B = 0, your function must return 0 (this comes from Digital Logic Design, 0 corresponds to false, and 1 corresponds to true).

This is what I managed to do so far:

type Variable =  Char

data LogicExpr = V Variable
                 | Negation  LogicExpr
                 | Conjunction LogicExpr LogicExpr
                 | Disjunction  LogicExpr LogicExpr 
                 | Implication  LogicExpr LogicExpr 


evaluate :: LogicExpr -> [(Variable,Bool)] -> Bool

evaluate (V a) ((x1,x2):xs) | a==x1 = x2
                            | otherwise = (evaluate(V a)xs)

evaluate (Negation a) l | (evaluate a l)==True = False
                        | otherwise = True

evaluate (Conjunction a b) l = (evaluate a l)&&(evaluate b l)

evaluate (Disjunction a b) l = (evaluate a l)||(evaluate b l)

evaluate (Implication a b) l
    | (((evaluate b l)==False)&&((evaluate a l)==True)) = False
    | otherwise = True

The next part is to define generateTruthTable, which is a function that takes a logic expression as input and returns the truth table of the expression in the form of a list of lists of assignment pairs. That is, if you pass to the function the expression E = A ∧ B, your function must return A = 0, B = 0, E = 0 | A = 0, B = 1, E = 0 | A = 1, B = 0, E = 0 | A = 1, B = 1, E = 1.

I'm not exactly familiar with the syntax so I don't know how to return the list.

Answer 1

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

Answer 2

Standard library functions, reuse of code. Also, your parentheses usage and spacing are really whacked.

evaluate (V a) l =
    case lookup a l
      of Just x -> x
         Nothing -> error $ "Unbound variable: " ++ show a
-- same as
evaluate (V a) l = maybe (error $ "Unbound variable: " ++ show a) id $ lookup a l

evaluate (Negation a) l = not $ evaluate a l

evaluate (Implication a b) l = evaluate (Negation a `Disjunction` b) l

Now, you want a generateTruthTable? That's easy, just take all the possible states of the boolean variables, and tack the evaluated expression on to the end of each.

generateTruthTable :: [Variable] -> LogicExpr -> [[(Variable, Bool)]]
generateTruthTable vs e = [l ++ [('E', evaluate e l)] | l <- allPossible vs]

If only you had a function to generate all those possible states.

allPossible :: [Variable] -> [[(Variable, Bool)]]

Following my functional gut instinct, this feels like it should be a catamorphism. After all, it does need to look at everything in the list, but return something of a different structure, and it can probably be broken down in a simple way because this is an intro-level CS class. (I don't care what the course number is, this is introductory stuff.)

allPossible = foldr step initial where
    step v ls = ???; initial = ???

Now, foldr :: (a -> b -> b) -> b -> [a] -> b, so the first two parameters must be step :: a -> b -> b and initial :: b. Now, allPossible :: [Variable] -> [[(Variable, Bool)]] = foldr step initial :: [a] -> b. Hmm, this must mean that a = Variable and b = [[(Variable, Bool)]]. What does this mean for step and initial?

    step :: Variable -> [[(Variable, Bool)]] -> [[(Variable, Bool)]]
    initial :: [[(Variable, Bool)]]

Interesting. Somehow, there needs to be a way to step from a list of variable states and add a single variable to it, and some initial list with no variables at all.

If your mind has managed to "click" into the functional programming paradigm already, this should be more than sufficient. If not, you're pretty much screwed in a couple of hours when the assignment is due, regardless of what instruction you've received here. Good luck, and if you're still stuck after the assignment is due, you should ask your professor, or ask a non-urgent question here.

---

If you're having basic usability issues with the language ("what is the syntax", "what are the run-time semantics", "is there pre-existing functionality for xxx", etc.):

• Haskell 98 Language and Libraries is a freely-available, canonical definition of the base language and libraries. More links are available on the Haskell wiki.
• For post-98 language extensions, see the GHC documentation.
• GHC, Hugs, and other modern Haskell implementations also provide a much richer standard library than is specified in Haskell 98. Full documentation for the hierarchical libraries is also available online.
• Hoogλe is a specialized search engine for the extended Haskell standard libraries. Hayoo! is similar but also covers HackageDB, a collection of Haskell libraries far beyond the standard distribution.

I hope your class has provided similar resources, but if not, all of the above are easily discoverable from a Google search.

Given proper references, any programmer worth his or her own salt should be able to pick up the syntax of any new language within a few hours, and have a working understanding of the runtime within days. Of course, mastering a new paradigm may take ages, and it's somewhat unfair to hold students to the same standards, but that's what the class is for.

Questions about higher-level problems on Stack Overflow may invite less answers, but they'll also be provided with far less petulance :) Homework questions are categorized as "do my work for me!" in most peoples' eyes.

---

Spoiler

Please don't cheat. However, just to give you a taste of how awesome stuff can be done in Haskell...

{-# LANGUAGE FlexibleInstances, UndecidableInstances #-}
{-# LANGUAGE OverlappingInstances, PatternGuards #-}

module Expr (Ring(..), (=:>), Expr(..), vars, eval, evalAll) where

import Control.Monad.Error

infixl 5 =:>, :=>
infixl 6 +:, -:, :+, :-
infixl 7 *:, :*

class (Eq a) => Ring a where
    (+:) :: a -> a -> a; (-:) :: a -> a -> a; x -: y = x +: invert y
    (*:) :: a -> a -> a; invert :: a -> a; invert x = zero -: x
    zero :: a; one :: a
(=:>) :: (Ring a) => a -> a -> a
(=:>) = flip (-:)

instance (Num a) => Ring a where
    (+:) = (+); (-:) = (-); (*:) = (*)
    invert = negate; zero = 0; one = 1

instance Ring Bool where
    (+:) = (||); (*:) = (&&)
    invert = not; zero = False; one = True

data Expr a b
  = Expr a b :+ Expr a b | Expr a b :- Expr a b
  | Expr a b :* Expr a b | Expr a b :=> Expr a b
  | Invert (Expr a b) | Var a | Const b

paren :: ShowS -> ShowS
paren ss s = '(' : ss (')' : s)

instance (Show a, Show b) => Show (Expr a b) where
    showsPrec _ (Const c) = ('@':) . showsPrec 9 c
    showsPrec _ (Var v) = ('$':) . showsPrec 9 v
    showsPrec _ (Invert e) = ('!':) . showsPrec 9 e

    showsPrec n e@(a:=>b)
      | n > 5 = paren $ showsPrec 0 e
      | otherwise = showsPrec 7 a . ('=':) . ('>':) . showsPrec 5 b

    showsPrec n e@(a:*b)
      | n > 7 = paren $ showsPrec 0 e
      | otherwise = showsPrec 7 a . ('*':) . showsPrec 7 b

    showsPrec n e | n > 6 = paren $ showsPrec 0 e
    showsPrec _ (a:+b) = showsPrec 6 a . ('+':) . showsPrec 6 b
    showsPrec _ (a:-b) = showsPrec 6 a . ('-':) . showsPrec 6 b

vars :: (Eq a) => Expr a b -> [a]
vars (a:+b) = vars a ++ vars b
vars (a:-b) = vars a ++ vars b
vars (a:*b) = vars a ++ vars b
vars (a:=>b) = vars a ++ vars b
vars (Invert e) = vars e; vars (Var v) = [v]; vars _ = []

eval :: (Eq a, Show a, Ring b, Monad m) => [(a, b)] -> Expr a b -> m b
eval m (a:+b) = return (+:) `ap` eval m a `ap` eval m b
eval m (a:-b) = return (-:) `ap` eval m a `ap` eval m b
eval m (a:*b) = return (*:) `ap` eval m a `ap` eval m b
eval m (a:=>b) = return (=:>) `ap` eval m a `ap` eval m b
eval m (Invert e) = return invert `ap` eval m e
eval m (Var v)
  | Just c <- lookup v m = return c
  | otherwise = fail $ "Unbound variable: " ++ show v
eval _ (Const c) = return c

namedProduct :: [(a, [b])] -> [[(a, b)]]
namedProduct = foldr (\(v, cs) l -> concatMap (\c -> map ((v, c):) l) cs) [[]]

evalAll :: (Eq a, Show a, Ring b) => [b] -> a -> Expr a b -> [[(a, b)]]
evalAll range name e =
    [ vs ++ [(name, either error id $ eval vs e)]
    | vs <- namedProduct $ zip (vars e) (repeat range)
    ]

$ ghci
GHCi, version 6.10.2: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
Prelude> :l Expr.hs
[1 of 1] Compiling Expr             ( Expr.hs, interpreted )
Ok, modules loaded: Expr.
*Expr> mapM_ print . evalAll [1..3] 'C' $ Var 'A' :* Var 'B'
Loading package mtl-1.1.0.2 ... linking ... done.
[('A',1),('B',1),('C',1)]
[('A',1),('B',2),('C',2)]
[('A',1),('B',3),('C',3)]
[('A',2),('B',1),('C',2)]
[('A',2),('B',2),('C',4)]
[('A',2),('B',3),('C',6)]
[('A',3),('B',1),('C',3)]
[('A',3),('B',2),('C',6)]
[('A',3),('B',3),('C',9)]
*Expr> let expr = Var 'A' :=> (Var 'B' :+ Var 'C') :* Var 'D'
*Expr> expr
$'A'=>($'B'+$'C')*$'D'
*Expr> mapM_ print $ evalAll [True, False] 'E' expr
[('A',True),('B',True),('C',True),('D',True),('E',True)]
[('A',True),('B',True),('C',True),('D',False),('E',False)]
[('A',True),('B',True),('C',False),('D',True),('E',True)]
[('A',True),('B',True),('C',False),('D',False),('E',False)]
[('A',True),('B',False),('C',True),('D',True),('E',True)]
[('A',True),('B',False),('C',True),('D',False),('E',False)]
[('A',True),('B',False),('C',False),('D',True),('E',False)]
[('A',True),('B',False),('C',False),('D',False),('E',False)]
[('A',False),('B',True),('C',True),('D',True),('E',True)]
[('A',False),('B',True),('C',True),('D',False),('E',True)]
[('A',False),('B',True),('C',False),('D',True),('E',True)]
[('A',False),('B',True),('C',False),('D',False),('E',True)]
[('A',False),('B',False),('C',True),('D',True),('E',True)]
[('A',False),('B',False),('C',True),('D',False),('E',True)]
[('A',False),('B',False),('C',False),('D',True),('E',True)]
[('A',False),('B',False),('C',False),('D',False),('E',True)]