Álgebra Booleana

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Introdução aos Sistemas 
Computacionais 
Disciplina: 113468 
 
Prof. Marcus Vinicius Lamar 
 
Álgebra Booleana 
UnB/CIC 113468– Introdução aos Sistemas Computacionais 
Álgebra Booleana 
 Desenvolvida por Geoge Boole por volta de 
1847, numa tentativa de formalizar o 
pensamento humano 
 Na álgebra Booleana, variáveis podem assumir 
apenas os valores 1 e 0 
 Define as operações lógicas AND, OR e NOT 
3 
 Ex.: 
 só vou ao estádio se for jogo da Seleção e Neymar jogar 
 F = 1, indica que vou ao estádio 
 Sejam a e b os times, Ta = 1 se a = Seleção; Tb = 1 se b = Seleção 
 N = 1 se Neymar vai jogar. 
 Então: F = (Ta OR Tb) AND N 
UnB/CIC 113468– Introdução aos Sistemas Computacionais 
Álgebra Booleana... 
 É uma estrutura algébrica ⟨ B, ⋀, ⋁, ¬, 0, 1 ⟩ onde: 
 B é um conjunto de elementos 
 ⋀ é o operador binário conjunção (AND) 
 ⋁ é o operador binário disjunção (OR) 
 ¬ é o operador unário negação (NOT) 
 0 e 1 são os elementos mínimo e máximo de B 
 
 Representação utilizada em engenharia 
 Produto lógico: x ⋀ y  x · y 
 Soma lógica: x ⋁ y  x + y 
 Complemento: ¬ x  x 
 
4 
UnB/CIC 113468– Introdução aos Sistemas Computacionais 
Axiomas da Álgebra Booleana... 
 Fechamento em B: 
 x ∧ y ∈ B x ⋅ y ∈ B 
 x ∨ y ∈ B x + y ∈ B 
 
 Identidade: 
 x ∧ 1 = x x ⋅ 1 = x 
 x ∨ 0 = x x+0 = x 
 
 Complemento: 
 ¬ x ∧ x = 0 x ⋅ x = 0 
 ¬ x ∨ x = 1 x + x = 1 
5 
Lógica Proposicional: Eletrônica Digital: 
UnB/CIC 113468– Introdução aos Sistemas Computacionais 
Axiomas da Álgebra Booleana... 
 Associatividade: 
x ∧ (y ∧ z) = (x ∧ y) ∧ z x⋅ y⋅z = x⋅y ⋅z 
x ∨ (y ∨ z) = (x ∨ y) ∨ z x+ y+z = x+y +z 
 
 Comutatividade: 
x ∧ y = y ∧ x x⋅y = y⋅x 
x ∨ y = y ∨ x x+y = y+x 
 
 Distributividade: 
x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z) x⋅ y+z = x⋅y + x⋅𝑧 
x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z) x+ y⋅z = x+y ⋅ x+𝑧 
6 
UnB/CIC 113468– Introdução aos Sistemas Computacionais 
Teoremas de De Morgan 
 O complemento do produto lógico das variáveis x e y 
corresponde à soma lógica do complemento das variáveis 
 
 
 
 O complemento da soma lógica das variáveis x e y 
corresponde ao produto lógico do complemento das variáveis 
 
 
Exercício provar 
7 
 x y x y    
 x y x y    
 x.y x y 
 x y x . y 
UnB/CIC 113468– Introdução aos Sistemas Computacionais 
Avaliando Expressões Booleanas 
 F = (a AND b) OR (c AND d) 
 
 a = 1, b = 0, c = 1, d = 0 
 F = (1 AND 0) OR (1 AND 0) = 0 OR 0 = 0 
 a = 0, b = 1, c = 1, d = 1 
 F = (0 AND 1) OR (1 AND 1) = 0 OR 1 = 1 
 a = 1, b = 1, c = 1, d = 1 
 F = (1 AND 1) OR (1 AND 1) = 1 OR 1 = 1 
8 
UnB/CIC 113468– Introdução aos Sistemas Computacionais 
Formulando Expressões Booleanas 
 O alarme de um carro deve tocar se ele estiver ligado e 
o carro for sacudido ou um dos 4 sensores de janela for 
acionado 
 
 Deve-se atribuir variáveis Booleanas a cada condição e elaborar 
a expressão que indica quando o alarme deve tocar 
 L = alarme ligado 
 j1, j2, j3 e j4, sensores das janelas 
 s é o sensor de movimento do carro que indica se ele é movido 
ou sacudido 
 a = 1 indica que o alarme é acionado 
 
 a = L AND (s OR j1 OR j2 OR j3 OR j4) 
9 
UnB/CIC 113468– Introdução aos Sistemas Computacionais 
Construindo Circuitos Lógicos 
 Acendimento automático de luz em ambientes 
 detectar movimento no ambiente (a=1) 
 se luz do ambiente estiver apagada (b=0), acender lâmpada (F=1) 
 
 F = a AND NOT(b) 
10 
UnB/CIC 113468– Introdução aos Sistemas Computacionais 
Mapeando Expressões em Circuitos 
 Procedimento: começar pela saída, associando portas 
