Algebra-Booleana-e-Circuitos-Logicos-Tabelas-Verdade-e-Operacoes

Álgebra Booleana e Circuitos Lógicos Uma álgebra Booleana pode ser definida com um conjunto de operadores e axiomas assumidos verdadeiros Fundamentos da Álgebra Booleana Valores Limitados Diferentemente da álgebra ordinária dos reais variáveis Booleanas assumem apenas valores finitos 01 Tabela Verdade Como o número de valores é finito podemos descrever completamente as funções usando tabelas Estados Finitos O número de estados que uma função pode assumir também é finito e pequeno Operações Básicas da Álgebra Booleana Na álgebra Booleana existem três operações fundamentais que formam a base para todas as funções Booleanas Operação OU Adição lógica que resulta 1 se pelo menos uma das variáveis de entrada vale 1 Operação E Multiplicação lógica que resulta 0 se pelo menos uma das variáveis de entrada vale 0 Complementação negação Inversão que retorna o valor complementar da variável Operação OU Adição Lógica A operação OU resulta 1 se pelo menos uma das variáveis de entrada vale 1 Automaticamente resulta 0 nos demais casos O símbolo utilizado é ou A B AB 0 0 0 0 1 1 1 0 1 1 1 1 O operador OU é binário requerendo pelo menos duas variáveis Possui propriedades associativa e comutativa Lei da identidade do OU com 1 Ou seja se uma das entradas do OU é 1 o resultado sempre é 1 Operação OU Adição Lógica Construir a tabela verdade Operação OU Adição Lógica Construir a tabela verdade Operação E Multiplicação Lógica A operação E resulta 0 se pelo menos uma das variáveis de entrada vale 0 Resulta 1 somente quando todas as entradas valem 1 O símbolo utilizado é ou A B A B 0 0 0 0 1 0 1 0 0 1 1 1 Assim como a operação OU a operação E é binária e possui propriedades associativa e comutativa Operação E Multiplicação Lógica Construir a tabela verdade Operação E Multiplicação Lógica Construir a tabela verdade Complementação Negação A operação complementação retorna o valor complementar da variável Se a variável vale 0 o resultado é 1 se vale 1 o resultado é 0 Símbolos Utilizados A barra sobre a variável A til antes da variável A apóstrofe após a variável Tabela Verdade A A 0 1 1 0 Diferentemente das operações OU e E a complementação é unária operando sobre apenas uma variável Avaliação de Expressões Booleanas Para avaliar uma expressão Booleana criamos uma tabela verdade listando todas as combinações possíveis das variáveis de entrada e calculamos o resultado da função 01 Criar Colunas Listar todas as combinações possíveis usando 2ⁿ combinações n número de variáveis 02 Variáveis Complementadas Criar colunas para variáveis que aparecem negadas na equação 03 Seguir Precedência Avaliar primeiro multiplicação lógica depois adição lógica Exemplo de Avaliação W X Y Z Vamos avaliar a expressão W X Y Z com três variáveis de entrada X Y Z resultando em 2³ 8 combinações possíveis X Y Z Z Y Z W X Y Z Exemplo de Avaliação W X Y Z Vamos avaliar a expressão W X Y Z com três variáveis de entrada X Y Z resultando em 2³ 8 combinações possíveis Exercício W XZ Y Exercício W XZ YZ Propriedades da Álgebra Booleana As propriedades fundamentais da álgebra Booleana são essenciais para simplificação de expressões Propriedades da Álgebra Booleana Existe uma lei fundamental da álgebra booleana 𝐴 𝐴 𝑋 𝐴 Isto porque Ou seja o fator A absorve a soma REGRAS BÁSICAS DA ÁLGEBRA BOOLEANA Propriedade OU E P1 Identidade X 1 1 X 0 0 P2 Elemento Neutro X 0 X X 1 X P3 Idempotência X X X X X X P4 Involução X X X X P5 Complemento X X 1 X X 0 P6 Comutatividade X Y Y X X Y Y X P7 Associatividade X Y Z X Y Z X Y Z X Y Z P8 Distributividade X Y Z X Y X Z X Y Z X Y X Z P9 Cobertura X X Z X X X Y X P10 Combinação X Y X Y X X Y X Y X P11 Consenso X Y X Z Y Z X Y X Z X Y X Z Y Z X Y X Z P12 De Morgan X Y X Y X Y X Y Simplificação de Expressão Booleana a Z D BCD b Y ABD ABD c Z A BA B d X ACD ABCD e X A CB D f F X YZ W Simplificação de Expressão Booleana a Z D B C D 1 Primeiro aplique De Morgan na barra externa Z D BC D 2 Na segunda barra outra vez De Morgan BC D BC D 3 Dupla negação BC BC portanto Z D BC D 4 Distribua Z D BC D D 5 D D D então Z D D BC 6 Pela absorção P PQ P Z D b Y ABD ABD 1 Coloque o fator comum AB Y ABD D 2 Como D D 1 Y AB c Z A BA B 1 Distribua Z AA AB BA B² 2 Sabendo que AA 0 e B² B Z AB BA B 3 Fatorando B Z BA A B1 B Simplificação de Expressão Booleana f Simplificação de Equações Lógica Mostre usando simplificação por postulados e propriedades ou seja por transformações algébricas que a AAB A b AAB A c A AB A B d ABAC A BC Simplificação de Equações Lógica Mostre usando simplificação por postulados e propriedades ou seja por transformações algébricas que a b c ou d Portas Lógicas Portas lógicas são símbolos gráficos que representam operações Booleanas e fisicamente circuitos eletrônicos capazes de realizar essas operações Porta OU Símbolo curvo com múltiplas entradas à esquerda e uma saída à direita Porta E Símbolo retangular com lado curvo múltiplas entradas e uma saída Inversor Triângulo com círculo pequeno na saída uma entrada e uma saída Portas Lógicas Símbolos equivalentes para as portas NE e NOU Conforme os teoremas de DeMorgan Assim às vezes são utilizados os símbolos a seguir para representar as portas NE e NOU Construção de Circuitos Lógicos Para desenhar um circuito lógico a partir de uma equação Booleana seguimos a mesma ordem de avaliação das operações Identificar Variáveis Traçar linhas para cada variável independente da esquerda para direita Parêntesis Resolver primeiro os parêntesis mais internos Operações E Desenhar portas E para multiplicações lógicas Operações OU Desenhar portas OU para adições lógicas Exemplo de Circuito Lógico A figura 24 mostra o circuito lógico para a equação W X Y Z Figura 24 Um circuito lógico Exemplo Dado S ABBC Informe quem é A A expressão booleana B Contrua o circuito C Construa a tabela verdade Exemplo S ABBC Expressão Booleana Circuito Tabela Verdade Exemplo Dado S ABCCDA Informe quem é A A expressão booleana B Contrua o circuito C Construa a tabela verdade Exemplo S ABCCDA Expressão Booleana Circuito Tabela Verdade Derivação de Expressões Booleanas Derivar uma expressão Booleana é encontrar uma equação que descreva uma função a partir de sua tabela verdade É o problema inverso da avaliação Soma de Produtos Descreve situações onde a função vale 1 Produto de Somas Descreve situações onde a função vale 0 Qualquer função Booleana pode ser descrita por qualquer um dos dois métodos bastando usar um deles para encontrar uma equação completa Método Soma de Produtos SdP No método SdP cada combinação de entradas é associada a um termo produto mintermo onde todas as variáveis estão presentes 01 Construir Mintermos Se variável vale 0 aparece negada se vale 1 aparece não negada 02 Identificar Mintermos1 Selecionar mintermos correspondentes aos 1s da função 03 Fazer OU dos Mintermos A expressão final é o OU entre todos os mintermos1 Exemplo Soma de Produtos Para a função F com mintermos1 em 010 011 101 e 110 A B C F A expressão resultante é Exemplo Soma de Produtos Para a função F com mintermos1 em 010 011 101 e 110 A expressão resultante é OBS NA SOMA DE PRODUTO O ZERO FICA NEGATIVO Método Produto de Somas PdS No método PdS cada combinação é associada a um termo soma maxtermo onde todas as variáveis estão presentes 01 Construir Maxtermos Se variável vale 1 aparece negada se vale 0 aparece não negada 02 Identificar Maxtermos0 Selecionar maxtermos correspondentes aos 0s da função 03 Fazer E dos Maxtermos A expressão final é o E entre todos os maxtermos0 Os parêntesis em torno de cada termo soma são obrigatórios devido à precedência de operadores Exemplo Produto de Somas PdS Para a função F com mintermos1 em 000 001 100 e 111 A B C F A expressão resultante é Exemplo Produto de Somas PdS Para a função F com mintermos1 em 000 001 100 e 111 A expressão resultante é OBS NO PRODUTO DE SOMA O UM FICA NEGATIVO Formas Canônicas e Padrão As representações em álgebra Booleana podem ser classificadas em diferentes formas Formas Padrão Soma de produtos e produto de somas são as formas padrão básicas Formas Canônicas Casos especiais onde todas as variáveis aparecem em cada termo Formas Simplificadas Versões reduzidas obtidas através de manipulação algébrica Formas Canônicas e Padrão A tabela a seguir lista todos os mintermos e maxtermos de uma função de três variáveis A B e C Voltando à função F das seções anteriores podemos reescrever a expressão em soma de produtos na forma canônica como segue Ou ainda Ou ainda Onde os números representam os índices decimais dos mintermos1 Onde os números representam os índices decimais dos maxtermos0 Circuitos para Formas Padrão e NãoPadrão As regras seguintes devem ser observadas a fim de facilitar a compreensão do desenho as variáveis de entrada devem ser identificadas preferencialmente à esquerda junto aos respectivos fios inversores devem ser providos para as variáveis que aparecem negadas na equação as portas que implementam as operações Booleanas que aparecem na equação normalmente são posicionadas da esquerda para a direita seguindo a ordem de avaliação dos operadores Circuitos para Formas Padrão e NãoPadrão Circuitos lógicos para formas padrão seguem estruturas específicas Soma de Produtos Primeiro nível portas E produtos Segundo nível porta OU soma Produto de Somas Primeiro nível portas OU somas Segundo nível porta E produto Estes são chamados circuitos em dois níveis lógicos A complexidade é medida pelo número total de entradas das portas Circuitos para Formas Padrão e NãoPadrão Repare que em todas as interseções de fios em que há conexão física deve haver um ponto suficientemente grande como se fora uma solda Logo quando não há o referido ponto na interseção de fios significa que tais fios estão eletricamente isolados No caso de equações na forma soma de produtos canônica ou simplificada Circuitos para Formas Padrão e NãoPadrão O circuito da figura 25 pode ainda ser desenhado utilizandose uma notação simplificada para os inversores das entradas Ao invés de se desenhar um inversor para cada variável que aparece negada na equação colocase um círculo junto a cada entrada de cada porta na qual há uma variável negada A aplicação desse procedimento para o circuito da figura 25 resulta no seguinte desenho Circuitos para Formas Padrão e NãoPadrão No caso de equações na forma produto de somas canônica ou simplificada Circuitos para Formas Padrão e NãoPadrão Circuitos lógicos para formas padrão seguem estruturas específicas Soma de Produtos Primeiro nível portas E produtos Segundo nível porta OU soma Produto de Somas Primeiro nível portas OU somas Segundo nível porta E produto Estes são chamados circuitos em dois níveis lógicos A complexidade é medida pelo número total de entradas das portas Construção do Mapa de Karnaugh Para construir um mapa de Karnaugh organizamos os mintermos em uma disposição especial 01 Escolher Mapa Selecionar mapa conforme número de variáveis 2 3 ou 4 variáveis 02 Preencher Valores Inserir valores da função conforme tabela verdade 03 Identificar Subcubos Encontrar grupos de 2ᵐ elementos adjacentes Construção do Mapa de Karnaugh Em um mapa de Karnaugh de 4 variáveis cada posição corresponde a um número binário formado por Exemplo binário 0000 mintermo 0 binário 0001 mintermo 1 binário 0010 mintermo 2 binário 1100 mintermo 12 binário 1101 mintermo 13 e assim por diante Mapas de Karnaugh Os mapas de Karnaugh são uma ferramenta visual para simplificação de funções Booleanas organizando mintermos de forma que adjacências representem possibilidades de simplificação Organização Visual Mintermos dispostos em tabela onde adjacentes diferem por uma variável Identificação de Grupos Grupos de mintermos adjacentes podem ser simplificados Simplificação Automática Processo visual torna a simplificação mais intuitiva Mapas de Karnaugh Tabela de adjacências para uma função de 3 variáveis 1 2 3 4 5 6 7 8 Se trocarmos o 3 mintermo com o 4 e trocarmos também o 7 mintermo com o 8 obteremos uma nova ordem na qual quaisquer dois mintermos adjacentes são passíveis de simplificação É interessante notar também que o 1 mintermo pode ser simplificado com o 5 o 2 mintermo pode ser simplificado com o 6 e assim por diante A figura a seguir explicita as relações de adjacência dos mintermos para uma função de três variáveis Mapas de Karnaugh 1 2 3 4 5 6 7 8 Funções Incompletamente Especificadas Algumas funções possuem condições dont care DC ou X combinações de entrada cujo valor não importa Dont Care Condições não especificadas marcadas com X ou DC Flexibilidade Podem assumir valor 0 ou 1 conforme conveniência Otimização Explorados para obter máxima simplificação Exemplo com Dont Care Para S₅ABCD Σ0121213 DC3710111415 Determinar a expressão mínima em soma de produtos para a função Exemplo com Dont Care Para S₅ABCD Σ0121213 DC3710111415 Determinar a expressão mínima em soma de produtos para a função 1 1 X 1 0 0 X O 1 1 X X 0 0 X X Bibliografia e Recursos Recursos fundamentais para aprofundamento no estudo de álgebra Booleana e circuitos lógicos Livros Clássicos GAJSKI Principles of Digital Design MANO Computer Engineering Hardware Design BROWN VRANESIC Fundamentals of Digital Logic Referências Complementares ERCEGOVAC Introdução aos Sistemas Digitais KATZ Contemporary Logic Design TAUB Circuitos Digitais e Microprocessadores