AB - Algebra - Boole - Simplificação - Circuitos

AB - Algebra - Boole - Simplificação - Circuitos

José Augusto Baranauskas

Departamento de Computação e Matemática –FFCLRP-USP augusto @u sp.br http://dc m.f mrp.usp.br/~augusto

Álgebra de Boolee Simplificação de Circuitos Lógicos

Nesta apresentação serão vistos os postulados e propriedades e formas canônicas de expressões booleanas

Além disso, serão vistas duas forma de simplificar circuitos

Fatoraçã o

Diagramas de Veitch- Karnaugh

Motivação

Como visto, os circuitos lógicos correspondem (executam) expressões booleanas, as quais representam problemas no mundo real

Porém, os circuitos gerados por tabelas verdade muitas vezes admitem simplificações, o que reduz o número de portas lógicas; essa redução diminui o grau de dificuldade na montagem e custo do sistema digital

Motivação

O estudo da simplificação de circuitos lógicos requer o conhecimento da álgebra de Boole, por meio de seus postulados, propriedades, equivalências, etc

De fato, na álgebra de Boole encontram-se os fundamentos da eletrônica digital de circutos

Constantes, Variáveis e Expressões

Existem apenas duas constantes booleanas

Uma variável booleana é representada por letra e pode assumir apenas dois valores (0 ou 1)

Exemplos: A, B, C

Uma expressão booleana é uma expressão matemática envolvendo constantes e/ou variáveis booleanas e seu resultado assume apenas dois valores (0 ou 1)

Exemplos:

Na álgebra booleana há postulados (axiomas) a partir dos quais são estabelecidas várias propriedades

Existem várias propriedades da negação

(complemento, inversor), adição (porta E) e soma (porta OU)

Estas propriedades podem ser verificadas como equivalências lógicas

Para demonstrar cada uma, basta utilizar as tabelas-verdade, constatando a equivalência

Postulados & Propriedades

Postulados

Co mple mento

Se A=0 então Ā=1 Se A=1 então Ā=0

Notações alternativas

Adição

Multiplicação

Propriedades Propriedade Co mple mento Adição Multiplicação

Identidade Ā= A

A + A = A . A = A A + Ā= 1A . Ā= 0

ComutativaA + B = B + A . B = B . A

Propriedades

Absorção

OutrasIdentidades A + Ā.B = A + B

De Morgan

( A. Bn)’ = Ā +  +... + 

Exercício

Mostre, usando simplificação por postulados e propriedades, ou seja, por transformações algébricas que:

Solução

A + A.B = A.(1+ B) distributiva

= A.(1)identidade da adição

= Aidentidade da multiplicação

= A + (A.B)identidade da multiplicação

= Apela prova do exercício acima

Exercício

Idem ao exercício anterior A + Ā.B = A + B

Solução

= (0 + Ā. )’identidade da multiplicação

= (Ā. )’identidade da adição

= A + BDe Morgan

= 1.(A+B)identidade da adição = A + Bidentidade da multiplicação

Solução

= A.A + A.C + A.B + B.Ccomutativa

= A + A.C + A.B + B.Cidentidade da multiplicação

= A + A.(C+B) + B.Cdistributiva

= A.(1) + B.Cidentidade da adição

= A + B.Cidentidade da multiplicação

Simplificação de Expressões Booleanas

Usando a álgebra booleana é possível si mplificar expressões

Como cada circuito corresponde a uma expressão, simplificações de expressões significam em simplificações de circuitos

Há duas formas para simplificar expressões

Fatoração Mapas de Veitch-Karnaugh

Veremos, a seguir, o processo de fatoração

Fa toração

Consiste na aplicação dos postulados e propriedades da álgebra booleana, com o objetivo de simplificar a expressã o

Por exemplo

= A.(B.C + ( (C’ + B’)’ )’)identidade do complemento

= Aidentidade da multiplicação

Fa toração

Essa expressão mostra a importância da simplificação de expressões e a consequente minimização do circuito, sendo o resultado final igual ao da variável A

Circuito antes da simplificação

Circuito após simplificação

Exercício

Simplifique as expressões

Solução

Simplifique as expressões

Exercício

Simplifique as expressões

