08-boole

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

Álgebra de Boole
Sumário
• Estrutura e Modelos
• Definições e Propriedades
• Isomorfismo
• As mesmas propriedades matemáticas 
podem ser observadas em contextos 
diferentes?
Modelos e Generalizações
• Uma estrutura matemática é um 
conjunto abstrato de objetos, junto com 
operações ou relações bem definidas 
entre eles 
‣ modelo formal que descreve propriedades 
específicas (que podem ser comuns a 
diferentes sistemas);
‣ generalização que captura um conjunto de 
caraterísticas essenciais;
Definição
Uma álgebra de Boole é um conjunto B no qual estão 
definidas duas operações binárias, + e ⋅, e uma operação 
unária, ′, e que contém dois elementos distintos, 0 e 1, tais 
que as seguintes propriedades são válidas, quaisquer que 
sejam x, y, z ∈ B:
x+y = y+x x⋅y = y⋅x Comutatividade
(x+y)+z= x+(y+z) (x⋅y)⋅z= x⋅(y⋅z) Associatividade
x+(y⋅z)=(x+y)⋅(x+z) x⋅(y+z)=(x⋅y)+(x⋅z) Distributividade
x+0 = x x⋅1 = x Elemento neutro
x+x′ = 1 x⋅x′ = 0 Complemento
• A Álgebra de Boole é uma estrutura 
matemática.
‣ A Lógica Proposicional é uma álgebra de boole
‣ A Teoria dos Conjuntos é uma álgebra de boole
‣ A Álgebra de Boole caracteriza formalmente as 
propriedades comuns entre Lógica proposicional 
e a Teoria dos Conjuntos.
‣ A aritmética de inteiros não é uma álgebra de 
boole
Notação
• Podemos denotar uma álgebra de boole 
por [ B, +, ⋅, ′, 0, 1 ]
• Qualquer modelo matemático que seja 
uma álgebra de boole possui
‣ as operações +, ⋅ e ′ 
‣ os elementos 0 e 1
‣ as propriedades especificadas.
Complemento
• Se x é um elemento de uma álgebra de 
boole, o elemento x′ é denominado o 
complemento de x.
• O complemento é único.
Propriedades
• A formalização permite identificar as 
propriedades comuns a todos os modelos
• Se demonstrarmos uma nova 
propriedade, esta nova propriedade será 
válida para qualquer álgebra de boole
‣ ela também poderá ser usada para demonstrar 
outras propriedades.
Idempotência
A propriedade de idempotência da soma
x + x = x
é valida em qualquer álgebra de boole.
Exemplo
• Usando as propriedades de uma álgebra 
de boole, demonstre que a idempotência 
da soma é válida.
Exemplo
• Usando as propriedades de uma álgebra 
de boole, demonstre que a idempotência 
da soma é válida.
 x+x = (x+x)⋅1 
 = (x+x)⋅(x+x′)
 = x + (x⋅x′)
 = x+0
= x
Propriedade Dual
• Cada propriedade em uma álgebra de 
Boole tem a sua propriedade dual
• A propriedade dual é obtida 
permutando-se + com ⋅ e 1 com 0.
• Exemplos
Propriedade Propriedade Dual
x + x = x x⋅x = x
x+0 = x x⋅1 = x
Exemplo
• Como fica a idempotência da soma no 
contexto de lógica proposicional?
• E no contexto de teoria dos conjuntos?
Exemplo
• Como fica a idempotência da soma no 
contexto de lógica proposicional?
• E no contexto de teoria dos conjuntos?
P ∨ P = P
Exemplo
• Como fica a idempotência da soma no 
contexto de lógica proposicional?
• E no contexto de teoria dos conjuntos?
P ∨ P = P
A ∪ A = A
Exemplo
• Prove que propriedade x+1 = 1 é válida 
em qualquer álgebra de boole.
• Qual é a propriedade dual?
Exemplo
• Prove que propriedade x+1 = 1 é válida 
em qualquer álgebra de boole.
• Qual é a propriedade dual?
 x+1 = x + (x+x′)
 = (x+x)+x′
 = x+x′
= 1
Exemplo
• Prove que propriedade x+1 = 1 é válida 
em qualquer álgebra de boole.
• Qual é a propriedade dual?
 x+1 = x + (x+x′)
 = (x+x)+x′
 = x+x′
= 1
x⋅0 = 0
Exercício
• Prove que o complemento é único.
Isomorfismo
• Duas instâncias de uma estrutura são 
isomorfas se existe uma bijeção que 
relaciona os elementos de uma instância aos 
elementos da outra, de modo que as 
propriedades são preservadas.
‣ Cada instância é uma imagem espelhada da outra.
‣ As duas instâncias são, essencialmente, iguais.
Isomorfismo
• Um isomorfismo é uma bijeção que 
preserva as propriedades relevantes. 
• Exemplo: Sejam (S1,ρ) e (S2,σ) dois 
conjuntos parcialmente ordenados.
‣ S1 = {1,2,3,5,6,10,15,30}; x ρ y ↔ x divide y
‣ S2 = ℘({1,2,3}); A σ B ↔ A ⊆ B
‣ S1 e S2 são isomorfos
• A função bijetora f é um isomorfismo do 
conjunto parcialmente ordenado (S1,ρ) no 
conjunto parcialmente ordenado (S2, σ)
‣ as propriedades são preservadas!
f: {1,2,3,5,6,10,15,30} → ℘({1,2,3})
f(1) = ∅
f(2) = {1}
f(3) = {2}
f(5) = {3}
f(6) = {1,2}
f(10) = {1,3}
f(15) = {2,3}
f(30) = {1,2,3}
A função f-1 é um isomorfismo 
de (S2, σ) em (S1, ρ).
É fácil encontrar um isomorfismo 
entre duas instâncias?
Considere o caso de uma estrutura matemática 
mais complexa, como uma álgebra de Boole.
O isomorfismo precisa preservar também o 
comportamento das operações!
efetuar a operação e 
aplicar a bijeção
aplicar a bijeção e 
efetuar a operação=
a, b c
operação
r, s
bijeção bijeção
t
operação
f(a) = r
f(b) = s
f(c) = t
Isomorfismo de Álgebras de Boole
• Sejam A1 e A2 álgebras de Boole.
‣ A1 = [B, +, ×, ′, 0, 1] e A2 = [C, ⊕, ⊗, ″, ∅, ⊥]
• Uma função f: B→C é um isomorfismo de 
A1 em A2 se:
1. f é uma bijeção
2. f( x + y) = f(x) ⊕ f(y)
3. f( x × y) = f(x) ⊗ f(y) 
4. f(x′) = (f(x))″
Exemplo
• Sejam A1 e A2 álgebras de Boole.
‣ A1 = [ {0, 1, a, a′}, +, ⋅, ′, 0, 1]
‣ A2 = [ ℘(S), ∪, ∩, ′, ∅, S], S = {1,2}
′⋅
Exemplo
• Então a função f, como definida a seguir, é 
um isomorfismo de A1 em A2
 f(0) = ∅
f(1) = S
 f(a) = {1}
 f(a′) = {2}
• Não é fácil determinar se duas instâncias 
de uma estrutura matemática são 
isomorfas.
• Porém, sabemos que
‣ Se B é uma álgebra de Boole com n 
elementos, então n = 2m para algum m e B é 
isomorfa a [℘(S), ∪, ∩, ′, ∅, S], S = {1, 2, ... , m}.