¿Cuántas tablas de verdad si hay sólo $\land$ o $\lor$ $n$ variables?

Question

Por ejemplo, si tenemos tres operadores de $\land, \lor$$\neg$. Para $n$ variables, no se $2^{2^n}$ diferentes tablas de verdad. Porque para $2^n$ filas de la tabla de verdad, hay $2$ opciones - $T/F$.

Sin embargo, si sólo contamos con dos operadores de $\land$$\lor$, ¿cuántas tablas de verdad se queda para $n$ variables?

Answer 1

Realmente estás preguntando cómo muchas diferentes funciones booleanas de $n$ variables puede ser construido con $\land$$\lor$. Asumiendo que no permiten vacío expresiones (siempre verdadero o falso), esto es OEIS secuencia A007153.

Answer 2

Deje $v_1,\ldots,v_n$ ser las variables y $\phi(v_1,\ldots,v_n)$ una expresión en estas usando sólo $\land$ $\lor$ como conectivas. Entonces podemos reescribir esto como $$\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})$$ por lo que podemos representar con una expresión en $n$ variables como un par de expresiones en $n-1$ variables. Podemos asegurar que $\phi_2\to\phi_1$ y con esta condición, el par $(\phi_1,\phi_2)$ está determinada únicamente. Vamos a empezar a enumerar:

• Con $n=0$ tenemos $F$ $T$
• Con $n=1$ tenemos $F,v_1,T$ (a partir de $F\to F$, $F\to T, T\to T$)
• Con $n=2$ tenemos $F,v_1\land v_2,v_1,v_2,v_1\lor v_2,T$ (mineral de seis maneras para recoger $\phi_2\to\phi_1$$F\to v_1\to T$)
• Con $n=3$ tenemos un total de $20$ manera de elegir el $\phi_2\to \phi_1$ a partir de los anteriores (nota de que, con la excepción de $(v_1,v_2)$ una primera expresión en la lista anterior implica siempre una segunda expresión que es igual o a la derecha de la anterior).

No voy a escribir estos 20 opción explícitamente, ni seguir este camino aún más. En su lugar, la búsqueda OEIS para 2,3,6,20 y encontrar como principal efecto el número de monotonía funciones Booleanas de $n$ variables, que parece describir tu problema exactamente.