Detalhes

Categoria: Art of Assembly

Atualização: Domingo, 19 Abril 2009 13:08

Autor: vovó Vicki

Acessos: 12570

Como existe uma variedade infinita de funções booleanas com n variáveis mas apenas um número finito de funções booleanas únicas para estas n variáveis, você deve estar se perguntado se existe algum método para simplificar uma dada função booleana para obter a forma ótima.

É claro que as transformações algébricas sempre podem ser usadas, mas o uso da heurística nem sempre garante uma transformação ótima. No entanto, existem dois métodos que reduzirão uma dada função booleana à sua forma ótima: o método de diagramas e o método das plicas. Neste texto abordaremos apenas o método de diagramas ou mapeamento

Já que para qualquer função lógica deve existir alguma forma ótima, você poderia ser perguntar por que não utilizamos a forma ótima para a forma canônica. Há duas razões. Primeiro, há muitas formas ótimas. Não há garantia de que sejam únicas. Segundo, é fácil fazer uma conversão entre a forma canônica e a tabela lógica (ou tabela verdade).

Utilizar o método de mapeamento para otimizar funções booleanas é prático apenas para funções de duas, três ou quatro variáveis. Com cuidado, você pode utilizá-lo para funções de cinco ou seis variáveis, mas o método de mapeamento é incômodo a partir deste ponto. Para mais do que seis variáveis, não é aconselhável tentar fazer simplificações a mão através de mapeamentos.

O primeiro passo para a utilização do método de mapeamento é construir uma tabela verdade de duas dimensões para a função:

Alerta: dê uma boa olhada nessas tabelas lógicas. Elas não têm o mesmo formato das que você viu anteriormente neste capítulo. Uma particularidade é que a progressão dos valores é 00, 01, 11, 10 e não 00, 01, 10, 11. Isto é muito importante! Se você organizar as tabelas verdade na sequência binária, o método de otimização por mapeamento não funcionará corretamente. Chamaremos estes de mapas verdade para distingui-los das tabelas verdade padrão.

Assumindo que a função booleana esteja na forma canônica (soma de mintermos), insira uns para cada uma das entradas do mapa verdade correspondentes ao mintermo da função. Coloque zeros em todo o resto. Por exemplo, considere a função de três variáveis F = C'B'A + C'BA' + C'BA + CB'A' + CB'A + CBA' + CBA. A figura abaixo mostra o mapa verdade para esta função.

O próximo passo é desenhar retângulos em volta de grupos retangulares de 1. Os retângulos que você incluir devem ter lados cujos tamanhos sejam potências de dois. Para funções de três variáveis, os retângulos podem ter lados cujos tamanhos sejam um, dois ou quatro. O conjunto de retângulos desenhados deve cercar todas as células contendo 1 no mapa verdade. O truque é desenhar todos os retângulos possíveis, a menos que um retângulo possa ser completamente englobado por outro. Note que os retângulos podem ser sobrepostos se um não contiver o outro. No mapa verdade ao lado há três retângulos nessa condição.

Cada retângulo representa um termo da função booleana simplificada. Isto significa que a função booleana simplificada terá apenas três termos. Cria-se cada um dos termos utilizando o processo de eliminação. Elimina-se quaisquer variáveis cujas formas plicadas (negadas) e não plicadas (não negadas) aparecem dentro do retângulo. Considere o retângulo longo e estreito que está situado na linha onde C=1. Este retângulo contém A e B nas formas negada e não negada. Pode-se, então, eliminar A e B do termo. Uma vez que o retângulo se situa na região C=1, este retângulo representa um único literal C.

Agora considere o quadrado destacado pela linha sólida. Este retângulo inclui C, C', B, B' e A. Portanto, ele representa o termo único A. Da mesma forma, o quadrado com a linha pontilhada contém C, C', A, A' e B. Portanto, ele representa o termo simples B.

A função final ótima é a soma (OR lógico) dos termos representados pelos três quadrados, ou seja, F = A + B + C. Não é preciso considerar quadrados que contenham zeros.

Quando se fecha grupos de 1 no mapa verdade, deve-se considerar o fato de que um mapa verdade forma um tórulo, ou saliência arredondada (como uma rosquinha). A margem direita do mapa envolve a margem esquerda (e vice-versa). Da mesma forma, a margem superior envolve a margem inferior. Isto introduz possibilidades adicionais ao se cercar grupos de 1 num mapa. Considere a função booleana F = C'B'A' + C'BA' + CB'A' + CBA'. A figura abaixo mostra o mapa verdade para esta função.

À primeira vista tem-se a impressão de que há dois retângulos possíveis, como mostrado na figura da esquerda.

Entretanto, pelo fato do mapa verdade ser um objeto contínuo, com os lados direito e esquerdo conectados, podemos formar um único retângulo, como mostrado à direita.

E daí? Por que se importar se há um ou dois retângulos no mapa verdade? A resposta é porque, quanto maiores forem os retângulos, mais termos eles eliminarão e quanto menos retângulos existirem, menos termos aparecerão na função booleana final. Por exemplo, o exemplo da esquerda, com dois retângulos, gera uma função com dois termos. O primeiro retângulo, à esquerda, elimina a variável C, deixando A'B' como seu termo. O segundo retângulo, à direita, também elimina a variável C, deixando o termo BA'. Então, este mapa verdade produziria a equação F = A'B' + A'B. Sabemos que esta não é a função ótima, veja o teorema T13. Agora considere o mapa verdade da direita. Possui um único retângulo, portanto, a função booleana terá apenas um único termo. Obviamente esta função é "mais ótima" do que uma equação com dois termos. Já que este retângulo inclui C e C', como também B e B', o único termo que permanece é A'. Então, esta função booleana reduz-se a F = A'.

