lgebra Booleana, Reviso Portas Lgicas e Mapas de Karnaugh1) lgebra Booleana: Em 1854, George Boole introduziu o formalismo que at hoje se usa para o tratamento sistemtico da lgica, que a chamada lgebra Booleana. Em 1938, C. E. Shannon aplicou esta lgebra para mostrar que as propriedades de circuitos eltricos de chaveamento podem ser representadas por uma lgebra Booleana com dois valores (estado ligadoe desligadoassociado a 0 e 1).. Em particular, na lgebra Booleana de dois valores, cada v arivel pode assumir um dentre dois valores possveis, os quais podem ser denotados por [F,V] (falso ou verdadeiro), [H,L] (high and low) ou ainda [0,1]. Nesta disciplina, adotaremos a notao [0,1], a qual tambm utilizada em eletrnica digital. Como o nmero de valores que cada varivel pode assumir finito (e pequeno), o nmero de estados que uma funo Booleana pode assumir tambm ser finito, o que significa que podemos descrever completamente as funes Booleanas utilizando tabelas. Devido a este fato, uma tabela que descreva uma funo Booleana recebe o nome de tabela verdade, e nela so listadas todas as combinaes de valores que as variveis de entrada podem assumir e os correspondentes valores da funo (sadas). Na lgebra Booleana, existem trs operaes ou funes bsicas. So elas, operao OU, operao E e complementao. Todas as funes Booleanas podem ser representadas em termos destas operaes bsicas. Axiomas e propriedades: comutatividade, associatividade, distributividade FUNO OU / OR Tabela Verdade: A 0 0 1 1 B 0 1 0 1 S 0 1 1 1

Representao da porta lgica

A B

A+B

A B C

A+B+C

(a)(a) Funo OU de 2 entradas (b) Funo OU de 3 entradas

(b)

FUNO E / AND Tabela Verdade: A 0 0 1 1 B 0 1 0 1 S 0 0 0 1

Representao da porta lgica

A B

A.B

A B C

A.B.C

(a)(a) Funo E de 2 entradas (b) Funo E de 3 entradas

(b)

FUNO COMPLEMENTAR Tabela Verdade: A 0 1 S 1 0

Representao da porta lgica

A

A

Para desenhar um circuito a partir da equao Booleana, seguir a ordem de avaliao de expresses: 1. Parntesis (dos mais internos para os mais externos); 2. Operaes E; 3. Operaes OU

Para criar Tabelas Verdades a partir de funes Booleanas: 1. Criar colunas para as variveis de entrada e listar todas as combinaes possveis, utilizando a frmula : no de combinaes = 2 n (onde n o nmero de variveis de entrada); 2. Criar uma coluna para cada varivel de entrada que aparea complementada na equao e anotar os valores resultantes; 3. Avaliar a equao seguindo a ordem de precedncia, a partir do nvel de parnteses mais interno: 1o negao de variveis, i.e., operador complementao 2o multiplicao lgica, i.e., operador E 3o adio lgica, i.e., operador OU Exerccio: Dada a funo Booleana F= (A+B).C./A.D, determinar a tabela verdade e o circuito lgico associado a equao. A 0 0 0 0 0 0 0 0 1 1 1 B 0 0 0 0 1 1 1 1 0 0 0 C 0 0 1 1 0 0 1 1 0 0 1 D 0 1 0 1 0 1 0 1 0 1 0 /A 1 1 1 1 1 1 1 1 0 0 0 C./A.D 0 0 0 1 0 0 0 1 0 0 0 A+B 0 0 0 0 1 1 1 1 1 1 1 F= (A+B).C./A.D 0 0 0 0 0 0 0 1 0 0 0

1 1 1 1 1

0 1 1 1 1

1 0 0 1 1

1 0 1 0 1

0 0 0 0 0

0 0 0 0 0

1 1 1 1 1

0 0 0 0 0

F= (A+B).C./A.D = A.C./A.D + /A.B.C.D = /A.B.C.D F= /A.B.C.D Representao grfica: 1 porta E de 4 entradas onde a entrada A invertida por um inversor. 2) Leis Fundamentais da lgebra Booleana:

