Consider a Boolean function $f(x\_1, x\_2, \dots, x\_n)$ from $\{0,1\}^n$ to $\{0,1\}$. It is well known that there are $2^{(2^n)}$ such functions, because for each of $2^n$ possible input vectors you can choose the result. Moreover, all these functions can be constructed with AND, OR, NOT, e.g. using disjunctive normal form. (Obviously we allow each input $x\_i$ to appear multiple times in the logic formula.) My question is: 

**How many such functions can be constructed if you can use AND, OR, but you cannot use NOT?**

As usual, a function is defined by its outputs. So two different-looking formulas that agree on every input counts as the same function, e.g. $(x\_1 \land x\_2) \lor x\_3$ is the same function as $(x\_1 \lor x\_3) \land (x\_2 \lor x\_3).$

**My thoughts:**

At the very minimum, the function now must return $1$ when all inputs are $1$s, and must return $0$ when all inputs are $0$s. (Note: constant functions $f\equiv 1$ and $f\equiv 0$ cannot be constructed using AND, OR, without NOT and without the literals $1, 0$ themselves.) This upperbounds the number to $2^{(2^n-2)}$, because for those two input vectors you no longer have a choice of output. However, I suspect this bound is extremely loose.

More generally, consider input vectors $x$ and $y$ where $x\_i = 1 \Rightarrow y\_i = 1$ (or equivalently, $y\_i = 0 \Rightarrow x\_i = 0$). Then *I think* any function with $f(x) = 1$ forces $f(y) = 1$, and similarly $f(y) =0$ forces $f(x) = 0$. This is because turning some $0$s in the input into $1$s cannot decrease the output if you are only combining with AND, OR, but without NOT. (However, I am not sure how to make this reasonsing rigorous... maybe assume a tree structure of the formula and recurse up the tree?)

Anyway, assuming the previous paragraph is correct, then it seems one approach is to consider an input vector $x$ as the subset of indices $\{i: x\_i = 1\}$. These $2^n$ subsets are partially ordered by inclusion, and any $f()$ must kind of define a "surface" of transition or a "cut" in the directed graph of ordering s.t. $f = 1$ on one side of the surface/cut (the side including the all $1$s vector), and $f=0$ on the other side. However:

* (A) I have no idea how to count the number of such surfaces/cuts, and
* (B) I am not sure every such surface/cut can be constructed with AND, OR, but without NOT. (I *think* each surface/cut can be constructed, as a disjunctive normal form of the "minimal" subsets for which $f = 1$, but I'm not perfectly sure. Anyway if some surface/cut cannot be constructed, this would still provide an interesting upperbound on the number of such functions.)

**Further motivation:**

My original motivation was actually how many functions of $n$ real variables can be constructed by composing with $\max(,)$ and $\min(,)$, allowing each variable to appear multiple times in the formula. However, after I noticed that $\max(x,\min(y,z)) = \min(\max(x,y), \max(x,z))$, *I think* they act like the Boolean AND, OR, so *I think* the questions are actually equivalent. (Comments on this point are also welcome, even though it is not my main question.)

Finally, expert users of MSE please feel free to edit the tags... I'm not sure I'm using the right ones for this question.