Um gráfico conectado é um gráfico que contém um caminho entre dois vértices.

Desafio

Construa um circuito [2-NAND-gate] que determina se um gráfico de 4 vértices está conectado.
(As 2 entradas de uma porta podem ser o mesmo bit de entrada ou outra porta.)
Saída True se o gráfico estiver conectado e False caso contrário.

Entrada

As seis arestas possíveis de um gráfico simples com 4 vértices:

[ ₀ e ₁ , ₀ e ₂ , ₁ e ₂ , ₀ e ₃ , ₁ e ₃ , ₂ e ₃ ]

onde _um e _b representa se existe uma aresta entre os vértices de um e b

A conexão é equivalente às seguintes condições:

• Se menos de 3 entradas forem True, produza False.

• Se mais de 3 entradas forem True, emita True.

• Se exatamente 3 entradas forem Verdadeiras e formarem um triângulo, então produza Falso.

• Caso contrário, produza True.

A resposta que usa o menor número de portões vence. Os laços serão quebrados pela
profundidade mais baixa do circuito (comprimento do (s) caminho (s) mais longo (s) da entrada à saída).

30 NANDS

Em vez de perguntar quando obtemos um 1, fiz a pergunta quando obtemos um 0. É melhor perguntar desta maneira, porque há menos 0s que 1s.

Aqui está a distribuição de acordo com o número de arestas (6a linha do triângulo de Pascal)

Edges     0  1  2  3  4  5  6
Frequency 1  6 15 20 15  6  1 (total 64)
Output    0  0  0  *  1  1  1
* = 0 if triangle (4 possibilities) 1 if claw (4 possibilities) 
1 if two opposite edges and one other (12 possibilities)

Fazendo a pergunta dessa maneira, obtemos o seguinte diagrama e expressão

 ___D___
|\     /|
| E   F |
|  \ /  |
A   X   C
|  / \  |
| /   \ |
|/__B__\|

(A|C|D|B)&(A|D|E)&(D|B|E|F)&(C|B|E)&(A|C|E|F)&(D|F|C)&(A|F|B) 

Assumimos que a saída será padronizada como 1, mas será alterada para 0 sob qualquer uma das seguintes condições

1.A 0 para três arestas adjacentes (teste 3 entradas)

2.A 0 para dois pares de arestas opostos (teste 4 entradas)

Os termos acima já estão ordenados da maneira que permitirá que sejam agrupados conforme abaixo. (Aliás, esta versão da expressão é simétrica rotacionalmente perto do vértice AFB.)

((A|D)|((C|B)&E))&((B|E)|((D|F)&C))&((C|F)|((A|E)&D))&(A|F|B)    =6 inverters
   1      1  1       1      1  1       1      1  1      1        =10 (7 OR with both inputs inverted, 3 NAND)
      2                 2                 2               2      =8  (4 OR with one input inverted)
                 2                 2                 2           =6  (3 AND) 
                                                        Total    =30

A pontuação para cada um &ou |é colocada abaixo do símbolo e justificada da seguinte forma:

Nível 0: Investimos em um inversor para cada entrada: 6 NANDS

Nível 1: Podemos construir um OR a partir de uma porta NAND colocando um inversor na entrada (total de 3 NANDS), mas como já investimos em 6 NANDS na etapa anterior, podemos fazer 7 portas OR a partir de 7 portas NAND. Também precisamos de 3 portas. Para isso, apenas usaremos NANDs e deixaremos a saída invertida. 10 NANDS

Nível 2: Novamente construímos 4 portas OR a partir de portas NAND. Em cada caso, temos 1 entrada de uma porta OR, portanto, temos que inverter isso. Mas a outra entrada já está invertida (proveniente de uma das NANDs na etapa anterior que corresponde a um &símbolo em três casos e de um inversor na última), portanto, precisamos apenas de 2 portas para cada funcionalidade OR. 4 * 2 = 8

Nível 3: agora precisamos AND das quatro saídas juntas. Isso requer 3 portas E, cada uma construída com 2 NANDs, 3 * 2 = 6

No total, são 30 portões NAND, com profundidade máxima de 2 + 2 + 4 = 8 NANDs para galhos com |nível 1 ou 3 + 1 + 4 = 8 NANDs para galhos com &nível 1.

O script Ruby a seguir confirma visualmente que a expressão acima é válida.

64.times{|i|
  a=i%2
  b=i/2%2
  c=i/4%2
  d=i/8%2
  e=i/16%2 
  f=i/32%2

puts i, ((a|d)|((c|b)&e))&((b|e)|((d|f)&c))&((c|f)|((a|e)&d))&(a|f|b)

puts " ___#{d}___
|\\     /|
| #{e}   #{f} |
|  \\ /  |
#{a}   X   #{c}
|  / \\  |
| /   \\ |
|/__#{b}__\\|


"
}

19 NANDs

Não existe um circuito mais simples que esse.

Há um código para testá-lo abaixo da imagem. Quanto à compreensão, isso é difícil. Existem alguns portões IF, e as entradas são agrupadas em um triângulo com as linhas de canto livres adicionadas para análise uma a uma, mas não de uma maneira simples. Se alguém conseguir entender, ficarei impressionado.

Código Verilog com teste:

