Prévia do material em texto
ÁLGEBRA BOOLEANA E SIMPLIFICAÇÃO LÓGICA ÁLGEBRA BOOLEANA E SIMPLIFICAÇÃO LÓGICA 44 TÓPICOS DO CAPÍTULO 4-1 Operações e Expressões Booleanas 4-2 Leis e Regras da Álgebra Booleana 4-3 Teoremas de DeMorgan 4-4 Análise Booleana de Circuitos Lógicos 4-5 Simplificação Usando a Álgebra Booleana 4-6 Formas Padronizadas de Expressões Booleanas 4-7 Expressões Booleanas e Tabelas-verdade 4-8 O Mapa de Karnaugh 4-9 Minimização de Soma-de-Produtos Usando o Mapa de Karnaugh 4-10 Minimização de Produto-de-Somas Usando o Mapa de Karnaugh 4-11 Mapas de Karnaugh de Cinco Variáveis 4-12 VHDL (Opcional) ■ ■ ■ Aplicações em Sistemas Digitais 199 TERMOS IMPORTANTES Termos importantes na ordem em que aparecem no capítulo. ■ Variável ■ Complemento ■ Termo-soma ■ Termo-produto ■ soma-de-produtos ■ Produto-de-somas ■ Mapa de Karnaugh ■ Minimização ■ “Don’t care” ■ VHDL INTRODUÇÃO Em 1854, Georg Boole publicou um trabalho intitulado “Uma Investigação das leis do Pensamento, sobre as quais são fundadas as teorias Matemáticas de Lógica e Probabilida- des” (Investigation of the Laws of Thought, on Which Are Foun- ded the Mathematical Theories of Logic AND Probabilities). Foi nessa publicação que uma “álgebra lógica”, conhecida hoje em dia como álgebra Booleana, foi formulada. A álgebra Booleana é uma forma conveniente e sistemática de expres- sar e analisar a operação de circuitos lógicos. Claude Shan- non foi o primeiro a aplicar o trabalho de Boole na análise e projeto de circuitos lógicos. Em 1938, Shannon escreveu uma tese no MIT intitulada A Symbolic Analysis of Relay and Switching Circuits. Este capítulo aborda as leis, regras e teoremas da álgebra Booleana e suas aplicações em circuitos digitais. Estudare- mos como definir um dado circuito com uma expressão Booleana e então avaliar a sua operação. Estudaremos tam- bém como simplificar circuitos lógicos usando os métodos da álgebra Booleana e mapas de Karnaugh. A linguagem de descrição de hardware VHDL para a pro- gramação de dispositivos lógicos é introduzida. ■ ■ ■ DISCUSSÃO PRÉVIA DE APLICAÇÕES EM SISTEMAS DIGITAIS O tópico Aplicações em Sistemas Digitais ilustra conceitos ensinados neste capítulo. O circuito lógico de um display de 7 segmentos usado no sistema de contagem e controle de comprimidos a partir do Capítulo 1 é uma boa maneira de ilustrar a aplicação da álgebra Booleana e do mapa de Kar- naugh para obter a implementação mais simples possível no projeto de circuitos lógicos. Portanto, nessa aplicação em sistemas digitais, o foco é no decodificador de BCD para 7 segmentos que aciona os dois sistemas de displays mostra- dos na Figura 1–58. ACESSE O SITE Recursos que o ajudarão no estudo deste capítulo estão disponíveis em http://www.prenhall.com/floyd OBJETIVOS DO CAPÍTULO ■ Aplicar as leis e regras básicas da álgebra Booleana ■ Aplicar os teoremas de DeMorgan em expressões Booleanas ■ Descrever circuitos de portas lógicas com expressões Booleanas ■ Calcular expressões Booleanas ■ Simplificar expressões usando as leis e regras da álgebra Booleana ■ Converter qualquer expressão Booleana numa soma-de-produtos ■ Converter qualquer expressão Booleana num produto-de-somas ■ Usar um mapa de Karnaugh para simplificar expressões Booleanas ■ Usar um mapa de Karnaugh para simplificar funções de tabela- verdade ■ Utilizar condições “don’t care” para simplificar funções lógicas ■ Escrever um programa VHDL para uma lógica simples ■ Aplicar a álgebra Booleana, o método do mapa de Karnaugh e VHDL numa aplicação de sistema 200 ■ SISTEMAS DIGITAIS Os termos variável, complemento e literal são usados em álgebra Booleana. Uma variável é um símbolo (geralmente uma letra maiúscula em itálico) usado para representar uma grandeza lógi- ca. Qualquer variável simples pode ter um valor 1 ou 0. O complemento é o inverso de uma va- riável e é indicado por uma barra sobre a variável. Por exemplo, o complemento da variável A é A–. O complemento de uma variável A é lido como “A negado” ou “A barrado”. Algumas vezes é usado um outro símbolo, em vez de uma barra, para in- dicar o complemento de uma variável; por exemplo, B’ indica o complemento de B. Neste livro, é usado apenas a barra sobre a variável. Uma literal é a variável ou o complemento de uma variável. Adição Booleana Lembre-se, do Capítulo 3, de que a adição Booleana é equivalente à operação OR e as regras bá- sicas são ilustradas com suas relações com a porta OR da seguinte forma: Na álgebra Booleana, um termo-soma é uma soma de literais. Em circuitos lógicos, um ter- mo-soma é produzido por uma operação OR sem o envolvimento de operações AND. Alguns exemplos de termos-soma são Um termo-soma será igual a 1 quando uma ou mais das literais no termo for 1. Um termo-so- ma será igual a 0 somente se cada uma das literais for 0. A + B, A + B, A + B + C e A + B + C + D. Se A = 1, então A = 0. Se A = 0, então A = 1. 4-1 OPERAÇÕES E EXPRESSÕES BOOLEANAS A álgebra Booleana é a matemática dos sistemas digitais. Um conhecimento básico da álgebra Booleana é indispensável para o estudo e análise de circuitos lógicos. No capítulo anterior, as operações Booleanas em termos de suas relações com as portas NOT, AND, OR, NAND e NOR foram introduzidas. Ao final do estudo desta seção você deverá ser capaz de: ■ Definir variável ■ Definir literal ■ Identificar um termo-soma ■ Calcular um termo-so- ma ■ Identificar um termo-produto ■ Calcular um termo-produto ■ Explicar a adição Booleana ■ Explicar a multiplicação Booleana NOTA: COMPUTAÇÃO Em um microprocessador, a uni- dade lógica e aritmética (ALU – arithmetic logic unit) realiza ope- rações lógicas Booleanas e arit- méticas sobre dados digitais con- forme determinado pelas instru- ções do programa. As operações lógicas são equivalentes às ope- rações das portas básicas as quais estamos familiarizados, po- rém realizadas com um mínimo de 8 bits de cada vez. AND, OR, NOT e EX-OR são exemplos de instruções lógicas Booleanas, as quais são denominadas de mne- mônicos. Um programa em lin- guagem assembly usa mnemôni- cos para especificar uma opera- ção. Um outro programa deno- minado de assembler traduz os mnemônicos num código binário que pode ser entendido pelo mi- croprocessador. 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 1 A porta OR é um somador Booleano. EXEMPLO 4–1 Determine os valores de A, B, C e D que tornam o termo-soma igual a 0. Solução Para o termo-soma ser 0, cada uma das literais tem que ser 0. Portanto, A = 0 e B = 1, de forma que, C = 0 e D = 1, de forma que Problema relacionado* Determine os valores de A– e B que tornam o termo-soma igual a 0. * As respostas estão no final do capítulo. A + B + C + D = 0 + 1 + 0 + 1 = 0 + 0 + 0 + 0 = 0 D = 0.B = 0, A + B + C + D CAPÍTULO 4 • ÁLGEBRA BOOLEANA E SIMPLIFICAÇÃO LÓGICA ■ 201 Multiplicação Booleana Lembre-se, também do Capítulo 3, de que a multiplicação Booleana é equivalente à operação AND e as regras básicas são ilustradas com as relações com a porta AND a seguir: Na álgebra Booleana, um termo-produto é o produto de literais. Em circuitos lógicos, um termo-produto é produzido por uma operação AND sem o envolvimento de operações OR. Alguns exemplos de termos-produto são Um termo-produto é igual a 1 apenas se cada uma das literais no termo for 1. Um termo-pro- duto é igual a 0 quando uma ou mais das literais for 0. AB, AB, ABC e ABCD. A porta AND é um multipli- cador Booleano. 0 • 0 = 0 0 • 1 = 0 1 • 0 = 0 1 • 1 = 1 EXEMPLO 4–2 Determine os valores e A, B, C e D que torna o termo-produto igual a 1. Solução Para o termo-produto ser 1, cada uma das literais no termo tem que ser 1. Portanto, A = 1, B = 0 de forma que C = 1 e D = 0 de forma que Problema relacionadoDetermine os valores de A e B que tornam o termo-produto igual a 1.A B ABCD = 1 �0 �1 �0 = 1 �1 �1 �1 = 1 D = 1.B = 1, ABCD 1. Se A = 0, qual é o valor de ? 2. Determine o valor de A, B e C que tornam o termo-soma igual a 0. 3. Determine o valor de A, B e C que tornam o termo-produto igual a 1.ABC A + B + C ASEÇÃO 4–1 REVISÃO As respostas estão no final do capítulo. 4-2 LEIS E REGRAS DA ÁLGEBRA BOOLEANA Assim como em outras áreas da matemática, existem certas regras bem-desenvolvidas e leis que têm que ser seguidas para aplicar adequadamente a álgebra Booleana. As mais importantes são apresentadas nesta seção. Ao final do estudo desta seção você deverá ser capaz de: ■ Aplicar as leis comutativas da adição e multiplicação ■ Aplicar as leis associativas da adi- ção e multiplicação ■ Aplicar a lei distributiva ■ Aplicar as doze regras básicas da álgebra Booleana Leis da Álgebra Booleana As leis básicas da álgebra Booleana – as leis comutativas para a adição e multiplicação, as leis associativas para a adição e multiplicação e a lei distributiva – são as mesmas que para a álgebra 202 ■ SISTEMAS DIGITAIS comum. Cada uma das leis está ilustrada com duas ou três variáveis, porém o número de variáveis não é limitado para essas leis. Lei Comutativa A lei comutativa da adição para duas variáveis é escrita da seguinte forma: A + B = B + A Essa lei diz que a ordem das variáveis na qual a função OR é aplicada não faz diferença. Lem- bre-se que, na álgebra Booleana aplicada a circuitos lógicos, a adição e a operação OR são as mes- mas. A Figura 4–1 ilustra a lei comutativa aplicada a uma porta OR e mostra que não importa em qual entrada cada variável é aplicada. (O símbolo ≡ significa “equivalente a”). A lei comutativa da multiplicação para duas variáveis é a seguinte: AB = BA Essa lei diz que a ordem das variáveis na qual a operação AND é aplicada não faz diferença. A Figura 4–2 ilustra essa lei aplicada a uma porta AND. Lei Associativa A lei associativa da adição escrita para três variáveis é mostrada a seguir: A + (B + C) = (A + B) + C Essa lei diz que quando é aplicada uma operação OR em mais de duas variáveis, o resultado é o mesmo independente da forma de agrupar as variáveis. A Figura 4–3 ilustra essa lei aplicada em portas OR de 2 entradas. A lei associativa da multiplicação escrita para três variáveis é mostrada a seguir: A(BC) = (AB)C Essa lei diz que a ordem em que as variáveis são agrupadas não faz diferença quando é apli- cada uma operação AND em mais de duas variáveis. A Figura 4–4 ilustra essa lei aplicada a por- tas AND de 2 entradas. Lei Distributiva A lei distributiva escrita para três variáveis é mostrada a seguir: A(B + C) = AB + AC Equação 4–1 Equação 4–2 Equação 4–3 Equação 4–4 Equação 4–5 A B B + A B A + B A ᭤ FIGURA 4–1 Aplicação da lei comutativa da adição. A B BA B AB A ᭤ FIGURA 4–2 Aplicação da lei comutativa da multiplicação. B + C B C A + (B + C) A A + B B C (A + B) + C A BC B C A(BC) A AB B C (AB)C A ᭤ FIGURA 4–3 Aplicação da lei associativa da adição. Abra o arquivo F04-03 para verificar. ᭤ FIGURA 4–4 Aplicação da lei associativa da multiplicação. Abra o arquivo E04-04 para verificar. CAPÍTULO 4 • ÁLGEBRA BOOLEANA E SIMPLIFICAÇÃO LÓGICA ■ 203 Essa lei diz que a operação AND de uma única variável com o resultado de uma operação OR aplicada em duas ou mais variáveis é equivalente a uma operação OR entre os resultados das ope- rações AND entre uma única variável e cada uma das duas ou mais variáveis. A lei distributiva também expressa o processo de fatoração no qual a variável comum A é fatorada em termos-pro- duto, por exemplo, AB + AC = A(B + C). A Figura 4–5 ilustra a lei distributiva em termos de im- plementação com portas. Regras da Álgebra Booleana A Tabela 4–1 apresenta uma lista de 12 regras básicas úteis na manipulação e simplificação de ex- pressões Booleanas. As regras de 1 a 9 serão analisadas em termos de suas aplicações em portas lógicas. As regras de 10 a 12 serão obtidas em termos de regras mais simples e das leis discutidas anteriormente. Regra 1. A + 0 = A A operação OR de uma variável com 0 é sempre igual a variável. Se a va- riável de entrada A for 1, a variável X de saída será 1, que é igual a A. Se A for 0, a saída será 0, que também é igual a A. Essa regra é ilustrada na Figura 4–6, na qual a entrada inferior da porta está fixa em 0. Regra 2. A + 1 = 1 A operação OR da variável com 1 é igual a 1. Um 1 numa entrada de uma porta OR produz um 1 na saída, independente do valor da variável na outra entrada. Essa regra é ilustrada na Figura 4–7, na qual a entrada inferior da porta está fixa em 1. B + C C A X B X = A(B + C) AB B X A C A AC X = AB + AC ᭣ FIGURA 4–5 Aplicação da lei distributiva. Abra o arquivo F04-05 para verificar. �� � � � �� � � � �� � ���� � �� � ���� � �� � � � �� � �� �� � � � � �� � � � �� ��� � �� � ��� � � � � ��� �� ���� �� � �� � � � � � ����������������������������������������������������� ������������������������ ᭣ TABELA 4–1 Regras básicas da álgebra Boo- leana X = A + 0 = A X = 0 A = 0 0 X = 1 A = 1 0 ᭣ FIGURA 4–6 X = A + 1 = 1 X = 1 A = 0 1 X = 1 A = 1 1 ᭣ FIGURA 4–7 204 ■ SISTEMAS DIGITAIS Regra 3. A · 0 ؍ 0 A operação AND da variável com 0 sempre é igual a 0. Todas as vezes que uma entrada de uma porta AND for 0, a saída será 0, independente do valor da variável na outra entrada. Essa regra está ilustrada na Figura 4–8, na qual a entrada inferior está fixa em 0. Regra 4. A · 1 ؍ A A operação AND da variável com 1 é sempre igual a variável. Se A for 0 a saída da porta AND será 0. Se A for 1, a saída da porta AND será 1 porque ambas as entradas ago- ra são 1s. Essa regra é mostrada na Figura 4–9, onde a entrada inferior está fixa em 1. Regra 5. A ؉ A = A A operação OR da variável com ela mesma é sempre igual a variável. Se A for 0, então 0 + 0 = 0; e se A for 1, então 1 + 1 = 1. Isso é mostrado na Figura 4–10, onde as duas entradas são a mesma variável. Regra 6. A operação OR da variável com o seu complemento é sempre igual a 1. Se A for 0, então Se A for 1, então Veja a Figura 4–11, onde uma entrada é o complemento da outra. Regra 7. A · A ؍ A A operação AND de uma variável com ela mesma é sempre igual a variá- vel. Se A = 0, então 0 · 0 = 0; e se A = 1, então 1 · 1 = 1. A Figura 4–12 ilustra essa regra. p 1 + 1 = 1 + 0 = 1.0 + 0 = 0 + 1 = 1. – A + A = 1 X = A • 0 = 0 X = 0 A = 1 0 X = 0 A = 0 0 ᭤ FIGURA 4–8 X = A • 1 = A X = 0 A = 0 1 X = 1 A = 1 1 ᭤ FIGURA 4–9 X = A + A = A X = 1 A = 1 A = 1 X = 0 A = 0 A = 0 ᭤ FIGURA 4–10 X = A + A = 1 X = 1 A = 1 A = 0 X = 1 A = 0 A = 1 ᭤ FIGURA 4–11 X = A • A = A X = 1 A = 1 A = 1 X = 0 A = 0 A = 0 ᭤ FIGURA 4–12 CAPÍTULO 4 • ÁLGEBRA BOOLEANA E SIMPLIFICAÇÃO LÓGICA ■ 205 Regra 8. A operação AND de uma variável e o seu complemento é sempre igual a 0. Nesse caso, ou A– ou sempre será 0; e quando um 0 é aplicado na entrada de uma porta AND, a saí- da também será 0. A Figura 4–13 ilustra essa regra. Regra 9. O complemento duplo de uma variável é sempre igual a variável. Se comple- mentarmos (invertermos) a variável A uma vez, obtemos A–. Então se complementarmos (inverte- mos) A–, obtemos A, que é a variável original. Essa regra é mostrada na Figura 4–14 usando inver- sores. Regra 10. A ؉ AB ؍ A Essa regra pode ser provada aplicando a lei distributiva, Regra 2, e a Re- gra 4 como a seguir: A + B = A(1 + B) Fatorando (lei distribuitiva) = A · 1 Regra 2: (1 + B) = 1 = A Regra 4: A · 1 = A A prova é mostrada na Tabela 4–2, onde temos a tabela-verdade e a conseqüentesimplifica- ção do circuito lógico. Regra 11. Essa regra pode ser provada da seguinte forma:–A ؉ AB ؍ A ؉ B ؍ A؍ A – A · A ؍ 0 = A + B� A = AA A + AB = (A + AB) + AB� = (AA + AB) + AB� = (A + A)(A + B)� = 1 �(A + B)� Regra 10: A = A + AB Regra 7: Fatorando Regra 6: A + A = 1 Regra 4: simplifica o 1 = AA + AB + AA + AB�R egra 8: adicionando AA = 0 X = 0 A = 1 A = 0 X = 0 A = 0 A = 1 X = A • A = 0 ᭣ FIGURA 4–13 A = 1 A = 0 A = 1 A = 0 A = 1 A = 0 A = A ᭣ FIGURA 4–14 0 0 1 1 0 1 0 1 0 0 0 1 0 0 1 1 B A A igual conexão direta A B AB A + AB ᭣ TABELA 4–2 Regra 10: A + AB = A. Abra o ar- quivo T04-02 para verificar 206 ■ SISTEMAS DIGITAIS A prova é mostrada na Tabela 4–3, onde temos a tabela-verdade e a conseqüente simplificação do circuito lógico. Regra 12. (A ؉ B)(A ؉ C) ؍ A ؉ BC Essa regra pode ser provada da seguinte forma: A prova é mostrada na Tabela 4–4, onde temos a tabela-verdade e a conseqüente simplifica- ção do circuito lógico. A 0 0 1 1 B 0 1 0 1 0 1 1 1 AB 0 1 0 0 0 1 1 1 B A A B igual A + AB A + B ᭤ TABELA 4–3 Regra 11: . Abra o arquivo T04-03 para verificar A + AB = A + B = A + BC� = A �1 + BC� + B = 1 = A(1 + B) + BC� = A �1 + AB + BC� + C = 1 = A + AC + AB + BC� AA = A( A + B)(A + C) = AA + AC + AB + BC�Lei distribuitivaRegra 7: = A(1 + C) + AB + BC� Fatorando (lei distribuitiva) Regra 2: 1 Fatorando (lei distribuitiva) Regra 2: 1 Regra 4: A�1 = A A 0 0 0 0 1 1 1 1 B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 1 1 1 1 BC 0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 B A C C B A igual A + B A + C (A + B)(A + C) A + BC ᭢ TABELA 4–4 Regra 12: (A + B)(A + C) = A + BC. Abra o arquivo T04-04 para verificar SEÇÃO 4–2 REVISÃO 1. Aplique a lei associativa da adição na expressão A + (B + C + D). 2. Aplique a lei distributiva na expressão A(B + C + D). CAPÍTULO 4 • ÁLGEBRA BOOLEANA E SIMPLIFICAÇÃO LÓGICA ■ 207 Um dos teoremas de DeMorgan é: O complemento de um produto de variáveis é igual a soma dos complementos das variáveis. Dizendo de outra forma, O complemento de duas ou mais variáveis submetidas a uma operação AND é equiva- lente a uma operação OR entre os complementos das variáveis individuais. A fórmula que expressa esse teorema para duas variáveis é: O segundo teorema de DeMorgan é expresso da seguinte forma: O complemento de uma soma de variáveis é igual ao produto do complemento das va- riáveis. Dizendo de outra forma, O complemento de duas ou mais variáveis submetidas a uma operação OR é equivalen- te a uma operação AND entre os complementos das variáveis individuais. A fórmula para a expressão desse teorema para duas variáveis é: A Figura 4–15 mostra as equivalências de portas e as tabelas-verdade para as Equações 4–6 e 4–7. X + Y = X Y XY = X + Y 4-3 TEOREMAS DE DEMORGAN DeMorgan, um matemático que conheceu Boole, propôs dois teoremas que representam uma parte importante da álgebra Booleana. Em termos práticos, os teoremas de DeMorgan provêm uma verificação da equivalência entre as portas NAND e OR negativa e a equivalência entre as portas NOR e AND negativa, discutidas no Capítulo 3. Ao final do estudo desta seção você deverá ser capaz de: ■ Citar os teoremas de DeMorgan ■ Relacionar os teoremas com a equivalência entre as portas NAND e OR negativa e a equivalência entre as portas NOR e AND negativa ■ Aplicar os teore- mas de DeMorgan na simplificação de expressões Booleanas Equação 4–6 Equação 4–7 XY X Y X + Y X Y XY X Y X + Y X Y N AND OR negativa NOR AND negativa Saída Entradas X Y XY X + Y X Y X + Y XY Saída Entradas 0 0 1 1 0 1 0 1 1 1 1 0 1 1 1 0 0 0 1 1 0 1 0 1 1 0 0 0 1 0 0 0 ᭣ FIGURA 4–15 Equivalências entre portas e as correspondentes tabelas-verda- de que ilustram os teoremas de DeMorgan. Observe a igualdade entre as duas colunas de saída em cada tabela. Isso mostra que as portas equivalentes realizam a mesma função lógica. 208 ■ SISTEMAS DIGITAIS Conforme já foi dito, os teoremas de DeMorgan também se aplicam a expressões nas quais existem mais que duas variáveis. Os exemplos a seguir ilustram a aplicação dos teoremas de De- Morgan em expressões de 3 e 4 variáveis. EXEMPLO 4–3 Aplique os teoremas de DeMorgan nas expressões: Solução Problema relacionado Aplique o teorema de DeMorgan na expressão: X + Y + Z. X + Y + Z = X Y Z XYZ = X + Y + Z X + Y + Z.XYZ e EXEMPLO 4–4 Aplique os teoremas de DeMorgan nas expressões: Solução Problema relacionado Aplique o teorema de DeMorgan na expressão: W X Y Z. W + X + Y + Z = W X Y Z WXYZ = W + X + Y + Z WXYZ e W + X + Y + Z. Cada variável nos teoremas de DeMorgan, conforme dito nas Equações 4–6 e 4–7, também pode representar uma combinação de outras variáveis. Por exemplo, X pode ser igual ao termo AB + C e Y pode ser igual ao termo A + BC. Assim, se podemos aplicar o teorema de DeMorgan para duas variáveis conforme foi dito para na expressão , obtemos o seguinte resultado: Observe que no resultado anterior temos dois termos, , para cada um dos quais podemos aplicar novamente o teorema de DeMorgan individualmente, con- forme a seguir: Observe que ainda temos dois termos na expressão nos quais o teorema de DeMorgan pode ser aplicado novamente. Esses termos são Uma última aplicação do teorema de DeMor- gan resulta no seguinte: Embora esse resultado possa ser simplificado pelo uso das leis e regras Booleanas, os teore- mas de DeMorgan não podem mais ser usados. Aplicando os Teoremas de DeMorgan Os procedimentos a seguir ilustram a aplicação dos teoremas de DeMorgan e da álgebra Boolea- na na seguinte expressão: Passo 1. Identifique os termos nos quais podemos aplicar os teoremas de DeMorgan e pense que cada termo é uma única variável. Faça A + BC = X e D(E + F) = Y. A + BC + D(E + F) (AB)C + A(BC) = (A + B)C + A(B + C) AB e BC. (AB + C) + (A + BC) = (AB)C + A(BC) X + Y = X Y AB + C e A + BC (AB + C)(A + BC) = (AB + C) + (A + BC) (AB + C)(A + BC)XY = X + Y CAPÍTULO 4 • ÁLGEBRA BOOLEANA E SIMPLIFICAÇÃO LÓGICA ■ 209 Passo 2. Como Passo 3. Use a Regra 9 para cancelar a dupla barra sobre o termo da esquerda (isso não é parte do teorema de DeMorgan). Passo 4. Aplique o teorema de DeMorgan ao segundo termo. Passo 5. Use a Regra 9 para cancelar a dupla barra sobre a parte do termo. Os próximos três exemplos ilustram ainda mais como usar os teoremas de DeMorgan. (A + BC)(D + E + F) = (A + BC)(D + E + F) E + F(A = A) (A + BC)(D(E + F)) = (A + BC)(D + (E + F)) (A + BC)(D(E + F)) = (A + BC)(D(E + F)) (A = A) (A + BC) + (D(E + F)) = (A + BC)(D(E + F)) X + Y = X Y, EXEMPLO 4–5 Aplique os teoremas de DeMorgan em cada uma das seguintes expressões: Solução (a) Faça A + B + C = X e D = Y. A expressão é da forma e pode ser reescrita como: Em seguida aplique o teorema de DeMorgan no termo (b) Faça ABC = X e DEF = Y. A expressão está na forma e pode ser reescrita da seguinte forma: Em seguida, aplique o teorema de DeMorgan em cada um dos seguintes termos: (c) Faça A expressão está na forma e pode ser reescrita como: Em seguida, aplique o teorema de DeMorgan em cada um dos seguintes termos: Problema relacionado Aplique os teoremas de DeMorgan na expressão: ABC + D + E. (AB)(CD)(EF) = (A + B)(C + D)(E + F) AB, CD e EF. AB + CD + EF = (AB)(CD)(EF) X + Y + Z = X Y Z AB + CD + EFAB = X, CD = Y e EF = Z. (ABC)(DEF) = (A + B + C)(D + E + F) ABC e DEF. ABC + DEF = (ABC)(DEF) X + Y = X YABC + DEFA + B + C. (A + B + C)D = A + B + C + D XY = X + Y(A + B + C)D (a) (b) (c) AB + CD + EFABC + DEF(A + B + C)D 210 ■ SISTEMAS DIGITAIS 4-4 ANÁLISE BOOLEANA DE CIRCUITOS LÓGICOS A álgebra Booleana provê uma forma concisa de expressar a operação de um circuito lógico constituído de uma combinação de portas lógicas de forma que a saída possa ser determinada por várias combinações de valores de entrada. Ao final do estudo desta seção você deverá ser capaz de: ■ Determinar a expressão Booleana para uma combinação de portas ■ Avaliar a operação ló- gica de um circuito a partir da expressão Booleana ■ Construir uma tabela-verdade EXEMPLO 4–6 Aplique os teoremas de DeMorgan em cada uma das expressões a seguir: Solução Problema relacionado Aplique os teoremas na expressão AB(C + D) + E. (a) (b) (c) (A + B)C D + E + F = ((A + B)C D)(E + F) = (A B + C + D)EF (A + B) + CD = (A + B)CD = (A B)(C + D) = AB(C + D) (A + B) + C = (A + B)C = (A + B)C (a) (b) (c) (A + B)C D + E + F(A + B) + CD(A + B) + C EXEMPLO 4–7 A expressão Booleana para uma porta EX-OR é Tendo essa expressão como ponto de partida, use o teorema de DeMorgan e quaisquer outras regras ou leis aplicáveis para desenvolver uma expressão para a porta EX-NOR. Solução Comece pela complementação da expressão para a EX-OR, aplicando em seguida o teo- rema de DeMorgan como mostrado a seguir: Em seguida, aplique a lei distributiva e a Regra A expressão final para a EX-NOR é Observe que essa expressão é igual a 1 todas as vezes que as duas variáveis forem 0 ou 1. Problema relacionado Começando pela expressão da porta NAND de 4 entradas, use os teoremas de DeMorgan para desenvolver uma expressão para uma porta OR negativa de 4 entradas. A B + AB. (A + B)(A + B) = AA + A B + AB + BB = A B + AB 8 (A · A = 0). AB + AB = (AB)(AB) = (A + B)(A + B) = (A + B)(A + B) AB + AB. SEÇÃO 4–3 REVISÃO 1. Aplique os teoremas e DeMorgan às seguintes expressões: (b) (c) A + B + C + DE(A + B)CABC + (D + E)(a) CAPÍTULO 4 • ÁLGEBRA BOOLEANA E SIMPLIFICAÇÃO LÓGICA ■ 211 Expressão Booleana para um Circuito Lógico Para obter a expressão Booleana para um dado circuito lógico, comece pelas entradas mais à es- querda e, percorrendo o circuito até a saída final, escreva a expressão para cada porta lógica. Pa- ra o exemplo de circuito mostrado na Figura 4–16, a expressão Booleana é determinada da se- guinte forma: 1. A expressão para a porta AND mais à esquerda com entradas C e D é CD. 2. A saída da porta AND mais à esquerda é uma das entradas da porta OR e B é a outra entra- da. Portanto, a expressão para a porta OR é B + CD. 3. A saída da porta OR é uma das entradas da porta AND mais à direita e A é a outra entrada. Portanto, a expressão para essa porta AND é A(B + CD), que é a expressão final de saída pa- ra o circuito completo. Construindo uma Tabela-verdade para um Circuito Lógico Uma vez que a expressão Booleana para um dado circuito lógico foi determinada, uma tabela- verdade que mostra a saída para todos os valores possíveis das variáveis de entrada pode ser de- senvolvida. O procedimento requer que avaliemos a expressão Booleana para todas as combina- ções possíveis dos valores das variáveis de entrada. No caso do circuito visto na Figura 4–16, existem quatro variáveis de entrada (A, B, C e D) sendo possível portanto dezesseis (24 = 16) combinações de valores. Calculando a Expressão Para o cálculo da expressão A(B + CD), determine primeiro os valo- res das variáveis que tornam a expressão igual a 1, usando as regras para a adição e multiplicação Booleanas. Nesse caso, a expressão é igual a 1 apenas se A = 1 e B + CD = 1 porque A(B + CD) = 1 · 1 = 1 Agora determine quando o termo B + CD é igual a 1. O termo B + CD = 1 se B = 1 ou CD = 1 ou se B e CD forem ambos iguais a 1 porque B + CD = 1 + 0 = 1 B + CD = 0 + 1 = 1 B + CD = 1 + 1 = 1 O termo CD = 1 apenas se C = 1 e D = 1. Resumindo, a expressão A (B + CD) = 1 quando A = 1 e B = 1 independente dos valores de C e D ou quando A = 1, C = 1 e D = 1 independente do valor de B. A expressão A (B + CD) = 0 pa- ra todas as outras combinações de valores das variáveis. Colocando os Resultados no Formato de Tabela-Verdade O primeiro passo é fazer uma lista das dezesseis combinações de 1s e 0s das variáveis de entrada numa seqüência binária conforme mostra a Tabela 4–5. Em seguida, coloque um 1 na coluna de saída para cada combinação das va- riáveis de entrada que foi determinada na avaliação. Finalmente, coloque um 0 na coluna de saída para todas as outras combinações das variáveis de entrada. Esses resultados são mostrados na ta- bela-verdade na Tabela 4–5. Um circuito lógico pode ser descrito por uma equação Booleana. Um circuito lógico pode ser descrito por uma tabela- verdade. CD D B B + CD C A A(B + CD) ᭣ FIGURA 4–16 Um circuito lógico mostrando o desenvolvimento da expressão Booleana de saída. 212 ■ SISTEMAS DIGITAIS Uma expressão Booleana simplificada usa a menor quantidade de portas possível para imple- mentar uma dada expressão. Os Exemplos 4–8 a 4–11 ilustram a simplificação Booleana. 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 ENTRADAS SAÍDA A B C D A(B + CD) ᭤ TABELA 4–5 Tabela-verdade para o circuito lógico mostrado na Figura 4–16 SEÇÃO 4–4 REVISÃO 1. Substitua as portas AND por portas OR e a porta OR por porta AND no circuito visto na Figura 4–16 e determine a expressão Booleana para a saída. 2. Construa uma tabela-verdade para o circuito da Questão 1. 4-5 SIMPLIFICAÇÃO USANDO A ÁLGEBRA BOOLEANA Ao aplicarmos a álgebra Booleana, muitas vezes temos que reduzir uma determinada expressão para a sua forma mais simples ou transformá-la em um formato mais conveniente a fim de im- plementar a expressão mais eficientemente. A abordagem feita nesta seção usa as leis básicas, re- gras e teoremas da álgebra Booleana para manipular e simplificar uma expressão. Esse método depende do conhecimento completo da álgebra Booleana e uma considerável prática na sua apli- cação, além de habilidade e inteligência. Ao final do estudo desta seção você deverá ser capaz de: ■ Aplicar as leis, regras e teoremas da álgebra Booleana para simplificar expressões em geral CAPÍTULO 4 • ÁLGEBRA BOOLEANA E SIMPLIFICAÇÃO LÓGICA ■ 213 A Figura 4–17 mostra que o processo de simplificação dado no Exemplo 4–8 reduziu significati- vamente o número de portas lógicas necessárias para implementar a expressão. A parte (a) dessa figura mostra que cinco portas são necessárias para implementar a expressão na sua forma origi- nal; entretanto, apenas duas portas são necessárias para a expressão simplificada, mostrada na par- te (b). É importante perceber que esses dois circuitos de portas são equivalentes. Ou seja, para qualquer combinação de níveis nas entradas A, B e C temos a mesma saída para qualquer um dos dois circuitos. EXEMPLO 4–8 Usando técnicas da álgebra Booleana, simplifique a expressão AB + A(B + C) + B(B + C) Solução Os passos apresentados a seguir não representam necessariamente a única abordagem. Passo 1 Aplique a lei distributiva ao segundo e terceiro termos da expressão, conforme mostrado a seguir: AB + AB + AC + BB + BC Passo 2 Aplique a Regra 7 (BB = B) no quarto termo. AB + AB + AC + B + BC Passo 3 Aplique a Regra 5 (AB + AB = AB) nos primeiros dois termos. AB + AC + B + BC Passo 4 Aplique a Regra 10 (B + BC = B) nos últimos dois termos. AB + AC + B Passo 5 Aplique a Regra 10 (AB + B = B) ao primeiro e terceiro termos. B + AC Nesse ponto a expressão está com a máxima simplificação possível. Uma vez adquirido prática na aplicação da álgebra Booleana, podemos combinar diversos passos indivi- duais. Problema relacionado Simplifique a expressãoBooleana AB + A(B + C) + B(B + C). Simplificação significa me- nos portas lógicas para a mesma função. B C A AB + A(B + C) + B(B + C) C B + AC A B (a) (b) Esses dois circuitos são equivalentes ᭡ FIGURA 4–17 Circuitos de portas para o Exemplo 4–8. Abra o arquivo F04-17 para verificar a equivalência. 214 ■ SISTEMAS DIGITAIS EXEMPLO 4–9 Simplifique a seguinte expressão Booleana: Observe que os colchetes e parênteses significam o mesmo: o termo interno é multiplica- do (operação AND) com os termos externos. Solução Passo 1 Aplique a lei distributiva aos termos dentro dos colchetes. Passo 2 Aplique a Regra 8 ao segundo termo dentro dos parênteses. Passo 3 Aplique a Regra 3 (A · 0 · D = 0) ao segundo termo dentro dos parênteses. Passo 4 Aplique a Regra 1 (simplifique o 0) dentro dos parênteses. Passo 5 Aplique a lei distributiva. Passo 6 Aplique a Regra 7 (CC = C) ao primeiro termo. Passo 7 Fatore Passo 8 Aplique a Regra 6 Passo 9 Aplique a Regra 4 (simplifique o 1). Problema relacionado Simplifique a seguinte expressão Booleana [AB(C + B D) + A B]CD. BC BC �1 (A + A = 1). BC(A + A) BC. ABC + A BC ABCC + A BC (ABC + A B)C (ABC + 0 + A B)C (ABC + A �0 �D + A B)C (BB = 0) (ABC + ABBD + A B)C [AB(C + BD) + A B]C EXEMPLO 4–10 Simplifique a seguinte expressão Booleana: Solução Passo 1 Fatore BC com o primeiro e o último termos. Passo 2 Aplique a Regra 6 ao termo entre parênteses e fatore a partir do segundo e último termos. BC �1 + AB(C + C) + A B C AB(A + A + 1) BC(A + A) + AB C + A B C + ABC ABC + AB C + A B C + ABC + ABC CAPÍTULO 4 • ÁLGEBRA BOOLEANA E SIMPLIFICAÇÃO LÓGICA ■ 215 Passo 3 Aplique a Regra 4 (simplifique o 1) ao primeiro termo e a Regra 6 ao termo entre parênteses. Passo 4 Aplique a Regra 4 (simplifique o 1) no segundo termo. Passo 5 Fatore B– a partir do segundo e terceiro termos. Passo 6 Aplique a Regra 11 no termo entre parênteses. Passo 7 Use as leis distributiva e comutativa para obter a seguinte expressão: Problema relacionado Simplifique a seguinte expressão Booleana: ABC + A BC + ABC + A B C. BC + AB + B C BC + B(A + C) (A + A C = A + C) BC + B(A + A C) BC + AB + A B C BC + AB�1 + A B C (C + C = 1) EXEMPLO 4–11 Simplifique a seguinte expressão Booleana: Solução Passo 1 Aplique o teorema de DeMorgan no primeiro termo. Passo 2 Aplique o teorema de DeMorgan em cada termo entre parênteses. Passo 3 Aplique a lei distributiva ao dois termos entre parênteses. Passo 4 Aplique a Regra 7 no primeiro termo, e aplique a Regra 10 no terceiro e último termos. Passo 5 Aplique a Regra 10 no primeiro e segundo termos. Passo 6 Aplique a Regra 10 no primeiro e segundo termos. Problema relacionado Simplifique a seguinte expressão Booleana: AB + AC + A B C. A + B C [A + A B = A(1 + B) = A] A + A B + B C [A + A C = A(1 + C) = A] A + A C + A B + B C [A B + A BC = A B(1 + C) = A B] (A A = A) A A + A C + A B + B C + A BC (A + B)(A + C) + A BC (AB)(AC) + A BC AB + AC + A BC 216 ■ SISTEMAS DIGITAIS A Forma de soma-de-produtos Um termo-produto foi definido na Seção 4–1 como um termo que consiste em produto (multipli- cação Booleana) de literais (variáveis ou seus complementos). Quando dois ou mais termos-pro- duto são somados por uma adição Booleana, a expressão resultante é uma soma-de-produtos. Al- guns exemplos são mostrados a seguir: Uma expressão na forma de soma-de-produtos também pode conter um termo de uma úni- ca variável, como em Consulte os exemplos de simplificação na última se- ção, e o leitor verá que cada uma das expressões finais é um termo de produto único ou uma so- ma-de-produtos. Numa expressão na forma de soma-de-produtos, uma barra não se estende por mais que uma variável; entretanto, mais de uma variável num termo pode ter uma barra sobre ela. Por exemplo, uma expressão na forma de soma-de-produtos pode ter um termo po- rém não um termo Domínio de uma Expressão Booleana O domínio de uma expressão Booleana geral é o con- junto das variáveis contidas na expressão na forma complementada ou não complementada. Por exemplo, o domínio da expressão é o conjunto das variáveis A, B, C, e o domínio da expressão é o conjunto das variáveis A, B, C, D e E. Implementação AND/OR de uma Expressão de soma-de-produtos A implementação de uma expressão de soma-de-produtos requer simplesmente uma operação OR das saídas de duas ou mais portas AND. Um termo-produto é produzido por uma operação AND e a soma (adição) de dois ou mais termos-produto é produzida por uma operação OR. Portanto, uma expressão de soma-de-produtos pode ser implementada por uma lógica AND/OR na qual as saídas (em quanti- dade igual ao número de termos-produto na expressão) de portas AND são conectadas às entradas de uma porta OR, conforme mostra a Figura 4–18 para a expressão AB + BCD + AC. A saída X da porta OR é igual a expressão de soma-de-produtos. ABC + CDE + BCD AB + ABC ABC. A B C A + A BC + BCD. AB + ABC + AC ABC + CDE + BCD AB + ABC SEÇÃO 4–5 REVISÃO 1. Simplifique, quando possível, as seguintes expressões Booleanas: 2. Implemente cada expressão originalmente apresentada na Questão 1 usando as portas lógicas apropriadas. Em seguida, implemente a expressão simplificada e compare o número de portas. (a) (b) – (c) ABC( BD + CDE) + ACA + AB + ABC (A + B)C + ABC 4-6 FORMAS PADRONIZADAS DE EXPRESSÕES BOOLEANAS Todas as expressões Booleanas, independente das suas formas, podem ser convertidas em qual- quer uma das duas formas padrão: a forma de soma-de-produtos e a forma de produto-de-somas. A padronização faz a avaliação, simplificação e implementação de expressões Booleanas de for- ma muito mais sistemática e fácil. Ao final do estudo desta seção você deverá ser capaz de: ■ Identificar uma expressão de soma-de-produtos ■ Determinar o domínio de uma expres- são Booleana ■ Converter qualquer expressão de soma-de-produtos para uma forma padrão ■ Avaliar uma expressão padrão de soma-de-produtos em termos dos valores binários ■ Iden- tificar uma expressão de produto-de-somas ■ Converter qualquer expressão de produto-de-so- mas para uma forma padrão ■ Avaliar uma expressão padrão de produto-de-somas em termos dos valores binários ■ Converter expressões de um padrão para outro Uma expressão de soma- de-produtos pode ser im- plementada com uma OR e duas ou mais ANDs. CAPÍTULO 4 • ÁLGEBRA BOOLEANA E SIMPLIFICAÇÃO LÓGICA ■ 217 Implementação NAND/NAND de uma Expressão de soma-de-produtos As portas NAND po- dem ser usadas na implementação de uma expressão de soma-de-produtos. Usando apenas portas NAND, uma função AND/OR pode ser realizada, conforme ilustra a Figura 4–19. O primeiro nível de portas NAND alimenta a porta NAND que funciona como uma porta OR negativa. As inversões da porta NAND e da OR negativa se cancelam e o resultado é efetivamente um circuito AND/OR. Conversão de uma Expressão Geral para a Forma de soma-de-produtos Qualquer expressão lógica pode ser mudada para o formato de soma-de-produtos aplicando técni- cas da álgebra Booleana. Por exemplo, a expressão A(B + CD) pode ser convertida para o forma- to de soma-de-produtos aplicando a lei distributiva: A(B + CD) = AB + ACD A B X = AB + BCD + AC B D A C C ᭣ FIGURA 4–18 Implementação da expressão de soma-de-produtos AB + BCD + AC. A B X = AB + BCD + AC B D A C C ᭣ FIGURA 4–19 Essa implementação NAND/NAND é equivalente a AND/OR da Figura 4–18. EXEMPLO 4–12 Converta cada uma das seguintes expressões Booleanas para o formato de soma-de-produtos: Solução Problema relacionado Converta para a forma de soma-de-produtos.ABC + (A + B)( B + C + AB) (a) (b) = (A + B)C = (A + B)C = AC + BC AB + B(CD + EF) = AB + BCD + BEF (A + B)(B + C + D) = AB + AC + AD + BB+ BC + BD (c) (A + B) + C (a) (b) (c)AB + B(CD + EF) (A + B)(B + C + D) (A + B) + C A Forma Padrão de soma-de-produtos Até agora, lidamos com expressões de soma-de-produtos nas quais alguns dos termos-produto não continham todas as variáveis no domínio da expressão. Por exemplo, a expressão tem um domínio constituído pelas variáveis A, B, C e D. Entretanto, observe que o conjun- to completo de variáveis do domínio não é representado nos primeiros dois termos da expressão; ou seja, não aparece no primeiro termo e não aparece no segundo termo. Uma expressão de soma-de-produtos padrão é uma expressão na qual todas as variáveis do do- mínio aparecem em cada um dos termos-produto na expressão. Por exemplo, é uma expressão de soma-de-produtos padrão. Expressões de soma-de-produtos padrão são importantes na construção de tabelas-verdade, abordado na Seção 4–7, e no uso do método de sim- plificação com mapa de Karnaugh, o qual é abordado na Seção 4–8. Qualquer expressão de soma- de-produtos não padrão (mencionada simplesmente como soma-de-produtos) pode ser convertida na forma padrão usando a álgebra Booleana. ABC D ABCD + A BCD + C ou CD ou D ABCD ABC + ABD + 218 ■ SISTEMAS DIGITAIS Conversão de Termos-Produto para Soma-de-Produtos Padrão Cada termo-produto numa expressão de soma-de-produtos que não contém todas as variáveis do domínio pode ser expandi- da para a forma padrão de modo a incluir todas as variáveis do domínio e seus complementos. Conforme expresso nos passos a seguir, uma expressa de soma-de-produtos não padrão é conver- tida na forma padrão usando a regra 6 da álgebra Booleana a partir da Tabela 4–1: uma variável somada ao seu complemento é igual a 1. Passo 1. Multiplique cada termo-produto não padrão por um termo constituído de uma soma de uma variável que não aparece no termo com o seu complemento. O resultado é dois termos-pro- duto. Conforme sabemos, podemos multiplicar qualquer coisa por 1 sem alterar o seu valor. Passo 2. Repita o passo 1 até que todos os termos-produto resultantes contenham todas as variá- veis do domínio na forma complementada ou não-complementada. Na conversão de um termo-produto para a forma padrão, o número de termos-produto é duplicado para cada variável que não aparece, conforme mostra o Exemplo 4–13. (A + A = 1) EXEMPLO 4–13 Converta a seguinte expressão Booleana para a forma de soma-de-produtos padrão: Solução O domínio dessa expressão de soma-de-produtos é A, B, C, D. Trabalhe com um termo de cada vez. O primeiro termo, não tem a variável então multiplique o primeiro termo por , conforme mostrado a seguir: Nesse caso, dois termos-produto padrão aparecem como resultado. No segundo termo, não aparece a variável .Assim, multiplique primeiro o segundo termo por , conforme mostrado a seguir: Nos dois termos resultantes não aparece a variável assim, multiplique os dois termos por , conforme mostrado a seguir: Nesse caso, o resultado são quatro termos-produto padrão. O terceiro termo, já está na forma padrão. O formato completo padrão da soma dos produtos da expressão original é: Problema relacionado Converta para a forma padrão de soma-de-produtos.WXY + XYZ + WXY ABC + A B + ABCD = ABCD + ABCD + A BCD + A BCD + A B CD + A B C D + ABCD ABCD, = A BCD + A BCD + A B CD + A B C D A B = A BC + A B C = A BC(D + D) + A B C(D + D) D + D D ou D, A B = A B(C + C) = A BC + A B C C + C C ou C e D ou DA B, ABC = ABC(D + D) = ABCD + ABCD D + D D ou D,ABC, ABC + A B + ABCD Representação Binária de um Termo-produto Padrão Um termo-produto padrão é igual a 1 para apenas uma combinação de valores das variáveis. Por exemplo, o termo-produto é igual a 1 quando A = 1, B = 0, C = 1 e D = 0, conforme mostrado abaixo, e é 0 para todas as outras combinações de valores das variáveis. Nesse caso, o termo-produto tem um valor binário de 1010 (decimal dez). Lembre-se, o termo-produto é implementado com uma porta AND cuja saída é 1 apenas se ca- da uma de suas entradas for 1. Inversores são usados para produzir os complementos das variáveis conforme necessário. Uma expressão na forma de soma-de-produtos é igual a 1 apenas se um ou mais dos ter- mos-produto na expressão for igual a 1. ABCD = 1 �0 �1 �0 = 1 �1 �1 �1 = 1 ABCD CAPÍTULO 4 • ÁLGEBRA BOOLEANA E SIMPLIFICAÇÃO LÓGICA ■ 219 EXEMPLO 4–14 Determine os valores binários para os quais a expressão de soma-de-produtos padrão a seguir é igual a 1: Solução O termo ABCD é igual a 1 quando A = 1, B = 1, C = 1 e D = 1. ABCD = 1 · 1 · 1 · 1 = 1 O termo é igual a 1 quando A = 1, B = 0, C = 0 e D = 1. O termo é igual a 1 quando A = 0, B = 0, C = 0 e D = 0. A expressão de soma-de-produtos é igual a 1 quando qualquer um ou os três termos-pro- duto for 1. Problema relacionado Determine os valores binários para os quais a seguinte expressão de soma-de-produtos é igual a 1: Essa expressão é uma soma-de-produtos padrão? XYZ + XYZ + XYZ + XYZ + XYZ A B C D = 0 �0�0�0 = 1 �1 �1 �1 = 1 A B C D AB CD = 1 �0�0�1 = 1 �1 �1 �1 = 1 AB CD ABCD + AB CD + A B C D A Forma de Produto-de-Somas Um termo-soma foi definido na Seção 4–1 como um termo que consiste de uma soma (adição Boo- leana) de literais (as variáveis ou seus complementos). Quando dois ou mais termos-soma são mul- tiplicados, a expressão resultante é um produto-de-somas. Alguns exemplos são mostrados a seguir: Uma expressão de produto-de-somas pode conter um termo com uma única variável, confor- me ocorre em Numa expressão de produto-de-somas, uma única barra sobreposta não pode se estender por mais que uma variável; entretanto, mais que uma variá- vel no termo pode conter uma barra sobreposta. Por exemplo, uma expressão de produto-de-so- mas pode ter um termo mas não um termo Implementação de uma Expressão de Produto-de-Somas A implementação de uma expres- são de produto-de-somas requer simplesmente uma operação AND entre as saídas de duas ou mais portas OR. Um termo-soma é produzido por uma operação OR, sendo que o produto de dois ou mais termos-soma é produzido por uma operação AND. Portanto, uma expressão de produto-de- somas pode ser implementada por uma lógica na qual as saídas (numa quantidade igual ao núme- ro de termos-soma na expressão) das portas OR são conectadas às entradas de uma porta AND, conforme mostra a Figura 4–20 para a expressão (A + B)(B + C + D)(A + C). A saída X da porta AND é igual a expressão de produto-de-somas. A + B + C.A + B + C A(A + B + C)( B + C + D) . (A + B)( A + B + C)( A + C) (A + B + C)( C + D + E)( B + C + D) (A + B)( A + B + C) A B X = (A + B)(B + C + D)(A + C) B D A C C ᭣ FIGURA 4–20 Implementação da expressão de produ- to-de-somas (A + B)(B + C + D)(A + C). 220 ■ SISTEMAS DIGITAIS A Forma Padrão de Produto-de-Somas Até agora, temos lidado com expressões nas quais alguns dos termos-soma não continham todas as variáveis do domínio da expressão. Por exemplo, a expressão tem um domínio constituído pelas variáveis A, B, C e D. Observe que o conjunto completo das va- riáveis no domínio não é representada nos dois primeiros termos da expressão; ou seja, não aparece no primeiro termo e não aparece no segundo termo. Uma expressão de produto-de-somas padrão é uma expressão na qual todas as variáveis do domínio aparecem em cada termo-soma na expressão. Por exemplo, é uma expressão de produto-de-somas. Qualquer expressão de produto-de-somas não padrão (menciona- da simplesmente de produto-de-somas) pode ser convertida na forma padrão usando a álgebra Booleana. Conversão de um Termo-Soma para um Produto-de-Somas Padrão Cada termo-soma nu- ma expressão de produto-de-somas que não contém todas as variáveis do domínio pode ser expan- dido para a forma padrão de modo a incluir todas as variáveis do domínio e os seus complemen- tos. Conforme expresso nos passos a seguir, uma expressão de produto-de-somasnão padrão é convertida para a forma padrão usando a Regra 8 da álgebra Booleana a partir da Ta- bela 4–1: a variável multiplicada pelo seu complemento é igual a 0. Passo 1. Acrescente a cada termo-produto não padrão um termo constituído do produto da va- riável que não aparece pelo complemento dela. Isso resulta em dois termos-soma. Co- mo sabemos, podemos somar 0 com qualquer coisa sem alterar o seu valor. Passo 2. Aplique a Regra 12 a partir da Tabela 4–1: A + BC = (A + B)(A + C) Passo 3. Repita o passo 1 até que todos os termos-soma resultantes contenham todas as variá- veis do domínio na forma complementada ou não complementada. (A · A = 0) (A + B + C + D)( A + B + C + D)( A + B + C + D) C ou C D ou D (A + B + C)( A + B + D)( A + B + C + D) EXEMPLO 4–15 Converta a seguinte expressão Booleana para a forma de produto-de-somas padrão: Solução O domínio dessa expressão de produto-de-somas é A, B, C e D. Trabalhe com um termo de cada vez. No primeiro termo, a variável não aparece, assim, acrescentamos e aplicamos a Regra 12 como mostrado a seguir: No segundo termo, a variável não aparece, assim, acrescentamos e aplicamos a Regra 12 como mostrado a seguir: O terceiro termo, já está na forma padrão. A forma do produto-de-so- mas padrão a partir da expressão original é: Problema relacionado Converta para a forma de produto-de-somas.A + B + C + D =(A + B + C)( B + C + D)( A + B + C + D) (A + B + C + D)( A + B + C + D)( A + B + C + D)( A + B + C + D)( A + B + C + D) A + B + C + D, B + C + D = B + C + D + AA = (A + B + C + D)( A + B + C + D) AA A ou AB + C + D, A + B + C = A + B + C + DD = (A + B + C + D)( A + B + C + D) DD D ou DA + B + C, (A + B + C)( B + C + D)( A + B + C + D) Representação Binária de um Termo-Soma Padrão Um termo-soma padrão é igual a 0 para apenas uma combinação de valores das variáveis. Por exemplo, o termo-soma é 0 quando A = 0, B = 1, C = 0 e D = 1, conforme mostrado abaixo, e é 1 para todas as outras com- binações de valores das variáveis. A + B + C + D = 0 + 1 + 0 + 1 = 0 + 0 + 0 + 0 = 0 A + B + C + D CAPÍTULO 4 • ÁLGEBRA BOOLEANA E SIMPLIFICAÇÃO LÓGICA ■ 221 Nesse caso, o termo-soma tem um valor binário e 0101 (decimal 5). Lembre-se, um termo-soma é implementado com uma porta OR cuja saída é 0 apenas se cada uma de suas entradas for 0. In- versores são usados para produzir os complementos das variáveis conforme necessário. Uma expressão na forma de produto-de-somas é igual a 0 apenas se um ou mais termos- soma na expressão for igual a 0. EXEMPLO 4–16 Determine os valores binários das variáveis para os quais as seguintes expressões produ- to-de-somas sejam iguais a zero. Solução O termo A + B + C + D é igual a 0 quando A = 0, B = 0, C = 0 e D = 0. A + B + C + D = 0 + 0 + 0 + 0 = 0 O termo é igual a zero quando A = 0, B = 1, C = 1 e D = 0. O termo é igual a 0 quando A = 1, B = 1, C = 1 e D = 1. A expressão de produto-de-somas é igual a 0 quando qualquer dos três termos-soma for igual a 0. Problema relacionado Determine os valores binários para os quais a seguinte expressão de produto-de-somas é igual a 0: Essa expressão é um produto-de-somas padrão? (X + Y + Z)( X + Y + Z)( X + Y + Z)( X + Y + Z)( X + Y + Z) A + B + C + D = 1 + 1 + 1 + 1 = 0 + 0 + 0 + 0 = 0 A + B + C + D A + B + C + D = 0 + 1 + 1 + 0 = 0 + 0 + 0 + 0 = 0 A + B + C + D (A + B + C + D)( A + B + C + D)( A + B + C + D) Conversão de uma Soma-de-Produtos Padrão para um Produto-de- Somas Padrão Os valores binários dos termos-produto numa dada expressão de soma-de-produtos não estão pre- sentes na expressão equivalente de produto-de-somas padrão. Além disso, os valores binários que não são representados na expressão de soma-de-produtos estão presentes na expressão equivalen- te de produto-de-somas. Portanto, para converter de soma-de-produtos padrão para produto-de-so- mas padrão, os passos a seguir são realizados: Passo 1. Avalie cada termo-produto na expressão de soma-de-produtos. Ou seja, determine os números binários que representam os termos-produto. Passo 2. Determine todos os números binários não incluídos na avaliação no Passo 1. Passo 3. Escreva o termo-soma equivalente para cada número binário a partir do passo 2 e os ex- presse na forma de produto-de-somas. EXEMPLO 4–17 Converta a seguinte expressão de soma-de-produtos para uma expressão equivalente de produto-de-somas: Solução A avaliação é a seguinte: 000 + 010 + 011 + 101 + 111 Como existem três variáveis de domínio nessa expressão, existe um total de oito (23) com- binações possíveis. A expressão de soma-de-produtos contém cinco dessas combinações, assim, o produto-de-somas tem que conter os outros três os quais são 001, 100 e 110. A B C + ABC + ABC + ABC + ABC 222 ■ SISTEMAS DIGITAIS Conversão de Expressões de soma-de-produtos para o Formato de Tabela-Verdade Lembre-se, da Seção 4–6, de que uma expressão de soma-de-produtos é igual a 1 apenas se pelo menos um dos termos-produto for igual a 1. Uma tabela-verdade é simplesmente uma lista de com- binações possíveis dos valores das variáveis de entrada e os correspondentes valores de saída (1 ou 0). Para uma expressão com um domínio de duas variáveis, existem quatro combinações diferen- tes para as variáveis (22 = 4). Para uma expressão com um domínio de três variáveis, existem oito diferentes combinações de variáveis (23 = 8). Para uma expressão com um domínio de quatro va- riáveis, existem dezesseis combinações diferentes para as variáveis (24 = 16), e assim por diante. O primeiro passo na construção de uma tabela-verdade é fazer uma lista de todas as combina- ções possíveis dos valores binários das variáveis na expressão. Em seguida, converta a expressão de soma-de-produtos para a forma padrão caso ela não esteja nesse formato. Finalmente, coloque um 1 na coluna de saída (X) para cada valor binário que torna a expressão de soma-de-produtos padrão um 1 e coloque um 0 para todos os valores binários restantes. Esse procedimento é ilustra- do no Exemplo 4–18. Lembre-se, esses são os valores binários que tornam o termo-soma 0. A expressão de produto-de-somas equivalente é Problema relacionado Verifique que as expressões de soma-de-produtos e produto-de-somas nesse exemplo são equivalentes substituindo os valores binários em cada uma. (A + B + C)(A + B + C)(A + B + C) SEÇÃO 4–6 REVISÃO 1. Identifique cada uma das seguintes expressões como soma-de-produtos, soma-de-produtos padrão, produto-de-somas e produto-de-somas padrão. 2. Converta cada expressão de soma-de-produtos na Questão 1 para a forma padrão. 3. Converta cada expressão de produto-de-somas na Questão 1 para a forma padrão. (b) (c) (d) A(A + C)(A + B)ABC + ABC (A + B + C)(A + B + C)AB + ABD + ACD(a) 4-7 EXPRESSÕES BOOLEANAS E TABELAS-VERDADE Todas as expressões Booleanas padrão podem ser facilmente convertidas no formato de uma ta- bela-verdade usando valores binários para cada termo na expressão. A tabela-verdade é uma for- ma comum de apresentação, num formato conciso, da operação lógica de um circuito. Além dis- so, expressões de soma-de-produtos padrão ou produto-de-somas podem ser determinadas a par- tir de uma tabela-verdade. Encontramos tabelas-verdade em folhas de dados e outras literaturas relacionadas à operação de circuitos digitais. Ao final do estudo desta seção você deverá ser capaz de: ■ Converter uma expressão de soma-de-produtos padrão no formato de tabela-verdade ■ Con- verter uma expressão de produto-de-somas padrão no formato de tabela-verdade ■ Obter uma expressão padrão a partir de uma tabela-verdade ■ Interpretar adequadamente os dados de uma tabela-verdade. CAPÍTULO 4 • ÁLGEBRA BOOLEANA E SIMPLIFICAÇÃO LÓGICA ■ 223 Conversão de Expressões de Produto-de-Somas para o Formato de Tabela-verdade Lembre-se de que uma expressão de produto-de-somas é igual a 0apenas se pelo menos um dos termos-soma for igual a 0. Para construir uma tabela-verdade a partir de uma expressão de produ- to-de-somas, faça uma lista de todas as combinações possíveis de valores binários das variáveis da mesma forma que foi feito para a expressão de soma-de-produtos. Em seguida, converta a expres- são de produto-de-somas para a forma padrão, caso ela ainda não esteja nesta forma. Finalmente, coloque um 0 na coluna de saída (X) para cada valor binário que torna a expressão um 0 e coloque um 1 para todos os outros valores binários restantes. Esse procedimento está ilustrado no Exem- plo 4–19. EXEMPLO 4–18 Desenvolva uma tabela-verdade para a expressão de soma-de-produtos Solução Existem três variáveis no domínio, assim existem oito combinações possíveis de valores binários das variáveis conforme listado nas três colunas à esquerda da Tabela 4–6. Os va- lores binários que tornam os termos-produto nas expressões iguais a 1 são Para cada um desses valores binários, coloque um 1 na coluna de saída como mostrado na tabela. Para cada uma das combinações binárias restantes, coloque um 0 na coluna de saída. Problema relacionado Crie uma tabela-verdade para a expressão de soma-de-produtos padrão ABC + ABC. AB C: 100; e ABC: 111. A BC: 001; A BC + AB C + ABC. 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1 ABC AB C A BC A B C ENTRADAS SAÍDA TERMO PRODUTOX ᭤ TABELA 4–6 EXEMPLO 4–19 Determine a tabela-verdade para a seguinte expressão de produto-de-somas: Solução Existem três variáveis no domínio e as oito possibilidades de valores binários estão lista- das nas três colunas à esquerda da Tabela 4–7. Os valores binários que tornam os termos- soma na expressão iguais a 0 são A + B + C: 000; Para cada um desses valores binários, coloque um 0 na coluna de saída conforme mostra a tabela. Para cada uma das combinações binárias restantes, coloque um 1 na coluna de saída. A + B + C: 101 e A + B + C: 110. A + B + C: 010; A + B + C: 011; (A + B + C)( A + B + C)( A + B + C)( A + B + C)( A + B + C) 224 ■ SISTEMAS DIGITAIS Determinação de Expressões Padrão a partir de uma Tabela-Verdade Para determinar a expressão de soma-de-produtos padrão representada por uma tabela-verdade, faça uma lista dos valores binários das variáveis de entrada para os quais a saída seja 1. Converta cada valor binário para o termo-produto correspondente substituindo cada 1 pela variável corres- pondente e cada 0 pelo complemento da variável correspondente. Por exemplo, o valor binário 1010 é convertido para o termo-produto mostrado a seguir: Se substituirmos os valores, veremos que o termo-produto é 1: Para determinar a expressão de produto-de-somas representado pela tabela-verdade, liste os valo- res binários para os quais a saída é 0. Converta cada valor binário para o correspondente termo-so- ma substituindo cada 1 pelo complemento da variável correspondente e cada 0 pela variável cor- respondente. Por exemplo, o valor binário 1001 é convertido num termo-soma como mostrado a seguir: Se substituirmos os valores, veremos que o termo-soma é 0. A + B + C + D = 1 + 0 + 0 + 1 = 0 + 0 + 0 + 0 = 0 1001 A + B + C + D ABCD = 1 �0�1 �0 = 1 �1 �1 �1 = 1 1010 ABCD Observe que a tabela-verdade nesse exemplo é a mesma que para o Exemplo 4–18. Isso significa que a expressão de soma-de-produtos no exemplo anterior e a expressão de pro- duto-de-somas nesse exemplo são equivalentes. Problema relacionado Desenvolva a tabela-verdade para a seguinte expressão de produto-de-somas padrão: (A + B + C)( A + B + C)( A + B + C) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1 (A + B + C) (A + B + C) (A + B + C) (A + B + C) (A + B + C) XA B C ENTRADAS SAÍDA TERMO-SOMA EXEMPLO 4–20 A partir da tabela-verdade na Tabela 4–8, determine a expressão de soma-de-produtos padrão e a expressão equivalente de produto-de-somas padrão. ᭤ TABELA 4–7 CAPÍTULO 4 • ÁLGEBRA BOOLEANA E SIMPLIFICAÇÃO LÓGICA ■ 225 Solução Existem quatro 1s na coluna de saída e os valores binários correspondentes são 011, 110 e 111. Converta esses valores binários para termos-produto como mostrado a seguir: A expressão de soma-de-produtos padrão resultante para a saída X é Para a expressão de produto-de-somas, a saída é 0 para os valores binários 000, 001, 010 e 101. Converta esses valores binários para termos-soma como mostrado a seguir: A expressão de produto-de-somas padrão resultante para a saída X é Problema relacionado Através da substituição dos valores binários, mostre que as expressões de soma-de-pro- dutos e de produto-de-somas obtidas nesse exemplo são equivalentes; ou seja, para qual- quer valor binário ambas devem ser 1 ou 0. X = (A + B + C)( A + B + C)( A + B + C)( A + B + C) 000 A + B + C 001 A + B + C 010 A + B + C 101 A + B + C X = ABC + AB C + ABC + ABC 011 ABC 100 AB C 110 ABC 111 ABC 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 1 A B C X ENTRADAS SAÍDA ᭤ TABELA 4–8 SEÇÃO 4–7 REVISÃO 1. Se uma certa expressão Booleana tem um domínio de cinco variáveis, quantos valores binários terão a tabela-verdade? 2. Numa certa tabela-verdade, a saída é 1 para o valor binário 0110. Converta esse valor binário para o termo-produto correspondente usando as variáveis W, X, Y e Z. 3. Numa certa tabela-verdade, a saída é 0 para o valor binário 1100. Converta esse valor binário para o termo-soma correspondente usando as variáveis W, X, Y e Z. 226 ■ SISTEMAS DIGITAIS Um mapa de Karnaugh é similar a uma tabela-verdade porque todos os valores possíveis das va- riáveis de entrada e a saída resultante para cada valor estão presentes no mapa. Em vez de estar or- ganizado em colunas e linhas como uma tabela-verdade, o mapa de Karnaugh é um arranjo de cé- lulas no qual cada célula representa um valor binário das variáveis de entrada. As células são ar- ranjadas de forma que a simplificação de uma dada expressão é obtida simplesmente fazendo um agrupamento adequado de células. Os mapas de Karnaugh podem ser usados para expressões com duas, três, quatro e cinco variáveis, porém discutiremos apenas as situações de 3 e 4 variáveis pa- ra ilustrar os princípios. A Seção 4–11 apresenta o caso de 5 variáveis usando um mapa de Kar- naugh de 32 células. Um outro método, que está além do escopo desse livro, denominado de mé- todo Quine-McClusky pode ser usado para um número maior de variáveis. O número de células num mapa de Karnaugh é igual ao número total de combinações possí- veis das variáveis de entrada que é igual ao número de linhas na tabela-verdade. Para o caso de três variáveis, o número de células é 23 = 8. Para quatro variáveis, o número de células é 24 = 16. O Mapa de Karnaugh de 3 Variáveis O mapa de Karnaugh de 3 variáveis é um arranjo de oito células, conforme mostra a Figura 4–21(a). Nesse caso, A, B e C são usadas como variáveis embora outras letras poderiam ser usa- das. Os valores binários de A e B estão ao longo do lado esquerdo (observe a seqüência) e os va- lores de C estão na parte superior. O valor de uma dada célula corresponde aos valores binários de A e B à esquerda na mesma linha combinados com o valor de C na parte superior na mesma colu- na. Por exemplo, a célula no canto superior esquerdo tem um valor binário de 000 e a célula no canto inferior direito tem um valor binário de 101. A Figura 4–21(b) mostra os termos-produto pa- drão que são representados por cada célula do mapa de Karnaugh. O Mapa de Karnaugh de 4 Variáveis O mapa de Karnaugh de 4 variáveis é um arranjo de dezesseis células, conforme mostra a Figura 4–22(a). Os valores binários de A e B estão ao longo do lado esquerdo e os valores de C e D estão 0 1 00 01 11 10 0 1 00 01 11 10 AB C AB C ABC ABC ABC ABC ABC ABC ABC ABC 4-8 O MAPA DEKARNAUGH Um mapa de Karnaugh provê um método sistemático para simplificação de expressões Boolea- nas e, se usado adequadamente, produz a expressão de soma-de-produtos ou de produto-de-so- mas mais simples possível, conhecida como expressão mínima. Conforme já vimos, a efetivida- de da simplificação algébrica depende da nossa familiaridade com todas as leis, regras e teore- mas da álgebra Booleana e da habilidade de cada um em aplicá-las. Por outro lado, o mapa de Karnaugh provê um método tipo “livro de receitas” para simplificação. Ao final do estudo desta seção você deverá ser capaz de: ■ Construir um mapa de Karnaugh para três ou quatro variáveis ■ Determinar o valor binário de cada célula num mapa de Karnaugh ■ Determinar o termo-produto padrão representado por cada célula num mapa de Karnaugh ■ Explicar a adjacência de células e identificar células adjacentes A finalidade do mapa de Karnaugh é simplificar uma expressão Booleana. ᭤ FIGURA 4–21 Um mapa de Karnaugh de 3 variáveis mos- trando os termos-produto. CAPÍTULO 4 • ÁLGEBRA BOOLEANA E SIMPLIFICAÇÃO LÓGICA ■ 227 na parte superior. O valor de uma dada célula corresponde aos valores binários de A e B à esquer- da na mesma linha combinados com os valores binários de C e D na parte superior na mesma co- luna. Por exemplo, a célula no canto superior direito tem um valor binário de 0010 e a célula no canto inferior direito tem um valor binário de 1010. A Figura 4–22(b) mostra os termos-produto padrão que são representados por cada célula no mapa de Karnaugh de 4 variáveis. Célula Adjacente As células num mapa de Karnaugh são arranjadas de forma que exista apenas uma mudança sim- ples de variável entre células adjacentes. A adjacência é definida por uma mudança simples de va- riável. Num mapa de 3 variáveis a célula 010 é adjacente à célula 000, à célula 011 e à célula 110. A célula 010 não é adjacente à célula 001, nem à célula 111, nem à célula 100 ou à célula 101. Fisicamente, cada célula é adjacente a células que estão imediatamente próximas a ela por qualquer um dos seus quatro lados. Uma célula não é adjacente às células que tocam diagonalmen- te qualquer um dos vértices. Além disso, as células na linha superior são adjacentes às células cor- respondentes na linha inferior e as células na coluna mais à esquerda são adjacentes à células cor- respondentes na coluna mais à direita. Isso é denominado de adjacência cilíndrica porque podemos pensar no mapa enrolado de cima para baixo formando um cilindro ou da esquerda para a direita formando um cilindro. A Figura 4–23 ilustra a adjacência de células com um mapa de 4 variáveis, embora as mesmas regras se aplicam a mapas de Karnaugh com qualquer número de células. 00 01 00 01 11 10 (a) AB CD 11 10 00 01 00 01 11 10 (b) AB CD 11 10 ABCD ABCD ABCD ABCD ABCD ABCD ABCD ABCD ABCD ABCD ABCD ABCD ABCD ABCD ABCD ABCD ᭣ FIGURA 4–22 Um mapa de Karnaugh de 4 va- riáveis. Células que diferem em apenas uma variável são ad- jacentes. Células com valores que di- ferem em mais de uma va- riável não são adjacentes. 00 01 11 10 00 01 11 10 CD AB ᭣ FIGURA 4–23 Células adjacentes num mapa de Karnaugh são aquelas que dife- rem uma da outra em apenas uma variável. As setas indicam as células adjacentes. SEÇÃO 4–8 REVISÃO 1. Num mapa de Karnaugh de 3 variáveis, qual é o valor binário para cada célula nas seguintes localizações: (a) canto superior esquerdo (b) canto inferior direito (c) canto inferior esquerdo (d) canto superior direito 2. Qual é o termo-produto padrão para cada célula na Questão 1 para as variáveis X, Y e Z? 3. Repita a Questão 1 para um mapa de 4 variáveis. 4. Repita a Questão 2 para um mapa de 4 variáveis usando as variáveis W, X, Y e Z. 228 ■ SISTEMAS DIGITAIS Mapeando uma Expressão Padrão de soma-de-produtos Para uma expressão na forma de soma-de-produtos padrão, um 1 é colocado no mapa de Kar- naugh para cada termo-produto na expressão. Cada 1 é colocado na célula correspondente ao va- lor de um termo-produto. Por exemplo, para o termo-produto um 1 é colocado na célula 101 num mapa de 3 variáveis. Quando uma expressão de soma-de-produtos é completamente inserida no mapa, existirá um número de 1s no mapa de Karnaugh igual ao número de termos-produto na expressão de soma-de- produtos padrão. As células que não possuem um 1 são as células para as quais a expressão é 0. Geralmente, quando trabalhamos com expressões de soma-de-produtos, os 0s são deixados fora do mapa. Os passos a seguir e a ilustração mostrada na Figura 4–24 apresentam o processo de in- serção da expressão no mapa. Passo 1 Determine o valor binário de cada termo-produto na expressão de soma-de-produtos. Após adquirir alguma prática, podemos geralmente fazer a avaliação dos termos men- talmente. Passo 2 À medida que cada termo-produto é avaliado, coloque um 1 no mapa de Karnaugh na célula que tem o mesmo valor que o termo-produto. ABC, 4-9 MINIMIZAÇÃO DE SOMA-DE-PRODUTOS USANDO O MAPA DE KARNAUGH Conforme dito na seção anterior, o mapa de Karnaugh é usado para simplificação de expressões Booleanas para a forma mínima. Uma expressão de soma-de-produtos minimizada contém a me- nor quantidade possível de termos com a menor quantidade possível de variáveis por termo. Ge- ralmente uma expressão de soma-de-produtos mínima pode ser implementada com menos por- tas lógicas que uma expressão padrão. Ao final do estudo desta seção você deverá ser capaz de: ■ Inserir no mapa uma expressão de soma-de-produtos padrão ■ Agrupar os 1s no mapa em grupos de tamanho máximo ■ Determinar o termo-produto mínimo para cada grupo no mapa ■ Combinar os termos-produto mínimo para formar uma expressão de soma-de-produtos míni- ma ■ Converter uma tabela verdade num mapa de Karnaugh para simplificação da expressão representada ■ Usar condições “don’t care” no mapa de Karnaugh 0 1 00 01 11 10 AB C ABC + ABC + ABC + ABC 1 1 1 1 000 001 110 100 ᭤ FIGURA 4–24 Exemplo de inserção de uma expressão de soma-de-produtos no mapa. EXEMPLO 4–21 Coloque no mapa de Karnaugh a seguinte expressão de soma-de-produtos: Solução Avalie a expressão conforme mostrado a seguir. Coloque um 1 no mapa de Karnaugh de 3 variáveis, visto na Figura 4–25, para cada termo-produto padrão da expressão. A BC + ABC + ABC + ABC 0 0 1 0 1 0 1 1 0 1 1 1 A BC + ABC + ABC + ABC CAPÍTULO 4 • ÁLGEBRA BOOLEANA E SIMPLIFICAÇÃO LÓGICA ■ 229 EXEMPLO 4–22 Coloque a seguinte expressão de soma-de-produtos num mapa de Karnaugh: Solução Avalie a expressão conforme mostrado abaixo. Coloque um 1 no mapa de Karnaugh de 4 variáveis, visto na Figura 4–26, para cada termo-produto padrão da expressão. Problema relacionado Coloque num mapa de Karnaugh a seguinte expressão de soma-de-produtos padrão: ABCD + ABCD + ABC D + ABCD A BCD + ABC D + ABCD + ABCD + ABC D + A B CD + ABCD 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 0 1 0 A BCD + ABC D + ABCD + ABCD + ABC D + A B CD + ABCD Mapeando uma Expressão Não Padrão de Soma-de-Produtos Uma expressão Booleana tem que estar primeiro na forma padrão antes de usarmos o mapa de Karnaugh. Se uma expressão não estiver na forma padrão, então ela deve ser convertida para a for- ma padrão usando o procedimento abordado na Seção 4–6 ou através de expansão numérica. Co- mo uma expressão deve ser avaliada antes de colocar no mapa, a expansão numérica é provavel- mente a forma mais eficiente. Expansão Numérica de um Termo-Produto Lembre que um termo-produto não padrão tem uma ou mais variáveis que não aparecem. Por exemplo, considere que um dos termos-produto nu- Problema relacionado Coloque num mapa de Karnaugh a expressão de soma-de-produtos .ABC + ABC + AB C 0 1 00 01 11 10 AB C 1 1 11 ABC ABC ABC ABC᭤ FIGURA 4–25 00 01 11 10 00 01 11 10 CD AB 1 1 1 1 1 1 1 ABCD ABCD ABCDABCD ABCD ABCD ABCD ᭤ FIGURA 4–26 230 ■ SISTEMAS DIGITAIS EXEMPLO 4–23 Insira no mapa de Karnaugh a seguinte expressão de soma-de-produtos: Solução A expressão de soma-de-produtos não está obviamente na forma padrão porque cada ter- mo-produto não possui as três variáveis. No primeiro termo não aparecem duas variáveis e no segundo termo não aparece uma variável. Já o terceiro termo está na forma padrão. Primeiro faça a expansão numérica dos termos como mostrado a seguir: Preencha o mapa com os valores binários resultantes colocando um 1 na célula apropria- da do mapa de Karnaugh de 3 variáveis mostrado na Figura 4–27. Problema relacionado Insira no mapa de Karnaugh a expressão de soma-de-produtos .BC + A C A AB ABC 000 100 110 001 101 010 011 A + AB + ABC. ma certa expressão de soma-de-produtos de 3 variáveis seja Esse termo pode ser expandido numericamente para a forma padrão conforme explicado a seguir. Primeiro, escreva o valor biná- rio das duas variáveis e acrescente um 0 para a variável que não aparece Em seguida, es- creva o valor binário das duas variáveis e acrescente um 1 para a variável C: 100 que não aparece. Os dois números binários resultantes são os valores dos termos da soma-de-produtos padrão Como um outro exemplo, considere que um dos termos-produto na expressão de 3 variáveis seja B (lembre que uma única variável conta como um termo-produto numa expressão de soma- de-produtos). Esse termo pode ser expandido numericamente para a forma padrão como mostra- do a seguir. Escreva o valor binário da variável: então acrescente todos os valores possíveis para as variáveis A e C que não aparecem como mostrado a seguir: Os quatro números binários resultantes são os valores dos termos e ABC da soma-de-produtos padrão. ABC, ABC, ABC B 010 011 110 111 AB C e ABC. C: 100. AB. 0 1 00 01 11 10 AB C 1 1 11 1 11 ᭤ FIGURA 4–27 CAPÍTULO 4 • ÁLGEBRA BOOLEANA E SIMPLIFICAÇÃO LÓGICA ■ 231 EXEMPLO 4–24 Insira no mapa de Karnaugh a seguinte expressão de soma-de-produtos: Solução A expressão de soma-de-produtos não está obviamente na forma padrão porque cada ter- mo-produto não tem as quatro variáveis. No primeiro e segundo termos não aparecem duas variáveis e os termos restantes já estão na forma padrão. Primeiro faça a expansão numéricas dos termos incluindo todas as combinações das variáveis que não aparecem como mostrado a seguir: Preencha o mapa com os valores binários resultantes colocando um 1 na célula apropria- da do mapa de Karnaugh de 4 variáveis mostrado na Figura 4–28. Observe que alguns dos valores na expressão expandida são redundantes. Problema relacionado Insira no mapa de Karnaugh a expressão .A + CD + ACD + ABCD B C + AB + ABC + ABCD + A B CD + ABCD Simplificação via Mapa de Karnaugh de Expressões de soma-de-produtos O processo que resulta numa expressão que contém o menor número de termos possível com o menor número de variáveis possível é denominado de minimização. Após a expressão de soma- de-produtos ser inserida no mapa, uma expressão de soma-de-produtos mínima é obtida agrupan- do os 1s e determinando a expressão de soma-de-produtos mínima a partir do mapa. Agrupando os 1s Podemos fazer grupos de 1s no mapa de Karnaugh de acordo com as regras apresentadas em seguida, enlaçando aquelas células adjacentes que contêm 1s. A meta é maximi- zar o tamanho dos grupos e minimizar o número de grupos. 1. Um grupo tem que conter 1, 2, 4, 8 ou 16 células, cujos números são potências inteiras de 2. No caso de um mapa de 3 variáveis, 23 = 8 células é o grupo máximo. 2. Cada célula num grupo tem que ser adjacente a uma ou mais células do mesmo grupo, po- rém todas as células não têm que ser adjacentes uma da outra. 3. Sempre inclua o maior número de 1s num grupo de acordo com a regra 1. B C AB + ABC + ABCD + A B CD + ABCD 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 0 0 1 1 0 1 1 0 0 0 1 1 0 0 1 1 1 0 1 1 0 0 0 1 0 1 0 1 0 0 1 1 0 1 1 00 01 11 10 00 01 11 10 CD AB 1 1 11 1 111 ᭤ FIGURA 4–28 232 ■ SISTEMAS DIGITAIS 4. Cada 1 no mapa tem que ser incluído em pelo menos um grupo. Os 1s que já fazem parte de um grupo podem ser incluídos num outro grupo enquanto os grupos sobrepostos incluem 1s não comuns. EXEMPLO 4–25 Agrupe os 1s em cada um dos mapas de Karnaugh mostrados na Figura 4–29. Solução Os agrupamentos são mostrados na Figura 4–30. Em alguns casos, existem mais de uma forma de agrupar os 1s para formar agrupamentos máximos. Problema relacionado Determine, caso existam, outras formas de agrupar os 1s nos mapas da Figura 4–30 para obter um número mínimo de grupos máximos. 0 1 00 01 11 10 AB C 00 01 11 10 00 01 11 10 CD AB 1 1 11 1 111 (a) 0 1 00 01 11 10 AB C 1 1 1 1 11 (b) (c) 00 01 11 10 00 01 11 10 CD AB (d ) 1 1 1 1 1 1 11 1 11 1 1 1 1 ᭡ FIGURA 4–29 CD AB (d ) 00 01 11 10 00 01 11 10 1 1 1 1 1 1 1 1 1 1 1 Adjacência cilíndricaAdjacência cilíndrica 00 01 11 10 00 01 11 10 CD AB (c) 1 1 1 1 1 1 1 1 00 01 11 10 AB C (b ) 0 1 1 1 1 1 1 1 0 1 00 01 11 10 AB C (a) 1 1 1 1 ᭡ FIGURA 4–30 Determinação da Expressão de soma-de-produtos Mínima a partir do Mapa Quando to- dos os 1s que representam termos-produto padrão estão adequadamente inseridos no mapa e agru- pados, começa o processo de determinação da expressão de soma-de-produtos mínima resultante. As regras a seguir são aplicadas para determinar os termos-produto mínimos e a expressão de so- ma-de-produtos mínima: 1. Agrupe as células que têm 1s. Cada grupo de células que contém 1s cria um termo-produto composto de todas as variáveis que ocorrem num formato apenas (não complementada ou CAPÍTULO 4 • ÁLGEBRA BOOLEANA E SIMPLIFICAÇÃO LÓGICA ■ 233 complementada) dentro do grupo. Variáveis que ocorrem tanto de forma complementada quanto não complementada dentro do grupo são eliminadas. Essas são denominadas de va- riáveis contraditórias. 2. Determine o termo-produto mínimo para cada grupo. a. Para um mapa de 3 variáveis: (1) Um grupo de 1 célula resulta num termo-produto de 3 variáveis (2) Um grupo de 2 células resulta num termo-produto de 2 variáveis (3) Um grupo de 4 células resulta num termo-produto de 1 variáveis (4) Um grupo de 8 células resulta num valor 1 para a expressão b. Para um mapa de 4 variáveis: (1) Um grupo de 1 célula resulta num termo-produto de 4 variáveis (2) Um grupo de 2 células resulta num termo-produto de 3 variáveis (3) Um grupo de 4 células resulta num termo-produto de 2 variáveis (4) Um grupo de 8 células resulta num termo de 1 variável (5) Um grupo de 16 células resulta numa expressão de valor 1 3. Quando se obtém todos os termos-produto mínimos a partir do mapa de Karnaugh, eles são somados para formar a expressão de soma-de-produtos mínima. EXEMPLO 4–26 Determine os termos-produto para o mapa de Karnaugh visto na Figura 4–31 e escreva a expressão de soma-de-produtos mínima. Solução Elimine as variáveis de um grupo que estão na forma complementada e não complemen- tada. Na Figura 4–31, o termo-produto para o grupo de 8 células é B porque as células dentro desse grupo contêm tanto A quanto , tanto C quanto e tanto D quanto , as quais são eliminadas. O grupo de 4 células contém, , sobrando as quais formam o termo-produto . O grupo de 2 células contém sobrando as va- riáveis ,
Compartilhar