15
\$\begingroup\$

The majority function is a boolean function which takes three boolean inputs and returns the most common. For instance if maj(x,y,z) is the majority function and T denotes true and F denotes false then:

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

This question concerns writing boolean functions as compositions of majority functions. An example of a 5-ary composition of majority functions is (x1,x2,x3,x4,x5) => maj(x1,x2,maj(x3,x4,x5)). This function returns the following output on these sample input vectors:

(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

Task

Write a program which inputs a positive integer n and a list of length n vectors of booleans and outputs a tree of majority gates that returns true on all of the given vectors if possible. The function may return either true or false on vectors not in the list of constraints.

  • The list of vectors may be input in any format you like. If you prefer, instead of inputting the vector, you may input the list of true positions in the vector. So for instance, [TTF,TFT,FTT] or [[T,T,F],[T,F,T],[F,T,T]] or [[1,2],[1,3],[2,3]] (list of true positions) are all fine.

  • Output can be any valid tree format. For instance, maj(maj(x1,x2,x3),x4,x5) works. You will probably want to use single numbers as stand-ins for variables, as in [[1,2,3],4,5]. Reverse polish 123m45m is also okay, for instance.

  • If there is no function that works, your program should generate an error or output a falsey value.

  • If there are multiple functions that work, your program can return any of them. The function does not need to be simplified. For instance, maj(x1,x1,x2) or x1 are equivalent.

Scoring

This is code golf: Shortest solution in bytes wins.

Test cases:

Note that there are many possible outputs for each of these cases, so you should write a checker script that converts your output to a function and check that your function returns true on each of the specified input vectors.

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]]]]]
\$\endgroup\$
  • \$\begingroup\$ "5-ary composition of majority functions is (x1,x2,x3,x4,x5) => maj(x1,x2,maj(x3,x4,x5))" how? What the answer should be if x1=x2=F; x3=x4=x5=T; ? \$\endgroup\$ – tsh Jan 19 '18 at 5:44
  • \$\begingroup\$ I will add a truth table. \$\endgroup\$ – Hood Jan 19 '18 at 5:45
  • 1
    \$\begingroup\$ What does an output of 1 mean? \$\endgroup\$ – Mhmd Jan 19 '18 at 10:21
  • 2
    \$\begingroup\$ Suggested title: Gerrymandering with logic gates \$\endgroup\$ – Robert Fraser Jan 19 '18 at 16:32
  • 1
    \$\begingroup\$ @trichoplax No, the output on all remaining vectors can be anything. I will update to make that explicit. \$\endgroup\$ – Hood Oct 14 '18 at 18:42
2
\$\begingroup\$

JavaScript (ES6), 260 bytes

Takes input as an array of arrays of booleans. Returns a tree of 1-indexed majority gates or throws a recursion error (1) if no solution exists.

The main function f() recursively attempts to find a solution by calling the solver F() and incrementing the maximum nesting level m at each iteration.

(1) after a long time, and assuming infinite memory

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)

Demo

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)

test = a => console.log(JSON.stringify(f(a.split(',').map(s => [...s].map(c => c == 'T')))))

test('TFF')
test('TTF,TFT')
test('TTF,TFT,FTT')
test('TTTF,TTFT,TFTT,FTTT')
test('TTTFF,FTTFT,TFFFT')
test('TTTFFF,FTFTTF,TFFTFT')
test('TTTFF,TTFTF,TTFFT,TFTTF,TFTFT,TFFTT,FTTTF,FTTFT,FTFTT,FFTTT')

Example

Below is a validation table of the solution found for the last test case of the demo.

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
\$\endgroup\$
  • \$\begingroup\$ There is an efficient solution, which hopefully someone will find. In the meantime, I guess brute force sort of works... \$\endgroup\$ – Hood Jan 19 '18 at 16:30
1
\$\begingroup\$

Mathematica, 121 bytes

An anonymous function which takes its second argument as a list of the lists of true positions in the vector of booleans.

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

Formatted slightly nicer:

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

\$\def\maj{\mathrm{maj}}\def\T{\mathrm{True}}\def\F{\mathrm{False}}\$ If there are fewer than three variables, intersect the constraint vectors to see if there is a common "True" in all of the constraints. If there is one, then the constant function (x_1,x_2) --> x_i works, otherwise it is impossible (and will throw an error by trying to take the first element of an empty list).

