Mat Discreta9

Prévia do material em texto

Matemática Discreta para Ciência da Computação - P. Blauth Menezes 1
Matemática Discreta para
Ciência da Computação
P. Blauth Menezes
blauth@inf.ufrgs.br
Departamento de Informática Teórica
Instituto de Informática / UFRGS
 
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 2
Matemática Discreta para Ciência da Computação
P. Blauth Menezes
1 Introdução e Conceitos Básicos
2 Lógica e Técnicas de Demonstração
3 Álgebra de Conjuntos
4 Relações
5 Funções Parciais e Totais
6 Endorrelações, Ordenação e Equivalência
7 Cardinalidade de Conjuntos
8 Indução e Recursão
9 Álgebras e Homomorfismos
10 Reticulados e Álgebra Booleana
11 Conclusões
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 3
9 – Álgebras e
Homomorfismos
9.1 Operações Binárias
9.2 Propriedades das Operações Binárias
9.3 Grupóides, Semigrupos, Monóides, Grupos
9.4 Importantes Propriedades dos Monóides e
Grupos
9.5 Homomorfismos
9.6 Monóide Livre Gerado e Fecho de Kleene
9.7 Grafos
9.8 Categorias
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 4
9 Álgebras e Homomorfismos
◆ Já foi introduzido que
• Álgebra, desde a sua origem até a sua forma atual
∗ refere-se a cálculos
• Desenvolvida de forma informal ou formal
∗ praticamente em todos os níveis de escolaridade
∗ ex: operações aritméticas (adição, multiplicação…) sobre R
• Álgebras, em CC, destaca-se a partir de 1950
∗ Teoria dos Autômatos e Linguagens Formais
• De certa forma, toda a CC é construída sobre álgebras
∗ Álgebra: denominação alternativa para a Matemática Discreta
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 5
◆ Assim, o estudo mais amplo de álgebras
• central no contexto da Matemática Discreta
◆ Alguns exemplos de álgebras já introduzidos
• Álgebra de Conjuntos
∗ conjuntos e as operações sobre conjuntos (união,…)
• Álgebra de Funções
∗ funções e composição de funções
• Álgebra de Proposições
∗ proposições e conetivos lógicos (e, negação,…)
◆ Seguindo a mesmo linha de raciocínio
• Álgebra de Relações, Álgebra de Funções Parciais, ...
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 6
◆ Conceito formal de álgebra
• simples
• mas com um nível de abstração relativamente alto
∗ para caracterizar todos os tipos de álgebras
◆ O conceito é construindo do concreto para o abstrato
• inicialmente são introduzidos alguns exemplos
◆ Exemplos acima são de álgebras grandes
• operações definidas sobre coleções (e não conjuntos)
◆ Neste capítulo
• ênfase às álgebras pequenas
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 7
◆ Homomorfismo de Álgebras
• conceito tão importante quanto o de álgebra
• são funções (álgebras pequenas)
∗ mapeiam álgebras (estruturalmente similares)
∗ preservando as estruturas
• morfismo
∗ alguma forma de mapeamento (relação, função, …)
∗ entre duas estruturas similares
• homo
∗ preserva a estrutura
• noção de homomorfismo é desenvolvida gradativamente
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 8
◆ Estudo mais formal de álgebra
• conceito de operação
• principais propriedades das operações
◆ Importantes álgebras e homomorfismos
• fecho de Kleene
• grafo (visto como álgebra)
• categoria (vista como álgebra)
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 9
9 – Álgebras e
Homomorfismos
9.1 Operações Binárias
9.2 Propriedades das Operações Binárias
9.3 Grupóides, Semigrupos, Monóides, Grupos
9.4 Importantes Propriedades dos Monóides e
Grupos
9.5 Homomorfismos
9.6 Monóide Livre Gerado e Fecho de Kleene
9.7 Grafos
9.8 Categorias
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 10
9.1 Operações Binárias
◆ Operação (pequena): função parcial
• já foi introduzido
◆ De especial interesse para a Computação e Informática
• operações binárias
∗ domínio: produto cartesiano
• operações internas a um conjunto A
∗ domínio e contra-domínio são definidos sobre A
• operações fechadas
∗ total
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 11
Def: Operação Binária, Interna, Fechada
A, B e C conjuntos
Operação Binária
⊕: A × B → C
Operação Interna ao conjunto A
• domínio e contra-domínio são definidos em A
∗ o próprio A ou
∗ conjunto resultante do produto cartesiano sobre A
• operação binária interna ao conjunto A
⊕: A × A → A
Operação Fechada: operação total (função)
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 12
Exp: Operação binária? interna? fechada?
Divisão nos reais. div: R × R → R
div〈x, y〉 = x/y
Quadrado nos naturais. quadrado: N → N
quadrado(n) = n2
Elemento. 1 = { * } conjunto unitário. zero: 1 → N
zero〈*〉 = 0
União. A conjunto. ∪: P(A) × P(A) → P(A)
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 13
Obs: Elemento de Conjunto como Função
Função zero: 1 → N tal que zero〈*〉 = 0
• forma de identificar um elemento de um conjunto por uma função
• se 1 é conjunto unitário fixo, e A conjunto qualquer
#A = #{ f  f : 1 → A é função }
• exemplo
true
false
1 boolean
true
true
false
1 boolean
false
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 14
9 – Álgebras e
Homomorfismos
9.1 Operações Binárias
9.2 Propriedades das Operações Binárias
9.3 Grupóides, Semigrupos, Monóides, Grupos
9.4 Importantes Propriedades dos Monóides e
Grupos
9.5 Homomorfismos
9.6 Monóide Livre Gerado e Fecho de Kleene
9.7 Grafos
9.8 Categorias
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 15
9.2 Propriedades das Operações
Binárias
◆ Principais propriedades das operações binárias,
internas e fechadas
• Comutativa *
• Associativa *
• Elemento neutro *
• Elemento inverso
* introduzidas anteriormente: Álgebra de Conjuntos & Lógica
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 16
Def: Comutativa, Associativa, Elemento Neutro,
Elemento Inverso
⊕: A × A → A operação binária, interna e fechada
Comutativa
(∀a ∈ A)(∀b ∈ A) ( a ⊕ b = b ⊕ a )
Associativa
(∀a ∈ A)(∀b ∈ A)(∀c ∈ A) ( a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c )
Elemento Neutro
(∃e ∈ A)(∀a ∈ A) ( a ⊕ e = e ⊕ a = a )
Elemento Inverso
(∀a ∈ A)(∃a ∈ A) ( a ⊕ a = a ⊕ a = e )
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 17
◆ Associativa ???
• precedência na aplicação do operando não é importante
• parênteses podem ser omitidos
a ⊕ b ⊕ c
◆ Elemento Neutro
• satisfazer simultaneamente à esquerda e à direita é fundamental
(∃e ∈ A)(∀a ∈ A) ( a ⊕ e = e ⊕ a = a )
• divisão nos reais
∗ possui neutro à direita número um
∗ não possui neutro à esquerda
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 18
Exp: Propriedades da União
A conjunto. ∪: P(A) × P(A) → P(A)
• Comutativa?
• Associativa?
• Elemento neutro? (qual ?)
• Elemento inverso?
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 19
Exp: Propriedades da Adição
+: N × N → N
• comutativa
• associativa
• elemento neutro (zero)
+: Z × Z → Z
• comutativa
• associativa
• elemento neutro
• elemento inverso
n + –n = –n + n = 0
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 20
Exp: Propriedades da Multiplicação
*: N × N → N
• comutativa, associativa e elemento neutro (um)
*: R × R → R
• comutativa, associativa e elemento neutro
• se considerada sem o zero
∗ elemento inverso
x * 1/x = 1/x * x = 1
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 21
9 – Álgebras e
Homomorfismos
9.1 Operações Binárias
9.2 Propriedades das Operações Binárias
9.3 Grupóides, Semigrupos,Monóides, Grupos
9.4 Importantes Propriedades dos Monóides e
Grupos
9.5 Homomorfismos
9.6 Monóide Livre Gerado e Fecho de Kleene
9.7 Grafos
9.8 Categorias
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 22
9.3 Grupóides, Semigrupos, Monóides,
Grupos
◆ Exemplo de álgebra
• operação binária e interna ⊕: A × A → A
• usualmente denotada como um par ordenado
〈A, ⊕〉
• álgebra interna
∗ operação ⊕ é interna
• conjunto suporte da álgebra interna 〈A, ⊕〉
∗ conjunto A
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 23
◆ Operações binárias e internas são especialmente
importantes para Computação e Informática
◆ Tipos mais importantes de álgebras internas com uma
única operação binária
• se a operação for comutativa, é dita abeliana
 Tipo de
