Algebra Booleana

Prévia do material em texto

1
Álgebra Álgebra BooleanaBooleana
Aula 1Aula 1
Prof Dr Luiz Antônio Pereira NevesProf Dr Luiz Antônio Pereira Neves
Prof Neves - Algebra Booleana 1 2
Objetivos
• Compreender a aritmética da Álgebra 
Booleana
• Identificar os Conceitos Básicos
• Analisar os exemplos apresentados
2
Prof Neves - Algebra Booleana 1 3
Álgebra Booleana
• A álgebra de Boole é um conjunto de 
postulados e operações lógicas com 
variáveis binárias desenvolvido pelo 
matemático e filósofo inglês George 
Boole (1815-1864). 
• George Boole foi o primeiro a defini-
las como parte de um sistema de 
lógica em meados do século XIX.
• A álgebra booleana foi uma tentativa 
de utilizar técnicas algébricas para 
lidar com expressões no cálculo 
proposicional. 
Hoje, as álgebras booleanas têm muitas aplicações na eletrônica. Foram pela 
primeira vez aplicadas a interruptores por Claude Shannon, no século XX. 
Prof Neves - Algebra Booleana 1 4
Conceitos
• Também conhecida como Álgebra de Boole.
• Na matemática e na ciência da computação, as 
álgebras booleanas são estruturas algébricas que 
"capturam a essência" das operações lógicas E, OU e
NÃO, bem como das operações da teoria de 
conjuntos soma, produto e complemento. 
• Ela também é o fundamento da matemática 
computacional, baseada em números binários. 
3
Prof Neves - Algebra Booleana 1 5
Aplicações
• A álgebra Booleana de dois 
elementos é também utilizada no 
c em engenharia elétrica; aqui 0 e 
1 representam os dois diferentes 
estados de um bit em um circuito 
digital, tipicamente alta e baixa 
voltagem. 
• Os circuitos são descritos por 
expressões contendo variáveis, e 
as tais duas expressões são 
iguais para todos os valores das 
variáveis se e somente se o 
circuito correspondente tiver o 
mesmo comportamento de 
entrada-saída. 
Prof Neves - Algebra Booleana 1 6
Simbologias
• É freqüente serem simplesmente escritos como E, OU ou NÃO (são 
mais comuns os seus equivalentes em inglês: AND, OR e NOT).
• Na descrição de circuitos também podem ser utilizados NAND 
(NOT AND), NOR (NOT OR) e XOR (OR exclusivo). 
• Os matemáticos usam com freqüência + para OU e . para E (visto 
que sob alguns aspectos estas operações são análogas à adição e 
multiplicação noutras estruturas algébricas) e representam NÃO 
com uma linha traçada sobre a expressão que está a ser negada.
• Outra notação comum, com ^ (ou ^ para browsers que não 
suportam esse caracter) para E, V (ou v) para OU, e ¬ (ou ~) para 
NÃO.
4
Prof Neves - Algebra Booleana 1 7
Simbologias
Prof Neves - Algebra Booleana 1 8
Variáveis
Uma variável booleana representa um dígito binário, ou seja, só pode 
ter os valores 0 ou 1. Matematicamente pode-se dizer que o domínio 
de uma variável é o conjunto
B = {0, 1} e uma variável genérica X é elemento desse conjunto, X 
pertence a B.
São comuns, para os valores 0 e 1, as designações falso e 
verdadeiro, respectivamente.
5
Prof Neves - Algebra Booleana 1 9
Operações Básicas
As operações fundamentais da álgebra de Boole têm semelhança com
operações aritméticas comuns, inclusive alguns símbolos são 
idênticos, mas não são necessariamente coincidentes:
1) Operação OU
2) Operação E
3) Operação NÃO 101
000
10E
111
100
10OU
0 é interpretado como "falso“ e 1 é "verdadeiro”
Prof Neves - Algebra Booleana 1 10
Operações Básicas
Operação OU
É similar à adição comum, mas a correspondência não é plena. 
Símbolo usual é o mesmo da adição. 
Exemplo:
X = A + B (lê-se X igual a A ou B). 
Um outro símbolo, comum em linguagem de programação, é a barra 
vertical (X = A | B). 
6
Prof Neves - Algebra Booleana 1 11
Operações Básicas
Operação E
É similar à multiplicação comum e há correspondência, como 
poderá ser visto adiante. Símbolo usual é o mesmo da 
multiplicação.
Exemplo:
X = A · B (lê-se X igual a A e B). 
Muitas vezes, também de forma semelhante à álgebra comum, o 
sinal de ponto é suprimido: X = AB. 
O e comercial (&) é um símbolo usado em algumas linguagens 
(X = A & B). 
Prof Neves - Algebra Booleana 1 12
Operações Básicas
Operação NÃO
Também denominada negação ou complemento, pode ser 
considerada similar ao negativo da álgebra comum. 
Entretanto, não há correspondência plena porque a álgebra de Boole 
não usa sinal negativo. Símbolo usual é uma barra acima (ou 
antes) da variável. 
Exemplo:
X = Ã (lê-se X igual a não A). Alguns outros símbolos são o sinal 
de exclamação (X = !A) e o apóstrofo (X = A'). 
7
Prof Neves - Algebra Booleana 1 13
Postulados
• Os postulados da álgebra de Boole definem os resultados das 
operações básicas informadas no tópico anterior.
Postulados da operação OU
0 + 0 = 0 
0 + 1 = 1 
1 + 0 = 1 
1 + 1 = 1 
Algumas referências escrevem postulados da 
adição. Mas lembrar que é adição booleana, 
não equivale plenamente à adição comum 
porque, para esta última, 1 + 1 deve ser 0.
Algumas referências escrevem postulados da 
adição. Mas lembrar que é adição booleana, 
não equivale plenamente à adição comum 
porque, para esta última, 1 + 1 deve ser 0.
Prof Neves - Algebra Booleana 1 14
Postulados
Postulados da operação E
0 · 0 = 0 
0 · 1 = 0 
1 · 0 = 0 
1 · 1 = 1 
Em algumas referências, são denominados 
postulados da multiplicação. Notar que há 
equivalência plena com a multiplicação 
comum. 
Em algumas referências, são denominados 
postulados da multiplicação. Notar que há 
equivalência plena com a multiplicação 
comum. 
8
Prof Neves - Algebra Booleana 1 15
Postulados
Postulados da operação NÃO
-0 = 1 
-1 = 0 
Prof Neves - Algebra Booleana 1 16
Exercício 1
Omitindo as demonstrações, algumas identidades podem ser 
deduzidas a partir dos postulados acima:
a) Da operação OU
X + 0 = ?
X + 1 = ? 
X + X = ? 
b) Da operação E
X · 0 = ?
X · 1 = ? 
X · X = ? 
c) Da operação NÃO
- - X = ?
a) Da operação OU
X + 0 = X 
X + 1 = 1 
X + X = X 
X + X = 1 
b) Da operação E
X · 0 = 0 
X · 1 = X 
X · X = X 
X · X = 0 
c) Da operação NÃO
- - X = X 
Solução
9
Prof Neves - Algebra Booleana 1 17
Propriedades e Teoremas
1) Propriedade comutativa
A + B = B + A 
A · B = B · A 
2) Propriedade associativa
A + (B + C) = A + (B + C) = A + B + C 
A · (B · C) = A · (B · C) = A · B · C 
3) Propriedade distributiva
A · (B + C) = A·B + A·C
4) Teoremas de Morgan
Prof Neves - Algebra Booleana 1 18
Função Booleana
10
Prof Neves - Algebra Booleana 1 19
Exemplo
Prof Neves - Algebra Booleana 1 20
Trabalho 1
• Desenvolva uma pesquisa sobre as Redes e Portas Lógicas e sua 
Aplicação.
• Temas:
– Expressão Booleana
– Função Verdade
– Portas Lógicas
• Leia o resumo “Algebra_booleana.pdf” que está no site do Professor 
como material de suporte.
• Faça um artigo (usando regras da ABNT) com a seguinte 
metodologia:
– Introdução (Conceitos e Escopo da Pesquisa)
– Desenvolvimento (Explicações do Uso de Portas lógicas e dois 
estudos de caso como exemplos, usando portas lógicas com funções 
algébricas)
– Conclusão (Justificativas, relevância do uso e opinião da equipe)
• Data de entrega: quarta-feira (04/06/2008)
11
Prof Neves - Algebra Booleana 1 21
Link interessante
• http://www.inf.ufsc.br/ine5365/algboole.html
Prof Neves - Algebra Booleana 1 22
Conclusões
A álgebra booleana é 
importante na ciência 
computacional 
Uso da tabela verdade nas 
expressões algébricas
O conhecimento da álgebra 
booleana é fundamental para 
compreender o comportamento 
dos circuitos
12
Prof Neves - Algebra Booleana 1 23
Contato
• Prof. Dr. Luiz Antônio Pereira Neves
– neves@sbs.udesc.br
– www.ppgia.pucpr.br/~neves