¿Cómo implementa la siguiente función usando nada más que 2: 1 MUX?

Creo que no es demasiado complejo, suponiendo que haya resuelto la ecuación que quería correctamente (supongo que lo hizo bien allí). Comience mirando la ecuación para un MUX de 2 pulgadas:

$$\begin{align*} M_2(A,B,S) &= A\cdot \bar{S} + B\cdot S \end{align*}$$

A partir de esto, puede obtener algunos resultados útiles:

$$\begin{align*} M_2(0,x,y) &= x\cdot y \\ M_2(x,0,y) &= x\cdot\bar{y} \\ M_2(x,y,0) &= x \\ M_2(1,x,y) &= x + \bar{y} \\ M_2(x,1,y) &= x + y \\ M_2(x,y,1) &= y \\ M_2(x,y,x) &= x\cdot y \\ M_2(x,y,y) &= x + y \\ M_2(0,0,x) &= 0 \\ M_2(0,1,x) &= x \\ M_2(1,0,x) &= \bar{x} \\ M_2(1,1,x) &= 1 \end{align*}$$

Entonces se sigue que:

$$\begin{align*} F &= A B + B C + C D \\ x &= A B = M_2(A,B,A) \\ y &= B C = M_2(B,C,B) \\ z &= C D = M_2(C,D,C) \\ \therefore F &= x + y + z \\ F &= M_2(M_2(x,y,y),z,z) \end{align*}$$

En resumen, necesitará (5) muxes de 2 pulgadas:

^{simular este circuito : esquema creado con CircuitLab}

También hay una buena simetría allí. ¿Notarlo?

AGREGADO: Usted preguntó si solo puede usar 0, 1 o D como fuente de entrada de datos mux. Supongo que con esto quiere decir que todo A, B, C y D se pueden usar como selectores mux. (De lo contrario, no creo que se pueda lograr el resultado). Entonces, esto solo significa que necesita usar algunos de los otros resultados útiles que mencioné anteriormente. La idea más simple sería simplemente agregar tres muxes más de 2 pulgadas:

^{simular este circuito}

No estoy seguro de si hay una manera de optimizarlo aún más. No he examinado todas las posibilidades.

EDITAR DE NUEVO: ¡Sí! Usando la solución recién agregada de OP, los dos siguientes simplemente fluyen. El izquierdo responde su primera parte de la pregunta, el derecho responde su segunda parte.

^{simular este circuito}

EDITAR DE NUEVO OTRA VEZ: El pedido no es complicado. Es solo asignar las letras a donde pertenecen. El autor tomó (A) como el bit de orden superior de un valor binario de tres bits, por lo que representa$0\cdot 2^2=0$o$1\cdot 2^2=4$; tomó (B) como el bit medio de un valor binario de tres bits, por lo que representa$0\cdot 2^1=0$o$1\cdot 2^1=2$; y tomó (C) como el bit de orden inferior de un valor binario de tres bits, por lo que representa$0\cdot 2^0=0$o$1\cdot 2^0=1$. Una variedad de perspectivas diferentes funcionaría igualmente bien. Pero ese es el que parecen haber elegido.

Así que ahora comenzaron con el primer nivel (izquierdo), colocaron (4) muxes controlados por (A) y se mantuvieron mentalmente convenientes numerando esos muxes como ABC="x00", ABC="x01", ABC="x10" , y para el inferior ABC="x11".

Ahora, dado que para el de arriba, ABC="x00", esto significa que acepta "000"=0 o "100"=4. Entonces, para la entrada "0" de ese mux (mux1), buscaron en la tabla ABC="000"=0 y colocaron la entrada de la tabla en su entrada lateral "0". Para la entrada "1" de ese mux, buscaron en la tabla ABC="100"=4 y colocaron esa entrada de la tabla en su entrada lateral "1". (Esa tabla se ve mal aquí, ya que debería ser un 0 en ese cuadro, confirmado al mirar las columnas expandidas anteriores).

El siguiente mux descendente (mux2) es para ABC="x10" y, por lo tanto, se usa ABC="010"=2 y ABC="110"=6; el siguiente mux hacia abajo (mux3) es para ABC="x01" y, por lo tanto, se usa ABC="001"=1 y ABC="101"=5; y finalmente el último mux down (mux4) es para ABC="x11" y por lo tanto se usa ABC="011"=3 y ABC="111"=7.

Tanto mux1 (ABC="x00") como mux2 (ABC="x10") se alimentan conjuntamente a mux5. Puedes ver aquí que B es la variación entre estos, 0 o 1, así es como los conectaron aquí. La salida de mux5 será ABC="xy0", donde los primeros dos bits ya han sido decodificados y todo lo que queda es decodificar la situación C=0. Entonces, la salida de mux5 va a la entrada "0" de mux7. De manera similar, mux3 (ABC="x01") y mux4 (ABC="x11") se alimentan conjuntamente a mux6. B nuevamente es la variación entre la que mux6 selecciona. La salida de mux6 siempre está relacionada con el caso C=1, y eso se alimenta a la entrada "1" de mux7.

Todo lo que queda es que mux7 elija entre C=0 y C=1.

Un mux 2:1 contiene un inversor, dos puertas AND y una puerta OR. Con el cableado apropiado, puede usarlo como una puerta AND, una puerta OR, un inversor y algunas otras funciones. De hecho, ciertas familias de FPGA se basan íntegramente en este concepto.

Esto debería ser una pista suficiente para permitirle realizar cualquier función arbitraria utilizando muxes 2:1.

Un multiplexor de dos entradas tiene tres entradas (a, b y select). Considere en qué degenera cuando elige dos de ellos y conecta el otro a "0" o "1". Considere lo que sucede cuando elige dos de ellos y conecta el tercero a cualquiera de ellos. Básicamente, hay un montón de formas de degenerar ese espacio de tres entradas en un espacio de dos entradas.

Sin hacer nada tan sofisticado, solo debe darse cuenta de que un multiplexor le permite establecer explícitamente el valor de salida para las filas de la tabla de verdad que corresponden a las entradas seleccionadas decodificadas. Por lo tanto, con un multiplexor de cuatro entradas (y, por lo tanto, dos bits de selección), puede representar cualquier función booleana de 2 entradas simplemente cableando las entradas de manera adecuada.

Además, debe quedar claro que puede crear un multiplexor 4:1 a partir de tres multiplexores 2:1, un multiplexor 8:1 a partir de siete multiplexores 2:1, y cuarto, creando una topología de árbol y cableando las selecciones de manera adecuada. Simplemente coloque suficientes multiplexores 2:1 para obtener la cantidad de entradas que necesita, luego haga fluir las salidas, en pares, hacia los multiplexores 2:1 aguas abajo hasta llegar a una sola salida, y piense en cómo conectar las entradas seleccionadas.

Puede salirse con la suya con una variable oculta porque solo tiene 16 términos mínimos a pesar de que tiene una tabla de verdad de 32 filas, y están agrupados de tal manera que los subárboles completos son ignorables.