Solução

Formas Normais (Canônicas)

Toda expressão booleana pode ser escrita em uma forma padronizada, denominada forma normal ou forma canônica

Duas formas normais são

Forma Normal Conjuntiva (FNC), Produto de Somas ou Produto de Maxtermos

Forma Normal Disjuntiva (FND), Soma de Produtos ou Soma de Mintermos

Maxter mos e Minter mos

Maxtermos (ou maxitermos)

Variável com valor 0 é deixada intact a

Variável com valor 1 é alterada pela sua negação

Variáveis de uma mesma linha são conectadas por +(adição)

Mintermos (ou minitermos)

Variável com valor 1 é deixada intact a

Variável com valor 0 é alterada pela sua negação

Variáveis de uma mesma linha são conectadas por . ( multiplica çã o)

A B C Maxter mo Minter mo

Forma Normal Disjuntiva

Mintermo(ou minitermo) é o termo produto associado à cada linha da tabela verdade, no qual todas as variáveis de entrada estão presentes

Dado um dado mintermo, se substituirmos os valores das variáveis associadas, obteremos 1

Porém, se substituirmos nesse mesmo mintermo quaisquer outras combinações de valores, obteremos 0

Dessa forma, se quisermos encontrar a equação para uma função a partir de sua tabela verdade, basta montarmos um OUentre os mintermos associados aos 1s da função

FND: Exemplo

S é uma função das variáveis de entrada A, B e C

Os valores de (A,B,C) para os quais S=1 encontram-se nas situações 2, 3, 5 e 6

Os mintermosassociados a essas condições (ou seja, os mintermos1) são mostrados na tabela ao lado

Logo, a expressão em soma de produtos (FND) para S será o OUentre estes produtos

Situaçã o A B C S Minter mo

Forma Normal Conjuntiva

Maxtermo(ou maxitermo) é o termo soma associado à cada linha da tabela verdade, no qual todas as variáveis de entrada estão presentes

Dado um dado maxtermo, se substituirmos os valores das variáveis associadas, obteremos 0

Porém, se substituirmos nesse mesmo maxtermo quaisquer outras combinações de valores, obteremos 1

Dessa forma, se quisermos encontrar a equação para uma função a partir de sua tabela verdade, basta montarmos um Eentre os maxtermos associados aos 0s da função

FNC: Exemplo

S é uma função das variáveis de entrada A, B e C

Os valores de (A,B,C) para os quais S=0 encontram-se nas situações 0, 1, 4 e 7

Os maxtermosassociados a essas condições (ou seja, os maxtermos0) são mostrados na tabela ao lado

Logo, a expressão em produto de somas (FNC) para S será o Eentre estas somas

Situaçã o A B C S Maxter mo

Simplificação a partir da Forma Nor mal

Uma vez obtida a forma normal de uma função booleana, é possível simplificá-la por meio de manipulação algébrica, respeitando os postulados e propriedades da álgebra booleana, com visto anteriormente

Mapas de Veitch-Karnaugh

Alternativamente ao método de simplificação algébrico por fatoração, há outro método de simplificação baseado na identificação visual de grupos de mintermos que podem ser simplificados

Para tanto, é necessário que os mintermos sejam dispostos de maneira conveniente, em tabelas conhecidas como diagra mas ou mapas de Veitch-Karnaugh

Diagrama de Veitch-Karnaugh para 2 Variáveis

Em um mapa de Veitch-Karnaugh, há uma região própria para cada linha da tabela verdade

Essas regiões são os locais ondem devem ser colocados os valores que a expressão S assume nas diferentes possi bilidades

Para obter a expressão simplificada por meio do diagrama

Agrupar as regiões onde S=1 no menor número possível de pares (diagonais não são permitidas no agrupamento de pares)

As regiões onde S=1 que não puderem ser agrupadas em pares são consideradas isoladamente

0 0 Situação 0

0 1 Situação 1

1 0 Situação 2

1 1 Situação 3

Diagrama de Veitch-Karnaugh para 2 Variáveis

Exe mplo

A tabela verdade mostra o estudo de uma função

A expressão booleana da função S obtida da tabela verdade usando mintermos é

Obtenha uma expressão equivalente, simplificada usando mapa de Veitch- Karnaugh

Exe mplo

Inicialmente, o diagrama é preenchido com cada situação da tabela ve rdade

Exe mplo

Inicialmente, o diagrama é preenchido com cada situação da tabela ve rdade

Situaçã o A B S

Exe mplo

Inicialmente, o diagrama é preenchido com cada situação da tabela ve rdade

Situaçã o A B S 0 0 0 0

Exe mplo

Inicialmente, o diagrama é preenchido com cada situação da tabela ve rdade

Exe mplo

Inicialmente, o diagrama é preenchido com cada situação da tabela ve rdade

Exe mplo

Agora tentamos agrupar as regiões onde S=1 no menor número possível de pares

Um par é o conjunto de duas regiões onde S=1 que tem um lado em comum, ou seja, são vizi nhos

Exe mplo

Agora tentamos agrupar as regiões onde S=1 no menor número possível de pares

Um par é o conjunto de duas regiões onde S=1 que tem um lado em comum, ou seja, são vizi nhos

Um mesmo valor 1 pode pertencer a mais de um par

Par 2 Par 1

Exe mplo

Então, escrevemos a expressão de cada par, ou seja, a região que o par ocupa no diagra ma

O par 1 ocupa a região A=1, então sua expressão é A

O par 2 ocupa a região onde B=1, sendo sua expressão B

Neste caso, nenhum 1 ficou isolado, ou seja, fora dos pares

Basta então somar os resultados de cada par

S = Par 1 + Par 2 S = A + B

Par 2 Par 1

Exe mplo

A expressão de S obtida por mapa de Veitch-Karnaugh é S = A + B

Como é possível notar, essa é a expressão de uma porta OU, pois a tabela verdade também é da porta OU

Outro ponto importante é que a expressão obtida diretamente da tabela verdade S = Ā.B + A. + A.B é visivelmente maior que a expressão mini mizada

Par 2 Par 1

Exercício

Dada a tabela ao lado, obtenha a expressão de S diretamente da tabela, usando minter mos

A seguir, transporte a tabela para o diagrama de Veitch-

Karnaugh e obtenha a expressão si mplificada

Solução

Dada a tabela ao lado, obtenha a expressão de S diretamente da

A seguir, transporte a tabela para o diagrama de Veitch-Karnaugh e obtenha a expressão simplificada

Nota-se que a tabela verdade é a de uma porta NAND, cuja expressão é S=(A.B)’

Aplicando De Morgan na expressão encontrada, tem-se S = Ā+ = (A.B)’

Par 1

Diagrama de Veitch-Karnaugh para 3 Variáveis

De forma análoga para 2 variáveis, com 3 variáveis também há uma região própria para cada linha da tabela verdade em um mapa de Veitch -Karnaugh

Para obter a expressão simplificada por meio do diagrama

Agrupar as regiões onde S=1 no menor número possível de quadras

Em seguida, agrupar as regiões onde S=1 no menor número possível de pares

As regiões onde S=1 que não puderem ser agrupadas em quadras ou pares são consid eradas is ola da mente

C RegiãoA=1 (Região A)

C RegiãoB=1 (Região B)

C RegiãoC=1 (Região C)

C RegiãoA=0 (Região Ā)

C RegiãoC=0 (Região C)

Quadras

C Região Ā.C

C Região Ā.B

C Região A.C

C Região A.B

C C C Região Ā.C

C C C Região A.C

C C C Região B.C

C C C Região B.C

Quadra e Pares nas Extre midades

C RegiãoC=0 (Região C)

C Região Ā.C

C Região A.C

Note que a região marcada corresponde a uma quadra, mesmo não estando contígua no dia gra ma

De forma análoga, estas regiões marcadas correspondem a pares

Exe mplo

A expressão extraída diretamente da tabela verdade para S é

Como antes, o diagrama é preenchido com cada situação da tabela verdade

Exe mplo

A expressão extraída diretamente da tabela verdade para S é

Como antes, o diagrama é preenchido com cada situação da tabela verdade

Exe mplo

A expressão extraída diretamente da tabela verdade para S é

Como antes, o diagrama é preenchido com cada situação da tabela verdade

Comentários