Cruzar os fios sem cruzar os fios

Problema de lógica booleana (electrónica digital):
Cruza os fios sem cruzar os fios.

Preenche a caixa preta com NANDs: ==|)o---

PS: Com 12 NANDs é fácil - 12 NANDs de duas entradas.
Pensando um bocado consegue-se com 10 NANDs.
O óptimo é 8 NANDs - um NAND de três entradas e dois NANDs de uma entrada.

PS: Há uma patente americana com a solução óptima: U.S. Patent 3'248'573 (April 26, 1966)

Tabelas de verdade:
     +---+---+-----+        +---+---+-----+
AND: | A | B | out |  NAND: | A | B | out |
     +---+---+-----+        +---+---+-----+
     | 0 | 0 |  0  |        | 0 | 0 |  1  |
     | 0 | 1 |  0  |        | 0 | 1 |  1  |
     | 1 | 0 |  0  |        | 1 | 0 |  1  |
     | 1 | 1 |  1  |        | 1 | 1 |  0  |
     +---+---+-----+        +---+---+-----+

Cross the wires without crossing the wires

The Crossover Circuit

problem of logic (digital logic):

    input          output

 A -----> +-------+ -----> B              fill the black box
          | black |                       with some quantity
 B -----> |  box  | -----> A              of NANDs
          +-------+
                                          =====|)o-----

You can make it with 12 two-input nand-gates,
10 nand-gates
or 8 nand-gates (one three-input nand-gate and two single-input nand-gates)

There are a U.S. Patent with the optimal solution: U.S. Patent 3'248'573 (April 26, 1966)