estruturas_algebricas

Prévia do material em texto

Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Estruturas Alge´bricas
Prof. Dr. Leandro Balby Marinho
Matema´tica Discreta
Prof. Dr. Leandro Balby Marinho 1 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Roteiro
1. Introduc¸a˜o
2. Estruturas Alge´bricas Ba´sicas
3. Reticulados
4. A´lgebras Booleanas
5. Homomorfismos e Isomorfismos
6. Outras Estruturas Alge´bricas
Prof. Dr. Leandro Balby Marinho 2 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Introduc¸a˜o
I Algumas vezes, propriedades matema´ticas ou operac¸o˜es semelhantes
podem ser observadas em contextos diferentes.
I Modelos matema´tica sa˜o utilizados para capturar essas propriedades
comuns.
I Esses modelos sa˜o expressos atrave´s de estruturas matema´ticas:
conjuntos + operac¸o˜es sobre esses conjuntos.
Prof. Dr. Leandro Balby Marinho 2 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Introduc¸a˜o
Considere algumas das identidades da lo´gica proposicional e conjuntos
abaixo. Voceˆ alguma estrutura em comum entre elas?
Identidade (lo´gica) Identidade (conjuntos) Nome
p ∨ q ≡ q ∨ p A ∪ B = B ∪ A Leis Comutativas
p ∧ q ≡ q ∧ p A ∩ B = B ∩ A
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) A ∪ (B ∪ C ) = (A ∪ B) ∪ C Leis Associativas
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r) A ∩ (B ∩ C ) = (A ∩ B) ∩ C
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C ) Leis Distributivas
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) A ∪ (B ∩ C ) = (A ∪ B) ∩ (A ∪ C )
p ∨ F = p A ∪ ∅ = A Elementos Neutros
p ∧ T = p A ∩ U = A
p ∨ ¬p ≡ T A ∪ A¯ = U Leis de Complemento
p ∧ ¬p ≡ F A ∩ A¯ = ∅
Prof. Dr. Leandro Balby Marinho 3 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Roteiro
1. Introduc¸a˜o
2. Estruturas Alge´bricas Ba´sicas
3. Reticulados
4. A´lgebras Booleanas
5. Homomorfismos e Isomorfismos
6. Outras Estruturas Alge´bricas
Prof. Dr. Leandro Balby Marinho 4 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Estruturas Alge´bricas
Definic¸a˜o 1
Uma estrutura alge´brica consiste de um conjunto associado a uma ou mais
operac¸o˜es fechadas sobre esse conjunto satisfazendo certos axiomas.
I Denotamos uma estrutura alge´brica por 〈C ,F〉 onde C denota um
conjunto arbitra´rio e F um conjunto de operac¸o˜es em C .
I Estruturas alge´bricas tambe´m sa˜o chamadas de a´lgebras ou a´lgebras
universais.
Prof. Dr. Leandro Balby Marinho 4 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Operac¸o˜es
Definic¸a˜o 2
Uma operac¸a˜o n-a´rea em um conjunto A e´ uma func¸a˜o
f : A× A× . . .× A︸ ︷︷ ︸
n vezes
→ A
Notac¸a˜o
Dada uma a´lgebra 〈C ,+〉, com
+ : C × C → C
para +(a, b) = c escrevemos a + b = c .
Prof. Dr. Leandro Balby Marinho 5 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Exemplos de Estruturas Alge´bricas
Exemplo 1: Seja 〈C ,F〉 onde C = R e F = {s,m}, onde s e m
sa˜o duas func¸o˜es bina´rias dadas por
s : R2 → R tal que s(x , y) = x + y e
m : R2 → R tal que m(x , y) = x · y
Ou de forma equivalente 〈R,+, ·〉
Prof. Dr. Leandro Balby Marinho 6 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Propriedades das Operac¸o˜es
Dada uma a´lgebra 〈C , ◦〉, onde ◦ representa uma operac¸a˜o bina´ria qual-
quer, as seguintes propriedades podem ser va´lidas, para quaisquer x , y , z
de C :
x ◦ y = y ◦ x (Comutativa)
(x ◦ y) ◦ z = x ◦ (y ◦ z) (Associativa)
∃e ∈ C : (x ◦ e = x) (Identidade)
∀x ∈ C ∃x ′ ∈ C : (x ◦ x ′ = e) (Inverso)
Exerc´ıcio 1: Analise a estrutura 〈Z,+〉 de acordo com as propriedades
acima, onde + e´ a soma usual entre dois inteiros.
Prof. Dr. Leandro Balby Marinho 7 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Roteiro
1. Introduc¸a˜o
2. Estruturas Alge´bricas Ba´sicas
3. Reticulados
4. A´lgebras Booleanas
5. Homomorfismos e Isomorfismos
6. Outras Estruturas Alge´bricas
Prof. Dr. Leandro Balby Marinho 8 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Reticulados
Definic¸a˜o 3
Um reticulado e´ um POSET (S ,�) tal que para cada dois elementos
a, b ∈ L existe supremo (menor limite superior) e ı´nfimo (maior limite
inferior) de {a, b}.
I Para t, r , s, q ∈ S
I t = sup(r , s) como o ’menor’ elemento t tal que r � t e s � t.
I q = inf(r , s) como o ’maior’ elemento q tal que q � r e q � s.
Note que nem todo poset possui sup(r , s) e inf(r , s).
Prof. Dr. Leandro Balby Marinho 8 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Reticulados: Exemplo
Exemplo 2: Os POSETS (a) e (c) da figura abaixo sa˜o reticulados. Note
que a figura (b) na˜o e´ um reticulado pois os elementos b e c a˜o possuem
um menor limite superior.
Prof. Dr. Leandro Balby Marinho 9 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Reticulados como Estrutura Alge´brica
Definic¸a˜o 4
De forma equivalente, um reticulado e´ uma estrutura alge´brica 〈B,+, ·, 〉
onde para todo x , y e z em B vale:
Identidade Nome
x · x = x + x = x Idempoteˆncia
x · y = y · x Comutatividade
x + y = y + x
x · (y · z) = (x · y) · z Associatividade
x + (y + z) = (x + y) + z
x · (x + y) = x Absorveˆncia
x + (x · y) = x
Prof. Dr. Leandro Balby Marinho 10 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Exemplos de Reticulados
Exemplo 2: Seja 〈C ,+, ·〉 uma estrutura onde C = P(B), para algum
conjunto na˜o vazio B, e sejam as func¸o˜es bina´rias ∧ e ∨ definidas para
todos a, b ⊂ C , por a · b = a ∩ b, a + b = a ∪ b. Mostre que essa
estrutura e´ um reticulado.
Soluc¸a˜o: Como unia˜o e intersec¸a˜o sa˜o operac¸o˜es idempotentes,
comutativas, associativas e absorventes em conjuntos, enta˜o a estrutura
e´ um reticulado.
Exerc´ıcio 2: Seja 〈R,∨,∧〉 onde as func¸o˜es bina´rias ∧ e ∨ sa˜o definidas
por:
a ∧ b := min(a, b),
a ∨ b := max(a, b)
Prof. Dr. Leandro Balby Marinho 11 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Exemplos de Reticulados
Exemplo 2: Seja 〈C ,+, ·〉 uma estrutura onde C = P(B), para algum
conjunto na˜o vazio B, e sejam as func¸o˜es bina´rias ∧ e ∨ definidas para
todos a, b ⊂ C , por a · b = a ∩ b, a + b = a ∪ b. Mostre que essa
estrutura e´ um reticulado.
Soluc¸a˜o: Como unia˜o e intersec¸a˜o sa˜o operac¸o˜es idempotentes,
comutativas, associativas e absorventes em conjuntos, enta˜o a estrutura
e´ um reticulado.
Exerc´ıcio 2: Seja 〈R,∨,∧〉 onde as func¸o˜es bina´rias ∧ e ∨ sa˜o definidas
por:
a ∧ b := min(a, b),
a ∨ b := max(a, b)
Prof. Dr. Leandro Balby Marinho 11 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Exemplos de Reticulados
Exemplo 2: Seja 〈C ,+, ·〉 uma estrutura onde C = P(B), para algum
conjunto na˜o vazio B, e sejam as func¸o˜es bina´rias ∧ e ∨ definidas paratodos a, b ⊂ C , por a · b = a ∩ b, a + b = a ∪ b. Mostre que essa
estrutura e´ um reticulado.
Soluc¸a˜o: Como unia˜o e intersec¸a˜o sa˜o operac¸o˜es idempotentes,
comutativas, associativas e absorventes em conjuntos, enta˜o a estrutura
e´ um reticulado.
Exerc´ıcio 2: Seja 〈R,∨,∧〉 onde as func¸o˜es bina´rias ∧ e ∨ sa˜o definidas
por:
a ∧ b := min(a, b),
a ∨ b := max(a, b)
Prof. Dr. Leandro Balby Marinho 11 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Reticulados e Ordens Parciais
Exemplo 4: Dado um reticulado 〈L,+, ·〉, podemos definir uma
ordem parcial � em L assumindo:
a � b sse a = a · b ou
a � b sse b = a + b
Mostre que essa estrutura e´ um ordem parcial.
Prof. Dr. Leandro Balby Marinho 12 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Roteiro
1. Introduc¸a˜o
2. Estruturas Alge´bricas Ba´sicas
3. Reticulados
4. A´lgebras Booleanas
5. Homomorfismos e Isomorfismos
6. Outras Estruturas Alge´bricas
Prof. Dr. Leandro Balby Marinho 13 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
A´lgebras Booleanas
Definic¸a˜o 4
Uma A´lgebra Booleana e´ uma estrutura alge´brica 〈B,+, ·, ,¯ 0, 1〉 onde B
conte´m dois elementos distintos, denotados genericamente por 0 e 1, e por
treˆs func¸o˜es, onde + e · sa˜o func¸o˜es bina´rias e¯e´ uma func¸a˜o una´ria. Essas
func¸o˜es sa˜o supostas satisfazer os seguintes requisitos:
1. B, + e · formam um reticulado distributivo.
2. Para todo a ∈ B vale que 1 + a = a e que 0 · a = a (Identidade).
3. Para todo a ∈ B vale que a + a¯ = 0 e que a + a¯ = 1 (Complemento).
Prof. Dr. Leandro Balby Marinho 13 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Outras Identidades Booleanas
Identidade Nome
¯¯x = x Lei de Involuc¸a˜o
x + 0 = x Leis de Identidade
x · 1 = x
x + 1 = 1 Leis de Dominac¸a˜o
x · 0 = 0
(x · y) = x¯ + y¯ Leis de De Morgan
(x + y) = x¯ · y¯
Prof. Dr. Leandro Balby Marinho 14 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Exemplos de A´lgebras Booleanas
Exemplo 5: Seja A um conjunto na˜o-vazio. A estrutura 〈P(A),∪,∩, ,¯ ∅,A〉
e´ uma A´lgebra de Boole pois satisfaz todas os axiomas da definic¸a˜o 4.
Exemplo 6: Seja B = {0, 1}, e defina as operac¸o˜oes + e · por x + y =
max(x , y) e x ·y = min(x , y). As tabelas a seguir ilustram essas operac¸o˜es.
+ 0 1
0 0 1
1 1 1
· 0 1
0 0 0
1 0 1
Tambe´m definimos a operac¸a˜o una´ria ¬ na tabela abaixo:
¬
0 1
1 0
Prof. Dr. Leandro Balby Marinho 15 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Exemplos de A´lgebras Booleanas
Exemplo 5: Seja A um conjunto na˜o-vazio. A estrutura 〈P(A),∪,∩, ,¯ ∅,A〉
e´ uma A´lgebra de Boole pois satisfaz todas os axiomas da definic¸a˜o 4.
Exemplo 6: Seja B = {0, 1}, e defina as operac¸o˜oes + e · por x + y =
max(x , y) e x ·y = min(x , y). As tabelas a seguir ilustram essas operac¸o˜es.
+ 0 1
0 0 1
1 1 1
· 0 1
0 0 0
1 0 1
Tambe´m definimos a operac¸a˜o una´ria ¬ na tabela abaixo:
¬
0 1
1 0
Prof. Dr. Leandro Balby Marinho 15 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Exemplo 6 cont.
Para mostrar associatividade para ·, por exemplo, ter´ıamos que verificar
todos os casos:
(0 · 0) · 0 = 0 · (0 · 0) = 0
(0 · 0) · 1 = 0 · (0 · 1) = 0
(0 · 1) · 0 = 0 · (1 · 0) = 0
(0 · 1) · 0 = 0 · (1 · 0) = 0
(0 · 1) · 1 = 0 · (1 · 1) = 0
(1 · 0) · 0 = 1 · (0 · 0) = 0
(1 · 0) · 1 = 1 · (0 · 1) = 0
(1 · 1) · 0 = 1 · (1 · 1) = 0
(1 · 1) · 1 = 1 · (1 · 1) = 0
Exerc´ıcio 3: Verifique a comutatividade e elemento neutro.
Prof. Dr. Leandro Balby Marinho 16 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
A´lgebra Booleana
I Basicamente, uma A´lgebra Booleana fornece operac¸o˜es e regras para
trabalhar com o conjunto {0, 1}.
I As treˆs operac¸o˜es usuais da A´lgebra Booleana sa˜o: complemento (1¯ =
0 e 0¯ = 1), adic¸a˜o Booleana (denotada por + ou ∨ (OR)), e produto
Booleano (denotado por · ou ∧ (AND)).
I Valores da soma Booleana:
1 + 1 = 1, 1 + 0 = 1, 0 + 1 = 1, 0 + 0 = 0
I Valores do Produto Booleano:
1 · 1 = 1, 1 · 0 = 0, 0 · 1 = 0, 0 · 0 = 0
Prof. Dr. Leandro Balby Marinho 17 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
A´lgebra Booleana
A menos que pareˆnteses sejam usados as regras de precedeˆncia sa˜o: (1)
complemento, (2) produto, (3) soma.
Exemplo 7: O valor da expressa˜o 1 · 0 + (0 + 1) e´ 0.
Igualdades em a´lgebra Booleana podem ser traduzidas em equivaleˆncias
de proposic¸o˜es compostas da lo´gica proposicional.
Exemplo 8: A expressa˜o 1 · 0 + (0 + 1) = 0 pode ser dada pela
equivaleˆncia lo´gica T ∧ F ∨ ¬(F ∨ 1).
Prof. Dr. Leandro Balby Marinho 18 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
A´lgebra Booleana
A menos que pareˆnteses sejam usados as regras de precedeˆncia sa˜o: (1)
complemento, (2) produto, (3) soma.
Exemplo 7: O valor da expressa˜o 1 · 0 + (0 + 1) e´ 0.
Igualdades em a´lgebra Booleana podem ser traduzidas em equivaleˆncias
de proposic¸o˜es compostas da lo´gica proposicional.
Exemplo 8: A expressa˜o 1 · 0 + (0 + 1) = 0 pode ser dada pela
equivaleˆncia lo´gica T ∧ F ∨ ¬(F ∨ 1).
Prof. Dr. Leandro Balby Marinho 18 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
A´lgebra Booleana
A menos que pareˆnteses sejam usados as regras de precedeˆncia sa˜o: (1)
complemento, (2) produto, (3) soma.
Exemplo 7: O valor da expressa˜o 1 · 0 + (0 + 1) e´ 0.
Igualdades em a´lgebra Booleana podem ser traduzidas em equivaleˆncias
de proposic¸o˜es compostas da lo´gica proposicional.
Exemplo 8: A expressa˜o 1 · 0 + (0 + 1) = 0 pode ser dada pela
equivaleˆncia lo´gica T ∧ F ∨ ¬(F ∨ 1).
Prof. Dr. Leandro Balby Marinho 18 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
A´lgebra Booleana
A menos que pareˆnteses sejam usados as regras de precedeˆncia sa˜o: (1)
complemento, (2) produto, (3) soma.
Exemplo 7: O valor da expressa˜o 1 · 0 + (0 + 1) e´ 0.
Igualdades em a´lgebra Booleana podem ser traduzidas em equivaleˆncias
de proposic¸o˜es compostas da lo´gica proposicional.
Exemplo 8: A expressa˜o 1 · 0 + (0 + 1) = 0 pode ser dada pela
equivaleˆncia lo´gica T ∧ F ∨ ¬(F ∨ 1).
Prof. Dr. Leandro Balby Marinho 18 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Func¸o˜es Booleanas
Definic¸a˜o 5
Seja B = {0, 1}. Enta˜o Bn = {(x1, x2, . . . , xn | xi ∈ B para 1 ≤ i ≤ n)} e´ o
conjunto de todas as n-uplas poss´ıveis de 0s e 1s, onde a varia´vel Booleana
x assume apenas valores de B. Uma func¸a˜o de Bn em B e´ chamada de
func¸a˜o Booleana de grau n.
Exemplo 10: Ache os valores da func¸a˜o Booleana representada por
F (x , y) = x · y¯ .
Exemplo 11: Ache os valores da func¸a˜o Booleana representada por
F (x , y , z) = x · y + z¯ .
Prof. Dr. Leandro Balby Marinho 19 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras EstruturasFunc¸o˜es Booleanas
Definic¸a˜o 5
Seja B = {0, 1}. Enta˜o Bn = {(x1, x2, . . . , xn | xi ∈ B para 1 ≤ i ≤ n)} e´ o
conjunto de todas as n-uplas poss´ıveis de 0s e 1s, onde a varia´vel Booleana
x assume apenas valores de B. Uma func¸a˜o de Bn em B e´ chamada de
func¸a˜o Booleana de grau n.
Exemplo 10: Ache os valores da func¸a˜o Booleana representada por
F (x , y) = x · y¯ .
Exemplo 11: Ache os valores da func¸a˜o Booleana representada por
F (x , y , z) = x · y + z¯ .
Prof. Dr. Leandro Balby Marinho 19 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Func¸o˜es Booleanas
Definic¸a˜o 5
Seja B = {0, 1}. Enta˜o Bn = {(x1, x2, . . . , xn | xi ∈ B para 1 ≤ i ≤ n)} e´ o
conjunto de todas as n-uplas poss´ıveis de 0s e 1s, onde a varia´vel Booleana
x assume apenas valores de B. Uma func¸a˜o de Bn em B e´ chamada de
func¸a˜o Booleana de grau n.
Exemplo 10: Ache os valores da func¸a˜o Booleana representada por
F (x , y) = x · y¯ .
Exemplo 11: Ache os valores da func¸a˜o Booleana representada por
F (x , y , z) = x · y + z¯ .
Prof. Dr. Leandro Balby Marinho 19 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Portas Lo´gicas
I A a´lgebra Booleana e´ utilizada para a modelagem de circtuitos eletroˆnicos.
I Os elementos ba´sicos de circuitos sa˜o chamados portas lo´gicas.
I Portas lo´gicas sa˜o dispositivos que operam um ou mais sinais lo´gicos
de entrada para produzir uma e somente uma sa´ıda, dependente da
func¸a˜o implementada no circuito.
Prof. Dr. Leandro Balby Marinho 20 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Portas Lo´gicas
I A a´lgebra Booleana e´ utilizada para a modelagem de circtuitos eletroˆnicos.
I Os elementos ba´sicos de circuitos sa˜o chamados portas lo´gicas.
I Portas lo´gicas sa˜o dispositivos que operam um ou mais sinais lo´gicos
de entrada para produzir uma e somente uma sa´ıda, dependente da
func¸a˜o implementada no circuito.
Prof. Dr. Leandro Balby Marinho 20 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Portas Lo´gicas
I A a´lgebra Booleana e´ utilizada para a modelagem de circtuitos eletroˆnicos.
I Os elementos ba´sicos de circuitos sa˜o chamados portas lo´gicas.
I Portas lo´gicas sa˜o dispositivos que operam um ou mais sinais lo´gicos
de entrada para produzir uma e somente uma sa´ıda, dependente da
func¸a˜o implementada no circuito.
Prof. Dr. Leandro Balby Marinho 20 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Portas Lo´gicas
I A a´lgebra Booleana e´ utilizada para a modelagem de circtuitos eletroˆnicos.
I Os elementos ba´sicos de circuitos sa˜o chamados portas lo´gicas.
I Portas lo´gicas sa˜o dispositivos que operam um ou mais sinais lo´gicos
de entrada para produzir uma e somente uma sa´ıda, dependente da
func¸a˜o implementada no circuito.
Prof. Dr. Leandro Balby Marinho 20 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Portas Lo´gicas
I A a´lgebra Booleana e´ utilizada para a modelagem de circtuitos eletroˆnicos.
I Os elementos ba´sicos de circuitos sa˜o chamados portas lo´gicas.
I Portas lo´gicas sa˜o dispositivos que operam um ou mais sinais lo´gicos
de entrada para produzir uma e somente uma sa´ıda, dependente da
func¸a˜o implementada no circuito.
Prof. Dr. Leandro Balby Marinho 20 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Combinando Portas Lo´gicas
Circuitos podem ser constru´ıdos usando-se uma combinac¸a˜o de inversores,
portas OR e AND.
Exemplo 12: Construa circuitos que gerem as seguintes sa´ıdas:
1. x · y + x¯ · y
2. (x + y) · x¯
3. x¯ · (y + z¯)
Exemplo 13: Um comiteˆ de treˆs indiv´ıduos decide questo˜es de uma Uni-
versidade. Cada indiv´ıduo vota sim ou na˜o para cada proposta que aparece.
Uma proposta e´ aprovada se ela recebe pelo menos dois votos. Desenvolva
um circuito que determine quando uma proposta e´ aprovada.
Prof. Dr. Leandro Balby Marinho 21 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Combinando Portas Lo´gicas
Circuitos podem ser constru´ıdos usando-se uma combinac¸a˜o de inversores,
portas OR e AND.
Exemplo 12: Construa circuitos que gerem as seguintes sa´ıdas:
1. x · y + x¯ · y
2. (x + y) · x¯
3. x¯ · (y + z¯)
Exemplo 13: Um comiteˆ de treˆs indiv´ıduos decide questo˜es de uma Uni-
versidade. Cada indiv´ıduo vota sim ou na˜o para cada proposta que aparece.
Uma proposta e´ aprovada se ela recebe pelo menos dois votos. Desenvolva
um circuito que determine quando uma proposta e´ aprovada.
Prof. Dr. Leandro Balby Marinho 21 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Conjuntos Completos de Operadores
I Como qualquer func¸a˜o Booleana pode ser expressa atrave´s dos oper-
adores {+, ·,¯ }, dizemos que esse conjunto de operadores e´ funcional-
mente completo.
I Pode-se achar um conjunto menor de operadores que tambe´m seja
funcionalmente completo?
x + y = x¯ y¯ , {·,¯ } Lei de De Morgan
xy = x¯ + y¯ , {+,¯ } Lei de De Morgan
I Pode-se achar um conjunto contendo um so´ operador que tambe´m
seja funcionalmente completo?
Prof. Dr. Leandro Balby Marinho 22 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Conjuntos Completos de Operadores
I Como qualquer func¸a˜o Booleana pode ser expressa atrave´s dos oper-
adores {+, ·,¯ }, dizemos que esse conjunto de operadores e´ funcional-
mente completo.
I Pode-se achar um conjunto menor de operadores que tambe´m seja
funcionalmente completo?
x + y = x¯ y¯ , {·,¯ } Lei de De Morgan
xy = x¯ + y¯ , {+,¯ } Lei de De Morgan
I Pode-se achar um conjunto contendo um so´ operador que tambe´m
seja funcionalmente completo?
Prof. Dr. Leandro Balby Marinho 22 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Conjuntos Completos de Operadores
I Como qualquer func¸a˜o Booleana pode ser expressa atrave´s dos oper-
adores {+, ·,¯ }, dizemos que esse conjunto de operadores e´ funcional-
mente completo.
I Pode-se achar um conjunto menor de operadores que tambe´m seja
funcionalmente completo?
x + y = x¯ y¯ , {·,¯ } Lei de De Morgan
xy = x¯ + y¯ , {+,¯ } Lei de De Morgan
I Pode-se achar um conjunto contendo um so´ operador que tambe´m
seja funcionalmente completo?
Prof. Dr. Leandro Balby Marinho 22 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Conjuntos Completos de Operadores
Defina um operador | (NAND) como
1 | 1 = 0 e 1 | 0 = 0 | 1 = 0 | 0 = 1 e
um operador ↓ (NOR) como
1 ↓ 1 = 1 ↓ 0 = 0 ↓ 1 = 0 e 0 ↓ 0 = 1
Exemplo 14: Mostre que:
I x¯ = x | x .
I xy = (x | y) | (x | y).
I x¯ = x ↓ x .
I xy = (x ↓ x) ↓ (y ↓ y).
Prof. Dr. Leandro Balby Marinho 23 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Roteiro
1. Introduc¸a˜o
2. Estruturas Alge´bricas Ba´sicas
3. Reticulados
4. A´lgebras Booleanas
5. Homomorfismos e Isomorfismos
6. Outras Estruturas Alge´bricas
Prof. Dr. Leandro Balby Marinho 24 / 34 UFCG CEEIIntroduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Homomorfismos e Isomorfismos
Mapeamentos entre estruturas matema´ticas ou alge´bricas sa˜o chamados
de morfismos. E.g. h : 〈A, µA〉 → 〈B, µB〉.
Definic¸a˜o 7
Um homomorfismo da a´lgebra universal 〈A, µA〉 em 〈B, µB〉 e´ um par de
aplicac¸o˜es 〈f ,∆〉 com f : A→ B e ∆ : µA → µB tal que
f (µA(a1, . . . , an)) = µB(f (a1), . . . , f (an))
para qualquer operac¸a˜o n-a´rea µA e para todos elementos a1, . . . , an ∈ A.
Definic¸a˜o 8
Um isomorfismo e´ um morfismo bijetivo h, tal que tanto h quanto seu
inverso h−1, sa˜o homomorfismos.
Prof. Dr. Leandro Balby Marinho 24 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Homomorfismos e Isomorfismos
Mapeamentos entre estruturas matema´ticas ou alge´bricas sa˜o chamados
de morfismos. E.g. h : 〈A, µA〉 → 〈B, µB〉.
Definic¸a˜o 7
Um homomorfismo da a´lgebra universal 〈A, µA〉 em 〈B, µB〉 e´ um par de
aplicac¸o˜es 〈f ,∆〉 com f : A→ B e ∆ : µA → µB tal que
f (µA(a1, . . . , an)) = µB(f (a1), . . . , f (an))
para qualquer operac¸a˜o n-a´rea µA e para todos elementos a1, . . . , an ∈ A.
Definic¸a˜o 8
Um isomorfismo e´ um morfismo bijetivo h, tal que tanto h quanto seu
inverso h−1, sa˜o homomorfismos.
Prof. Dr. Leandro Balby Marinho 24 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Exemplo 15
Considere os seguintes POSETS:
I S1 := ({1, 2, 3, 5, 6, 10, 15, 30}, xρy ↔ x divide y)
I S2 := (P({1, 2, 3}),AρB ↔ A ⊆ B)
Prof. Dr. Leandro Balby Marinho 25 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Exemplo 15
Considere os seguintes POSETS:
I S1 := ({1, 2, 3, 5, 6, 10, 15, 30}, xρy ↔ x divide y)
I S2 := (P({1, 2, 3}),AρB ↔ A ⊆ B)
Se duas ocorreˆncias de uma estrutura sa˜o isomorfas, cada uma e´ a imagem
semelhante a` outra, com um novo rotulamento de seus elementos.
Prof. Dr. Leandro Balby Marinho 26 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Isomorfismo em A´lgebra Booleana
Exemplo 16: Sejam 〈B,+, ·, ,¯ 0, 1〉 e 〈P,∨,∧,¬,T ,F 〉 duas a´lgebras
booleanas com as definic¸o˜es usuais. Verifique se essas duas estruturas sa˜o
isomo´rficas.
Soluc¸a˜o: Para quaisquer x , y ∈ B:
I Seja f : {0, 1} → {T ,F}, definida por f (1) = T, f (0) = F e,
I ∆ : {+, ·,¯ } → {∨,∧,¬} definida por ∆(+) = ∨,∆(·) = ∧ e
∆(¯) = ¬. Precisamos mostrar que:
I ∆(x + y) = ∆(x) ∨∆(y)
I ∆(x · y) = ∆(x) ∧∆(y)
I ∆(x¯) = ¬∆(x)
Prof. Dr. Leandro Balby Marinho 27 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Isomorfismo em A´lgebra Booleana
Exemplo 16: Sejam 〈B,+, ·, ,¯ 0, 1〉 e 〈P,∨,∧,¬,T ,F 〉 duas a´lgebras
booleanas com as definic¸o˜es usuais. Verifique se essas duas estruturas sa˜o
isomo´rficas.
Soluc¸a˜o: Para quaisquer x , y ∈ B:
I Seja f : {0, 1} → {T ,F}, definida por f (1) = T, f (0) = F e,
I ∆ : {+, ·,¯ } → {∨,∧,¬} definida por ∆(+) = ∨,∆(·) = ∧ e
∆(¯) = ¬. Precisamos mostrar que:
I ∆(x + y) = ∆(x) ∨∆(y)
I ∆(x · y) = ∆(x) ∧∆(y)
I ∆(x¯) = ¬∆(x)
Prof. Dr. Leandro Balby Marinho 27 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Isomorfismo em A´lgebra Booleana
Exemplo 16: Sejam 〈B,+, ·, ,¯ 0, 1〉 e 〈P,∨,∧,¬,T ,F 〉 duas a´lgebras
booleanas com as definic¸o˜es usuais. Verifique se essas duas estruturas sa˜o
isomo´rficas.
Soluc¸a˜o: Para quaisquer x , y ∈ B:
I Seja f : {0, 1} → {T ,F}, definida por f (1) = T, f (0) = F e,
I ∆ : {+, ·,¯ } → {∨,∧,¬} definida por ∆(+) = ∨,∆(·) = ∧ e
∆(¯) = ¬. Precisamos mostrar que:
I ∆(x + y) = ∆(x) ∨∆(y)
I ∆(x · y) = ∆(x) ∧∆(y)
I ∆(x¯) = ¬∆(x)
Prof. Dr. Leandro Balby Marinho 27 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Isomorfismo em A´lgebra Booleana
Exemplo 16: Sejam 〈B,+, ·, ,¯ 0, 1〉 e 〈P,∨,∧,¬,T ,F 〉 duas a´lgebras
booleanas com as definic¸o˜es usuais. Verifique se essas duas estruturas sa˜o
isomo´rficas.
Soluc¸a˜o: Para quaisquer x , y ∈ B:
I Seja f : {0, 1} → {T ,F}, definida por f (1) = T, f (0) = F e,
I ∆ : {+, ·,¯ } → {∨,∧,¬} definida por ∆(+) = ∨,∆(·) = ∧ e
∆(¯) = ¬. Precisamos mostrar que:
I ∆(x + y) = ∆(x) ∨∆(y)
I ∆(x · y) = ∆(x) ∧∆(y)
I ∆(x¯) = ¬∆(x)
Prof. Dr. Leandro Balby Marinho 27 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Isomorfismo em A´lgebra Booleana
Exemplo 16: Sejam 〈B,+, ·, ,¯ 0, 1〉 e 〈P,∨,∧,¬,T ,F 〉 duas a´lgebras
booleanas com as definic¸o˜es usuais. Verifique se essas duas estruturas sa˜o
isomo´rficas.
Soluc¸a˜o: Para quaisquer x , y ∈ B:
I Seja f : {0, 1} → {T ,F}, definida por f (1) = T, f (0) = F e,
I ∆ : {+, ·,¯ } → {∨,∧,¬} definida por ∆(+) = ∨,∆(·) = ∧ e
∆(¯) = ¬. Precisamos mostrar que:
I ∆(x + y) = ∆(x) ∨∆(y)
I ∆(x · y) = ∆(x) ∧∆(y)
I ∆(x¯) = ¬∆(x)
Prof. Dr. Leandro Balby Marinho 27 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Isomorfismo em A´lgebra Booleana
Exemplo 16: Sejam 〈B,+, ·, ,¯ 0, 1〉 e 〈P,∨,∧,¬,T ,F 〉 duas a´lgebras
booleanas com as definic¸o˜es usuais. Verifique se essas duas estruturas sa˜o
isomo´rficas.
Soluc¸a˜o: Para quaisquer x , y ∈ B:
I Seja f : {0, 1} → {T ,F}, definida por f (1) = T, f (0) = F e,
I ∆ : {+, ·,¯ } → {∨,∧,¬} definida por ∆(+) = ∨,∆(·) = ∧ e
∆(¯) = ¬. Precisamos mostrar que:
I ∆(x + y) = ∆(x) ∨∆(y)
I ∆(x · y) = ∆(x) ∧∆(y)
I ∆(x¯) = ¬∆(x)
Prof. Dr. Leandro Balby Marinho 27 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Exemplo 16 cont.
I Para x = 1 e y = 0, por exemplo, para as operac¸o˜es + e ∨ temos:
∆(0 + 1) = ∆(0) ∨∆(1)
∆(1) = F ∨ T
T = T
I Para as operac¸o˜es · e ∧ temos:
∆(0 · 1) = ∆(0) ∧∆(1)
∆(0) = F ∧ T
F = F
I Para x e para as operac¸o˜es¯e ¬ temos:
∆(0¯) = ¬∆(0)
T = ¬F
T = T
Prof. Dr. Leandro Balby Marinho 28 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Exemplo 16 cont.
I Para x = 1 e y = 0, por exemplo, para as operac¸o˜es + e ∨ temos:
∆(0 + 1) = ∆(0) ∨∆(1)
∆(1) = F ∨ T
T = T
I Para as operac¸o˜es · e ∧ temos:
∆(0 · 1) = ∆(0) ∧∆(1)
∆(0) = F ∧ T
F = F
I Para x e para as operac¸o˜es¯e ¬ temos:
∆(0¯) = ¬∆(0)
T = ¬F
T = T
Prof. Dr. Leandro Balby Marinho 28 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Exemplo 16 cont.
I Para x = 1 e y = 0, por exemplo, para as operac¸o˜es + e ∨ temos:
∆(0 + 1) = ∆(0) ∨∆(1)
∆(1) = F ∨ T
T = T
I Para as operac¸o˜es · e ∧ temos:
∆(0 · 1) = ∆(0) ∧∆(1)
∆(0) = F ∧ T
F = F
I Para x e para as operac¸o˜es¯e ¬ temos:
∆(0¯) = ¬∆(0)
T = ¬F
T = T
Prof. Dr. Leandro Balby Marinho 28 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Princ´ıpio da dualidade em A´lgebras de Boole
Para qualquer A´lgebra de Boole 〈B,+, ·,¯ , a, b〉, a estrutura
〈B, ·,+,¯ , b, a〉 tambe´m e´ uma A´lgebra de Boole de forma que
ambas sa˜o isomo´rficas.
Prof. Dr. Leandro Balby Marinho 29 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras EstruturasRoteiro
1. Introduc¸a˜o
2. Estruturas Alge´bricas Ba´sicas
3. Reticulados
4. A´lgebras Booleanas
5. Homomorfismos e Isomorfismos
6. Outras Estruturas Alge´bricas
Prof. Dr. Leandro Balby Marinho 30 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Grupos
Definic¸a˜o 8
Um grupo e´ uma estrutura alge´brica 〈G , ◦〉 (onde ◦ representa uma
operac¸a˜o bina´ria) satisfazendo os seguintes axiomas:
1. Associatividade - Quando satisfeito temos um semigrupo.
2. Identidade - Quando satisfeito juntamente com associatividade temos
um mono´ide.
3. Inverso - Quando satisfeitos esses treˆs axiomas temos um grupo.
4. Comutatividade - Se comutatividade tambe´m e´ satisfeito, enta˜o
temos um grupo abeliano ou comutativo.
Prof. Dr. Leandro Balby Marinho 30 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Grupos
Definic¸a˜o 8
Um grupo e´ uma estrutura alge´brica 〈G , ◦〉 (onde ◦ representa uma
operac¸a˜o bina´ria) satisfazendo os seguintes axiomas:
1. Associatividade - Quando satisfeito temos um semigrupo.
2. Identidade - Quando satisfeito juntamente com associatividade temos
um mono´ide.
3. Inverso - Quando satisfeitos esses treˆs axiomas temos um grupo.
4. Comutatividade - Se comutatividade tambe´m e´ satisfeito, enta˜o
temos um grupo abeliano ou comutativo.
Prof. Dr. Leandro Balby Marinho 30 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Grupos
Definic¸a˜o 8
Um grupo e´ uma estrutura alge´brica 〈G , ◦〉 (onde ◦ representa uma
operac¸a˜o bina´ria) satisfazendo os seguintes axiomas:
1. Associatividade - Quando satisfeito temos um semigrupo.
2. Identidade - Quando satisfeito juntamente com associatividade temos
um mono´ide.
3. Inverso - Quando satisfeitos esses treˆs axiomas temos um grupo.
4. Comutatividade - Se comutatividade tambe´m e´ satisfeito, enta˜o
temos um grupo abeliano ou comutativo.
Prof. Dr. Leandro Balby Marinho 30 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Grupos
Definic¸a˜o 8
Um grupo e´ uma estrutura alge´brica 〈G , ◦〉 (onde ◦ representa uma
operac¸a˜o bina´ria) satisfazendo os seguintes axiomas:
1. Associatividade - Quando satisfeito temos um semigrupo.
2. Identidade - Quando satisfeito juntamente com associatividade temos
um mono´ide.
3. Inverso - Quando satisfeitos esses treˆs axiomas temos um grupo.
4. Comutatividade - Se comutatividade tambe´m e´ satisfeito, enta˜o
temos um grupo abeliano ou comutativo.
Prof. Dr. Leandro Balby Marinho 30 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Grupos
Definic¸a˜o 8
Um grupo e´ uma estrutura alge´brica 〈G , ◦〉 (onde ◦ representa uma
operac¸a˜o bina´ria) satisfazendo os seguintes axiomas:
1. Associatividade - Quando satisfeito temos um semigrupo.
2. Identidade - Quando satisfeito juntamente com associatividade temos
um mono´ide.
3. Inverso - Quando satisfeitos esses treˆs axiomas temos um grupo.
4. Comutatividade - Se comutatividade tambe´m e´ satisfeito, enta˜o
temos um grupo abeliano ou comutativo.
Prof. Dr. Leandro Balby Marinho 30 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Grupos
Exemplo 17: A estrutura 〈Z,+〉. onde + e´ a operac¸a˜o usual de soma,e´
um grupo comutativo? E 〈Z, ·〉 sob a operac¸a˜o usual de produto?
Exemplo 18: O conjunto S = {1, 2, 3, . . .} em relac¸a˜ a` operac¸a˜o de soma
usual e´ um semigrupo, mono´ide ou grupo? E quanto ao conjunto S =
{0, 1, 2, 3, . . .}? Justifique.
Exemplo 19: O conjunto R dotado da operac¸a˜o de multiplicac¸a˜o usual e´
um semigrupo, mono´ide ou grupo? Justifique.
Prof. Dr. Leandro Balby Marinho 31 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Grupos
Exemplo 17: A estrutura 〈Z,+〉. onde + e´ a operac¸a˜o usual de soma,e´
um grupo comutativo? E 〈Z, ·〉 sob a operac¸a˜o usual de produto?
Exemplo 18: O conjunto S = {1, 2, 3, . . .} em relac¸a˜ a` operac¸a˜o de soma
usual e´ um semigrupo, mono´ide ou grupo? E quanto ao conjunto S =
{0, 1, 2, 3, . . .}? Justifique.
Exemplo 19: O conjunto R dotado da operac¸a˜o de multiplicac¸a˜o usual e´
um semigrupo, mono´ide ou grupo? Justifique.
Prof. Dr. Leandro Balby Marinho 31 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Grupos
Exemplo 17: A estrutura 〈Z,+〉. onde + e´ a operac¸a˜o usual de soma,e´
um grupo comutativo? E 〈Z, ·〉 sob a operac¸a˜o usual de produto?
Exemplo 18: O conjunto S = {1, 2, 3, . . .} em relac¸a˜ a` operac¸a˜o de soma
usual e´ um semigrupo, mono´ide ou grupo? E quanto ao conjunto S =
{0, 1, 2, 3, . . .}? Justifique.
Exemplo 19: O conjunto R dotado da operac¸a˜o de multiplicac¸a˜o usual e´
um semigrupo, mono´ide ou grupo? Justifique.
Prof. Dr. Leandro Balby Marinho 31 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Ane´is
Definic¸a˜o 9
Uma a´lgebra 〈S ,+, ·〉 e´ um anel se valem as seguintes propriedades:
1. Se 〈S ,+〉 e´ um grupo abeliano.
2. Se 〈S , ·〉 e´ um semigrupo.
3. Vale a distributividade a esquerda e a direita da operac¸a˜o · sobre +,
ou seja,
a · (b + c) = a · b + a · c e (a + b) · c = a · c + b · c
Exemplo 23: A estrutura 〈Z,+, ·〉 sob a soma usual em inteiros e´ um
anel.
Prof. Dr. Leandro Balby Marinho 32 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Ane´is
Definic¸a˜o 9
Uma a´lgebra 〈S ,+, ·〉 e´ um anel se valem as seguintes propriedades:
1. Se 〈S ,+〉 e´ um grupo abeliano.
2. Se 〈S , ·〉 e´ um semigrupo.
3. Vale a distributividade a esquerda e a direita da operac¸a˜o · sobre +,
ou seja,
a · (b + c) = a · b + a · c e (a + b) · c = a · c + b · c
Exemplo 23: A estrutura 〈Z,+, ·〉 sob a soma usual em inteiros e´ um
anel.
Prof. Dr. Leandro Balby Marinho 32 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Corpos
Definic¸a˜o 10
Uma a´lgebra 〈S ,+, ·〉 e´ um corpo se valem as seguintes propriedades:
1. Se 〈S ,+, ·〉 e´ um anel.
2. Se 〈S , ·〉 e´ um mono´ide comutativo.
3. Vale a distributividade a esquerda e a direita da operac¸a˜o · sobre +,
ou seja,
a · (b + c) = a · b + a · c e (a + b) · c = a · c + b · c
Exemplo 24: A estrutura 〈R,+, ·〉 e´ um corpo. E quanto a 〈Z,+, ·〉?
Dado um corpo 〈S ,+, ·〉 podemos definir operadores de diferenc¸a e
divisa˜o como a− b = a + (−b) e a/b = a · b−1.
Prof. Dr. Leandro Balby Marinho 33 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Corpos
Definic¸a˜o 10
Uma a´lgebra 〈S ,+, ·〉 e´ um corpo se valem as seguintes propriedades:
1. Se 〈S ,+, ·〉 e´ um anel.
2. Se 〈S , ·〉 e´ um mono´ide comutativo.
3. Vale a distributividade a esquerda e a direita da operac¸a˜o · sobre +,
ou seja,
a · (b + c) = a · b + a · c e (a + b) · c = a · c + b · c
Exemplo 24: A estrutura 〈R,+, ·〉 e´ um corpo. E quanto a 〈Z,+, ·〉?
Dado um corpo 〈S ,+, ·〉 podemos definir operadores de diferenc¸a e
divisa˜o como a− b = a + (−b) e a/b = a · b−1.
Prof. Dr. Leandro Balby Marinho 33 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos OutrasEstruturas
Corpos
Definic¸a˜o 10
Uma a´lgebra 〈S ,+, ·〉 e´ um corpo se valem as seguintes propriedades:
1. Se 〈S ,+, ·〉 e´ um anel.
2. Se 〈S , ·〉 e´ um mono´ide comutativo.
3. Vale a distributividade a esquerda e a direita da operac¸a˜o · sobre +,
ou seja,
a · (b + c) = a · b + a · c e (a + b) · c = a · c + b · c
Exemplo 24: A estrutura 〈R,+, ·〉 e´ um corpo. E quanto a 〈Z,+, ·〉?
Dado um corpo 〈S ,+, ·〉 podemos definir operadores de diferenc¸a e
divisa˜o como a− b = a + (−b) e a/b = a · b−1.
Prof. Dr. Leandro Balby Marinho 33 / 34 UFCG CEEI
Introduc¸a˜o Estruturas Alge´bricas Reticulados A´lgebras Booleanas Homomorfismos e Isomorfismos Outras Estruturas
Refereˆncias
Keneth H. Rosen. Discrete Mathematics and Its Applications.
Sexta Edic¸a˜o. McGRAW-HILL International Edition, 2007.
Judith L. Gersting. Fundamentos Matema´ticos para a Cieˆncia
da Computac¸a˜o. Quinta Edic¸a˜o. LTC, 2004.
“Algebraic Structures.” Wikipedia. Wikimedia Foundation Inc..
02 Nov. 2010.
〈http://en.wikipedia.org/wiki/Algebraic_structure〉.
Joa˜o C. A. Barata. Curso de F´ısica Matema´tica. Livro on-line.
02 Nov. 2010. 〈http://denebola.if.usp.br/~jbarata/
Notas_de_aula/notas_de_aula.html〉.
Prof. Dr. Leandro Balby Marinho 34 / 34 UFCG CEEI
	1. Introdução
	2. Estruturas Algébricas Básicas
	3. Reticulados
	4. Álgebras Booleanas
	5. Homomorfismos e Isomorfismos
	6. Outras Estruturas Algébricas