Majority function of 11 inputs

Question

Problem: I need to create a circuit for the 11-input majority function using only AND and OR,assuming that each AND and OR can have multiple inputs (one AND/OR can compute the conjunction/disjunction of multiple inputs). This task has two sub-tasks

1. We are allowed to use only 1 OR as the output element and multiple ANDs.
2. We are allowed to use only 1 AND as the output element and multiple ORs.

Questions: How many elements do we have to use in each case?

Solution

1. By definition a majority function is a function which equals 1 if more than half of the elements equal 1, which means that we need to have any 6 elements to be equal to 1. Hence I conclude that the number of elements we need equals to $${11\choose 6} + 1=463$$
2. I don't know how to do that. I suspect that I need to convert the majority function to CNF but I don't know how to do it. My idea is: something like $$(\overline{x}_{i}+\overline{x}_{i+1}+\overline{x}_{i+2}+\overline{x}_{i+3})$$

repeated $${11\choose 5}$$ times, but since I have only AND and OR I need to express NOT through AND/OR and I don't know how.

3. Assuming that I'm right, how to prove that this is the maximum number of elements?

So, to sum up, my questions:

1. Am I right with #1?
2. How to finish the computation of the number of elements in #2?
3. How to prove #3?

Answer 1

Hint for a question raised in comments: Here is a 7-input majority circuit with 22 gates. Can you see how to generalize it to 11 inputs? (It is easiest to start by figuring out what the intuitive meaning of each of the horizontal wires is).

In general, this design uses $2k^2-3k+2$ gates to compute the majority of $2k-1$ inputs. It is not optimal for $k>4$, though.

Answer 2

The brute-force solution (using a, b, c, ... k as inputs):

CNF product-of-sums form:

