Gerrymandering with Logic Gates
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)=&gt;(F=(a,d,I=a[i=0].map(_=&gt;++i),g=(a,b)=&gt;b[1]?b.reduce((s,i)=&gt;s+g(a,i),0)&gt;1:a[b-1])=&gt;I.find(i=&gt;a.every(a=&gt;g(a,i)))||d&amp;&amp;(I.reduce((a,x)=&gt;[...a,...a.map(y=&gt;[...y,x])],[[]]).some(b=&gt;r=b.length==3&amp;&amp;F(a.map(a=&gt;[...a,g(a,b)]),d-1,[...I,b]))&amp;&amp;r))(a,m)||f(a,-~m)


Demo



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

test = a =&gt; console.log(JSON.stringify(f(a.split(',').map(s =&gt; [...s].map(c =&gt; 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]]] --&gt; [F,T,[T,F,T]] -&gt; [F,T,T] --&gt; T
TTFTF | [F,[T,T,T],[F,T,[T,T,F]]] --&gt; [F,T,[F,T,T]] -&gt; [F,T,T] --&gt; T
TTFFT | [T,[T,T,F],[F,F,[T,T,F]]] --&gt; [T,T,[F,F,T]] -&gt; [T,T,F] --&gt; T
TFTTF | [F,[T,F,T],[T,T,[T,F,T]]] --&gt; [F,T,[T,T,T]] -&gt; [F,T,T] --&gt; T
TFTFT | [T,[T,F,F],[T,F,[T,F,T]]] --&gt; [T,F,[T,F,T]] -&gt; [T,F,T] --&gt; T
TFFTT | [T,[T,F,T],[F,T,[T,F,F]]] --&gt; [T,T,[F,T,F]] -&gt; [T,T,F] --&gt; T
FTTTF | [F,[F,T,T],[T,T,[F,T,T]]] --&gt; [F,T,[T,T,T]] -&gt; [F,T,T] --&gt; T
FTTFT | [T,[F,T,F],[T,F,[F,T,T]]] --&gt; [T,F,[T,F,T]] -&gt; [T,F,T] --&gt; T
FTFTT | [T,[F,T,T],[F,T,[F,T,F]]] --&gt; [T,T,[F,T,F]] -&gt; [T,T,F] --&gt; T
FFTTT | [T,[F,F,T],[T,T,[F,F,T]]] --&gt; [T,F,[T,T,F]] -&gt; [T,F,T] --&gt; T