Gerrymandering avec Logic Gates

16

La fonction majoritaire est une fonction booléenne qui prend trois entrées booléennes et renvoie la plus courante. Par exemple, si maj(x,y,z)est la fonction majoritaire et Tdénote vrai et Fdénote faux alors:

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

Cette question concerne l'écriture des fonctions booléennes en tant que compositions de fonctions majoritaires. Un exemple d'une composition à 5 aires de fonctions majoritaires est (x1,x2,x3,x4,x5) => maj(x1,x2,maj(x3,x4,x5)). Cette fonction renvoie la sortie suivante sur ces exemples de vecteurs d'entrée:

(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

Tâche

Écrivez un programme qui entre un entier positif n et une liste de vecteurs de longueur n de booléens et sort un arbre de portes majoritaires qui retourne vrai sur tous les vecteurs donnés si possible. La fonction peut renvoyer true ou false sur des vecteurs ne figurant pas dans la liste des contraintes.

  • La liste des vecteurs peut être entrée dans le format de votre choix. Si vous préférez, au lieu de saisir le vecteur, vous pouvez entrer la liste des vraies positions dans le vecteur. Ainsi, par exemple, [TTF,TFT,FTT]ou [[T,T,F],[T,F,T],[F,T,T]]ou [[1,2],[1,3],[2,3]](liste des positions réelles) sont très bien.

  • La sortie peut être n'importe quel format d'arbre valide. Par exemple, ça maj(maj(x1,x2,x3),x4,x5)marche. Vous voudrez probablement utiliser des nombres simples comme remplaçants pour les variables, comme dans [[1,2,3],4,5]. Le polissage inversé 123m45mest également correct, par exemple.

  • S'il n'y a aucune fonction qui fonctionne, votre programme devrait générer une erreur ou produire une valeur de falsey.

  • S'il existe plusieurs fonctions qui fonctionnent, votre programme peut renvoyer n'importe laquelle d'entre elles. La fonction n'a pas besoin d'être simplifiée. Par exemple, maj(x1,x1,x2)ou x1sont équivalents.

Notation

Voici le code golf: la solution la plus courte en octets gagne.

Cas de test:

Notez qu'il existe de nombreuses sorties possibles pour chacun de ces cas, vous devez donc écrire un script de vérificateur qui convertit votre sortie en fonction et vérifier que votre fonction renvoie true sur chacun des vecteurs d'entrée spécifiés.

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]]]]]
capuche
la source
"La composition 5 fonctions des fonctions majoritaires est (x1, x2, x3, x4, x5) => maj (x1, x2, maj (x3, x4, x5))" comment? Quelle devrait être la réponse si x1 = x2 = F; x3 = x4 = x5 = T; ?
tsh
J'ajouterai une table de vérité.
Hood
1
Que signifie une sortie de 1?
Mhmd
2
Titre suggéré: Gerrymandering avec portes logiques
Robert Fraser
1
@trichoplax Non, la sortie sur tous les vecteurs restants peut être n'importe quoi. Je mettrai à jour pour rendre cela explicite.
Hood

Réponses:

2

JavaScript (ES6), 260 octets

Prend l'entrée comme un tableau de tableaux de booléens. Renvoie un arbre de portes majoritaires indexées 1 ou renvoie une erreur de récursivité (1) si aucune solution n'existe.

La fonction principale f () tente récursivement de trouver une solution en appelant le solveur F () et en incrémentant le niveau d'imbrication maximum m à chaque itération.

(1) après une longue période, et en supposant une mémoire infinie

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)

Démo

Exemple

Voici un tableau de validation de la solution trouvée pour le dernier cas de test de la démo.

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
la source
Il existe une solution efficace que, espérons-le, quelqu'un trouvera. En attendant, je suppose que la force brute fonctionne ...
Hood
2

Mathematica, 121 octets

Une fonction anonyme qui prend son deuxième argument comme une liste des listes de vraies positions dans le vecteur des booléens.

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

Format légèrement plus agréable:

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

S'il y a moins de trois variables, coupez les vecteurs de contrainte pour voir s'il y a un "vrai" commun à toutes les contraintes. S'il y en a une, alors la fonction constante (x_1, x_2) -> x_i fonctionne, sinon elle est impossible (et lancera une erreur en essayant de prendre le premier élément d'une liste vide).

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

Explication:

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)) et prendre la majorité d'entre eux.

Pourquoi est-ce vrai? Eh bien, la fonction majoritaire satisfait deux propriétés:

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

  2. maj(x,y,False)maj(x,y,True). In general, if we say that FalseTrue and say (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
la source