(a+b+c+g+h+i) & (a+b+c+d+g+h) & (a+b+d+g+h+i) & (a+b+c+d+g+i) &
(a+c+d+g+h+i) & (a+b+c+d+h+i) & (b+c+d+g+h+i) & (a+b+c+g+h+j) & 
(a+b+g+h+i+j) & (a+b+c+g+i+j) & (a+c+g+h+i+j) & (a+b+c+h+i+j) & 
(b+c+g+h+i+j) & (a+b+d+g+h+j) & (a+b+c+d+g+j) & (a+c+d+g+h+j) & 
(a+b+c+d+h+j) & (b+c+d+g+h+j) & (a+b+d+g+i+j) & (a+d+g+h+i+j) & 
(a+b+d+h+i+j) & (b+d+g+h+i+j) & (a+c+d+g+i+j) & (a+b+c+d+i+j) & 
(b+c+d+g+i+j) & (a+c+d+h+i+j) & (c+d+g+h+i+j) & (b+c+d+h+i+j) & 
(a+b+c+e+g+h) & (a+b+e+g+h+i) & (a+b+c+e+g+i) & (a+c+e+g+h+i) & 
(a+b+c+e+h+i) & (b+c+e+g+h+i) & (a+b+d+e+g+h) & (a+b+c+d+e+g) & 
(a+c+d+e+g+h) & (a+b+c+d+e+h) & (b+c+d+e+g+h) & (a+b+d+e+g+i) & 
(a+d+e+g+h+i) & (a+b+d+e+h+i) & (b+d+e+g+h+i) & (a+c+d+e+g+i) & 
(a+b+c+d+e+i) & (b+c+d+e+g+i) & (a+c+d+e+h+i) & (c+d+e+g+h+i) & 
(b+c+d+e+h+i) & (a+b+e+g+h+j) & (a+b+c+e+g+j) & (a+c+e+g+h+j) & 
(a+b+c+e+h+j) & (b+c+e+g+h+j) & (a+b+e+g+i+j) & (a+e+g+h+i+j) & 
(a+b+e+h+i+j) & (b+e+g+h+i+j) & (a+c+e+g+i+j) & (a+b+c+e+i+j) & 
(b+c+e+g+i+j) & (a+c+e+h+i+j) & (c+e+g+h+i+j) & (b+c+e+h+i+j) & 
(a+b+d+e+g+j) & (a+d+e+g+h+j) & (a+b+d+e+h+j) & (b+d+e+g+h+j) & 
(a+c+d+e+g+j) & (a+b+c+d+e+j) & (b+c+d+e+g+j) & (a+c+d+e+h+j) & 
(c+d+e+g+h+j) & (b+c+d+e+h+j) & (a+d+e+g+i+j) & (a+b+d+e+i+j) & 
(b+d+e+g+i+j) & (a+d+e+h+i+j) & (d+e+g+h+i+j) & (b+d+e+h+i+j) & 
(a+c+d+e+i+j) & (c+d+e+g+i+j) & (b+c+d+e+i+j) & (c+d+e+h+i+j) & 
(a+b+c+g+h+k) & (a+b+g+h+i+k) & (a+b+c+g+i+k) & (a+c+g+h+i+k) & 
(a+b+c+h+i+k) & (b+c+g+h+i+k) & (a+b+d+g+h+k) & (a+b+c+d+g+k) & 
(a+c+d+g+h+k) & (a+b+c+d+h+k) & (b+c+d+g+h+k) & (a+b+d+g+i+k) & 
(a+d+g+h+i+k) & (a+b+d+h+i+k) & (b+d+g+h+i+k) & (a+c+d+g+i+k) & 
(a+b+c+d+i+k) & (b+c+d+g+i+k) & (a+c+d+h+i+k) & (c+d+g+h+i+k) & 
(b+c+d+h+i+k) & (a+b+g+h+j+k) & (a+b+c+g+j+k) & (a+c+g+h+j+k) & 
(a+b+c+h+j+k) & (b+c+g+h+j+k) & (a+b+g+i+j+k) & (a+g+h+i+j+k) & 
(a+b+h+i+j+k) & (b+g+h+i+j+k) & (a+c+g+i+j+k) & (a+b+c+i+j+k) & 
(b+c+g+i+j+k) & (a+c+h+i+j+k) & (c+g+h+i+j+k) & (b+c+h+i+j+k) & 
(a+b+d+g+j+k) & (a+d+g+h+j+k) & (a+b+d+h+j+k) & (b+d+g+h+j+k) & 
(a+c+d+g+j+k) & (a+b+c+d+j+k) & (b+c+d+g+j+k) & (a+c+d+h+j+k) & 
(c+d+g+h+j+k) & (b+c+d+h+j+k) & (a+d+g+i+j+k) & (a+b+d+i+j+k) & 
(b+d+g+i+j+k) & (a+d+h+i+j+k) & (d+g+h+i+j+k) & (b+d+h+i+j+k) & 
(a+c+d+i+j+k) & (c+d+g+i+j+k) & (b+c+d+i+j+k) & (c+d+h+i+j+k) & 
(a+b+e+g+h+k) & (a+b+c+e+g+k) & (a+c+e+g+h+k) & (a+b+c+e+h+k) & 
(b+c+e+g+h+k) & (a+b+e+g+i+k) & (a+e+g+h+i+k) & (a+b+e+h+i+k) & 
(b+e+g+h+i+k) & (a+c+e+g+i+k) & (a+b+c+e+i+k) & (b+c+e+g+i+k) & 
(a+c+e+h+i+k) & (c+e+g+h+i+k) & (b+c+e+h+i+k) & (a+b+d+e+g+k) & 
(a+d+e+g+h+k) & (a+b+d+e+h+k) & (b+d+e+g+h+k) & (a+c+d+e+g+k) & 
(a+b+c+d+e+k) & (b+c+d+e+g+k) & (a+c+d+e+h+k) & (c+d+e+g+h+k) & 
(b+c+d+e+h+k) & (a+d+e+g+i+k) & (a+b+d+e+i+k) & (b+d+e+g+i+k) & 
(a+d+e+h+i+k) & (d+e+g+h+i+k) & (b+d+e+h+i+k) & (a+c+d+e+i+k) & 
(c+d+e+g+i+k) & (b+c+d+e+i+k) & (c+d+e+h+i+k) & (a+b+e+g+j+k) & 
(a+e+g+h+j+k) & (a+b+e+h+j+k) & (b+e+g+h+j+k) & (a+c+e+g+j+k) & 
(a+b+c+e+j+k) & (b+c+e+g+j+k) & (a+c+e+h+j+k) & (c+e+g+h+j+k) & 
(b+c+e+h+j+k) & (a+e+g+i+j+k) & (a+b+e+i+j+k) & (b+e+g+i+j+k) & 
(a+e+h+i+j+k) & (e+g+h+i+j+k) & (b+e+h+i+j+k) & (a+c+e+i+j+k) & 
(c+e+g+i+j+k) & (b+c+e+i+j+k) & (c+e+h+i+j+k) & (a+d+e+g+j+k) & 
(a+b+d+e+j+k) & (b+d+e+g+j+k) & (a+d+e+h+j+k) & (d+e+g+h+j+k) & 
(b+d+e+h+j+k) & (a+c+d+e+j+k) & (c+d+e+g+j+k) & (b+c+d+e+j+k) & 
(c+d+e+h+j+k) & (a+d+e+i+j+k) & (d+e+g+i+j+k) & (b+d+e+i+j+k) & 
(d+e+h+i+j+k) & (c+d+e+i+j+k) & (a+b+c+f+g+h) & (a+b+f+g+h+i) & 
(a+b+c+f+g+i) & (a+c+f+g+h+i) & (a+b+c+f+h+i) & (b+c+f+g+h+i) & 
(a+b+d+f+g+h) & (a+b+c+d+f+g) & (a+c+d+f+g+h) & (a+b+c+d+f+h) & 
(b+c+d+f+g+h) & (a+b+d+f+g+i) & (a+d+f+g+h+i) & (a+b+d+f+h+i) & 
(b+d+f+g+h+i) & (a+c+d+f+g+i) & (a+b+c+d+f+i) & (b+c+d+f+g+i) & 
(a+c+d+f+h+i) & (c+d+f+g+h+i) & (b+c+d+f+h+i) & (a+b+f+g+h+j) & 
(a+b+c+f+g+j) & (a+c+f+g+h+j) & (a+b+c+f+h+j) & (b+c+f+g+h+j) & 
(a+b+f+g+i+j) & (a+f+g+h+i+j) & (a+b+f+h+i+j) & (b+f+g+h+i+j) & 
(a+c+f+g+i+j) & (a+b+c+f+i+j) & (b+c+f+g+i+j) & (a+c+f+h+i+j) & 
(c+f+g+h+i+j) & (b+c+f+h+i+j) & (a+b+d+f+g+j) & (a+d+f+g+h+j) & 
(a+b+d+f+h+j) & (b+d+f+g+h+j) & (a+c+d+f+g+j) & (a+b+c+d+f+j) & 
(b+c+d+f+g+j) & (a+c+d+f+h+j) & (c+d+f+g+h+j) & (b+c+d+f+h+j) & 
(a+d+f+g+i+j) & (a+b+d+f+i+j) & (b+d+f+g+i+j) & (a+d+f+h+i+j) & 
(d+f+g+h+i+j) & (b+d+f+h+i+j) & (a+c+d+f+i+j) & (c+d+f+g+i+j) & 
(b+c+d+f+i+j) & (c+d+f+h+i+j) & (a+b+e+f+g+h) & (a+b+c+e+f+g) & 
(a+c+e+f+g+h) & (a+b+c+e+f+h) & (b+c+e+f+g+h) & (a+b+e+f+g+i) & 
(a+e+f+g+h+i) & (a+b+e+f+h+i) & (b+e+f+g+h+i) & (a+c+e+f+g+i) & 
(a+b+c+e+f+i) & (b+c+e+f+g+i) & (a+c+e+f+h+i) & (c+e+f+g+h+i) & 
(b+c+e+f+h+i) & (a+b+d+e+f+g) & (a+d+e+f+g+h) & (a+b+d+e+f+h) & 
(b+d+e+f+g+h) & (a+c+d+e+f+g) & (a+b+c+d+e+f) & (b+c+d+e+f+g) & 
(a+c+d+e+f+h) & (c+d+e+f+g+h) & (b+c+d+e+f+h) & (a+d+e+f+g+i) & 
(a+b+d+e+f+i) & (b+d+e+f+g+i) & (a+d+e+f+h+i) & (d+e+f+g+h+i) & 
(b+d+e+f+h+i) & (a+c+d+e+f+i) & (c+d+e+f+g+i) & (b+c+d+e+f+i) & 
(c+d+e+f+h+i) & (a+b+e+f+g+j) & (a+e+f+g+h+j) & (a+b+e+f+h+j) & 
(b+e+f+g+h+j) & (a+c+e+f+g+j) & (a+b+c+e+f+j) & (b+c+e+f+g+j) & 
(a+c+e+f+h+j) & (c+e+f+g+h+j) & (b+c+e+f+h+j) & (a+e+f+g+i+j) & 
(a+b+e+f+i+j) & (b+e+f+g+i+j) & (a+e+f+h+i+j) & (e+f+g+h+i+j) & 
(b+e+f+h+i+j) & (a+c+e+f+i+j) & (c+e+f+g+i+j) & (b+c+e+f+i+j) & 
(c+e+f+h+i+j) & (a+d+e+f+g+j) & (a+b+d+e+f+j) & (b+d+e+f+g+j) & 
(a+d+e+f+h+j) & (d+e+f+g+h+j) & (b+d+e+f+h+j) & (a+c+d+e+f+j) & 
(c+d+e+f+g+j) & (b+c+d+e+f+j) & (c+d+e+f+h+j) & (a+d+e+f+i+j) & 
(d+e+f+g+i+j) & (b+d+e+f+i+j) & (d+e+f+h+i+j) & (c+d+e+f+i+j) & 
(a+b+f+g+h+k) & (a+b+c+f+g+k) & (a+c+f+g+h+k) & (a+b+c+f+h+k) & 
(b+c+f+g+h+k) & (a+b+f+g+i+k) & (a+f+g+h+i+k) & (a+b+f+h+i+k) & 
(b+f+g+h+i+k) & (a+c+f+g+i+k) & (a+b+c+f+i+k) & (b+c+f+g+i+k) & 
(a+c+f+h+i+k) & (c+f+g+h+i+k) & (b+c+f+h+i+k) & (a+b+d+f+g+k) & 
(a+d+f+g+h+k) & (a+b+d+f+h+k) & (b+d+f+g+h+k) & (a+c+d+f+g+k) & 
(a+b+c+d+f+k) & (b+c+d+f+g+k) & (a+c+d+f+h+k) & (c+d+f+g+h+k) & 
(b+c+d+f+h+k) & (a+d+f+g+i+k) & (a+b+d+f+i+k) & (b+d+f+g+i+k) & 
(a+d+f+h+i+k) & (d+f+g+h+i+k) & (b+d+f+h+i+k) & (a+c+d+f+i+k) & 
(c+d+f+g+i+k) & (b+c+d+f+i+k) & (c+d+f+h+i+k) & (a+b+f+g+j+k) & 
(a+f+g+h+j+k) & (a+b+f+h+j+k) & (b+f+g+h+j+k) & (a+c+f+g+j+k) & 
(a+b+c+f+j+k) & (b+c+f+g+j+k) & (a+c+f+h+j+k) & (c+f+g+h+j+k) & 
(b+c+f+h+j+k) & (a+f+g+i+j+k) & (a+b+f+i+j+k) & (b+f+g+i+j+k) & 
(a+f+h+i+j+k) & (f+g+h+i+j+k) & (b+f+h+i+j+k) & (a+c+f+i+j+k) & 
(c+f+g+i+j+k) & (b+c+f+i+j+k) & (c+f+h+i+j+k) & (a+d+f+g+j+k) & 
(a+b+d+f+j+k) & (b+d+f+g+j+k) & (a+d+f+h+j+k) & (d+f+g+h+j+k) & 
(b+d+f+h+j+k) & (a+c+d+f+j+k) & (c+d+f+g+j+k) & (b+c+d+f+j+k) & 
(c+d+f+h+j+k) & (a+d+f+i+j+k) & (d+f+g+i+j+k) & (b+d+f+i+j+k) & 
(d+f+h+i+j+k) & (c+d+f+i+j+k) & (a+b+e+f+g+k) & (a+e+f+g+h+k) & 
(a+b+e+f+h+k) & (b+e+f+g+h+k) & (a+c+e+f+g+k) & (a+b+c+e+f+k) &
(b+c+e+f+g+k) & (a+c+e+f+h+k) & (c+e+f+g+h+k) & (b+c+e+f+h+k) & 
(a+e+f+g+i+k) & (a+b+e+f+i+k) & (b+e+f+g+i+k) & (a+e+f+h+i+k) & 
(e+f+g+h+i+k) & (b+e+f+h+i+k) & (a+c+e+f+i+k) & (c+e+f+g+i+k) & 
(b+c+e+f+i+k) & (c+e+f+h+i+k) & (a+d+e+f+g+k) & (a+b+d+e+f+k) & 
(b+d+e+f+g+k) & (a+d+e+f+h+k) & (d+e+f+g+h+k) & (b+d+e+f+h+k) & 
(a+c+d+e+f+k) & (c+d+e+f+g+k) & (b+c+d+e+f+k) & (c+d+e+f+h+k) & 
(a+d+e+f+i+k) & (d+e+f+g+i+k) & (b+d+e+f+i+k) & (d+e+f+h+i+k) & 
(c+d+e+f+i+k) & (a+e+f+g+j+k) & (a+b+e+f+j+k) & (b+e+f+g+j+k) & 
(a+e+f+h+j+k) & (e+f+g+h+j+k) & (b+e+f+h+j+k) & (a+c+e+f+j+k) & 
(c+e+f+g+j+k) & (b+c+e+f+j+k) & (c+e+f+h+j+k) & (a+e+f+i+j+k) & 
(e+f+g+i+j+k) & (b+e+f+i+j+k) & (e+f+h+i+j+k) & (c+e+f+i+j+k) & 
(a+d+e+f+j+k) & (d+e+f+g+j+k) & (b+d+e+f+j+k) & (d+e+f+h+j+k) & 
(c+d+e+f+j+k) & (d+e+f+i+j+k)

