Gerrymandering с логическими воротами

16

Мажоритарная функция - это логическая функция, которая принимает три логических входа и возвращает наиболее распространенные. Например, если maj(x,y,z)является мажоритарной функцией и Tобозначает true и Fобозначает false, то:

maj(T,T,T) = T
maj(T,T,F) = T
maj(T,F,F) = F
maj(F,F,F) = F

Этот вопрос касается написания булевых функций как составов функций большинства. Примером 5-арной композиции мажоритарных функций является (x1,x2,x3,x4,x5) => maj(x1,x2,maj(x3,x4,x5)). Эта функция возвращает следующие выходные данные для этих примеров входных векторов:

(T,T,F,F,F) => maj(T,T,maj(F,F,F)) = maj(T,T,F) = T
(T,F,T,T,F) => maj(T,F,maj(T,T,F)) = maj(T,F,T) = T
(T,F,T,F,F) => maj(T,F,maj(T,F,F)) = maj(T,F,F) = F
(F,F,F,T,T) => maj(F,F,maj(F,T,T)) = maj(F,F,T) = F

задача

Напишите программу, которая вводит положительное целое число n и список логических векторов длины n и выводит дерево мажоритарных вентилей, которое возвращает true для всех заданных векторов, если это возможно. Функция может возвращать true или false для векторов, не входящих в список ограничений.

  • Список векторов может быть введен в любом формате, который вам нравится. Если вы предпочитаете, вместо ввода вектора, вы можете ввести список истинных позиций в векторе. Так, например, [TTF,TFT,FTT]или [[T,T,F],[T,F,T],[F,T,T]]или [[1,2],[1,3],[2,3]](список истинных позиций) все в порядке.

  • Выходными данными может быть любой допустимый формат дерева. Например, maj(maj(x1,x2,x3),x4,x5)работает. Возможно, вы захотите использовать отдельные числа в качестве резервных для переменных, как в [[1,2,3],4,5]. 123m45mНапример, обратная полировка тоже подойдет.

  • Если функция не работает, ваша программа должна выдать ошибку или вывести значение Falsey.

  • Если работает несколько функций, ваша программа может вернуть любую из них. Функция не нуждается в упрощении. Например, maj(x1,x1,x2)или x1эквивалентны.

счет

Это код гольф: выигрывает самое короткое решение в байтах.

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

Обратите внимание, что существует много возможных выходных данных для каждого из этих случаев, поэтому вы должны написать скрипт проверки, который преобразует ваши выходные данные в функцию и проверяет, что ваша функция возвращает true для каждого из указанных входных векторов.

Input: 3, [TFF]
Output: 1 or [1,1,2] or [1,[1,2,2],[1,1,3]] or other equivalent

