Slides 13

Prévia do material em texto

1
Matemática Discreta
Aula nº 13
Francisco Restivo
2006-04-20
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.
2
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 Cawley) em que o 
resultado x * y fica na intersecção da linha x com a coluna y:
acbdd
aabcc
bacdb
dcbaa
dcba*
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).
3
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
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 Cawley de um grupo (G, *) finito, cada elemento de 
G aparece uma e uma só vez em cada linha.
4
7
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:
baecc
aecbb
ecbaa
cbaee
cbae*
8
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
r0r1r2m1m2m3m3
r2r0r1m3m1m2m2
r1r2r0m2m3m1m1
m2m1m3r1r0r2r2
m1m3m2r0r2r1r1
m3m2m1r2r1r0r0
m3m2m1r2r1r0*
1
2 3
1
3 2
3
2 1
m1 * r2 = m2
Grupo diedral de ordem 3:
5
9
Grupos de permutações:
Uma permutação de um conjunto S é uma bijecção de S sobre S:
24
33
42
11
p1(x)x
ú
û
ù
ê
ë
é
=
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).
10
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: