Encontrar funciones de verdad expresivamente adecuadas

Question

Me preguntaba si alguien podría ayudarme a contar el número total de funciones de verdad de 3 variables, que pueden generar todas las funciones de verdad posibles..

Tengo 56 pero no estoy seguro de la respuesta.

EDIT: Me gustaría añadir que las funciones tienen 3 variables pero siguen teniendo entradas y salidas binarias. También cada función tiene una tabla de verdad única

Answer 1

Tienes toda la razón: el número exacto es 56, y se puede demostrar rigurosamente de la siguiente manera.

Por Teorema de Post una función booleana no es expresivamente adecuada si es monótona, afín sobre $\frac{\mathbb Z}{2\mathbb Z}$ , autodual, que preserva la verdad o que preserva la falsedad.

En tres variables esto se simplifica considerablemente. En efecto, el hecho de no preservar la verdad o la falsedad se reduce a $f(0,0,0)=1$ y $f(1,1,1)=0$ . Entonces $f$ nunca es monótona.

Ahora dividimos el conjunto restante de funciones en cuatro subconjuntos indexados por $\lbrace 0,1 \rbrace^2$ : para $a,b$ en $\lbrace 0,1 \rbrace$ , poned

$$ G_{a,b}=\lbrace f | f(0,0,0)=1, f(1,1,1)=0, f(0,0,1)=a, f(0,1,0)=b\rbrace $$

Cada $G_{a,b}$ contiene un único mapa afín (explícitamente, $f(x,y,z)=1+ax+by-(a+b)z$ módulo 2). Este mapa afín es siempre autodual, y $G_{a,b}$ contiene exactamente dos mapas autoduales. Por último, cada $G_{a,b}$ contiene dos funciones no adecuadas, y por lo tanto $2^4-2=14$ funciones adecuadas, lo que hace un total de $2^2\times (2^4-2)=56$ .