Md9 estruturas algébricas

1. Módulo 6:
Estruturas Matemáticas
•Modelos matemáticos de fenômenos da natureza podem
ser divididos em três grandes categorias:
•Estruturas de Ordem <C, R>
•Estruturas Algébricas <C, Op>
•Estruturas Topológicas (Geometria, Análise) <C, P(C)>
•UNIVERSIDADE FEDERAL DE CAMPINA GRANDE
•CENTRO DE ENGENHARIA ELÉTRICA E INFORMÁTICA
•DEPARTAMENTO DE SISTEMAS E COMPUTAÇÃO
•Professor Ulrich Schiel

2. Estruturas Algébricas
•Estruturas Algébricas:
- conjunto abstrato de objetos juntamente com operações e
relações entre esses objetos e que obedecem certas regras.
A = <C, Op, R>
Em que Op é um conjunto de operações e R é um conjunto de
relações
Se R é vazio temos uma Álgebra,
se Op é vazio temos um Modelo ou um Sistema Relacional

3. Estruturas Algébricas
•Estruturas Algébricas - Operações:
Uma operação (interna) * sobre um conjunto C, é uma função
*:C´.. ´ C ® C
Exemplos: A = <Z, +>; B = <Z, +, £>;
C = < Z, £ >; D = < N, succ, *, 0, 1, max, min >
 Uma operação externa * de um domínio K sobre um conjunto
C, é uma função
* : K ´ C ® C
Exemplo:
E = < N, R
2
, *>, com *: N´R
2
® R
2
, dado por *(k,(x,y)) = (kx,ky)

4. Estruturas Algébricas
•DEFINIÇÃO:
•Uma Álgebra é um par <C, Op> com:
- C é um conjunto
- Op é um conjunto de operações sobre C
NOTAÇÃO: dado uma álgebra <C,*>, com
*:C ´ C ® C
para *(a,b) = c escrevemos a*b = c

5. Estruturas Algébricas
Propriedades das operações:
- Dado uma álgebra <C,*> as seguintes propriedades podem
ser válidas, para quaisquer x, y, z de C:
x * y = y * x (comutativa)
(x * y) * z = x * (y * z) (associativa)
$ 1ÎC (x * 1 = x)(identidade ou neutro à direita)
"x ÎC $ x
’
ÎC (x * x’ = 1) (inverso)
Se houver outra operação + em C, ou seja, temos <C,*, Å>,
pode valer a propriedade:
x Å (y * z) = (x Å y) * (x Å z) (distributiva-1)
x * (y Å z) = (x * y) Å (x * z)(distributiva-2)

6. Estruturas Algébricas
•Estruturas Algébricas – Álgebras de Boole
•Um exemplo notável de estrutura algébrica é a
álgebra booleana ou Álgebra de Boole (George
Boole, 1850), formulada inicialmente para modelar a
lógica proposicional e utilizada posteriormente por
Shannon (1938) para modelar circuitos eletrônicos
(ou digitais).

7. Álgebra Booleana
→Uma Álgebra de Boole B é uma álgebra
B = <B, +, ·, ‘, a, b> formada por
→um conjunto não-vazio (domínio) B,
→duas operações binárias + : B
2
→B e ·
: B
2
→B,
→uma operação unária ‘ : B→B e
→dois elementos distinguíveis de B, a e b,(funções 0-árias)
satisfazendo as seguintes propriedades:
→ para todo x, y e z pertencentes à B vale
•1a. x+y = y+x 1b. x · y = y · x
•2a. (x+y)+z = x+(y+z)2b. (x · y) · z = x · (y · z)
•3a. x+(y · z) = (x+y)·(x+z)3b. x · (y+z) = (x · y)+(x · z)
•4a. x+a = x 4b. x · b = x
•5a. x+x’ = b 5b. x · x’ = a

