minimiza

L´gica combinacional dois-n´ o ıveis
Computadores digitais processam dados em formato bin´rio. Esses processamentos podem ser encaraa n → {0, 1}m . Vimos que qualquer mapeamento f : {0, 1}n → dos como mapeamentos do tipo f : {0, 1}
{0, 1} pode ser expresso como soma de produtos canˆnicos (soma de mintermos) ou como produto de o somas canˆnicas (produto de maxtermos). As express˜es do tipo soma e produto podem ser realizao o das em circuito pelas portas OU e E, respectivamente. Ent˜o, em pr´ ıpio, qualquer mapeamento a ınc´ f : {0, 1}n → {0, 1}m pode ser realizado por circuitos que utilizam apenas os inversores e as portas E e OU.
Deste cap´ ıtulo em diante trataremos apenas de fun¸˜es booleanas do tipo f : {0, 1}n → {0, 1}. Essas co fun¸˜es s˜o, por alguns autores, chamadas de fun¸˜es de chaveamento. co a co 1.1

L´gica combinacional e seq¨ encial o u

Circuitos l´gicos s˜o classificados em dois tipos: combinacionais e seq¨enciais. Os circuitos combio a u nacionais s˜o aqueles nos quais as sa´ a ıdas s˜o determinadas em fun¸˜o apenas das entradas atuais. Os a ca circuitos seq¨ enciais s˜o aqueles nos quais as sa´ u a ıdas dependem n˜o apenas das entradas atuais mas a tamb´m de dados pr´vios nos instantes anteriores. Pode-se dizer que circuitos seq¨enciais envolvem e e u realimenta¸˜o, ou seja, eles possuem “mem´ria”. ca o
O n´mero de n´ u ıveis de um circuito ´ definido como o n´mero m´ximo de portas l´gicas que um sinal e u a o de entrada deve atravessar para chegar at´ a sa´ e ıda. No caso de express˜es do tipo soma de produtos, o uma realiza¸˜o direta em circuito consiste de um conjunto de portas E (que s˜o alimentados pelos ca a sinais de entrada, invertidos ou n˜o) no primeiro n´ e, no segundo n´ a ıvel ıvel, uma porta OU (que recebe como entradas as sa´ ıdas das portas E do primeiro n´ ıvel). A sa´ da porta OU no segundo n´ ´ o ıda ıvel e valor da fun¸˜o. Assim, um circuito desses ´ um