Input: 3, [TFF,FTF]
Output: Falsey or error (it's not possible)

Input: 3, [TTF,TFT]
Output: [1,2,3] or 1 or other equivalent

Input: 3, [TTF,TFT,FTT]
Output: [1,2,3] or [1,3,2] or other equivalent

Input: 4, [TTFF,TFTF,FFTT]
Output: Falsey or error

Input: 4, [TTTF,TTFT,TFTT,FTTT]
Output: [1, 2, 3] or [2,3,4], or many other options

Input: 5, [TTTFF,FTTFT,TFFFT]
Output: [1,[1,[1,2,5],[2,4,5]],3] or many other options 

Input: 6, [TTTFFF,FTFTTF,TFFTFT]
Output: [1, 2, 4] or [1, [1, 2, 4], [2, 3, 4]] or others

Input: 5, [TTTFF,TTFTF,TTFFT,TFTTF,TFTFT,TFFTT,FTTTF,FTTFT,FTFTT,FFTTT]
Output: [[1, [1, 3, 5], 4], [1, 2, [2, 4, 5]], [2, 3, [3, 4, 5]]] or others

Input: 7, [TTTTFFF,TTTFTFF,TTTFFTF,TTTFFFT,TTFTTFF,TTFTFTF,TTFTFFT,TTFFTTF,TTFFTFT,TTFFFTT,TFTTTFF,TFTTFTF,TFTTFFT,TFTFTTF,TFTFTFT,TFTFFTT,TFFTTTF,TFFTTFT,TFFTFTT,TFFFTTT,FTTTTFF,FTTTFTF,FTTTFFT,FTTFTTF,FTTFTFT,FTTFFTT,FTFTTTF,FTFTTFT,FTFTFTT,FTFFTTT,FFTTTTF,FFTTTFT,FFTTFTT,FFTFTTT,FFFTTTT]
Output: [[[1, [1, [1, 4, 7], 6], 5], [1, [1, 3, [3, 6, 7]], [3, 5, [5, 6, 7]]], [3, 4, [4, [4, 5, 7], 6]]], [[1, [1, [1, 4, 7], 6], 5], [1, 2, [2, [2, 5, 7], 6]], [2, [2, 4, [4, 6, 7]], [4, 5, [5, 6, 7]]]], [[2, [2, [2, 4, 7], 6], 5], [2, 3, [3, [3, 5, 7], 6]], [3, [3, 4, [4, 6, 7]], [4, 5, [5, 6, 7]]]]]
капот
источник
«5-арная композиция большинства функций имеет вид (x1, x2, x3, x4, x5) => maj (x1, x2, maj (x3, x4, x5))» как? Какой ответ должен быть, если x1 = x2 = F; x3 = x4 = х5 = Т; ?
TSH
Я добавлю таблицу правды.
Капот
1
Что означает вывод 1?
Mhmd
2
Предлагаемое название: Gerrymandering с логическими воротами
Роберт Фрейзер
1
@trichoplax Нет, выходные данные по всем оставшимся векторам могут быть любыми. Я обновлю, чтобы сделать это явным.
капот

Ответы:

2

JavaScript (ES6), 260 байт

Принимает ввод как массив массивов логических значений. Возвращает дерево 1-индексированных мажорных ворот или выдает ошибку рекурсии (1), если решения не существует.

Основная функция f () рекурсивно пытается найти решение, вызывая решатель F () и увеличивая максимальный уровень вложенности m на каждой итерации.

(1) после долгого времени и принимая бесконечную память

f=(a,m)=>(F=(a,d,I=a[i=0].map(_=>++i),g=(a,b)=>b[1]?b.reduce((s,i)=>s+g(a,i),0)>1:a[b-1])=>I.find(i=>a.every(a=>g(a,i)))||d&&(I.reduce((a,x)=>[...a,...a.map(y=>[...y,x])],[[]]).some(b=>r=b.length==3&&F(a.map(a=>[...a,g(a,b)]),d-1,[...I,b]))&&r))(a,m)||f(a,-~m)

демонстрация

пример

Ниже приведена таблица проверки решения, найденного для последнего контрольного примера демонстрации.

12345 | [5,[1,2,4],[3,4,[1,2,3]]]
------+-------------------------------------------------------------
TTTFF | [F,[T,T,F],[T,F,[T,T,T]]] --> [F,T,[T,F,T]] -> [F,T,T] --> T
TTFTF | [F,[T,T,T],[F,T,[T,T,F]]] --> [F,T,[F,T,T]] -> [F,T,T] --> T
TTFFT | [T,[T,T,F],[F,F,[T,T,F]]] --> [T,T,[F,F,T]] -> [T,T,F] --> T
TFTTF | [F,[T,F,T],[T,T,[T,F,T]]] --> [F,T,[T,T,T]] -> [F,T,T] --> T
TFTFT | [T,[T,F,F],[T,F,[T,F,T]]] --> [T,F,[T,F,T]] -> [T,F,T] --> T
TFFTT | [T,[T,F,T],[F,T,[T,F,F]]] --> [T,T,[F,T,F]] -> [T,T,F] --> T
FTTTF | [F,[F,T,T],[T,T,[F,T,T]]] --> [F,T,[T,T,T]] -> [F,T,T] --> T
FTTFT | [T,[F,T,F],[T,F,[F,T,T]]] --> [T,F,[T,F,T]] -> [T,F,T] --> T
FTFTT | [T,[F,T,T],[F,T,[F,T,F]]] --> [T,T,[F,T,F]] -> [T,T,F] --> T
FFTTT | [T,[F,F,T],[T,T,[F,F,T]]] --> [T,F,[T,T,F]] -> [T,F,T] --> T
Arnauld
источник
Существует эффективное решение, которое, надеюсь, кто-то найдет. В то же время, я думаю, что грубая сила вроде работает ...
Капюшон
2

Mathematica, 121 байт

Анонимная функция, которая принимает второй аргумент в виде списка истинных позиций в векторе логических значений.

f[n_][s_]:=If[n<3,(Intersection@@s)[[1]],{#/. 2->1,#2/.{2->1,3->2},#3}&@@(1+f[n-1]/@(s-1/.{{0->1},{1->2,0->1},{0->2}}))]

Отформатирован немного лучше:

f[n_][s_] := If[n < 3, (Intersection @@s)[[1]],
   {# /. 2 -> 1, #2 /. {2 -> 1, 3 -> 2}, #3} & @@ 
    (1 + f[n - 1] /@ (s - 1 /. {{0 -> 1}, {1 -> 2, 0 -> 1}, {0 -> 2}}))]

Если существует менее трех переменных, пересекайте векторы ограничений, чтобы увидеть, есть ли общее «Истина» во всех ограничениях. Если она есть, то функция константы (x_1, x_2) -> x_i работает, иначе это невозможно (и выдает ошибку, пытаясь взять первый элемент пустого списка).

f1=f(x1,x1,x2,x3,,xn1)f2=f(x1,x2,x2,x3,,xn1)f3=f(x1,x2,x1,x3,,xn1))f=maj(f1(x1,x3,x4,,xn),f2(x1,x2,x4,,xn),f2(x2,x3,x4,,xn))

Объяснение:

nn1ff(x1,,xn)=maj(f(x1,x1,x3,x4,,xn),f(x1,x2,x2,),f(x3,x2,x3,))

x2x1x3x2x1x3

f(x1,x1,x3,x4,,xn)f(x1,x2,x2,x4,,xn)f(x3,x2,x3,x4,,xn))

Почему это правда? Ну, функция большинства удовлетворяет двум свойствам:

  1. !xxmaj(!x,!y,!z)=!maj(x,y,z)

  2. maj(x,y,False)maj(x,y,True)FalseTrue(x1,,xn)(y1,,yn) if xiyi for all i, then I say a function f is monotonic if (x1,xn)(y1,,yn) implies f(x1,xn)f(y1,,yn). The composition of monotonic functions is monotonic so every function we can build out of the majority function is monotonic.

It turns out that complementary monotonic functions are exactly the class of functions that can be built out of majority gates.

Now, we show that for f a complementary monotonic function, our identity holds: f(x1,,xn)=maj(f(x1,x1,x3,x4,,xn),f(x1,x2,x2,x4,,xn),f(x3,x2,x3,x4,,xn))

Let's set f1(x1,x2,x3,,xn)=f(x1,x1,x3,x4,,xn), f2(x1,,xn)=f(x1,x2,x2,x4,,xn) and f3(x1,,xn)=f(x3,x2,x3,x4,,xn). To show that f=maj(f1,f2,f3), we need to show that for any input, at least two of f1, f2, and f3 are equal to f. We divide up into cases based on the values of x1, x2 and x3. If x1=x2=x3 then f1=f2=f3=f.

Suppose not all of x1, x2, and x3 are the same. By permuting the variables of f, we can assume that x1=x2 and x3 is different and because f is complementary, it suffices to deal with the case x1=x2=False and x3=True. In this case, (x1,x1,x3)=(False,False,True)=(x1,x2,x3), (x1,x2,x2)=(False,False,False)(x1,x2,x3) and (x3,x2,x3)=(True,False,True)(x1,x2,x3). By monotonicity we deduce that f2f1=ff3. If f=False then f2False implies f2=False=f and if f=True then f3True implies f3=True. Thus, at least two of f1, f2, and f3 are equal to f in all cases so f=maj(f1,f2,f3).

Hood
источник