Lógica combinatoria

Clases de autómatas

En la teoría de autómatas , la lógica combinacional (también conocida como lógica independiente del tiempo ^{[ 1 ]} ) es un tipo de lógica digital implementada mediante circuitos booleanos , donde la salida es una función pura de la entrada actual únicamente. Esto contrasta con la lógica secuencial , en la que la salida depende no solo de la entrada actual, sino también de su historial. En otras palabras, la lógica secuencial posee memoria, mientras que la lógica combinacional no.

La lógica combinacional se utiliza en circuitos informáticos para realizar álgebra booleana sobre señales de entrada y datos almacenados. Los circuitos informáticos prácticos suelen contener una combinación de lógica combinacional y secuencial. Por ejemplo, la parte de una unidad aritmético-lógica (ALU) que realiza cálculos matemáticos se construye utilizando lógica combinacional. Otros circuitos utilizados en computadoras, como semisumadores , sumadores completos , semirestadores , restadores completos , multiplexores , demultiplexores , codificadores y decodificadores, también se construyen utilizando lógica combinacional.

El diseño práctico de sistemas lógicos combinacionales puede requerir considerar el tiempo finito necesario para que los elementos lógicos prácticos reaccionen a los cambios en sus entradas. Cuando una salida es el resultado de la combinación de varias rutas diferentes con distinto número de elementos de conmutación, la salida puede cambiar de estado momentáneamente antes de estabilizarse en el estado final, a medida que los cambios se propagan a lo largo de diferentes rutas. ^{[ 2 ]}

La lógica combinacional se utiliza para construir circuitos que producen salidas específicas a partir de ciertas entradas. La construcción de la lógica combinacional generalmente se realiza mediante uno de dos métodos: una suma de productos o un producto de sumas. Considere la siguiente tabla de verdad , que representa un elemento de lógica combinacional de 3 entradas que toma las entradas A, B y C, y cuya salida es verdadera solo cuando la entrada A es verdadera y las entradas B y C son ambas verdaderas o ambas falsas.

Utilizando la suma de productos, se suman todas las proposiciones lógicas que producen resultados verdaderos, obteniendo el siguiente resultado:

${\displaystyle (A\wedge \neg B\wedge \neg C)\vee (A\wedge B\wedge C)\,}$

Utilizando álgebra booleana , el resultado se simplifica al siguiente equivalente de la tabla de verdad:

${\displaystyle A\wedge ((\neg B\wedge \neg C)\vee (B\wedge C))\,}$

La minimización (simplificación) de fórmulas de lógica combinacional se realiza utilizando las siguientes reglas basadas en las leyes del álgebra booleana :

${\displaystyle {\begin{aligned}(A\vee B)\wedge (A\vee C)&=A\vee (B\wedge C)\\(A\wedge B)\vee (A\wedge C)&=A\wedge (B\vee C)\end{aligned}}}$

${\displaystyle {\begin{aligned}A\vee (A\wedge B)&=A\\A\wedge (A\vee B)&=A\end{aligned}}}$

${\displaystyle {\begin{aligned}A\vee (\lnot A\wedge B)&=A\vee B\\A\wedge (\lnot A\vee B)&=A\wedge B\end{aligned}}}$

${\displaystyle {\begin{aligned}(A\vee B)\wedge (\lnot A\vee B)&=B\\(A\wedge B)\vee (\lnot A\wedge B)&=B\end{aligned}}}$

${\displaystyle {\begin{aligned}(A\wedge B)\vee (\lnot A\wedge C)\vee (B\wedge C)&=(A\wedge B)\vee (\lnot A\wedge C)\\(A\vee B)\wedge (\lnot A\vee C)\wedge (B\vee C)&=(A\vee B)\wedge (\lnot A\vee C)\end{aligned}}}$

Mediante el uso de la minimización (a veces llamada optimización lógica ), se puede llegar a una función o circuito lógico simplificado, y el circuito combinacional lógico se vuelve más pequeño y más fácil de analizar, usar o construir.

• circuito asíncrono
• matriz de puertas programables en campo
• Verificación formal
• lógica de escalera
• Controlador lógico programable
• lógica de relés
• Lógica secuencial
• Transformación de Tseytin

• Predko, Michael; Predko, Myke (2004). La electrónica digital desmitificada . McGraw-Hill. ISBN 0-07-144141-7.

• Belton, D.; Bigwood, R. "Guía tutorial de lógica y sistemas combinacionales" . Archivado del original el 22 de octubre de 2013.