Álgebra
 Fechada Associativa Elemento
Neutro
 Elemento
Inverso
Grupóide ✔
Semigrupo ✔ ✔
Monóide ✔ ✔ ✔
Grupo ✔ ✔ ✔ ✔
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 24
◆ Hierarquia entre estes tipos de álgebras
 Grupóides
(fechada)
 Semigrupos
(fechada + associativa)
Universo de Todas as Álgebras Internas
(uma operação)
Monóides
(fechada + associativa + neutro)
Grupos
(fechada + associativa + neutro + inverso)
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 25
Def: Grupóide, Semigrupo, Monóide, Grupo
Grupóide: álgebra interna 〈A, ⊕〉
• ⊕: A × A → A operação (binária e interna)
• fechada
Semigrupo: álgebra interna 〈A, ⊕〉
• 〈A, ⊕〉 grupóide
• associativa
Monóide: álgebra interna 〈A, ⊕〉 ou 〈A, ⊕, e〉
• 〈A, ⊕〉 semigrupo
• elemento neutro
Grupo: álgebra interna 〈A, ⊕〉 ou 〈A, ⊕, e〉
• 〈A, ⊕〉 monóide
• elemento inverso
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 26
Def: Grupóide, Semigrupo, Monóide, Grupo
Se a operação for comutativa
• Grupóide Comutativo ou Grupóide Abeliano
• Semigrupo Comutativo ou Semigrupo Abeliano
• Monóide Comutativo ou Monóide Abeliano
• Grupo Comutativo ou Grupo Abeliano
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 27
Exp: Grupóide, Semigrupo, Monóide: Concatenação
Σ alfabeto não-vazio, operação de concatenação
conc: Σ* × Σ* → Σ*
• fechada
• associativa
• elemento neutro (palavra vazia ε)
Portanto, a álgebra interna 〈Σ*, conc〉 é simultaneamente
• grupóide
• semigrupo
• monóide
Não é
• grupo (e se o alfabeto for vazio?)
• comutativa (e se o alfabeto for vazio ou unitário?)
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 28
Exp: Grupóide, Semigrupo, Monóide: União e
Intersecção
A conjunto, operações de união e de intersecção
∪: P(A) × P(A) → P(A) e ∩: P(A) × P(A) → P(A)
• fechadas
• associativas
• elemento neutro (∅ e A)
• comutativas
Portanto álgebras internas 〈P(A), ∪〉 e 〈P(A), ∩〉 são simultaneamente
• grupóides abelianos
• semigrupos abelianos
• monóides abelianos
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 29
Exp: Grupóide, Semigrupo, Monóide: União e
Intersecção
Se união e intersecção
• definidas sobre todos os conjuntos
• constituem grupóides?
Se o conjunto suporte A for vazio,
• 〈P(A), ∪〉 e 〈P(A), ∩〉
• constituem grupos?
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 30
Exp: Grupóide, Semigrupo, Monóide, Grupo: Adição e
Multiplicação
Simultaneamente grupóides abelianos, semigrupos abelianos e
monóides abelianos (qual o elemento neutro ?)
• 〈N, +〉 e 〈N, ∗〉
• 〈Z, +〉 e 〈Z, ∗〉
• 〈R, +〉 e 〈R, ∗〉
Grupos abelianos
• 〈Z, +〉 adição nos inteiros
• 〈R, +〉 adição nos reais
• 〈R – { 0 }, ∗〉 multiplicação nos reais sem o zero
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 31
Exp: Grupóide, Semigrupo, Monóide, Grupo: Unitário
Simultaneamente grupóide abeliano, semigrupo abeliano, monóide
abeliano e grupo abeliano
Unitário. 〈{ ∗ }, !〉, operação !: { ∗ } × { ∗ } → { ∗ }
• fechada
• associativa
• comutativa
• elemento neutro (o único elemento do suporte)
• elemento inverso (por quê?)
• única op. com origem em { ∗ } × { ∗ } e destino em { ∗ } (por quê?)
Menor monóide (em termos do cardinal do conjunto suporte)
• unitário
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 32
Exp: Grupóide, Semigrupo: Vazio
Simultaneamente grupóide abeliano e semigrupo abeliano
Vazio. 〈∅, ∅〉, operação vazia ∅: ∅ × ∅ → ∅
• fechada
• associativa (por quê?)
• comutativa
• única operação com origem em ∅ × ∅ e destino em ∅ (por quê?)
Menor grupóide (em termos do cardinal do conjunto suporte)
• vazio
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 33
Exp: Álgebra Não-Grupóide
A conjunto não-vazio. Não são grupóides (por que?)
• Subtração nos naturais: 〈N, -〉
• Divisão nos reais: 〈R, /〉
• Produto cartesiano no conjunto das partes 〈P(A), ×〉
Exp: Álgebra Não-Semigrupo
São grupóides, mas não são semigrupos (operações não-associativas)
• Subtração nos inteiros: 〈Z, -〉
• Divisão nos reais sem o zero: 〈R - { 0 }, /〉
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 34
Exp: Álgebra Não-Monóide
Vazio. Semigrupo abeliano 〈∅, ∅〉
• operação ∅: ∅ × ∅ → ∅
• não possui elemento neutro
∗ suporte de um monóide não pode ser vazio
Adição e Multiplicação. Excluindo-se, respectivamente, 0 e 1
• 〈N - { 0 }, +〉 e 〈N - { 1 }, ∗〉
• 〈R - { 0 }, +〉 e 〈R - { 1 }, ∗〉
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 35
Exp: Álgebra Não-Grupo
Adição e Multiplicação.
• 〈N, +〉 adição nos inteiros
• 〈R, ∗〉 multiplicação nos reais
União e Intersecção. A conjunto não-vazio
• 〈P(A), ∪〉
• 〈P(A), ∩〉
Concatenação. Σ alfabeto não-vazio
• 〈Σ*, conc, ε〉
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 36
9 – Álgebras e
Homomorfismos
9.1 Operações Binárias
9.2 Propriedades das Operações Binárias
9.3 Grupóides, Semigrupos, Monóides, Grupos
9.4 Importantes Propriedades dos Monóides e
Grupos
9.5 Homomorfismos
9.6 Monóide Livre Gerado e Fecho de Kleene
9.7 Grafos
9.8 Categorias
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 37
9.4 Importantes Propriedades dos
Monóides e Grupos
◆ Elemento neutro em um monóide é único???
• Técnicas de Demonstração - prova por absurdo
0 é o único elemento neutro da adição em N
Teorema: Elemento Neutro de um Monóide é Único
〈A, ⊕, e〉 monóide. Então, e ∈ A é o único elemento neutro do monóide
Prova: (por absurdo)
〈A, ⊕, e〉 monóide. Suponha que e não é o único elemento neutro
• existe um outro elemento neutro e, diferente de e
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 38
Então (suponha a ∈ A)
• e é neutro
∗ a = e ⊕ a = a ⊕ e
∗ para a = e tem-se que e = e ⊕ e = e ⊕ e
• e é neutro
∗ a = e ⊕ a = a ⊕ e
∗ para a = e tem-se que e = e ⊕ e = e ⊕ e
• transitividade da igualdade
∗ e = e
∗ contradição!!! foi suposto que e ≠ e
É absurdo supor que o elemento neutro de 〈A, ⊕, e〉 não é único
Logo, o elemento neutro é único
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 39
◆ Teorema a seguir
• importante propriedade dos grupos
• generaliza a intuição sobre operações como a adição nos reais
∗ se x + 3 = y + 3
∗ então, x = y
• propriedade cancelamento
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 40
Teorema: Propriedade de Cancelamento dos Grupos
〈A, ⊕〉 um grupo satisfaz à propriedade de cancelamento, ou seja,
simultaneamente:
• Cancelamento à direita
(∀a ∈ A)(∀x ∈ A)(∀y ∈ A) ( x ⊕ a = y ⊕ a → x = y )
• Cancelamento à esquerda:
(∀a ∈ A)(∀x ∈ A)(∀y ∈ A) ( a ⊕ x = a ⊕ y → x = y )
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 41
Prova: 
Cancelamento à direita. Suponha que x ⊕ a= y ⊕ a
• x = elemento neutro
• x ⊕ e = elemento inverso
• x ⊕ (a ⊕ a) = associatividade
• (x ⊕ a) ⊕ a = hipótese
• (y ⊕ a) ⊕ a = associatividade
• y ⊕ (a ⊕ a) = elemento inverso
• y ⊕ e = elemento neutro
• y
• Portanto, x = y
Cancelamento à esquerda. A prova é análoga (exercício)
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 42
Teorema Elemento Inverso em um Grupo é Único
〈A, ⊕〉 grupo. Então, para qualquer a ∈ A, o elemento inverso de a é
único
Prova: 
Exercício
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 43
9 – Álgebras e Homomorfismos
9.1 Operações Binárias
9.2 Propriedades das Operações Binárias
9.3 Grupóides, Semigrupos, Monóides, Grupos
9.4 Importantes Propriedades dos Monóides e
Grupos
9.5 Homomorfismos
9.5.1 Grupóides e Semigrupos
9.5.2 Monóides
9.5.3 Grupos
9.6 Monóide Livre Gerado e Fecho de Kleene
9.7 Grafos
9.8 Categorias
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 44
9.5 Homomorfismos
◆ Homomorfismo de álgebras (já foi afirmado)
• é constituído por funções (no caso de álgebras pequenas)
• mapeiam álgebras de um mesmo tipo
• preservando as suas estruturas
◆ Como estruturas (abelianas ou não) são preservadas
por homomorfismos de
• Grupóides?
• Semigrupos?
• Monóides?
• Grupos?
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 45
◆ Monomorfismo, epimorfismo e isomorfismo?
• seria de se esperar que os conceitos fossem naturalmente
estendidos para mapeamentos de álgebras
• somente o de isomorfismo pode ser estendido
Obs: Monomorfismo, Epimorfismo e Isomorfismo de
Álgebras
Isomorfismo
• baseado na existência de um morfismo inverso
• pode ser naturalmente estendido para as estruturas algébricas
Monomorfismo e epimorfismo
• necessitam de noções e conceitos baseados em Teoria das
Categorias (fogem do escopo da disciplina)
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 46
◆ Estruturas algébricas isomorfas
• se existe um isomorfismo entre tais estruturas
• são consideradas basicamente a mesma
iguais a menos de isomorfismo
• e, obrigatoriamente
possuem as mesmas propriedades
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 47
9 – Álgebras e Homomorfismos
9.1 Operações Binárias
9.2 Propriedades das Operações Binárias
9.3 Grupóides, Semigrupos, Monóides, Grupos
9.4 Importantes Propriedades dos Monóides e
Grupos
9.5 Homomorfismos
9.5.1 Grupóides e Semigrupos
9.5.2 Monóides
9.5.3 Grupos
9.6 Monóide Livre Gerado e Fecho de Kleene
9.7 Grafos
9.8 Categorias
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 48
9.5.1 Homomorfismo: Grupóides e Semigrupos
◆ Homomorfismo de grupóides
• função entre os conjuntos suportes
• preserva a operação
a1
a2
a3 = a1⊕a2
b1
b2
b3 = b1⊗b2
 homomorfismo