DNF sum-of-products form:

abcghi + abcdgh + abdghi + abcdgi + acdghi + abcdhi + bcdghi +
abcghj + abghij + abcgij + acghij + abchij + bcghij + abdghj +
abcdgj + acdghj + abcdhj + bcdghj + abdgij + adghij + abdhij +
bdghij + acdgij + abcdij + bcdgij + acdhij + cdghij + bcdhij +
abcegh + abeghi + abcegi + aceghi + abcehi + bceghi + abdegh +
abcdeg + acdegh + abcdeh + bcdegh + abdegi + adeghi + abdehi +
bdeghi + acdegi + abcdei + bcdegi + acdehi + cdeghi + bcdehi +
abeghj + abcegj + aceghj + abcehj + bceghj + abegij + aeghij +
abehij + beghij + acegij + abceij + bcegij + acehij + ceghij +
bcehij + abdegj + adeghj + abdehj + bdeghj + acdegj + abcdej +
bcdegj + acdehj + cdeghj + bcdehj + adegij + abdeij + bdegij +
adehij + deghij + bdehij + acdeij + cdegij + bcdeij + cdehij +
abcghk + abghik + abcgik + acghik + abchik + bcghik + abdghk +
abcdgk + acdghk + abcdhk + bcdghk + abdgik + adghik + abdhik +
bdghik + acdgik + abcdik + bcdgik + acdhik + cdghik + bcdhik +
abghjk + abcgjk + acghjk + abchjk + bcghjk + abgijk + aghijk +
abhijk + bghijk + acgijk + abcijk + bcgijk + achijk + cghijk +
bchijk + abdgjk + adghjk + abdhjk + bdghjk + acdgjk + abcdjk +
bcdgjk + acdhjk + cdghjk + bcdhjk + adgijk + abdijk + bdgijk +
adhijk + dghijk + bdhijk + acdijk + cdgijk + bcdijk + cdhijk +
abeghk + abcegk + aceghk + abcehk + bceghk + abegik + aeghik +
abehik + beghik + acegik + abceik + bcegik + acehik + ceghik +
bcehik + abdegk + adeghk + abdehk + bdeghk + acdegk + abcdek +
bcdegk + acdehk + cdeghk + bcdehk + adegik + abdeik + bdegik +
adehik + deghik + bdehik + acdeik + cdegik + bcdeik + cdehik +
abegjk + aeghjk + abehjk + beghjk + acegjk + abcejk + bcegjk +
acehjk + ceghjk + bcehjk + aegijk + abeijk + begijk + aehijk +
eghijk + behijk + aceijk + cegijk + bceijk + cehijk + adegjk +
abdejk + bdegjk + adehjk + deghjk + bdehjk + acdejk + cdegjk +
bcdejk + cdehjk + adeijk + degijk + bdeijk + dehijk + cdeijk +
abcfgh + abfghi + abcfgi + acfghi + abcfhi + bcfghi + abdfgh +
abcdfg + acdfgh + abcdfh + bcdfgh + abdfgi + adfghi + abdfhi +
bdfghi + acdfgi + abcdfi + bcdfgi + acdfhi + cdfghi + bcdfhi +
abfghj + abcfgj + acfghj + abcfhj + bcfghj + abfgij + afghij +
abfhij + bfghij + acfgij + abcfij + bcfgij + acfhij + cfghij +
bcfhij + abdfgj + adfghj + abdfhj + bdfghj + acdfgj + abcdfj +
bcdfgj + acdfhj + cdfghj + bcdfhj + adfgij + abdfij + bdfgij +
adfhij + dfghij + bdfhij + acdfij + cdfgij + bcdfij + cdfhij +
abefgh + abcefg + acefgh + abcefh + bcefgh + abefgi + aefghi +
abefhi + befghi + acefgi + abcefi + bcefgi + acefhi + cefghi +
bcefhi + abdefg + adefgh + abdefh + bdefgh + acdefg + abcdef +
bcdefg + acdefh + cdefgh + bcdefh + adefgi + abdefi + bdefgi +
adefhi + defghi + bdefhi + acdefi + cdefgi + bcdefi + cdefhi +
abefgj + aefghj + abefhj + befghj + acefgj + abcefj + bcefgj +
acefhj + cefghj + bcefhj + aefgij + abefij + befgij + aefhij +
efghij + befhij + acefij + cefgij + bcefij + cefhij + adefgj +
abdefj + bdefgj + adefhj + defghj + bdefhj + acdefj + cdefgj +
bcdefj + cdefhj + adefij + defgij + bdefij + defhij + cdefij +
abfghk + abcfgk + acfghk + abcfhk + bcfghk + abfgik + afghik +
abfhik + bfghik + acfgik + abcfik + bcfgik + acfhik + cfghik +
bcfhik + abdfgk + adfghk + abdfhk + bdfghk + acdfgk + abcdfk +
bcdfgk + acdfhk + cdfghk + bcdfhk + adfgik + abdfik + bdfgik +
adfhik + dfghik + bdfhik + acdfik + cdfgik + bcdfik + cdfhik +
abfgjk + afghjk + abfhjk + bfghjk + acfgjk + abcfjk + bcfgjk +
acfhjk + cfghjk + bcfhjk + afgijk + abfijk + bfgijk + afhijk +
fghijk + bfhijk + acfijk + cfgijk + bcfijk + cfhijk + adfgjk +
abdfjk + bdfgjk + adfhjk + dfghjk + bdfhjk + acdfjk + cdfgjk +
bcdfjk + cdfhjk + adfijk + dfgijk + bdfijk + dfhijk + cdfijk +
abefgk + aefghk + abefhk + befghk + acefgk + abcefk + bcefgk +
acefhk + cefghk + bcefhk + aefgik + abefik + befgik + aefhik +
efghik + befhik + acefik + cefgik + bcefik + cefhik + adefgk +
abdefk + bdefgk + adefhk + defghk + bdefhk + acdefk + cdefgk +
bcdefk + cdefhk + adefik + defgik + bdefik + defhik + cdefik +
aefgjk + abefjk + befgjk + aefhjk + efghjk + befhjk + acefjk +
cefgjk + bcefjk + cefhjk + aefijk + efgijk + befijk + efhijk +
cefijk + adefjk + defgjk + bdefjk + defhjk + cdefjk + defijk

A simplification approach would be to identify and use common subexpressions.