How many truth tables if there are only $\land$ or $\lor$ for $n$ variables?

Question

For example, if we have three operators $\land, \lor$ and $\neg$. For $n$ variables, there will be $2^{2^n}$ different truth tables. Because for $2^n$ rows of the truth table, there are $2$ choices - $T/F$.

However, if we have only two operators $\land$ and $\lor$, how many truth tables will be left for $n$ variables?

Answer 1

You are really asking how many different boolean functions of $n$ variables can be constructed using $\land$ and $\lor$. Assuming you don't allow empty expressions (always true or always false), this is OEIS sequence A007153.

Answer 2

Let $v_1,\ldots,v_n$ be the variables and $\phi(v_1,\ldots,v_n)$ an expression in these using only $\land$ and $\lor$ as connectives. Then we can rewrite this as $$\phi(v_1,\ldots,v_n)\iff v_n\land\phi_1(v_1,\ldots,v_{n-1})\lor \phi_2(v_1,\ldots,v_{n-1})$$ so that we can represent an expression in $n$ variables as a pair of expressions in $n-1$ variables. We can ensure that $\phi_2\to\phi_1$ and with this condition, the pair $(\phi_1,\phi_2)$ is uniquely determined. Let's start enumerating:

• With $n=0$ we have $F$ and $T$
• With $n=1$ we have $F,v_1,T$ (from $F\to F$, $F\to T, T\to T$)
• With $n=2$ we have $F,v_1\land v_2,v_1,v_2,v_1\lor v_2,T$ (there ore six ways to pick $\phi_2\to\phi_1$ from $F\to v_1\to T$)
• With $n=3$ we have a total of $20$ way to pick $\phi_2\to \phi_1$ from the above (note that with the exception of $(v_1,v_2)$ a first expression in the above list always implies a second expression that is equal or to the right of the former).

I shall not write these 20 option down explicitly, nor follow this trail further. Instead, we search OEIS for 2,3,6,20 and find as main hit the number of monotone Boolean functions of $n$ variables, which seems to describe your problem exactly.