Detalhes

Categoria: Art of Assembly

Atualização: Sábado, 27 Fevereiro 2010 16:27

Autor: vovó Vicki

Acessos: 6810

Uma função booleana é uma representação matemática abstrata de um procedimento computacional ou de um circuito eletrônico. Um programa e um circuito eletrônico são matematicamente equivalentes. Neste laboratório vamos explorar esta equivalência.

A álgebra booleana é um sistema matemático com dois valores (zero e um) e com três operadores lógicos (AND, OR e NOT). O sistema booleano é fechado em relação a estas três operações, isto é, dados operandos booleanos, estes operadores sempre produzem um resultado booleano. As operações lógicas AND e OR são comutativas, ou seja, os operandos podem trocar de posição que o resultado permanece o mesmo. As operações lógicas AND e OR são associativas, isto é, A AND (B AND C) é igual a (A AND B) AND C. O mesmo vale para o OR lógico. As operações lógicas AND e OR também são distributivas, o que quer dizer que A AND (B OR C) é igual a (A AND B) OR (A AND C). Da mesma forma, A OR (B AND C) é igual a (A OR B) AND (A OR C). O valor 1 é o elemento de identidade em relação ao AND lógico, o valor zero é o elemento de identidade em relação ao OR lógico. Para qualquer valor booleano A existe um outro valor A' que não é igual a A (é o inverso de A). A OR A' é 1 (ou A + A' = 1) e A AND A' é zero (ou A x A' = 0). Estas declarações formam os postulados básicos do sistema algébrico booleano. É possível provar todos os teoremas e fatos do sistema booleano usando este conjunto de postulados.

Q02.01 - Qual é a regra (postulado) que podemos usar para provar que A AND (B AND C) é igual a (A AND B) AND (A AND C)?

Q02.02 - Qual é a regra (postulado) que podemos usar para mostrar que A AND (B AND C) é igual a (A AND B) AND C?

Usando os postulados acima podemos provar com facilidade vários teoremas importantes da álgebra booleana. Os teoremas mais importantes são:

T1: A + A = A          T8: (AB)' = A' + B'
T2: A x A = A          T9: A + AB = A
T3: A + 0 = A          T10: A x (A + B) = A
T4: A x 1 = A          T11: A + A'B = A + B
T5: A x 0 = 0          T12: A' x (A+B') = A'B'
T6: A + 1 = 1          T13: AB + AB' = A
T7: (A+B)' = A'B'      T14 (A' + B') x (A' + B) = A'

Q02.03 - No capítulo 1 você aprendeu que pode usar a operação lógica AND para zerar vários bits numa string de bits. Qual dos teoremas acima descreve esta operação?

Q02.04 - No capítulo 1 você aprendeu que pode usar a operação lógica OR para forçar o valor um em vários bits numa string de bits. Qual dos teoremas acima descreve esta operação?

