Sebuah terhubung grafik adalah grafik yang berisi jalur antara dua simpul.

Tantangan

Buat sirkuit [gerbang NAND-input 2] yang menentukan apakah grafik 4-simpul terhubung.
(2 input gerbang dapat berupa bit input yang sama atau gerbang lainnya.)
Output True jika grafik terhubung, dan False sebaliknya.

Memasukkan

Enam kemungkinan tepi grafik sederhana dengan 4 simpul:

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

di mana _sebuah e _b mewakili apakah ada kelebihan antara simpul a dan b

Keterhubungan setara dengan kondisi berikut:

• Jika kurang dari 3 input Benar maka output Salah.

• Jika lebih dari 3 input Benar maka output Benar.

• Jika tepat 3 input Benar dan mereka membentuk segitiga kemudian output Salah.

• Kalau tidak, output Benar.

Jawaban yang menggunakan gerbang paling sedikit menang. Ikatan akan rusak oleh
kedalaman rangkaian terendah (panjang jalur terpanjang dari input ke output).

30 NANDS

Alih-alih bertanya kapan kita mendapatkan angka 1, saya mengajukan pertanyaan kapan kita mendapatkan angka 0. Lebih baik bertanya dengan cara ini karena ada kurang dari 0 daripada 1.

Berikut distribusi menurut jumlah sisi (baris ke-6 dari pascal's triangle)

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)

Mengajukan pertanyaan seperti ini, kita mendapatkan diagram dan ungkapan berikut

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

Kami mengasumsikan output akan default ke 1, tetapi akan berubah menjadi 0 dalam kondisi berikut

1.A 0 untuk tiga sisi yang berdekatan (uji 3 input)

2.A 0 untuk dua pasang sisi yang berlawanan (tes 4 input)

Persyaratan di atas sudah dipesan dengan cara yang akan memungkinkan mereka untuk dikelompokkan seperti di bawah ini. (Kebetulan, versi ekspresi ini simetris secara rotasi tentang titik 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

Skor untuk masing-masing &atau |ditempatkan di bawah simbol dan dibenarkan sebagai berikut:

Level 0: Kami berinvestasi dalam inverter untuk setiap input: 6 NANDS

Level 1: Kita dapat membangun OR dari gerbang NAND dengan meletakkan inverter pada input (total 3 NANDS) tetapi karena kita telah berinvestasi dalam 6 NAND pada langkah sebelumnya, kita dapat membuat 7 OR gerbang dari 7 gerbang NAND. Kami juga membutuhkan 3 DAN gerbang. Untuk ini, kita hanya akan menggunakan NAND dan membiarkan outputnya terbalik. 10 NANDS

Level 2: Sekali lagi kami membangun 4 OR gerbang dari gerbang NAND. Dalam setiap kasus kami memiliki 1 input dari gerbang OR, jadi kami harus membalikkannya. Tetapi input lainnya sudah terbalik (berasal dari salah satu NAND pada langkah sebelumnya yang sesuai dengan &simbol dalam tiga kasus, dan dari inverter di yang terakhir) sehingga kita hanya perlu 2 gerbang untuk setiap fungsi ATAU. 4 * 2 = 8

Level 3: Kita sekarang perlu DAN empat output bersama. Ini membutuhkan 3 gerbang AND, masing-masing dibangun dari 2 NAND, 3 * 2 = 6

Itu total 30 gerbang NAND, dengan kedalaman maksimal 2 + 2 + 4 = 8 NAND untuk cabang dengan |level 1 atau 3 + 1 + 4 = 8 NAND untuk cabang dengan &level 1.

Script Ruby berikut secara visual mengkonfirmasi bahwa ekspresi di atas adalah valid.

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

Tidak ada rangkaian yang lebih sederhana dari ini.

Ada kode untuk mengujinya di bawah gambar. Sedangkan untuk memahaminya, itu sulit. Ada beberapa gerbang IF di sana, dan input agak dikelompokkan menjadi segitiga dengan garis sudut bebas ditambahkan untuk analisis satu per satu, tetapi tidak dengan cara yang sederhana. Jika ada yang berhasil memahaminya, saya akan terkesan.

Kode Verilog dengan pengujian:

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

Kami hanya menyebutkan semua aturan, membangun fungsi boolean, dan menguranginya dalam NANDbentuk.

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

Hasil :

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

, di mana #1...#6ada 6 slot untuk argumen.

Kasus uji :

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

Keenam sisi dapat dibagi menjadi tiga pasang sisi yang berlawanan. Agar grafik terhubung, harus ada dua sisi yang berlawanan serta sisi ketiga, atau tiga sisi yang terhubung ke titik yang sama.

       •
       U

   Z   •   Y  
    V     W 
 •     X     •

Pasangan yang berlawanan adalah UX, VY, WZ, jadi:

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

Membangun AND dan OR gerbang dengan cara biasa, jumlah total gerbang yang digunakan adalah 3*3+7*3+34= 64.