8. Álgebra Booleana
•Exemplo 1: B1 = <{0,1}, +, ·, ‘, 0, 1>, onde:
•x+y = max(x,y), x · y = min(x,y), 0’=1 e 1’=0.
•Exemplo 2: B2 = <{Æ, {1}, {2}, {1,2}}, È, Ç, ‘, Æ, {1,2} >
•Exemplo 3: B3 = <P(S), È, Ç, ‘, Æ, S>, para qualquer S
•Exemplo 4: B4 = <{F,V}, OR, AND, NOT, F, V>.

9. Propriedades de uma àlgebra de Boole
•Demonstre as seguintes propriedades para uma
álgebra de Boole B = <B, +, ·, ‘, a, b> :
1.x+x = x, para todo x Î B (Idempotência)
2.x+b = b, para todo x Î B
3.(x ’) ’ = x, para todo x Î B (involução)
4.x+(x · y) = x, para todo x, y Î B
5.(x+y)’ = x ’ · y ’ e (x·y)’ = x’ + y’ (Leis de De Morgan)
1.Variante: x.y=(x’+y’)’ e x+y=(x’.y’)’
6.O elemento neutro é único.

10. Álgebra Booleana – conjuntos completos de
operadores
•Considerando a álgebra de Boole
B4 = <{F,V}, OR, AND, NOT, F, V>.
pode-se mostrar que toda expressão booleana pode ser
realizada com um dos conjuntos
{AND, OR, NOT} ou {+, ·, ‘}
{AND, NOT} ou {·, ‘}
{NAND} ou {‘·} xNANDy = NOT(xANDy) ou x ’· y = (x·y)’
{NOR} ou {‘+} xNORy = NOT(xORy) ou x ‘+ y = (x+y)’

11. Álgebra Booleana – conjuntos completos de operadores
•Para escrever uma expressão booleana apenas com operadores NANDNAND deve-se
•(1) colocá-la na forma normal disjuntiva-FND (somas de produtos) e
•(2) eliminar as somas com as leis de DeMorgan
• (3) converter os produtos em NAND usando involução
•(4) eliminar as negações pela fórmula x’ = (x.1)’ = x '· 1
•EXEMPLO:EXEMPLO: x+(y·z’)=
deMorg
(x’ . (y.z’)’)’ =
defNAND x’ '· (y.z’)’ =
defNAND x’ '· (y '· z’)
•=
defNOT (x '· 1) '· (y '· (z '· 1))
•Para escrever uma expressão booleana apenas com operadores NORNOR deve-se
•(1) colocá-la na forma normal conjuntiva-FNC (produtos de somas) e
•(2) eliminar os produtos com as leis de DeMorgan
• (3) converter as somas em NOR usando involução
•(4) eliminar as negações pela fórmula x’ = (x+0)’ = x ‘+ 0
•EXEMPLO:EXEMPLO: x+(y.z’) =
distrib (x+y).(x+z’) =