Seja A uma varivel Booleana. Ento: Se A ? 0 A = 1 Se A ? 1 A = 0 (definio do espao de uma varivel Booleana)

Propriedades da Operao OU

(1) (2) (3) (4)

A+ 0 = A A+ 1= 1 A +A = A A+ A = 1

, A.0 = 0 , A.1 = 1 , A.A = A , A./A = 0

Propriedade da Complementao

(9)Propriedade Comutativa

A=A

(10) (11)Propriedade Associativa

A + B = B+ A A B = B A

(12) (13)

A +(B+ C ) =(A + B )+ C = ( A + C )+ B A (B C) = (A B) C = (A C) B

Propriedade Distributiva

(14)Teoremas de Morgan

A (B + C) = A B + A C

A B C ... = A + B + C + ... (2.1) Para duas variveis A B = A + B

(2.3)

A + B + C + ... = A B C ... (2.2) A + B = A B (2.4)

Derivao das Expressoes Booleanas: Tabela Verdade, Simplificao, Equao Lgica atravs da soma de produtos (Lista todas as combinaes das variveis de entrada para os quais a funo vale 1) ou produto de somas (Lista todas as combinaes das variveis de entrada para os quais a funo vale 0). Construo do circuito lgico. 3) Simplificao de Funes Booleanas usando Mapas de Karnaugh O mtodo de simplificao apresentado na seo 2.6 de aplicabilidade limitada, uma vez que bastante difcil certificar-se que todos os pares de mintermos que podiam ser simplificados foram determinados. Alternativamente quele mtodo, h outro

mtodo de simplificao baseado na identificao visual de grupos de mintermos passveis de serem simplificados. No entanto, para que se possa identificar tais grupos, necessrio que os mintermos sejam dispostos de maneira mais conveniente, o que ser explicado a seguir. Na descrio do mtodo de simplificao literal, foi mencionado que os pares de mintermos que se diferenciam de somente uma varivel so passveis de simplificao. Observando a ordem com que os mintermos de uma funo Booleana qualquer (com, por exemplo, 3 variveis) aparecem na tabela verdade, vemos que, se trocarmos o 3 mintermo com o 4 e trocarmos tambm o 7 mintermo com o 8, obteremos uma nova ordem, na qual quaisquer dois mintermos adjacentes so passveis de simplificao. interessante notar tambm que o 1 mintermo pode ser simplificado com o 5, o 2 mintermo pode ser simplificado com o 6 e assim por diante.

Repare que nessa nova tabela, quaisquer dois mintermos adjacentes (na horizontal ou na vertical) so passveis de serem simplificados, pois s se diferenciam de uma varivel. importante ressaltar que esse conceito de adjacncia no est restrito aos limites da tabela, uma vez que os elementos extremos de uma mesma linha (ou de uma mesma coluna) tambm so simplificveis. Isto implica que a tabela de adjacncias de mintermos da figura 2.11 pode e deve ser encarada como uma figura geomtrica tridimensional do tipo toride (ou uma rosquinha). A figura a seguir explicita as relaes de adjacncia dos mintermos para uma funo de trs variveis.

importante ressaltar que o conceito de adjacncia aplicvel na horizontal e na vertical, mas nunca na diagonal. Por exemplo, observe que m0 e m5 no so adjacentes, pois no esto nem na mesma linha, nem na mesma coluna. O processo de simplificao usando a nova disposio inicia pela construo da tabela em si: os valores da funo que se quer simplificar devem ser preenchidos conforme a nova ordem. Aps, identificam-se todos os grupos de mintermos-1 adjacentes entre si. Cada grupo origina um termo produto, no qual somente as variveis comuns a todos os mintermos-1 permanecem. Desde que os grupos de mintermos-1 adjacentes tenham sido corretamente identificados, a simplificao se torna trivial.

Exemplo 2.3: simplificar a funo F, cuja tabela verdade encontra-se no item 2.5.2. O primeiro passo construir uma tabela para F, usando a nova disposio dos mintermos.

