¿cuántas funciones booleanas semánticamente diferentes existen para n variables booleanas?

Question

En pocas palabras, se trata de una pregunta para un curso que estoy haciendo - la redacción exacta es la siguiente:

"Dadas n variables booleanas, ¿cuántas funciones booleanas 'semánticamente' diferentes puedes construir?".

Yo mismo lo intenté y me quedé bastante atascado. La pregunta no indica cuántos operadores booleanos hay (and, or, xor, nand, nor, iff, implies, not) ni si se deben utilizar paréntesis, es decir, a ^ (b v c) es diferente de (a ^ b) v c.

Así pues, mi pregunta para usted es: ¿es posible esta pregunta dada la escasa información disponible?

¿Va a ser algo como ${n^x}$ donde x es el número de operadores booleanos.

Agradeceríamos cualquier orientación al respecto.

Answer 1

Esta cuestión, en cierto sentido, es una cuestión de combinaciones.

Podemos empezar con una función de un solo valor de variables booleanas. Afirmo que existen $2^n$ combinaciones de una función de un solo valor. Por ejemplo, si empezamos con una variable, hay dos combinaciones; a saber, $a$ y $\neg a$ . Si tenemos dos variables, hay cuatro combinaciones. Esto se debe a que podemos tener, para $a$ o bien $a$ ou $\neg a$ . Entonces, para $b$ podemos tener $b$ ou $\neg b$ . Así que hay cuatro combinaciones entre estas dos variables. Del mismo modo, para tres variables, hay $2 \times 2 \times 2=2^3$ combinaciones entre estas variables.

Ahora, para considerar el conjunto de TODOS funciones booleanas, tenemos que considerar de nuevo cada una de estas combinaciones. Podemos decir que existen $2^\text{combinations}$ diferentes combinaciones entre variables booleanas. Esto se debe a que, para cada combinación, puede ser verdadero o falso. Así, en el párrafo anterior, hemos afirmado que existen $2^n$ combinaciones entre las variables. Cada una de estas combinaciones puede ser verdadera o falsa para una determinada asignación de variables. Así que, de nuevo, obtenemos $2^\text{combinations} = 2^{(2^n)}$ combinaciones entre todas ellas.

Answer 2

Hagamos ingeniería inversa: En el caso de $n=2$ hay $2^{(2^n)}=2^4=16$ funciones distintas: $F0...F15$ . A continuación se muestra la tabla verdadero-falso resultante. Cada columna representa el resultado de la función $F0...F15$

$F0(0,0) = 0$

$F0(0,1) = 0$ ....

$F15(1,1)=1$

---

A   B|  F0  F1  F2  F3  F4  F5  F6  F7
0   0|  0   0   0   0   0   0   0   0
0   1|  0   0   0   0   1   1   1   1
1   0|  0   0   1   1   0   0   1   1
1   1|  0   1   0   1   0   1   0   1

A   B|  F8  F9  F10 F11 F12 F13 F14 F15
0   0|  1   1   1   1   1   1   1   1
0   1|  0   0   0   0   1   1   1   1
1   0|  0   0   1   1   0   0   1   1
1   1|  0   1   0   1   0   1   0   1

---

Para comprobar por qué hay 16 funciones distintas, empezamos con nuestra primera función $F0$ que asigna cualquier par $(A,B)$ a $FALSE$ . Para la siguiente función $F1$ basta con diferir en una sola posición para ser distinto de $F0$ $=>F1(A=1,B=1)=1$ . Lo mismo ocurre con $F2$ con respecto a $F1$ etc. Finalmente llegamos a $F15$ que se distingue de $F14$ simplemente asignando todas las entradas a TRUE.

Hagamos también cuentas:

¿De cuántas formas distintas se pueden elegir k elementos de un conjunto de n elementos con repetición ( $k=2$ $n=2$ ) ? $n^k$ = $2^2=4$ . Hay 4 maneras de formar una pareja $(A,B)$ de ahí $F(A,B)$ también produce 4 resultados $k1,k2,k3,k4$ . ¿De cuántas formas distintas se pueden elegir k elementos de un conjunto de n elementos con repetición ( $k=4$ $n=2$ ) ? $n^k$ = $2^4=(2^{(2^2)})=16$ . Por tanto, 16 funciones booleanas semánticamente diferentes.

---