lógicas aos operadores até alcançar as entradas 
 Ex.: F = a AND NOT(b OR NOT(c)) 
11 
F 
AND 
a 
NOT 
OR 
NOT b 
c 
UnB/CIC 113468– Introdução aos Sistemas Computacionais 
Exemplos 
12 
UnB/CIC 113468– Introdução aos Sistemas Computacionais 
Alarme de Cinto de Segurança 
Cinto de Segurança 
Alarme 
s 
c 
a 
 Sensores: 
 s = 1: cinto de segurança afivelado 
 c = 1: chave inserida 
 a = 1: alarme acionado 
 Expressão Booleana: 
 cinto não afivelado e chave inserida 
 a = NOT(s) AND c 
 
 Mapear expressão em circuito 
 
 Diagrama de tempo: 
13 
c 
s 
a 
1 
0 
1 
0 
1 
0 
tempo 
UnB/CIC 113468– Introdução aos Sistemas Computacionais 
Terminologia Booleana 
 Termo produto 
produto (AND): a’bc, a’b’c, ab a .b.c, a .b .c, a.b 
 Soma de produtos 
F(a,b,c) = (a’bc) + (a’b’c) + (ab) F a,b,c = a .b.c + a .b .c +ab 
 
 Termo soma 
soma (OR): a’+b+c, a’+b’+c, a+b a +b+c, a +b +c, a+b 
 Produto de somas 
F(a,b,c) = (a’+b+c).(a’+b’+c).(a+b) F a,b,c = a +b+c . a +b +c .(a+b) 
14 
UnB/CIC 113468– Introdução aos Sistemas Computacionais 
Precedência dos Operadores Booleanos 
 Precedência: 
 1. ( ) => avalia primeiro conteúdo dos parênteses 
 2. NOT 
 3. AND avaliados da esquerda para a direita 
 4. OR 
F = a.b + c F = a + b.c 
1. a.b 1. b.c 
2. a.b + c 2. a + b.c 
F = (a + b’).c + d’ F = a + b’.(c + d’) 
1. b’ 1. d’ 
2. a + b’ 2. c+d’ 
3. (a + b’).c 3. b’.(c+d’) 
4. (a + b’).c + d’ 4. a+ b’.(c+d’) 
15 
UnB/CIC 113468– Introdução aos Sistemas Computacionais 
Construindo uma Tabela Verdade 
 F = (a + b’).c 
16 
a b c F 
F = (0 + 0’).0 = (0 + 1).0 = 1.0 = 0 0 0 0 0 
F = (0 + 0’).1 = (0 + 1).1 = 1.1 = 1 0 0 1 1 
F = (0 + 1’).0 = (0 + 0).0 = 0.0 = 0 0 1 0 0 
F = (0 + 1’).1 = (0 + 0).1 = 0.1 = 0 0 1 1 0 
F = (1 + 0’).0 = (1 + 1).0 = 1.0 = 0 1 0 0 0 
F = (1 + 0’).1 = (1 + 1).1 = 1.1 = 1 1 0 1 1 
F = (1 + 1’).0 = (1 + 0).0 = 1.0 = 0 1 1 0 0 
F = (1 + 1’).1 = (1 + 0).1 = 1.1 = 1 1 1 1 1 
UnB/CIC 113468– Introdução aos Sistemas Computacionais 
Obtendo uma Expressão Booleana para 
uma Tabela Verdade 
 Ex.: função paridade - 1 se número ímpar de bits 1 na entrada 
 construir uma soma de produtos 
com um termo produto para cada 1 
que aparece na coluna F 
F = a’b’c + a’bc’ + ab’c’ + abc 
 
 construir um produto de somas 
com um termo soma para cada 0 
que aparece na coluna F 
F = (a+b+c) . (a+b’+c’) . (a’+b+c’) . (a’+b’+c) 
 
 
 Existem outros métodos mais eficientes 
 
17 
a b c F 
0 0 0 0 
0 0 1 1 
0 1 0 1 
0 1 1 0 
1 0 0 1 
1 0 1 0 
1 1 0 0 
1 1 1 1 
UnB/CIC 113468– Introdução aos Sistemas Computacionais UnB/CIC 113468 – Introdução aos Sistemas Computacionais 
Exemplo de Simplificação com Álgebra 
Booleana 
18 
 Controle de fechadura eletrônica para uma porta 
 saída: F = 1 abre a porta F = 0 não abre a porta 
 entradas: 
 c=1: porta chaveada 
 a=1: interruptor para manter porta aberta acionado 
 p=1: pessoa detectada 
 Acionar abertura quando: 
 c = 0 e a = 1 ou 
 c = 0 e a = 0 e p = 1 
 Equação: 
 F = ac’ + a’pc’ 
UnB/CIC 113468– Introdução aos Sistemas Computacionais 
Simplificação 
19 
 
    
    
 
. . . (comutatividade)
. . . (distributividade)
. . (distributividade)
. . (complemento)
. 1 . (identidade)
.
F a c a p c
c a c a p
c a a p
c a a a p
c a p
c a p
 
 
 
  
 
 
 Obs.: x y z (x y) (x z)     