Baixe o app para aproveitar ainda mais
Prévia do material em texto
PROGRAMA DE INFORMÁTICA BÁSICA Álgebra Booleana Prof. João Dallyson Na aula passada.... • Sistemas de Numeração • Operações Aritméticas 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 2 Sumário • Introdução • Variáveis Lógicas • Tipos de Representação • Operações Lógicas – AND, OR, XOR, NOT, NAND, NOR • Aplicações de Portas Lógicas • Equivalência de Expressões Lógicas 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 3 Introdução • O computador codifica a informação por meio de padrões de 0s e 1s. (bits) – O bit 0 representa o valor falso – O bit 1 representa o valor positivo • Operações Booleanas: – São operações que manipulam valores verdadeiro/false – George Boole (1815-1864) • Pioneiro na área da matemática chamada de lógica • A álgebra booleana foi inicialmente relacionada ao computador por Claude Shannon em 1937; 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 4 Variáveis Lógicas • Toda variável lógica só pode assumir dois estados lógicos distintos • Operações: AND, OR, NOT, XOR, NAND, NOR 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 5 Baixo e Alto ON e OFF Falso e Verdadeiro 0 e 1 (usado em digital) Tipos de representação • Expressões booleanas • Tabela Verdade • Circuitos Lógicos 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 6 Tipos de representação • Expressões booleanas – Precedência na avaliação: • Respeitar os parênteses • Avaliar a inversão • Avaliar a multiplicação • Avaliar a adição 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 7 Tipos de representação • Tabela Verdade: – Tabela na qual são exibidas todas as possíveis entradas e saídas de uma expressão booleana – facilita o cálculo do valor lógico de uma proposição composta – Para n variáveis booleanas, há 2^n 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 8 Tipos de representação • Porta Lógica: – Dispositivo que produz a saída de um operação booleana dados os valores de entrada – Podem ser construídas: • Engrenagens, relés, circuitos eletrônicos e dispositivos ópticos – Gráficos: AB ; ABCD..N 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 9 Operação Lógica: “E” (AND) • Possuem duas ou mais entradas e apenas uma saída; • Para que a proposição composta seja considerada verdade ambas as proposições que a compõem devem ser verdade; • realiza a multiplicação booleana de duas ou mais variáveis binárias; • Notação: P1 and P2 – P1P2, P1.P2, P1˄P2 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 10 P1 P2 P1 e P2 F F F F V F V F F V V V P1 P2 P1 . P2 0 0 0 0 1 0 1 0 0 1 1 1 Tabela Verdade Operação Lógica: “E” (AND) • Exemplo: – Considere as seguintes sentenças abaixo: • O Brasil é pentacampeão mundial de futebol masculino; – Verdade • O Vasco é campeão mundial; – Falso 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 11 P1 P2 O Brasil é pentacampeão mundial de futebol masculino E Nenhuma seleção possui tantos título mundiais como o Brasil O Flamengo é campeão mundial E O Vasco é campeão mundial P1 E P2 V F Operação Lógica: “E” (AND) • Implementação da Porta Lógica AND 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 12 Operação Lógica: “E” (AND) • Casos possíveis (AND) 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 13 Operação Lógica: “OU” (OR) • Possuem duas ou mais entradas e apenas uma saída; • Nesse caso a proposição composta só será verdade se pelo menos uma das proposições sejam verdade; • Realiza a soma booleana de duas ou mais variáveis binárias; • Notação: P1 or P2 – P1 + P2, P1 v P2 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 14 P1 P2 P1 ou P2 F F F F V V V F V V V V P1 P2 P1 + P2 0 0 0 0 1 1 1 0 1 1 1 1 Tabela Verdade Operação Lógica: “OU” (OR) • Exemplo: – Considere as seguintes sentenças abaixo: 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 15 P1 P2 O Brasil é pentacampeão mundial de futebol masculino OU Nenhuma seleção possui tantos título mundiais como o Brasil O Flamengo é campeão mundial OU O Vasco é campeão mundial O Paraguai possui sete títulos mundiais OU O Vasco é tricampeão mundial P1 E P2 V V F Operação Lógica: “OU” (OR) • Implementação da Porta Lógica OR 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 16 Operação Lógica: “OU” (OR) • Casos possíveis Porta Lógica OR 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 17 Operação Lógica: “NÃO” (NOT) • Possuem apenas uma entrada e uma única saída; • Este conectivo tem o papel de negar uma proposição, ou seja, inverte seu valor; • Basta acrescentar “é falso que”; • Notação: not P1; P1’ ; ¬P1 ; P1 ; ~; • Exemplo: – É falso que a Itália possui 7 títulos mundiais • Verdadeiro 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 18 P1 Não P1 V F F V Operação Lógica: “NÃO” (NOT) • Implementação porta lógica NOT • Casos possíveis 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 19 Operações Lógicas “Não E” (NAND) • NAND – realiza a multiplicação booleana de duas ou mais variáveis binárias e inverte o resultado – Notação: P1 nand P2 ; P1.P2 ; (P1.P2)’ ; ¬(P1.P2) 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 20 P1 P2 P1 nand P2 0 0 1 0 1 1 1 0 1 1 1 0 Tabela Verdade Porta Lógica Operações Lógicas “Não Ou” (NOR) • NOR – Realiza a soma booleana de duas ou mais variáveis binárias e inverte o resultado – Notação: P1 nor P2 ; P1+P2 ; (P1+P2)’ ; ¬(P1+P2) 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 21 P1 P2 P1 nor P2 0 0 1 0 1 0 1 0 0 1 1 0 Tabela Verdade Porta Lógica Operação Lógica: “Ou Exclusivo” (XOR) • Nesse caso a preposição composta só será verdade se as proposições forem diferentes; • Notação: P1 xor P2 ; P1 P2 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 22 P1 P2 P1 xor P2 F F F F V V V F V V V F P1 P2 P1 xor P2 0 0 0 0 1 1 1 0 1 1 1 0 Tabela Verdade Operação Lógica: “Ou Exclusivo” (XOR) • Implementação porta lógica XOR 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 23 Operação Lógica: “Ou Exclusivo” (XOR) • Casos possíveis porta lógica XOR 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 24 Aplicação de Portas Lógicas • Ex: – Circuito para testar de modo rápido se duas palavras são iguais 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 25 Solução: Porta XOR e porta NOR Aplicação de Portas Lógicas • Ex: – Alerta de cinto de segurança não afivelado 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 26 1 1 1 0 0 1 0 1 0 0 0 0 campainha Cinto desafi- velado ignição Solução: Porta AND Exemplos • (A E B) OU C09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 27 A 0 0 0 0 1 1 1 1 B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1 A E B 0 0 0 0 0 0 1 1 C 0 1 0 1 0 1 0 1 (A E B) OU C 0 1 0 1 0 1 1 1 Resumo 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 28 Exemplo 1 • Composição de operações lógicas: 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 29 Exemplo 2 • Composição de operações lógicas: 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 30 Exemplo 3 • Composição de operações lógicas: 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 31 Exemplo 4 • Representação por Tabela Verdade 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 32 Exemplo 5 • Representação por Tabela Verdade 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 33 Equivalência de expressões Lógicas ● Uma expressão booleana pode ser representada por mais de um circuito lógico ● Dados dois circuitos, como saber se eles são equivalentes (possuem a mesma expressão lógica)? – Tabela verdade • Se os resultados da tabela verdade são iguais, então são equivalentes • Se os resultados da tabela verdade são diferentes, então não são equivalentes 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 34 Equivalência de expressões Lógicas ● Exemplo 1: ● Exemplo 2: 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 35 Exercícios • Faça a tabela-verdade dos circuitos combinatórios (portas lógicas): 1) 2) 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 36 Exercícios 3) Represente a função F = A.B + A.B usando portas lógicas e a tabela verdade (tabela de combinações). 4) Verifique se as expressões abaixo são equivalentes: 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 37 Exercícios 5) Dadas as seguintes proposições: A = 3, B = 10, C = 21 e D = 8 Determine o resultado de: a) A < B b) ~(C < B) c) (A > D) + (C > D) d) (C < B) + ~(A < A) e) ~((D < B) . (C < B)) f) (B > C) + (A > D) g) (C < D) + ((D < A) . ((A < D) + (B > D))) h) ~(D > C) + ~(A > B) i) ~(((A < D) + (A = B)) . (A < 3)) j) (9 > C) + (C < C) . ~(D > 2) 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 38 Agradecimentos • Ao Prof. Dr. Bruno Feres, do BCT/UFMA • Ao Prof. Dr. Sergio Souza Costa, do BCT/UFMA • Ao Prof. Me. Geraldo Braz, DEINF/UFMA • Ao Prof. Me. Osvaldo Silva Sousa Junior, NTI/UFMA 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 39 Referências • TANENBAUM, A. S. Organização Estruturada de Computadores. 5ª Ed. São Paulo: Prentice-Hall, 2007. • MARÇULA, M.; BENINI FILHO, P. A. Informática Conceitos e Aplicações. 3ª Ed. São Paulo: Érica, 2008; • VELLOSO, F. C. Informática Conceitos Básicos. 8.ed. Rio de Janeiro: Elsevier, 2011. 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 40 Perguntas.... 09/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 41
Compartilhar