〈A,⊕〉 〈B,⊗〉
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 49
◆ Homomorfismo de semigrupos
• é como um homomorfismo de grupóides
• preserva operação ⇒ preserva associatividade
Def: Homomorfismo de Grupóides
〈A, ⊕〉 e 〈B, ⊗〉 grupóides
h: 〈A, ⊕〉 → 〈B, ⊗〉
função entre os conjuntos suportes h: A → B tal que
(∀a1 ∈ A)(∀a2 ∈ A)( h〈a1 ⊕ a2〉 = h〈a1〉 ⊗ h〈a2〉 )
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 50
◆ Notação
h: 〈A, ⊕〉 → 〈B, ⊗〉
• e não simplesmente como função h: A → B
• destaca o fato de que se trata de um morfismo entre álgebras
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 51
Exp: Homomorfismo de Grupóides: Identidade, Inclusão
〈A, ⊕〉, 〈N, +〉 e 〈Z, +〉 grupóides
Identidade. Função identidade idA: A → A induz
id〈A,⊕〉: 〈A, ⊕〉 → 〈A, ⊕〉
Inclusão. Função inclusão incN,Z: N → Z induz
inc〈N,+〉,〈Z,+〉: 〈N, +〉 → 〈Z, +〉
◆ Termos identidade e inclusão
• consideram toda a estrutura do grupóide
• e não apenas o conjunto suporte
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 52
Exp: Morfismo Não-Homomorfismo de Grupóides
A um conjunto e 〈P(A), ∪〉, 〈P(A), ∩〉 grupóides
Morfismo induzido pela identidade idP(A): P(A) → P(A) não é, em geral,
um homomorfismo de grupóides
idP(A): 〈P(A), ∪〉 → 〈P(A), ∩〉
Exemplo: A = { a, b }, P(A) = { ∅, { a }, { b }, { a, b } }
• São diferentes
∗ idP(A)〈{ a } ∪ { b }〉 = idP(A)〈{ a, b }〉 = { a, b }
∗ idP(A)〈{ a } ∪ { b }〉 = idP(A)〈{ a }〉 ∩ idP(A)〈{ b }〉 = {a} ∩ {b} = ∅
Exercício: função inclusão (não-identidade) a qual induz um morfismo
não-homomorfismo de grupóides
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 53
Exp: Homomorfismo de Grupóides: Concatenação
Σ1 = { a, b, c } e Σ2 = { r, s } alfabetos
〈Σ1*, conc1〉 e 〈Σ2*, conc2〉 grupóides
Função f: Σ1 → Σ2 tal que (função entre alfabetos)
• f〈a〉 = r
• f〈b〉 = r
• f〈c〉 = s
induz canonicamente o homomorfismo de grupóides (mapeia palavras)
f*: 〈Σ1*, conc1〉 → 〈Σ2*, conc2〉
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 54
indutivamente definido
• f*〈ε〉 = ε
• para qualquer x ∈ Σ1, vale f*〈x〉 = f〈x〉
• se x ∈ Σ1 e w ∈ Σ1*, então f*〈x w〉 = f〈x〉 f*〈w〉
ε
a
b
c
aa
ab
ac
bb
Σ1* ε
r
s
r r
rs
...
Σ2*
 f*