Uma função booleana, ou expressão, é um conjunto de literais combinadas com os operadores lógicos AND e OR. Uma literal é o valor zero ou 1, ou uma variável plicada (por exemplo, A') ou não plicada (por exemplo, A). A plica (ou linha, como falamos) indica uma negação lógica (NOT). Exemplos de funções booleanas típicas incluem:

F = AB + C          G = A(B + C)          H = A'B'C + ABC'

Dados os valores para A, B e C, podemos calcular os valores das funções acima. Por exemplo, se A=0, B=1 e C=1, então F = 0 x 1 + 1 = 0 + 1 = 1. Da mesma forma, G = 0 x (1 + 1) = 0 x 1 = 0. E, por último, podemos calcular H = 1 x 0 x 1 + 0 x 1 x 0 = 0 + 0 = 0. Entretanto, avaliar funções booleanas desta forma é chato e sujeito a erros. Como é provável que se confunda alguns valores fazendo cálculos mentais, uma solução melhor e mais segura é procurar a resposta numa tabela.

Como existem apenas dois valores booleanos, é possível relacionar todos os valores que uma função booleana possa produzir. Por exemplo, a função F acima usa três variáveis independentes, A, B e C. Dadas n variáveis, cada uma tendo dois valores distintos, há 2ⁿ combinações possíveis dos valores destas variáveis. Portanto, existem oito (2³) combinações possíveis de A, B e C como entradas da função F. Sabendo disto, fica fácil criar uma tabela que mostre todas as entradas possíveis de uma dada função (ou funções) e colocar os resultados desta função na tabela. Uma tabela deste tipo é chamada de tabela verdade.

Para construir uma tabela verdade, comece listando todas as combinações possíveis das variáveis que aparecem na função. As três funções deste exemplo têm três variáveis de entrada. Neste caso, comece listando os oito valores binários de três bits, que vão de 0 a 7.

Por convenção, trataremos a variável A como o bit menos significativo e a variável C como o bit mais significativo do número binário. O próximo passo é calcular os valores para cada função. Para a função F calculamos o seguinte:

F(C,B,A) = AB + C
------------------------
F(0,0,0) = 0 x 0 + 0 = 0
F(0,0,1) = 1 x 0 + 0 = 0
F(0,1,0) = 0 x 1 + 0 = 0
F(0,1,1) = 1 x 1 + 0 = 1
F(1,0,0) = 0 x 0 + 1 = 1
F(1,0,1) = 1 x 0 + 1 = 1
F(1,1,0) = 0 x 1 + 1 = 1
F(1,1,1) = 1 x 1 + 1 = 1

O próximo passo é inserir os valores encontrados na tabela verdade na coluna correspondente. Para a função F os valores são:

Q02.05 - Para a função G, quais são os valores?

Q02.06 - Para a função H, quais são os valores?

Considere a função F = AB + C'D'. Como esta função usa quatro valores de entrada, existem 2⁴ (16) possíveis combinações diferentes das entradas. Listando estes valores obtemos:

J(D, C, B, A) = AB + C'D'
J(0, 0, 0, 0) = 0x0 + 1x1 = 1
J(0, 0, 0, 1) = 0x1 + 1x1 = 1
J(0, 0, 1, 0) = 1x0 + 1x1 = 1
J(0, 0, 1, 1) = 1x1 + 1x1 = 1
J(0, 1, 0, 0) = 0x0 + 1x0 = 0
J(0, 1, 0, 1) = 0x1 + 1x0 = 0
J(0, 1, 1, 0) = 1x0 + 1x0 = 0
J(0, 1, 1, 1) = 1x1 + 1x0 = 1
J(1, 0, 0, 0) = 0x0 + 0x1 = 0
J(1, 0, 0, 1) = 0x1 + 0x1 = 0
J(1, 0, 1, 0) = 1x0 + 0x1 = 0
J(1, 0, 1, 1) = 1x1 + 0x1 = 1
J(1, 1, 0, 0) = 0x0 + 0x0 = 0
J(1, 1, 0, 1) = 0x1 + 0x0 = 0
J(1, 1, 1, 0) = 1x0 + 0x0 = 0
J(1, 1, 1, 1) = 1x1 + 0x0 = 1

Q02.07 - Construa a tabela verdade da função J.

Para funções booleanas complexas, com muitos termos e operações diferentes, é possível escrever um programa simples que gera automaticamente a tabela verdade. O programa LOGICEV é um bom exemplo, você verá adiante.

Não é surpresa nenhuma que as expressões booleanas possam ser manipuladas algebricamente. Usando os teoremas mostrados no tópico A álgebra booleana, podemos transformar uma expressão booleana numa outra expressão equivalente. Existem duas razões para proceder desta forma: para simplificar expressões complexas ou para transformá-las na forma canônica.

Para demonstrar como se usa transformações algébricas para simplificar uma expressão, o exemplo seguinte está ao contrário. Nele, uma equação simples é transformada algebricamente numa equação complexa. O processo de simplificação é apenas o inverso desta mesma sequência de transformações:

F = ab + c                              função original
  = ab*1 + c                            pelo T4
  = ab(c + c') + c                      lei dos inversos (P5)
  = abc + abc' + c                      lei distributiva (P4)
  = abc + abc' + c + 0                  pelo T3
  = abc + abc' + c + bc*0               pelo T5
  = abc + abc' + c + a'bca              lei dos inversos (P5)
  = a(bc + bc' + a'bc) + c              lei distributiva (P4)
  = a(bc + bc' + a'bc) + c*1            pelo T4
  = a(bc + bc' + a'bc) + c(b+b')        lei dos inversos (P5)
  = a(bc + bc' + a'bc) + cb + cb'       lei distributiva

Obviamente podemos continuar o processo e tornar esta expressão cada vez mais complexa. O importante é saber que esta complexidade pode ser reduzida usando os mesmos passos ao contrário. Infelizmente não existe uma algoritmo simples que descreva este procedimento. É uma questão habilidade que depende de experiência e de tentativa e erro. A seguir, vamos tentar simplificar a seguinte equação lógica para o segmento número quatro de um display de sete segmentos:

Tentando otimizar a expressão, o truque é combinar termos que contenham versões plicadas e não plicadas da variável. Na expressão acima, podemos usar a lei distributiva para combinar D'C'B'A' e DC'B'A', obtendo (D+D')C'B'A'. Uma vez que a lei dos inversos diz que D + D' é 1, isto reduz estes dois termos para o termo único C'B'A'. Portanto, uma versão simplificada de S₄ é:

Depois, podemos usar a lei distributiva nos dois últimos termos para reduzí-la para:

Este último passo aumentou o número de termos de três para quatro, mas reduziu o número total de operações necessárias para calcular o resultado da função. A versão anterior precisava de oito operações AND e de duas operações OR, a atual precisa apenas de seis operações AND e de duas operações OR.

Q02.08 - Indique as regras aplicadas em cada uma das etapas da simplificação de S₀ = D'C'B'A' + D'C'BA' + D'C'BA + D'CB'A + D'CBA' + D'CBA + DC'B'A' + DC'B'A.
A primeira etapa resultou em S₀ = D'C'B'A' + D'C'BA' + D'C'BA + D'CB'A + D'CBA' + D'CBA + DC'B'A' + DC'B'A' + DC'B'A.

Q02.09 - S₀ = C'B'A'(D + D') + D'C'BA' + D'C'BA + D'CB'A + D'CBA' + D'CBA + DC'B'A' + DC'B'A

Q02.10 - S₀ = C'B'A' + D'C'BA' + D'C'BA + D'CB'A + D'CBA' + D'CBA + DC'B'A' + DC'B'A

Q02.11 - S₀ = C'B'A' + D'C'BA' + D'C'BA + D'CB'A + D'CBA' + D'CBA + DC'B'(A' + A)