Véanse a continuación los nombres de las funciones y los símbolos correspondientes. (Fuente: http://mathworld.wolfram.com/BooleanFunction.html )

function            symbol          name
F0                  0               FALSE
F1                  A ^ B           AND
F2                  A ^ !B          A AND NOT B
F3                  A               A
F4                  !A ^ B          NOT A AND B
F5                  B               B
F6                  A xor B         XOR
F7                  A v B           OR
F8                  A nor B         NOR
F9                  A XNOR B        XNOR
F10                 !B              NOT B
F11                 A v !B          A OR NOT B
F12                 !A              NOT A
F13                 !A v B          NOT A OR B
F14                 A nand B        NAND
F15                 1               TRUE

Answer 3

Piensa en la tabla de verdad, digamos para un concreto $n$ como $n=3$ . Existen $2^3$ secuencias de longitud $3$ compuesto por $0$ y/o $1$ 's. En términos más generales, existen $2^n$ secuencias de $0$ y/o $1$ de longitud $n$ .

Para hacer una función booleana, para cada de estas secuencias, podemos elegir independientemente el valor de nuestra función en la secuencia.

Así, hay $2^{(2^n)}$ Funciones booleanas de $n$ variables.

Answer 4

Aquí permítanme añadir mi parte. Consideremos que tenemos dos variables lógicas a y b . Estas dos variables pueden ser 0 ó 1. Por lo tanto, las posibilidades totales son

    a  |  b
    -------
    0  |  0    =  a'b'
    0  |  1    =  a'b
    1  |  0    =  a b'
    1  |  1    =  a b
    -------

___2__ X __2__ = 4 possibilities
0 or 1   0 or 1

Ahora es el momento de encontrar el número total de funciones para 2 variables! ... Hemos encontrado 4 términos para 2 variables en el ejemplo anterior, ¿no? Entonces para Una Ecuación o Función puede contener cualquier número de los 4 términos que hemos encontrado anteriormente. Por ejemplo

    a'b' + a'b             - contain two terms
    a b'                   - contain single term
    a'b' + a'b + a b       - contain three terms
    a'b' + a'b + ab' + a b - contain four terms (maximum possibilities)

Así que la combinación total (recuento) de funciones para 2 variables son

_______2_______ X _______2_______ X _______2_______ X _______2_______ = 16 possibilities
term or no term   term or no term   term or no term   term or no term

       -                -                  -                 -        = 0(false)

       ab               -                  -                 -        = ab

       -               a'b                 -                 -        = a'b

       -                -                  ab'               -        = ab'

       -                -                  -                 a'b'     = a'b'

       ab              a'b                 -                 -        = ab + a'b

       -               a'b                ab'                -        = a'b + ab'

       -                -                 ab'               a'b'      = ab' + a'b'

       ab               -                 ab'                -        = ab + ab'

       ab               -                  -                a'b'      = ab + a'b'

    ..... //some more possible combinations like this, ( to lazy to type it;) )
    and finally it would be like 

       ab              a'b                ab'             a'b'        =  1 (True)

Entonces La combinación(cuenta) de funciones que pueden ser formadas por n variables es 2^2n

n = 2

2 ^ 2*2 = 16

Answer 5

No sé si es semánticamente correcto, pero es bastante fácil calcular el caso aún más general: ¿cuántas funciones de $k$ argumentos, cada uno puede tomar n valores y la función puede producir uno de m resultados para cada combinación. Como este blog dice , sus argumentos proporcionan $n^k$ combinaciones de valores. Usted puede interpretar su función como una función de argumento único, que toma uno de $n^k$ valores. Ahora, se empieza por colocar todas las funciones posibles en un grupo

[all possible functions]

y aplicar el primer valor de $n^k$ . Las funciones del grupo responderán con $m$ diversos resultados. De este modo, habrá resuelto un grupo en $m$ subgrupos.

[responded with 1][responded with 2] ... [responded with m]

En el siguiente paso, se aplica el siguiente valor de $n^k$ a cada subgrupo. De nuevo, las funciones en esos subgrupos se dividirán en $m$ otros subgrupos. Después de dos pasos, habrá resuelto todas sus funciones en $m^2$ subgrupos. Tras aplicar todos $n^k$ valores de entrada, ha resuelto el grupo inicial en $m^{n^k}$ subgrupos. No tiene más pruebas que aplicar. Por lo tanto, consideras que todas las funciones de los subgrupos resultantes son idénticas. Tiene $m^{n^k}$ diferentes funciones. ¿No es precioso?

En caso de que los argumentos de la función y los valores pertenezcan al mismo tipo (el tipo es un rango de valores que puede tomar la variable), se tiene $m=n$ y $n^{n^k}$ diferentes funciones. En particular, en caso de que el tipo sea binario, podemos tener $2^{2^k}$ funciones. Estoy seguro de que todas las funciones son realizables (existe la noción de integridad funcional ) y, por lo tanto, son semánticamente correctos si eso es lo que quieres decir.