Подключенный граф представляет собой график , который содержит путь между любыми двумя вершинами.

Вызов

Создайте схему [2-входной NAND-gate], которая определяет, подключен ли 4-вершинный граф.
(2 входа шлюза могут быть одним и тем же входным битом или другим вентилем.)
Выведите True, если граф подключен, и False в противном случае.

вход

Шесть возможных ребер простого графа с 4 вершинами:

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

где _a e _b представляет, есть ли ребро между вершинами a и b

Связность эквивалентна следующим условиям:

• Если менее 3 входов имеют значение True, выведите False.

• Если более 3 входов имеют значение True, выведите True.

• Если ровно 3 входа имеют значение True и они образуют треугольник, выведите False.

• В противном случае выведите True.

Ответ, который использует наименьшее количество ворот, побеждает. Связи будут разорваны по
наименьшей глубине цепи (длина самого длинного пути от входа до выхода).

30 NANDS

Вместо того, чтобы спрашивать, когда мы получим 1, я задал вопрос, когда мы получим 0. Лучше задать это так, потому что меньше 0, чем 1.

Вот распределение по количеству ребер (6 ряд треугольника Паскаля)

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)

Задавая вопрос таким образом, мы получаем следующую диаграмму и выражение

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

Мы предполагаем, что выход будет по умолчанию 1, но изменится на 0 при любом из следующих условий

1.A 0 для трех смежных ребер (тест 3 входа)

2.A 0 для двух противоположных пар ребер (тест 4 входа)

Вышеуказанные условия уже упорядочены таким образом, чтобы их можно было сгруппировать, как показано ниже. (Кстати, эта версия выражения является вращательно-симметричной относительно вершины 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

Оценка для каждого &или |ставится ниже символа и обосновывается следующим образом:

Уровень 0: Мы инвестируем в инвертор для каждого входа: 6 NANDS

Уровень 1: Мы можем построить ИЛИ из логического элемента NAND, поставив инвертор на входе (всего 3 NANDS), но, как мы уже вложили в 6 NANDS на предыдущем шаге, мы можем сделать 7 вентилей ИЛИ из 7 вентилей NAND. Нам также нужны 3 И ворота. Для этого мы просто будем использовать NAND и оставить выход инвертированным. 10 NANDS

Уровень 2: Снова мы строим 4 ИЛИ ворота от NAND. В каждом случае у нас есть 1 вход от логического элемента ИЛИ, поэтому мы должны инвертировать его. Но другой вход уже инвертирован (поступающий от одного из NAND на предыдущем шаге, который соответствует &символу в трех случаях, и от инвертора на последнем), поэтому нам нужны только 2 вентиля для каждой функциональности ИЛИ. 4 * 2 = 8

Уровень 3: Теперь нам нужно И четыре выхода вместе. Для этого требуется 3 элемента И, каждый из которых состоит из 2 NAND, 3 * 2 = 6

Это в общей сложности 30 вентилей NAND, с максимальной глубиной 2 + 2 + 4 = 8 NAND для ветвей с |уровнем 1 или 3 + 1 + 4 = 8 NAND для веток с &уровнем 1.

Следующий скрипт Ruby визуально подтверждает, что приведенное выше выражение является допустимым.

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

Нет более простой схемы, чем эта.

Ниже приведен код для тестирования. Что касается понимания, это сложно. Там есть пара шлюзов ПЧ, и входы в некотором роде сгруппированы в треугольник с линиями свободного угла, добавленными для анализа одна за другой, но не простым способом. Если кому-то удастся это понять, я буду впечатлен.

Verilog код с тестированием:

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

Ким Ойхус

Mathematica, 17 ворот

Мы просто перечисляем все правила, конструируем логическую функцию и минимизируем ее по NANDформе.

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

Результат :

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

где #1...#66 слотов для аргументов.

Тестовые случаи :

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

Шесть ребер можно разделить на три пары противоположных ребер. Для связности графа должны быть либо два противоположных ребра, либо третье ребро, либо три ребра, соединенные с одной и той же вершиной.

       •
       U

   Z   •   Y  
    V     W 
 •     X     •

Противоположные пары - UX, VY, WZ, поэтому:

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

Построение вентилей И и ИЛИ обычным способом, общее количество используемых шлюзов 3*3+7*3+34= 64.