Md9 Estruturas-algébricas
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Md9 Estruturas-algébricas as PDF for free.
More details
- Words: 2,142
- Pages: 26
•UNIVERSIDADE FEDERAL DE CAMPINA GRANDE •CENTRO DE ENGENHARIA ELÉTRICA E INFORMÁTICA •DEPARTAMENTO DE SISTEMAS E COMPUTAÇÃO •Professor Ulrich Schiel
Estruturas Matemáticas • Modelos matemáticos de fenômenos da natureza podem ser divididos em três grandes categorias: • Estruturas de Ordem
• Estruturas Algébricas
• Estruturas Topológicas (Geometria, Análise)
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 = 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
Estruturas Algébricas •
Estruturas Algébricas - Operações:
Uma operação (interna) * sobre um conjunto C, é uma função *:C×.. × C → C Exemplos: A =; C = < Z, ≤ >;
B =;
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 = < R2, N, *>, com *: N → R2, dado por *(k,(x,y)) = (kx,ky)
Estruturas Algébricas
• DEFINIÇÃO: • Uma Álgebra é um par com: - C é um conjunto - Op é um conjunto de operações sobre C
Estruturas Algébricas Propriedades das operações: - Dado uma álgebra 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)
∀x ∈C ∃ x-1 ∈C (x * x-1 = 1)
(inverso)
Se houver outra operação + em C, ou seja, temos, pode valer a propriedade: x + (y * z) = (x + y) * (x+ z) e x * (y + z) = (x * y) + (x * z)
(distributiva)
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).
Álgebra Booleana → Uma Álgebra de Boole B é uma estrutura algébrica B = formada por →um conjunto não-vazio (domínio) B, →duas operações binárias + : B2→B e · : B2→B, →uma operação unária ‘ : B→B e →dois elementos distinguíveis de B, a e b, obedecendo às seguintes propriedades, para todo x, y e z pertencentes à B: • • • • •
1a. x+y = y+x 2a. (x+y)+z = x+(y+z) 3a. x+(y · z) = (x+y)·(x+z) 4a. x+a = x 5a. x+x’ = b
1b. x · y = y · x 2b. (x · y) ·.z = x · (y · z) 3b. x · (y+z) = (x · y)+(x · z) 4b. x · b = x 5b. x · x’ = a
Á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 =, para qualquer S • Exemplo 4: B4 = <{F,V}, OR, AND, NOT, F, V>.
Exercícios •
Demonstre as seguintes propriedades para uma álgebra de Boole B = :
2. x+x = x, para todo x ∈ B (Idempotência) 3. x+b = b, para todo x ∈ B 4. (x ’) ’ = x, para todo x ∈ B 5. x+(x · y) = x, para todo x, y ∈ B 6. (x+y)’ = x ’ · y ’ (Lei de De Morgan) 7. O elemento neutro é único.
Homomorfismos e Isomorfismos • •
Entre conjuntos temos funções f:C → D Entre estruturas matemáticas ou álgebras ou categorias temos morfismos h: →
•
Dados duas Álgebras A= e 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)
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:
• •
P1: ({1,2,3,6}, x divide y)
•
P2: (P({1,2}), x⊆y)
Isomorfismo • •
Seja f:: {1,2,3,6} → P({1,2}) definida por:
•
f(1) = ∅;
f(2) = {1};
f(3) = {2};
6
f(6) = {1,2} {1,2}
f 2
3
{1}
1
f é um isomorfismo de P1 em P2
{2}
∅
Isomorfismo de álgebras booleanas • Sejam A = e B = duas álgebras booleanas. Um morfismo f: A → B é dita ser um isomorfismo de A em B, se para todo x e y ∈A: – – –
f é uma bijeção f(x+y) = f(x) & f(y) f(x.y) = f(X) * f(y)
–
f(x’) = f(x)”
Isomorfismo
x,y ∈B
operação (+, ., ‘)
f
u,w∈A
z ∈B
f-1
operação (&, *, “)
v ∈A
Exercício Sejam C = <{0, 1, a, b}, +, ·, “, 0, 1>, onde as operações são dadas pelas tabelas ao lado, e B = duas álgebras booleanas.
Mostre que a função f:{0,1,a,b} → P({1,2}) dada por: f(0) = ∅ f(1) = {1,2} f(a) = {1} f(b) = {2} é um isomorfismo de C em 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
Teorema de álgebras booleanas finitas Seja B qualquer álgebra booleana com |B|=n elementos. Então, n = 2m, para algum m, e B é isomorfa a P({1,2,...,m}). Obs.: o número de elementos do domínio de qualquer álgebra booleana é uma potência de 2.
Outras estruturas algébricas Seja S um conjunto e * uma operação binária : * : S x S → S. • A operação * é associativa se: x * (y * z) = (x * y) * z, para quaisquer x, y e z ∈ S. • A operação . é comutativa se: x * y = y * x, para todo x e y ∈ S. • S tem um elemento neutro em relação à operação * se: existe i ∈ S tal que para todo x ∈ S, x * i = x = i * x . • Todo elemento tem um inverso em relação à operação * se: para todo x ∈ S existe x-1 ∈ S tal que x * x-1 = i = x-1 * x . Ex.: As estruturas < Z, + >, < Z, . >.
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: •
a operação * é associativa;
• •
S tem um elemento neutro em relação à operação * ; todo elemento de S tem um elemento inverso em relação à operação *
→ Se valer só a associatividade temos um semi-grupo. → Obs. Um grupo no qual a operação de grupo chamado de grupo comutativo ou abeliano. → A estrutura < Z, + > é um grupo comutativo.
* é comutativa é
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.
Exercícios •
< R, . > é um grupo ? É semi-grupo?
•
< Z, - > é um grupo ? É semi-grupo?
•
Seja M2(Z) o conjunto das matrizes 2x2 de elementos inteiros e seja + a operação de adição de matrizes. Mostre que < M2(Z), + > é um grupo comutativo. Mostre que < M2(Z), . > não é um grupo.
•
Temos e . Como será ??
Anel → Uma álgebra G = < S, +, * > é um anel se valem as seguintes propriedades: • < S, + > é um grupo abeliano; • < S, * > é um semi-grupo; • Vale a distributividade a esquerda e a direita entre as operações, 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)
Corpo → Uma álgebra G = < S, +, * > é um corpo se valem as seguintes propriedades: • < S, + , * > é um anel; • < S-{0}, * > é um grupo comutativo; • Vale a distributividade a esquerda e a direita entre as operações, ou seja, a*(b+c)= a*b + a*c e (a+b)*c = a*c + a*c Exemplos: Q, R, C com + e . são corpos. → Dado um corpo < S, +, * >, podemos definir a diferença e a divisão como → a - b = a + (-b) e a / b = a * b-1
Operadores externos → Dado um conjunto S uma operação externa * de um domínio K sobre S é uma função: • * : K x S → S, ou seja k*a = b ; • Operações externas de um anel podem ser combinadas com operações internas em um grupo <S, + >: → k * (a + b) = k*a + k*b → (k + s)* a = k * a + s * a → (k . s) * a = k*(s*a) →1*a=a Que da origem a estrutura de Módulo
Exercícios Propriedades: <S,*> Exemplos: * é fechada se x * y está em S • grupo A – associativa x * (y * z) = (x * y) * z • comutativo C – comutativa x * y = y * x • <M2(Z), +> comutativo N – neutro ou identidade x * i = i * x = x • comutativo I – inverso x * x-1 = x-1 * x = i • monóide • comutativo A → semi-grupo • comutativo AN → monóide • comutativo ANI → grupo • comutativo ACNI → grupo comutativo • <M2(Z), . > não-comutativo • semi-grupo • comutativo
Exercícios Propriedades: <S,*> Exemplos: * é fechada se x * y está em S • grupo A – associativa x * (y * z) = (x * y) * z • comutativo C – comutativa x * y = y * x • monóide N – neutro ou identidade x * i = i * x = x • comutativo I – inverso x * x-1 = x-1 * x = i • < Σ*, ||> não-comutativo A → semi-grupo AN → monóide ANI → grupo ACNI → grupo comutativo
• • semi-grupo •
Exercícios Propriedades: * é 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 D-distributivo a.(b+c)= a.b + a.c (a+b)*c = a*c + b*c Dado <S,+,*> é um: Anel se <S, +> grupo comutativo (ACNI) <S, *> semi-grupo (A) vale D Corpo se é um anel e < S-{0}, * > é um grupo Corpo comutativo se é um corpo e * é comutativa
Exemplos: • anel • comutativo • corpo • comutativo • <M2(Z), +, . > não-comut. • •
comutativo
• Em uma Álgebra de Boole e são monóides comutativos
Estruturas Matemáticas • Modelos matemáticos de fenômenos da natureza podem ser divididos em três grandes categorias: • Estruturas de Ordem
• Estruturas Algébricas
• Estruturas Topológicas (Geometria, Análise)
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 =
Estruturas Algébricas •
Estruturas Algébricas - Operações:
Uma operação (interna) * sobre um conjunto C, é uma função *:C×.. × C → C Exemplos: A =
B =
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 = < R2, N, *>, com *: N → R2, dado por *(k,(x,y)) = (kx,ky)
Estruturas Algébricas
• DEFINIÇÃO: • Uma Álgebra é um par
Estruturas Algébricas Propriedades das operações: - Dado uma álgebra
(comutativa)
(x * y) * z = x * (y * z)
(associativa)
∃ 1∈C (x * 1 = x)
(identidade)
∀x ∈C ∃ x-1 ∈C (x * x-1 = 1)
(inverso)
Se houver outra operação + em C, ou seja, temos
(distributiva)
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).
Álgebra Booleana → Uma Álgebra de Boole B é uma estrutura algébrica B =
1a. x+y = y+x 2a. (x+y)+z = x+(y+z) 3a. x+(y · z) = (x+y)·(x+z) 4a. x+a = x 5a. x+x’ = b
1b. x · y = y · x 2b. (x · y) ·.z = x · (y · z) 3b. x · (y+z) = (x · y)+(x · z) 4b. x · b = x 5b. x · x’ = a
Á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 =
Exercícios •
Demonstre as seguintes propriedades para uma álgebra de Boole B =
2. x+x = x, para todo x ∈ B (Idempotência) 3. x+b = b, para todo x ∈ B 4. (x ’) ’ = x, para todo x ∈ B 5. x+(x · y) = x, para todo x, y ∈ B 6. (x+y)’ = x ’ · y ’ (Lei de De Morgan) 7. O elemento neutro é único.
Homomorfismos e Isomorfismos • •
Entre conjuntos temos funções f:C → D Entre estruturas matemáticas ou álgebras ou categorias temos morfismos h:
•
Dados duas Álgebras A=
•
h(a *A b) = h(a) *B h(b)
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:
• •
P1: ({1,2,3,6}, x divide y)
•
P2: (P({1,2}), x⊆y)
Isomorfismo • •
Seja f:: {1,2,3,6} → P({1,2}) definida por:
•
f(1) = ∅;
f(2) = {1};
f(3) = {2};
6
f(6) = {1,2} {1,2}
f 2
3
{1}
1
f é um isomorfismo de P1 em P2
{2}
∅
Isomorfismo de álgebras booleanas • Sejam A =
f é uma bijeção f(x+y) = f(x) & f(y) f(x.y) = f(X) * f(y)
–
f(x’) = f(x)”
Isomorfismo
x,y ∈B
operação (+, ., ‘)
f
u,w∈A
z ∈B
f-1
operação (&, *, “)
v ∈A
Exercício Sejam C = <{0, 1, a, b}, +, ·, “, 0, 1>, onde as operações são dadas pelas tabelas ao lado, e B =
Mostre que a função f:{0,1,a,b} → P({1,2}) dada por: f(0) = ∅ f(1) = {1,2} f(a) = {1} f(b) = {2} é um isomorfismo de C em 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
Teorema de álgebras booleanas finitas Seja B qualquer álgebra booleana com |B|=n elementos. Então, n = 2m, para algum m, e B é isomorfa a P({1,2,...,m}). Obs.: o número de elementos do domínio de qualquer álgebra booleana é uma potência de 2.
Outras estruturas algébricas Seja S um conjunto e * uma operação binária : * : S x S → S. • A operação * é associativa se: x * (y * z) = (x * y) * z, para quaisquer x, y e z ∈ S. • A operação . é comutativa se: x * y = y * x, para todo x e y ∈ S. • S tem um elemento neutro em relação à operação * se: existe i ∈ S tal que para todo x ∈ S, x * i = x = i * x . • Todo elemento tem um inverso em relação à operação * se: para todo x ∈ S existe x-1 ∈ S tal que x * x-1 = i = x-1 * x . Ex.: As estruturas < Z, + >, < Z, . >.
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: •
a operação * é associativa;
• •
S tem um elemento neutro em relação à operação * ; todo elemento de S tem um elemento inverso em relação à operação *
→ Se valer só a associatividade temos um semi-grupo. → Obs. Um grupo no qual a operação de grupo chamado de grupo comutativo ou abeliano. → A estrutura < Z, + > é um grupo comutativo.
* é comutativa é
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.
Exercícios •
< R, . > é um grupo ? É semi-grupo?
•
< Z, - > é um grupo ? É semi-grupo?
•
Seja M2(Z) o conjunto das matrizes 2x2 de elementos inteiros e seja + a operação de adição de matrizes. Mostre que < M2(Z), + > é um grupo comutativo. Mostre que < M2(Z), . > não é um grupo.
•
Temos
Anel → Uma álgebra G = < S, +, * > é um anel se valem as seguintes propriedades: • < S, + > é um grupo abeliano; • < S, * > é um semi-grupo; • Vale a distributividade a esquerda e a direita entre as operações, 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)
Corpo → Uma álgebra G = < S, +, * > é um corpo se valem as seguintes propriedades: • < S, + , * > é um anel; • < S-{0}, * > é um grupo comutativo; • Vale a distributividade a esquerda e a direita entre as operações, ou seja, a*(b+c)= a*b + a*c e (a+b)*c = a*c + a*c Exemplos: Q, R, C com + e . são corpos. → Dado um corpo < S, +, * >, podemos definir a diferença e a divisão como → a - b = a + (-b) e a / b = a * b-1
Operadores externos → Dado um conjunto S uma operação externa * de um domínio K sobre S é uma função: • * : K x S → S, ou seja k*a = b ; • Operações externas de um anel
Exercícios Propriedades: <S,*> Exemplos: * é fechada se x * y está em S • grupo A – associativa x * (y * z) = (x * y) * z •
Exercícios Propriedades: <S,*> Exemplos: * é fechada se x * y está em S • grupo A – associativa x * (y * z) = (x * y) * z •
• • semi-grupo •
Exercícios Propriedades: * é 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 D-distributivo a.(b+c)= a.b + a.c (a+b)*c = a*c + b*c Dado <S,+,*> é um: Anel se <S, +> grupo comutativo (ACNI) <S, *> semi-grupo (A) vale D Corpo se é um anel e < S-{0}, * > é um grupo Corpo comutativo se é um corpo e * é comutativa
Exemplos: • anel •
comutativo
• Em uma Álgebra de Boole
More Documents from "uschiel"
