Gerrymandering con puertas lógicas

16

La función mayoritaria es una función booleana que toma tres entradas booleanas y devuelve la más común. Por ejemplo, si maj(x,y,z)es la función mayoritaria y Tdenota verdadero y Fdenota falso, entonces:

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

Esta pregunta se refiere a escribir funciones booleanas como composiciones de funciones mayoritarias. Un ejemplo de una composición de 5 funciones de funciones mayoritarias es (x1,x2,x3,x4,x5) => maj(x1,x2,maj(x3,x4,x5)). Esta función devuelve el siguiente resultado en estos vectores de entrada de muestra:

(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

Tarea

Escriba un programa que ingrese un entero positivo n y una lista de vectores de longitud n de booleanos y genere un árbol de compuertas mayoritarias que devuelva verdadero en todos los vectores dados si es posible. La función puede devolver verdadero o falso en vectores que no están en la lista de restricciones.

  • La lista de vectores se puede ingresar en cualquier formato que desee. Si lo prefiere, en lugar de ingresar el vector, puede ingresar la lista de posiciones verdaderas en el vector. Entonces, por ejemplo, [TTF,TFT,FTT]or [[T,T,F],[T,F,T],[F,T,T]]o [[1,2],[1,3],[2,3]](lista de posiciones verdaderas) están bien.

  • La salida puede ser cualquier formato de árbol válido. Por ejemplo, maj(maj(x1,x2,x3),x4,x5)funciona. Probablemente desee utilizar números individuales como sustitutos para las variables, como en [[1,2,3],4,5]. El pulido inverso 123m45mtambién está bien, por ejemplo.

  • Si no hay una función que funcione, su programa debería generar un error o generar un valor falsey.

  • Si hay varias funciones que funcionan, su programa puede devolver cualquiera de ellas. La función no necesita ser simplificada. Por ejemplo, maj(x1,x1,x2)o x1son equivalentes.

Puntuación

Este es el código de golf: la solución más corta en bytes gana.

Casos de prueba:

Tenga en cuenta que hay muchos resultados posibles para cada uno de estos casos, por lo que debe escribir un script de verificación que convierta su salida en una función y verifique que su función devuelva verdadero en cada uno de los vectores de entrada especificados.

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]]]]]
capucha
fuente
"La composición de 5 funciones de funciones mayoritarias es (x1, x2, x3, x4, x5) => maj (x1, x2, maj (x3, x4, x5))" ¿cómo? Cuál debería ser la respuesta si x1 = x2 = F; x3 = x4 = x5 = T; ?
tsh
Agregaré una tabla de verdad.
Hood
1
¿Qué significa una salida de 1?
Mhmd
2
Título sugerido: Gerrymandering con puertas lógicas
Robert Fraser
1
@trichoplax No, la salida en todos los vectores restantes puede ser cualquier cosa. Actualizaré para hacer eso explícito.
Hood

Respuestas:

2

JavaScript (ES6), 260 bytes

Toma datos como una matriz de matrices de booleanos. Devuelve un árbol de puertas mayoritarias indexadas en 1 o arroja un error de recursión (1) si no existe una solución.

La función principal f () intenta recurrentemente encontrar una solución llamando al solucionador F () e incrementando el nivel máximo de anidamiento m en cada iteración.

(1) después de mucho tiempo, y asumiendo memoria infinita

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)

Manifestación

Ejemplo

A continuación se muestra una tabla de validación de la solución encontrada para el último caso de prueba de la demostración.

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
fuente
Hay una solución eficiente, que con suerte alguien encontrará. Mientras tanto, creo que la fuerza bruta funciona ...
Hood
2

Mathematica, 121 bytes

Una función anónima que toma su segundo argumento como una lista de las listas de posiciones verdaderas en el vector de booleanos.

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}}))]

Formateado ligeramente mejor:

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}}))]

Si hay menos de tres variables, intersecte los vectores de restricción para ver si hay un "Verdadero" común en todas las restricciones. Si hay uno, entonces la función constante (x_1, x_2) -> x_i funciona, de lo contrario es imposible (y arrojará un error al tratar de tomar el primer elemento de una lista vacía).

De lo contrario, sustituya f1=f(x1,x1,x2,x3,,xn1) , f2=f(x1,x2,x2,x3,,xn1) , y f3=f(x1,x2,x1,x3,,xn1)) , resuelve recursivamente cada uno de estos, luego establecef=maj(f1(x1,x3,x4,,xn),f2(x1,x2,x4,,xn),f2(x2,x3,x4,,xn)) .

Explicación:

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

x2x1x3x2x1x3

Una vez que conoce esta identidad, el algoritmo es claro: cuando hay dos o menos variables, el problema es trivial. De lo contrario, resuelve recursivamente los tres problemas de representar f(x1,x1,x3,x4,,xn)f(x1,x2,x2,x4,,xn)f(x3,x2,x3,x4,,xn))

¿Por qué es esto cierto? Bueno, la función mayoritaria cumple dos propiedades:

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

  2. Es monotónico. Es decir, maj(x,y,False)maj(x,y,True)y n ) si x iy i para todo i , entonces digo una funciónFalseTrue(x1,,xn)(y1,,yn)xiyiif(x1,xn)(y1,,yn)f(x1,xn)f(y1,,yn). La composición de las funciones monotónicas es monotónica, por lo que cada función que podemos construir a partir de la función mayoritaria es monotónica.

Resulta que las funciones monotónicas complementarias son exactamente la clase de funciones que se pueden construir a partir de puertas mayoritarias.

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

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

x1x2x3fx1=x2x3F es complementario, basta con tratar el caso X1=X2=Funlsmi y X3=Trtumi. En este caso,(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
fuente