Há apenas dois casos que o mapa verdade não pode tratar apropriadamente: um mapa verdade que contenha somente zeros e um mapa verdade que contenha somente 1. Esses dois casos correspondem respectivamente às funções booleans F = 0 e F = 1. Essas funções são fáceis de criar através da inspeção do mapa verdade.

Uma coisa importante que se deve ter em mente ao otimizar funções booleanas utilizando o método de mapeamento é que sempre se deve escolher os maiores retângulos cujos tamanhos dos lados sejam uma potência de dois. Isto também deve ser feito para retângulos que se interceptem (a não ser que um retângulo inclua outro). Considere a função booleana F = C'B'A' + C'BA' + CB'A' + C'AB + CBA' + CBA. Ela produz um mapa verdade semelhante ao da esquerda.

A tentação inicial é criar um dos conjuntos de retângulos encontrados na figura abaixo:

Contudo, o mapa correto é o mostrado à esquerda. Todos os três mapas produzirão uma função booleana com dois termos. Entretanto, os dois primeiros produzirão as expressões F = B + A'B' e F = AB + A'. A terceira forma produzirá F = B + A'. Obviamente, esta última forma é melhor do que as duas anteriores (veja os teoremas 11 e 12).

Para funções de três variáveis, o tamanho do retângulo determina o número de termos que ele representa:

• Um retângulo fechando um quadrado simples representa um mintermo. O termo associado terá três literais.
• Um retângulo envolvendo dois quadrados contendo uns representa um termo contendo dois literais.
• Um retângulo envolvendo quatro quadrados contendo uns representa um termo contendo um único literal.
• Um retângulo envolvendo oito quadrados representa a função F = 1.

Os mapas verdade criados para funções de quatro variáveis são sempre enganadores. Isto acontece porque há muitos retângulos válidos que podem estar ocultos perto perto das margens. As figuras abaixo mostram alguns possíveis retângulos válidos que podem estar ocultos.

E esta lista de padrões nem cobre todas as possibilidades! Por exemplo, este diagrama mostra nove dos retângulos 1x2. É preciso ter cuidado quando se trabalha com mapas de quatro variáveis para garantir que os maiores retângulos possíveis sejam selecionados, especialmente quando ocorrerem sobreposições. Isto é particularmente importante quando se tem um retângulo próximo a uma margem do mapa verdade.

Assim como com funções de três variáveis, o tamanho do retângulo num mapa de quatro variáveis controla o número de termos que ele representa:

• Um retângulo fechando um quadrado simples representa um mintermo. O termo associado terá quatro literais.
• Um retângulo envolvendo dois quadrados contendo uns representa um termo contendo três literais.
• Um retângulo envolvendo quatro quadrados contendo uns representa um termo contendo um dois literais.
• Um retângulo envolvendo oito quadrados representa um termo contendo um único literal.
• Um retângulo envolvendo dezesseis quadrados representa a função F = 1.

Este último exemplo demonstra a otimização de uma função que contém quatro variáveis. A função é F = D'C'B'A' + D'C'B'A + D'C'BA + D'C'BA' + D'CB'A + D'CBA + DCB'A + DCBA + DC'B'A' + DC'BA' e o mapa verdade aparece à esquerda. À direita estão dois conjuntos possíveis de retângulos máximos para esta função, cada um produzindo três termos.

As duas funções são equivalentes, ambas são o melhor que se pode obter. Qualquer uma das duas satisfará os nossos propósitos.

Primeiro vamos considerar o termo representado pelo retângulo formado pelos quatro cantos. Este retângulo contém B, B', D e D', portanto, estes termos podem ser eliminados. Os termos restantes, contidos dentro destes retângulos, são C' e A' - portanto, este retângulo representa o termo C'A'.

O segundo retângulo, comum para os dois mapas na figura, é o retângulo formado pelo meio dos quadrados. Este retângulo inclui os termos A, B, B', C, D e D'. Eliminando B, B', D e D' (uma vez que existem tanto os termos negados como os não negados), obtemos CA como termo para este retângulo.

O mapa sobre a esquerda das figuras tem um terceiro termo representado pela linha superior. Este termo inclui as variáveis A, A', B, B', C' e D'. Já que ele contém A, A', B e B', podemos eliminar estes termos. Isto deixa o termo C'D'. Então, a função representada pelo mapa à esquerda é F = C'A' + CA + C'D'.

O mapa da direita tem um terceiro termo representado pelos quatro quadrados centrais superiores. Este retângulo inclui as variáveis A, B, B', C, C' e D'. Podemos eliminar B, B', C e C' uma vez que as versões negadas e não negadas aparecem, o que nos deixa o termo AD. Então, a função representada pela função à direita é F = C'A' + CA + AD'.

Já que as duas expressões são equivalentes, porque contém o mesmo número de termos e o mesmo número de operadores, as formas são igualmente ótimas.

Fonte

• Art of Assembly de Randall Hyde.
• Tradução meio que livre da vovó Vicki.