...
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 55
Exemplo:
• f*〈abc〉 = 
• f〈a〉 f*〈bc〉 = 
• f〈a〉 f〈b〉 f*〈c〉 = 
• f〈a〉 f〈b〉 f〈c〉 f*〈ε〉 = 
• r r s ε = r r s
ε
a
b
c
aa
ab
ac
bb
Σ1* ε
r
s
r r
rs
...
Σ2*
 f*
...
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 56
Função entre alfabetos g: Σ2 → Σ1
• g〈r〉 = a
• g〈s〉 = b
induz o homomorfismo de grupóides
ε
a
b
c
aa
ab
ac
bb...
ε
r
s
r r
rs
...
Σ2* Σ1*
 g*
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 57
Def: Isomorfismo de Grupóides
h: 〈A, ⊕〉 → 〈B, ⊗〉 é um Isomorfismo de Grupóides se e somente se
• h possui um homomorfismo de grupóides inverso
g: 〈B, ⊗〉 → 〈A, ⊕〉
g o h = id〈A,⊕〉 e h o g = id〈B,⊕〉
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 58
Exp: Isomorfismo de Grupóides
〈{ a }*, conc〉 e 〈N, +〉 grupóides
h: { a } → N 
• tal que h〈a〉 = 1
induz o homomorfismo de grupóides indutivamente definido
h*: 〈{ a }*, conc〉 → 〈N, +〉
• h*〈ε〉 = 0
• h*〈a〉 = h〈a〉
• se w ∈ { a }*, então h*〈a w〉 = h〈a〉 + h*〈w〉
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 59
Exp: …Isomorfismo de Grupóides
Mapeia cada palavra no seu correspondente tamanho
h*〈aaa〉 = h〈a〉 + h*〈aa〉 = h〈a〉 + h〈a〉 + h*〈a〉 = 
h〈a〉 + h〈a〉 + h〈a〉 + h*〈ε〉 = 1 + 1 + 1 + 0 = 3
Homomorfismo induzido h*: 〈{ a }*, conc〉 → 〈N, +〉
• é isomorfismo de grupóides (qual o homomorfismo inverso?).
Logo, 〈Σ*, conc〉 e 〈N, +〉 são
iguais a menos de isomorfismo
• base unária para os naturais e a operação de adição
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 60
Obs: Base de Sistemas Numéricos
Base decimal
• base dos sistemas numéricos usualmente adotada na Matemática
∗ origem: número de dedos das duas mãos
• base complicada para representação em sistemas computadores
∗ computador: usa base binária
∗ os dois valores possíveis de um bit: 0 e 1 ou qq alfabeto binário
Exemplo anterior: base unária para os naturais e a adição
Estudo de bases
• Arquitetura de Computadores e Aritmética Computacional
Exercício: base binária para os números naturais e a adição
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 61
◆ Dois teoremas importantes
• composição de hom. de grupóides é hom. de grupóides
• hom. de grupóides preservam a propriedade associativa
Teorema: Composição de Homomorfismo de Grupóides
〈A, ⊕〉, 〈B, ⊗〉 e 〈C, ∇〉 grupóides
f: 〈A, ⊕〉 → 〈B, ⊗〉 e g: 〈B, ⊗〉 → 〈C, ∇〉 hom. de grupóidesg o f: 〈A, ⊕〉 → 〈C, ∇〉
induzido pela composição das funções f: A → B e g: B → C
g o f: A → C
é homomorfismo de grupóides
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 62
Prova: 
Suponha f: 〈A, ⊕〉 → 〈B, ⊗〉 e g: 〈B, ⊗〉 → 〈C, ∇〉 hom. de grupóides
Como a composição de funções é uma função
• mostrar que g o f: 〈A, ⊕〉 → 〈C, ∇〉 é hom. de grupóides
• basta mostrar que preserva a operação
Para quaisquer a1 ∈ A e a2 ∈ A
• g o f〈a1 ⊕ a2〉 = definição de composição
• g〈f〈a1 ⊕ a2〉〉 = f hom. de grupóides
• g〈f〈a1〉 ⊗ f〈a2〉〉 = g hom. de grupóides
• g〈f〈a1〉〉 ∇ g〈f〈a2〉〉 = definição de composição
• g o f〈a1〉 ∇ g o f〈a2〉
Portanto g o f: 〈A, ⊕〉 → 〈C, ∇〉 é hom. de grupóides
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 63
Teorema: Hom de Grupóides Preserva a Associatividade
Sejam 〈A, ⊕〉 e 〈B, ⊗〉 grupóides e f: 〈A, ⊕〉 → 〈B, ⊗〉 hom. de grupóides
Se 〈A, ⊕〉 ou 〈B, ⊗〉 é semigrupo
• então f: 〈A, ⊕〉 → 〈B, ⊗〉 preserva a associatividade
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 64
Prova: 
Caso 1: 〈A, ⊕〉 é semigrupo
Como ⊕ é associativa, para quaisquer a ∈ A, b ∈ A e c ∈ A
f〈a ⊕ (b ⊕ c)〉 = f〈(a ⊕ b) ⊕ c〉
Como f: 〈A, ⊕〉 → 〈B, ⊗〉 preserva a operação
• f〈a ⊕ (b ⊕ c)〉 = f〈(a ⊕ b) ⊕ c〉 ⇔ 
• f〈a〉 ⊗ f〈(b ⊕ c)〉 = f〈(a ⊕ b)〉 ⊗ f〈c〉 ⇔ 
• f〈a〉 ⊗ (f〈b〉 ⊗ f〈c〉) = (f〈a〉 ⊗ f〈b〉) ⊗ f〈c〉
Logo, preserva a associatividade
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 65
Caso 2: 〈B, ⊗〉 é semigrupo
Para quaisquer a ∈ A, b ∈ A e c ∈ A
• f〈a ⊕ (b ⊕ c)〉 = f preserva a operação
• f〈a〉 ⊗ f〈b ⊕ c〉 = f preserva a operação
• f〈a〉 ⊗ (f〈b〉 ⊗ f〈c〉) = ⊗ é associativa
• (f〈a〉 ⊗ f〈b〉) ⊗ f〈c〉 = f preserva a operação
• f〈a ⊕ b〉 ⊗ f〈c〉 = f preserva a operação
• f〈(a ⊕ b) ⊕ c〉
Logo, preserva a associatividade
Portanto, hom de semigrupos é como um hom. de grupóides
• basta preservar a operação
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 66
Def: Homomorfismo de Semigrupos
〈A, ⊕〉 e 〈B, ⊗〉 semigrupos
Homomorfismo de Semigrupos
h: 〈A, ⊕〉 → 〈B, ⊗〉
• é um homomorfismo de grupóides h: 〈A, ⊕〉 → 〈B, ⊗〉
Isomorfismo de semigrupos
• se e somente se h possui um hom. de semigrupos inverso
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 67
◆ Comutatividade
• raciocínio análogo
• exercício
Teorema: Hom. de Grupóides Preserva Comutatividade
〈A, ⊕〉 e 〈B, ⊗〉 grupóides
f: 〈A, ⊕〉 → 〈B, ⊗〉 hom. de grupóides
Se 〈A, ⊕〉 ou 〈B, ⊗〉 é abeliano
• então f: 〈A, ⊕〉 → 〈B, ⊗〉 preserva a comutatividade
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 68
9 – Álgebras e Homomorfismos
9.1 Operações Binárias
9.2 Propriedades das Operações Binárias
9.3 Grupóides, Semigrupos, Monóides, Grupos
9.4 Importantes Propriedades dos Monóides e
Grupos
9.5 Homomorfismos
9.5.1 Grupóides e Semigrupos
9.5.2 Monóides
9.5.3 Grupos
9.6 Monóide Livre Gerado e Fecho de Kleene
9.7 Grafos
9.8 Categorias
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 69
9.1.2 Homomorfismo de Monóides
◆ Mapeamento de monóides
• preservar a operação
• não necessariamente implica preservar o elemento neutro
∗ exercício
◆ Homomorfismo de monóides
• função entre os conjuntos suportes tal que, preserva
∗ operação (como hom. de grupóides/semigrupos)
∗ elemento neutro
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 70
◆ Homomorfismo de monóides
• função entre os conjuntos suportes
∗ preserva operação (como hom. de grupóides/semigrupos)
∗ preserva elemento neutro
eA
a1
a2
a3 = a1⊕a2
eB
b1
b2
b3 = b1⊗b2
 homomorfismo
〈A,⊕,eA〉 〈B,⊗,eB〉
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 71
Def: Homomorfismo de Monóides
〈A, ⊕, eA〉 e 〈B, ⊗, eB〉 monóides
Homomorfismo de Monóides
h: 〈A, ⊕, eA〉 → 〈B, ⊗, eB〉
• hom. de semigrupos (ou grupóides) h: 〈A, ⊕〉 → 〈B, ⊗〉
• preserva o elemento neutro
h〈eA〉 =eB
Isomorfismo de monóides
• se e somente se possuir um hom. de monóides inverso
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 72
Exp: Homomorfismo: Identidade, Inclusão
〈A, ⊕, e〉, 〈N, +, 0〉 e 〈Z, +, 0〉 monóides
Identidade. Função identidade idA: A → A
• induz homomorfismo identidade de monóides
• isomorfismo de monóides
id〈A,⊕,e〉: 〈A, ⊕, e〉 → 〈A, ⊕, e〉
Inclusão. Função inclusão incN,Z: N → Z
• induz o homomorfismo inclusão de monóides abelianos
inc〈N,+,0〉,〈Z,+,0〉: 〈N, +, 0〉 → 〈Z, +, 0〉
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 73
Exp: Homomorfismo: União
A = { a, b } e X = { x, y, z } conjuntos
〈P(A), ∪, ∅〉 e 〈P(B), ∪, ∅〉 monóides abelianos
h: 〈P(A), ∪, ∅〉 → 〈P(X), ∪, ∅〉
tal que:
• h〈 ∅ 〉 = ∅
• h〈 { a } 〉 = { x, y }
• h〈 { b } 〉 = { y, z }
• h〈 { a, b } 〉 = { x, y, z }
Preserva elemento neutro e operação
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 74
Exp: …Homomorfismo: União
Exemplificando a preservação da operação
• h〈 { a } ∪ { b } 〉 = 
• h〈 { a, b } 〉 = 
• { x, y, z } = 
• { x, y } ∪ { y, z } = 
• h〈 { a } 〉 ∪ h〈 { b } 〉
Portanto, h〈 { a } ∪ { b } 〉 = h〈 { a } 〉 ∪ h〈 { b } 〉
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 75
Exp: Homomorfismo: Isomorfismo
O homomorfismo de grupóides (exemplo anterior)
h*: 〈{ a }*, conc, ε〉 → 〈N, +, 0〉
é um isomorfismo de monóides
• preserva operação (é hom. de grupóides)
• preserva elemento neutro
h*〈ε〉 = 0
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 76
Teorema: Composição de Homomorfismo de Monóides
〈A, ⊕, eA〉, 〈B, ⊗, eB〉 e 〈C, ∇, eC〉 monóides
f: 〈A, ⊕, eA〉 → 〈B, ⊗, eB〉 e g: 〈B, ⊗, eB〉 → 〈C, ∇, eC〉 hom. de monóides
O homomorfismo composto
g o f: 〈A, ⊕, eA〉 → 〈C, ∇, eC〉
• induzido pela composição das funções f: A → B e g: B → C
• é um homomorfismo de monóides
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 77
Prova: (direta)
f: 〈A, ⊕, eA〉 → 〈B, ⊗, eB〉 e g: 〈B, ⊗, eB〉 → 〈C, ∇, eC〉 hom. de monóides
Como a composição de hom. de semigrupos é hom. de semigrupos
basta mostrar que g o f: 〈A, ⊕, eA〉 → 〈C, ∇, eC〉 preserva elem. neutro
• g o f〈eA〉 = definição de composição
• g〈f〈eA〉〉 = f é homomorfismo de monóides
• g〈eB〉 = g é homomorfismo de monóides
• eC
Portanto, g o f〈eA〉 = eC
Logo, g o f: 〈A, ⊕, eA〉 → 〈C, ∇, eC〉 é um homomorfismo de monóides
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 78
9 – Álgebras e Homomorfismos
9.1 Operações Binárias
9.2 Propriedades das Operações Binárias
9.3 Grupóides, Semigrupos, Monóides, Grupos
9.4 Importantes Propriedades dos Monóides e
Grupos
9.5 Homomorfismos
9.5.1 Grupóides e Semigrupos
9.5.2 Monóides
9.5.3 Grupos
9.6 Monóide Livre Gerado e Fecho de Kleene
9.7 Grafos
9.8 Categorias
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 79
9.1.3 Homomorfismo de Grupos
◆ Homomorfismo de grupos
• como homomorfismo de grupóides
• basta preservar a operação
◆ Prova-se que, em se tratando de grupos
• preservar a operação
• implica preservar
∗ elemento neutro
∗ elemento inverso
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 80
◆ Composição homs. de grupóides é hom. de grupóides
• Implica: composição de homs. de grupos é hom. de grupos
◆ Analogamente aos homs. Anteriores
• isomorfismo de grupos se e somente se
∗ possuir um homomorfismo de grupos inverso
Teorema: Homomorfismo de Grupos × Elemento Neutro
〈A, ⊕, eA〉 e 〈B, ⊗, eB〉 grupos
f: 〈A, ⊕, eA〉 → 〈B, ⊗, eB〉 homomorfismo de grupóides
Então, f preserva o elemento neutro
f〈eA〉 = eB
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 81
Prova: 
Suponha 〈A, ⊕, eA〉 e 〈B, ⊗, eB〉 grupos e f: 〈A, ⊕, eA〉 → 〈B, ⊗, eB〉 hom.
de grupóides• f〈eA〉 ⊗ f〈eA〉 = f é homomorfismo de grupóides
• f〈eA ⊕ eA〉 = elemento neutro de ⊕
• f〈eA〉 = elemento neutro de ⊗
• f〈eA〉 ⊗ eB
Portanto, f〈eA〉 ⊗ f〈eA〉 = f〈eA〉 ⊗ eB. Pela propriedade do cancelamento
f〈eA〉 = eB
Logo, f preserva o elemento neutro
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 82
Teorema: Homomorfismo de Grupos × Elemento Inverso
〈A, ⊕, eA〉 e 〈B, ⊗, eB〉 grupos
f: 〈A, ⊕, eA〉 → 〈B, ⊗, eB〉 homomorfismo de grupóides
Então f preserva o elemento inverso
(∀a ∈ A) ( f〈a〉 = f〈a〉 )
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 83
Prova: 
Suponha 〈A, ⊕, eA〉 e 〈B, ⊗, eB〉 grupos, f: 〈A, ⊕, eA〉 → 〈B, ⊗, eB〉
homomorfismo de grupóides e qualquer a ∈ A
• f〈a〉 ⊗ f〈a〉 = f é homomorfismo de grupóides
• f〈a ⊕ a〉 = elemento inverso de ⊕
• f〈eA〉 = f preserva elemento neutro
• eB = elemento inverso de ⊗
• f〈a〉 ⊗ f〈a〉 f é homomorfismo de grupóides
Portanto, f〈a〉 ⊗ f〈a〉 = f〈a〉 ⊗ f〈a〉. Pela propriedade do cancelamento
f〈a〉 = f〈a〉
Logo, f preserva o elemento inverso
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 84
9 – Álgebras e
Homomorfismos
9.1 Operações Binárias
9.2 Propriedades das Operações Binárias
9.3 Grupóides, Semigrupos, Monóides, Grupos
9.4 Importantes Propriedades dos Monóides e
Grupos
9.5 Homomorfismos
9.6 Monóide Livre Gerado e Fecho de Kleene
9.7 Grafos
9.8 Categorias
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 85
9.6 Monóide Livre Gerado e Fecho de
Kleene
◆ Já foi visto
• para um alfabeto Σ, a álgebra interna 〈Σ*, conc, ε〉 é monóide
• Σ* pode ser indutivamente definido a partir do alfabeto Σ
◆ Definição indutiva
• Base de Indução
∗ ε ∈ Σ*
∗ para qualquer x ∈ Σ, tem-se que x ∈ Σ*
• Passo de Indução
∗ se u e v são palavras de Σ*, então a concatenação u v ∈ Σ*
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 86
◆ O raciocínio pode ser aplicado a um conjunto A qq
• não necessariamente é um alfabeto (não finito)
• passo de indução
∗ considera a palavra vazia ε como elemento neutro
se u ∈ A*, então u ε = ε u = u
◆ Monóide livre
• tipo especial e importante de monóide
• conjunto suporte A* é (livremente) gerado por um conjunto A
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 87
Def: Monóide Livre, Fecho de Kleene
A conjunto
Monóide Livre Gerado por A ou Monóide Livremente Gerado por A
〈A*, conc, ε〉
• conjunto suporte A* = Fecho de Kleene de A
• A é denominado de Gerador
Base de Indução
• ε ∈ A*
• para qualquer x ∈ A, tem-se que x ∈ A*
Passo de Indução
• se u e v são palavras de A*, então a concatenação u v ∈ A*
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 88
◆ Portanto
• conjunto de todas as palavras sobre um alfabeto
∗ conjunto suporte do monóide livremente gerado pelo alfabeto
∗ Fecho de Kleene do alfabeto
• linguagem formal (como Pascal)
∗ subconjunto do Fecho de Kleene do alfabeto
◆ Condições para que monóide livre seja abeliano???
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 89
Exp: Homomorfismo – Monóides Livres
∑1 = { a, b, c } e ∑2 = { r, s } alfabetos
〈∑1*, conc1, ε〉 e 〈∑2*, conc2, ε〉 monóides
Canonicamente induzidos por funções nos geradores
• f: ∑1 → ∑2 função
∗ f〈a〉 = r
∗ f〈b〉 = r
∗ f〈c〉 = s
• g: ∑2 → ∑1 função
∗ g〈r〉 = a
∗ g〈s〉 = b
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 90
Exp: …Homomorfismo – Monóides Livres
∑1 = { a, b, c } e ∑2 = { r, s } alfabetos
Homomorfismo não induzido por função entre os geradores
∗ h〈ε〉 = ε
∗ h〈a〉 = rr
∗ h〈b〉 = rs
∗ h〈c〉 = ss
∗ se x ∈ Σ1 e w ∈ Σ1*, então h〈x w〉 = h〈x〉 h〈w〉
• exemplo
∗ h〈abc〉 = 
∗ h〈a〉 h〈bc〉 = 
∗ h〈a〉 h〈b〉 h〈c ε〉 = 
∗ h〈a〉 h〈b〉 h〈c〉 h〈ε〉 = 
∗ rr rs ss ε = 
∗ rr rs ss
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 91
9 – Álgebras e
Homomorfismos
9.1 Operações Binárias
9.2 Propriedades das Operações Binárias
9.3 Grupóides, Semigrupos, Monóides, Grupos
9.4 Importantes Propriedades dos Monóides e
Grupos
9.5 Homomorfismos
9.6 Monóide Livre Gerado e Fecho de Kleene
9.7 Grafos
9.8 Categorias
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 92
9.7 Grafos
◆ Até o momento, as álgebras apresentadas
• uma única operação
• definida sobre um único conjunto
◆ Freqüentemente, álgebras
• mais de uma operação
• operações definidas sobre mais de um conjunto
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 93
◆ Álgebras polissortidas
• definidas sobre mais de um conjunto
• termo sorte: gênero, classe ou espécie
◆ Álgebras monossortidas
• definidas sobre um único conjunto
◆ Noção de grafo
• informalmente apresentada: estudo das endorrelações
• toda endorrelação pode ser vista como um grafo
∗ e conseqüentemente, como uma álgebra
• nem todo grafo pode ser visto como uma endorrelação
∗ exercício
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 94
◆ Grafos são importantes para Computação e
Informática
◆ Estudo de Grafos é brevemente apresentado
◆ Ênfase grafos
• grafos pequenos
∗ nodos e arcos constituem conjuntos
• grafos direcionados
∗ arcos possuem sentido
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 95
◆ Grafo visto como álgebra
• nodos e arcos
∗ conjuntos sobre os quais as operações são definidas
∗ álgebra polissortida
• origem e destino
∗ operações unárias fechadas (não-internas)
∗ associam, para cada arco, o nodo origem e destino
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 96
Def: Grafo
Grafo Pequeno Direcionado ou simplesmente Grafo G
• álgebra polissortida
G = 〈V, T, orig, dest〉
• V conjunto de Nodos ou Vértices
• T conjunto de Arcos, Arestas ou Setas
• orig: T → V e dest: T → V
∗ operações totais (funções)
∗ denominadas Origem e Destino
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 97
◆ Notação
• arco t tal que orig〈t〉 = A e dest〈t〉 = B
• denotado por t: A → B
• representado na forma de diagrama
tA B
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 98
Exp: Grafo
Arco único. G1 = 〈{ A, B }, { t }, orig1, dest1〉
• orig〈t〉 = A
• dest〈t〉 = B
Nodo isolado. G2 = 〈{ X }, ∅, orig2, dest2〉
• orig2: ∅ → { X } e dest2: ∅ → { X }
• funções vazias
Arcos paralelos. G3 = 〈{ 1, 2 }, { r, s, t, u, v }, ∂03, ∂13〉
• arcos paralelos: mesmos nodos origem e destino
1 2
r
 s
t
u
vtA B X
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 99
◆ Multigrafo
• freqüentemente, grafos com arcos paralelos são ditos multigrafos
◆ Homomorfismo de grafos
• preserva a estrutura dos grafos,
• ao mapear os nodos e arcos
∗ deve preservar as operações origem e destino
• mapeamento de um arco
∗ de acordo com o mapeamento dos seus nodos origem e destino
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 100
Def: Homomorfismo de Grafos
G1 = 〈V1, T1, orig1, dest1〉 e G2 = 〈V2, T2, orig2, dest2〉 grafos
h: G1 → G2
par de funções
h = 〈hV, hT〉
onde
hV: V1 → V2 e hT: T1 → T2
tais que
orig2 o hT = hV o orig1 e dest2 o hT = hV o dest1
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 101
Exp: Homomorfismo de Grafos
A
B
C
1 2
3
r
s
t
a
bc
d
e
G1 G2 hV
 hT
• existe mais algum homomorfismo de grafos de G1 para G2?
• existe pelo menos um morfismo de G2 para G1?
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 102
Teorema: Composição de Homomorfismos de Grafos
Sejam f: G1 → G2 e g: G2 → G3 homomorfismos de grafos
g o f: G1 → G3
tal que g o f = 〈gV o fV, gT o fT〉, é um homomorfismo de grafosProva: (direta)
Seja t: A → B arco de G1. Então
• t: A → B é arco de G1 ⇒
• fT(t): fV(A) → fV(B) é arco de G2 (f é hom. de grafos) ⇒
• gT(fT(t)): gV(fV(A)) → gV(fV(B)) é arco de G3 (g é hom. de
grafos)
Logo, g o f é homomorfismo de grafos
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 103
9 – Álgebras e
Homomorfismos
9.1 Operações Binárias
9.2 Propriedades das Operações Binárias
9.3 Grupóides, Semigrupos, Monóides, Grupos
9.4 Importantes Propriedades dos Monóides e
Grupos
9.5 Homomorfismos
9.6 Monóide Livre Gerado e Fecho de Kleene
9.7 Grafos
9.8 Categorias
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 104
9.8 Categorias
◆ Em um primeiro momento, Teoria das Categorias pode
ser vista como
• generalização da álgebra de funções
• principal operação: composição de funções
◆ Categoria é uma estrutura abstrata
• constituída de objetos e setas entre os objetos
• com uma propriedade fundamental
∗ composicionalidade das setas
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 105
Categoria Objetos Setas Composição
conjuntos e funções conjuntos funções (totais) composição de funções
figuras figuras transform. de figuras construtor de transform.
“complexas”
um programa
funcional
tipos de dados operações construtor operações
não-primitivas
espaços vetoriais espaços vetoriais transforma. lineares composição de
transformações lineares
grafos grafos homomorfismo de
grafos
composição
homomorfismo de grafos
lógica proposições provas transitividade das provas
uma máquina de
estados
estados transições construtor de
computações
conjuntos
parcialmente
ordenados
conjuntos
parcialmente
ordenados
funções monotônicas composição de funções
monotônicas
um conjunto
parcialmente
ordenado
elementos do
conjunto
pares da relação de
ordem parcial
transitividade da relação
de ordem parcial
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 106
◆ Qq modificação sobre objetos, setas ou composição
• nova categoria
Exp: Conjuntos e Funções
Substituição das funções (totais) por funções parciais
• nova categoria
∗ conjuntos e funções parciais
∗ com diferentes propriedades
• produto cartesiano
∗ generalizado categorialmente
∗ diferente nas duas categorias
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 107
◆ Objeto, seta e composição
• não necessariamente possuem estruturas
∗ que lembrem as da Teoria dos Conjuntos
Exp: Conjunto Parcialmente Ordenado como Categoria
0 1 20 ≤ 1 1 ≤ 2
(0 ≤ 2) = (1 ≤ 2) • (0 ≤ 1)
0 ≤ 0 1 ≤ 1 2 ≤ 2
• objetos - não possuem qualquer estrutura (elementos de conjunto)
• setas - pares de elementos
• composição - transitividade da relação
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 108
◆ Uma mesma estrutura, simultaneamente
• pode constituir uma categoria por si só
∗ conj. parcialmente ordenado como categoria
• ou ser objeto de uma categoria
∗ categoria dos conj. parcialmente ordenados
∗ (conjuntos parcialmente ordenados e funções monotônicas)
Exp: Categoria dos Conjuntos Parcialmente Ordenados
• pode ser vista como uma categoria de categorias
∗ uma categoria
∗ cujos objetos são conjuntos parcialmente ordenados vistos
como categorias
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 109
◆ Teoria das Categorias e Ciência da Computação
• possuem muito em comum
• são enriquecidas mutuamente
∗ a partir de visões e abordagens de um campo sobre o outro
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 110
◆ Entre as características que motivam o seu uso
• destaca-se a expressividade de suas construções
• observado nas Diretrizes Curriculares do MEC para Cursos de
Computação e Informática
Teoria das Categorias possui construções cujo poder de
expressão não possui, em geral, paralelo em outras teorias. Esta
expressividade permite formalizar idéias mais complexas de forma
mais simples, bem como propicia um novo ou melhor
entendimento das questões relacionadas com toda a Ciência da
Computação. Como Teoria das Categorias é uma ferramenta
nova, para exemplificar, vale a pena estabelecer um paralelo com
a linguagem Pascal: Teoria das Categorias está para a Teoria dos
Conjuntos assim como Pascal está para a linguagens Assembler.
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 111
◆ Apenas o conceito de categoria (como álgebra) é
apresentado
• estudo de suas propriedades e aplicações
∗ não é objetivo desta disciplina
◆ Categoria é basicamente um grafo
• eventualmente grande
• arcos são componíveis, formando caminhos
• cada nodo possui um endoarco especial: identidade
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 112
Def: Categoria
Uma álgebra polissortida
C = 〈ObC, MorC, orig, dest, ι, o〉
• ObC - coleção de Objetos
• MorC - coleção de Morfismos ou Setas
• orig: MorC → ObC e dest: MorC → ObC
∗ operações fechadas e totais Origem e Destino
∗ um morfismo f tal que orig(f) = A e dest(f) = B é denotado por
f: A → B
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 113
• o: (MorC )2 → MorC - operação Composição
∗ cada par de morfismos
 〈f: A → B, g: B → C〉
∗ é associado a um morfismo
 g o f: A → C
∗ deve satisfazer a propriedade associativa
(h o g) o f = h o (g o f)
• ι: ObC → MorC - operação Identidade
∗ cada objeto A é associado a um morfismo
ιA: A → A
∗ deve satisfazer a propriedade da identidade (suponha f: A → B)
f o ιA = ιB o f = f
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 114
Exp: Categoria Set
Set = 〈ObSet, MorSet, orig, dest, ι, o〉
• ObSet - coleção de todos os conjuntos
• MorSet - coleção de todas as funções (totais)
• orig: MorSet → ObSet e dest: MorSet → ObSet
∗ para qualquer função f com domínio em A e codomínio em B,
orig(f) = A e dest(f) = B
• o: (MorSet  )2 → MorSet
∗ operação de composição de funções (é associativa)
• ι: ObSet → MorSet - operação identidade
∗ cada conjunto A é associado à função identidade idA: A → A
ι〈A〉 = idA
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 115
Exp: Categoria Mon
• objetos: todos os monóides
• morfismos: todos os homomorfismos de monóides
• composição: composição de homomorfismos de monóides
• identidade: dada pelo homomorfismo identidade de cada monóide
◆ Análogamente, as categorias
• grupóides e correspondentes homomorfismos
• semigrupos e corrrespondentes homomorfismos
• grupos e corrrespondentes homomorfismos
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 116
Exp: Categoria Gr
• objetos: todos os grafos
• morfismos: todos os homomorfismos de grafos
• composição: composição de homomorfismos de grafos
• identidade: dada pelo homomorfismo identidade de cada grafo
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 117
Exp: As "Menores" Categorias
Categoria Vazia (justifique cada componente)
〈∅, ∅, ∅, ∅, ∅, ∅〉
Categoria 1
• um objeto e um morfismo (identidade desse objeto)
Categoria 1+1
• dois objetos e dois morfismos (identidade)
Categoria 2
• dois objetos e três morfismos (sendo dois identidade)
 2
A B
 1+1
A B
 1
 A
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 118
EXEMPLO Categoria Três Porquinhos e o Lobo Mau
3 porquinhos P1, P2 e P3, o lobo mau L e os morfismos “persegue”
com origem no lobo mau e destino em cada um dos porquinhos,
além dos morfismos identidade "outra atividade qualquer"
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 119
Matemática Discreta para Ciência da Computação
P. Blauth Menezes
1 Introdução e Conceitos Básicos
2 Lógicae Técnicas de Demonstração
3 Álgebra de Conjuntos
4 Relações
5 Funções Parciais e Totais
6 Endorrelações, Ordenação e Equivalência
7 Cardinalidade de Conjuntos
8 Indução e Recursão
9 Álgebras e Homomorfismos
10 Reticulados e Álgebra Booleana
11 Conclusões
Matemática Discreta para Ciência da Computação - P. Blauth Menezes 120
Matemática Discreta para
Ciência da Computação
P. Blauth Menezes
blauth@inf.ufrgs.br
Departamento de Informática Teórica
Instituto de Informática / UFRGS