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.
You want the Dedekind numbers (OEIS sequence A007153). The first few terms of the sequence: $(1, 4, 18, 166, 7579,\dots).$ The key is in the title "number of monotone Boolean functions". This is equivalent to being constructible from AND and OR. Read the sequence entry for more details and examples.
The part of the question about MAX and MIN makes sense in the context of a Lattice in the sense of an ordered structure. The Wikipedia article has some details. In particular, the two operations are usually denoted by $\;\vee\;$ and $\;\wedge\;$ and sometimes called "join" and "meet". The Boolean lattice is equivalent to the lattice of subsets of a fixed set using union and intersection as lattice operators.