Slides 12 0607

Prévia do material em texto

Matemática Discreta
Aula nº 12
Francisco Restivo
2007-04-12
2
Estruturas algébricas:
A união e a intersecção de conjuntos, a composição de funções, a 
adição e a multiplicação de matrizes, as operações aritméticas no 
conjunto dos números reais, são operações binárias.
A subtracção não é uma operação binária no conjunto Z+ dos 
inteiros positivos (o resultado não pode ser negativo).
A divisão não é uma operação binária em Z (resultado não pode 
ser fraccionário), nem em Q (divisão por zero).
Operações binárias:
Uma operação binária ∗ num conjunto não vazio S é uma regra 
para combinar dois elementos x, y ∈ S para produzir um elemento 
z ∈ S, representado como x ∗ y.
De outro modo, uma operação binária num conjunto não vazio S é
uma função f: S × S → S. Se x e y são elementos de S, f(x, y) é
representado como x ∗ y.
3
Definições:
Propriedade associativa: se e só se ∀x,y,z∈S, (x∗y)∗z = x∗(y∗z)
Propriedade comutativa: se e só se ∀x,y∈S, x∗y = y∗x
Elemento identidade e: se e só se ∀x∈S, x∗e = e∗x = x
Elemento inverso y = x-1: se e só se x∗y = y∗x = e
Tabelas:
Uma operação binária ∗ num conjunto não vazio S pode ser 
definida por uma tabela bidimensional (de Cayley) em que o 
resultado x ∗ y fica na intersecção da linha x com a coluna y:
∗ a b c d
a a b c d
b d c a b
c c b a a
d d b c a
4
Teorema:
Numa operação binária ∗ em S, se existir elemento identidade, ele 
é único.
Teorema:
Numa operação binária associativa ∗ em S, com elemento 
identidade e, se existir elemento inverso, ele é único.
Se y∗x = x∗y = e e z∗x = x∗z = e, então y = y∗e = y∗(x∗z) = (y∗x)∗z = e∗z = z
Definição:
Um conjunto não vazio S com uma operação binária associativa ∗
(S, ∗) diz-se um semigrupo: ∀x,y,z∈S, (x∗y)∗z=x∗(y∗z)
Se a operação binária ∗ for comutativa, o semigrupo diz-se 
abeliano (ou comutativo).
5
Definição:
Um semigrupo (S, ∗) com elemento identidade diz-se um monóide.
Se a operação binária ∗ for comutativa, o monóide diz-se um 
monóide abeliano (ou comutativo).
Definição:
Um monóide (S, ∗) em que cada elemento tem um elemento 
inverso diz-se um grupo.
Se a operação binária ∗ for comutativa, o grupo diz-se um grupo 
abeliano (ou comutativo).
Muitas vezes omite-se o símbolo ∗ nas expressões algébricas, 
desde que daí não resulte confusão (notação multiplicativa). 
Não esquecer que xy = yx só se a operação for comutativa.
Também se pode usar a operação ‘potência’ xn = x ∗ x ... ∗ x.
Se a operação binária é a adição, utiliza-se a notação aditiva.
6
Semigrupo Monóide Grupo
Propriedade 
associativa
sim sim sim
sim
sim
Grupo 
Abeliano
Elemento 
identidade
sim
Elemento 
inverso
Propriedade 
comutativa
Semigrupo 
Abeliano
Monóide 
Abeliano
7
Definição:
A ordem de um grupo (G, ∗) é a cardinalidade do conjunto G, |G|.
Teorema:
Num grupo (G, ∗) verificam-se as leis do cancelamento
i) à esquerda: se ax = ay então x = y
ii) à direita: se xa = ya então x = y
Teorema:
Num grupo (G, ∗) 
i) a equação ax = b tem uma solução única x = a-1b 
ii) a equação ya = b tem uma solução única y = ba-1
Teorema:
Na tabela de Cayley de um grupo (G, ∗) finito, cada elemento de 
G aparece uma e uma só vez em cada linha.
8
Um grupo (G, ∗) diz-se cíclico se existe um elemento a ∈ G tal que 
∀g∈G, ∃n∈Z tal que g = an. 
O elemento a diz-se o elemento gerador do grupo (G, ∗).
Grupos cíclicos:
Considere-se o seguinte grupo:
∗ e a b c
e e a b c
a a b c e
b b c e a
c c e a b
9
Grupos diedrais:
1
2 3
1
2 3
3
1 2
2
3 1
3
2 1
2
1 3
1
3 2
r0
r1
r2
m1
m2
m3
∗ r0 r1 r2 m1 m2 m3
r0 r0 r1 r2 m1 m2 m3
r1 r1 r2 r0 m2 m3 m1
r2 r2 r0 r1 m3 m1 m2
m1 m1 m3 m2 r0 r2 r1
m2 m2 m1 m3 r1 r0 r2
m3 m3 m2 m1 r2 r1 r0
1
2 3
1
3 2
3
2 1
m1 ∗ r2 = m2
Grupo diedral de ordem 3:rotate
mirror
10
Grupos de permutações:
Uma permutação de um conjunto S é uma bijecção de S sobre S:
x p1(x)
1 1
2 4
3 3
4 2
⎥⎦
⎤⎢⎣
⎡=
2341
4321
p1
No conjunto de todas as permutações de um conjunto S pode 
definir-se a operação binária composição de permutações: pipj, pi
seguido de pj (e não pi depois de pj, como no caso da composição de funções).
primeira linha, posição inicial; segunda linha, posição final
11
Exemplo:
Conjunto de todas as permutações do conjunto {1, 2, 3}
⎥⎦
⎤⎢⎣
⎡=⎥⎦
⎤⎢⎣
⎡=⎥⎦
⎤⎢⎣
⎡=
⎥⎦
⎤⎢⎣
⎡=⎥⎦
⎤⎢⎣
⎡=⎥⎦
⎤⎢⎣
⎡=
312
321
p 
123
321
p 
231
321
p
213
321
p 
132
321
p 
321
321
p
654
321
453 p231
321
123
321
213
321
pp =⎥⎦
⎤⎢⎣
⎡=⎥⎦
⎤⎢⎣
⎡⎥⎦
⎤⎢⎣
⎡=
Operação binária:
12
Tabela de Cayley do conjunto de todas as permutações do 
conjunto {1, 2, 3}
∗ p1 p2 p3 p4 p5 p6
p1 p1 p2 p3 p4 p5 p6
p2 p2 p3 p1 p5 p6 p4
p3 p3 p1 p2 p6 p4 p5
p4 p4 p6 p5 p1 p3 p2
p5 p5 p4 p6 p2 p1 p3
p6 p6 p5 p4 p3 p2 p1
Tem a propriedade associativa (decorre da composição de funções). 
O elemento identidade é p1. Todos os elementos têm elemento inverso. 
É um grupo não Abeliano. 
	Matemática Discreta