Detalhes

Categoria: Art of Assembly

Atualização: Quarta, 24 Fevereiro 2010 20:57

Autor: vovó Vicki

Acessos: 11575

Uma vez que existe um número finito de funções booleanas para n variáveis de entrada, mas é possível construir um número infinito de expressões com estes n valores de entrada, fica claro que existem infinitas expressões lógicas equivalentes (isto é, que produzem o mesmo resultado quando recebem as mesmas entradas).

Para ajudar a eliminar possíveis confusões, os projetistas da lógica geralmente especificam uma função booleana usando a forma canônica ou padrão. Para cada uma das funções booleanas dadas existe uma única forma canônica. Isto elimina confusões que possam ocorrer quando se lida com funções booleanas. Na verdade existem várias formas canônicas diferentes. Discutiremos apenas duas e empregaremos apenas a primeira.

A primeira é chamada de soma de mintermos e a segunda é o produto de maxtermos. Usando o princípio da dualidade, é muito fácil fazer a conversão entre estas duas formas. Um termo é uma variável ou o produto (AND lógico) de várias literais diferentes. Por exemplo, se há duas variáveis, A e B, então existem oito termos possíveis: A, B, A', B', A'B', A'B, AB' e AB. Para três variáveis tem-se 26 termos diferentes: A, B, C, A', B', C', A'B', A'B, AB', AB, A'C', A'C, AC', AC, B'C', B'C, BC', BC, A'B'C', AB'C', A'BC', ABC', A'B'C, AB'C, A'BC e ABC. Percebe-se que, na medida em que o número de variáveis aumenta, o número de termos aumenta drasticamente. Um mintermo é um produto contendo exatamente n literais. Por exemplo, os mintermos de duas variáveis são A'B', AB', A'B e AB. Da mesma forma, os mintermos para três variáveis são A'B'C', AB'C', A'BC', ABC', A'B'C, AB'C, A'BC e ABC. Em geral existem 2ⁿ mintermos para n variáveis. O conjunto de mintermos possíveis pode ser gerado com facilidade porque os mintermos correspondem à sequência dos números binários.

Podemos especificar qualquer função booleana usando a soma (OR lógico) de mintermos. Dada a função F248 = AB + C, a forma canônica equivalente é ABC + A'BC + AB'C + A'B'C + ABC'. Podemos mostrar algebricamente que estas duas formas são equivalentes:

