Problems.P47

Description

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

Synopsis

# 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 ith and jth 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

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

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

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

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

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

>>> evaluateCircuit [(-1,-1),(-2,-2),(1,2)] False 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

>>> evaluateCircuit (buildCircuit (&&)) False False
False

>>> evaluateCircuit (buildCircuit (&&)) False True
False

>>> evaluateCircuit (buildCircuit (&&)) True False
False

>>> evaluateCircuit (buildCircuit (&&)) True True
True


### Hint

Expand

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.