Algebra Booleana e Simplificacao Algebrica - Notas de Aula EL66J UTFPR

Notas de aula 5 Álgebra Booleana e simplificação algébrica EL66J 14 UTFPR Disciplina EL66J Prof Gustavo B Borba Notas de aula 5 ÁLGEBRA BOOLEANA e SIMPLIFICAÇÃO ALGÉBRICA Em uma publicação científica de 1854 denominada An investigation of the laws of thought on which are founded the mathematical theories of logic and probability o matemático inglês George Boole por isso o nome álgebra Booleana com maiúscula estabeleceu os princípios de um sistema algébrico para variáveis binárias variáveis que assumem apenas dois valores Em 1938 o matemático e engenheiro eletricista norte americano Claude E Shannon utilizou a álgebra Booleana para analisar e descrever circuitos elétricos baseados em relés Faz todo sentido já que os contatos dos relés são variáveis binárias só interessam as situações nas quais está aberto ou fechado O título do artigo científico publicado por ele é Symbolic analysis of relay and switching circuits Nos tópicos a seguir observe que os axiomas afirmações que não exigem provas para serem consideradas verdadeiras 1 da álgebra Booleana estabelecem aquilo que utilizamos como ponto de partida as operações não e ou e que os estados das variáveis são mutuamente exclusivos Os teoremas podem ser considerados como o conjunto de regras para a manipulação das variáveis Em eletrônica digital os teoremas podem ser utilizados em uma técnica de simplificação de equações lógicas que agora podemos chamar também de equações Booleanas denominada simplificação algébrica O objetivo de um processo de simplificação de uma equação lógica é obter uma equação equivalente à original porém mais simples claro Duas equações lógicas são equivalentes quando apresentam a mesma tabela verdade Mais simples pode ser entendido como menor Por isso este processo também é chamado de minimização de uma equação lógica A simplificação é importante porque pode permitir não necessariamente a implementação de um circuito digital mais compacto portanto mais vantajoso que suas versões não minimizadas Axiomas há autores que chamam de postulados a1 A 0 se A 1 a1 A 1 se A 0 a2 se A 0 então A 1 a2 se A 1 então A 0 a3 0 0 0 a3 11 1 a4 1 1 1 a4 00 0 a5 0 1 1 0 0 a5 10 01 1 Notas de aula 5 Álgebra Booleana e simplificação algébrica EL66J 24 Teoremas há autores que chamam de leis propriedades identidades regras t1 A A t2 A 0 0 t4 A A A t3 A 1 A t5 A A 0 t2 A1 1 t4 AA A t3 A0 A t5 AA 1 Involução Elementos nulos Idempotência Identidades Complementos t6 A B B A t8 A BC A B A C t7 A B C A B C t6 AB BA t8 AB C AB AC t7 ABC ABC Comutativa Distributiva Associativa t9 A AB A t9 A A B A Absorção t10 A AB A B t10 A A B AB Absorção t11 AB AB A t11 A B A B A Adjacência lógica t12 A B A C B C A B A C t12 AB AC BC AB AC Consenso t13 A B Z ABZ t13 ABZ A B Z DeMorgan Algumas provas t9 A AB A t9 A A B A Absorção t10 A AB A B t10 A A B AB Absorção t11 AB AB A t11 A B A B A Adjacência lógica t12 A B A C B C A B A C t12 AB AC BC AB AC Consenso A0 AB A0 B A0 A 1 A B A 1B A 1 A A A A A B 0 A B A B AA AB 1 AB AB A B B A 0 A A BB A 1 A A B A C B C AA A B A C B C A B C A A B A B C A C A C B A B 1C A C 1B A B 1 A C 1 A B A C AB AC BCA A AB AC BCA BCA AB ABC AC ACB AB0 C AC0 B AB0 AC0 AB AC Notas de aula 5 Álgebra Booleana e simplificação algébrica EL66J 34 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 Exemplos 1 DeMorgan a Y ABCD E A B C DE A B C DE b Y A B C D E F A B C D E F ABC DEF c Y A BC DE F A BCDE F AB C D EF d Y AB CD EF A BCD E F AB C DEF AB C DEF Resolver de fora para dentro seria mais fácil 2 Prove que os circuitos são equivalentes utilizando manipulação algébrica Obs outra forma de provar a equvalência lógica seria através das tabelas verdade As tabelas verdade de Y1 e Y2 devem ser iguais A B Y1 A B AB A BAB Y1 A B Y2 Y2 A BAB A BAB Notas de aula 5 Álgebra Booleana e simplificação algébrica EL66J 44 3 Simplifique o circuito Para observar que os circuitos original e simplificado são realmente equivalentes obtenha as tabelas verdade de cada um As tabelas verdades devem ser iguais A C Y A B BC AB B C Y B A B CB B C B C A1 B C B Y C Simplif ABBC AB A B 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0 BC 1 0 0 0 1 0 0 0 Original 4 Simplifique as equações lógicas a Y AB ABC BBC AB AB AC BB BC b Y ABC BD ABC ABC ABBD ABC c Y ABAC AA AC AB BC d Y AB ABC A AB ABAB C A AB AC B BC B1AC AC B1 AC B AC ABC 0 ABC ABCC ABC ABC ABC BCA A BC1 BC A AC AB BC A1CB BC A1 BC A BC 1AB C A AB C A A1B C A1 C A C e Y ABC ABC ABCD ABC ABC ABCD f Y ABCABCBCAC ABCABBCCACC g Y AB AC A B AC h Y AB CD ACD ABCD AC D ABCAB00 ABCAB AABBC ABC A1C B A1 B A B ABC ABC ABCD ABC ABCD ABC CD ABCCCD AB1CD ABCD ABCD A C D ABC ABD A C D CAB1 A ABD D C1 AAABD D C 1ABD D C A D DB C A DDDB C A 1DB C A D B Referências 1 iDicinário Aulete disponível em httpauleteuolcombraxioma acessado em jan2013