cálculo del número de funciones booleanas

Question

Me gustaría aclarar si estoy en el camino correcto o no. Tengo estas preguntas:

Consideremos las funciones booleanas $f(x,y,z)$ en tres variables tal que la tabla de valores de $f$ contiene exactamente cuatro $1$ 's.

1. Calcula el número total de estas funciones.
2. Aplicamos el método del mapa de Karnaugh a dicha función $f$ . Supongamos que el mapa no contiene ningún bloque de cuatro $1$ 's, y los cuatro $1$ 's están cubiertos por tres bloques de dos $1$ 's. Además, encontramos que no es posible no es posible cubrir todos los $1$ por menos de tres bloques. Calcula el número de funciones con esta propiedad.

1a: He respondido $70 = \binom{8}{4}$ .

1b: He elaborado manualmente los mapas de Karnaugh y he obtenido la respuesta $12$ pero mi amigo tiene $24$ . ¿Hay otra forma de hacerlo?

Gracias

Answer 1

Un "bloque de dos" en un mapa de Karnaugh corresponde a una función booleana de la forma $xy$ (se permiten complementos de variables). Por tanto, buscamos funciones booleanas de peso $4$ ( $4$ UNOS en la tabla de verdad o en el mapa de Karnaugh) que pueden ser cubiertos por $3$ "bloques de dos" pero no por $2$ "bloques de dos", es decir, la expresión de la suma mínima de productos tiene tres términos, y no dos. La forma más sencilla es la siguiente $$xy \vee xz \vee yz$$ que es la forma de T a la que se hace referencia (véase también mi comentario sobre la pregunta principal), y complementando las variables nos da $2^3 = 8$ diferentes formas de T, algunas de las cuales están "envueltas" en los bordes (lo que es perfectamente aceptable). ¿Hay otras? Pues intentemos contarlas. El principio de inclusión-exclusión nos dice que

el peso total de $4$ es igual a la suma de los pesos de los tres "bloques de dos" menos el suma de los pesos de las intersecciones intersecciones de "bloques de dos" más el peso de la intersección de todas las tres "bloques de dos".

Pues bien, dos "bloques de dos" diferentes deben intersecarse en una posición porque si se cruzan en ambas posiciones, son idénticos, y si no se no se cruzan en absoluto, cubren todas $4$ UNO en la función. Por lo tanto, los tres "bloques de dos" también deben intersecarse en la misma posición dando $$4 = (2+2+2) - (1 + 1 + 1) + 1$$ como el peso total, y también mostrando que la forma de T es la única posible.

Answer 2

Podemos clasificar todos los $\binom 8 4$ funciones de tres variables con $4$ minterms según el "número de bloques" que se obtiene en un mapa de Karnaugh. En primer lugar, hay que tener en cuenta que el método del mapa K produce una expresión prima e irreducible: cada término (o bloque) es un implicante primo, y cada término cubre un minitérmino no cubierto por ningún otro término de la expresión.

Clasificamos las cubiertas primarias e irredundantes según el número de implicados primos. Luego argumentaremos que la correspondencia entre cubiertas y funciones es uno a uno.

• Cubiertas primarias e irredundantes con cuatro implicantes. Hay dos, la paridad y la imparidad. No puede haber dos términos de minteria adyacentes en el mapa, y sólo hay dos formas de conseguirlo.
• Cubiertas primarias e irreducibles con tres implicados primos. Hay ocho del tipo mostrado por @DilipSarwate, a saber $(x \wedge y) \vee (x \wedge z) \vee (y \wedge z)$ . Hay 24 más de la forma $(x \wedge y \wedge z) \vee (\neg x \wedge \neg y) \vee (\neg x \wedge \neg z)$ .
• Cubiertas primarias e irreducibles con dos implicados primos. Las dividimos según el número de variables que aparecen en la cubierta.
  • Dos variables: son las funciones de paridad par e impar de dos variables, de las cuales hay seis en total.
  • Tres variables: Estas cubiertas deben ser de la forma $(v \wedge b) \vee (\neg v \wedge c)$ , donde $v$ es una variable y $b$ , $c$ son literales (no de $v$ ). La variable $v$ puede elegirse de tres maneras; para cada elección de $v$ Hay cuatro opciones de $b$ y luego dos opciones para $c$ para un total de 24 tapas.
• Cubiertas primarias e irreducibles con un implicado primo. El implicante es un literal; por lo tanto, hay seis opciones en este caso.

En resumen: $2 + (8+24) + (6+24) + 6 = 70 = \binom 8 4$ como se esperaba. El número de portadas que se componen de tres "bloques de dos" es de 8, según lo identificado por @DilipSarwate.

Ahora argumentamos que cada una de las 70 funciones tiene exactamente una cobertura prima e irreducible. Esto no es necesario si estamos convencidos de haber contado todas las coberturas anteriores, pero tampoco está de más. Recordemos que el consenso de $a \wedge b$ y $\neg a \wedge c$ es $b \wedge c$ . Recordemos, además, que un término de una cubierta primaria es esencial (es decir, debe formar parte de cualquier cubierta primaria) si no está cubierto por la disyunción de sus conjunciones y términos consensuados con los otros implicantes primos de la cubierta.

Por último, si una cubierta de primos está formada por todos los primos esenciales, es la única cubierta de primos e irreducibles. Todos estos son resultados clásicos. Dado que todas las coberturas enumeradas anteriormente están formadas por primos esenciales, todas son únicas.

Answer 3

Formas L: --. o --' o '-- o .-- cuentan: 8

Formas T: -'- o -.- cuentan: 4

Formas Z: -.. o ..- cuentan: 4

Cada una de estas formas tiene 3 cruces en el mapa, así que puedes desplazar cada una de ellas en uno para obtener otra función booleana.

total: 16

Si tratas los bordes laterales como envolventes obtienes 32