apresentacao_aula_7

Prévia do material em texto

Fundamentos de Computação
Bruno Feres de Souza
bferes@gmail.com
Universidade Federal do Maranhão
Bacharelado em Ciência e Tecnologia
1° semestre de 2013
Na aula passada...
● George Boole (1815-1864): filósofo, 
matemático e lógico inglês
– Sistema matemático de análise lógica
• Palavras, frases e proposições são expressas por 
símbolos, como X, Y e Z.
• Relação entre símbolos é feita por meio de 
operações, como soma e multiplicação.
• Resolução de uma equação nesse contexto leva a 
uma conclusão lógica. 
– “Álgebra do pensamento”: Álgebra booleana
Álgebra booleana
Introdução: Histórico
● Álgebra booleana difere da álgebra tradicional 
em três aspectos principais:
– Nos valores que os símbolos podem assumir
– Nas operações aplicáveis a esses símbolos
– Nas propriedades dessas operações
● Álgebra tradicional
– Variáveis são números reais
– Resultados das operações são números reais
● Álgebra booleana
– Variáveis são entidades lógicas (V ou F)
– Resultados das operaçoes são V ou F
Álgebra booleana
Introdução: Definições
● Considere:
– X = jovem
– Y = faz BCT
● Assim:
– (1-X): tudo que não é jovem
– (XY): tudo que é jovem e faz BCT
– (X+Y): tudo que é jovem ou faz BCT
● Do exemplo, define-se:
– Expressão booleana: 0, 1 e literais separados por 
operadores 
– Literal: nome de uma variável, em sua forma negada ou 
não 
– Variável booleana: X e Y, assumindo 0 ou 1
– Função booleana: expressão booleana específica. F(X,Y) 
= X+Y
Álgebra booleana
Introdução: Definições
● Por que estudar lógica booleana?
– Computador realiza operações lógicas e 
aritméticas sobre bits
– Dispositivos eletrônicos biestáveis
– Ferramenta matemática atualmente utilizada 
para entender o comportamento circuitos lógicos
• Claude Elwood Shannon (1938): análise e 
projeto de circuitos elétricos de chaveamento.
Álgebra booleana
Introdução: Por que estudar?
● Função: realiza a multiplicação booleana de 
duas ou mais variáveis binárias
● Notação de S = A and B
– S=AB, S=A.B,
● Representação por tabela verdade
– Tabela na qual são exibidas todas as possíveis 
entradas e saídas de uma expressão booleana
– Para n variáveis booleanas, há 2^n 
Álgebra booleana
Operações lógicas: E (AND)
● Implementação por porta lógica
– Circuito que executa a operaçao AND
– Respeita a tabela verdade correspondente
● Gráfico da porta lógica
– S = AB
– S = ABCD...N
Álgebra booleana
Operações lógicas: E (AND)
● Função: realiza a soma booleana de duas ou 
mais variáveis binárias
● Notação de S = A or B
– S=A+B,
Álgebra booleana
Operações lógicas: OU (OR)
Porta lógica de S:Tabela verdade de S:
● Função: realiza a negação booleana de uma 
variável binária. Chamada de inversora.
● Notação de S = not A
– S=A' S=1-A, , 
Álgebra booleana
Operações lógicas: NÃO (NOT)
Porta lógica de S:Tabela verdade de S:
● Função: realiza a mutiplicação booleana de 
duas ou mais variáveis binárias e inverte o 
resultado 
● Notação de S = A nand B
– S= , S= , S=
Álgebra booleana
Operações lógicas: NÃO E (NAND)
Porta lógica de S:Tabela verdade de S:
● Função: realiza a soma booleana de duas ou 
mais variáveis binárias e inverte o resultado 
● Notação de S = A nor B
– S= , S= , S=
Álgebra booleana
Operações lógicas: NÃO OU (NOR)
Porta lógica de S:Tabela verdade de S:
● Função: realiza verificação de desigualdade 
entre as entradas 
● Notação de S = A xor B
– S=
Álgebra booleana
Operações lógicas: OU Exclusivo (XOR)
Porta lógica de S:Tabela verdade de S:
Álgebra booleana
Operações lógicas: Resumo
● Representação por expressões booleanas
– Precedência na avaliação:
• Respeitar os parênteses
• Avaliar a inversão
• Avaliar a multiplicação
• Avaliar a adição
Álgebra booleana
Composição de operações lógicas: Expressões booleanas
● Representação por circuitos lógicos
– Todo circuito lógico executa uma expressão booleana
– Um circuito, por mais complexo que seja, é composto 
pela interligação de portas lógicas.
Álgebra booleana
Composição de operações lógicas: Circuitos lógicos
● Exemplo 1
Álgebra booleana
Composição de operações lógicas: Exemplos
● Exemplo 2
Álgebra booleana
Composição de operações lógicas: Exemplos
● Exemplo 3
Álgebra booleana
Composição de operações lógicas: Exemplos
● Exemplo 4
Álgebra booleana
Composição de operações lógicas: Exemplos
● Exemplo 5
Álgebra booleana
Composição de operações lógicas: Exemplos
● Exemplo 6
Álgebra booleana
Composição de operações lógicas: Exemplos
● Exemplo 7
Álgebra booleana
Composição de operações lógicas: Exemplos
● Tabela verdade
– Expressão → Tabela verdade
– Circuito → Expressão → Tabela verdade
● Como obter?
– Colocar todas as situações para as n variáveis de 
entrada (2^n)
– Adicionar colunas para cada subfórmula da expressão
– Adicionar coluna para o resultado final
Álgebra booleana
Composição de operações lógicas: Comportamento lógico
● Exemplo 1
Álgebra booleana
Composição de operações lógicas: Comportamento lógico
● Exemplo 2
Álgebra booleana
Composição de operações lógicas: Comportamento lógico
● Exemplo 3
Álgebra booleana
Composição de operações lógicas: Comportamento lógico
● Dadas as expressões booleanas do slide 15
– Desenhe os circuitos lógicos correspondentes
– Construa as tabelas verdades
● Dados os circuitos lógicos do slide 16
– Escreva as expressõe booleanas correspondentes
– Construa as tabelas verdades
Álgebra booleana
Composição de operações lógicas: Exercícios
● Um circuito lógico equivale a apenas uma 
expressão booleana
● 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
Álgebra booleana
Equivalência de expressões lógicas
● Exemplo 1
Álgebra booleana
Equivalência de expressões lógicas: Exemplos
● Exemplo 2
Álgebra booleana
Equivalência de expressões lógicas: Exemplos
● Exemplo 3
Álgebra booleana
Equivalência de expressões lógicas: Exemplos
● Exemplo 4
Álgebra booleana
Equivalência de expressões lógicas: Exemplos
● As expressões abaixo são equivalentes?
Álgebra booleana
Equivalência de expressões lógicas: Exercícios
● Próxima aula...
Álgebra booleana
Simplificação de expressões lógicas
Cálculo eletrônico
2ª Geração (1955-1965): transistores
Material didático
● Organização e Arquitetura de Computadores (Eliane Mariade 
Bortoli Fávero). Capítulo 3.
● redeetec.mec.gov.br/images/stories/pdf/eixo_infor_comun
/tec_inf/081112_org_arq_comp.pdf
● Álgebra Booleana e Circuitos Lógicos – Notas de aula 
(Antonio Carlos Schneider Beck Filho e Júlio Carlos Balzano 
de Mattos).
● ftp://ftp.unilins.edu.br/balbino/NocoesLogica/Aula06%20-
%20Algebra%20Booleana%20e%20Circuitos
%20Logicos.pdf
Dúvidas?
● Estes slides foram baseados em apresentação 
do Prof. José Augusto Baranauskas, do Depto 
de Computação e Matemática do FFCLRP-USP, 
ministrada em 2012.
Agradecimentos