Copyright | Copyright (C) 2021 Yoo Chung |
---|---|

License | GPL-3.0-or-later |

Maintainer | dev@chungyc.org |

Safe Haskell | Safe-Inferred |

Language | GHC2021 |

Part of Ninety-Nine Haskell Problems. Some solutions are in Solutions.P47.

# Documentation

evaluateCircuit :: [(Int, Int)] -> Bool -> Bool -> Bool Source #

Consider a logic circuit composed of NAND gates with binary input, specified as follows.

- A list of pairs of numbers for each NAND gate.
A pair

`(i,j)`

in the list denotes that the inputs for the NAND gate are the outputs for the`i`

th and`j`

th gates in the list, respectively, with the first element starting at index 1.- As a special case, -1 and -2 denote the first and second boolean variables fed into the circuit, respectively.
- An input to a NAND gate can only use output from a NAND gate which appears earlier in the list.

- The output of the last gate in the list is the output of the logic circuit.

Write a function to evaluate a given logic circuit as specified above.

### Examples

`>>>`

False`evaluateCircuit [(-1,-2)] True True`

`>>>`

True`evaluateCircuit [(-1,-2)] True False`

`>>>`

True`evaluateCircuit [(-1,-2), (1,1)] True True`

`>>>`

False`evaluateCircuit [(-1,-2), (1,1)] True False`

`>>>`

True`evaluateCircuit [(-1,-1),(-2,-2),(1,2)] True False`

`>>>`

False`evaluateCircuit [(-1,-1),(-2,-2),(1,2)] False False`

buildCircuit :: (Bool -> Bool -> Bool) -> [(Int, Int)] Source #

Any boolean function can be computed with logic circuits composed solely of NAND gates. I.e., NAND is a universal logic gate.

Write a function to return a logic circuit composed of NAND gates
which computes a given a binary boolean function.
The logic circuit should be in a form which `evaluateCircuit`

can evaluate.

### Examples

`>>>`

False`evaluateCircuit (buildCircuit (&&)) False False`

`>>>`

False`evaluateCircuit (buildCircuit (&&)) False True`

`>>>`

False`evaluateCircuit (buildCircuit (&&)) True False`

`>>>`

True`evaluateCircuit (buildCircuit (&&)) True True`

### Hint

There are only 16 binary boolean functions, ignoring how they are actually computed, so it is feasible to devise logic circuits for all of them manually.

To have a computer construct them automatically, which may be more difficult, take advantage of the fact that a boolean function can be represented by its truth table. Consider what the inputs must be like for a NAND gate to output a desired truth table.