// 4-vertex Connectedness Tester                                                                  
// Minimal at 19 NANDs                                                                            
//                                                                                                
// By Kim Øyhus 2018 (c) into (CC BY-SA 3.0)                                                      
// This work is licensed under the Creative Commons Attribution 3.0                               
// Unported License. To view a copy of this license, visit                                        
// https://creativecommons.org/licenses/by-sa/3.0/                                                
//                                                                                                
// This is my entry to win this Programming Puzzle & Code Golf                                    
// at Stack Exchange:                                                                             
// /codegolf/69912/build-a-4-vertex-connectedness-tester-using-nand-gates/                                                                                      
//                                                                                                
// I am sure there are no simpler solutions to this problem.                                      
// It has a logical depth of 11, which is deeper than                                             
// circuits using a few more NANDs.                                                               

module counting6 ( in_000, in_001, in_002, in_003, in_004, in_005, in_006, out000 );
  input  in_000, in_001, in_002, in_003, in_004, in_005, in_006;
  output out000;
  wire   wir000, wir001, wir002, wir003, wir004, wir005, wir006, wir007, wir008, wir009, wir010, wir011, wir012, wir013, wir014, wir015, wir016, wir017;

  nand gate000 ( wir000, in_000, in_000 );
  nand gate001 ( wir001, in_001, in_003 );
  nand gate002 ( wir002, wir001, wir000 );
  nand gate003 ( wir003, in_002, wir002 );
  nand gate004 ( wir004, wir002, wir002 );
  nand gate005 ( wir005, wir004, in_002 );
  nand gate006 ( wir006, wir005, wir004 );
  nand gate007 ( wir007, in_005, wir006 );
  nand gate008 ( wir008, in_003, wir006 );    
  nand gate009 ( wir009, in_004, wir003 );
  nand gate010 ( wir010, wir003, wir009 );
  nand gate011 ( wir011, wir009, wir000 );
  nand gate012 ( wir012, wir011, in_001 );
  nand gate013 ( wir013, wir008, wir012 );
  nand gate014 ( wir014, wir013, in_005 );
  nand gate015 ( wir015, wir006, wir013 );
  nand gate016 ( wir016, wir015, wir007 );
  nand gate017 ( wir017, wir016, wir010 );
  nand gate018 ( out000, wir014, wir017 );
endmodule


module connecting6_test;
   reg [5:0] X;
   wire a;

  counting6 U1 (
  .in_000 (X[0]),
  .in_001 (X[1]),
  .in_002 (X[2]),
  .in_003 (X[3]),
  .in_004 (X[4]),
  .in_005 (X[5]),
  .in_006 (X[6]),
  .out000 (a )
  );

  initial begin
    X = 0;
  end

  always
    #10  X = X+1;

 initial  begin
    $display("\t\t     \t_");
    $display("\t\ttime,\t \\db/_,\tconnected");
    $monitor("%d,\t%b,\t%d",$time, X, a );
  end

  initial
   #630  $finish;

endmodule

// iverilog -o hello hello.v                                                                      
// vvp hello                                                                                      

Kim Øyhus

Mathematica, 17 portões

Simplesmente enumeramos todas as regras, construímos a função booleana e a minimizamos na NANDforma.

#->If[Total@#<3||
       MemberQ[{{1,1,1,0,0,0},{1,0,0,1,1,0},{0,1,0,1,0,1},{0,0,1,0,1,1}},#]
       ,0,1] /.{1->True,0->False}& /@
     Tuples[{0,1},6];
BooleanMinimize[BooleanFunction[rule], "NAND"]

Resultado :

(#1⊼#2⊼#4)⊼(#1⊼#2⊼#5)⊼(#1⊼#2⊼#6)⊼(#1⊼#3⊼#4)⊼ \
(#1⊼#3⊼#5)⊼(#1⊼#3⊼#6)⊼(#1⊼#4⊼#6)⊼(#1⊼#5⊼#6)⊼ \
(#2⊼#3⊼#4)⊼(#2⊼#3⊼#5)⊼(#2⊼#3⊼#6)⊼(#2⊼#4⊼#5)⊼ \
(#2⊼#5⊼#6)⊼(#3⊼#4⊼#5)⊼(#3⊼#4⊼#6)⊼(#4⊼#5⊼#6)&

, onde #1...#6estão 6 espaços para argumentos.

Casos de teste :

f=%; (* assign the function to symbol f *)

f[True, True, True, True, False, False]
(* True *)

f[True, True, False, True, False, False]
(* True *) (*, three Trues do not form a triangle *)

f[True, True, True, False, False, False]
(* False *) (*, three Trues form a triangle *)

64 NANDs

As seis arestas podem ser divididas em três pares de arestas opostas. Para que um gráfico seja conectado, deve haver duas arestas opostas e uma terceira aresta ou três arestas conectadas ao mesmo vértice.

       •
       U

   Z   •   Y  
    V     W 
 •     X     •

Os pares opostos são UX, VY, WZ, então:

A = U+V   ;3 gates
B = W+X
C = Y+Z

D = UV(B+C)  ;2+2+3=7 gates
E = WX(A+C)
F = YZ(C+A)

Result = D+E+F+UVW+UYZ+XVZ+XWY ; 18 + 16 = 34 gates

Construindo portas AND e OR da maneira usual, o número total de portas usadas é 3*3+7*3+34= 64.