Álgebra Booleana: Introdução e Conceitos Básicos

ÁLGEBRA BOOLEANA Material original desenvolvido pelos Profs Júlio Machado Marcelo Yamaguti e Sérgio Johann Filho 1 Introdução à Computação Material complementar 2 BROOKSHEAR J G Ciência da Computação uma visão abrangente 11a ed Porto Alegre Bookman 2013 Capítulo 1 FOROUZAN B MOSHARRAF F Fundamentos da Ciência da Computação São Paulo Cengage Learning 2012 Capítulos 4 DALE N LEWIS J Ciência da Computação 4ª ed Rio de Janeiro LTC 2011 Capítulo 4 Conceitos Básicos Operações complexas de um computador digital combinações de operações aritméticas e lógicas simples Somar bits Complementar bits Comparar bits Mover bits 3 Conceitos Básicos Operações realizadas fisicamente por circuitos eletrônicos lógicos Álgebra booleana Conjunto de operadores e um conjunto de axiomas que são assumidos verdadeiros sem necessidade de prova Computadores digitais circuitos eletrônicos digitais portas lógicas CE Shannon 1938 Álgebra de Boole álgebra de chaveamentos lógica e matemática G Boole 1854 4 Conceitos Básicos 5 Existem apenas duas constantes booleanas 0 zero falso 1 um verdadeiro 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 eou variáveis booleanas e seu resultado assume apenas dois valores 0 ou 1 Exemplos S AB S ABC Operadores Lógicos Os conectivos ou OPERADORES LÓGICOS são E ou AND uma sentença é verdadeira se e somente se todos os termos forem verdadeiros OU ou OR uma sentença resulta verdadeira se qualquer um dos termos for verdadeiro NÃO ou NOT este operador inverte o valor lógico de um termo 6 Operadores Lógicos Os operadores lógicos são representados usualmente por NÃO uma barra horizontal sobre o termo a ser invertido ou negado Notação alternativa A E um ponto como se fosse uma multiplicação eventualmente é o operador default e pode ser omitido OU o sinal de soma 7 Tabelas Verdade São tabelas que representam todas as possíveis combinações das variáveis de entrada de uma função lógica e os seus respectivos valores de saída O número de combinações que as N variáveis de entrada podem assumir é 2N 8 Tabelas Verdade 9 Lista das combinações possíveis dos estados das variáveis de entrada Variáveis FunçãoLógica Resultados da função lógica para cada combinação dos estados de entrada A B ZfAB 0 0 0 0 1 1 1 0 1 1 1 1 Uma Tabela Verdade relaciona os resultados saída de uma função lógica para todas as combinações possíveis de suas variáveis entrada Na Tabela Verdade acima a função lógica Z possui duas variáveis A e B sendo Z fA B A B Tabelas Verdade 10 OU OR soma lógica x y x OR y 0 0 0 0 1 1 1 0 1 1 1 1 E AND produto lógico x y x AND y 0 0 0 0 1 0 1 0 0 1 1 1 NÃO NOT complemento x NOT x 0 1 1 0 Tabelas Verdade 11 Exercício Calcule a tabela verdade para as seguintes funções booleanas A ordem de precedência das operações é NÃO E OU AB AB AB ABC AC AB Operadores Lógicos Derivados Vários operadores lógicos podem ser criados a partir dos operadores E OU e NÃO XOR OUEXCLUSIVO NAND NÃOE NOR NÃOOU Exercício Construa as tabelas verdade para os operadores derivados 12 AB AB AB AB A B Propriedades da ÁlgebraBooleana 13 Propriedade Complemento Adição Multiplicação Identidade A 0 A A 1 1 A A A A Ā 1 A 0 0 A 1 A A A A A Ā 0 Comutatividade A B B A A B B A Associatividade ABC ABC ABC ABC ABC ABC Distributividade ABC AB AC ABC AB AC Propriedades da ÁlgebraBooleana 14 A B C ABC 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 Propriedade Associativa eAcumulativa A ordem que as variáveis são avaliadas é irrelevante Propriedades da ÁlgebraBooleana 15 A B C ABC 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 Propriedade Associativa e Acumulativa A ordem que as variáveis são avaliadas é irrelevante Propriedades da ÁlgebraBooleana 16 Absorção A AB A A AB A Outras Identidades A ĀB A B ABAC A BC Teoremas de DeMorgan 17 Exercício Demonstre os dois teoremas de De Morgan utilizando tabelas verdade De Morgan estendida para n variáveis AB X A B X AB X A B X Resumindo 17 De Morgan estendida para n variáveis AB X A B X AB X A B X Propriedade Adição Multiplicação Identidade A 0A A 1 1 A A A A Ā 1 A 0 0 A 1 A A A A A Ā 0 Comutatividade A B BA A B BA Associatividade ABC ABC ABC ABC ABC ABC Distributividade ABC AB AC ABC AB AC Propriedade Absorção A AB A A AB A Outras Identidades A ĀB A B ABAC A BC Exercício exemplo 18 Demonstre 1 utilizando as propriedades da álgebra booleana e transformações algébricas as seguintes propriedades 2 utilizando tabelas verdade AAB A AAB A Exercício exemplo solução1 19 AAB A A AB A1B A1 A AAB A AAB AA AB A AB A distributiva identidade da adição identidade da multiplicação distributiva identidade da multiplicação pela prova do exercício acima Exercício exemplo solução2 20 AAB A A B AB AAB 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 1 AAB A A B AB AAB 0 0 0 0 0 1 1 0 1 0 1 1 1 1 1 1 Exercício 21 Demonstre 1 utilizando as propriedades da álgebra booleana e transformações algébricas as seguintes propriedades 2 utilizando tabelas verdade A ĀB A B ABAC A BC Derivação de Expressões Dada uma função booleana descrita por sua tabela verdade desejase um método para encontrar uma equação que a descreva Técnica básica Soma de Produtos 22 Soma de Produtos Dada uma função booleana a cada combinação de entradas podemos associar um termo produto ou mintermo no qual todas as variáveis estão presentes Esse termo é formado da seguinte maneira Se a variável correspondente vale 0 ela deve aparecer negada Se a variável correspondente vale 1 ela deve aparecer sem negação 23 Soma de Produtos Para obter a equação em soma de produtos Montar um OU entre todos o mintermos de valor 1 associado à função Exemplo 24 Derivação de Expressões Exercício Obtenha a equação via Soma de Produtos 25 A B C S 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 0 Simplificação de expressões 26 Usando a álgebra booleana é possível simplificar 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 disciplina de lógica Mapas de VeitchKarnaugh disciplina de sistemas digitais Simplificação por fatoração 27 Exemplo S ABC ACAB ABC C B ABC C B ABC C B identidade do complemento ABC CB ABC BC A1 A distributiva associativa De Morgan comutativa identidade da adição DD1 identidade da multiplicação Exercício escreva a tabela verdade para a função S Exercício 28 Simplifique as expressões S ABC ABC ABC S ĀB ĀB