# 99 questions/Solutions/46

### From HaskellWiki

(cleanup, comment, format) |
|||

Line 4: | Line 4: | ||

Now, write a predicate table/3 which prints the truth table of a given logical expression in two variables. | Now, write a predicate table/3 which prints the truth table of a given logical expression in two variables. | ||

+ | |||

+ | The first step in this problem is to define the Boolean predicates: | ||

<haskell> | <haskell> | ||

+ | -- Negate a Boolean argument | ||

not' :: Bool -> Bool | not' :: Bool -> Bool | ||

not' True = False | not' True = False | ||

not' False = True | not' False = True | ||

+ | -- True if both a and b are True | ||

and',or',nor',nand',xor',impl',equ' :: Bool -> Bool -> Bool | and',or',nor',nand',xor',impl',equ' :: Bool -> Bool -> Bool | ||

and' True True = True | and' True True = True | ||

and' _ _ = False | and' _ _ = False | ||

+ | -- True if a or b or both are True | ||

or' False False = False | or' False False = False | ||

or' _ _ = True | or' _ _ = True | ||

+ | -- Negation of 'or' | ||

nor' a b = not' $ or' a b | nor' a b = not' $ or' a b | ||

+ | |||

+ | -- Negation of 'and' | ||

nand' a b = not' $ and' a b | nand' a b = not' $ and' a b | ||

+ | -- True if either a or b is true, but not if both are true | ||

xor' True False = True | xor' True False = True | ||

xor' False True = True | xor' False True = True | ||

xor' _ _ = False | xor' _ _ = False | ||

+ | -- True if a implies b, equivalent to (not a) or (b) | ||

impl' a b = (not' a) `or'` b | impl' a b = (not' a) `or'` b | ||

+ | -- True if a and b are equal | ||

equ' True True = True | equ' True True = True | ||

equ' False False = True | equ' False False = True | ||

equ' _ _ = False | equ' _ _ = False | ||

+ | </haskell> | ||

− | + | The explicit implementation of logic functions above could be shortened using Haskell's builtin equivalents: | |

− | + | ||

− | + | <haskell> | |

+ | and' a b = a && b | ||

+ | or' a b = a || b | ||

+ | nand' a b = not (and' a b) | ||

+ | nor' a b = not (or' a b) | ||

+ | xor' a b = and' (or' a b) (nand' a b) | ||

+ | impl' a b = or' (not a) b | ||

+ | equ' a b = a == b | ||

</haskell> | </haskell> | ||

− | + | Some could be reduced even further through [[Pointfree]] style: | |

+ | |||

+ | <haskell> | ||

+ | and' = (&&) | ||

+ | or' = (||) | ||

+ | equ' = (==) | ||

+ | </haskell> | ||

+ | |||

+ | Anyway, the only remaining difficulty is to generate the truth table. This approach accepts a Boolean function <tt>(Bool -> Bool -> Bool)</tt>, then calls that function with all four combinations of two Boolean values: | ||

+ | |||

+ | <haskell> | ||

+ | table :: (Bool -> Bool -> Bool) -> IO () | ||

+ | table f = mapM_ putStrLn [show a ++ " " ++ show b ++ " " ++ show (f a b) | ||

+ | | a <- [True, False], b <- [True, False]] | ||

+ | </haskell> | ||

The table function in Lisp supposedly uses Lisp's symbol handling to substitute variables on the fly in the expression. I chose passing a binary function instead because parsing an expression would be more verbose in haskell than it is in Lisp. Template Haskell could also be used :) | The table function in Lisp supposedly uses Lisp's symbol handling to substitute variables on the fly in the expression. I chose passing a binary function instead because parsing an expression would be more verbose in haskell than it is in Lisp. Template Haskell could also be used :) |

## Revision as of 02:34, 18 July 2010

(**) Define predicates and/2, or/2, nand/2, nor/2, xor/2, impl/2 and equ/2 (for logical equivalence) which succeed or fail according to the result of their respective operations; e.g. and(A,B) will succeed, if and only if both A and B succeed.

A logical expression in two variables can then be written as in the following example: and(or(A,B),nand(A,B)).

Now, write a predicate table/3 which prints the truth table of a given logical expression in two variables.

The first step in this problem is to define the Boolean predicates:

-- Negate a Boolean argument not' :: Bool -> Bool not' True = False not' False = True -- True if both a and b are True and',or',nor',nand',xor',impl',equ' :: Bool -> Bool -> Bool and' True True = True and' _ _ = False -- True if a or b or both are True or' False False = False or' _ _ = True -- Negation of 'or' nor' a b = not' $ or' a b -- Negation of 'and' nand' a b = not' $ and' a b -- True if either a or b is true, but not if both are true xor' True False = True xor' False True = True xor' _ _ = False -- True if a implies b, equivalent to (not a) or (b) impl' a b = (not' a) `or'` b -- True if a and b are equal equ' True True = True equ' False False = True equ' _ _ = False

The explicit implementation of logic functions above could be shortened using Haskell's builtin equivalents:

and' a b = a && b or' a b = a || b nand' a b = not (and' a b) nor' a b = not (or' a b) xor' a b = and' (or' a b) (nand' a b) impl' a b = or' (not a) b equ' a b = a == b

Some could be reduced even further through Pointfree style:

and' = (&&) or' = (||) equ' = (==)

Anyway, the only remaining difficulty is to generate the truth table. This approach accepts a Boolean function `(Bool -> Bool -> Bool)`, then calls that function with all four combinations of two Boolean values:

table :: (Bool -> Bool -> Bool) -> IO () table f = mapM_ putStrLn [show a ++ " " ++ show b ++ " " ++ show (f a b) | a <- [True, False], b <- [True, False]]

The table function in Lisp supposedly uses Lisp's symbol handling to substitute variables on the fly in the expression. I chose passing a binary function instead because parsing an expression would be more verbose in haskell than it is in Lisp. Template Haskell could also be used :)