Número de funciones booleanas de $n$ variables construibles a partir de AND y OR, pero sin NOT

Question

Consideremos una función booleana $f(x_1, x_2, \dots, x_n)$ de $\{0,1\}^n$ a $\{0,1\}$ . Es bien sabido que hay $2^{(2^n)}$ tales funciones, porque para cada una de $2^n$ posibles vectores de entrada se puede elegir el resultado. Además, todas estas funciones se pueden construir con AND, OR, NOT, por ejemplo, utilizando la forma normal disyuntiva. (Obviamente, permitimos que cada entrada $x_i$ aparezca varias veces en la fórmula lógica). Mi pregunta es

¿Cuántas funciones de este tipo se pueden construir si se puede utilizar AND, OR, pero no se puede utilizar NOT?

Como es habitual, una función se define por sus resultados. Así, dos fórmulas de aspecto diferente que coinciden en cada entrada cuentan como la misma función, por ejemplo $(x_1 \land x_2) \lor x_3$ es la misma función que $(x_1 \lor x_3) \land (x_2 \lor x_3).$

Mis pensamientos:

Como mínimo, la función debe devolver ahora $1$ cuando todas las entradas son $1$ s, y debe devolver $0$ cuando todas las entradas son $0$ s. (Nota: las funciones constantes $f\equiv 1$ y $f\equiv 0$ no se puede construir con AND, OR, sin NOT y sin los literales $1, 0$ a sí mismos). Esto limita el número a $2^{(2^n-2)}$ porque para esos dos vectores de entrada ya no se puede elegir la salida. Sin embargo, sospecho que este límite es extremadamente flojo.

De forma más general, consideremos los vectores de entrada $x$ y $y$ donde $x_i = 1 \Rightarrow y_i = 1$ (o, de forma equivalente, $y_i = 0 \Rightarrow x_i = 0$ ). Entonces Creo que cualquier función con $f(x) = 1$ fuerzas $f(y) = 1$ , y de forma similar $f(y) =0$ fuerzas $f(x) = 0$ . Esto se debe a que al girar algunos $0$ s en la entrada en $1$ s no puede disminuir la salida si sólo se combina con AND, OR, pero sin NOT. (Sin embargo, no estoy seguro de cómo hacer este razonamiento riguroso... ¿quizás asumir una estructura de árbol de la fórmula y recurrir hacia arriba del árbol?)

De todos modos, asumiendo que el párrafo anterior es correcto, entonces parece que un enfoque es considerar un vector de entrada $x$ como el subconjunto de índices $\{i: x_i = 1\}$ . Estos $2^n$ Los subconjuntos están parcialmente ordenados por inclusión, y cualquier $f()$ debe definir una especie de "superficie" de transición o un "corte" en el grafo dirigido de ordenación s.t. $f = 1$ en un lado de la superficie/corte (el lado que incluye el todo $1$ s vector), y $f=0$ en el otro lado. Sin embargo:

• (A) No tengo ni idea de cómo contar el número de tales superficies/cortes, y

• (B) No estoy seguro de que todas esas superficies/cortes puedan construirse con AND, OR, pero sin NOT. (I piense en cada superficie/corte puede construirse, como una forma normal disyuntiva de los subconjuntos "mínimos" para los que $f = 1$ pero no estoy muy seguro. De todos modos, si no se puede construir alguna superficie/corte, esto seguiría proporcionando un límite superior interesante en el número de tales funciones).

Más motivación:

Mi motivación original era en realidad cuántas funciones de $n$ las variables reales se pueden construir componiendo con $\max(,)$ y $\min(,)$ permitiendo que cada variable aparezca varias veces en la fórmula. Sin embargo, después de que me diera cuenta de que $\max(x,\min(y,z)) = \min(\max(x,y), \max(x,z))$ , Creo que actúan como los booleanos AND, OR, por lo que Creo que las preguntas son realmente equivalentes. (Los comentarios sobre este punto también son bienvenidos, aunque no es mi pregunta principal).

Por último, los usuarios expertos de MSE no duden en editar las etiquetas... No estoy seguro de estar usando las correctas para esta pregunta.

Answer 1

Usted quiere que el Números Dedekind (secuencia OEIS A007153) . Los primeros términos de la secuencia: $(1, 4, 18, 166, 7579,\dots).$ La clave está en el título "número de funciones booleanas monótonas". Esto equivale a ser construible a partir de AND y OR. Lea la entrada de la secuencia para obtener más detalles y ejemplos.

La parte de la pregunta sobre MAX y MIN tiene sentido en el contexto de un Celosía en el sentido de una estructura ordenada. El artículo de Wikipedia contiene algunos detalles. En particular, las dos operaciones se suelen denotar por $\;\vee\;$ y $\;\wedge\;$ y a veces se denominan "join" y "meet". El entramado booleano es equivalente al entramado de subconjuntos de un conjunto fijo utilizando la unión y la intersección como operadores de entramado.

Answer 2

Cualquier fórmula de este tipo se puede poner en DNF mediante la distribución repetida de AND sobre OR. Y, como por absorción tenemos que $p + pq=p$ Esto significa que sólo tenemos que encontrar el número de maneras en que podemos formar una colección de términos donde ningún término es parte de otro término.

Por ejemplo, para $n=3$ (Digamos que tenemos $p$ , $q$ y $r$ ) podemos crear las siguientes colecciones de términos:

$p$

$q$

$r$

$p+q$

$p+r$

$q+r$

$p+q+r$

$p+qr$

$q+pr$

$r+pq$

$pq$

$pr$

$qr$

$pq+pr$

$pq+qr$

$pr+qr$

$pq+pr+qr$

$pqr$

Como tal, el problema es equivalente a encontrar el número de conjuntos de subconjuntos de un conjunto de $n$ elementos tales que no hay dos elementos de cualquier conjunto de subconjuntos (es decir, no hay dos subconjuntos del conjunto original) que sean un subconjunto cada uno.