Minimização de circuitos

Predefinição:Formatar referências Predefinição:TOC-direita 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, 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. Considere o circuito usado para representar $(A\wedge \overline{B})\vee (\overline{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\ne B$. Em termos de portas lógicas, a desigualdade simplesmente significa uma porta XOR (OU exclusivo). Portanto, $(A\wedge \overline{B})\vee (\overline{A}\wedge B)⟺A\ne 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

• Árvore de decisão
• Mapa de Karnaugh
• Composição de funções

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
• Predefinição:Citar livro