Right at the top of the page, the author remarks that for n<=4 the parity function (f(a,b,c,d) = a XOR b XOR c XOR d) requires a maximal number of AND/OR gates to compute. Later on, he mentions that someone else proved that this isn't true for very large n. Nowhere on the page does he say what the worst case actually is, though the tables indicate that there are three genuinely-different Boolean functions of 5 variables that need 28 gates.
So, what's the worst case for n=5?
It turns out (http://boolean-oracle.swtch.com/?q=x%2by%2bz%2bw%2bv+in+0,1,...) that one of those three functions is the one that's true if and only if either 0, or 1, or 3 of the five variables are TRUE. (The other two are slight variations on that theme.)
It would be interesting to know whether the worst-case functions for larger n have as much symmetry as the worst cases for n<=5. (I'd guess not.)
So, what's the worst case for n=5?
It turns out (http://boolean-oracle.swtch.com/?q=x%2by%2bz%2bw%2bv+in+0,1,...) that one of those three functions is the one that's true if and only if either 0, or 1, or 3 of the five variables are TRUE. (The other two are slight variations on that theme.)
It would be interesting to know whether the worst-case functions for larger n have as much symmetry as the worst cases for n<=5. (I'd guess not.)