deMorg [(x+y)’ + (x+z’)’]’ =
•=
defNOR (x '+ y) '+ (x '+ z’) =
OBS-2 (x '+ y) '+ (x '+ (z '+ 0))

12. Álgebra Booleana – Exemplo de conversão
(1) Escreva a expressão booleana (x+(y·z’))’ com operadores NANDNAND
•(1) FND:(1) FND: (x+(y·z’))’ =
distrib ((x+y).(x+z’))’ =deMorgan (x+y)’ + (x+z’)’
• =deMorgan (x’.y’) + (x’.z) =
•(2) deMorgan: (2) deMorgan: = (= ((x’.y’)’ . (x’.z)’)’
•(3) involução+def(3) involução+def = (((x’.y’)’ . (x’.z)’)’ = (x’.y’)’ '· (x’.z)’ = (x’ '· y’) '· (x’ '· z)
•(4) elim. negações(4) elim. negações = ((x '·1) '· (y '·1)) '· ((x '·1) '· z)
(2) Escreva a expressão booleana (x+(y·z’))’ com operadores NORNOR
•(1) FNC:(1) FNC: (x+(y·z’))’ =deMorgan x’ . (y.z’)’ =deMorgan x’ . (y’+z) =
•(2) deMorgan: (2) deMorgan: =deMorgan (x + (y’+z)’)’
•(3) involução+def:(3) involução+def: = x ‘+ (y’+z)’ = x ‘+ (y’ ‘+ z)
•(3) elim. Negações:(3) elim. Negações: = x ‘+ ((y ‘+ 0) ‘+ z))

13. Exercícios
• Escrever a expressão booleana x.(y’+z)
• apenas com operadores NANDNAND
• apenas com operadores NORNOR
• Calcule o valor da expressão para x=1, y=0 e z=0. Use primeiro a
expressão original e depois a com NAND e com NOR.
Exercício adicional: (x+y).(x.y)’

14. Funções Booleanas
Dado uma álgebra de Boole
B = <B, +, ·, ‘, a, b>
Uma função booleana é uma função
f: B x...x B ® B
determinada por uma expressão da álgebra de Boole.
Exemplo:
f(x,y,z) = x.y + x.z’ + y.z'

15. Funções Booleanas
Formas de definição de uma
função booleana:
• algébrica
•tabular (tabela verdade)
• esquemática
•Definição algébricaalgébrica:
f(x,y,z)=x+(y'⋅z)
•Definição tabulartabular :
•Definição esquemáticaesquemática:
x y z f(x,y,z)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1

y
z
x
f(x,y,z)

16. Funções Booleanas
Conectores lógicos:
•inversorinversor •NOTNOT
•ANDAND •NANDNAND
•OROR •NORNOR
•XORXOR •XNORXNOR
NOT(x) = x’
AND(x,y) = x.y
OR(x,y) = x+y
NAND(x,y) = (x.y)’
NOR(x,y) = (x+y)’
XOR(x,y) = (x+y).(x.y)’
XNOR(x,y) = ((x+y).(x.y)’)’

17. Funções Booleanas
Conversões:
• algébrica => tabular (resolver cada trecho da expressão)
•tabular => algébrica (FND: cada linha com valor 1 é uma expressão AND;
combinar linhas com OR)
• algébrica <=> esquemática (substituir componentes)
• tabular <=> esquemática (converter para algébrica)

18. Funções Booleanas
Exemplo:
1. seja a função f(x,y) = (x+y’).(x’+y)
• encontre suas definições tabular e esquemática
2. seja a função f(x,y) dada
pela tabela ao lado:
• encontre suas
definições algébrica e
esquemática
x y f(x,y)
0 0 1
0 1 1
1 0 1
1 1 0

19. Funções Booleanas
Redução de uma expressão Booleana:
f(x,y) = (x’.y’) + (x.y’)+ (x’.y) =
=
[3b]
(x’+x).y’ + (x’.y)
=
[5a+4b]
y’ + (x’.y) =
[3a]
(y’+x’)(y’+y) =
[5a]
(y’+x’).1
=
[4b]
y’+x’ =
[deMorgan]
(x.y)’
1.f(x,y) = (x’.y’) + (x.y’)+ (x’.y) =? (x.y)’
Forma normal disjuntiva (soma de produtos)

20. Funções Booleanas
Exercícios:
1. seja a função f(x,y,z) = (x.y’).(y+z’)
• encontre suas definições tabular e esquemática
2. seja a função
f(x,y,z) dada pela
tabela ao lado:
• encontre suas
definições algébrica
(reduzida) e
esquemática
x y z f(x,y,z)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

21. Álgebras - Homomorfismos e Isomorfismos
•Entre conjuntos temos funções
f:C → D
•Entre estruturas matemáticas ou álgebras ou categorias
temos morfismos
h:<A, op
A
> → <B, op
B
>,
com h: A → B e h: op
A
→ op
B
funções
•Dados duas Álgebras A=<A, *
A
> e B=<B, *
B
>, um morfismo

h: A → B
é um homomorfismo se conserva as operações, ou
seja, para todo a,b Î A temos
• h(a *
A
b) = h(a) *
B
h(b)

22. Álgebras - Homomorfismos e Isomorfismos
•Duas estruturas matemáticas A e B são ditas serem
isomorfas se e somente se existir uma bijeção
(isomorfismo) que leva elementos de uma em
elementos da outra de modo que as propriedades
(funções e relações) sejam preservadas.
•Se duas estruturas são isomorfas então cada uma é
a imagem semelhante da outra, a menos do
rotulamento de seus elementos.
•Ex.: considere os seguintes POSET’s:
• P
1
= ({1,2,3,6}, x divide y)
•
• P
2
= (P({1,2}), xÍy)

23. Isomorfismo
•
• Seja h:: {1,2,3,6} → P({1,2}) definida por:
• h(1) = Æ; h(2) = {1}; h(3) = {2}; h(6) = {1,2}
h é um isomorfismo de P
1
em P
2
2
6
3
1
{1}
{1,2}
{2}
Æ
h

24. Isomorfismo de álgebras booleanas
•Sejam A = <A, +, ·, ‘, a, b > e B = <B, &, *, “, c, d >
duas álgebras booleanas.
Um morfismo f: A → B é um isomorfismo de A em B,
se para todo x e y ÎA:
1.f é uma bijeção entre A e B
2.f(x+y) = f(x) & f(y)
3.f(x.y) = f(x)
*
f(y)
4.f(x’) = f(x)”

25. Isomorfismo
Princípio da dualidade em Álgebras de Boole
Para qualquer Álgebra de Boole
• B = <B, +, ·, ‘, a, b>
A estrutura
B
D
= <B, ·,+, ‘, b, a>
É uma Álgebra de Boole e, além disso,
B @ B
D

são isomorfos

26. Teorema de álgebras booleanas finitas
Teorema: Seja B qualquer álgebra booleana com |B|=n
elementos. Então,
•n = 2
m
, para algum inteiro m, e
•B é isomorfa a <P({1,2,..,m}), È, Ç, ‘, Æ, {1,2,..m}> .
Corolário: o número de elementos do domínio de
qualquer álgebra booleana é uma potência de 2.

27. Isomorfismo
x,y ÎB
f
u,vÎA
operação (+,
.
, ‘)
operação (&, *, “)
z ÎB
f
-1
w ÎA
Podemos implementar uma operação em outra estrutura:
P.ex.: u&v = f
-1
(f(u)+f(v))

28. Exemplo
Sejam
C = <{a, b, c, d}, sup, inf>,
onde as operações são dadas pelas
tabelas ao lado, e
B = <P({1,2}), È, Ç> duas álgebras.
Seja o morfismo f:{a,b,c,d} → P({1,2}) dada
por:
f(a) = Æ f(b) = {1} f(c) = {2}
f(d) = {1,2}
2. Calcule
inf(sup(a,b),b) = f
-1
(f(a) È f(b)Çf(b))
supa b c d
aa b c d
b b b d d
c c d c d
d d d d d
inf
a b c d
a a a a a
b a b a b
c a a c c
d a b c d

29. Álgebras
Seja S um conjunto e * uma operação binária :
* : S x S → S.
1.A operação * é associativa (A) se:
x * (y * z) = (x * y) * z, para quaisquer x, y e z Î S.
1.S tem um elemento neutro (N) em relação à
operação * se:
existe i Î S tal que para todo x Î S, x * i = x = i * x .
1.Todo elemento tem um inverso (I) em relação à
operação * se:
para todo x Î S existe yÎ S tal que x * y = i = y * x .
Notação: y= x
-1
1.A operação * é comutativa (C) se:
x * y = y * x, para todo x e y Î S.
Exemplo: As estruturas < Z, + >, < Z, . >.

30. Grupo
→Uma estrutura G = < S, * > é um grupo se S é um
conjunto não vazio e * é uma operação binária sobre S
(operação de grupo) tal que:
1.* é associativa;
2.S tem um elemento neutro ;
3.todo elemento de S tem um elemento inverso

→Se valer só a associatividade temos um semi-grupo.
→ Se valer a associativa e neutro temos um monóide
→Obs. Um grupo em que * é comutativa é chamado de
grupo comutativo ou abeliano.
→Exemplos: A estrutura < Z, + > é um grupo comutativo.
E <Z, .> ??

31. Exemplo
Seja R
+
o conjunto dos reais positivos e seja . a
operação de multiplicação de reais. Então :

• < R
+
, . > é um grupo comutativo.
• O elemento neutro é o 1.
• Para qualquer real positivo x, 1/x é o seu inverso com
relação à operação de multiplicação.
• < R
+
, + > é um semi-grupo comutativo.

32. Exercícios
1.< R, . > é um grupo ? É semi-grupo?
1.< Z, - > é um grupo ? É semi-grupo?
1.Seja M
2
(Z) o conjunto das matrizes 2x2 de
elementos inteiros e seja + a operação de adição de
matrizes. Mostre que < M
2
(Z), + > é um grupo
comutativo. Mostre que < M
2
(Z), . > não é um grupo.
Temos o grupo <Z, +> e o semi-grupo <Z, .>.
O que será <Z, +, .> ??

33. Anel
→Uma álgebra G = < S, +, * > é um anel se valem as
seguintes propriedades:
1.< S, + > é um grupo abeliano;
2.< S, * > é um semi-grupo;
3.Vale a distributividade a esquerda e a direita da
operação * sobre +, ou seja,
a*(b+c)= a*b + a*c e (a+b)*c = a*c + a*c
Um anel é comutativo se * é comutativa.
Exemplos: Z, Q, R, C com + e . são anéis. Uma álgebra de
Boole é um anel comutativo idempotente (i.e. a.a = a)

Dado um anel <S, +, .>
O que falta para <S,*> ser um grupo ??

34. Corpo
→Uma álgebra G = < S, +, * > é um corpo se valem as
seguintes propriedades:
1.< S, + , * > é um anel com o neutro 0 em +;
2.< S-{0}, * > é um grupo comutativo;
Exemplos: Q, R, C com + e . são corpos.
→Dado um corpo < S, +, * >, podemos definir operadores
de diferença e divisão como
→ a - b = a + (-b) e a / b = a * b
-1

35. Corpo ordenado
Uma estrutura < S, +, * , ≤> é um corpo ordenado, quando
1.< S, +, * > é um corpo
2. a ≤ b → a+c ≤ b+ c
3.0 ≤ a e 0 ≤ b → 0 ≤ a.b
Exemplos: < R, +, * , ≤> é um corpo ordenado
< C, +, * , ≤> não é um corpo ordenado

36. Operadores externos
→Dado um grupo <S, +> uma operação externa * de um
domínio K sobre S é uma função:
1. * : K x S ® S, ou seja k*s
1
= s
2
;
Operações externas de um anel <K, +, . > podem ser
combinadas com operações internas do grupo :
→k * (s
1
+ s
2
) = k * s
1
+ k * s
2

→(k + m) * s = k * s + m * s
→ (k . m) * s = (k * s) . (m * s)
→1 * s = s
Que da origem a estrutura de Módulo.
Ou seja, um módulo é uma estrutura:
M = <K,S, *> em que K é um anel comutativo <K,+,.> e
S é um grupo comutativo <S,+>
Se K é um corpo, temos um espaço vetorial.

37. Operadores externos
EXEMPLOS:
1.M = <R, R
2
, *> com a soma de vetores e
k*<x,y> = <k.x, k.y> é um espaço vetorial
2.M = <Z, R
2
, *> com k*<x,y> = <k.x, k.y> é um
módulo
3.Espaço vetorial das funções reais lineares:
M = <R, F, *> em que
F = {f:R →R, com f(x)=ax+b} com
f(x)+g(x) e com k*f(x)

38. Resumo & Exemplos
Propriedades: <S,*>
* é fechada se x * y está em S
A – associativa x * (y * z) = (x * y) * z
C – comutativa x * y = y * x
N – neutro ou identidade x * i = i * x = x
I – inverso x * x
-1
= x
-1
* x = i
A ® semi-grupo
AN ® monóide
ANI ® grupo
ANIC ® grupo comutativo
Exemplos:
• grupo
• <R
+
, . > comutativo
• <M
2
(Z), +> comutativo
• <R, + > comutativo
• monóide
•<R, . > comutativo
• <N, +> comutativo
• <P(S), È> comutativo
• <P(S), Ç> comutativo
• <M
2
(Z), . > não-comutativo
• semi-grupo
• <R-{0}, +> comutativo

39. Resumo & Exemplos
Propriedades: <S,*>
* é fechada se x * y está em S
A – associativa x * (y * z) = (x * y) * z
N – neutro ou identidade x * i = i * x = x
I – inverso x * x
-1
= x
-1
* x = i
C – comutativa x * y = y * x
A ® semi-grupo
AN ® monóide
ANI ® grupo
ANIC ® grupo comutativo
Exemplos:
• grupo
• <R[x], + > comutativo
• monóide
•<R[x], . > comutativo
•
< S*, ||> não-comutativo
•
• semi-grupo
•

40. Resumo & Exemplos
Propriedades: <S,+,*>
* é fechada se x * y está em S
A – associativa x * (y * z) = (x * y) * z
N – neutro ou identidade x * i = i * x = x
I – inverso x * x
-1
= x
-1
* x = i
C – comutativa x * y = y * x
D-distributivo a *(b+c)= a * b + a * c
(a+b)*c = a*c + b*c
Dado <S,+,*> é um:
Anel se
<S, +> grupo comutativo (ANIC)
<S, *> semi-grupo (A)
vale D
Corpo se
é um anel e
< S-{0}, * > é um grupo
Corpo comutativo se
é um corpo e * é comutativa
Exemplos:
• anel
• <Z, + , . > comutativo
• corpo
• <R, +, . > comutativo
• <M
2
(Z), +, . > não-comut.
•<R[x], +, . > comutativo
•
• Em uma Álgebra de Boole
<B, +, ·, ‘, 0, 1>
<B, +> e <B, .> são monóides
comutativos

41. Exercício
Sejam
C = <{0, 1, a, b}, +, *, “, 0, 1>,
onde as operações são dadas pelas tabelas ao lado, e
B = <P({1,2}), È, Ç, ‘, Æ, {1,2}> duas álgebras booleanas.
Seja o morfismo f:{0,1,a,b} → P({1,2}) dada por:
f(0) = Æ f(1) = {1,2} f(a) = {1} f(b) = {2}
2. Calcule (a+b)”*b = f
-1
(f(a) È f(b)’ Çf(b))
+ 0 1 a b
0 0 1 a b
1 1 1 1 1
a a 1 a 1
b b 1 1 b
*
0 1 a b
0 0 0 0 0
1 0 1 a b
a 0 a a 0
b 0 b 0 b
“
01
10
ab
ba

42. Exercícios
Analise a estrutura algébrica de
1) < S*, ||> com:
S* o conjunto de todas cadeias de caracteres (strings)
|| a operação de concatenação de strings
2) < Z
7
, +
7
, .
7
> com:
Z
7
= {0,1,2,3,4,5,6} e + a soma módulo 7 e . o produto módulo 7.
3) Sendo Z=< Z
7
, +
7
,.
7
> da questão anterior e N = <N
+
, +, .> o anel
dos inteiros positivos, como será a estrutura M = < N
+
, Z, *> em
que *:N
+
x Z

® Z é o produto módulo 7 de N
+
em Z.
4) < C, sup, inf> com:
C um reticulado finito ordenado por uma relação £ e inf(x,y) é o
ínfimo de x e y e sup(x,y) é o supremo de x e y.

43. Exercícios
Mais exercícios resolvidos em
http://pt.scribd.com/doc/57701066/Matematica-Discreta-Exercicios-resolvidos
http://web.ist.utl.pt/~ist10898/public/sd/Problems/Resolv_v01.pdf
http://pt.scribd.com/doc/93333089/Estruturas-Algebricas-Exercicios-
Resolvidos