Minimização de circuitos

Na álgebra booleana, minimização de circuitos é o problema de se obter o menor circuito lógico, que representa uma função booleana ou uma tabela verdade dada. Acredita-se que o problema de minimização de circuitos é intratável,^[1] mas existem heurísticas efetivas como o Mapa de Karnaugh e o algoritmo Quine-McCluskey que facilitam o processo.

Objetivo

O problema de ter um circuito eletrônico complicado (isto é, um com muitos elementos, como as portas lógicas) é que cada elemento ocupa um determinado espaço físico em sua implementação, o que custa tempo e dinheiro para produzi-lo. A minimização de circuitos pode ser uma forma de otimização lógica, usada para reduzir o tamanho da complexidade lógica dos circuitos integrados.

Exemplo

Existem muitas formas de minimizar um circuito, este é um exemplo que minimiza (ou simplifica) uma função booleana. Note que a função booleana realizada pelo circuito está diretamente relacionada com a expressão algébrica da qual a função é implementada.^[2] Considere o circuito usado para representar $(A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)$ . É evidente que duas negações, duas conjunções, e uma dinjunção são utilizadas nessa proposição. Isto significa que para construir o circuito, precisaria-se de duas portas NOT, duas portas AND, e uma porta OR.

Nós podemos simplificar (minimizar) o circuito, aplicando identificadores lógicos ou utilizando a intuição. Uma vez que o exemplo mostra que A é verdadeiro quando B é falso, ou o contrário, podemos concluir que isto simplesmente significa $A\neq B$ . Em termos de portas lógicas, a desigualdade simplesmente significa uma porta XOR (OU exclusivo). Portanto, $(A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)\iff A\neq B$ . Então os dois circuitos mostrados abaixo são equivalentes:

Você pode observar também a veracidade do resultado usando uma tabela verdade.

Ver também

Referências

↑ Kabanets, Valentine; Cai, Jin-Yi (2000), «Circuit minimization problem», Proc. 32nd Symposium on Theory of Computing, Portland, Oregon, USA, pp. 73–79, doi:10.1145/335305.335314, Predefinição:ECCC .
↑ M. Mano, C. Kime. "Logic and Computer Design Fundamentals" (Fourth Edition). Pg 54

Leitura adicional

De Micheli, Giovanni. Synthesis and Optimization of Digital Circuits. McGraw-Hill, 1994, Part III, Logic-Level Syntesis and Optimization
Zvi Kohavi, Niraj K. Jha. Switching and Finite Automata Theory. 3rd ed. Cambridge University Press. 2009. ISBN 978-0-521-85748-2, chapters 4–6
Knuth, Donald E. (2010). «chapter 7.1.2: Boolean Evaluation». The Art of Computer Programming. 4A. [S.l.]: Addison-Wesley. pp. 96–133. ISBN 0-201-03804-8

[1] Kabanets, Valentine; Cai, Jin-Yi (2000), «Circuit minimization problem», Proc. 32nd Symposium on Theory of Computing, Portland, Oregon, USA, pp. 73–79, doi:10.1145/335305.335314, Predefinição:ECCC .

[2] M. Mano, C. Kime. "Logic and Computer Design Fundamentals" (Fourth Edition). Pg 54

[1]

[2]