ABC + A'BC + AB'C + A'B'C + ABC'=
BC(A + A') + B'C(A + A') + ABC'=
BC1 + B'C1 + ABC' =
C(B + B') + ABC' =
C + ABC' =
C + AB

Obviamente a forma canônica não é uma forma ótima. Por outro lado, uma grande vantagem da soma de mintermos da forma canônica é que fica muito fácil gerar a tabela lógica para a função. Além disto, também fica muito fácil gerar a equação lógica a partir da tabela lógica. Para construir a tabela lógica a partir da forma canônica basta transformar cada mintermo num valor binário substituindo as variáveis plicadas por 0 e as não plicadas por 1. Depois, é só colocar um 1 na posição correspondente (especificada pelo valor binário do mintermo) na tabela lógica. Valores sem correspondência recebem o valor 0 na tabela lógica. Vamos inicialmente converter os mintermos da função F248 para valores binários:

Mintermos       CBA + CBA' + CB'A + CB'A' + C'BA
Valor binário   111   110    101    100     011

Agora é só localizar os valores binários dos mintermos na tabela lógica e atribuir-lhes o valor 1. Valores sem correspondência recebem o valor 0:

O caminho inverso, ou seja, criar uma função lógica a partir de uma tabela lógica, também é fácil. Inicialmente precisamos localizar todas as entradas da tabela que contenham 1. Na tabela acima existem cinco destas entradas. O número das entradas contendo 1 determina o número de mintermos da equação canônica. Para criar cada um dos mintermos, basta substituir os 1s por A, B ou C e os 0s por A', B' ou C'. Depois é preciso calcular a soma destes itens. No exemplo acima, F248 contém 1 para CBA = 111, 110, 101, 100 e 011. Portanto, F248 = CBA + CBA' + CB'A + CB'A' + C'BA. O primeiro termo, CBA, corresponde à última entrada da tabela. Como as operações lógicas OR e AND são comutativas, podemos rearranjar os termos dos mintermos (CBA = ABC = ACB, etc) além de rearranjar os mintermos na soma (CBA + CBA'... = CBA' + CBA...).

Este processo funciona igualmente bem para qualquer número de variáveis. Considere a função F53504 = ABCD + A'BCD + A'B'CD + A'B'C'D. Colocando 1 nas posições apropriadas da tabela lógica obtemos o seguinte:

Talvez o jeito mais fácil de gerar a forma canônica de uma função booleana seja criar primeiro a tabela lógica desta função e depois gerar a forma canônica da tabela. Usaremos esta técnica, por exemplo, quando fizermos a conversão das duas formas canônicas deste capítulo. Entretanto, calcular a soma dos mintermos algebricamente também é uma coisa simples. O uso da lei distributiva e do teorema 15 (A + A' = 1) facilitam a tarefa. Considere a F248 = AB + C. Esta função possui dois termos, AB e C, mas que não são mintermos. Os mintermos representam cada uma das variáveis possíveis na forma plicada ou não plicada. Podemos converter o primeiro termo para uma soma de mintermos da seguinte maneira:

AB      =       AB x 1           pelo T4
        =       AB x (C + C')    pelo T15
        =       ABC + ABC'       pela lei distributiva
        =       CBA + C'BA       pela lei associativa

Da mesma forma podemos converter o segundo termo da F248 para uma soma de mintermos:

C  =  C x 1				pelo T4
   =  C x (A + A')			pelo T15
   =  CA + CA'				pela lei distributiva
   =  CA1 + CA'1			pelo T4
   =  CA x (B + B') + CA'  (B + B')	pelo T15
   =  CAB + CAB' + CA'B + CA'B'		pela lei distributiva
   =  CBA + CBA' + CB'A + CB'A'		pela lei associativa

A última etapa destas duas conversões, a de rearranjar os termos, é opcional. Para obter a forma canônica final da F248 precisamos apenas somar os resultados destas duas conversões:

F248    = (CBA + C'BA) + (CBA + CBA' + CB'A + CB'A')
        = CBA + CBA' + CB'A + CB'A' + C'BA

Outro modo de criar a forma canônica é através dos produtos de maxtermos. Um maxtermo é a soma (OR lógico) de todas as variáveis de entrada, plicadas ou não plicadas. Por exemplo, considere a seguinte função lógica G de três variáveis:

G = (A + B + C) x (A' + B + C) x (A + B' + C)

Assim como na soma de mintermos, existe um produto de maxtermos para cada uma das funções lógicas possíveis. Deste modo, para cada produto de maxtermos existe uma soma de mintermos equivalente. Na verdade, a função G é equivalente a:

F248 = CBA + CBA' + CB'A + CB'A' + C'BA = AB + C

Criar a tabela lógica do produto dos maxtermos não é mais difícil do que criá-la a partir da soma dos mintermos. Para isto, usa-se o princípio da dualidade. Lembre-se, o princípio da dualidade diz para trocar AND por OR e zeros por uns (e vice versa). Portanto, para fazer a tabela lógica, precisamos primeiro intercambiar as literais plicadas e não plicadas. Na função G isto seria:

G = (A' + B' + C') x (A + B' + C') x (A' + B + C')

O próximo passo é intercambiar os operadores lógicos OR e AND. Isto produz:

G = A'B'C' + AB'C' + A'BC'

Finalmente, é preciso intercambiar todos os zeros e uns. Isto significa que, nos itens da tabela lógica que correspondem aos termos, devem ser colocados 0 e, nos restantes, 1. As linhas com 000, 001 e 010 devem conter 0, as restantes devem conter 1. Observe que é a mesma tabela lógica da função F248.

A conversão destas duas formas canônicas pode ser feita com facilidade criando-se a tabela lógica para uma delas e, a partir desta tabela, gerando-se a outra forma. Por exemplo, considere a função com duas variáveis F7 = A + B. A soma da forma de mintermos é F7 = A'B + AB' + AB. A tabela lógica é a seguinte:

Trabalhando ao contrário para obter o produto dos maxtermos, localizamos todas as linhas que tenham resultado 0. Esta é apenas a entrada onde A e B são 0. Isto nos dá o primeiro passo, onde G = A'B'. Agora é preciso inverter as variáveis, o que nos dá G = AB. Pelo princípio da dualidade, invertemos os operadores lógicos OR e AND, obtendo G = A + B. Esta é a forma canônica do produto dos maxtermos.

Trabalhar com produtos de maxtermos é um pouco mais atrapalhado do que com somas de mintermos, por isto os textos deste tutorial geralmente farão uso da soma de mintermos. Além disso, a soma de mintermos é mais utilizada em trabalhos sobre lógica booleana.

Fonte

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