CIRCUITOS DIGITAIS 2011

Pesquisar o site

Autor da Pagina

Atividade recente no site

Álgebra de Boole e Simplificação de Circuitos Lógicos

ÁLGEBRA DE BOOLE

As operações básicas da Álgebra de Boole são:

AVALIAÇÃO DE UMA EXPRESSÃO BOOLEANA
Uma expressão booleana é uma expressão formada por sinais de entrada (chamados variáveis de entrada) ligados por conectivos lógicos, produzindo como resultado um único sinal de saída.

Na avaliação de uma expressão Booleana, deverá ser seguida uma ordem de precedência conforme a seguir definido:

1º - avalie NOT
2º - avalie AND
3º - avalie OR
Obs.: respeitando-se sempre os parênteses!

Ex.: Avalie a expressão:

EQUIVALÊNCIA DE FUNÇÕES LÓGICAS
Duas funções Booleanas são equivalentes se - e somente se - para a mesma entrada, produzirem iguais valores de saída .

PORTANTO, DUAS FUNÇÕES LÓGICAS EQUIVALENTES TEM A MESMA TABELA VERDADE.

Ex.: Verifique se as funções lógicas a seguir representam funções equivalentes:

PROPRIEDADES DA ÁLGEBRA DE BOOLE

Exercício:
Simplifique a seguinte expressão:

PROPRIEDADES DA FUNÇÃO EXCLUSIVE OR (XOR)

FORMAS CANÔNICAS

REPRESENTAÇÃO DE UM CIRCUITO ATRAVÉS DE UMA TABELA VERDADE
Os circuitos de um computador realizam funções de grande complexidade, cuja representação geralmente não é óbvia. O processo para realização de uma função através de um circuito começa na descrição verbal do circuito (descrição do comportamento de suas possíveis saídas, em função das diversas combinações possíveis de seus sinais de entrada), a partir do que é possível montar sua tabela verdade.

Exemplos:
a) Considere um circuito elétrico composto de uma fonte de energia comercial (a alimentação da empresa de distribuição de energia, p.ex., a Light) e um interruptor (nossas entradas ) e uma lâmpada (nossa saída). A lâmpada acenderá se - e somente se - a) houver energia disponível (se não estiver "faltando luz") e b) o interruptor estiver ligado. Elabore a tabela verdade que representa esse circuito lógico.

b) Considere um sistema composto de duas caixas d'água (uma superior e uma cisterna). A cisterna é alimentada pela entrada de água da "rua", via empresa distribuidora (ex.: CEDAE). A caixa superior serve para distribuir a água, por gravidade, em todo o prédio: bicas, chuveiros, descargas sanitárias, circuitos anti-incêndio, etc, com a água sendo impulsionada por uma bomba hidráulica através de uma tubulação que liga a cisterna à caixa superior. Considerando que a bomba queimará se for acionada sem haver água no circuito hidráulico, projete um circuito lógico para acionar a bomba sempre que a caixa superior estiver vazia, desde que tenha água na cisterna.

c) Considere um circuito elétrico composto de uma fonte de energia comercial (a alimentação da empresa de distribuição de energia, p.ex., a Light), uma alimentação auxiliar (um gerador e um no-break, com bateria de acumulação) e um interruptor (nossas entradas ) e um sistema de computadores (nossa saída). O computador poderá operar se: a) houver energia disponível (se não estiver "faltando luz") em um dos circuitos de alimentação e b) o interruptor estiver ligado. Elabore a tabela verdade que representa esse circuito lógico.

FORMAS CANÔNICAS
A partir da tabela verdade produzida conforme item anterior, é possível chegar à expressão que representa o comportamento do circuito, e em seguida construir o circuito, usando as portas lógicas já estudadas. O processo de elaboração da expressão usa as chamadas formas canônicas, que consistem em regras para representar as condições de entrada que:
a) produzirão saída 1 (e portanto as demais condições produzirão saída 0) ou alternativamente,
b) produzirão saída 0 (e portanto as demais condições produzirão saída 1).

São portanto duas as formas canônicas: uma representa as condições que produzem saída 1 (SOMA DOS MINITERMOS) , a outra representa as condições que produzirão saída 0 (PRODUTO DOS MAXITERMOS). Essas formas são alternativas, isto é, a expressão poderá ser encontrada aplicando-se alternativamente UMA ou OUTRA das formas.

MINITERMO - são termos somente com AND (termos PRODUTO)
MAXITERMO - são termos somente com OR (termos SOMA).


SOMA DOS MINITERMOS
É produzida construindo:
- um termo (uma sub-expressão) para cada linha da tabela verdade (que representa uma combinação de valores de entrada) em que a saída é 1,
- cada um desses termos é formado pelo PRODUTO (FUNÇÃO AND) das variáveis de entrada, sendo que:
------ quando a variável for 1, mantenha;
------ quando a variável for 0, complemente-a (função NOT).
- a função booleana será obtida unindo-se os termos PRODUTO (ou minitermos) por uma porta OR (ou seja, "forçando-se" a saída 1 caso qualquer minitermo resulte no valor 1).

Dessa forma, ligando os termos-produto (também chamados minitermos) pela porta OR, caso QUALQUER UM dos minitermos seja 1 (portanto, caso qualquer uma das condições de valores de entrada que produz saída 1se verifique), a saída pela porta OR será também 1. Ou seja, basta que se verifique qualquer uma das alternativas de valores de entrada expressos em um dos minitermos, e a saída será também 1, forçada pelo OR. Caso nenhuma dessas alternativas se verifique, produz-se a saída 0.

Exemplo:

PRODUTO DOS MAXITERMOS
É produzida construindo:
- um termo (uma sub-expressão) para cada linha da tabela verdade (que representa uma combinação de valores de entrada) em que a saída é 0,
- cada um desses termos é formado pela SOMA (FUNÇÃO OR) das variáveis de entrada, sendo que:
------ quando a variável for 0, mantenha;
------ quando a variável for 1, complemente-a (função NOT).
- a função booleana será obtida unindo-se os termos SOMA (ou maxitermos) por uma porta AND (ou seja, "forçando-se" a saída 0 caso qualquer minitermo resulte no valor 0).

Dessa forma, ligando os termos-soma (também chamados maxitermos) pela porta AND, caso QUALQUER UM dos minitermos seja 0 (portanto, caso qualquer uma das condições de valores de entrada que produz saída 0 se verifique), a saída pela porta AND será também 0. Ou seja, basta que se verifique qualquer uma das alternativas de valores de entrada 0 expressos em um dos maxitermos, e a saída será também 0, forçada pelo AND. Caso nenhuma dessas alternativas se verifique, produz-se a saída 1.

Exemplo:

O MESMO COMPORTAMENTO (A MESMA TABELA VERDADE) PODE SER IGUALMENTE REPRESENTADA POR QUALQUER DAS FORMAS CANÔNICAS.

Exemplo:

Se ambas as formas canônicas produzem expressões equivalentes, como escolher qual a representação a utilizar? Escolha a que resultar em menor número de termos, produzindo uma expressão mais simples.

Por esse método, pode-se encontrar a expressão que represente qualquer tabela verdade.

Após se encontrar uma expressão que represente o comportamento esperado, é possível que não seja uma expressão simples que possa ser construída com poucas portas lógicas. Antes de projetar o circuito, é útil SIMPLIFICAR a expressão, de forma a possibilitar construir um circuito mais simples e portanto mais barato.

Portanto, o fluxo de nosso procedimento será:

DESCRIÇÃO VERBAL ---> TABELA VERDADE ---> FORMA CANÔNICA --->
--->FUNÇÃO SIMPLIFICADA ---> CIRCUITO

 

Determinando circuitos a partir da tabela de verdade


Em geral, a primeira ação a tomar no desenvolvimento de circuitos é determinar o que ele deve fazer. Para circuitos lógicos, isso é dado pela tabela de verdade.

A tabela a seguir representa um circuito de 3 entradas (A, B e C) e uma saída S. A coluna Comb significa combinação. É apenas uma numeração seqüencial das combinações das entradas para referências no texto.

Tabela 01

Comb

A

B

C

S

0

0

0

0

1

1

0

0

1

0

2

0

1

0

1

3

0

1

1

0

4

1

0

0

1

5

1

0

1

1

6

1

1

0

1

7

1

1

1

0


Deseja-se desenvolver um circuito lógico que execute a tabela.

O procedimento a seguir descrito é possivelmente um dos mais simples, embora não seja o mais eficiente.

Em primeiro lugar, consideram-se somente as combinações de saída não zero. Elas são as de números 0, 2, 4, 5 e 6.


Fig 01


A cada combinação de saída não nula, corresponde um bloco E com número de entradas igual ao da tabela (3 neste caso). Portanto, são 5 blocos E conforme Figura 01.

Em cada bloco E, são adicionados inversores (blocos NÃO) em cada entrada com valor zero na combinação.

A saída de cada bloco E é ligada à entrada de um bloco OU. A saída desse bloco é a saída S do circuito.

Conforme já dito, este método não é dos mais eficientes. Os circuitos são grandes demais e podem ser mais simples, o que é objeto dos próximos tópicos.


Diagramas de Veitch Karnaugh


O método de Veitch Karnaugh consiste em representar graficamente os valores das variáveis de entrada e os correspondentes valores da saída. A simplificação é obtida pela observação dos grupos formados.

Seja uma tabela de verdade simples, com apenas duas entradas e uma saída.

Tabela 01

Comb

A

B

S

0

0

0

0

1

0

1

1

2

1

0

1

3

1

1

1


Na Figura 01 (a), são representados:

• quadrados acima da linha horizontal     A = 0

• quadrados abaixo da linha horizontal    A = 1



• quadrados à esquerda da linha vertical → B = 0

• quadrados à direita da linha vertical  → B = 1

 


Fig 01


As saídas são marcadas pelas sobreposições.

Por exemplo, o quadrado inferior esquerdo é a sobreposição de A = 1 e B = 0, correspondendo à combinação de número 2 da tabela. A saída respectiva é S = 1 e é indicada no quadrado.

Procede-se de forma análoga para as demais combinações da tabela de verdade.

Uma vez inseridas todas as saídas, devem ser identificados todos os pares não diagonais possíveis de valores não nulos, mesmo que sobrepostos.

Há, portanto, dois pares possíveis:

Par 1: equivalente a A
Par 2: equivalente a B.

E a saída é uma função OU dos pares: S = A + B.

Esse resultado é um bloco OU simples, indicado em (b) da Figura 01.


Considera-se agora a tabela de verdade segundo Tabela 02 a seguir.

Tabela 02

Comb

A

B

S

0

0

0

0

1

0

1

0

2

1

0

0

3

1

1

1


A Figura 02 (a) exibe o diagrama de Veitch-Karnaugh para essa tabela de verdade.


Fig 02


Neste caso, não há formação de pares.

A saída S = 1 está isolada e deve ser entendida como uma função E das entradas sobrepostas, isto é,

S = A . B

O resultado é, portanto, um bloco E simples conforme (b) da figura.


Diagrama de Veitch Karnaugh para 3 variáveis


A tabela de verdade para o exemplo deste tópico é a mesma usada no tópico Determinando circuitos a partir da tabela de verdade desta página.

O diagrama para as três variáveis é dado em (a) da Figura 01.

O preenchimento é feito de modo similar ao do diagrama de duas variáveis já visto.

Tabela 01

Comb

A

B

C

S

0

0

0

0

1

1

0

0

1

0

2

0

1

0

1

3

0

1

1

0

4

1

0

0

1

5

1

0

1

1

6

1

1

0

1

7

1

1

1

0


Exemplo: a combinação 0 tem A = 0, B = 0 e C = 0. É, portanto, a interseção de A, B e C. Marca-se então 1 no quadrado correspondente porque a saída S tem esse valor segundo a tabela.

Outro exemplo: para a combinação 6, A = 1, B = 1 e C = 0. Portanto, A, B e C. E o quadrado é marcado com o valor da saída conforme tabela (1).


Fig 01


No diagrama de duas variáveis, os grupos de valores 1 só podem se pares. Para três variáveis, podem ser quadras e pares.

As seguintes regras devem ser observadas:

• quadras (e também pares) podem ser formadas por elementos não adjacentes se estiverem na borda (neste caso, são considerados adjacentes).

• pares devem estar fora das quadras ou podem ter um elemento comum. Não valem os pares com os dois elementos no interior de uma quadra.

No diagrama da Figura 01 (a) são identificados:

• par AB (interseção da área A com a área B).
• quadra C (toda na área C).

Portanto, a expressão lógica da saída é

S = AB + C

O circuito corresponde é dado em (b) da figura. Comparando com o circuito obtido para a mesma tabela de verdade no tópico Determinando circuitos a partir da tabela de verdade, nota-se que a simplificação é considerável.

Cabe lembrar que o diagrama de Veitch-Karnaugh pode ser construído a partir da expressão booleana no lugar da tabela de verdade. Para o circuito não simplificado do tópico mencionado (Determinando circuitos a partir da tabela de verdade), a expressão lógica é:

S = A B C + A B C + A B C + A B C + A B C

Basta, portanto, considerar cada parcela como saída 1 no diagrama e os demais quadrados nulos.


Diagrama de Veitch Karnaugh para 4 variáveis

  Seja agora o exemplo, conforme Tabela 01 a seguir, de uma tabela de verdade com 4 variáveis de entrada e uma saída.

Há 11 combinações com saída 1. Portanto, um circuito montado a partir da tabela, segundo método já visto, teria 11 portas E de 4 entradas e uma porta OU de 11 entradas.

Por indução, conclui-se que o diagrama de Veitch-Karnaugh para 4 variáveis pode ter pares, quadras e oitavas. São aplicáveis regras similares às vistas no tópico anterior.

Tabela 01

Comb

A

B

C

D

S

0

0

0

0

0

0

1

0

0

0

1

1

2

0

0

1

0

1

3

0

0

1

1

1

4

0

1

0

0

0

5

0

1

0

1

1

6

0

1

1

0

0

7

0

1

1

1

1

8

1

0

0

0

1

9

1

0

0

1

1

10

1

0

1

0

0

11

1

0

1

1

1

12

1

1

0

0

1

13

1

1

0

1

1

14

1

1

1

0

0

15

1

1

1

1

1


O diagrama para a tabela é dado em (a) da Figura 01 a seguir.

São identificados 3 grupos:

• par A B C

• quadra A C

• oitava D

Assim, a expressão booleana simplificada é:

S = A B C + A C + D

O circuito correspondente é dado em (b) da mesma figura.


Fig 01


Repetindo observação do tópico anterior, elementos nas bordas podem formar grupos. Isso deve ser sempre verificado, pois uma única omissão invalida o resultado.


Fig 02


Nos exemplos da Figura 02 (que não têm relação com o circuito anterior), são identificados:

Em (a):

• quadra BD

Em (b):

• quadra BD
• par ABD

Deve-se também observar que o maior grupo possível contém apenas uma variável. O segundo maior contém duas variáveis e assim por diante. Portanto, para melhor simplificação, a identificação dos grupos deve partir dos maiores para os menores.

Comments