Aps, deve-se identificar todos os grupos de mintermos-1 adjacentes entre si. Cada grupo de mintermos-1 originar um produto, conforme indicado na figura 213. A equao em soma de produtos simplificada ser o OU entre os produtos encontrados:

Mapas de Karnaugh e Subcubos A tabela modificada usada para a identificao dos mintermos-1 adjacentes no exemplo anterior denominada mapa de Karnaugh (no caso, para 3 variveis). Na figura 2.14 so mostrados os mapas de Karnaugh para funes de 2, 3 e 4 variveis.

O primeiro passo para simplificar-se uma funo usando mapa de Karnaugh escolher o mapa conforme o nmero de variveis da funo e preencher os valores dos mintermos conforme a tabela verdade fornecida, ou conforme a equao fornecida. O segundo passo identificar grupos de mintermos adjacentes que formem grupos de 2m elementos adjacentes entre si, com 0_m_n, onde n o nmero de variveis da funo. Estes grupos so denominados subcubos. No caso de se querer encontrar uma expresso em soma de produtos, estaremos interessados nos subcubos de mintermos-1. Ento, cada subcubo contendo mintermos1 ir originar um produto, no qual uma ou mais variveis podero estar ausentes devido simplificao que obtida. Os produtos associados aos subcubos de mintermos-1, simplificados ou no, so denominados implicantes. importante ressaltar que quanto maior o nmero de elementos do subcubo, maior ser a simplificao obtida. Exemplo: Determinar os implicantes do Mapa a seguir:

No caso de se querer encontrar uma expresso em produtos de somas, estaremos interessados nos subcubos de mintermos-0. Ento, cada subcubo contendo mintermos0 ir originar uma soma, no qual uma ou mais variveis podero estar ausentes devido simplificao que obtida. As somas associados aos subcubos de mintermos-0, simplificadas ou no, so denominadas implicados. Tambm neste caso, quanto maior o nmero de elementos do subcubo, maior ser a simplificao obtida. Exemplo 2.5: determinar os implicados das funes dadas a seguir.

Cobertura dos Mapas de Karnaugh

Normalmente, possvel identificar-se numa mesma funo Booleana mais de um implicante (ou mais de um implicado). Neste caso, necessrio determinar o conjunto de implicantes (ou implicados) que melhor cobre a funo, onde a melhor cobertura significa necessariamente a expresso mais simplificada possvel, a qual denominada expresso mnima. O procedimento bsico para se determinar a melhor cobertura (tambm chamada cobertura mnima) para uma expresso em soma de produtos o seguinte: Identificar os subcubos de mintermos-1 com maior nmero de elementos possvel, iniciando do tamanho 2n , onde n o nmero de variveis da funo. Caso algum mintermo-1 fique isolado (isto , no h nenhum outro mintermo-1 adjacente a ele), ento ele constituir um subcubo de um elemento; Identificar o menor conjunto de subcubos de modo que cada mintermo-1 pertena a pelo menos um subcubo (= seja coberto pelo menos uma vez). Observaes: 1. Cada mintermo-1 pode ser coberto por mais de um subcubo, caso isso resulte numa simplificao maior; 2. Um ltimo teste para verificar se a expresso obtida realmente a mnima consiste em verificar se algum subcubo pode ser removido, sem deixar algum mintermo-1 descoberto. Um subcubo que poder ser removido sem descobrir mintermos dito subcubo no-essencial. Logo, todo o subcubo que no pode ser removido dito essencial.; 3. Pode haver mais de uma expresso mnima para uma mesma funo Booleana; 4. A expresso mnima aquela de menor complexidade. E a complexidade ser medida pelo nmero de literais de uma funo.

\

At agora, tem-se visto apenas duas funes booleanas de duas variveis, OU e E. Mas, existem 22^2 n funes Booleanas com n variveis binrias. Assim, existem 16 funes Booleanas de duas variveis e as funes E e OU so apenas duas dessas 16 funes. A tabela a seguir lista todas as 16 funes Booleanas de duas variveis, x e y.