Połączony wykres jest wykresem, który zawiera ścieżkę między dwoma wierzchołkami.

Wyzwanie

Zbuduj obwód [2-wejściowa bramka NAND], który określa, czy podłączony jest wykres 4-wierzchołkowy.
(2 wejścia bramki mogą być tym samym bitem wejściowym lub inną bramą.)
Wyjście Prawda, jeśli wykres jest podłączony, i False w przeciwnym razie.

Wejście

Sześć możliwych krawędzi prostego wykresu z 4 wierzchołkami:

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

gdzie e _b przedstawia czy istnieje krawędź pomiędzy wierzchołkami i B

Łączność jest równoważna z następującymi warunkami:

• Jeśli mniej niż 3 wartości wejściowe to Prawda, wówczas wartość wyjściowa False.

• Jeśli więcej niż 3 wartości wejściowe są Prawdą, wówczas wartość wyjściowa Prawda.

• Jeśli dokładnie 3 dane wejściowe są Prawdą i tworzą one trójkąt, wówczas wysyłają False.

• W przeciwnym razie należy wyprowadzić wartość True.

Odpowiedź wykorzystująca najmniej bramek wygrywa. Więzy zostaną zerwane przez
najniższą głębokość obwodu (długość najdłuższych ścieżek od wejścia do wyjścia).

30 NANDS

Zamiast pytać, kiedy otrzymujemy 1, zadałem pytanie, kiedy otrzymujemy 0. Lepiej jest zadawać to w ten sposób, ponieważ jest mniej 0 niż 1.

Oto rozkład według liczby krawędzi (6. rząd trójkąta Pascala)

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)

Zadając pytanie w ten sposób, otrzymujemy następujący schemat i wyrażenie

 ___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) 

Zakładamy, że wyjście będzie domyślnie ustawione na 1, ale zmieni się na 0 w dowolnym z poniższych warunków

1.A 0 dla trzech sąsiednich krawędzi (test 3 wejścia)

2.A 0 dla dwóch przeciwnych par krawędzi (test 4 wejścia)

Powyższe warunki są już uporządkowane w sposób, który umożliwi ich grupowanie, jak poniżej. (Nawiasem mówiąc, ta wersja wyrażenia jest obrotowo symetryczna względem wierzchołka 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

Wynik dla każdego &lub |jest umieszczony pod symbolem i uzasadniony w następujący sposób:

Poziom 0: Inwestujemy w falownik dla każdego wejścia: 6 NANDS

Poziom 1: Możemy zbudować OR z bramki NAND, umieszczając falownik na wejściu (łącznie 3 NANDS), ale ponieważ już zainwestowaliśmy w 6 NANDS w poprzednim kroku, możemy wykonać 7 bram OR z 7 bram NAND. Potrzebujemy również 3 bramek. W tym celu użyjemy NAND i pozostawimy wynik odwrócony. 10 NANDS

Poziom 2: Ponownie budujemy 4 bramki OR z bram NAND. W każdym przypadku mamy 1 wejście z bramki OR, więc musimy to odwrócić. Ale drugie wejście jest już odwrócone (pochodzące z jednego z NAND w poprzednim kroku, który odpowiada &symbolowi w trzech przypadkach, oraz z falownika w ostatnim), więc potrzebujemy tylko 2 bramek dla każdej funkcji OR. 4 * 2 = 8

Poziom 3: Teraz musimy ORAZ cztery wyjścia razem. Wymaga to 3 bramek AND, każda zbudowana z 2 NAND, 3 * 2 = 6

To łącznie 30 bramek NAND, przy maksymalnej głębokości 2 + 2 + 4 = 8 NAND dla gałęzi |na poziomie 1 lub 3 + 1 + 4 = 8 NAND dla gałęzi &na poziomie 1.

Poniższy skrypt Ruby wizualnie potwierdza, że ​​powyższe wyrażenie jest poprawne.

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 NAND

Nie ma prostszego obwodu niż ten.

Pod obrazem znajduje się kod do testowania. Jeśli chodzi o zrozumienie, to trudne. Jest tam kilka bram IF, a dane wejściowe są trochę zgrupowane w trójkąt z wolnymi liniami narożnymi dodawanymi do analizy jeden po drugim, ale nie w prosty sposób. Jeśli komuś uda się to zrozumieć, będę pod wrażeniem.

Kod Verilog z testowaniem:

// 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 bram

Po prostu wyliczamy wszystkie reguły, konstruujemy funkcję boolowską i minimalizujemy ją w NANDformie.

#->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"]

Wynik :

(#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)&

, gdzie #1...#6jest 6 miejsc na argumenty.

Przypadki testowe :

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 NAND

Sześć krawędzi można podzielić na trzy pary przeciwległych krawędzi. Aby wykres mógł zostać połączony, muszą istnieć dwie przeciwległe krawędzie oraz trzecia krawędź lub trzy krawędzie połączone z tym samym wierzchołkiem.

       •
       U

   Z   •   Y  
    V     W 
 •     X     •

Przeciwnymi parami są UX, VY, WZ, więc:

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

Budując bramy AND i OR w zwykły sposób, całkowita liczba użytych bram wynosi 3*3+7*3+34= 64.