Q02.12 - S₀ = C'B'A' + D'C'BA' + D'C'BA + D'CB'A + D'CBA' + D'CBA + DC'B'

Q02.13 - S₀ = C'B'A' + D'C'B(A' + A) + D'CB'A + D'CBA' + D'CBA + DC'B'

Q02.14 - S₀ = C'B'A' + D'C'B + D'CB'A + D'CBA' + D'CBA + DC'B'

Q02.15 - S₀ = C'B'A' + D'C'B + D'CB'A + D'CB(A' + A) + DC'B'

Q02.16 - S₀ = C'B'A' + D'C'B + D'CB'A + D'CB + DC'B'

Q02.17 - S₀ = C'B'A' + D'C'B + D'CB'A + D'CB + D'CB + DC'B'

Q02.18 - S₀ = C'B'A' + D'B(C' + C) + D'CB'A + D'CB + DC'B'

Q02.19 - S₀ = C'B'A' + D'B + D'CB'A + D'CB + DC'B'

Q02.20 - S₀ = C'B'A' + D'B + D'C(B'A + B) + DC'B'

Q02.21 - S₀ = C'B'A' + D'B + D'C(A + B) + DC'B'

Q02.22 - S₀ = C'B'A' + D'B + D'CA + D'CB + DC'B'

Q02.23 - S₀ = C'B'A' + D'B x 1 + D'CA + D'CB + DC'B'

Q02.24 - S₀ = C'B'A' + D'B(1 + C) + D'CA + DC'B'

Q02.25 - S₀ = C'B'A' + D'B(1) + D'CA + DC'B'

Q02.26 - S₀ = C'B'A' + D'B + D'CA + DC'B'

Q02.27 - S₀ = C'B'(A' + D) + D'B + D'CA

Q02.28 - S₀ = C'B'(A' + D) + D'(B + CA)

Otimizar um circuito geralmente significa reduzir o número de operações ou os termos de uma expressão booleana. Entretanto, este não é sempre o caso. Algumas vezes uma operação de otimização acaba aumentando os termos ou as operações. Imagine um engenheiro que esteja projetando um circuito que precisa calcular A + B. O engenheiro pode usar uma porta OR, como o circuito integrado (CI) 74LS32. Este CI possui quatro portas OR. De forma semelhante, o chip 75LS08 possui quatro portas lógicas AND e o chip 74LS04 possui seis portas inversoras. Agora imagine que o engenheiro tenha um 74LS04 com três inversores não usados, um 78LS08 com uma porta AND livre e nenhuma porta OR disponível no circuito. Para obter a função OR necessária, ele poderia adicionar um 78LS32 no circuito, mas isto aumentaria o custo do mesmo. Se quiser reduzir o custo e o número de componentes (isto é, otimizar o custo ao invés do número de termos ou operações), ele poderia sintetizar a operação OR da seguinte maneira:

ou seja, o engenheiro poderia usar dois inversores para inverter os valores de A e B, depois usar uma porta AND e, finalmente, usar um terceiro inversor para inverter a saída da porta AND.

Q02.29 - Quais são os teoremas que apoiam a igualdade acima, ou seja, que A + B = (A' x B')'?

Quando se otimiza equações lógicas para criar um circuito eletrônico, a simples redução do número de termos e operadores nem sempre é a solução mais efetiva em termos de custo. Por outro lado, quando se implementa uma função lógica no software, a solução ótima provavelmente será aquela que usar o menor número de operações.

Q02.30 - Otimize a função F = AB + A' para minimizar o número de operações.

Como existem infinitas funções booleanas equivalentes, usaremos a forma canônica da soma de mintermos para especificar funções lógicas. Para cada uma das funções lógicas existe uma soma de mintermos única. A soma de mintermos é conveniente porque é fácil criar uma tabela verdade a partir da equação lógica e, além do mais, é fácil construir a equação lógica com soma de mintermos a partir da tabela verdade.

Um mintermo é um termo no qual todas as variáveis de uma expressão booleana estão presentes na forma plicada ou não plicada. Numa função booleana de quatro variáveis o mintermo será composto por quatro literais (lembre-se, um literal é uma variável plicada ou não plicada). Como cada uma das variáveis pode assumir um de dois estados (plicada ou não plicada), existem 2ⁿ possíveis mintermos diferentes para uma função de n variáveis. Isto corresponde ao número de entradas da tabela verdade.

Cada mintermo na forma canônica corresponde a uma entrada de valor 1 na tabela verdade. A soma de mintermos é o OR lógico de todos os mintermos presentes numa tabela verdade (isto é, o "endereço" de cada entrada da tabela que contenha 1). Por exemplo, considere a tabela verdade ao lado. Esta tabela verdade contém uns nas casa endereçadas por C'B'A, C'BA', C'BA, CB'A e CBA'. Estes "endereços correspondem aos mintermos. A soma dos mintermos é o OR lógico destes mintermos, portanto, a função para a tabela verdade acima é C'B'A + C'BA' + C'BA + CB'A + CBA'.

Q02.31 - Qual é a forma canônica (soma de mintermos) da tabela verdade acima?

Q02.32 - Qual é a forma canônica da tabela verdade acima?

Q02.33 - Qual é a forma canônica da tabela verdade acima?

Criar uma tabela verdade a partir de uma forma canônica é tão fácil quanto. Só é preciso preencher todas as entradas da tabela verdade cujos endereços correspondam aos mintermos. A equação F = C'B'A' + C'BA + CBA + CB'A', por exemplo, dá a seguinte tabela verdade:

Q02.34 - Construa a tabela para F = CBA + C'BA' + CBA' + C'BA

Q02.35 - Construa a tabela para F = C'B'A' + C'B'A + C'BA' + C'BA + CBA

Q02.36 - Construa a tabela para F = DC'BA + DC'B'A' + DCBA + D'CBA

Se quisermos simplificar uma expressão booleana para reduzir o número de termos na expressão, existe um método mais fácil do que as transformações algébricas - é o método de otimização por mapeamento. O primeiro passo é criar uma mapa verdade (também conhecido como Diagrama de Veitch ou Mapa de Carnot). Mapas verdade são uma pequena variação das tabelas verdade: a única diferença entre um mapa verdade e uma tabela verdade é a disposição das linhas e colunas. Um mapa verdade para duas variáveis é idêntico a uma tabela verdade para duas variáveis. Um mapa verdade para três variáveis é parecido com uma tabela verdade para três variáveis - apenas as duas últimas colunas são trocadas. Um mapa verdade para quatro variáveis é parecido com uma tabela verdade para quatro variáveis - são trocadas apenas as duas últimas colunas e as duas últimas linhas.

Para a função booleana F = C'B'A' + C'BA + CBA + CB'A' o mapa verdade de três variáveis é:

Q02.37 - Construa o mapa verdade para a função F = CBA + C'BA' + CBA' + C'BA

Q02.38 - Construa o mapa verdade para a função F = C'B'A' + C'B'A + C'BA' + C'BA + CBA

Q02.39 - Construa o mapa verdade para F= DC'BA + DC'B'A' + DCBA + D'CBA

Depois de construir um mapa verdade, o próximo passo é identificar visualmente grupos de mintermos que formam blocos de 1x1, 1x2, 2x1, 2x2, 1x4, 4x1, 4x2, 2x4 e 4x4. Lembre-se, as beiradas da tabela verdade se ligam com o lado oposto, isto é, a linha do topo do mapa verdade é adjacente à linha da base do mapa verdade e a coluna da esquerda é adjacente à coluna direita. No mapa verdade para F = C'B'A' + C'BA + CBA + CB'A' encontramos dois blocos de 1x2.

Uma das coisas que chama a atenção é que os dois blocos possuem células nas linhas C' e C. Estes blocos correspondem a dois mintermos que se diferenciam apenas porque um mintermo do bloco contém uma literal C' e o outro contém uma literal C. Por exemplo, o bloco da esquerda corresponde aos dois mintermos C'B'A' e CB'A'. Podemos reduzir algebricamente estes dois termos para B'A'(C' + C). Como o termo entre parênteses é igual a 1, podemos combinar estes dois termos para obter um termo único B'A'.

Q02.40 - Porque (C' + C) é igual a 1 (qual foi a regra aplicada)?

Podemos repetir o processo para o segundo bloco do mapa verdade. O bloco da direita é igual aos mintermos C'BA e CBA. Podemos usar a lei distributiva para obter BA(C' + C), o que é igual a BA. Portanto, a versão simplificada de F = C'B'A' + C'BA + CBA + CB'A' é F = B'A' + BA.

Quando agrupamos bloco é preciso marcar todos os grupos de células que contenham 1 e que se enquadrem nos padrões acima citados (1x1, 1x2, 2x1, etc). Grupos podem se sobrepor quando pelo menos um mintermo (célula contendo 1) do grupo não estiver incluído num outro grupo. O objetivo é escolher o conjunto dos maiores possíveis retângulos existentes no mapa verdade. Considere o mapa verdade ao lado: os grupos são a primeira e a terceira colunas (1x4), além da última linha (4x1). Isto deixa apenas dois mintermos que precisam ser agrupados e que farão parte de dois blocos de 2x2:

Observe que estes não são os únicos blocos que podem ser individualizados. Por exemplo, podemos capturar o mintermo D'C'BA' (o da célula superior direita) e casá-lo com os mintermos dos outros cantos, além de capturar DCBA' e associá-lo à célula abaixo e às duas correspondentes do lado oposto:

Não importa qual grupo vai ser usado, qualquer escolha gera uma equação com um mínimo de termos. Sob este ponto de vista, são todos equivalentes. Vamos usar a primeira versão deste exemplo.

Uma vez que células adjacentes de mintermos tenham sido apropriadas em blocos, podemos convertê-las em termos eliminando as literais que aparecem tanto na forma plicada quanto na forma não plicada. Por exemplo, considere o primeiro bloco, o qual é composto pelos mintermos que possuem as literais C/C' e D/D'. Estas quatro células compartilham os termos B'A'. Portanto, podemos criar um termo único eliminando as literais C, C', D e D', produzindo o termo simplificado B'A'.

Q02.41 - No mapa verdade acima, quais são as literais que aparecem no bloco destacado?

Q02.42 - Qual é a expressão simplificada para este bloco?

Q02.43 - No mapa verdade acima, quais são as literais que aparecem no bloco destacado?

Q02.44 - Qual é a expressão simplificada para este bloco?

Q02.45 - No mapa verdade acima, quais são as literais que aparecem no bloco destacado?

Q02.46 - Qual é a expressão simplificada para este bloco?

Q02.47 - No mapa verdade acima, quais são as literais que aparecem no bloco destacado?

Q02.48 - Qual é a expressão simplificada para este bloco?

Depois de criar expressões simplificadas para cada um dos blocos podemos criar uma expressão simplificada que é equivalente à função booleana original fazendo um OR lógico na expressão simplificada. Como existem cinco blocos, no final haverá cinco termos na expressão booleana simplificada. Compare a expressão simplificada com os 12 mintermos da expressão canônica original.

Q02.49 - Como nunca vimos a expressão booleana "original" para esta função, como sabemos que há 12 mintermos na expressão canônica?

Q02.50 - Qual é a expressão booleana simplificada decorrente da otimização do mapa verdade do exemplo?

Estas 50 questões referem-se a parte do conteúdo do capítulo 2. Como o assunto é extenso, os outros tópicos deste capítulo estão no módulo AoA - Laboratório Cap.2 II.