Lógica para computação - álgebra booleana

Prévia do material em texto

Profa. Fabrícia Damando 
fabriciadamando@gmail.com 
 
1 
Lógica para computação 
Álgebra Booleana 
Álgebra Booleana 
2 
 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. 
 
 George Boole desenvolveu no século XIX a álgebra necessária 
à investigação das leis fundamentais das operações da mente 
humana ligadas ao raciocínio. 
 
Álgebra Booleana 
3 
 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. 
 
 Enquanto a álgebra tradicional opera com relações quantitativas a 
álgebra de boole opera com relações lógicas 
 
 Ela também é o fundamento da matemática computacional, 
baseada em números binários. 
 
 Base da aritmética computacional 
Álgebra de Boole 
4 
 Em 1938, Claude Shannon, sugeriu que a álgebra booleana 
poderia ser usada para solucionar problemas relativos ao 
projeto de circuitos de comutação de relés 
 
 As técnica sugeridas por Shannon, foram usadas para análise e 
projeto de circuitos eletrônicos digitais 
Simbologia 
5 
 A álgebra booleana faz uso de variáveis e operações, ou, 
variáveis e operações lógicas 
 Constantes booleanas 
 1 (verdadeiro) 
 0 (falso) 
 Variável Booleana – representada por letra e pode assumir 
apenas 2 valores (0 ou 1) 
 Ex: A, B, C, .... 
 Operações lógicas 
 AND (e) 
 OR (ou) 
 NOT (não) 
Simbologia 
6 
 Uma expressão booleana é uma expressão matemática 
envolvendo expressões booleanas e seu resultado pode 
assumir apenas 2 valores: 
 S = A.B 
 S – A+B+C 
 
 A AND B = A . B 
 A OR B = A + B 
 NOT A = A 
 Operação AND com resultado verdadeiro (valor binário 1) 
 Ambos operandos têm valor verdadeiro 
 Operação OR com resultado verdadeiro 
 Se qualquer dos operandos ou ambos têm valor verdadeiro 
 Operação NOT inverte o valor do operando 
Operação OU + 
7 
 É similar à adição comum, mas a correspondência não é 
plena. 
 Símbolo usual é o mesmo da adição. 
 
 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). 
Operação AND 
8 
 É similar à multiplicação comum e há correspondência. 
 Símbolo usual é o mesmo da multiplicação. 
 
 X = A · B (lê-se X igual a A e B). 
 
 X= A AND B 
 Muitas vezes, também de forma semelhante à álgebra 
comum, o sinal de ponto é suprimido: 
 
 X = AB. 
 
 
Operação NOT 
9 
 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. 
 
 X = A (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'). 
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 AND 
 3) Operação NÃO 
AND 0 1 
0 0 0 
1 0 1 
10 
OU 0 1 
0 0 1 
1 1 1 
0 = Falso 1 = Verdadeiro 
Postulados 
11 
 Os postulados da álgebra de Boole definem os resultados das 
operações básicas. 
 Postulados da operação OR: 
 
 0 + 0 = 0 
 0 + 1 = 1 
 1 + 0 = 1 
 1 + 1 = 1 
 
Postulados 
12 
 Postulados da operação AND 
 
 0 · 0 = 0 
 0 · 1 = 0 
 1 · 0 = 0 
 1 · 1 = 1 
Postulados 
13 
 Postulados da operação NOT 
 
 -0 = 1 
 -1 = 0 
 
Propriedades 
14 
Álgebra de Boole x Álgebra Tradicional 
15 
 Enquanto que a álgebra tradicional opera com relações 
quantitativas, a álgebra de Boole opera com relações lógicas 
 
 Enquanto que na álgebra tradicional as variáveis podem 
assumir qualquer valor, na álgebra booleana, as variáveis, 
podem assumir um de dois valores binários. 
 
 Estes valores binários não exprimem quantidades mas 
apenas, e só, estados do sistema 
Operador Álgebra Tradicional Álgebra Booleana 
“ + “ Soma OR 
“ x “ Multiplicação AND 
16 
Álgebra de Boole x Álgebra Tradicional 
Operadores Booleanos – Tabela da verdade 
P Q NOT 
P 
P AND Q P OR Q P XOR Q P NAND Q P NOR Q 
0 0 1 0 0 0 1 1 
0 1 1 0 1 1 1 0 
1 0 0 0 1 1 1 0 
1 1 0 1 1 0 0 0 
17 
XOR – efetua a operação OU-exclusivo resultando em 1 se e somente se 
exatamente um dos operandos tem 1 
 
NAND – é o complemento (NOT) da função AND 
 
NOR - é o complemento de OR 
Postulados básicos 
18 
 0 . A = 0 
 1 + A = 1 
 A . A = A 
 A + A = A 
 
 Teorema De Morgan 
 A.B = A + B 
 A+B = A . B 
 Complemento 
 ¬¬A = A 
 ¬ 0 = 1 
 ¬ 1 = 0 
Postulados Básicos – “novamente” 
19 
 Leis da comutatividade 
 A . B = B . A 
 A + B = B + A 
 
 Leis da distributividade 
 A . (B + C) = (A . B) + (A . C) 
 A + (B . C) = (A + B) . (A + C) 
 
 Elemento identidade 
 1 . A = A 
 0 +A = A 
 
 Elemento inverso 
 A . A = 0 
 A +A = 1 
Simplificação por postulados e 
propriedades 
 A+ A.B = A 
 A + A.B DISTRIBUTIVA 
 A . (1 + B) IDENTIDADE DA ADIÇÃO 
 A. (1) IDENTIDADE DA MULTIPLICAÇÃO 
 A 
 
 
 
20 
Exemplo 
21 
Exercícios 
 Simplifique as expressões abaixo usando postulados e 
propriedades 
 
 A.(A+B) = A 
 A + Ā.B = A + B 
 (A+B).(A+C) = A + B.C 
22 
Aplicações 
23 
 A importância da lógica booleana no mundo digital é hoje 
indiscutível, sendo utilizada em áreas tão diversas como as 
memórias digitais; os circuitos discretos; ou os 
microprocessadores. 
Aplicações 
24 
 A álgebra Booleana de dois 
elementos é também 
utilizada em engenharia 
elétrica; 
 0 e 1 representam os dois 
diferentes estados de um bit 
em um circuito digital, 
tipicamente alta e baixa 
voltagem. 
 
Circuito digital gravado no FPGA 
25 
A B Y 
0 0 0 
0 1 0 
1 0 0 
1 1 1 
26 
AND 
A B Y 
0 0 0 
0 1 1 
1 0 1 
1 1 1 
OR 
A B Y 
0 0 1 
0 1 1 
1 0 1 
1 1 0 
NAND 
A B Y 
0 0 1 
0 1 0 
1 0 0 
1 1 0 
NOR 
A Y 
0 1 
0 0 
NOT 
Tabela Verdade 
 Tabela verdadeé um tipo 
de tabela matemática usada 
em Lógica para determinar 
se uma fórmula é válida. 
 
 Negação 
 Conjunção (E) 
 Disjunção (OU) 
 Condicional (se...então) 
 Bicondicional (se e 
somente se) 
 Disjunção exclusiva (XOR) 
 NOR 
27 
Exemplo 
28 
 Dada a expressão: 
 (A OR B) AND (NOT 
C) 
 Construa a tabela da 
verdade 
 
Exercício 
29 
1. Determine a expressão booleana que representa a tabela da 
verdade abaixo: 
 
 
 
 
 
2. Simplifique e otimize