# Difference between revisions of "99 questions/Solutions/46"

(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> |
||

− | The implementations of the logic functions are quite verbose and can be shortened in places (like "equ' = (==)"). |
||

+ | 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> |
||

⚫ | |||

⚫ | |||

⚫ | |||

+ | </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 :)