Otherwise, substitute \$f_1=f(x_1,x_1,x_2,x_3,\ldots,x_{n-1})\$, \$f_2=f(x_1,x_2,x_2,x_3,\ldots,x_{n-1})\$, and \$f_3=f(x_1,x_2,x_1,x_3,\ldots,x_{n-1}))\$, recursively solve each of these, then set \$f=\maj(f_1(x_1,x_3,x_4,\ldots,x_n), f_2(x_1,x_2,x_4,\ldots,x_n),f_2(x_2,x_3,x_4,\ldots,x_n))\$.

Explanation:

This is a recursive algorithm that reduces the problem of finding a solution of an \$n\$ variable problem to finding three solutions to \$n-1\$ variable problems. The key observation that makes this work is that for \$f\$ one of the functions we are looking for we have: \$f(x_1,\ldots,x_n)=\maj(f(x_1,x_1,x_3,x_4,\ldots,x_n),f(x_1,x_2,x_2,\ldots),f(x_3,x_2,x_3,\ldots))\$

In the first position, we replaced \$x_2\$ with \$x_1\$, in the second position \$x_3\$ with \$x_2\$ and in the third position \$x_1\$ with \$x_3\$.

Once you know this identity, the algorithm is clear: when there are two or fewer variables, the problem is trivial. Otherwise, recursively solve the three problems of representing \$f(x_1,x_1,x_3,x_4,\ldots,x_n)\$, \$f(x_1,x_2,x_2,x_4,\ldots,x_n)\$, and \$f(x_3,x_2,x_3,x_4,\ldots,x_n))\$ and take the majority of them.

Why is this true? Well the majority function satisfies two properties:

  1. It is "complementary". That is, if \$!x\$ is the negation of \$x\$, then \$\maj(!x,!y,!z)=!\maj(x,y,z)\$. As a consequence, every function we can build out of the majority function is complementary.

  2. It is monotonic. That is, \$\maj(x,y,\F)\leq \maj(x,y,\T)\$. In general, if we say that \$\F\leq \T\$ and say \$(x_1,\ldots,x_n)\leq (y_1,\ldots, y_n)\$ if \$x_i\leq y_i\$ for all \$i\$, then I say a function \$f\$ is monotonic if \$(x_1,\ldots x_n)\leq(y_1,\ldots, y_n)\$ implies \$f(x_1,\ldots x_n)\leq f(y_1,\ldots, y_n)\$. 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(x_1,\ldots,x_n)=\maj(f(x_1,x_1,x_3,x_4,\ldots,x_n),f(x_1,x_2,x_2,x_4,\ldots,x_n),f(x_3,x_2,x_3,x_4,\ldots,x_n))\$

Let's set \$f_1(x_1,x_2,x_3,\ldots,x_n)=f(x_1,x_1,x_3,x_4,\ldots,x_n)\$, \$f_2(x_1,\ldots,x_n)=f(x_1,x_2,x_2,x_4,\ldots,x_n)\$ and \$f_3(x_1,\ldots,x_n)=f(x_3,x_2,x_3,x_4,\ldots,x_n)\$. To show that \$f=\maj(f_1,f_2,f_3)\$, we need to show that for any input, at least two of \$f_1\$, \$f_2\$, and \$f_3\$ are equal to \$f\$. We divide up into cases based on the values of \$x_1\$, \$x_2\$ and \$x_3\$. If \$x_1=x_2=x_3\$ then \$f_1=f_2=f_3=f\$.

Suppose not all of \$x_1\$, \$x_2\$, and \$x_3\$ are the same. By permuting the variables of \$f\$, we can assume that \$x_1=x_2\$ and \$x_3\$ is different and because \$f\$ is complementary, it suffices to deal with the case \$x_1=x_2=\F\$ and \$x_3=\T\$. In this case, \$(x_1,x_1,x_3)=(\F,\F,\T)=(x_1,x_2,x_3)\$, \$(x_1,x_2,x_2)=(\F,\F,\F)\leq (x_1,x_2,x_3)\$ and \$(x_3,x_2,x_3)=(\T, \F, \T) \geq (x_1,x_2,x_3)\$. By monotonicity we deduce that \$f_2\leq f_1=f\leq f_3\$. If \$f=\F\$ then \$f_2\leq \F\$ implies \$f_2=\F=f\$ and if \$f=\T\$ then \$f_3\geq \T\$ implies \$f_3=\T\$. Thus, at least two of \$f_1\$, \$f_2\$, and \$f_3\$ are equal to \$f\$ in all cases so \$f=\maj(f_1,f_2,f_3)\$.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.