Number of binary gates needed to compute AND and OR of n input bits simultaneously What is the minimal number of binary gates needed to compute AND and OR of $n$ input bits simultaneously?
The trivial upper bound is $2n-2$. I believe that this is optimal, but how to prove this? The standard 
gate elimination technique does not work here as by assigning a constant to any of the input variables
one trivializes one of the outputs. 

The problem is also given as an exercise 5.12 in the book "Complexity of Boolean Functions" by Ingo Wegener
in a slightly different form: "Let $f_n(x) = x_1\dots x_n \lor \bar{x}_1 \dots \bar{x}_n$. By the elimination method one
can prove only a lower bound of size $n+\Omega(1)$. Try to prove larger lower bounds."
This paper of Blum &amp; Seysen may be useful:

N.Blum, M. Seysen. Characterization of all Optimal Networks for a Simultaneous Computation of AND and NOR. Acta Inf. 21: 171-181 (1984)  

I have thought that for $x_1\dots x_n\vee \bar{x}_1\dots\bar{x}_n$ $2n-c$ lower bound can be obtained using methods of Blum &amp; Seysen, but it seems this is not the case.